Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
縦 H 行、横 W 列のマス目があり、このうち上から i 個目、左から j 個目のマスを (i,j) と呼びます。
このとき、マス (R,C) に辺で隣接するマスの個数を求めてください。
ただし、ある 2 つのマス (a,b),(c,d) が辺で隣接するとは、 |a-c|+|b-d|=1 (|x| を x の絶対値とする) であることを言います。
制約
- 入力は全て整数
- 1 \le R \le H \le 10
- 1 \le C \le W \le 10
入力
入力は以下の形式で標準入力から与えられる。
H W R C
出力
答えを整数として出力せよ。
入力例 1
3 4 2 2
出力例 1
4
入出力例 1,2,3 に対する説明は、出力例 3 の下にまとめて示します。
入力例 2
3 4 1 3
出力例 2
3
入力例 3
3 4 3 4
出力例 3
2
H=3,W=4 のとき、マス目は以下のようになります。
- 入力例 1 について、マス (2,2) に隣接するマスは 4 つです。
- 入力例 2 について、マス (1,3) に隣接するマスは 3 つです。
- 入力例 3 について、マス (3,4) に隣接するマスは 2 つです。
入力例 4
1 10 1 5
出力例 4
2
入力例 5
8 1 8 1
出力例 5
1
入力例 6
1 1 1 1
出力例 6
0
Score : 100 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).
Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).
Constraints
- All values in input are integers.
- 1 \le R \le H \le 10
- 1 \le C \le W \le 10
Input
Input is given from Standard Input in the following format:
H W R C
Output
Print the answer as an integer.
Sample Input 1
3 4 2 2
Sample Output 1
4
We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.
Sample Input 2
3 4 1 3
Sample Output 2
3
Sample Input 3
3 4 3 4
Sample Output 3
2
When H=3 and W=4, the grid looks as follows.
- For Sample Input 1, there are 4 squares adjacent to Square (2,2).
- For Sample Input 2, there are 3 squares adjacent to Square (1,3).
- For Sample Input 3, there are 2 squares adjacent to Square (3,4).
Sample Input 4
1 10 1 5
Sample Output 4
2
Sample Input 5
8 1 8 1
Sample Output 5
1
Sample Input 6
1 1 1 1
Sample Output 6
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は、毎日 S 時 0 分に部屋の電気をつけ、毎日 T 時 0 分に消します。
電気をつけている間に日付が変わることもあります。
X 時 30 分に部屋の電気がついているかどうか判定してください。
制約
- 0 \leq S, T, X \leq 23
- S \neq T
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
S T X
出力
X 時 30 分に部屋の電気がついているならば Yes と、そうでなければ No と出力せよ。
入力例 1
7 20 12
出力例 1
Yes
部屋の電気がついているのは 7 時 0 分から 20 時 0 分までの間です。12 時 30 分には電気がついているので、Yes と出力します。
入力例 2
20 7 12
出力例 2
No
部屋の電気がついているのは 0 時 0 分から 7 時 0 分までの間と、20 時 0 分から（次の日の）0 時 0 分までの間です。
12 時 30 分には電気がついていないので、No と出力します。
入力例 3
23 0 23
出力例 3
Yes
Score : 100 points
Problem Statement
Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.
Determine whether the light is on at 30 minutes past X o'clock.
Constraints
- 0 \leq S, T, X \leq 23
- S \neq T
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
S T X
Output
If the light is on at 30 minutes past X o'clock, print Yes; otherwise, print No.
Sample Input 1
7 20 12
Sample Output 1
Yes
The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.
Sample Input 2
20 7 12
Sample Output 2
No
The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.
Sample Input 3
23 0 23
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 市では、N 種類のゴミを定期的に収集しています。i\;(=1,2,\dots,N) 種類目のゴミは、日付を q_i で割ったあまりが r_i の日に収集されます。
Q 個の質問に答えてください。j\;(=1,2,\dots,Q) 番目の質問では、d_j 日に t_j 種類目のゴミが出たときに、次にそれが収集される日を答えてください。
ただし、i 種類目のゴミが出た日が、 i 種類目のゴミが回収される日であった場合、そのゴミは同じ日に収集されるとします。
制約
- 1 \leq N \leq 100
- 0 \leq r_i < q_i \leq 10^9
- 1 \leq Q \leq 100
- 1 \leq t_j \leq N
- 1 \leq d_j \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N q_1 r_1 q_2 r_2 \vdots q_N r_N Q t_1 d_1 t_2 d_2 \vdots t_Q d_Q
出力
Q 行出力せよ。j\;(1\leq j \leq Q) 行目には、j 番目の質問に対する答えを出力せよ。
入力例 1
2 7 3 4 2 5 1 1 1 3 1 4 1 15 2 7
出力例 1
3 3 10 17 10
- 1 番目の質問：1 種類目のゴミが 1 日以降に初めて回収されるのは 3 日です。
- 2 番目の質問：1 種類目のゴミが 3 日以降に初めて回収されるのは 3 日です。
- 3 番目の質問：1 種類目のゴミが 4 日以降に初めて回収されるのは 10 日です。
Score : 200 points
Problem Statement
In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.
Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.
Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.
Constraints
- 1 \leq N \leq 100
- 0 \leq r_i < q_i \leq 10^9
- 1 \leq Q \leq 100
- 1 \leq t_j \leq N
- 1 \leq d_j \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N q_1 r_1 q_2 r_2 \vdots q_N r_N Q t_1 d_1 t_2 d_2 \vdots t_Q d_Q
Output
Print Q lines. The j-th line (1\leq j \leq Q) should contain the answer to the j-th query.
Sample Input 1
2 7 3 4 2 5 1 1 1 3 1 4 1 15 2 7
Sample Output 1
3 3 10 17 10
- 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
- 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
- 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1,2,\ldots,N と番号づけられた N 人が M 回、一列に並んで集合写真を撮りました。i 番目の撮影で左から j 番目に並んだ人の番号は a_{i,j} です。
ある二人組は M 回の撮影で一度も連続して並ばなかった場合、不仲である可能性があります。
不仲である可能性がある二人組の個数を求めてください。なお、人 x と人 y からなる二人組と人 y と人 x からなる二人組は区別しません。
制約
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} には 1,\ldots,N が 1 回ずつ現れる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
出力
答えを出力せよ。
入力例 1
4 2 1 2 3 4 4 3 1 2
出力例 1
2
人 1 と人 4 からなる二人組と、人 2 と人 4 からなる二人組がそれぞれ不仲である可能性があります。
入力例 2
3 3 1 2 3 3 1 2 1 2 3
出力例 2
0
入力例 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
出力例 3
6
Score : 200 points
Problem Statement
N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.
Two people who did not stand next to each other in any of the photos may be in a bad mood.
How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.
Constraints
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
Output
Print the answer.
Sample Input 1
4 2 1 2 3 4 4 3 1 2
Sample Output 1
2
The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.
Sample Input 2
3 3 1 2 3 3 1 2 1 2 3
Sample Output 2
0
Sample Input 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.