Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数列 A=(A_1,A_2,A_3) が与えられます。
A の要素を自由に並べ替えた列を B=(B_1,B_2,B_3) とします。
このとき、 B_1 \times B_2 = B_3 を満たすようにできるか判定してください。
制約
- 入力は全て整数
- 1 \le A_1,A_2,A_3 \le 100
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3
出力
B_1 \times B_2 = B_3 を満たすようにできるなら Yes 、そうでないなら No と出力せよ。
入力例 1
3 15 5
出力例 1
Yes
A=(3,15,5) です。
B=(3,5,15) と並べ替えることで、 B_1 \times B_2 = B_3 を満たすようにできます。
入力例 2
5 3 2
出力例 2
No
B をどのように定めても、 B_1 \times B_2 = B_3 を満たすようにはできません。
入力例 3
3 3 9
出力例 3
Yes
Score : 100 points
Problem Statement
You are given a sequence of integers A = (A_1, A_2, A_3).
Let B = (B_1, B_2, B_3) be any permutation of A.
Determine whether it is possible that B_1 \times B_2 = B_3.
Constraints
- All input values are integers.
- 1 \le A_1, A_2, A_3 \le 100
Input
The input is given from Standard Input in the following format:
A_1 A_2 A_3
Output
If it is possible that B_1 \times B_2 = B_3, print Yes; otherwise, print No.
Sample Input 1
3 15 5
Sample Output 1
Yes
Here, A=(3,15,5). By rearranging it as B=(3,5,15), we can satisfy B_1 \times B_2 = B_3.
Sample Input 2
5 3 2
Sample Output 2
No
No permutation of B satisfies B_1 \times B_2 = B_3.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 R,C と 2 行 2 列からなる行列 A が与えられるので、 A_{R,C} を出力してください。
制約
- 入力は全て整数
- 1 \le R,C \le 2
- 0 \le A_{i,j} \le 100
入力
入力は以下の形式で標準入力から与えられる。
R C
A_{1,1} A_{1,2}
A_{2,1} A_{2,2}
出力
答えを整数として出力せよ。
入力例 1
1 2 1 0 0 1
出力例 1
0
A_{1,2}=0 です。
入力例 2
2 2 1 2 3 4
出力例 2
4
A_{2,2}=4 です。
入力例 3
2 1 90 80 70 60
出力例 3
70
A_{2,1}=70 です。
Score : 100 points
Problem Statement
Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.
Constraints
- All values in input are integers.
- 1 \le R,C \le 2
- 0 \le A_{i,j} \le 100
Input
Input is given from Standard Input in the following format:
R C
A_{1,1} A_{1,2}
A_{2,1} A_{2,2}
Output
Print the answer as an integer.
Sample Input 1
1 2 1 0 0 1
Sample Output 1
0
We have A_{1,2}=0.
Sample Input 2
2 2 1 2 3 4
Sample Output 2
4
We have A_{2,2}=4.
Sample Input 3
2 1 90 80 70 60
Sample Output 3
70
We have A_{2,1}=70.
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
配点 : 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
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は鳥 1,2,\dots,N の N 羽の鳥を M 日間観察しました。
高橋君が観察した鳥には色 1,2,\dots,N の N 色のうちいずれか 1 色がついていますが、これらの鳥には観察期間中に色が変化するという興味深い特徴があります。
鳥 i は D_i-1 日目以前の観察では色 A_i であり、 D_i 日目以降の観察では色 B_i になりました。
ただし、 D_i=1 である場合はその鳥の色は 1 日目の観察から B_i であり、 A_i=B_i である場合はその鳥の色は観察期間中に変化しませんでした。
j=1,2,\dots,M について、 j 日目の観察で鳥の色が何種類あったかを求めてください。
制約
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 3 \times 10^5
- 1 \le A_i,B_i \le N
- 1 \le D_i \le M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 D_1 B_1 A_2 D_2 B_2 \vdots A_N D_N B_N
出力
M 行出力せよ。
そのうち j 行目には、 j 日目に鳥の色が何種類あったかを出力せよ。
入力例 1
6 7 1 3 2 2 6 5 5 5 1 3 3 5 4 1 6 6 3 6
出力例 1
5 5 3 3 4 4 4
この入力では、 6 羽の鳥を 7 日間観察します。
- 1 日目の観察で、各鳥の色は 1,2,5,3,6,6 でした。鳥の色は全部で 5 種類です。
- 2 日目の観察で、各鳥の色は 1,2,5,3,6,6 でした。鳥の色は全部で 5 種類です。
- 3 日目の観察で、各鳥の色は 2,2,5,5,6,6 でした。鳥の色は全部で 3 種類です。
- 4 日目の観察で、各鳥の色は 2,2,5,5,6,6 でした。鳥の色は全部で 3 種類です。
- 5 日目の観察で、各鳥の色は 2,2,1,5,6,6 でした。鳥の色は全部で 4 種類です。
- 6 日目の観察で、各鳥の色は 2,5,1,5,6,6 でした。鳥の色は全部で 4 種類です。
- 7 日目の観察で、各鳥の色は 2,5,1,5,6,6 でした。鳥の色は全部で 4 種類です。
Score : 300 points
Problem Statement
Takahashi observed N birds, numbered 1, 2, \dots, N, over M days.
Each of the birds that Takahashi observed has one of N colors, numbered 1, 2, \dots, N, and these birds have an interesting characteristic: their color can change during the observation period.
Bird i had color A_i in observations on or before day D_i - 1, and color B_i in observations on or after day D_i.
Here, if D_i = 1, then the bird's color was B_i from the observation on day 1, and if A_i = B_i, then the bird's color did not change during the observation period.
For each j = 1, 2, \dots, M, find the number of different colors of birds on day j.
Constraints
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 3 \times 10^5
- 1 \le A_i, B_i \le N
- 1 \le D_i \le M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 D_1 B_1 A_2 D_2 B_2 \vdots A_N D_N B_N
Output
Output M lines.
The j-th line should contain the number of different colors of birds on day j.
Sample Input 1
6 7 1 3 2 2 6 5 5 5 1 3 3 5 4 1 6 6 3 6
Sample Output 1
5 5 3 3 4 4 4
In this input, six birds are observed over seven days.
- On day 1, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
- On day 2, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
- On day 3, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
- On day 4, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
- On day 5, the color of each bird was 2, 2, 1, 5, 6, 6. There are 4 different colors in total.
- On day 6, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.
- On day 7, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.