Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
いろはちゃんはこだわりもので、嫌いな数字が K 個あり、それぞれ D_1, D_2, ..., D_K です。
いろはちゃんはお店でお買い物をしていて、 N 円の品物を買おうとしています。 もちろん、この品物は N 円以上のお金を支払えば買うことができます。 しかし、先ほど述べたようにいろはちゃんは強いこだわりがあるので、自分がお店に支払う金額の 10 進表記にいろはちゃんの嫌いな数字が出現しないような最も少ない金額を支払おうとします。
いろはちゃんが支払う金額を求めてください。
制約
- 1 ≦ N < 10000
- 1 ≦ K < 10
- 0 ≦ D_1 < D_2 < … < D_K≦9
- \{D_1,D_2,...,D_K\} ≠ \{1,2,3,4,5,6,7,8,9\}
入力
入力は以下の形式で標準入力から与えられる。
N K D_1 D_2 … D_K
出力
いろはちゃんが支払う金額を出力せよ。
入力例 1
1000 8 1 3 4 5 6 7 8 9
出力例 1
2000
嫌いでない数字は 0 と 2 のみです。
N=1000 以上の整数で、桁に 0 と 2 のみが含まれる最小の整数は 2000 なのでそれを出力してください。
入力例 2
9999 1 0
出力例 2
9999
Score : 300 points
Problem Statement
Iroha is very particular about numbers. There are K digits that she dislikes: D_1, D_2, ..., D_K.
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 ≦ D_1 < D_2 < … < D_K≦9
- \{D_1,D_2,...,D_K\} ≠ \{1,2,3,4,5,6,7,8,9\}
Input
The input is given from Standard Input in the following format:
N K D_1 D_2 … D_K
Output
Print the amount of money that Iroha will hand to the cashier.
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
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
縦 H マス、横 W マスのマス目があります。 いろはちゃんは、今一番左上のマス目にいます。 そして、右か下に1マス移動することを繰り返し、一番右下のマス目へと移動します。 ただし、下から A 個以内、かつ左から B 個以内のマス目へは移動することは出来ません。
移動する方法は何通りあるか求めてください。
なお、答えは非常に大きくなることがあるので、答えは 10^9+7 で割ったあまりを出力してください。
制約
- 1 ≦ H, W ≦ 100,000
- 1 ≦ A < H
- 1 ≦ B < W
入力
入力は以下の形式で標準入力から与えられる。
H W A B
出力
移動する方法の数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
2 3 1 1
出力例 1
2
2×3 マスありますが、左下の 1 マスには移動することができません。「右右下」、「右下右」という 2 つの移動の仕方があります。
入力例 2
10 7 3 4
出力例 2
3570
移動できないマスが 12 マスあります。
入力例 3
100000 100000 99999 99999
出力例 3
1
入力例 4
100000 100000 44444 55555
出力例 4
738162020
Score : 400 points
Problem Statement
We have a large square grid with H rows and W columns. Iroha is now standing in the top-left cell. She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.
However, she cannot enter the cells in the intersection of the bottom A rows and the leftmost B columns. (That is, there are A×B forbidden cells.) There is no restriction on entering the other cells.
Find the number of ways she can travel to the bottom-right cell.
Since this number can be extremely large, print the number modulo 10^9+7.
Constraints
- 1 ≦ H, W ≦ 100,000
- 1 ≦ A < H
- 1 ≦ B < W
Input
The input is given from Standard Input in the following format:
H W A B
Output
Print the number of ways she can travel to the bottom-right cell, modulo 10^9+7.
Sample Input 1
2 3 1 1
Sample Output 1
2
We have a 2×3 grid, but entering the bottom-left cell is forbidden. The number of ways to travel is two: "Right, Right, Down" and "Right, Down, Right".
Sample Input 2
10 7 3 4
Sample Output 2
3570
There are 12 forbidden cells.
Sample Input 3
100000 100000 99999 99999
Sample Output 3
1
Sample Input 4
100000 100000 44444 55555
Sample Output 4
738162020
Time Limit: 4 sec / Memory Limit: 512 MB
配点 : 700 点
問題文
日本の誇る美しいリズムとして、五七五というものがあります。 いろはちゃんは、数列から五七五を探すことにしました。でもこれは簡単だったので、XYZを探すことにしました。
長さ N の、それぞれの値が 1~10 の数列 a_0, a_1, ..., a_{N-1} を考えます。このような数列は全部で 10^N 通りありますが、そのうちXYZを含むものは何通りでしょう?
ただし、XYZを含むとは以下のように定義されます。
- a_x + a_{x+1} + ... + a_{y-1} = X
- a_y + a_{y+1} + ... + a_{z-1} = Y
- a_z + a_{z+1} + ... + a_{w-1} = Z
を満たす 0 ≦ x < y < z < w ≦ N が存在する。
なお、答えは非常に大きくなることがあるので、答えは 10^9+7 で割ったあまりを出力してください。
制約
- 3 ≦ N ≦ 40
- 1 ≦ X ≦ 5
- 1 ≦ Y ≦ 7
- 1 ≦ Z ≦ 5
入力
入力は以下の形式で標準入力から与えられる。
N X Y Z
出力
XYZを含む数列の個数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
3 5 7 5
出力例 1
1
\{5,7,5\} という数列のみが条件を満たします。
入力例 2
4 5 7 5
出力例 2
34
入力例 3
37 4 2 3
出力例 3
863912418
入力例 4
40 5 7 5
出力例 4
562805100
Score : 700 points
Problem Statement
Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.
Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.
Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?
Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to contain an X,Y,Z-Haiku if and only if there exist four indices x, y, z, w (0 ≦ x < y < z < w ≦ N) such that all of the following are satisfied:
- a_x + a_{x+1} + ... + a_{y-1} = X
- a_y + a_{y+1} + ... + a_{z-1} = Y
- a_z + a_{z+1} + ... + a_{w-1} = Z
Since the answer can be extremely large, print the number modulo 10^9+7.
Constraints
- 3 ≦ N ≦ 40
- 1 ≦ X ≦ 5
- 1 ≦ Y ≦ 7
- 1 ≦ Z ≦ 5
Input
The input is given from Standard Input in the following format:
N X Y Z
Output
Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.
Sample Input 1
3 5 7 5
Sample Output 1
1
Here, the only sequence that contains a 5,7,5-Haiku is [5, 7, 5].
Sample Input 2
4 5 7 5
Sample Output 2
34
Sample Input 3
37 4 2 3
Sample Output 3
863912418
Sample Input 4
40 5 7 5
Sample Output 4
562805100
Time Limit: 5 sec / Memory Limit: 750 MB
配点 : 1500 点
問題文
いろはちゃんは N 個の文字列 s_1, s_2, ..., s_N を持っています。
いろはちゃんは、この中からいくつか文字列を選びます。そして添字の昇順で選んだ文字列を繋げ、長さ K の文字列を作ります。
作れる長さ K の文字列のうち、もっとも辞書順で小さいものを求めてください。
制約
- 1 ≦ N ≦ 2000
- 1 ≦ K ≦ 10^4
- 1 ≦ |s_i| ≦ K
- |s_1| + |s_2| + ... + |s_N| ≦ 10^6
- 各 i について, s_i は全て半角英小文字のみから成る文字列である。
- 長さ K の文字列を作る方法が存在することが保証される。
入力
入力は以下の形式で標準入力から与えられる。
N K s_1 s_2 : s_N
出力
作れる長さ K の文字列のうち、もっとも辞書順で小さいものを出力せよ。
入力例 1
3 7 at coder codar
出力例 1
atcodar
at
と codar
を選択します。
入力例 2
3 7 coder codar at
出力例 2
codarat
codar
と at
を選択します。
入力例 3
4 13 kyuri namida zzzzzzz aaaaaa
出力例 3
namidazzzzzzz
namida
と zzzzzzz
を選択します。
Score : 1500 points
Problem Statement
Iroha has a sequence of N strings s_1, s_2, ..., s_N.
She will choose some (possibly all) strings from the sequence, then concatenate those strings retaining the relative order, to produce a long string.
Among all strings of length K that she can produce in this way, find the lexicographically smallest one.
Constraints
- 1 ≦ N ≦ 2000
- 1 ≦ K ≦ 10^4
- For each i, 1 ≦ |s_i| ≦ K.
- |s_1| + |s_2| + ... + |s_N| ≦ 10^6
- For each i, s_i consists of lowercase letters.
- There exists at least one string of length K that Iroha can produce.
Input
The input is given from Standard Input in the following format:
N K s_1 s_2 : s_N
Output
Print the lexicographically smallest string of length K that Iroha can produce.
Sample Input 1
3 7 at coder codar
Sample Output 1
atcodar
at
and codar
should be chosen.
Sample Input 2
3 7 coder codar at
Sample Output 2
codarat
codar
and at
should be chosen.
Sample Input 3
4 13 kyuri namida zzzzzzz aaaaaa
Sample Output 3
namidazzzzzzz
namida
and zzzzzzz
should be chosen.