実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は植物を育てています。その植物の発芽時の高さは 0\,\mathrm{cm} です。発芽した日を 0 日目としたとき、発芽してから i (0 \le i) 日目の夜には 2^i\,\mathrm{cm} 植物の高さが伸びます。
高橋君の身長は H\,\mathrm{cm} です。
高橋君は毎朝この植物と背比べをします。植物の高さが高橋君の身長より高くなるのは発芽から何日目の朝か求めてください。
制約
- 1 \leq H \leq 10^{9}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
H
出力
植物の高さが高橋君の身長より高くなる日は発芽から何日目の朝か出力せよ。
入力例 1
54
出力例 1
6
植物が発芽してからの 1 日ごとの朝の高さは 1\,\mathrm{cm},3\,\mathrm{cm},7\,\mathrm{cm}, 15\,\mathrm{cm},31\,\mathrm{cm},63\,\mathrm{cm} となります。 6 日目の朝に高橋君より高くなるため、 6 を出力します。
入力例 2
7
出力例 2
4
植物が発芽してから 3 日目の朝の高さは 7\,\mathrm{cm} で、 4 日目の朝の高さは 15\,\mathrm{cm} です。 4 日目の朝に高橋君より高くなるため、 4 を出力します。3 日目の朝のときは高橋君と同じ高さですが、高橋君より高くないことに注意してください。
入力例 3
262144
出力例 3
19
Score : 100 points
Problem Statement
Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).
Takahashi's height is H\,\mathrm{cm}.
Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.
Constraints
- 1 \leq H \leq 10^{9}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H
Output
Print an integer representing the first day such that the plant's height is greater than Takahashi's height in the morning.
Sample Input 1
54
Sample Output 1
6
The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.
Sample Input 2
7
Sample Output 2
4
The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.
Sample Input 3
262144
Sample Output 3
19
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) および正整数 P,Q,R,S が与えられます。
ここで、P,Q,R,S は、1\leq P\leq Q<R\leq S \leq N および Q-P=S-R をみたしています。
数列 A の P 番目から Q 番目の項までと R 番目から S 番目の項までを入れ替えた数列を B=(B_1, B_2,\ldots, B_N) とします。
数列 B を出力してください。
制約
- 1\leq N \leq 100
- 1\leq A_i\leq 100
- 1\leq P\leq Q<R\leq S \leq N
- Q-P=S-R
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P Q R S A_1 A_2 \ldots A_N
出力
B_1, B_2,\ldots, B_N を空白区切りで出力せよ。
入力例 1
8 1 3 5 7 1 2 3 4 5 6 7 8
出力例 1
5 6 7 4 1 2 3 8
数列 A=(1,2,3,4,5,6,7,8) の 1 番目から 3 番目の項 (1,2,3) と 5 番目から 7 番目までの項 (5,6,7) を 入れ替えると, B=(5,6,7,4,1,2,3,8) となります。 よってこれを空白区切りで出力します。
入力例 2
5 2 3 4 5 2 2 1 1 1
出力例 2
2 1 1 2 1
数列には同じ整数が複数回現れる事もあります。
入力例 3
2 1 1 2 2 50 100
出力例 3
100 50
入力例 4
10 2 4 7 9 22 75 26 45 72 81 47 29 97 2
出力例 4
22 47 29 97 72 81 75 26 45 2
Score : 100 points
Problem Statement
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.
Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.
Constraints
- 1\leq N \leq 100
- 1\leq A_i\leq 100
- 1\leq P\leq Q<R\leq S \leq N
- Q-P=S-R
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P Q R S A_1 A_2 \ldots A_N
Output
Print B_1, B_2,\ldots, B_N, with spaces in between.
Sample Input 1
8 1 3 5 7 1 2 3 4 5 6 7 8
Sample Output 1
5 6 7 4 1 2 3 8
Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.
Sample Input 2
5 2 3 4 5 2 2 1 1 1
Sample Output 2
2 1 1 2 1
The same integer may occur multiple times in the sequence.
Sample Input 3
2 1 1 2 2 50 100
Sample Output 3
100 50
Sample Input 4
10 2 4 7 9 22 75 26 45 72 81 47 29 97 2
Sample Output 4
22 47 29 97 72 81 75 26 45 2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
AtCoder Land では時報がモールス信号で行なわれます。高橋君はこのモールス信号を解読したいです。
N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。S_i (1 \leq i \leq N) は . と - からなる文字列で、0 以上 9 以下のある数字に対応するモールス符号です。N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。
数字とモールス符号の対応は以下の通りです。
0 ----- 1 .---- 2 ..--- 3 ...-- 4 ....- 5 ..... 6 -.... 7 --... 8 ---.. 9 ----.
制約
- 1 \leq N \leq 100
- N は整数
- S_i (1 \leq i \leq N) は
.と-からなる文字列 - S_i (1 \leq i \leq N) は 0 以上 9 以下のある数字に対応するモールス符号
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。
入力例 1
3 ...-- ..... ---..
出力例 1
358
...-- は 3 と、..... は 5 と、---.. は 8 と復号されます。よって、358 を出力します。
入力例 2
10 ----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----.
出力例 2
0123456789
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。
1 x: A の末尾に x を追加する。2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。
制約
- 1 \leq Q \leq 100
- 1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
- 2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
クエリは以下の 2 つのいずれかの形式である。
1 x
2 k
出力
2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。
入力例 1
5 1 20 1 30 2 1 1 40 2 3
出力例 1
30 20
- 最初 A は空である。
- 1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
- 2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
- 3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
- 4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
- 5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。
Score: 200 points
Problem Statement
You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:
1 x: Append x to the end of A.2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.
Constraints
- 1 \leq Q \leq 100
- In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
- In the second type of query, k is a positive integer not greater than the current length of sequence A.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in one of the following two formats:
1 x
2 k
Output
Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.
Sample Input 1
5 1 20 1 30 2 1 1 40 2 3
Sample Output 1
30 20
- Initially, A is empty.
- The first query appends 20 to the end of A, making A=(20).
- The second query appends 30 to the end of A, making A=(20,30).
- The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
- The fourth query appends 40 to the end of A, making A=(20,30,40).
- The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個のボールが左右一列に並んでいます。初め、左から i \, (1 \leq i \leq N) 番目のボールには整数 i が書かれています。
高橋君は Q 回の操作を行いました。 i \, (1 \leq i \leq Q) 回目に行われた操作は次のようなものです。
- 整数 x_i が書かれているボールをその右隣のボールと入れ替える。ただし、整数 x_i が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。
操作後において左から i \, (1 \leq i \leq N) 番目のボールに書かれている整数を a_i とします。 a_1,\ldots,a_N を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q x_1 \vdots x_Q
出力
a_1,\ldots,a_N を空白区切りで出力せよ。
入力例 1
5 5 1 2 3 4 5
出力例 1
1 2 3 5 4
操作は以下のように行われます。
- 1 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 2,1,3,4,5 となる。
- 2 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
- 3 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,4,3,5 となる。
- 4 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
- 5 と書かれたボールは右端にあるので左隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,5,4 となる。
入力例 2
7 7 7 7 7 7 7 7 7
出力例 2
1 2 3 4 5 7 6
入力例 3
10 6 1 5 2 9 6 6
出力例 3
1 2 3 4 5 7 6 8 10 9
Score : 300 points
Problem Statement
N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.
Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.
- Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.
Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q x_1 \vdots x_Q
Output
Print a_1,\ldots,a_N, with spaces in between.
Sample Input 1
5 5 1 2 3 4 5
Sample Output 1
1 2 3 5 4
The operations are performed as follows.
- Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
- Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
- Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
- Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
- Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.
Sample Input 2
7 7 7 7 7 7 7 7 7
Sample Output 2
1 2 3 4 5 7 6
Sample Input 3
10 6 1 5 2 9 6 6
Sample Output 3
1 2 3 4 5 7 6 8 10 9