Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。
左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。
制約
- 1\leq N\leq 100
- 1\leq H_i \leq 100
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。
存在する場合、その内最も左のビルは左から何番目か出力せよ。
入力例 1
4 3 2 5 2
出力例 1
3
左から 1 番目のビルより高いビルは、左から 3 番目のビルです。
入力例 2
3 4 3 2
出力例 2
-1
左から 1 番目のビルより高いビルは存在しません。
入力例 3
7 10 5 10 2 10 13 15
出力例 3
6
左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。
Score: 100 points
Problem Statement
There are N buildings aligned in a row. The i-th building from the left has a height of H_i.
Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.
Constraints
- 1 \leq N \leq 100
- 1 \leq H_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
If no building is taller than the first one from the left, print -1.
If such a building exists, print the position (index) of the leftmost such building from the left.
Sample Input 1
4 3 2 5 2
Sample Output 1
3
The building taller than the first one from the left is the third one from the left.
Sample Input 2
3 4 3 2
Sample Output 2
-1
No building is taller than the first one from the left.
Sample Input 3
7 10 5 10 2 10 13 15
Sample Output 3
6
The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 以下の非負整数を大きい方から順にすべて出力してください。
制約
- 1 \leq N \leq 100
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 以下の非負整数が X 個存在するとき、X 行出力せよ。
i=1,2,\ldots,X に対し、i 行目には N 以下の非負整数のうち大きい方から i 番目のものを出力せよ。
入力例 1
3
出力例 1
3 2 1 0
3 以下の非負整数は 0,1,2,3 の 4 個です。
1 行目に 3 を、2 行目に 2 を、3 行目に 1 を、4 行目に 0 を出力することでこれらを大きい方から順に出力したことになります。
入力例 2
22
出力例 2
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Score : 100 points
Problem Statement
Print all non-negative integers less than or equal to N in descending order.
Constraints
- 1 \leq N \leq 100
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print X lines, where X is the number of non-negative integers less than or equal to N.
For each i=1, 2, \ldots, X, the i-th line should contain the i-th greatest non-negative integer less than or equal to N.
Sample Input 1
3
Sample Output 1
3 2 1 0
We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.
Sample Input 2
22
Sample Output 2
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
ボウリングのピンは 1 から 10 の番号が付けられており、上から見ると下図のように配置されます。
この図の二つの点線に挟まれた部分を列と呼ぶことにします。
例えば、ピン 1, 5 とピン 3, 9 はそれぞれ同じ列に存在します。
いくつかのピンが倒れた状態のうち、特殊なものはスプリットと呼ばれます。
ピンの配置がスプリットであるとは、以下の条件が全て成り立つことを言います。
- ピン 1 が倒れている。
- ある二つの異なる列であって、次の条件を満たすものが存在する。
- それぞれの列には、立っているピンが 1 本以上存在する。
- それらの列の間に、ピンが全て倒れている列が存在する。
具体例は入出力例を参考にしてください。
さて、あるピンの配置が長さ 10 の文字列 S として与えられます。
i = 1, \dots, 10 について、ピン i が倒れているとき S の i 文字目は 0 であり、ピン i が立っているとき S の i 文字目は 1 です。
S で表されるピンの配置がスプリットかどうか判定してください。
制約
- S は
0と1からなる長さ 10 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S で表されるピンの配置がスプリットなら Yes を、そうでないなら No を出力せよ。
入力例 1
0101110101
出力例 1
Yes
倒れているピンを灰色で、立っているピンを白色で示すと下図のようになります。
ピン 5 が立っている列とピン 6 が立っている列の間にはピン 3, 9 が置かれている列が存在しますが、ピン 3, 9 はいずれも倒れているので、この配置はスプリットです。
入力例 2
0100101001
出力例 2
Yes
入力例 3
0000100110
出力例 3
No
この配置はスプリットではありません。
入力例 4
1101110101
出力例 4
No
ピン 1 が倒れていないので、スプリットではありません。
Score : 200 points
Problem Statement
Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:
Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.
When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:
- Pin 1 is knocked down.
- There are two different columns that satisfy both of the following conditions:
- Each of the columns has one or more standing pins.
- There exists a column between these columns such that all pins in the column are knocked down.
See also Sample Inputs and Outputs for examples.
Now, you are given a placement of the pins as a string S of length 10.
For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.
Constraints
- S is a string of length 10 consisting of
0and1.
Input
Input is given from Standard Input in the following format:
S
Output
If the placement of the pins represented by S is a split, print Yes; otherwise, print No.
Sample Input 1
0101110101
Sample Output 1
Yes
In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:
Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.
Sample Input 2
0100101001
Sample Output 2
Yes
Sample Input 3
0000100110
Sample Output 3
No
This placement is not a split.
Sample Input 4
1101110101
Sample Output 4
No
This is not a split because Pin 1 is not knocked down.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。
- \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。
W 以下の正整数のうち、良い整数は何個ありますか？
制約
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
2 10 1 3
出力例 1
3
おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。
入力例 2
2 1 2 3
出力例 2
0
W 以下の良い整数は存在しません。
入力例 3
4 12 3 3 3 3
出力例 3
3
良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。
入力例 4
7 251 202 20 5 1 4 2 100
出力例 4
48
Score : 200 points
Problem Statement
There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:
- We can choose at most 3 different weights so that they have a total mass of n.
How many positive integers less than or equal to W are good integers?
Constraints
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to W.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
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.