Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) と整数 X が与えられます。
X が A に含まれるか判定してください。
制約
- 入力は全て整数
- 1 \le N \le 100
- 1 \le A_i \le 100
- 1 \le X \le 100
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N X
出力
X が A に含まれるなら Yes 、含まれないなら No と出力せよ。
入力例 1
5 3 1 4 1 5 4
出力例 1
Yes
A=(3,1,4,1,5), X=4 であり、 X は A に含まれます。
入力例 2
4 100 100 100 100 100
出力例 2
Yes
X が複数回 A に含まれる場合もあります。
入力例 3
6 2 3 5 7 11 13 1
出力例 3
No
Score : 100 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N and an integer X.
Determine whether X is contained in A.
Constraints
- All input values are integers.
- 1 \le N \le 100
- 1 \le A_i \le 100
- 1 \le X \le 100
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N X
Output
If X is contained in A, print Yes; otherwise, print No.
Sample Input 1
5 3 1 4 1 5 4
Sample Output 1
Yes
We have A=(3,1,4,1,5) and X=4; X is contained in A.
Sample Input 2
4 100 100 100 100 100
Sample Output 2
Yes
X may be contained in A multiple times.
Sample Input 3
6 2 3 5 7 11 13 1
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる 2 文字以上の文字列 S が与えられます。
S の先頭の文字と末尾の文字が同じ文字かどうか判定してください。
制約
- S は英小文字からなる長さ 2 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の先頭の文字と末尾の文字が同じ文字ならば Yes を、異なる文字ならば No を出力せよ。
入力例 1
luminol
出力例 1
Yes
先頭の文字は l、末尾の文字は l で一致しています。したがって Yes を出力してください。
入力例 2
rule
出力例 2
No
先頭の文字は r、末尾の文字は e で一致していません。したがって No を出力してください。
Score : 100 points
Problem Statement
You are given a string S of length at least 2 consisting of lowercase English letters.
Determine whether the first character and the last character of S are the same.
Constraints
- S is a string of length between 2 and 10, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
If the first character and the last character of S are the same, output Yes; otherwise, output No.
Sample Input 1
luminol
Sample Output 1
Yes
The first character is l and the last character is l, which match. Thus, output Yes.
Sample Input 2
rule
Sample Output 2
No
The first character is r and the last character is e, which do not match. Thus, output No.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 種類の元素があり、元素には 1, 2, \ldots, N の番号が付けられています。
元素どうしは合成させることができ、元素 i と元素 j を合成すると i \geq j のとき元素 A_{i, j} に、i < j のとき元素 A_{j, i} に変化します。
元素 1 に対して元素 1, 2, \ldots, N をこの順に合成したとき、最終的に得られる元素を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq A_{i, j} \leq N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}
出力
最終的に得られる元素の番号を出力せよ。
入力例 1
4 3 2 4 3 1 2 2 1 2 4
出力例 1
2
-
元素 1 と元素 1 を合成すると、元素 3 が得られます。
-
元素 3 と元素 2 を合成すると、元素 1 が得られます。
-
元素 1 と元素 3 を合成すると、元素 3 が得られます。
-
元素 3 と元素 4 を合成すると、元素 2 が得られます。
したがって、出力するべき値は 2 です。
入力例 2
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
出力例 2
5
入力例 3
6 2 1 5 1 6 3 2 6 1 4 2 1 1 1 6 5 6 1 2 2 5
出力例 3
5
Score : 200 points
Problem Statement
There are N types of elements numbered 1, 2, \ldots, N.
Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.
Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_{i, j} \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}
Output
Print the number representing the final element obtained.
Sample Input 1
4 3 2 4 3 1 2 2 1 2 4
Sample Output 1
2
-
Combining element 1 with element 1 results in element 3.
-
Combining element 3 with element 2 results in element 1.
-
Combining element 1 with element 3 results in element 3.
-
Combining element 3 with element 4 results in element 2.
Therefore, the value to be printed is 2.
Sample Input 2
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
Sample Output 2
5
Sample Input 3
6 2 1 5 1 6 3 2 6 1 4 2 1 1 1 6 5 6 1 2 2 5
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋くんは、以下の方法で 10 個の文字列 S_1,S_2,\dots,S_{10} を生成しました。
- まず、 S_i (1 \le i \le 10)=
..........(.が 10 個並んだ文字列) とする。 - 次に、以下の条件を全て満たす 4 つの整数 A,B,C,D を選ぶ。
- 1 \le A \le B \le 10
- 1 \le C \le D \le 10
- その後、以下の条件を全て満たす全ての整数組 (i,j) について、 S_i の j 文字目を
#に書き換える。- A \le i \le B
- C \le j \le D
以上の方法で生成された S_1,S_2,\dots,S_{10} が与えられるので、高橋くんが選んだ整数 A,B,C,D を求めてください。
なお、制約より A,B,C,D は一意に定まる (答えはただひとつ存在する) ことが証明できます。
制約
- S_1,S_2,\dots,S_{10} は問題文中の方法で生成されうるそれぞれ長さ 10 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S_1
S_2
\vdots
S_{10}
出力
答えを以下の形式で出力せよ。
A B C D
入力例 1
.......... .......... .......... .......... ...######. ...######. ...######. ...######. .......... ..........
出力例 1
5 8 4 9
高橋くんが選んだ整数は A=5,B=8,C=4,D=9 です。
このように選ぶことにより、 S_5,S_6,S_7,S_8 の 4 文字目から 9 文字目が # であり他の文字が . である 10 個の長さ 10 の文字列 S_1,S_2,\dots,S_{10} が生成されます。
これは入力で与えられた 10 個の文字列と一致します。
入力例 2
.......... ..#....... .......... .......... .......... .......... .......... .......... .......... ..........
出力例 2
2 2 3 3
入力例 3
########## ########## ########## ########## ########## ########## ########## ########## ########## ##########
出力例 3
1 10 1 10
Score : 200 points
Problem Statement
Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.
- First, let S_i (1 \le i \le 10)=
..........(10.s in a row). - Next, choose four integers A, B, C, and D satisfying all of the following.
- 1 \le A \le B \le 10.
- 1 \le C \le D \le 10.
- Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with
#.- A \le i \le B.
- C \le j \le D.
You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.
Constraints
- S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.
Input
The input is given from Standard Input in the following format:
S_1
S_2
\vdots
S_{10}
Output
Print the answer in the following format:
A B C D
Sample Input 1
.......... .......... .......... .......... ...######. ...######. ...######. ...######. .......... ..........
Sample Output 1
5 8 4 9
Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.
Sample Input 2
.......... ..#....... .......... .......... .......... .......... .......... .......... .......... ..........
Sample Output 2
2 2 3 3
Sample Input 3
########## ########## ########## ########## ########## ########## ########## ########## ########## ##########
Sample Output 3
1 10 1 10
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