実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
各要素が 0 あるいは 1 である N 行 N 列の行列 A, B が与えられます。
A の i 行目 j 列目の要素を A_{i,j}、B の i 行目 j 列目の要素を B_{i,j} で表します。
A を適切に回転することで、 A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできるか判定してください。
ただし、A を回転するとは、以下の操作を好きな回数（0 回でもよい）繰り返すことをいいます。
- 1 \leq i, j \leq N を満たすすべての整数の組 (i, j) について同時に A_{i,j} を A_{N + 1 - j,i} で置き換える
制約
- 1 \leq N \leq 100
- A, B の各要素は 0 か 1 のいずれか
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
出力
A を適切に回転することで、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできる場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
出力例 1
Yes
はじめ、A は
0 1 1 1 0 0 0 1 0
です。
1 回操作を行うと、A は
0 1 0 1 0 1 0 0 1
となります。
もう 1 度操作を行うと、A は
0 1 0 0 0 1 1 1 0
となります。
このとき、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているので、Yes を出力します。
入力例 2
2 0 0 0 0 1 1 1 1
出力例 2
Yes
入力例 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
出力例 3
No
Score : 200 points
Problem Statement
You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:
- for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.
Constraints
- 1 \leq N \leq 100
- Each element of A and B is 0 or 1.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
Output
If it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, print Yes; otherwise, print No.
Sample Input 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
Sample Output 1
Yes
Initially, A is :
0 1 1 1 0 0 0 1 0
After performing the operation once, A is :
0 1 0 1 0 1 0 0 1
After performing the operation once again, A is :
0 1 0 0 0 1 1 1 0
Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.
Sample Input 2
2 0 0 0 0 1 1 1 1
Sample Output 2
Yes
Sample Input 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
整数 1, 2, \dots, N が書かれたカードが 4 枚ずつ、合計 4N 枚あります。
高橋君は、これらのカードをシャッフルしたのち 1 枚のカードを選んで抜き取り、残りの 4N - 1 枚を束にしてあなたに渡しました。渡された束の i \, (1 \leq i \leq 4N - 1) 枚目のカードには、整数 A_i が書かれています。
高橋君が抜き取ったカードに書かれていた整数を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
- 各 k \, (1 \leq k \leq N) に対し、A_i = k となる i は 4 個以下である。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{4N - 1}
出力
答えを出力せよ。
入力例 1
3 1 3 2 3 3 2 2 1 1 1 2
出力例 1
3
高橋君が抜き取ったカードには 3 が書かれています。
入力例 2
1 1 1 1
出力例 2
1
入力例 3
4 3 2 1 1 2 4 4 4 4 3 1 3 2 1 3
出力例 3
2
Score : 200 points
Problem Statement
We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.
Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.
Find the integer written on the card removed by Takahashi.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
- For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{4N - 1}
Output
Print the answer.
Sample Input 1
3 1 3 2 3 3 2 2 1 1 1 2
Sample Output 1
3
Takahashi removed a card with 3 written on it.
Sample Input 2
1 1 1 1
Sample Output 2
1
Sample Input 3
4 3 2 1 1 2 4 4 4 4 3 1 3 2 1 3
Sample Output 3
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。
j=1,2,\ldots,Q について、以下の質問に答えてください。
- N 人のうち、身長が x_j 以上の生徒は何人か？
制約
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
出力
Q 行出力せよ。
j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。
入力例 1
3 1 100 160 130 120
出力例 1
2
身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。
入力例 2
5 5 1 2 3 4 5 6 5 4 3 2
出力例 2
0 1 2 3 4
入力例 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
出力例 3
5 3 5 5 5
Score : 300 points
Problem Statement
There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.
For each j=1,2,\ldots,Q, answer the following question.
- How many of the N students have a height of at least x_j?
Constraints
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
Output
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.
Sample Input 1
3 1 100 160 130 120
Sample Output 1
2
The students with a height of at least 120 are the 2-nd and 3-rd ones.
Sample Input 2
5 5 1 2 3 4 5 6 5 4 3 2
Sample Output 2
0 1 2 3 4
Sample Input 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
Sample Output 3
5 3 5 5 5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
冷蔵庫に N 種類の材料があります。これらを材料 1、\dots、材料 N と呼びます。材料 i は Q_i グラムあります。
あなたは 2 種類の料理を作れます。料理 A は、1 人分を作るのに各材料 i (1 \leq i \leq N) が A_i グラム必要です。料理 B は、1 人分を作るのに各材料 i が B_i グラム必要です。どちらも整数人分しか作れません。
冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れますか。
制約
- 1 \leq N \leq 10
- 1 \leq Q_i \leq 10^6
- 0 \leq A_i \leq 10^6
- A_i \geq 1 であるような i が存在する。
- 0 \leq B_i \leq 10^6
- B_i \geq 1 であるような i が存在する。
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q_1 Q_2 \dots Q_N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
最大で合計 S 人分の料理を作れるとして、整数 S を出力せよ。
入力例 1
2 800 300 100 100 200 10
出力例 1
5
この冷蔵庫には、800 グラムの材料 1 と 300 グラムの材料 2 があります。
100 グラムの材料 1 と 100 グラムの材料 2 で料理 A を 1 人分作れ、200 グラムの材料 1 と 10 グラムの材料 2 で料理 B を 1 人分作れます。
料理 A を 2 人分、料理 B を 3 人分作るのに必要な材料 1 の量は 100 \times 2 + 200 \times 3 = 800 グラム、材料 2 の量は 100 \times 2 + 10 \times 3 = 230 グラムで、いずれも冷蔵庫にある量を超えません。このようにして合計 5 人分の料理を作ることができますが、6 人分を作る方法はなく、答えは 5 です。
入力例 2
2 800 300 100 0 0 10
出力例 2
38
800 グラムの材料 1 で料理 A を 8 人分、300 グラムの材料 2 で料理 B を 30 人分、合計 38 人分作れます。
入力例 3
2 800 300 801 300 800 301
出力例 3
0
何も作れません。
入力例 4
10 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0
出力例 4
222222
Score: 300 points
Problem Statement
Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.
You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.
Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?
Constraints
- 1 \leq N \leq 10
- 1 \leq Q_i \leq 10^6
- 0 \leq A_i \leq 10^6
- There is an i such that A_i \geq 1.
- 0 \leq B_i \leq 10^6
- There is an i such that B_i \geq 1.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q_1 Q_2 \dots Q_N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Assuming that you can make a maximum total of S servings of dishes, print the integer S.
Sample Input 1
2 800 300 100 100 200 10
Sample Output 1
5
This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.
You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.
To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.
Sample Input 2
2 800 300 100 0 0 10
Sample Output 2
38
You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.
Sample Input 3
2 800 300 801 300 800 301
Sample Output 3
0
You cannot make any dishes.
Sample Input 4
10 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0
Sample Output 4
222222
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
以下のような、無限に広い六角形のグリッドがあります。最初、全てのマスは白です。
ある六角形のマスは 2 つの整数 i,j を用いて (i,j) と表されます。
マス (i,j) は以下の 6 つのマスと隣接します。
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
高橋くんは、 N 個のマス (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) を黒く塗りました。
黒いマスがいくつの連結成分をなすか求めてください。
ただし、ある 2 つの黒いマスが同じ連結成分に属するとは、この 2 つの黒いマスの間をいくつかの隣接する黒いマスを辿って移動できることを指します。
制約
- 入力は全て整数
- 1 \le N \le 1000
- |X_i|,|Y_i| \le 1000
- (X_i,Y_i) は相異なる
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを整数として出力せよ。
入力例 1
6 -1 -1 0 1 0 2 1 0 1 2 2 0
出力例 1
3
高橋くんがマスを黒く塗った後、グリッドは下図の状態になります。
黒いマスがなす連結成分は以下の 3 つです。
- (-1,-1)
- (1,0),(2,0)
- (0,1),(0,2),(1,2)
入力例 2
4 5 0 4 1 -3 -4 -2 -5
出力例 2
4
入力例 3
5 2 1 2 -1 1 0 3 1 1 -1
出力例 3
1
Score : 400 points
Problem Statement
We have an infinite hexagonal grid shown below. Initially, all squares are white.
A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.
Constraints
- All values in the input are integers.
- 1 \le N \le 1000
- |X_i|,|Y_i| \le 1000
- The pairs (X_i,Y_i) are distinct.
Input
The input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
6 -1 -1 0 1 0 2 1 0 1 2 2 0
Sample Output 1
3
After Takahashi paints cells black, the grid looks as shown below.
The black squares form the following three connected components:
- (-1,-1)
- (1,0),(2,0)
- (0,1),(0,2),(1,2)
Sample Input 2
4 5 0 4 1 -3 -4 -2 -5
Sample Output 2
4
Sample Input 3
5 2 1 2 -1 1 0 3 1 1 -1
Sample Output 3
1