[UVA][dfs] 10624 - Super Number
Problem B
Super Number
Input:
Standard Input
Output: Standard Output
Time Limit: 3 Seconds
Don't you think 162456723 very special? Look at the picture below if you are unable to find its speciality. (a | b means ‘b is divisible by a’)
Figure: Super Numbers
Given n, m (0 < n < m < 30), you are to find a m-digit positive integer X such that for every i (n <= i <= m), the first i digits of X is a multiple of i. If more than one such X exists, you should output the lexicographically smallest one. Note that the first digit of X should not be 0.
Input
Output
For each test case, print the case number and X. If no such number, print -1.
Sample Input Output for Sample Input
2 1 10 3 29 |
Case 1: 1020005640 Case 2: -1
|
Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel
Special Thanks to:
Monirul Hasan (Alternate solution)
Shahriar Manzoor (Figure Drawing)
注意小細節, 2000+ms 通過
#include <stdio.h>
int find, n, m;
int N[50];
int div(int len, int j) {
static int i, tmp;
for(i = 1, tmp = 0; i < len; i++) {
tmp = tmp*10 + N[i];
tmp %= len;
}
tmp = tmp*10 + j;
return tmp%len;
}
void dfs(int idx) {
if(find) return;
int i, j = 1;
if(idx == m+1) {
find = 1;
for(i = 1; i <= m; i++)
printf("%d", N[i]);
return;
}
for(i = (idx == 1); i < 10; i += j) {
if(idx >= n && div(idx, i) == 0) {
N[idx] = i;
j = idx;
dfs(idx+1);
} else if(idx < n) {
N[idx] = i;
dfs(idx+1);
}
}
}
int main() {
int t, cases = 0;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
printf("Case %d: ", ++cases);
find = 0;
dfs(1);
if(!find) puts("-1");
else puts("");
}
return 0;
}