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 の数列 A = (A_1, A_2, \cdots , A_N) が与えられます。
その後に 1 以上 N 以下の整数 X が与えられます。
A_X の値を出力してください。
制約
- 1 \le X \le N \le 100
- 1 \le A_i \le 100
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N X
出力
A_X の値を出力せよ。
入力例 1
5 1 2 3 4 5 3
出力例 1
3
(A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5) です。 A_3 = 3 のため 3 と出力してください。
入力例 2
10 6 6 9 6 10 5 7 2 8 2 4
出力例 2
6
入力例 3
10 4 4 4 3 4 2 1 1 2 1 10
出力例 3
1
Score : 100 points
Problem Statement
You are given a sequence A = (A_1, A_2, \cdots , A_N) of length N.
After that, an integer X between 1 and N, inclusive, is given.
Output the value of A_X.
Constraints
- 1 \le X \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 X
Output
Output the value of A_X.
Sample Input 1
5 1 2 3 4 5 3
Sample Output 1
3
We have (A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5). Since A_3 = 3, output 3.
Sample Input 2
10 6 6 9 6 10 5 7 2 8 2 4
Sample Output 2
6
Sample Input 3
10 4 4 4 3 4 2 1 1 2 1 10
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の人がおり、i 人目 (1\leq i\leq N) の現在の髪の長さは L_i です。
すべての人は 1 日経つごとに髪の長さが 1 ずつ増えます。
髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力してください。
ただし、現在の時点ですでに髪の長さが T 以上の人が P 人以上にいる場合は 0 を出力してください。
制約
- 1\leq N\leq 100
- 1\leq L_i\leq 100
- 1\leq T\leq 100
- 1\leq P\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N T P L_1 L_2 \ldots L_N
出力
髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力せよ。 ただし、現在の時点ですでに条件をみたしている場合は 0 を出力せよ。
入力例 1
5 10 3 3 11 1 6 2
出力例 1
7
5 人の人がおり、現在の時点で髪の長さはそれぞれ 3,11,1,6,2 であるため、髪の長さが 10 以上の人は 1 人です。
現在から 7 日後にはそれぞれの人の髪の長さは順に 10,18,8,13,9 となり、髪の長さが 10 以上の人は 3 人となります。
現在から 6 日後の時点では髪の長さが 10 以上の人は 2 人であるため条件をみたしておらず、よって 7 を出力します。
入力例 2
2 5 2 10 10
出力例 2
0
現在の時点ですでに髪の長さが 5 以上の人が 2 人いるため条件をみたしており、0 を出力します。
入力例 3
3 10 1 1 2 3
出力例 3
7
Score : 200 points
Problem Statement
There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.
Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.
Constraints
- 1 \leq N \leq 100
- 1 \leq L_i \leq 100
- 1 \leq T \leq 100
- 1 \leq P \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T P L_1 L_2 \ldots L_N
Output
Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time. If this condition is already satisfied now, print 0.
Sample Input 1
5 10 3 3 11 1 6 2
Sample Output 1
7
There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.
After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.
Sample Input 2
2 5 2 10 10
Sample Output 2
0
Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.
Sample Input 3
3 10 1 1 2 3
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
整数 N が与えられます。
非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。
非負整数の組の辞書順とは？
非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。
- x < x' である
- x=x' かつ y< y' である
- x=x' かつ y=y' かつ z< z' である
制約
- 0 \leq N \leq 21
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。
入力例 1
3
出力例 1
0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 3 0 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 2 0 2 0 0 2 0 1 2 1 0 3 0 0
入力例 2
4
出力例 2
0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 1 0 0 1 1 0 1 2 0 1 3 0 2 0 0 2 1 0 2 2 0 3 0 0 3 1 0 4 0 1 0 0 1 0 1 1 0 2 1 0 3 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 3 0 2 0 0 2 0 1 2 0 2 2 1 0 2 1 1 2 2 0 3 0 0 3 0 1 3 1 0 4 0 0
Score : 150 points
Problem Statement
You are given an integer N.
Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.
What is lexicographical order for non-negative integer triples?
A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:
- x < x';
- x=x' and y< y';
- x=x' and y=y' and z< z'.
Constraints
- 0 \leq N \leq 21
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.
Sample Input 1
3
Sample Output 1
0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 3 0 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 2 0 2 0 0 2 0 1 2 1 0 3 0 0
Sample Input 2
4
Sample Output 2
0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 1 0 0 1 1 0 1 2 0 1 3 0 2 0 0 2 1 0 2 2 0 3 0 0 3 1 0 4 0 1 0 0 1 0 1 1 0 2 1 0 3 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 3 0 2 0 0 2 0 1 2 0 2 2 1 0 2 1 1 2 2 0 3 0 0 3 0 1 3 1 0 4 0 0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N + 1 個の部屋が一列に並んでおり、順に 0, 1, \ldots, N の番号が付けられています。
部屋の間には N 個のドアがあり、1, 2, \ldots, N の番号が付けられています。ドア i は部屋 i - 1 と部屋 i の間にあります。
各ドアについて鍵の状態を表す値 L_i が与えられ、L_i = 0 のときドア i の鍵は開いており、L_i = 1 のときドア i の鍵は閉まっています。
高橋君ははじめ部屋 R におり、ドア i の鍵が開いているときに限り、部屋 i - 1 と部屋 i の間を移動することができます。また、高橋君は部屋 i - 1 または部屋 i にいるときに限り、ドア i の鍵に対して 開閉操作 を行うことができます。ドア i の鍵に対して開閉操作を行ったとき、その鍵が開いているときは閉まり、閉まっているときは開きます。
すべてのドアの鍵が閉まった状態にするために行う鍵の開閉操作の回数として考えられる最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 0 \leq R \leq N
- L_i \in \lbrace 0, 1 \rbrace
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N R L_1 L_2 \ldots L_N
出力
答えを出力せよ。
入力例 1
6 3 1 0 0 1 0 0
出力例 1
6
高橋君は以下のように行動することで 6 回の開閉操作ですべてのドアの鍵が閉まった状態にすることができます。
- 部屋 2 に移動する。
- ドア 2 に対して開閉操作を行い、ドア 2 の鍵を閉める。
- 部屋 3 に移動する。
- ドア 4 に対して開閉操作を行い、ドア 4 の鍵を開ける。
- ドア 3 に対して開閉操作を行い、ドア 3 の鍵を閉める。
- 部屋 4 に移動する。
- ドア 4 に対して開閉操作を行い、ドア 4 の鍵を閉める。
- 部屋 5 に移動する。
- ドア 5 に対して開閉操作を行い、ドア 5 の鍵を閉める。
- ドア 6 に対して開閉操作を行い、ドア 6 の鍵を閉める。
入力例 2
2 1 0 0
出力例 2
2
入力例 3
8 2 0 1 0 0 1 0 1 1
出力例 3
8
Score : 300 points
Problem Statement
There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.
Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.
For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.
Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.
Find the minimum number of switching operations needed to make all doors locked.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq R \leq N
- L_i \in \lbrace 0, 1 \rbrace
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N R L_1 L_2 \ldots L_N
Output
Output the answer.
Sample Input 1
6 3 1 0 0 1 0 0
Sample Output 1
6
Takahashi can make all doors locked with six switching operations by acting as follows:
- Move to room 2.
- Perform a switching operation on door 2 to lock door 2.
- Move to room 3.
- Perform a switching operation on door 4 to unlock door 4.
- Perform a switching operation on door 3 to lock door 3.
- Move to room 4.
- Perform a switching operation on door 4 to lock door 4.
- Move to room 5.
- Perform a switching operation on door 5 to lock door 5.
- Perform a switching operation on door 6 to lock door 6.
Sample Input 2
2 1 0 0
Sample Output 2
2
Sample Input 3
8 2 0 1 0 0 1 0 1 1
Sample Output 3
8