実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
文字列 A, B, C が与えられます。これがしりとりになっているか判定してください。
つまり、
- A の最後の文字と B の最初の文字が同じ
- B の最後の文字と C の最初の文字が同じ
この 2 つが正しいか判定してください。
両方とも正しいならば YES、そうでないならば NO を出力してください。
制約
- A, B, C は全て英小文字(
a~z)からなる。 - 1 ≦ |A|, |B|, |C| ≦ 10
- なお、|A|, |B|, |C| は文字列 A, B, C の長さを表します。
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
YES か NO を出力する。
入力例 1
rng gorilla apple
出力例 1
YES
これはしりとりになっています。
入力例 2
yakiniku unagi sushi
出力例 2
NO
A と B はしりとりになっていますが、B と C がしりとりになっていません。
入力例 3
a a a
出力例 3
YES
入力例 4
aaaaaaaaab aaaaaaaaaa aaaaaaaaab
出力例 4
NO
Score : 100 points
Problem Statement
You are given three strings A, B and C. Check whether they form a word chain.
More formally, determine whether both of the following are true:
- The last character in A and the initial character in B are the same.
- The last character in B and the initial character in C are the same.
If both are true, print YES. Otherwise, print NO.
Constraints
- A, B and C are all composed of lowercase English letters (
a-z). - 1 ≤ |A|, |B|, |C| ≤ 10, where |A|, |B| and |C| are the lengths of A, B and C, respectively.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print YES or NO.
Sample Input 1
rng gorilla apple
Sample Output 1
YES
They form a word chain.
Sample Input 2
yakiniku unagi sushi
Sample Output 2
NO
A and B form a word chain, but B and C do not.
Sample Input 3
a a a
Sample Output 3
YES
Sample Input 4
aaaaaaaaab aaaaaaaaaa aaaaaaaaab
Sample Output 4
NO
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。 どんなに大きな整数を選んでもよいですし、整数を 5000 兆個選んでもよいです。 ただし、選ぶ数はすべて A の倍数でなくてはいけません。 また、少なくとも 1 つは整数を選ばなくてはいけません。
そして総和を B で割ったあまりが C となるようにしたいです。 こうなるように整数を選ぶことが出来るか判定してください。
出来るならば YES、そうでないならば NO を出力してください。
制約
- 1 ≦ A ≦ 100
- 1 ≦ B ≦ 100
- 0 ≦ C < B
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
YES か NO を出力する。
入力例 1
7 5 1
出力例 1
YES
たとえば 7, 14 を選ぶと総和は 21 となり、これを 5 で割ったあまりは 1 となります。
入力例 2
2 2 1
出力例 2
NO
偶数をいくつ足したとしても、けっして奇数になることはありません。
入力例 3
1 100 97
出力例 3
YES
1 の倍数、つまりすべての整数が選べるので、97 を選べば良いです。
入力例 4
40 98 58
出力例 4
YES
入力例 5
77 42 36
出力例 5
NO
Score : 200 points
Problem Statement
We ask you to select some number of positive integers, and calculate the sum of them.
It is allowed to select as many integers as you like, and as large integers as you wish. You have to follow these, however: each selected integer needs to be a multiple of A, and you need to select at least one integer.
Your objective is to make the sum congruent to C modulo B. Determine whether this is possible.
If the objective is achievable, print YES. Otherwise, print NO.
Constraints
- 1 ≤ A ≤ 100
- 1 ≤ B ≤ 100
- 0 ≤ C < B
Input
Input is given from Standard Input in the following format:
A B C
Output
Print YES or NO.
Sample Input 1
7 5 1
Sample Output 1
YES
For example, if you select 7 and 14, the sum 21 is congruent to 1 modulo 5.
Sample Input 2
2 2 1
Sample Output 2
NO
The sum of even numbers, no matter how many, is never odd.
Sample Input 3
1 100 97
Sample Output 3
YES
You can select 97, since you may select multiples of 1, that is, all integers.
Sample Input 4
40 98 58
Sample Output 4
YES
Sample Input 5
77 42 36
Sample Output 5
NO
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 300 点
問題文
とある銭湯には、スイッチを押すと T 秒間お湯が出るシャワーがあります。
なお、お湯が出ているときにスイッチを押すと、そのタイミングから T 秒間お湯が出つづけます。 お湯の出る時間が T 秒間延長されるわけではないことに注意してください。
このシャワーの前を、N 人の人がスイッチを押して通り過ぎていきます。 i 人目の人は、1 人目の人がスイッチを押した t_i 秒後にスイッチを押します。
お湯が出る時間の総和は何秒かを求めてください。
制約
- 1 ≦ N ≦ 200,000
- 1 ≦ T ≦ 10^9
- 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≦ 10^9
- T, t_i はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N T t_1 t_2 ... t_N
出力
お湯が出る時間の総和を X 秒として、X を出力する。
入力例 1
2 4 0 3
出力例 1
7
1 人目の人がスイッチを押し、お湯が 3 秒出た後にもう一度スイッチが押され、4 秒間お湯が出続けます。 よって合計で 7 秒間お湯が出ます。
入力例 2
2 4 0 5
出力例 2
8
1 人目の人がスイッチを押して、お湯が出終わった 1 秒後にもう一度スイッチが押されます。
入力例 3
4 1000000000 0 1000 1000000 1000000000
出力例 3
2000000000
入力例 4
1 1 0
出力例 4
1
入力例 5
9 10 0 3 5 7 100 110 200 300 311
出力例 5
67
Score : 300 points
Problem Statement
In a public bath, there is a shower which emits water for T seconds when the switch is pushed.
If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.
N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.
How long will the shower emit water in total?
Constraints
- 1 ≤ N ≤ 200,000
- 1 ≤ T ≤ 10^9
- 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9
- T and each t_i are integers.
Input
Input is given from Standard Input in the following format:
N T t_1 t_2 ... t_N
Output
Assume that the shower will emit water for a total of X seconds. Print X.
Sample Input 1
2 4 0 3
Sample Output 1
7
Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.
Sample Input 2
2 4 0 5
Sample Output 2
8
One second after the shower stops emission of water triggered by the first person, the switch is pushed again.
Sample Input 3
4 1000000000 0 1000 1000000 1000000000
Sample Output 3
2000000000
Sample Input 4
1 1 0
Sample Output 4
1
Sample Input 5
9 10 0 3 5 7 100 110 200 300 311
Sample Output 5
67
実行時間制限: 2 sec / メモリ制限: 256 MB
Score : 400 points
Problem Statement
You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.
You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.
Your objective is to maximize the total value of the selected items.
Constraints
- 1 ≤ N ≤ 100
- 1 ≤ W ≤ 10^9
- 1 ≤ w_i ≤ 10^9
- For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.
- 1 ≤ v_i ≤ 10^7
- W, each w_i and v_i are integers.
Input
Input is given from Standard Input in the following format:
N W w_1 v_1 w_2 v_2 : w_N v_N
Output
Print the maximum possible total value of the selected items.
Sample Input 1
4 6 2 1 3 4 4 10 3 4
Sample Output 1
11
The first and third items should be selected.
Sample Input 2
4 6 2 1 3 7 4 10 3 6
Sample Output 2
13
The second and fourth items should be selected.
Sample Input 3
4 10 1 100 1 100 1 100 1 100
Sample Output 3
400
You can take everything.
Sample Input 4
4 1 10 100 10 100 10 100 10 100
Sample Output 4
0
You can take nothing.
配点 : 400 点
問題文
あなたは N 個の物と、強度 W のバッグを持っています。 i 個目の物は、重さが w_i で価値が v_i です。
あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は W 以下でなくてはいけません。
あなたは、バッグに入れた物の価値の総和を最大化したいです。
制約
- 1 ≦ N ≦ 100
- 1 ≦ W ≦ 10^9
- 1 ≦ w_i ≦ 10^9
- すべての i = 2,3,...,N について、w_1 ≦ w_i ≦ w_1 + 3
- 1 ≦ v_i ≦ 10^7
- W, w_i, v_i はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N W w_1 v_1 w_2 v_2 : w_N v_N
出力
価値の総和の最大値を出力する。
入力例 1
4 6 2 1 3 4 4 10 3 4
出力例 1
11
1, 3 個目の物を選ぶと良いです。
入力例 2
4 6 2 1 3 7 4 10 3 6
出力例 2
13
2, 4 個目の物を選ぶと良いです。
入力例 3
4 10 1 100 1 100 1 100 1 100
出力例 3
400
すべての物が選べます。
入力例 4
4 1 10 100 10 100 10 100 10 100
出力例 4
0
1 個も物が選べません。