こだわり者いろはちゃんIroha's Obsession（AtCoder-1973）

admin管理员组

文章数量:1571378

Problem Description

Iroha is very particular about numbers. There are K digits that she dislikes: D1,D2,…,DK.

She is shopping, and now paying at the cashier. Her total is N yen (the currency of Japan), thus she has to hand at least N yen to the cashier (and possibly receive the change).

However, as mentioned before, she is very particular about numbers. When she hands money to the cashier, the decimal notation of the amount must not contain any digits that she dislikes. Under this condition, she will hand the minimum amount of money.

Find the amount of money that she will hand to the cashier.

Constraints

1≦N<10000
1≦K<10
0≦D1<D2<…<DK≦9
{D1,D2,…,DK}≠{1,2,3,4,5,6,7,8,9}

Input

The input is given from Standard Input in the following format:

N K
D1 D2 … DK

Output

Print the amount of money that Iroha will hand to the cashier.

Example

Sample Input 1

1000 8
1 3 4 5 6 7 8 9

Sample Output 1

2000

She dislikes all digits except 0 and 2.

The smallest integer equal to or greater than N=1000 whose decimal notation contains only 0 and 2, is 2000.

Sample Input 2

9999 1
0

Sample Output 2

9999

题意：给出 k 个数字 di，以及一个数字 n，现在要找出一个比 n 大的最小的数字且这个数字不包括 k 个数字 di

思路：数据范围很小，直接暴力枚举即可

在读入 k 个数字的时候使用桶排，然后再从 n 开始枚举，不断分解数位判断即可

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 4000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
bool vis[10];
bool judge(int x){
    while(x){
        int temp=x%10;
        if(vis[temp])
            return false;
        x/=10;
    }
    return true;
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);

    memset(vis,false,sizeof(vis));
    for(int i=1; i<=k; i++){
        int x;
        scanf("%d",&x);
        vis[x]=true;
    }

    for(int i=n; ; i++){
        if(judge(i)){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

本文标签： ObsessionIrohaAtCoder