実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
消毒液の入ったボトルがあり、その消毒液によってちょうど M 本の手を消毒することができます。
N 人の宇宙人が順に手の消毒を行いに来ます。
i 人目 (1\leq i\leq N) の宇宙人は H_i 本の手を持っており、それぞれ自身のすべての手を 1 回ずつ消毒したいと考えています。
何人目の宇宙人までがすべての手を消毒できるか求めてください。
ただし、ある宇宙人が消毒を始める時点で、自身のすべての手を消毒する分の消毒液が残っていなかったとしても、その宇宙人はその消毒液を使い切ってしまうものとします。
制約
- 1\leq N,M\leq 100
- 1\leq H_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M H_1 H_2 \ldots H_N
出力
何人目の宇宙人までが自身のすべての手を消毒できるか出力せよ。
入力例 1
5 10 2 3 2 5 3
出力例 1
3
次の手順で宇宙人は自身の手を消毒します。
- 1 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、10-2=8 本の手を消毒できます。
- 2 人目の宇宙人は自身の 3 本の手を消毒します。残りの消毒液によって、8-3=5 本の手を消毒できます。
- 3 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、5-2=3 本の手を消毒できます。
- 4 人目の宇宙人は 5 本の手を持っていますが、消毒液は 3 本分しかないため消毒液を使い切り、かつ自身のすべての手を消毒できません。
よって、3 人目の宇宙人までが自身のすべての手を消毒できるため、3 を出力します。
入力例 2
5 10 2 3 2 3 5
出力例 2
4
入力例 3
1 5 1
出力例 3
1
すべての宇宙人が自身の手を消毒することができます。
Score : 100 points
Problem Statement
There is a bottle of disinfectant that can disinfect exactly M hands.
N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.
Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.
Constraints
- 1 \leq N, M \leq 100
- 1 \leq H_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M H_1 H_2 \ldots H_N
Output
Print the number of aliens who can disinfect all of their hands.
Sample Input 1
5 10 2 3 2 5 3
Sample Output 1
3
The aliens disinfect their hands in the following steps:
- The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
- The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
- The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
- The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.
Thus, the first three aliens can disinfect all of their hands, so print 3.
Sample Input 2
5 10 2 3 2 3 5
Sample Output 2
4
Sample Input 3
1 5 1
Sample Output 3
1
All aliens can disinfect their hands.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。 S の長さは 1 以上かつ 3 以下です。
S を繰り返して得られる文字列であって、長さが 6 のものを出力してください。
本問題の制約下で、そのような文字列はただ一つ存在することが示せます。
制約
- S は英小文字からなる長さ 1 以上 3 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えとなる長さ 6 の文字列を出力せよ。
入力例 1
abc
出力例 1
abcabc
S = abc を繰り返してできる文字列として、abc 、abcabc 、abcabcabc 、abcabcabcabc などがあります。
そのうち、長さが 6 のものは abcabc です。よって、abcabc と出力します。
入力例 2
zz
出力例 2
zzzzzz
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English characters. The length of S is between 1 and 3, inclusive.
Print the string of length 6 that is a repetition of S.
It can be shown that there uniquely exists such a string under the Constraints of this problem.
Constraints
- S is a string consisting of lowercase English characters of length between 1 and 3, inclusive.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer string, which is of length 6.
Sample Input 1
abc
Sample Output 1
abcabc
These are strings that are repetitions of S = abc: abc, abcabc, abcabcabc, abcabcabcabc, and so on.
Among them, abcabc has the length of 6, so abcabc should be printed.
Sample Input 2
zz
Sample Output 2
zzzzzz
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 150 点
問題文
実数 X が小数点以下第 3 位まで与えられます。
実数 X を以下の条件を満たすように出力してください。
- 小数点以下の部分について、末尾に
0を付けない - 末尾に過剰な小数点を付けない
制約
- 0 \le X < 100
- X は小数点以下第 3 位まで与えられる
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
1.012
出力例 1
1.012
1.012 はそのまま出力しても構いません。
入力例 2
12.340
出力例 2
12.34
12.340 を末尾に 0 を付けずに出力すると 12.34 となります。
入力例 3
99.900
出力例 3
99.9
99.900 を末尾に 0 を付けずに出力すると 99.9 となります。
入力例 4
0.000
出力例 4
0
0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。
Score : 150 points
Problem Statement
A real number X is given to the third decimal place.
Print the real number X under the following conditions.
- The decimal part must not have trailing
0s. - There must not be an unnecessary trailing decimal point.
Constraints
- 0 \le X < 100
- X is given to the third decimal place.
Input
The input is given from Standard Input in the following format:
X
Output
Output the answer.
Sample Input 1
1.012
Sample Output 1
1.012
1.012 can be printed as it is.
Sample Input 2
12.340
Sample Output 2
12.34
Printing 12.340 without the trailing 0 results in 12.34.
Sample Input 3
99.900
Sample Output 3
99.9
Printing 99.900 without the trailing 0s results in 99.9.
Sample Input 4
0.000
Sample Output 4
0
Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。
N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。
- 人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。
最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。
K X_1 X_2 \ldots X_K
すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。
入力例 1
5 3 1 4 5 4
出力例 1
2 2 4
5 人の行動は下記の通りです。
- 人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
- 人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
- 人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
- 人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
- 人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。
よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。
入力例 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
出力例 2
10 1 2 5 6 8 11 14 17 18 20
Score : 200 points
Problem Statement
There are N people whose IDs are 1, 2, \ldots, and N.
Each of person 1, person 2, \ldots, and person N performs the following action once in this order:
- If person i's ID has not been called out yet, call out person A_i's ID.
Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:
K X_1 X_2 \ldots X_K
In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.
Sample Input 1
5 3 1 4 5 4
Sample Output 1
2 2 4
The five people's actions are as follows.
- Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
- Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
- Person 3's ID has already been called out by person 1, so nothing happens.
- Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
- Person 5's ID has already been called out by person 4, so nothing happens.
Therefore, person 2 and 4's IDs are not called out until the end.
Sample Input 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
Sample Output 2
10 1 2 5 6 8 11 14 17 18 20
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
1\leq l\leq r\leq N を満たす整数の組 (l,r) であって、数列 (A_l,A_{l+1},\dots,A_r) が等差数列であるようなものが何通りあるか求めてください。
なお、数列 (x_1,x_2,\dots,x_{|x|}) が等差数列であるとは、ある d が存在して x_{i+1}-x_i=d\ (1\leq i < |x|) であることをいいます。 特に、長さ 1 の数列は常に等差数列です。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 3 6 9 3
出力例 1
8
条件を満たす整数の組 (l,r) は (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3) の 8 通りです。
実際、(l,r)=(1,3) のとき (A_l,\dots,A_r)=(3,6,9) は等差数列なので条件を満たしますが、 (l,r)=(2,4) のとき (A_l,\dots,A_r)=(6,9,3) は等差数列ではないので条件を満たしません。
入力例 2
5 1 1 1 1 1
出力例 2
15
すべての整数の組 (l,r)\ (1\leq l\leq r\leq 5) が条件を満たします。
入力例 3
8 87 42 64 86 72 58 44 30
出力例 3
22
Score : 300 points
Problem Statement
You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.
A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 3 6 9 3
Sample Output 1
8
There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).
Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.
Sample Input 2
5 1 1 1 1 1
Sample Output 2
15
All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.
Sample Input 3
8 87 42 64 86 72 58 44 30
Sample Output 3
22