Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の整数列 A と整数 K,X が与えられます。
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を出力してください。
制約
- 入力は全て整数
- 1 \le K \le N \le 100
- 1 \le A_i,X \le 100
入力
入力は以下の形式で標準入力から与えられる。
N K X A_1 A_2 \dots A_N
出力
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を、以下の形式で出力せよ。
B_1 B_2 \dots B_{N+1}
入力例 1
4 3 7 2 3 5 11
出力例 1
2 3 5 7 11
K=3, X=7, A=(2,3,5,11) のとき、 B=(2,3,5,7,11) です。
入力例 2
1 1 100 100
出力例 2
100 100
入力例 3
8 8 3 9 9 8 2 4 4 3 5
出力例 3
9 9 8 2 4 4 3 5 3
Score : 100 points
Problem Statement
You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.
Constraints
- All input values are integers.
- 1 \le K \le N \le 100
- 1 \le A_i, X \le 100
Input
The input is given from Standard Input in the following format:
N K X A_1 A_2 \dots A_N
Output
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A, in the following format:
B_1 B_2 \dots B_{N+1}
Sample Input 1
4 3 7 2 3 5 11
Sample Output 1
2 3 5 7 11
For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).
Sample Input 2
1 1 100 100
Sample Output 2
100 100
Sample Input 3
8 8 3 9 9 8 2 4 4 3 5
Sample Output 3
9 9 8 2 4 4 3 5 3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
不思議なボタンがあります。 このボタンを押すと飴を 1 つもらえますが、前回飴をもらってからの経過時間が C 秒未満である場合はもらえません。
高橋君はこのボタンを N 回押してみることにしました。 i 回目にボタンを押すのは今から T_i 秒後です。
高橋君は何個の飴をもらうことができますか？
制約
- 1\leq N \leq 100
- 1\leq C\leq 1000
- 0\leq T_1 < T_2 < \dots < T_N \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C T_1 T_2 \dots T_N
出力
高橋君がもらうことのできる飴の個数を出力せよ。
入力例 1
6 5 1 3 7 8 10 12
出力例 1
3
高橋君はボタンを 6 回押します。
- 1 回目（今から 1 秒後）：初めてボタンを押すときは必ず飴を 1 つもらえます。
- 2 回目（今から 3 秒後）：前回飴をもらってからの経過時間が 3-1=2<C 秒なので、飴はもらえません。
- 3 回目（今から 7 秒後）：前回飴をもらってからの経過時間が 7-1=6\geq C 秒なので、飴を 1 つもらえます。
- 4 回目（今から 8 秒後）：前回飴をもらってからの経過時間が 8-7=1<C 秒なので、飴はもらえません。
- 5 回目（今から 10 秒後）：前回飴をもらってからの経過時間が 10-7=3<C 秒なので、飴はもらえません。
- 6 回目（今から 12 秒後）：前回飴をもらってからの経過時間が 12-7=5\geq C 秒なので、飴を 1 つもらえます。
よって、高橋君は飴を 3 個もらうことができます。
入力例 2
3 2 0 2 4
出力例 2
3
入力例 3
10 3 0 3 4 6 9 12 15 17 19 20
出力例 3
7
Score : 150 points
Problem Statement
There is a mysterious button. When you press this button, you receive one candy, unless less than C seconds have elapsed since you last received a candy.
Takahashi decided to press this button N times. He will press the button for the i-th time T_i seconds from now.
How many candies will he receive?
Constraints
- 1 \leq N \leq 100
- 1 \leq C \leq 1000
- 0 \leq T_1 < T_2 < \dots < T_N \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C T_1 T_2 \dots T_N
Output
Print the number of candies that Takahashi will receive.
Sample Input 1
6 5 1 3 7 8 10 12
Sample Output 1
3
Takahashi will press the button six times.
- 1st press (1 second from now): You always receive a candy when pressing the button for the first time.
- 2nd press (3 seconds from now): 3 - 1 = 2 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
- 3rd press (7 seconds from now): 7 - 1 = 6 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
- 4th press (8 seconds from now): 8 - 7 = 1 < C second has elapsed since he last received a candy, so he does not receive a candy.
- 5th press (10 seconds from now): 10 - 7 = 3 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
- 6th press (12 seconds from now): 12 - 7 = 5 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
Therefore, he receives three candies.
Sample Input 2
3 2 0 2 4
Sample Output 2
3
Sample Input 3
10 3 0 3 4 6 9 12 15 17 19 20
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字のみからなる 2 つの文字列 S, T が与えられます。 S が T の接頭辞かどうかを判定してください。
接頭辞とは
長さ N の文字列 T_1T_2\ldots T_N の接頭辞とは、 0 \leq i \leq N を満たすある整数 i によって、T の先頭 i 文字目までの文字列 T_1T_2\ldots T_i として表される文字列です。例えば、T = abc のとき、T の接頭辞は、空文字列、a 、ab 、abc の 4 つです。制約
- S と T はそれぞれ英小文字のみからなる長さが 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S が T の接頭辞である場合は Yes を、そうでない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
atco atcoder
出力例 1
Yes
atco は atcoder の接頭辞です。よって、Yes を出力します。
入力例 2
code atcoder
出力例 2
No
code は atcoder の接頭辞ではありません。よって、No を出力します。
入力例 3
abc abc
出力例 3
Yes
文字列全体もその文字列の接頭辞であることに注意してください。
入力例 4
aaaa aa
出力例 4
No
Score : 200 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.
What is a prefix?
A prefix of a string T_1T_2\ldots T_N of length N is a string expressed as the first i characters of T, T_1T_2\ldots T_i, where i is an integer such that 0 \leq i \leq N. For example, when T = abc, there are four prefixes of T: an empty string, a, ab, and abc.Constraints
- S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T
Output
Print Yes if S is a prefix of T; print No otherwise.
Note that the judge is case-sensitive.
Sample Input 1
atco atcoder
Sample Output 1
Yes
atco is a prefix of atcoder. Thus, Yes should be printed.
Sample Input 2
code atcoder
Sample Output 2
No
code is not a prefix of atcoder. Thus, No should be printed.
Sample Input 3
abc abc
Sample Output 3
Yes
Note that a string is also a prefix of itself.
Sample Input 4
aaaa aa
Sample Output 4
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字と英大文字からなる文字列 S が与えられます。S の長さは奇数です。
S に含まれる大文字の個数が小文字の個数よりも多ければ、S に含まれる全ての小文字を大文字に変換してください。
そうでない場合は、S に含まれる全ての大文字を小文字に変換してください。
制約
- S は英小文字および英大文字からなる文字列
- S の長さは 1 以上 99 以下の奇数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
問題文の指示に従って文字を変換した後の S を出力せよ。
入力例 1
AtCoder
出力例 1
atcoder
AtCoder に含まれる小文字の個数は 5 個、大文字の個数は 2 個です。よって AtCoder に含まれる全ての大文字を小文字に変換した atcoder が答えとなります。
入力例 2
SunTORY
出力例 2
SUNTORY
SunTORY に含まれる小文字の個数は 2 個、大文字の個数は 5 個です。よって SunTORY に含まれる全ての小文字を大文字に変換した SUNTORY が答えとなります。
入力例 3
a
出力例 3
a
Score : 200 points
Problem Statement
You are given a string S consisting of lowercase and uppercase English letters. The length of S is odd.
If the number of uppercase letters in S is greater than the number of lowercase letters, convert all lowercase letters in S to uppercase.
Otherwise, convert all uppercase letters in S to lowercase.
Constraints
- S is a string consisting of lowercase and uppercase English letters.
- The length of S is an odd number between 1 and 99, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the string S after converting the letters according to the problem statement.
Sample Input 1
AtCoder
Sample Output 1
atcoder
The string AtCoder contains five lowercase letters and two uppercase letters. Thus, convert all uppercase letters in AtCoder to lowercase, which results in atcoder.
Sample Input 2
SunTORY
Sample Output 2
SUNTORY
The string SunTORY contains two lowercase letters and five uppercase letters. Thus, convert all lowercase letters in SunTORY to uppercase, which results in SUNTORY.
Sample Input 3
a
Sample Output 3
a
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
空の列と、N 個のボールがあります。i 個目 (1\leq i\leq N) のボールの大きさは 2^{A_i} です。
これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。
- 列にあるボールが 1 つ以下ならば操作を終了する。
- 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
- 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。
N 回の操作の後で、列にあるボールの数を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 回の操作の後で、列にあるボールの数を出力せよ。
入力例 1
7 2 1 1 3 5 3 3
出力例 1
3
操作は次のように行われます。
- 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^2 です。
- 2 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^2, 2^1 です。
- 3 回目の操作の後、列にあるボールは 1 つで、大きさは 2^3 です。これは次のようにして得ることができます。
- 3 回目の操作において 3 個目のボールを付け加えたとき、列にあるボールの大きさは順に 2^2,2^1,2^1 となります。
- 右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^1+2^1=2^2 のボールが追加されます。このとき、列にあるボールの大きさは 2^2, 2^2 となります。
- さらに、再び右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^2+2^2=2^3 のボールが追加され、列にあるボールの大きさは 2^3 となります。
- 4 回目の操作の後、列にあるボールは 1 つで、大きさは 2^4 です。
- 5 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^4, 2^5 です。
- 6 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^3 です。
- 7 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^4 です。
よって、最後に列にあるボールの数である 3 を出力します。
入力例 2
5 0 0 0 1 2
出力例 2
4
操作は次のように行われます。
- 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^0 です。
- 2 回目の操作の後、列にあるボールは 1 つで、大きさは 2^1 です。
- 3 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^1, 2^0 です。
- 4 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^1, 2^0, 2^1 です。
- 5 回目の操作の後、列にあるボールは 4 つで、大きさは順に 2^1, 2^0, 2^1, 2^2 です。
よって、最後に列にあるボールの数である 4 を出力します。
Score: 250 points
Problem Statement
You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.
You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:
- If the sequence has one or fewer balls, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.
Determine the number of balls remaining in the sequence after the N operations.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \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 \ldots A_N
Output
Print the number of balls in the sequence after the N operations.
Sample Input 1
7 2 1 1 3 5 3 3
Sample Output 1
3
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size 2^2.
- After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
- After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
- When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
- The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
- Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
- After the fourth operation, the sequence has one ball, of size 2^4.
- After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
- After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
- After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.
Therefore, you should print 3, the final number of balls in the sequence.
Sample Input 2
5 0 0 0 1 2
Sample Output 2
4
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size 2^0.
- After the second operation, the sequence has one ball, of size 2^1.
- After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
- After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
- After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.
Therefore, you should print 4, the final number of balls in the sequence.