Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A の中に同じ要素が 3 つ以上連続する箇所が存在するか判定してください。
より厳密には、 1 以上 N-2 以下の整数 i であって A_i=A_{i+1}=A_{i+2} を満たすものが存在するか判定してください。
制約
- 3\le N\le 100
- 1\le A_i\le 100
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の中に同じ要素が 3 つ以上連続する箇所が存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
5 1 4 4 4 2
出力例 1
Yes
A=(1,4,4,4,2) です。 4 が 3 つ連続している箇所が存在するので、 Yes を出力してください。
入力例 2
6 2 4 4 2 2 4
出力例 2
No
A=(2,4,4,2,2,4) です。同じ要素が 3 つ以上連続している箇所は存在しないので、 No を出力してください。
入力例 3
8 1 4 2 5 7 7 7 2
出力例 3
Yes
入力例 4
10 1 2 3 4 5 6 7 8 9 10
出力例 4
No
入力例 5
13 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 5
Yes
Score : 100 points
Problem Statement
You are given an integer sequence of length N: A = (A_1,A_2,\ldots,A_N).
Determine whether there is a place in A where the same element appears three or more times in a row.
More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.
Constraints
- 3 \le N \le 100
- 1 \le A_i \le 100
- 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
If there is a place in A where the same element appears three or more times in a row, print Yes. Otherwise, print No.
Sample Input 1
5 1 4 4 4 2
Sample Output 1
Yes
We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.
Sample Input 2
6 2 4 4 2 2 4
Sample Output 2
No
We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.
Sample Input 3
8 1 4 2 5 7 7 7 2
Sample Output 3
Yes
Sample Input 4
10 1 2 3 4 5 6 7 8 9 10
Sample Output 4
No
Sample Input 5
13 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 5
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋くんは、N 個の品物と 1 つのカバンを持っています。
i 番目 (1\le i\le N) の品物の大きさは A _ i で、カバンの大きさは M です。
カバンに入れようとしている品物の大きさの合計が M 以下のとき、かつそのときに限り、それらの品物をすべて同時にカバンに入れることができます。
高橋くんが N 個の品物すべてを同時にカバンに入れることができるなら Yes 、そうでなければ No と出力してください。
制約
- 1\le N\le100
- 1\le M\le10000
- 1\le A _ i\le100\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A _ 1 A _ 2 \ldots A _ N
出力
高橋くんがすべての品物を同時にカバンに入れられるなら Yes を、そうでなければ No を出力せよ。
入力例 1
5 15 3 1 4 1 5
出力例 1
Yes
5 つの品物の大きさの合計は 3+1+4+1+5=14 です。
これは、カバンの大きさ 15 以下なので、高橋くんはすべての品物を同時にカバンに入れることができます。
なので、Yes を出力してください。
入力例 2
5 5 3 1 4 1 5
出力例 2
No
5 つの品物の大きさの合計は 14 で、カバンの大きさ 5 より大きいため、高橋くんはすべての品物を同時にカバンに入れることができません。
なので、No を出力してください。
入力例 3
1 10000 100
出力例 3
Yes
Score : 100 points
Problem Statement
Takahashi has N items and one bag.
The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.
If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.
If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.
Constraints
- 1\le N\le100
- 1\le M\le10000
- 1\le A_i\le100\ (1\le i\le N)
- All input values are integers.
Input
The input is given from standard input in the following format:
N M A_1 A_2 \ldots A_N
Output
If Takahashi can put all items in the bag simultaneously, print Yes; otherwise, print No.
Sample Input 1
5 15 3 1 4 1 5
Sample Output 1
Yes
The total size of the 5 items is 3+1+4+1+5=14.
Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously.
Thus, print Yes.
Sample Input 2
5 5 3 1 4 1 5
Sample Output 2
No
The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously.
Thus, print No.
Sample Input 3
1 10000 100
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
正整数 N が与えられるので、 2^k \le N となる最大の整数 k を求めてください。
制約
- N は 1 \le N \le 10^{18} を満たす整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
6
出力例 1
2
- k=2 は 2^2=4 \le 6 を満たします。
- k \ge 3 である全ての整数 k について 2^k > 6 となります。
以上より、答えは k=2 となります。
入力例 2
1
出力例 2
0
2^0=1 であることに注意してください。
入力例 3
1000000000000000000
出力例 3
59
入力が 32 bit 整数に収まらない場合があります。
Score : 200 points
Problem Statement
Given a positive integer N, find the maximum integer k such that 2^k \le N.
Constraints
- N is an integer satisfying 1 \le N \le 10^{18}.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
6
Sample Output 1
2
- k=2 satisfies 2^2=4 \le 6.
- For every integer k such that k \ge 3, 2^k > 6 holds.
Therefore, the answer is k=2.
Sample Input 2
1
Sample Output 2
0
Note that 2^0=1.
Sample Input 3
1000000000000000000
Sample Output 3
59
The input value may not fit into a 32-bit integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1\leq l\leq r\leq N をみたす整数の組 (l,r) であって、
次の条件をみたすものの個数を求めてください。
l\leq i\leq r をみたす任意の整数 i について、A_i は A_l+A_{l+1}+\cdots+A_r の約数でない。
制約
- 1 \leq N \leq 50
- 1 \leq A_i \leq 1000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 8 6 10 5 7
出力例 1
6
A=(8,6,10,5,7) です。
例えば、(l,r)=(1,2) は、A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14 であり、A_1=8, A_2=6 はどちらも 14 の約数でないため、条件をみたします。
一方で、(l,r)=(1,3) は、A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24 であり、A_1=8 が 24 の約数であるため、条件をみたしません。
条件をみたす組は (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5) の 6 つであるため、6 を出力します。
入力例 2
3 1 1 1
出力例 2
0
Score : 200 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:
For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.
Constraints
- 1 \leq N \leq 50
- 1 \leq A_i \leq 1000
- 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
Output the answer.
Sample Input 1
5 8 6 10 5 7
Sample Output 1
6
We have A=(8,6,10,5,7).
For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.
The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.
Sample Input 2
3 1 1 1
Sample Output 2
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ある OS のバージョンは N 個あり、古い順に 1,2,\dots,N の番号がついています。
PC が N 台あり、初めは i 番目の PC の OS のバージョンは i です。
Q 回の操作を順に行ってください。そのうち i 回目は次の通りです。
- 現時点での OS のバージョンが X_i かそれ以前の PC 全てを、バージョンを Y_i(>X_i) にアップグレードする。その後、この操作でアップグレードを行った PC の台数を出力する。
i<Q について、 i 回目の操作でのアップグレードが行われた状態で i+1 回目の操作に進むことに注意してください。
制約
- 入力は全て整数
- 2 \le N \le 10^6
- 1 \le Q \le 2 \times 10^5
- 1 \le X_i < Y_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
出力
Q 行出力せよ。
そのうち i 行目には、 i 回目の操作でアップグレードを行った PC の台数を出力せよ。
入力例 1
8 5 2 6 3 5 1 7 5 7 7 8
出力例 1
2 1 0 3 7
この入力には 5 回の操作が含まれます。
- はじめ、 8 台の PC のバージョンは 1,2,3,4,5,6,7,8 です。
- 1 回目の操作で、バージョンが 2 かそれ以前のバージョンの PC をバージョン 6 にアップグレードします。
- この操作によって 2 台の PC がアップグレードされ、各 PC のバージョンは 6,6,3,4,5,6,7,8 となります。
- 2 回目の操作で、バージョンが 3 かそれ以前のバージョンの PC をバージョン 5 にアップグレードします。
- この操作によって 1 台の PC がアップグレードされ、各 PC のバージョンは 6,6,5,4,5,6,7,8 となります。
- 3 回目の操作で、バージョンが 1 かそれ以前のバージョンの PC をバージョン 7 にアップグレードします。
- この操作によって 0 台の PC がアップグレードされ、各 PC のバージョンは 6,6,5,4,5,6,7,8 となります。
- 4 回目の操作で、バージョンが 5 かそれ以前のバージョンの PC をバージョン 7 にアップグレードします。
- この操作によって 3 台の PC がアップグレードされ、各 PC のバージョンは 6,6,7,7,7,6,7,8 となります。
- 5 回目の操作で、バージョンが 7 かそれ以前のバージョンの PC をバージョン 8 にアップグレードします。
- この操作によって 7 台の PC がアップグレードされ、各 PC のバージョンは 8,8,8,8,8,8,8,8 となります。
Score : 300 points
Problem Statement
There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.
Perform Q operations in order. The i-th operation is as follows:
- Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.
Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.
Constraints
- All input values are integers.
- 2 \le N \le 10^6
- 1 \le Q \le 2 \times 10^5
- 1 \le X_i < Y_i \le N
Input
The input is given from Standard Input in the following format:
N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
Output
Output Q lines.
The i-th line should contain the number of PCs upgraded in the i-th operation.
Sample Input 1
8 5 2 6 3 5 1 7 5 7 7 8
Sample Output 1
2 1 0 3 7
This input contains five operations.
- Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
- In the first operation, PCs with version 2 or earlier are upgraded to version 6.
- This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
- In the second operation, PCs with version 3 or earlier are upgraded to version 5.
- This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
- In the third operation, PCs with version 1 or earlier are upgraded to version 7.
- This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
- In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
- This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
- In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
- This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.