実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 個の整数 A _ 1,A _ 2,\ldots,A _ N が与えられます。
これらの値がすべて等しいならば Yes 、そうでなければ No と出力してください。
制約
- 2\leq N\leq100
- 1\leq A _ i\leq100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N
出力
与えられた A _ 1,A _ 2,\ldots,A _ N の値がすべて等しいなら Yes を、そうでなければ No を 1 行で出力せよ。
入力例 1
3 3 2 4
出力例 1
No
A _ 1\neq A _ 2 なので、No と出力してください。
入力例 2
4 3 3 3 3
出力例 2
Yes
A _ 1=A _ 2=A _ 3=A _ 4 なので、Yes と出力してください。
入力例 3
10 73 8 55 26 97 48 37 47 35 55
出力例 3
No
Score : 100 points
Problem Statement
You are given N integers A _ 1,A _ 2,\ldots,A _ N.
If their values are all equal, print Yes; otherwise, print No.
Constraints
- 2\leq N\leq100
- 1\leq A _ i\leq100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N
Output
Print a single line containing Yes if the values of the given A _ 1,A _ 2,\ldots,A _ N are all equal, and No otherwise.
Sample Input 1
3 3 2 4
Sample Output 1
No
We have A _ 1\neq A _ 2, so you should print No.
Sample Input 2
4 3 3 3 3
Sample Output 2
Yes
We have A _ 1=A _ 2=A _ 3=A _ 4, so you should print Yes.
Sample Input 3
10 73 8 55 26 97 48 37 47 35 55
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
水圧は水深のみに依存し、水深 x [m] の場所では \dfrac{x}{100} [MPa] になるものとします。
水深 D [m] の場所の水圧は何 [MPa] ですか？
制約
- 1 \leq D \leq 10000
- D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
D
出力
答えを出力せよ。想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。
入力例 1
1000
出力例 1
10
水深 1000 [m] の場所の水圧は 10 [MPa] です。10.0 や 9.999999 などを出力しても正解となります。
入力例 2
50
出力例 2
0.5
入力例 3
3141
出力例 3
31.41
Score : 100 points
Problem Statement
Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.
What is the water pressure in megapascals at a depth of D meters?
Constraints
- 1 \leq D \leq 10000
- D is an integer.
Input
Input is given from Standard Input in the following format:
D
Output
Print the answer. Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-3}.
Sample Input 1
1000
Sample Output 1
10
The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.
Sample Input 2
50
Sample Output 2
0.5
Sample Input 3
3141
Sample Output 3
31.41
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君には N 人の友達がいます。N 人の友達はそれぞれ、友達 1 、友達 2 、\ldots 、友達 N というあだ名で呼ばれています。
ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達 X に知られてしまいました。
i = 1, 2, \ldots, N について、友達 i が高橋君の秘密を知ったとき、友達 A_i がまだ高橋君の秘密を知らなければ、友達 i は高橋君の秘密を友達 A_i にも教えてしまいます。
高橋君の秘密は最終的に何人の友達に知られることになるでしょうか？
制約
- 2 \leq N \leq 10^5
- 1 \leq X \leq N
- 1 \leq A_i \leq N
- A_i \neq i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \cdots A_N
出力
答えを出力せよ。
入力例 1
4 2 3 1 1 2
出力例 1
3
高橋君の秘密は以下の流れで友達 1 、友達 2 、友達 3 の 3 人に知れ渡ります。
- ある日、高橋君は秘密を友達 2 に知られてしまいました。
- 秘密を知った友達 2 は、その秘密を友達 1 に教えます。
- 秘密を知った友達 1 は、その秘密を友達 3 に教えます。
高橋君の秘密は最終的に 3 人の友達に知られることになるため、3 を出力します。
入力例 2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
出力例 2
7
Score : 200 points
Problem Statement
Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.
One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.
How many of Takahashi's friends will learn the secret in the end?
Constraints
- 2 \leq N \leq 10^5
- 1 \leq X \leq N
- 1 \leq A_i \leq N
- A_i \neq i
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
4 2 3 1 1 2
Sample Output 1
3
Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.
- One day, Takahashi let Friend 2 learn the secret.
- Friend 2 shares it with Friend 1.
- Friend 1 shares it with Friend 3.
In the end, three of his friends learn the secret, so we print 3.
Sample Input 2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
Sample Output 2
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
AtCoder Land の入り口には 1 つのチケット売り場があり、来園客はこのチケット売り場の前に一列に並んで順にチケットを購入します。 チケットの購入手続きには一人当たり A 秒かかり、列の先頭の人がチケットを購入し終わると、（存在すれば）次の人がすぐさま購入手続きを開始します。
現在チケット売り場に並んでいる人はおらず、今から N 人の人が順にチケットを買いに来ます。 具体的には、i 番目の人は今から T_i 秒後にチケット売り場を訪れ、既に列が存在すればその最後尾に並び、存在しなければすぐさま購入手続きを開始します。 ここで、T_1< T_2< \dots < T_N です。
各 i\ (1\leq i\leq N) について、i 番目の人がチケットを購入し終わるのは今から何秒後か求めてください。
制約
- 1\leq N \leq 100
- 0\leq T_1< T_2< \dots < T_N\leq 10^6
- 1\leq A\leq 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A T_1 T_2 \dots T_N
出力
N 行出力せよ。 i\ (1\leq i \leq N) 行目には、i 番目の人がチケットを購入し終わるのは今から何秒後かを整数として出力せよ。
入力例 1
3 4 0 2 10
出力例 1
4 8 14
時系列順に以下のように物事が進行します。
- 0 秒後：1 番目の人がチケット売り場を訪れ、チケットの購入手続きを開始する。
- 2 秒後：2 番目の人がチケット売り場を訪れ、1 番目の人の後ろに並ぶ。
- 4 秒後：1 番目の人がチケットを購入し終え、2 番目の人が購入手続きを開始する。
- 8 秒後：2 番目の人がチケットを購入し終える。
- 10 秒後：3 番目の人がチケット売り場を訪れ、チケットの購入手続きを開始する。
- 14 秒後：3 番目の人がチケットを購入し終える。
入力例 2
3 3 1 4 7
出力例 2
4 7 10
時系列順に以下のように物事が進行します。
- 1 秒後：1 番目の人がチケット売り場を訪れ、チケットの購入手続きを開始する。
- 4 秒後：1 番目の人がチケットを購入し終えると同時に、2 番目の人がチケット売り場を訪れ、チケットの購入手続きを開始する。
- 7 秒後：2 番目の人がチケットを購入し終えると同時に、3 番目の人がチケット売り場を訪れ、チケットの購入手続きを開始する。
- 10 秒後：3 番目の人がチケットを購入し終える。
入力例 3
10 50000 120190 165111 196897 456895 540000 552614 561627 743796 757613 991216
出力例 3
170190 220190 270190 506895 590000 640000 690000 793796 843796 1041216
Score : 200 points
Problem Statement
At the entrance of AtCoder Land, there is a single ticket booth where visitors line up to purchase tickets one by one. The purchasing process takes A seconds per person. Once the person at the front of the line finishes purchasing their ticket, the next person (if any) immediately starts their purchasing process.
Currently, there is no one in line at the ticket booth, and N people will come to buy tickets one after another. Specifically, the i-th person will arrive at the ticket booth T_i seconds from now. If there is already a line, they will join the end of it; if not, they will start the purchasing process immediately. Here, T_1 < T_2 < \dots < T_N.
For each i\ (1 \leq i \leq N), determine how many seconds from now the i-th person will finish purchasing their ticket.
Constraints
- 1 \leq N \leq 100
- 0 \leq T_1 < T_2 < \dots < T_N \leq 10^6
- 1 \leq A \leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A T_1 T_2 \dots T_N
Output
Print N lines. The i-th line should contain the number of seconds from now that the i-th person will finish purchasing their ticket.
Sample Input 1
3 4 0 2 10
Sample Output 1
4 8 14
The events proceed in the following order:
- At 0 seconds: The 1st person arrives at the ticket booth and starts the purchasing process.
- At 2 seconds: The 2nd person arrives at the ticket booth and joins the line behind the 1st person.
- At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person starts the purchasing process.
- At 8 seconds: The 2nd person finishes purchasing their ticket.
- At 10 seconds: The 3rd person arrives at the ticket booth and starts the purchasing process.
- At 14 seconds: The 3rd person finishes purchasing their ticket.
Sample Input 2
3 3 1 4 7
Sample Output 2
4 7 10
The events proceed in the following order:
- At 1 second: The 1st person arrives at the ticket booth and starts the purchasing process.
- At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person arrives at the ticket booth and starts the purchasing process.
- At 7 seconds: The 2nd person finishes purchasing their ticket, and the 3rd person arrives at the ticket booth and starts the purchasing process.
- At 10 seconds: The 3rd person finishes purchasing their ticket.
Sample Input 3
10 50000 120190 165111 196897 456895 540000 552614 561627 743796 757613 991216
Sample Output 3
170190 220190 270190 506895 590000 640000 690000 793796 843796 1041216
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。
(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。
順列とは？
(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。
辞書順とは？
長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
制約
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 \ldots P_N
出力
求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。
入力例 1
3 3 1 2
出力例 1
2 3 1
(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。
入力例 2
10 9 8 6 5 10 3 1 2 4 7
出力例 2
9 8 6 5 10 2 7 4 3 1
Score : 300 points
Problem Statement
You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).
Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.
What are permutations?
A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.
What is lexicographical order?
For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
Constraints
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P_1 \ldots P_N
Output
Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.
Sample Input 1
3 3 1 2
Sample Output 1
2 3 1
Here are the permutations of (1, 2, 3) in ascending lexicographical order.
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).
Sample Input 2
10 9 8 6 5 10 3 1 2 4 7
Sample Output 2
9 8 6 5 10 2 7 4 3 1