実行時間制限: 2 sec / メモリ制限: 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.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
0 と 1 の 2 種類の文字からなる文字列 s が与えられます。
s に含まれる 0 を 1 に、1 を 0 に置き換えた文字列を出力してください。
制約
- s の長さは 1 以上 10 以下
- s は
0と1の 2 種類の文字からなる
入力
入力は以下の形式で標準入力から与えられる。
s
出力
答えを 1 行で出力せよ。
入力例 1
01
出力例 1
10
s の 1 文字目は 1 なので、1 文字目に出力すべき文字は 0 です。
s の 2 文字目は 0 なので、2 文字目に出力すべき文字は 1 です。
入力例 2
1011
出力例 2
0100
入力例 3
100100001
出力例 3
011011110
Score : 100 points
Problem Statement
You are given a string s consisting of two kinds of characters, 0 and 1.
Print the string obtained by replacing 0 with 1 and 1 with 0 in s.
Constraints
- The length of s is between 1 and 10, inclusive.
- s consists of two kinds of characters,
0and1.
Input
The input is given from Standard Input in the following format:
s
Output
Print the answer in a single line.
Sample Input 1
01
Sample Output 1
10
The 1-st character of s is 1, so the 1-st character to print is 0.
The 2-nd character of s is 0, so the 2-nd character to print is 1.
Sample Input 2
1011
Sample Output 2
0100
Sample Input 3
100100001
Sample Output 3
011011110
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は容量が G ml のグラスと、容量が M ml のマグカップを 1 つずつ持っています。
ここで、G,M は G<M をみたします。
最初、グラスとマグカップはいずれも空です。
以下の操作を K 回繰り返した後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか求めてください。
- グラスが水で満たされているとき、すなわちグラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。
- そうでなく、マグカップが空であるとき、マグカップを水で満たす。
- 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。
制約
- 1\leq K\leq 100
- 1\leq G<M\leq 1000
- G,M,K は整数
入力
入力は以下の形式で標準入力から与えられる。
K G M
出力
操作を K 回行った後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか、この順に空白区切りで出力せよ。
入力例 1
5 300 500
出力例 1
200 500
操作は次の順で行われます。最初、グラスとマグカップはいずれも空です。
- マグカップを水で満たす。グラスには 0 ml, マグカップには 500 ml 入った状態になる。
- グラスが満たされるまでマグカップからグラスに水を移す。グラスには 300 ml, マグカップには 200 ml 入った状態になる。
- グラスの水をすべて捨てる。グラスには 0 ml, マグカップには 200 ml 入った状態になる。
- マグカップが空になるまでマグカップからグラスに水を移す。グラスには 200 ml, マグカップには 0 ml 入った状態になる。
- マグカップを水で満たす。グラスには 200 ml, マグカップには 500 ml 入った状態になる。
よって、5 回の操作の後でグラスには 200 ml, マグカップには 500 ml 入った状態になります。 ゆえに、200, 500 を空白区切りでこの順に出力します。
入力例 2
5 100 200
出力例 2
0 0
Score : 200 points
Problem Statement
AtCoder Inc. sells glasses and mugs.
Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.
Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.
- When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
- Otherwise, if the mug is empty, fill the mug with water.
- Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.
Constraints
- 1\leq K\leq 100
- 1\leq G<M\leq 1000
- G, M, and K are integers.
Input
The input is given from Standard Input in the following format:
K G M
Output
Print the amounts, in milliliters, of water in the glass and the mug, in this order, separated by a space, after performing the operation K times.
Sample Input 1
5 300 500
Sample Output 1
200 500
The operation will be performed as follows. Initially, both the glass and the mug are empty.
- Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
- Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
- Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
- Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
- Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.
Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.
Sample Input 2
5 100 200
Sample Output 2
0 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君はゲームの中で洞窟を探索しています。
洞窟は N 個の部屋が一列に並んだ構造であり、入り口から順に部屋 1,2,\ldots,N と番号がついています。
最初、高橋君は部屋 1 におり、持ち時間 は T です。
各 1 \leq i \leq N-1 について、持ち時間を A_i 消費することで、部屋 i から部屋 i+1 へ移動することができます。これ以外に部屋を移動する方法はありません。
また、持ち時間が 0 以下になるような移動は行うことができません。
洞窟内には M 個のボーナス部屋があります。i 番目のボーナス部屋は部屋 X_i であり、この部屋に到達すると持ち時間が Y_i 増加します。
高橋君は部屋 N にたどりつくことができますか?
制約
- 2 \leq N \leq 10^5
- 0 \leq M \leq N-2
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 < X_1 < \ldots < X_M < N
- 1 \leq Y_i \leq 10^9
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
出力
高橋君が部屋 N にたどりつくことができるなら Yes を、できないなら No を出力せよ。
入力例 1
4 1 10 5 7 5 2 10
出力例 1
Yes
- 高橋君は最初、部屋 1 にいて持ち時間は 10 です。
- 持ち時間を 5 消費して部屋 2 に移動します。持ち時間は 5 になります。その後、持ち時間が 10 増え 15 になります。
- 持ち時間を 7 消費して部屋 3 に移動します。持ち時間は 8 になります。
- 持ち時間を 5 消費して部屋 4 に移動します。持ち時間は 3 になります。
入力例 2
4 1 10 10 7 5 2 10
出力例 2
No
部屋 1 から部屋 2 へ移動することができません。
Score : 200 points
Problem Statement
Takahashi is exploring a cave in a video game.
The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.
Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms.
He cannot make a move that makes the time limit 0 or less.
There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.
Can Takahashi reach Room N?
Constraints
- 2 \leq N \leq 10^5
- 0 \leq M \leq N-2
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 < X_1 < \ldots < X_M < N
- 1 \leq Y_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
Output
If Takahashi can reach Room N, print Yes; otherwise, print No.
Sample Input 1
4 1 10 5 7 5 2 10
Sample Output 1
Yes
- Takahashi is initially in Room 1, and the time limit is 10.
- He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
- He consumes a time of 7 to move to Room 3. Now the time limit is 8.
- He consumes a time of 5 to move to Room 4. Now the time limit is 3.
Sample Input 2
4 1 10 10 7 5 2 10
Sample Output 2
No
He cannot move from Room 1 to Room 2.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は、レジ打ちの仕事をしています。
レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 11 個のボタンがあります。
レジの機械には、はじめ 0 が表示されています。
ボタン 00 を押すと、表示されている数が 100 倍されます。
それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。
高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
制約
- 1\leq S\leq 10^{100000}
- S は整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを 1 行で出力せよ。
入力例 1
40004
出力例 1
4
例えば、次のように操作することでボタンを 4 回押して 40004 を表示させることができます。 はじめ、レジには 0 が表示されています。
- ボタン
4を押す。レジに表示されている数は 4 となる。 - ボタン
00を押す。レジに表示されている数は 400 となる。 - ボタン
0を押す。レジに表示されている数は 4000 となる。 - ボタン
4を押す。レジに表示されている数は 40004 となる。
3 回までボタンを押すことでレジに 40004 を表示させることはできないので、出力すべき値は 4 です。
入力例 2
1355506027
出力例 2
10
入力例 3
10888869450418352160768000001
出力例 3
27
S は 64\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
Takahashi is a cashier.
There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
The cash register initially displays 0.
Whenever he types the key 00, the displayed number is multiplied by 100;
whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.
Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?
Constraints
- 1\leq S\leq 10^{100000}
- S is an integer.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer in a line.
Sample Input 1
40004
Sample Output 1
4
For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.
- Type the key
4. It now displays 4. - Type the key
00. It now displays 400. - Type the key
0. It now displays 4000. - Type the key
4. It now displays 40004.
He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.
Sample Input 2
1355506027
Sample Output 2
10
Sample Input 3
10888869450418352160768000001
Sample Output 3
27
Note that S may not fit into a 64-\operatorname{bit} integer type.