実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
xy 平面上に長方形があります。この長方形の各辺は x 軸または y 軸に平行であり、面積は 0 ではありません。
この長方形の 4 つの頂点のうち異なる 3 つの頂点の座標 (x_1, y_1), (x_2, y_2), (x_3, y_3) が与えられるので、残る 1 つの頂点の座標を求めてください。
制約
- -100 \leq x_i, y_i \leq 100
- (x_1, y_1), (x_2, y_2), (x_3, y_3) のすべてを頂点に持つ長方形がただ一つ存在し、その各辺は x 軸または y 軸に平行であり、面積は 0 ではない。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
x_1 y_1 x_2 y_2 x_3 y_3
出力
答えとなる頂点の座標 (x, y) を下記の形式にしたがい空白区切りで出力せよ。
x y
入力例 1
-1 -1 -1 2 3 2
出力例 1
3 -1
(-1, -1), (-1, 2), (3, 2) を頂点とする長方形の残る 1 つの頂点は (3, -1) です。
入力例 2
-60 -40 -60 -80 -20 -80
出力例 2
-20 -40
Score : 100 points
Problem Statement
There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.
Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.
Constraints
- -100 \leq x_i, y_i \leq 100
- There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
x_1 y_1 x_2 y_2 x_3 y_3
Output
Print the sought coordinates (x, y) separated by a space in the following format:
x y
Sample Input 1
-1 -1 -1 2 3 2
Sample Output 1
3 -1
The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).
Sample Input 2
-60 -40 -60 -80 -20 -80
Sample Output 2
-20 -40
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ 3 の文字列 S が与えられます。
S に 1 度だけ含まれる文字を 1 つ出力してください。
但し、そのような文字が存在しない場合は代わりに -1 と出力してください。
制約
- S は英小文字のみからなる 3 文字の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。正解が複数ある場合、どれを出力してもよい。
入力例 1
pop
出力例 1
o
pop に o は 1 度だけ含まれます。
入力例 2
abc
出力例 2
a
abc に a, b, c はどれも 1 度だけ含まれるので、どれを出力しても構いません。
入力例 3
xxx
出力例 3
-1
xxx に 1 度だけ含まれる文字はありません。
Score : 100 points
Problem Statement
You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.
Constraints
- S is a string of length 3 consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer. If multiple solutions exist, you may print any of them.
Sample Input 1
pop
Sample Output 1
o
o occurs only once in pop.
Sample Input 2
abc
Sample Output 2
a
a, b, and c occur once each in abc, so you may print any of them.
Sample Input 3
xxx
Sample Output 3
-1
No character occurs only once in xxx.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人が総当り戦の試合をしました。
N 行 N 列からなる試合の結果の表 A が与えられます。A の i 行目 j 列目の要素を A_{i,j} と表します。
A_{i,j} は i=j のとき - であり、それ以外のとき W, L, D のいずれかです。
A_{i,j} が W, L, D であることは、人 i が人 j との試合に勝った、負けた、引き分けたことをそれぞれ表します。
与えられた表に矛盾があるかどうかを判定してください。
次のいずれかが成り立つとき、与えられた表には矛盾があるといいます。
- ある組 (i,j) が存在して、人 i が人 j に勝ったが、人 j が人 i に負けていない
- ある組 (i,j) が存在して、人 i が人 j に負けたが、人 j が人 i に勝っていない
- ある組 (i,j) が存在して、人 i が人 j に引き分けたが、人 j が人 i に引き分けていない
制約
- 2 \leq N \leq 1000
- A_{i,i} は
-である - i\neq j のとき、A_{i,j} は
W,L,Dのいずれかである
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
出力
与えられた表に矛盾がないとき correct、矛盾があるとき incorrect と出力せよ。
入力例 1
4 -WWW L-DD LD-W LDW-
出力例 1
incorrect
人 3 が人 4 に勝ったにもかかわらず、人 4 も人 3 に勝ったことになっており、矛盾しています。
入力例 2
2 -D D-
出力例 2
correct
矛盾はありません。
Score : 200 points
Problem Statement
N players played a round-robin tournament.
You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.
Determine whether the given table is contradictory.
The table is said to be contradictory when some of the following holds:
- There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
- There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
- There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.
Constraints
- 2 \leq N \leq 1000
- A_{i,i} is
-. - A_{i,j} is
W,L, orD, for i\neq j.
Input
Input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
If the given table is not contradictory, print correct; if it is contradictory, print incorrect.
Sample Input 1
4 -WWW L-DD LD-W LDW-
Sample Output 1
incorrect
Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.
Sample Input 2
2 -D D-
Sample Output 2
correct
There is no contradiction.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
スーパーマーケットで卵のパックが売られています。
卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S M L
出力
答えを出力せよ。
入力例 1
16 120 150 200
出力例 1
300
8 個入りのパックを 2 個買うのが最適です。
入力例 2
10 100 50 10
出力例 2
10
12 個入りのパックを 1 個買うのが最適です。
入力例 3
99 600 800 1200
出力例 3
10000
8 個入りのパックと 12 個入りのパックを 5 個ずつ買うのが最適です。
Score : 200 points
Problem Statement
A supermarket sells egg packs.
A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.
When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.
Constraints
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S M L
Output
Print the answer.
Sample Input 1
16 120 150 200
Sample Output 1
300
It is optimal to buy two 8-egg packs.
Sample Input 2
10 100 50 10
Sample Output 2
10
It is optimal to buy one 12-egg pack.
Sample Input 3
99 600 800 1200
Sample Output 3
10000
It is optimal to buy five 8-egg packs and five 12-egg packs.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は武術家です。 武術家の覚えられる技は N 個あり、技 1, 2, \ldots, N と名前がついています。 1 \leq i \leq N について、技 i を習得するには時間 T_i の修練が必要で、 さらに、修練の開始時点で技 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} をすでに習得している必要があります。 ここで、1 \leq j \leq K_i について、A_{i,j} < i であることが保証されます。
高橋君は時刻 0 の時点で技を 1 つも覚えていません。 高橋君は同時に 1 つの技に対する修練しかできず、また、一度始めた修練を途中でやめることもできません。 高橋君が技 N を習得するのに必要な時間の最小値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq K_i < i
- 1 \leq A_{i,j} < i
- \sum_{i=1}^N K_i \leq 2\times 10^5
- A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} はすべて異なる。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
T_1 K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
T_2 K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
T_N K_N A_{N,1} A_{N,2} \ldots A_{N,K_N}
出力
技 N を習得するのに必要な時間の最小値を出力せよ。
入力例 1
3 3 0 5 1 1 7 1 1
出力例 1
10
例えば高橋君は次のように行動することができます。
- 高橋君は時刻 0 に技 1 の修練を開始し、時刻 3 に技 1 を習得します。
- その後、時刻 3 に技 3 の修練を開始し、時刻 10 に技 3 を習得します。
このときが最短で、高橋君が技 3 を習得するのに必要な時間は 3+7=10 となります。 技 3 の習得のためには、技 2 を習得する必要はありません。
入力例 2
5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4
出力例 2
5000000000
答えが 32 bit 整数に収まらないことがある事に注意してください。
Score : 300 points
Problem Statement
Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.
Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq K_i < i
- 1 \leq A_{i,j} < i
- \sum_{i=1}^N K_i \leq 2\times 10^5
- A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
T_1 K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
T_2 K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
T_N K_N A_{N,1} A_{N,2} \ldots A_{N,K_N}
Output
Print the minimum number of minutes needed for Takahashi to learn Move N.
Sample Input 1
3 3 0 5 1 1 7 1 1
Sample Output 1
10
Here is one possible plan for Takahashi.
- At time 0, start practicing for Move 1 to learn Move 1 at time 3.
- Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.
Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.
Sample Input 2
5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4
Sample Output 2
5000000000
Note that the answer may not fit into a 32-bit integer.