首页 > 代码库 > こだわり者いろはちゃん / Iroha's Obsession （暴力枚举）

こだわり者いろはちゃん / Iroha's Obsession （暴力枚举）

2024-11-17 11:27:39   203人阅读

题目链接：http://abc042.contest.atcoder.jp/tasks/arc058_a

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

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 KD1 D2 … DK

Output

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

Sample Input 1

Copy
1000 81 3 4 5 6 7 8 9

Sample Output 1

Copy
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

Copy
9999 10

Sample Output 2

Copy
9999

 题解：大致意思就是不能用出现过的数字组合去付钱 数据很小那就尽情暴力枚举吧 每次判断一下是否存在不喜欢的数

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 #include <cstdlib> 7 #include <iomanip> 8 #include <cmath> 9 #include <ctime>10 #include <map>11 #include <set>12 #include <queue>13 using namespace std;14 #define lowbit(x) (x&(-x))15 #define max(x,y) (x>y?x:y)16 #define min(x,y) (x<y?x:y)17 #define MAX 10000000000000000018 #define MOD 100000000719 #define pi acos(-1.0)20 #define ei exp(1)21 #define PI 3.14159265358979323846222 #define INF 0x3f3f3f3f3f23 #define mem(a) (memset(a,0,sizeof(a)))24 typedef long long ll;25 ll gcd(ll a,ll b){26     return b?gcd(b,a%b):a;27 }28 bool cmp(int x,int y)29 {30     return x>y;31 }32 const int N=10005;33 const int mod=1e9+7;34 int a[10];35 int prim(int n)36 {37     int b,flag=1;38     while(n){39         b=n%10;40         if(a[b]){41             flag=0;42             break;43         }44         n/=10;45     }46     if(flag) return 1;47     return 0;48 }49 int main()50 {51     std::ios::sync_with_stdio(false);52     int n,k,s,t;53     cin>>n>>k;54     mem(a);55     for(int i=0;i<k;i++){56         cin>>t;57         a[t]=1;58     }59     for(int i=n; ;i++){60         if(prim(i)){61             cout<<i<<endl;62             break;63         }64     }65     return 0;66 }

こだわり者いろはちゃん / Iroha's Obsession （暴力枚举）


联系
我们