Changing Digits（dfs）

Problem Description

Given two positive integers n and k, you are asked to generate a new integer, say m, by changing some (maybe none) digits of n, such that the following properties holds:

m contains no leading zeros and has the same length as n (We consider zero itself a one-digit integer without leading zeros.)
m is divisible by k
among all numbers satisfying properties 1 and 2, m would be the one with least number of digits different from n
among all numbers satisfying properties 1, 2 and 3, m would be the smallest one

Input

There are multiple test cases for the input. Each test case consists of two lines, which contains n(1≤n≤10¹⁰⁰) and k(1≤k≤10⁴, k≤n) for each line. Both n and k will not contain leading zeros.

Output

Output one line for each test case containing the desired number m.

Sample Input

2 2 619103 3219

Sample Output

2 119103

***************************************************************************************************************************

【题意】

给出n和k，求一个数m，m是满足所有以下4个条件的数：（1）与n位数相同（2）能被k整除（3）与n相同位的数不相同最少（4）满足以上3个条件的最小值。其中 1≤n≤10¹⁰⁰ ， 1≤k≤10⁴, k≤n

***************************************************************************************************************************

 1 #inc;ude<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int mod[110][10],test[110],nu[110],f[110][12000];
 6 char str[110];
 7 int k,len;
 8 void init()
 9 {
10     int i,j;
11     for(i=0;i<10;i++)mod[0][i]=i%k;
12     for(i=1;i<len;i++)
13     {
14         for(j=0;j<10;j++)
15         {
16             mod[i][j]=(mod[i-1][j]*10)%k;
17         }
18     }
19     memset(f,0,sizeof(f));
20 }
21 bool DFS(int pos,int num,int m )
22 {
23 
24     int i,j;
25     if(m==0)
26     {
27         for(i=len-1;i>=0;i--)printf("%d",test[i]);
28         printf("
");
29         return true;
30     }
31     if(pos<0||num<=f[pos][m]||num==0)return false;
32     for(i=pos;i>=0;i--)
33     {
34         for(j=0;j<nu[i];j++)//从后想前求小值
35         {
36             if(i==len-1&&j==0)continue;
37             test[i]=j;
38             int a=(m-(mod[i][nu[i]]-mod[i][j])+k)%k;
39 
40             if(DFS(i-1,num-1,a))return true;
41 
42         }
43         test[i]=nu[i];
44     }
45     for(i=0;i<=pos;i++)//从尾向高位求小值
46     {
47         for(j=nu[i]+1;j<10;j++)
48         {
49             if(i==len-1&&j==0)continue;
50             test[i]=j;
51             int a=(m+(mod[i][j]-mod[i][nu[i]]))%k;
52             if(DFS(i-1,num-1,a))return true;
53 
54         }
55         test[i]=nu[i];
56     }
57     f[pos][m]=num;//记录改变后的值
58     return false;
59 
60 }
61 void solve()
62 {
63     int i;
64     int m=0;
65     for(i=0;i<len;i++)
66     {
67          test[i]=nu[i]=str[len-i-1]-'0';
68          m+=mod[i][nu[i]];
69          m%=k;
70     }
71     for(i=1;i<=len;i++)
72     {
73         if(DFS(len-1,i,m))return;
74     }
75 }
76 int main()
77 {
78     while(scanf("%s",str)!=EOF)
79     {
80         scanf("%d",&k);
81          len=strlen(str);
82         init();
83         solve();
84     }
85 }

View Code