実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります（持ち点が負になることもあります）。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。
制約
- 2\leq N\leq 100
- -100\leq A_i\leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{N-1}
出力
答えを出力せよ。
入力例 1
4 1 -2 -1
出力例 1
2
最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。
- 最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
- 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
- 人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
- 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
- 人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
- 人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。
この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。
入力例 2
3 0 0
出力例 2
0
入力例 3
6 10 20 30 40 50
出力例 3
-150
Score: 100 points
Problem Statement
There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.
Constraints
- 2 \leq N \leq 100
- -100 \leq A_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{N-1}
Output
Print the answer.
Sample Input 1
4 1 -2 -1
Sample Output 1
2
Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.
- Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
- Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
- Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
- Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
- Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
- Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).
In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.
Sample Input 2
3 0 0
Sample Output 2
0
Sample Input 3
6 10 20 30 40 50
Sample Output 3
-150
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。
制約
- 1 \leq a \lt b \leq 10
- a, b は整数
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
a 番の点と b 番の点が線で直接結ばれている場合は Yes を出力し、結ばれていない場合は No を出力せよ。
ジャッジは英大文字と英小文字を厳密に区別することに注意せよ。
入力例 1
4 5
出力例 1
Yes
問題文で示した図において、4 番の点と 5 番の点は線で直接結ばれています。
よって、Yes を出力します。
入力例 2
3 5
出力例 2
No
問題文で示した図において、3 番の点と 5 番の点は線で直接結ばれていません。
よって、No を出力します。
入力例 3
1 10
出力例 3
Yes
Score : 100 points
Problem Statement
In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?
Constraints
- 1 \leq a \lt b \leq 10
- a and b are integers.
Input
Input is given from Standard Input in the following format:
a b
Output
If the points numbered a and b are directly connected by a line segment, print Yes; otherwise, print No.
The judge is case-sensitive: be sure to print uppercase and lowercase letters correctly.
Sample Input 1
4 5
Sample Output 1
Yes
In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.
Sample Input 2
3 5
Sample Output 2
No
In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.
Sample Input 3
1 10
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1 から N の番号がついた N 人の人がいます。
人 i はキーエンス本社ビルの建築面積を S_i 平方メートルであると予想しました。
キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。
N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。
制約
- 1 \leq N \leq 20
- 1 \leq S_i \leq 1000
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \ldots S_N
出力
答えを出力せよ。
入力例 1
3 10 20 39
出力例 1
1
a=1,b=1 のとき面積は 10 平方メートル、a=2,b=3 のとき面積は 39 平方メートルとなります。
しかし a,b がどのような正の整数であったとしても面積が 20 平方メートルになることはありません。
よって、人 2 の予想だけは確実に誤りであることがわかります。
入力例 2
5 666 777 888 777 666
出力例 2
3
Score : 200 points
Problem Statement
There are N people numbered 1 to N.
Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.
The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.
Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?
Constraints
- 1 \leq N \leq 20
- 1 \leq S_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N S_1 \ldots S_N
Output
Print the answer.
Sample Input 1
3 10 20 39
Sample Output 1
1
The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.
However, no pair of positive integers a and b would make the area 20 square meters.
Thus, we can only be sure that Person 2 guessed wrong.
Sample Input 2
5 666 777 888 777 666
Sample Output 2
3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
xy 平面上に N 人の人 1,2,\dots,N がおり、人 i は座標 (X_i,Y_i) にいます。
このうち、 K 人の人 A_1,A_2,\dots,A_K に同じ強さの明かりを持たせます。
座標 (x,y) にいる人が強さ R の明かりを持っている時、その明かりによって中心 (x,y) 、半径 R の円の内部全体(境界を含む)が照らされます。
すべての人が少なくとも 1 つの明かりによって照らされるために必要な明かりの強さの最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを実数として出力せよ。
出力された解と想定解との絶対誤差または相対誤差が 10^{-5} 以下であるならば、出力は正しいと見なされる。
入力例 1
4 2 2 3 0 0 0 1 1 2 2 0
出力例 1
2.23606797749978969
この入力では人が 4 人おり、そのうち人 2,3 が明かりを持ちます。
R \ge \sqrt{5} \approx 2.236068 である時、すべての人が少なくとも 1 つの明かりによって照らされます。
入力例 2
2 1 2 -100000 -100000 100000 100000
出力例 2
282842.712474619009
入力例 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
出力例 3
130379.280458974768
Score : 200 points
Problem Statement
There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.
Constraints
- All values in input are integers.
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer as a real number.
Your output will be considered correct if its absolute or relative error from the judge's output is at most 10^{-5}.
Sample Input 1
4 2 2 3 0 0 0 1 1 2 2 0
Sample Output 1
2.23606797749978969
This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.
Sample Input 2
2 1 2 -100000 -100000 100000 100000
Sample Output 2
282842.712474619009
Sample Input 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
Sample Output 3
130379.280458974768
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A = (a_1, a_2, \dots, a_N) があります。
以下で説明される Q 個のクエリに答えてください。
- クエリ i : 整数の組 (x_i, k_i) が与えられます。A の要素を a_1, a_2, \dots と前から順に見ていったときに、数 x_i が k_i 回目に登場するのは A の前から何番目の要素を見たときかを出力してください。
ただし条件を満たす要素が存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
- 1 \leq k_i \leq N (1 \leq i \leq Q)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q a_1 a_2 \dots a_N x_1 k_1 x_2 k_2 \vdots x_Q k_Q
出力
Q 行出力せよ。i 行目ではクエリ i に対する答えを出力せよ。
入力例 1
6 8 1 1 2 3 1 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 4 1
出力例 1
1 2 5 -1 3 6 -1 -1
A の中で 1 は a_1, a_2, a_5 に登場します。よって、クエリ 1 からクエリ 4 の答えは順に 1, 2, 5, -1 となります。
入力例 2
3 2 0 1000000000 999999999 1000000000 1 123456789 1
出力例 2
2 -1
Score : 300 points
Problem Statement
We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.
- Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
Print the index of that element, or -1 if there is no such element.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
- 1 \leq k_i \leq N (1 \leq i \leq Q)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q a_1 a_2 \dots a_N x_1 k_1 x_2 k_2 \vdots x_Q k_Q
Output
Print Q lines. The i-th line should contain the answer to Query i.
Sample Input 1
6 8 1 1 2 3 1 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 4 1
Sample Output 1
1 2 5 -1 3 6 -1 -1
1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.
Sample Input 2
3 2 0 1000000000 999999999 1000000000 1 123456789 1
Sample Output 2
2 -1