実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。
例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。
整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。
制約
- 100 \leq N \leq 919
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
320
出力例 1
326
320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。
入力例 2
144
出力例 2
144
144 は 326-like number です。
入力例 3
516
出力例 3
600
Score : 200 points
Problem Statement
A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.
For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.
Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.
Constraints
- 100 \leq N \leq 919
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
320
Sample Output 1
326
320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.
Sample Input 2
144
Sample Output 2
144
144 is a 326-like number.
Sample Input 3
516
Sample Output 3
600
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
AtCoder 国では、1 年が N か月からなる暦を使っています。 i 月 (1\leq i\leq N) は、i 月 1 日から i 月 D _ i 日までの D _ i 日からなります。
AtCoder 国において、1 年のうち日付がゾロ目になる日が何日あるか求めてください。
ただし、i 月 j 日 (1\leq i\leq N,1\leq j\leq D _ i) の日付がゾロ目になるとは、1 種類の数字だけを用いて i と j を十進法で表すことができることをいいます。
制約
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D _ 1 D _ 2 \ldots D _ N
出力
答えを出力せよ。
入力例 1
12 31 29 31 30 31 30 31 31 30 31 30 31
出力例 1
13
AtCoder 国では、 1 月 1 日、1 月 11 日、2 月 2 日、2 月 22 日、3 月 3 日、4 月 4 日、5 月 5 日、6 月 6 日、7 月 7 日、8 月 8 日、9 月 9 日、11 月 1 日、11 月 11 日の合計 13 日の日付がゾロ目になります。
入力例 2
10 10 1 2 3 4 5 6 7 8 100
出力例 2
1
AtCoder 国では、1 月 1 日のみが日付がゾロ目になります。
入力例 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
出力例 3
15
Score : 200 points
Problem Statement
AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.
How many days in a year of AtCoder have "repdigits" dates?
Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.
Constraints
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D _ 1 D _ 2 \ldots D _ N
Output
Print the answer.
Sample Input 1
12 31 29 31 30 31 30 31 31 30 31 30 31
Sample Output 1
13
In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 100
Sample Output 2
1
In AtCoder Kingdom, only January 1 has a repdigit date.
Sample Input 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
Sample Output 3
15
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
この問題は G 問題の簡易版です。
3 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。ここで、S_i は数字のみからなる長さ M の文字列です。
それぞれのリールには対応するボタンがついています。高橋君は各非負整数 t について、スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す、または何もしないことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、i 番目のリールは S_i の (t \bmod M)+1 文字目を表示して止まります。
ただし、t \bmod M で t を M で割ったあまりを表します。
高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
そのようなことが不可能であればそのことを報告してください。
制約
- 1 \leq M \leq 100
- M は整数
- S_i は数字のみからなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
M S_1 S_2 S_3
出力
全てのリールを止めた上で、表示されている文字が全て同じであるようにすることができないなら -1 を出力せよ。
できるなら、スロットが回り始めてからそのような状態にするまでに最小で何秒かかるか出力せよ。
入力例 1
10 1937458062 8124690357 2385760149
出力例 1
6
高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 6 秒後にリールに表示される文字を 8 で揃えることができます。
- スロットの回転開始から 0 秒後に 2 番目のリールに対応するボタンを押します。2 番目のリールは S_2 の (0 \bmod 10)+1=1 文字目である
8を表示して止まります。 - スロットの回転開始から 2 秒後に 3 番目のリールに対応するボタンを押します。3 番目のリールは S_3 の (2 \bmod 10)+1=3 文字目である
8を表示して止まります。 - スロットの回転開始から 6 秒後に 1 番目のリールに対応するボタンを押します。1 番目のリールは S_1 の (6 \bmod 10)+1=7 文字目である
8を表示して止まります。
5 秒以下で全てのリールに表示されている文字を揃える方法はないため、6 を出力します。
入力例 2
20 01234567890123456789 01234567890123456789 01234567890123456789
出力例 2
20
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
入力例 3
5 11111 22222 33333
出力例 3
-1
表示されている文字が全て同じであるようにリールを止めることはできません。
このとき -1 を出力してください。
Score : 300 points
Problem Statement
This problem is an easier version of Problem G.
There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.
Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.
Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.
Constraints
- 1 \leq M \leq 100
- M is an integer.
- S_i is a string of length M consisting of digits.
Input
The input is given from Standard Input in the following format:
M S_1 S_2 S_3
Output
If it is impossible to stop all the reels so that all the displayed characters are the same, print -1.
Otherwise, print the minimum possible number of seconds from the start of the spin until such a state is achieved.
Sample Input 1
10 1937458062 8124690357 2385760149
Sample Output 1
6
Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.
- Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays
8, the ((0 \bmod 10)+1=1)-st character of S_2. - Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays
8, the ((2 \bmod 10)+1=3)-rd character of S_3. - Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays
8, the ((6 \bmod 10)+1=7)-th character of S_1.
There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.
Sample Input 2
20 01234567890123456789 01234567890123456789 01234567890123456789
Sample Output 2
20
Note that he must stop all the reels and make them display the same character.
Sample Input 3
5 11111 22222 33333
Sample Output 3
-1
It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
6 個の整数 h_1, h_2, h_3, w_1, w_2, w_3 が与えられます。
縦横 3 \times 3 のマス目に、以下の条件をすべて満たすように各マスに正の整数を 1 つずつ書きこむことを考えます。
- i=1,2,3 について、上から i 行目に書きこんだ数の和が h_i になる。
- j=1,2,3 について、左から j 列目に書きこんだ数の和が w_j になる。
例えば (h_1, h_2, h_3) = (5, 13, 10), (w_1, w_2, w_3) = (6, 13, 9) のとき、以下の 3 通りの書きこみ方はすべて条件を満たしています。(条件を満たす書きこみ方は他にもあります)
さて、条件を満たす書きこみ方は全部で何通り存在しますか？
制約
- 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
h_1 h_2 h_3 w_1 w_2 w_3
出力
条件を満たす書きこみ方が何通りあるかを出力せよ。
入力例 1
3 4 6 3 3 7
出力例 1
1
条件を満たす数の書きこみ方は次の 1 通りのみです。よって 1 を出力します。
入力例 2
3 4 5 6 7 8
出力例 2
0
条件を満たす書きこみ方が存在しないこともあります。
入力例 3
5 13 10 6 13 9
出力例 3
120
入力例 4
20 25 30 22 29 24
出力例 4
30613
Score : 300 points
Problem Statement
You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:
- For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
- For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.
For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)
How many ways are there to write numbers to satisfy the conditions?
Constraints
- 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
h_1 h_2 h_3 w_1 w_2 w_3
Output
Print the number of ways to write numbers to satisfy the conditions.
Sample Input 1
3 4 6 3 3 7
Sample Output 1
1
The following is the only way to satisfy the conditions. Thus, 1 should be printed.
Sample Input 2
3 4 5 6 7 8
Sample Output 2
0
There may not be a way to satisfy the conditions.
Sample Input 3
5 13 10 6 13 9
Sample Output 3
120
Sample Input 4
20 25 30 22 29 24
Sample Output 4
30613
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
H 行 W 列の 2 つのグリッド A, B が与えられます。
1 \leq i \leq H と 1 \leq j \leq W を満たす各整数の組 (i, j) について、 i 行目 j 列目にあるマスをマス (i, j) と呼ぶとき、 グリッド A の マス (i, j) には整数 A_{i, j} が、 グリッド B の マス (i, j) には整数 B_{i, j} がそれぞれ書かれています。
あなたは「下記の 2 つのうちのどちらか 1 つを行う」という操作を好きな回数（ 0 回でもよい）だけ繰り返します。
- 1 \leq i \leq H-1 を満たす整数 i を選び、グリッド A の i 行目と (i+1) 行目を入れ替える。
- 1 \leq i \leq W-1 を満たす整数 i を選び、グリッド A の i 列目と (i+1) 列目を入れ替える。
上記の操作の繰り返しによって、グリッド A をグリッド B に一致させることが可能かどうかを判定してください。 さらに、一致させることが可能な場合は、そのために行う操作回数の最小値を出力してください。
ここで、グリッド A とグリッド B が一致しているとは、 1 \leq i \leq H と 1 \leq j \leq W を満たす全ての整数の組 (i, j) について、 グリッド A の マス (i, j) とグリッド B の マス (i, j) に書かれた整数が等しいこととします。
制約
- 入力される値は全て整数
- 2 \leq H, W \leq 5
- 1 \leq A_{i, j}, B_{i, j} \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}
出力
グリッド A をグリッド B に一致させることが不可能な場合は -1 を、
可能な場合はグリッド A をグリッド B に一致させるために行う操作回数の最小値を出力せよ。
入力例 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19
出力例 1
3
初期状態のグリッド A の 4 列目と 5 列目を入れ替えると、グリッド A は下記の通りになります。
1 2 3 5 4 6 7 8 10 9 11 12 13 15 14 16 17 18 20 19
続けて、グリッド A の 2 行目と 3 行目を入れ替えると、グリッド A は下記の通りになります。
1 2 3 5 4 11 12 13 15 14 6 7 8 10 9 16 17 18 20 19
最後に、グリッド A の 2 列目と 3 列目を入れ替えると、グリッド A は下記の通りになり、グリッド B に一致します。
1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19
上に述べた 3 回の操作でグリッド A をグリッド B に一致させることができ、 これより少ない回数の操作でグリッド A をグリッド B に一致させることはできないため、 3 を出力します。
入力例 2
2 2 1 1 1 1 1 1 1 1000000000
出力例 2
-1
問題文中の操作をどのように行ってもグリッド A をグリッド B に一致させることは不可能であるため -1 を出力します。
入力例 3
3 3 8 1 6 3 5 7 4 9 2 8 1 6 3 5 7 4 9 2
出力例 3
0
グリッド A ははじめからグリッド B に一致しています。
入力例 4
5 5 710511029 136397527 763027379 644706927 447672230 979861204 57882493 442931589 951053644 152300688 43971370 126515475 962139996 541282303 834022578 312523039 506696497 664922712 414720753 304621362 325269832 191410838 286751784 732741849 806602693 806602693 732741849 286751784 191410838 325269832 304621362 414720753 664922712 506696497 312523039 834022578 541282303 962139996 126515475 43971370 152300688 951053644 442931589 57882493 979861204 447672230 644706927 763027379 136397527 710511029
出力例 4
20
Score : 425 points
Problem Statement
You are given two grids, A and B, each with H rows and W columns.
For each pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, let (i, j) denote the cell in the i-th row and j-th column. In grid A, cell (i, j) contains the integer A_{i, j}. In grid B, cell (i, j) contains the integer B_{i, j}.
You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:
- Choose an integer i satisfying 1 \leq i \leq H-1 and swap the i-th and (i+1)-th rows in grid A.
- Choose an integer i satisfying 1 \leq i \leq W-1 and swap the i-th and (i+1)-th columns in grid A.
Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.
Here, grid A is identical to grid B if and only if, for all pairs of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, the integer written in cell (i, j) of grid A is equal to the integer written in cell (i, j) of grid B.
Constraints
- All input values are integers.
- 2 \leq H, W \leq 5
- 1 \leq A_{i, j}, B_{i, j} \leq 10^9
Input
The input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}
Output
If it is impossible to make grid A identical to grid B, output -1. Otherwise, print the minimum number of operations required to make grid A identical to grid B.
Sample Input 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19
Sample Output 1
3
Swapping the fourth and fifth columns of the initial grid A yields the following grid:
1 2 3 5 4 6 7 8 10 9 11 12 13 15 14 16 17 18 20 19
Then, swapping the second and third rows yields the following grid:
1 2 3 5 4 11 12 13 15 14 6 7 8 10 9 16 17 18 20 19
Finally, swapping the second and third columns yields the following grid, which is identical to grid B:
1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19
You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print 3.
Sample Input 2
2 2 1 1 1 1 1 1 1 1000000000
Sample Output 2
-1
There is no way to perform the operation to make grid A match grid B, so print -1.
Sample Input 3
3 3 8 1 6 3 5 7 4 9 2 8 1 6 3 5 7 4 9 2
Sample Output 3
0
Grid A is already identical to grid B at the beginning.
Sample Input 4
5 5 710511029 136397527 763027379 644706927 447672230 979861204 57882493 442931589 951053644 152300688 43971370 126515475 962139996 541282303 834022578 312523039 506696497 664922712 414720753 304621362 325269832 191410838 286751784 732741849 806602693 806602693 732741849 286751784 191410838 325269832 304621362 414720753 664922712 506696497 312523039 834022578 541282303 962139996 126515475 43971370 152300688 951053644 442931589 57882493 979861204 447672230 644706927 763027379 136397527 710511029
Sample Output 4
20