Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋くんと青木くんがゲームを行います。
はじめ、高橋くんは A 個、青木くんは B 個のアメを持っています。
C=0 ならば高橋くんが先手、C=1 ならば青木くんが先手で、高橋くんと青木くんは以下の操作を交互に繰り返します。
- 自分の持っているアメを 1 個食べる。
先に操作を行えなくなった者の負けです。どちらが勝つでしょうか?
制約
- 入力は全て整数
- 0 ≤ A, B ≤ 100
- C \in \{0, 1\}
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
高橋くんが勝つならば Takahashi
を、青木くんが勝つならば Aoki
を出力せよ。
入力例 1
2 1 0
出力例 1
Takahashi
はじめ、高橋くんと青木くんの持っているアメの個数はそれぞれ 2, 1 個です。 ゲームは以下のように進行します。
- 高橋くんがアメを 1 個食べる。
- 青木くんがアメを 1 個食べる。
- 高橋くんがアメを 1 個食べる。
- 青木くんはアメを持っていないので、高橋くんが勝つ。
入力例 2
2 2 0
出力例 2
Aoki
入力例 3
2 2 1
出力例 3
Takahashi
Score : 100 points
Problem Statement
Takahashi and Aoki will play a game against each other.
Initially, Takahashi and Aoki have A and B candies, respectively.
They will alternately do the operation below. Takahashi goes first if C=0, and Aoki goes first if C=1.
- Eat one of the candies he has.
The person who first becomes unable to do the operation loses. Which person will win?
Constraints
- All values in input are integers.
- 0 ≤ A, B ≤ 100
- C \in \{0, 1\}
Input
Input is given from Standard Input in the following format:
A B C
Output
If Takahashi will win, print Takahashi
; if Aoki will win, print Aoki
.
Sample Input 1
2 1 0
Sample Output 1
Takahashi
Initially, Takahashi and Aoki have 2 and 1 candy(ies), respectively. The game will proceed as follows:
- Takahashi eats his candy.
- Aoki eats his candy.
- Takahashi eats his candy.
- Aoki has no more candies, so Takahashi wins.
Sample Input 2
2 2 0
Sample Output 2
Aoki
Sample Input 3
2 2 1
Sample Output 3
Takahashi
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
魔法使いの高橋君は魔物と戦っています。
高橋君は N 種類の呪文を使うことができます。
i 番目の呪文は詠唱に X_i 秒かかり、威力は Y_i です。
ただし、この魔物は強いので、詠唱に S 秒以上かかる呪文や、威力が D 以下の呪文ではダメージを与えられません。
また、呪文以外の方法でダメージを与えることもできません。
高橋君は魔物にダメージを与えられるでしょうか?
制約
- 入力は全て整数
- 1 ≤ N ≤ 100
- 1 ≤ X_i ≤ 10^9
- 1 ≤ Y_i ≤ 10^9
- 1 ≤ S ≤ 10^9
- 1 ≤ D ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N S D X_1 Y_1 \vdots X_N Y_N
出力
魔物にダメージを与えられるならば Yes
を、与えられないならば No
を出力せよ。
入力例 1
4 9 9 5 5 15 5 5 15 15 15
出力例 1
Yes
2, 4 番目の呪文は詠唱の時間が長いためダメージを与えられません。
また、 1, 2 番目の呪文は威力が足りないためダメージを与えられません。
したがって、3 番目の呪文でのみダメージを与えられます。
入力例 2
3 691 273 691 997 593 273 691 273
出力例 2
No
入力例 3
7 100 100 10 11 12 67 192 79 154 197 142 158 20 25 17 108
出力例 3
Yes
7 番目の呪文でのみダメージを与えられます。
Score : 200 points
Problem Statement
Takahashi, the magician, is fighting with a monster.
He can use N spells.
The i-th spell takes X_i seconds to cast and has a power Y_i.
However, the monster is strong enough to avoid taking damage from spells taking S or more seconds to cast and spells with powers D or less.
Also, there is nothing other than spells that can do damage to the monster.
Can Takahashi do damage to the monster?
Constraints
- All values in input are integers.
- 1 ≤ N ≤ 100
- 1 ≤ X_i ≤ 10^9
- 1 ≤ Y_i ≤ 10^9
- 1 ≤ S ≤ 10^9
- 1 ≤ D ≤ 10^9
Input
Input is given from Standard Input in the following format:
N S D X_1 Y_1 \vdots X_N Y_N
Output
If Takahashi can do damage to the monster, print Yes
; otherwise, print No
.
Sample Input 1
4 9 9 5 5 15 5 5 15 15 15
Sample Output 1
Yes
The second and fourth spells take too much time to do damage.
Also, the first and second spells do not have enough powers to do damage.
Thus, only the third spell can do damage.
Sample Input 2
3 691 273 691 997 593 273 691 273
Sample Output 2
No
Sample Input 3
7 100 100 10 11 12 67 192 79 154 197 142 158 20 25 17 108
Sample Output 3
Yes
Only the seventh spell can do damage.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
1, 2, \dots, N の番号がついた N 個の皿と、1, 2, \dots, M の番号がついた M 個の条件があります。
条件 i は、皿 A_i と皿 B_i の両方にボールが (1 個以上) 置かれているとき満たされます。
1, 2, \dots, K の番号がついた K 人の人がいて、人 i は皿 C_i か皿 D_i のどちらか一方にボールを置きます。
満たされる条件の個数は最大でいくつでしょうか?
制約
- 入力は全て整数
- 2 ≤ N ≤ 100
- 1 ≤ M ≤ 100
- 1 ≤ A_i < B_i ≤ N
- 1 ≤ K ≤ 16
- 1 ≤ C_i < D_i ≤ N
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M K C_1 D_1 \vdots C_K D_K
出力
答えを出力せよ。
入力例 1
4 4 1 2 1 3 2 4 3 4 3 1 2 1 3 2 3
出力例 1
2
例えば、人 1, 2, 3 がそれぞれ皿 1, 3, 2 にボールを置くと、条件 1, 2 の 2 つが満たされます。
入力例 2
4 4 1 2 1 3 2 4 3 4 4 3 4 1 2 2 4 2 4
出力例 2
4
例えば、人 1, 2, 3, 4 がそれぞれ皿 3, 1, 2, 4 にボールを置くと、全ての条件が満たされます。
入力例 3
6 12 2 3 4 6 1 2 4 5 2 6 1 5 4 5 1 3 1 2 2 6 2 3 2 5 5 3 5 1 4 2 6 4 6 5 6
出力例 3
9
Score : 300 points
Problem Statement
We have N dishes numbered 1, 2, \dots, N and M conditions numbered 1, 2, \dots, M.
Condition i is satisfied when both Dish A_i and Dish B_i have (one or more) balls on them.
There are K people numbered 1, 2, \dots, K. Person i will put a ball on Dish C_i or Dish D_i.
At most how many conditions will be satisfied?
Constraints
- All values in input are integers.
- 2 ≤ N ≤ 100
- 1 ≤ M ≤ 100
- 1 ≤ A_i < B_i ≤ N
- 1 ≤ K ≤ 16
- 1 ≤ C_i < D_i ≤ N
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M K C_1 D_1 \vdots C_K D_K
Output
Print the answer.
Sample Input 1
4 4 1 2 1 3 2 4 3 4 3 1 2 1 3 2 3
Sample Output 1
2
For example, if People 1, 2, 3 put their balls on Dishes 1, 3, 2, respectively, Conditions 1 and 2 will be satisfied.
Sample Input 2
4 4 1 2 1 3 2 4 3 4 4 3 4 1 2 2 4 2 4
Sample Output 2
4
For example, if People 1, 2, 3, 4 put their balls on Dishes 3, 1, 2, 4, respectively, all conditions will be satisfied.
Sample Input 3
6 12 2 3 4 6 1 2 4 5 2 6 1 5 4 5 1 3 1 2 2 6 2 3 2 5 5 3 5 1 4 2 6 4 6 5 6
Sample Output 3
9
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか?
制約
- 1 ≤ N ≤ 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
12
出力例 1
4
- [12]
- [3, 4, 5]
- [-2, -1, 0, 1, 2, 3, 4, 5]
- [-11, -10, -9, \dots, 10, 11, 12]
の 4 個です。
入力例 2
1
出力例 2
2
- [1]
- [0, 1]
の 2 個です。
入力例 3
963761198400
出力例 3
1920
Score : 400 points
Problem Statement
How many arithmetic progressions consisting of integers with a common difference of 1 have a sum of N?
Constraints
- 1 ≤ N ≤ 10^{12}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
12
Sample Output 1
4
We have four such progressions:
- [12]
- [3, 4, 5]
- [-2, -1, 0, 1, 2, 3, 4, 5]
- [-11, -10, -9, \dots, 10, 11, 12]
Sample Input 2
1
Sample Output 2
2
We have two such progressions:
- [1]
- [0, 1]
Sample Input 3
963761198400
Sample Output 3
1920
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
AtCoder 王国には 1, 2, \dots, N の番号がついた N 種類の魔法石が流通しています。
高橋くんは、魔法石を一列に並べて飾りを作ろうとしています。
魔法石には隣り合わせにできる組とできない組があります。
隣り合わせにできる組は (魔法石 A_1, 魔法石 B_1), (魔法石 A_2, 魔法石 B_2), \dots, (魔法石 A_M, 魔法石 B_M) の M 組で、それ以外の組は隣り合わせることができません。(これらの組において、石の順序は不問です。)
魔法石 C_1, C_2, \dots, C_K をそれぞれ 1 個以上含む魔法石の列を作ることができるか判定し、作れる場合はそのような列を作るのに必要な魔法石の個数の最小値を求めてください。
制約
- 入力は全て整数
- 1 ≤ N ≤ 10^5
- 0 ≤ M ≤ 10^5
- 1 ≤ A_i < B_i ≤ N
- i ≠ j ならば (A_i, B_i) ≠ (A_j, B_j)
- 1 ≤ K ≤ 17
- 1 ≤ C_1 < C_2 < \dots < C_K ≤ N
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \hspace{7mm}\vdots A_M B_M K C_1 C_2 \cdots C_K
出力
魔法石 C_1, C_2, \dots, C_K を含む魔法石の列を作るのに必要な魔法石の個数の最小値を出力せよ。
作ることができない場合、代わりに -1
を出力せよ。
入力例 1
4 3 1 4 2 4 3 4 3 1 2 3
出力例 1
5
例えば、魔法石を [1, 4, 2, 4, 3] と並べると、魔法石 1, 2, 3 を含む長さ 5 の列を作ることができます。
入力例 2
4 3 1 4 2 4 1 2 3 1 2 3
出力例 2
-1
入力例 3
10 10 3 9 3 8 8 10 2 10 5 8 6 8 5 7 6 7 1 6 2 4 4 1 2 7 9
出力例 3
11
例えば、魔法石を [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2] と並べると、魔法石 1, 2, 7, 9 を含む長さ 11 の列を作ることができます。
Score : 500 points
Problem Statement
There are N kinds of magical gems, numbered 1, 2, \ldots, N, distributed in the AtCoder Kingdom.
Takahashi is trying to make an ornament by arranging gems in a row.
For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have M pairs for which the two gems can be adjacent: (Gem A_1, Gem B_1), (Gem A_2, Gem B_2), \ldots, (Gem A_M, Gem B_M). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)
Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds C_1, C_2, \dots, C_K. If the answer is yes, find the minimum number of stones needed to form such a sequence.
Constraints
- All values in input are integers.
- 1 ≤ N ≤ 10^5
- 0 ≤ M ≤ 10^5
- 1 ≤ A_i < B_i ≤ N
- If i ≠ j, (A_i, B_i) ≠ (A_j, B_j).
- 1 ≤ K ≤ 17
- 1 ≤ C_1 < C_2 < \dots < C_K ≤ N
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \hspace{7mm}\vdots A_M B_M K C_1 C_2 \cdots C_K
Output
Print the minimum number of stones needed to form a sequence of gems that has one or more gems of each of the kinds C_1, C_2, \dots, C_K.
If such a sequence cannot be formed, print -1
instead.
Sample Input 1
4 3 1 4 2 4 3 4 3 1 2 3
Sample Output 1
5
For example, by arranging the gems in the order [1, 4, 2, 4, 3], we can form a sequence of length 5 with Gems 1, 2, 3.
Sample Input 2
4 3 1 4 2 4 1 2 3 1 2 3
Sample Output 2
-1
Sample Input 3
10 10 3 9 3 8 8 10 2 10 5 8 6 8 5 7 6 7 1 6 2 4 4 1 2 7 9
Sample Output 3
11
For example, by arranging the gems in the order [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2], we can form a sequence of length 11 with Gems 1, 2, 7, 9.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0, 1, 2, \dots, N - 1 を並び替えた数列 A = [a_0, a_1, a_2, \dots, a_{N-1}] が与えられます。
k = 0, 1, 2, \dots, N - 1 のそれぞれについて、b_i = a_{i+k \bmod N} で定義される数列 B = [b_0, b_1, b_2, \dots, b_{N-1}] の転倒数を求めてください。
転倒数とは
数列 A = [a_0, a_1, a_2, \dots, a_{N-1}] の転倒数とは、i < j かつ a_i > a_j を満たす添字の組 (i, j) の個数のことです。制約
- 入力は全て整数
- 2 ≤ N ≤ 3 \times 10^5
- a_0, a_1, a_2, \dots, a_{N-1} は 0, 1, 2, \dots, N - 1 の並び替えである
入力
入力は以下の形式で標準入力から与えられる。
N a_0 a_1 a_2 \cdots a_{N-1}
出力
N 行出力せよ。
i + 1 行目には、k = i としたときの答えを出力せよ。
入力例 1
4 0 1 2 3
出力例 1
0 3 4 3
A = [0, 1, 2, 3] です。
k = 0 のとき、B = [0, 1, 2, 3] の転倒数は 0 です。
k = 1 のとき、B = [1, 2, 3, 0] の転倒数は 3 です。
k = 2 のとき、B = [2, 3, 0, 1] の転倒数は 4 です。
k = 3 のとき、B = [3, 0, 1, 2] の転倒数は 3 です。
入力例 2
10 0 3 1 5 4 2 9 6 8 7
出力例 2
9 18 21 28 27 28 33 24 21 14
Score : 600 points
Problem Statement
Given is a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}] that is a permutation of 0, 1, 2, \dots, N - 1.
For each k = 0, 1, 2, \dots, N - 1, find the inversion number of the sequence B = [b_0, b_1, b_2, \dots, b_{N-1}] defined as b_i = a_{i+k \bmod N}.
What is inversion number?
The inversion number of a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}] is the number of pairs of indices (i, j) such that i < j and a_i > a_j.Constraints
- All values in input are integers.
- 2 ≤ N ≤ 3 \times 10^5
- a_0, a_1, a_2, \dots, a_{N-1} is a permutation of 0, 1, 2, \dots, N - 1.
Input
Input is given from Standard Input in the following format:
N a_0 a_1 a_2 \cdots a_{N-1}
Output
Print N lines.
The (i + 1)-th line should contain the answer for the case k = i.
Sample Input 1
4 0 1 2 3
Sample Output 1
0 3 4 3
We have A = [0, 1, 2, 3].
For k = 0, the inversion number of B = [0, 1, 2, 3] is 0.
For k = 1, the inversion number of B = [1, 2, 3, 0] is 3.
For k = 2, the inversion number of B = [2, 3, 0, 1] is 4.
For k = 3, the inversion number of B = [3, 0, 1, 2] is 3.
Sample Input 2
10 0 3 1 5 4 2 9 6 8 7
Sample Output 2
9 18 21 28 27 28 33 24 21 14