実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、 上から i 行目、左から j 列目のマス（以下、(i, j) と表す）には、整数 A_{i, j} が書かれています。
いま、高橋君は (1, 1) にいます。 これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。 ただし、その過程でマス目の外部に移動することは出来ません。
その結果、高橋君が通ったマス（始点 (1, 1) と終点 (H, W) を含む）に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。 高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。
制約
- 2 \leq H, W \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
出力
答えを出力せよ。
入力例 1
3 3 3 2 2 2 1 3 1 5 4
出力例 1
3
高橋君の移動経路として考えられるものは下記の 6 通りです。
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
- (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。
入力例 2
10 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
出力例 2
48620
この例では、高橋君は考えられるどの経路を通っても嬉しくなります。
Score : 300 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.
Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.
Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.
Constraints
- 2 \leq H, W \leq 10
- 1 \leq A_{i, j} \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
Output
Print the answer.
Sample Input 1
3 3 3 2 2 2 1 3 1 5 4
Sample Output 1
3
There are six possible paths:
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
Thus, the third, fifth, and sixth paths described above make him happy.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Sample Output 2
48620
In this example, every possible path makes him happy.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。
ここで、S_i は 0, 1, \ldots, 9 がちょうど 1 回ずつ現れる長さ 10 の文字列です。
それぞれのリールには対応するボタンがついており、高橋君は各非負整数 t について、
スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す（または何もしない）ことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、
i 番目のリールは S_i の (t\bmod{10})+1 文字目を表示して止まります。
ただし、t\bmod{10} で t を 10 で割ったあまりを表します。
高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
制約
- 2\leq N\leq 100
- N は整数
- S_i は
0,1, \ldots,9がちょうど 1 回ずつ現れる長さ 10 の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを出力せよ。
入力例 1
3 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
5 0123456789 0123456789 0123456789 0123456789 0123456789
出力例 2
40
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
Score : 300 points
Problem Statement
There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.
Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.
Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.
Constraints
- 2\leq N\leq 100
- N is an integer.
- S_i is a string of length 10 containing each of
0,1, \ldots,9exactly once.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the minimum number of seconds needed to achieve Takahashi's objective after the start of the spin.
Sample Input 1
3 1937458062 8124690357 2385760149
Sample Output 1
6
Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.
- 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2,
8. - 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3,
8. - 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1,
8.
There is no way to make all reels display the same character in five seconds or less, so the answer is 6.
Sample Input 2
5 0123456789 0123456789 0123456789 0123456789 0123456789
Sample Output 2
40
Note that he must stop all reels to make them display the same character.
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。
高橋君が現在持っている硬貨を用いて、（お釣りが出ないように）ちょうど X 円を支払うことができるか判定してください。
制約
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i はすべて異なる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、
できない場合は No を出力せよ。
入力例 1
2 19 2 3 5 6
出力例 1
Yes
高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。
このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。
よって、Yes を出力します。
入力例 2
2 18 2 3 5 6
出力例 2
No
持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。
よって、No を出力します。
入力例 3
3 1001 1 1 2 1 100 10
出力例 3
Yes
1 枚も使用しない硬貨が存在しても構いません。
Score : 400 points
Problem Statement
Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
Constraints
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has;
print No otherwise.
Sample Input 1
2 19 2 3 5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins.
He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen.
Thus, Yes should be printed.
Sample Input 2
2 18 2 3 5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly 18 yen.
Thus, No should be printed.
Sample Input 3
3 1001 1 1 2 1 100 10
Sample Output 3
Yes
He need not use all kinds of coins.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
|A_i - A_{i+1}| \geq K (1 \le i \le N - 1)
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 1000
- 1 \leq M \leq 5000
- 0 \leq K \leq M-1
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 1
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,2)
- (1,3)
- (2,1)
- (2,3)
- (3,1)
- (3,2)
入力例 2
3 3 2
出力例 2
2
条件を満たす数列は以下の 2 つです。
- (1,3,1)
- (3,1,3)
入力例 3
100 1000 500
出力例 3
657064711
答えを 998244353 で割った余りを出力してください。
Score : 500 points
Problem Statement
How many integer sequences A=(A_1,\ldots,A_N) of length N satisfy all the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
|A_i - A_{i+1}| \geq K (1 \le i \le N - 1)
Since the count can be enormous, find it modulo 998244353.
Constraints
- 2 \leq N \leq 1000
- 1 \leq M \leq 5000
- 0 \leq K \leq M-1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the count modulo 998244353.
Sample Input 1
2 3 1
Sample Output 1
6
The following 6 sequences satisfy the conditions.
- (1,2)
- (1,3)
- (2,1)
- (2,3)
- (3,1)
- (3,2)
Sample Input 2
3 3 2
Sample Output 2
2
The following 2 sequences satisfy the conditions.
- (1,3,1)
- (3,1,3)
Sample Input 3
100 1000 500
Sample Output 3
657064711
Print the count modulo 998244353.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
高橋君は整数 x を持っています。はじめ、x = 0 です。
N 個の操作があります。i \, (1 \leq i \leq N) 個目の操作は整数 t_i, y_i を用いて以下のように表されます。
- t_i = 1 のとき、x を y_i で置き換える。
- t_i = 2 のとき、x を x + y_i で置き換える。
高橋君は 0 個以上 K 個以下の好きな個数の操作を無視することができます。残った操作を一度ずつ順序を変えずに行ったとき、最終的な x の値としてあり得る最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- t_i \in \{1,2\} \, (1 \leq i \leq N)
- |y_i| \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K t_1 y_1 \vdots t_N y_N
出力
答えを出力せよ。
入力例 1
5 1 2 4 2 -3 1 2 2 1 2 -3
出力例 1
3
5 個目の操作を無視すると、x は 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 と変化し、最終的な x の値は 3 となります。これが最大です。
入力例 2
1 0 2 -1000000000
出力例 2
-1000000000
入力例 3
10 3 2 3 2 -1 1 4 2 -1 2 5 2 -9 2 2 1 -6 2 5 2 -3
出力例 3
15
Score : 500 points
Problem Statement
Takahashi has an integer x. Initially, x = 0.
There are N operations. The i-th operation (1 \leq i \leq N) is represented by two integers t_i and y_i as follows:
- If t_i = 1, replace x with y_i.
- If t_i = 2, replace x with x + y_i.
Takahashi may skip any number between 0 and K (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of x.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- t_i \in \{1,2\} \, (1 \leq i \leq N)
- |y_i| \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K t_1 y_1 \vdots t_N y_N
Output
Print the answer.
Sample Input 1
5 1 2 4 2 -3 1 2 2 1 2 -3
Sample Output 1
3
If he skips the 5-th operation, x changes as 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3, so x results in 3. This is the maximum.
Sample Input 2
1 0 2 -1000000000
Sample Output 2
-1000000000
Sample Input 3
10 3 2 3 2 -1 1 4 2 -1 2 5 2 -9 2 2 1 -6 2 5 2 -3
Sample Output 3
15