首页 > 代码库 > poj 3373

poj 3373

2024-07-17 22:13:55   216人阅读

Changing Digits
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 2960 Accepted: 952

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:

  1. m contains no leading zeros and has the same length as n (We consider zero itself a one-digit integer without leading zeros.)
  2. m is divisible by k
  3. among all numbers satisfying properties 1 and 2, m would be the one with least number of digits different from n
  4. 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≤10100) and k(1≤k≤104, 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

Source

POJ Monthly--2007.09.09, Rainer

参考(很详细)：http://blog.csdn.net/lyy289065406/article/details/6698787/
AC代码：
<pre name="code" class="cpp">#include<iostream>
#include<cstring>
using namespace std;
char s[105];
int n[105],m[105];
int k,n_mod;
int mod[105][10],f[105][10005];
int DFS(int pos,int res_num,int m_mod){
    if(m_mod==0)
        return 1;
    if(pos<0 || res_num==0)
        return 0;
    if(res_num<=f[pos][m_mod])
        return 0;
    for(int i=pos;i>=0;i--){
        for(int j=0;j<n[i];j++){
            if(i==strlen(s)-1 && j==0)
                continue;
            int res=(m_mod-(mod[i][m[i]]-mod[i][j])+k)%k;
            int tmp=m[i];
            m[i]=j;
            if(DFS(pos-1,res_num-1,res))
                return 1;
            m[i]=tmp;
        }
    }

    for(int i=0;i<=pos;i++){
        for(int j=n[i]+1;j<=9;j++){
            if(i==strlen(s)-1 && j==0)
                continue;
            int res=(m_mod-(mod[i][m[i]]-mod[i][j]))%k;
            int tmp=m[i];
            m[i]=j;
            if(DFS(pos-1,res_num-1,res))
                return 1;
            m[i]=tmp;
        }
    }
    f[pos][m_mod]=res_num;
    return 0;
}
int main(){
    while(cin>>s>>k){
        for(int i=0;i<strlen(s);i++)
            n[i]=m[i]=s[strlen(s)-1-i]-'0';

        for(int i=0;i<=9;i++)
            mod[0][i]=i%k;
        for(int i=1;i<strlen(s);i++)
            for(int j=0;j<=9;j++)
                mod[i][j]=(mod[i-1][j]*10)%k;

        n_mod=0;
        for(int i=0;i<strlen(s);i++){
            n_mod=(n_mod+mod[i][m[i]])%k;
        }
        memset(f,0,sizeof(f));

        for(int i=0;i<=strlen(s);i++){
            if(DFS(strlen(s)-1,i,n_mod))
                break;
        }
        for(int i=strlen(s)-1;i>=0;i--)
            cout<<m[i];
        cout<<endl;
    }
    return 0;
}

































        

            
                
                  
                
                

                    联系

                    我们