Time Limit: 2 sec / Memory Limit: 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.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
7 枚のカードがあります。i 番目 (i=1,\ldots,7) のカードには整数 A_i が書かれています。
これらのカードから 5 枚を選び、フルハウスとできるか判定してください。
ただし、 5 枚組のカードは以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。
- 異なる整数 x,y について、 x が書かれたカード 3 枚と y が書かれたカード 2 枚からなる。
制約
- A_i は 1 以上 13 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3 A_4 A_5 A_6 A_7
出力
5 枚カードを選んでフルハウスとできるなら Yes 、そうでないなら No と出力せよ。
入力例 1
1 4 1 4 2 1 3
出力例 1
Yes
例えば、 (1,1,1,4,4) とカードを選択することでフルハウスとできます。
入力例 2
11 12 13 10 13 12 11
出力例 2
No
7 枚のカードからどのように 5 枚を選んでもフルハウスとはできません。
入力例 3
7 7 7 7 7 7 7
出力例 3
No
同じカード 5 枚組はフルハウスではないことに注意してください。
入力例 4
13 13 1 1 7 4 13
出力例 4
Yes
Score : 250 points
Problem Statement
We have seven cards. The i-th card (i=1,\ldots,7) has an integer A_i written on it.
Determine whether it is possible to choose five of them so that the chosen cards form a full house.
A set of five cards is called a full house if and only if the following conditions are satisfied:
- For different integers x and y, there are three cards with x and two cards with y.
Constraints
- A_i is an integer between 1 and 13, inclusive.
Input
The input is given from Standard Input in the following format:
A_1 A_2 A_3 A_4 A_5 A_6 A_7
Output
If a full house can be formed by choosing five cards, print Yes; otherwise, print No.
Sample Input 1
1 4 1 4 2 1 3
Sample Output 1
Yes
For example, by choosing the cards (1,1,1,4,4), we can form a full house.
Sample Input 2
11 12 13 10 13 12 11
Sample Output 2
No
No five cards chosen from the seven cards form a full house.
Sample Input 3
7 7 7 7 7 7 7
Sample Output 3
No
Note that five identical cards do not form a full house.
Sample Input 4
13 13 1 1 7 4 13
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
非負整数 n が次の条件を満たすとき、n を 良い整数 と呼びます。
- n を 10 進法で表したときに、偶数の数字 (0, 2, 4, 6, 8) のみが登場する。
例えば 0、68 および 2024 は良い整数です。
整数 N が与えられます。良い整数のうち小さい方から N 番目の整数を求めてください。
制約
- 1 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
小さい方から N 番目の良い整数を出力せよ。
入力例 1
8
出力例 1
24
良い整数を小さい方から順に並べると 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots となります。
小さい方から 8 番目の良い整数は 24 なので、これを出力します。
入力例 2
133
出力例 2
2024
入力例 3
31415926535
出力例 3
2006628868244228
Score: 300 points
Problem Statement
A non-negative integer n is called a good integer when it satisfies the following condition:
- All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).
For example, 0, 68, and 2024 are good integers.
You are given an integer N. Find the N-th smallest good integer.
Constraints
- 1 \leq N \leq 10^{12}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the N-th smallest good integer.
Sample Input 1
8
Sample Output 1
24
The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.
Sample Input 2
133
Sample Output 2
2024
Sample Input 3
31415926535
Sample Output 3
2006628868244228
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
二次元平面があります。1 以上 9 以下の整数 r,c について、S_{r} の c 番目の文字が # であるとき座標 (r,c) にポーンが置いてあり、S_{r} の c 番目の文字が . であるとき座標 (r,c) に何も置かれていません。
この平面上の正方形であって、4 頂点全てにポーンが置いてあるものの個数を求めてください。
制約
- S_1,\ldots,S_9 はそれぞれ
#と.からなる長さ 9 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 \vdots S_9
出力
答えを出力せよ。
入力例 1
##....... ##....... ......... .......#. .....#... ........# ......#.. ......... .........
出力例 1
2
座標 (1,1),(1,2),(2,2),(2,1) を頂点とする正方形は、4 頂点全てにポーンが置かれています。
座標 (4,8),(5,6),(7,7),(6,9) を頂点とする正方形も、4 頂点全てにポーンが置かれています。
よって答えは 2 です。
入力例 2
.#....... #.#...... .#....... ......... ....#.#.# ......... ....#.#.# ........# .........
出力例 2
3
Score : 300 points
Problem Statement
There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..
Find the number of squares in this plane with pawns placed at all four vertices.
Constraints
- Each of S_1,\ldots,S_9 is a string of length 9 consisting of
#and..
Input
The input is given from Standard Input in the following format:
S_1 S_2 \vdots S_9
Output
Print the answer.
Sample Input 1
##....... ##....... ......... .......#. .....#... ........# ......#.. ......... .........
Sample Output 1
2
The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.
The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.
Thus, the answer is 2.
Sample Input 2
.#....... #.#...... .#....... ......... ....#.#.# ......... ....#.#.# ........# .........
Sample Output 2
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数列 (A_1,\ldots,A_K) を使って、高橋君と青木君が石取りゲームをします。
最初、山には N 個の石があります。高橋君から順に、二人が交互に次の操作を行います。
- 現在山にある石の個数以下であるような A_i を 1 つ選ぶ。山から A_i 個の石を取り除く。
山から石がなくなったとき、ゲームは終了します。
二人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、高橋君は何個の石を取り除くことができますか？
制約
- 1 \leq N \leq 10^4
- 1 \leq K \leq 100
- 1 = A_1 < A_2 < \ldots < A_K \leq N
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_K
出力
答えを出力せよ。
入力例 1
10 2 1 4
出力例 1
5
ゲームの進行の一例は以下の通りです。
- 高橋君が山から 4 個の石を取り除く。
- 青木君が山から 4 個の石を取り除く。
- 高橋君が山から 1 個の石を取り除く。
- 青木君が山から 1 個の石を取り除く。
この例では高橋君は 5 個の石を取り除くことができます。高橋君が 6 個以上の石を取り除くことはできないためこれが最大です。
高橋君は 5 個の石を取り除くことができるゲームの進行の例には、他にも次のようなものがあります。
- 高橋君が山から 1 個の石を取り除く。
- 青木君が山から 4 個の石を取り除く。
- 高橋君が山から 4 個の石を取り除く。
- 青木君が山から 1 個の石を取り除く。
入力例 2
11 4 1 2 3 6
出力例 2
8
ゲームの進行の一例は以下の通りです。
- 高橋君が山から 6 個の石を取り除く。
- 青木君が山から 3 個の石を取り除く。
- 高橋君が山から 2 個の石を取り除く。
この例では高橋君は 8 個の石を取り除くことができます。高橋君が 9 個以上の石を取り除くことはできないためこれが最大です。
入力例 3
10000 10 1 2 4 8 16 32 64 128 256 512
出力例 3
5136
Score : 400 points
Problem Statement
Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).
There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.
- Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.
The game ends when the pile has no stones.
If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?
Constraints
- 1 \leq N \leq 10^4
- 1 \leq K \leq 100
- 1 = A_1 < A_2 < \ldots < A_K \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_K
Output
Print the answer.
Sample Input 1
10 2 1 4
Sample Output 1
5
Below is one possible progression of the game.
- Takahashi removes 4 stones from the pile.
- Aoki removes 4 stones from the pile.
- Takahashi removes 1 stone from the pile.
- Aoki removes 1 stone from the pile.
In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.
Below is another possible progression of the game where Takahashi removes 5 stones.
- Takahashi removes 1 stone from the pile.
- Aoki removes 4 stones from the pile.
- Takahashi removes 4 stones from the pile.
- Aoki removes 1 stone from the pile.
Sample Input 2
11 4 1 2 3 6
Sample Output 2
8
Below is one possible progression of the game.
- Takahashi removes 6 stones.
- Aoki removes 3 stones.
- Takahashi removes 2 stones.
In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.
Sample Input 3
10000 10 1 2 4 8 16 32 64 128 256 512
Sample Output 3
5136