[UVA][窮舉] 10396 - Vampire Numbers＠Morris' Blog

2013-12-01 11:27:41| 人氣1,485| 回應0 | 上一篇 | 下一篇

[UVA][窮舉] 10396 - Vampire Numbers

推薦 0 收藏 0 轉貼0 訂閱站台

Problem D

Vampire Numbers

Input: standard input

Output: standard output

Time Limit: 5 seconds

A number v = xy with an even number (n) of digits formed by multiplying a pair of n/2-digit numbers (where the digits are taken from the original number in any order) x and y together is known as vampire number. Pairs of trailing zeros (Both the numbers have a trailing zero) are not allowed. If v is a vampire number then x and y are called its "fangs." Examples of 4-digit vampire numbers include

1) 21 x 60 = 1260
2) 15 x 93 = 1395
3) 35 x 41 = 1435
4) 30 x 51 = 1530
5) 21 x 87 = 1827
6) 27 x 81 = 2187
7) 80 x 86 = 6880

In this program you will have to find all the 4, 6 and 8 digit even vampire numbers.

Input

The input file contains maximum ten lines of input. Each line contains a single integer n whose value is 4, 6 or 8. Input is terminated by end of file.

Output

For each input n produce all the n-digit vampire numbers that are even in ascending order. Print a blank line after the output for each set of input.

Sample Input:

Sample Output:

1260

1530

6880

1260

1530

6880

(Problem Setter: Shahriar Manzoor, CSE Dept, Southeast University, Dhaka)

Only the fool people reach their goals and stop. Those who are intelligent always

keep uplifting their goals and thus advance forward till death.

找吸血鬼數

而且這些吸血鬼數是偶數，且這兩個數字個別都不能以 0 做為結尾。

因此這題窮舉兩個數字相成之後進行檢查即可。
可以預先建造 10 到 10000 內的數字位數累計。

窮舉完後，要去除重複的吸血鬼數，否則會是錯誤的。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
char num[10000][10]={0};
vector<int> r[3];
void v4() {
   int i, j, k;
   for(i = 10; i < 100; i++) {
       for(j = i; j < 100; j++) {
           if((i*j)%2 || (i%10 == 0 && j%10 == 0))
               continue;
            int temp[10]={0}, tempn=i*j;
            while(tempn) {
                temp[tempn%10]++;
                tempn = tempn/10;
           }
            for(k = 0; k < 10; k++)
               if(temp[k] != num[i][k] + num[j][k])
                   break;
            if(k==10)
                r[0].push_back(i*j);
        }
    }
}void v6() {
   int i, j, k;
   for(i = 100; i < 1000; i++) {
       for(j = i; j < 1000; j++) {
           if((i*j)%2 || (i%10 == 0 && j%10 == 0))
               continue;
            int temp[10]={0}, tempn=i*j;
            while(tempn) {
                temp[tempn%10]++;
                tempn = tempn/10;
           }
            for(k = 0; k < 10; k++)
               if(temp[k] != num[i][k] + num[j][k])
                   break;
            if(k==10)
                r[1].push_back(i*j);
        }
    }
}void v8() {
   int i, j, k;
   for(i = 1000; i < 10000; i++) {
       for(j = i; j < 10000; j++) {
           if((i*j)%2 || (i%10 == 0 && j%10 == 0))
               continue;
            int temp[10]={0}, tempn=i*j;
            while(tempn) {
                temp[tempn%10]++;
                tempn = tempn/10;
           }
            for(k = 0; k < 10; k++)
               if(temp[k] != num[i][k] + num[j][k])
                   break;
            if(k==10)
                r[2].push_back(i*j);
        }
    }
}
int main() {
   int i, j, k, n;
    for(i = 11; i < 10000; i++) {
        n = i;
       while(n) {
             num[i][n%10]++;
             n = n/10;
        }
   }
   v4();
   v6();
   v8();
   sort(r[0].begin(), r[0].end());
   sort(r[1].begin(), r[1].end());
   sort(r[2].begin(), r[2].end());
   std::vector<int>::iterator it;
   for(i = 0; i < 3; i++) {
       it = std::unique (r[i].begin(), r[i].end());
       r[i].resize(std::distance(r[i].begin(), it));
   }
    while(scanf("%d",&n)==1) {
        n = n/2 - 2;
        for(i = 0; i < r[n].size(); i++)
            printf("%d\n", r[n][i]);
        puts("");
   }
    return 0;
}

我要檢舉

#10396#Vampire Numbers#窮舉

台長： Morris

您可能對以下文章有興趣

[UVA][greedy] 10570 - Meeting with Aliens

[UVA][數學] 11051 - Dihedral groups

[UVA] 10410 - Tree Reconstruction

[UVA][字串分析] 10442 - Basic

人氣(1,485) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][數學&窮舉] 10317 - Equating Equations
此分類上一篇:[UVA][bfs] 1341 - Different Digits

回應(0)