2012-10-06 19:53:03Morris
[UVA][Greedy] 10527 - Persistent Numbers
Problem B: Persistent Numbers
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 |
| 3 | 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 |
| 4 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 |
| 5 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 |
| 6 | 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 |
| 7 | 7 | 14 | 21 | 28 | 35 | 42 | 49 | 56 | 63 |
| 8 | 8 | 16 | 24 | 32 | 40 | 48 | 56 | 64 | 72 |
| 9 | 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 |
679 -> 378 -> 168 -> 48 -> 32 -> 6.
The problem that you are to solve here is: what is the smallest number such that the first step of computing its persistence results in the given number?
For each test case there is a single line of input containing a decimal number with up to 1000 digits. A line containing -1 follows the last test case. For each test case you are to output one line containing one integer number satisfying the condition stated above or a statement saying that there is no such number in the format shown below.
Sample input
0 1 4 7 18 49 51 768 -1
Output for sample input
10 11 14 17 29 77 There is no such number. 2688
P. Rudnicki
找一個最小的數字其每個位數相乘會等於 n, 個位數字特別討論,
接著從 9 開始試除直到 2, 如果仍然除不等於1則輸出無解
#include <stdio.h>
#include <stdlib.h>
int main() {
char s[3005];
int i, j;
while(gets(s)) {
if(s[0] == '-') break;
if(s[1] == '\0') {
printf("1%s\n", s);
continue;
}
for(i = 0; s[i]; i++) s[i] -= '0';
int len = i, idx = 0, st = 0;
char stk[3005];
for(i = 9; i >= 2; i--) {
while(1) {
int mod = 0;
for(j = st; j < len; j++) {
mod = mod*10 + s[j];
mod %= i;
}
if(!mod) {
stk[idx++] = i+'0';
mod = 0;
for(j = st; j < len; j++) {
mod = mod*10 + s[j];
s[j] = mod/i;
mod %= i;
}
while(s[st] == 0) st++;
} else break;
}
}
if(st == len-1 && s[st] == 1) {
for(i = idx-1; i >= 0; i--)
putchar(stk[i]);
puts("");
} else
puts("There is no such number.");
}
return 0;
}