Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
日本の誇る美しいリズムとして、五七五というものがあります。いろはちゃんは五七五が大好きです。
3 つの文節の並びの長さがそれぞれ 5,7,5 となるようにこの順番で並んでいるとき、その 3 つの文節の並びは五七五であると言います。
並び替えたい 3 つの文節の長さを表す整数 A,B,C が与えられるので、それらの文節を並び替えて五七五にできるか判定してください。
制約
- 1≦A,B,C≦10
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
文節の並びを五七五にすることができるなら YES 、そうでないなら NO を出力せよ。
入力例 1
5 5 7
出力例 1
YES
与えられる文節の長さはそれぞれ 5,5,7 であり、5,7,5 となるように文節を並び替えることができます。したがって、文節の並びを五七五にすることは可能といえます。
入力例 2
7 7 5
出力例 2
NO
Score : 100 points
Problem Statement
Iroha loves Haiku. Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.
To create a Haiku, Iroha has come up with three different phrases. These phrases have A, B and C syllables, respectively. Determine whether she can construct a Haiku by using each of the phrases once, in some order.
Constraints
- 1≦A,B,C≦10
Input
The input is given from Standard Input in the following format:
A B C
Output
If it is possible to construct a Haiku by using each of the phrases once, print YES (case-sensitive). Otherwise, print NO.
Sample Input 1
5 5 7
Sample Output 1
YES
Using three phrases of length 5, 5 and 7, it is possible to construct a Haiku.
Sample Input 2
7 7 5
Sample Output 2
NO
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
いろはちゃんは 長さ L の文字列を N 個持っており、それぞれ S_1, S_2, ..., S_N です。
それらの文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを求めてください。
なお、ある文字列 s=s_1s_2s_3...s_n と t=t_1t_2t_3...t_m について、以下のどちらかを満たすとき、辞書順比較で s<t であるといいます。
- ある整数 i(1≦i≦min(n,m)) に関して、 1≦j<i を満たす任意の整数 j において s_j = t_j が成立し、かつ s_i<t_i が成立する。
- 任意の整数 i(1≦i≦min(n,m)) に関して s_i = t_i が成立し、かつ n<m が成立する。
制約
- 1 ≦ N, L ≦ 100
- 全ての i (1≦i≦N) に対し、S_i の長さは L に等しい。
- 各 i について, S_i は全て半角英小文字のみから成る文字列である。
入力
入力は以下の形式で標準入力から与えられる。
N L S_1 S_2 : S_N
出力
与えられる文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを出力せよ。
入力例 1
3 3 dxx axx cxx
出力例 1
axxcxxdxx
与えられた文字列を axx,cxx,dxx という順番に並び替えてから結合することで、辞書順最小を達成できます。
Score : 200 points
Problem Statement
Iroha has a sequence of N strings S_1, S_2, ..., S_N. The length of each string is L.
She will concatenate all of the strings in some order, to produce a long string.
Among all strings that she can produce in this way, find the lexicographically smallest one.
Here, a string s=s_1s_2s_3...s_n is lexicographically smaller than another string t=t_1t_2t_3...t_m if and only if one of the following holds:
- There exists an index i(1≦i≦min(n,m)), such that s_j = t_j for all indices j(1≦j<i), and s_i<t_i.
- s_i = t_i for all integers i(1≦i≦min(n,m)), and n<m.
Constraints
- 1 ≦ N, L ≦ 100
- For each i, the length of S_i equals L.
- For each i, S_i consists of lowercase letters.
Input
The input is given from Standard Input in the following format:
N L S_1 S_2 : S_N
Output
Print the lexicographically smallest string that Iroha can produce.
Sample Input 1
3 3 dxx axx cxx
Sample Output 1
axxcxxdxx
The following order should be used: axx, cxx, dxx.
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