Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,\dots,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。
制約
- 入力は全て整数
- 1 \le L \le R \le N \le 100
入力
入力は以下の形式で標準入力から与えられる。
N L R
出力
操作後の数列を A'=(A'_1,A'_2,\dots,A'_N) として、以下の形式で出力せよ。
A'_1 A'_2 \dots A'_N
入力例 1
5 2 3
出力例 1
1 3 2 4 5
最初、 A=(1,2,3,4,5) です。
2 項目から 3 項目までを逆順に並べ替えた後の数列は (1,3,2,4,5) なので、これを出力してください。
入力例 2
7 1 1
出力例 2
1 2 3 4 5 6 7
L=R である場合もあります。
入力例 3
10 1 10
出力例 3
10 9 8 7 6 5 4 3 2 1
L=1 や R=N である場合もあります。
Score : 100 points
Problem Statement
You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.
Constraints
- All input values are integers.
- 1 \leq L \leq R \leq N \leq 100
Input
The input is given from Standard Input in the following format:
N L R
Output
Let A' = (A'_1, A'_2, \dots, A'_N) be the sequence after the operation. Print it in the following format:
A'_1 A'_2 \dots A'_N
Sample Input 1
5 2 3
Sample Output 1
1 3 2 4 5
Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.
Sample Input 2
7 1 1
Sample Output 2
1 2 3 4 5 6 7
It is possible that L = R.
Sample Input 3
10 1 10
Sample Output 3
10 9 8 7 6 5 4 3 2 1
It is possible that L = 1 or R = N.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正整数 N,K 及び長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。
制約
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A には K の倍数が 1 個以上含まれる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
A に含まれる要素のうち、K の倍数であるもの全てを K で割った値を、空白区切りで昇順に出力せよ。
入力例 1
5 2 2 5 6 7 10
出力例 1
1 3 5
A に含まれる要素のうち、2 の倍数は 2,6,10 です。それらを 2 で割って得られる 1,3,5 を空白区切りで昇順に出力してください。
入力例 2
3 1 3 4 7
出力例 2
3 4 7
入力例 3
5 10 50 51 54 60 65
出力例 3
5 6
Score: 100 points
Problem Statement
You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).
Extract all elements of A that are multiples of K, divide them by K, and print the quotients.
Constraints
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A has at least one multiple of K.
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Divide all elements of A that are multiples of K and print the quotients in ascending order with spaces in between.
Sample Input 1
5 2 2 5 6 7 10
Sample Output 1
1 3 5
The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.
Sample Input 2
3 1 3 4 7
Sample Output 2
3 4 7
Sample Input 3
5 10 50 51 54 60 65
Sample Output 3
5 6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
1,2,3,4,5,6 の 6 種類の目が出るサイコロを 2 つ振ったときに、次の 2 つの条件の少なくとも一方を満たす確率を求めてください。
- 2 つの出目の合計が X 以上である。
- 2 つの出目の差の絶対値が Y 以上である。
ここで、どちらのサイコロについても 6 種類のどの目が出るかは同様に確からしく、それぞれのサイコロの出目は独立であるとします。
制約
- 2\leq X\leq13
- 0\leq Y\leq6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
2 つのサイコロの出目が 2 つの条件の少なくとも一方を満たす確率を出力せよ。 出力された値と真の値との絶対誤差が 10 ^ {-9} 以下のとき、正答と判定される。
入力例 1
9 3
出力例 1
0.555555555555555555555555555555
2 つのサイコロの出目がそれぞれ x と y であることを (x,y) で表すことにすると、それぞれの条件を満たすのは次の場合です。
- 2 つのサイコロの出目の和が 9 以上になるのは、(3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6) のとき
- 2 つのサイコロの出目の差が 3 以上になるのは、(1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3) のとき
これらの条件の少なくとも一方を満たすのは (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6) の 20 通りのいずれかのときです。
よって、求める答えは \dfrac{20}{36}=\dfrac59=0.5555555555\ldots です。
絶対誤差が 10 ^ {-9} 以下のとき正答と判定されるので、0.5555555565 や 0.55555555456789 などと出力しても正解となります。
入力例 2
13 6
出力例 2
0
2 つのサイコロの出目の和が 13 以上になることも、差が 6 以上になることもありません。
よって、求める答えは 0 です。
入力例 3
10 3
出力例 3
0.5
Score : 250 points
Problem Statement
Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:
- The sum of the two outcomes is at least X.
- The absolute difference of the two outcomes is at least Y.
Each face of each die is equally likely, and the two dice are independent.
Constraints
- 2 \le X \le 13
- 0 \le Y \le 6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X Y
Output
Output the probability that the two outcomes satisfy at least one of the two conditions. Your answer is accepted if its absolute error from the true value is at most 10^{-9}.
Sample Input 1
9 3
Sample Output 1
0.555555555555555555555555555555
Let (x,y) denote the event that the dice show x and y.
- The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
- The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).
At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).
Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.
Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.
Sample Input 2
13 6
Sample Output 2
0
Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.
Thus, the answer is 0.
Sample Input 3
10 3
Sample Output 3
0.5
Time Limit: 2 sec / Memory Limit: 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
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 人の生徒が 4 日間にわたる試験を受けています。
それぞれの日に行われる試験は 300 点満点です。すなわち、4 日間を通した試験の満点は 1200 点です。
現在 3 日目までの試験が終わり、これから 4 日目の試験が行われようとしています。i \, (1 \leq i \leq N) 番目の生徒は j \, (1 \leq j \leq 3) 日目の試験で P_{i, j} 点獲得しました。
それぞれの生徒について、4 日目の試験後に上位 K 位以内に入っていることがあり得るかどうか判定してください。
ただし、4 日目の試験後の生徒の順位は、その生徒よりも 4 日間の合計点が高い生徒の人数に 1 を加えた値として定めます。
制約
- 1 \leq K \leq N \leq 10^5
- 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}
出力
N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 番目の生徒が 4 日目の試験後に上位 K 位以内に入っていることがあり得るならば Yes と、そうでないならば No と出力せよ。
入力例 1
3 1 178 205 132 112 220 96 36 64 20
出力例 1
Yes Yes No
4 日目に全員が 100 点を取ると、1 番目の生徒が 1 位になります。 4 日目に 2 番目の生徒が 100 点を取り、それ以外の生徒が 0 点を取ると、2 番目の生徒が 1 位になります。 3 番目の生徒が 1 位になることはあり得ません。
入力例 2
2 1 300 300 300 200 200 200
出力例 2
Yes Yes
入力例 3
4 2 127 235 78 192 134 298 28 56 42 96 120 250
出力例 3
Yes Yes No Yes
Score : 300 points
Problem Statement
N students are taking a 4-day exam.
There is a 300-point test on each day, for a total of 1200 points.
The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).
For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.
Constraints
- 1 \leq K \leq N \leq 10^5
- 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}
Output
Print N lines. The i-th line (1 \leq i \leq N) should contain Yes if it is possible that the i-th student is ranked in the top K after the fourth day, and No otherwise.
Sample Input 1
3 1 178 205 132 112 220 96 36 64 20
Sample Output 1
Yes Yes No
If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.
Sample Input 2
2 1 300 300 300 200 200 200
Sample Output 2
Yes Yes
Sample Input 3
4 2 127 235 78 192 134 298 28 56 42 96 120 250
Sample Output 3
Yes Yes No Yes