実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。
制約
- 1 \leq a \lt b \leq 15
- a,b は整数
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
a 番の点と b 番の点が線で直接結ばれているなら Yes、結ばれていないなら No を出力せよ。
入力例 1
1 2
出力例 1
Yes
問題文で示した図において、1 番の点と 2 番の点は線で直接結ばれています。 よって、Yes を出力します。
入力例 2
2 8
出力例 2
No
問題文で示した図において、2 番の点と 8 番の点は線で直接結ばれていません。 よって、No を出力します。
入力例 3
14 15
出力例 3
No
Score : 100 points
Problem Statement
Determine if there is a segment that directly connects the points numbered a and b in the figure below.
Constraints
- 1 \leq a \lt b \leq 15
- a and b are integers.
Input
The input is given from Standard Input in the following format:
a b
Output
Print Yes if there is a segment that directly connects the points numbered a and b; print No otherwise.
Sample Input 1
1 2
Sample Output 1
Yes
In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.
Sample Input 2
2 8
Sample Output 2
No
In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.
Sample Input 3
14 15
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
4 個のボールがあり、i 個目のボールの色は A_i です。
同じ色のボールを 2 つ選び両方捨てるという操作を最大何回行えるか求めてください。
制約
- A_1,A_2,A_3,A_4 はそれぞれ 1 以上 4 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3 A_4
出力
操作回数の最大値を整数として出力せよ。
入力例 1
2 1 2 1
出力例 1
2
1 個目のボールと 3 個目のボールはどちらも色が 2 なので、1 個目のボールと 3 個目のボールを共に捨てる操作を行えます。
次に、2 個目のボールと 4 個目のボールはどちらも色が 1 なので、2 個目のボールと 4 個目のボールを共に捨てる操作を行えます。
合計で 2 回操作を行えます。
入力例 2
4 4 4 1
出力例 2
1
入力例 3
1 2 3 4
出力例 3
0
操作を一度も行えない場合もあります。
Score : 100 points
Problem Statement
There are four balls, and the color of the i-th ball is A_i.
Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.
Constraints
- Each of A_1, A_2, A_3, A_4 is an integer between 1 and 4, inclusive.
Input
The input is given from Standard Input in the following format:
A_1 A_2 A_3 A_4
Output
Print the maximum number of times the operation can be performed as an integer.
Sample Input 1
2 1 2 1
Sample Output 1
2
The first and third balls both have color 2, so you can perform the operation to discard the first and third balls together.
Next, the second and fourth balls both have color 1, so you can perform the operation to discard the second and fourth balls together.
Hence, you can perform a total of two operations.
Sample Input 2
4 4 4 1
Sample Output 2
1
Sample Input 3
1 2 3 4
Sample Output 3
0
There are cases where you cannot perform the operation even once.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。ここで、文字列の長さはそれぞれ相異なります。
これらの文字列を長さの昇順に並べ替え、この順に結合して得られる文字列を求めてください。
制約
- 2 \leq N \leq 50
- N は整数
- S_i は長さ 1 以上 50 以下の英小文字からなる文字列
- i \neq j のとき S_i と S_j の長さは異なる
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 tc oder a
出力例 1
atcoder
( tc, oder, a ) を文字列の長さの昇順に並べ替えると ( a, tc, oder ) となります。これらの文字列を順に結合すると文字列 atcoder が得られます。
入力例 2
4 cat enate on c
出力例 2
concatenate
Score : 200 points
Problem Statement
You are given N strings S_1, S_2, \ldots, S_N, each consisting of lowercase English letters. The lengths of these strings are all distinct.
Sort these strings in ascending order of length, and then concatenate them in that order to form a single string.
Constraints
- 2 \leq N \leq 50
- N is an integer.
- Each S_i is a string consisting of lowercase English letters with length between 1 and 50, inclusive.
- If i \neq j, the length of S_i is different from the length of S_j.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
3 tc oder a
Sample Output 1
atcoder
When we sort (tc, oder, a) in ascending order of length, we get (a, tc, oder). Concatenating them in this order yields the string atcoder.
Sample Input 2
4 cat enate on c
Sample Output 2
concatenate
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。ここで、 A の各要素は -1 または 1 以上 N 以下の整数です。
以下の条件を全て満たす長さ N の整数列 P=(P_1,P_2,\ldots,P_N) が存在するか判定し、存在するならば一つ求めてください。
- P は (1,2,\ldots,N) を並び替えてできる整数列である。
- i=1,2,\ldots,N に対し、 A_i \neq -1 ならば P_i=A_i が成り立つ。
制約
- 1\le N\le 10
- A_i=-1 または 1\le A_i \le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
条件を全て満たす P が存在しない場合は No と出力せよ。
そうでない場合、条件を全て満たす P を以下の形式で出力せよ。
Yes P_1 P_2 \ldots P_N
条件を全て満たす P が複数存在する場合、どれを出力しても正答となる。
入力例 1
4 -1 -1 2 -1
出力例 1
Yes 3 1 2 4
P=(3,1,2,4) とすると条件を全て満たします。
このほかにも、 P=(1,3,2,4) や P=(4,3,2,1) なども条件を全て満たします。
入力例 2
5 -1 -1 1 -1 1
出力例 2
No
条件を全て満たす P は存在しません。
入力例 3
7 3 -1 4 -1 5 -1 2
出力例 3
Yes 3 7 4 1 5 6 2
Score : 200 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Here, each element of A is either -1 or an integer between 1 and N, inclusive.
Determine whether there exists an integer sequence P=(P_1,P_2,\ldots,P_N) of length N that satisfies all of the following conditions, and if it exists, find one.
- P is a permutation of (1,2,\ldots,N).
- For i=1,2,\ldots,N, if A_i \neq -1, then P_i=A_i holds.
Constraints
- 1\le N\le 10
- A_i=-1 or 1\le A_i \le N
- 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 no P that satisfies all conditions, output No.
Otherwise, output P that satisfies all conditions in the following format:
Yes P_1 P_2 \ldots P_N
If there are multiple P that satisfy all conditions, any of them may be output.
Sample Input 1
4 -1 -1 2 -1
Sample Output 1
Yes 3 1 2 4
P=(3,1,2,4) satisfies all conditions.
Besides this, P=(1,3,2,4) or P=(4,3,2,1) also satisfies all conditions.
Sample Input 2
5 -1 -1 1 -1 1
Sample Output 2
No
There is no P that satisfies all conditions.
Sample Input 3
7 3 -1 4 -1 5 -1 2
Sample Output 3
Yes 3 7 4 1 5 6 2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
長さ N の数列 A が与えられます。
A のうち丁度 K 要素を自由に選んで消し、残った要素を順序を保って連結した数列を B とします。
( B の最大値 ) - ( B の最小値 ) としてありうる最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K < N \le 2 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
5 2 3 1 5 4 9
出力例 1
2
A=(3,1,5,4,9) から丁度 2 要素を自由に選んで消すことを考えます。
- 例えば 2 要素目の 1 、 5 要素目の 9 を消すと、消した後の数列 B=(3,5,4) となります。
- このとき B の最大値は 5 、最小値は 3 なので ( B の最大値 ) - ( B の最小値 ) =2 となり、これは達成可能な最小値です。
入力例 2
6 5 1 1 1 1 1 1
出力例 2
0
入力例 3
8 3 31 43 26 6 18 36 22 13
出力例 3
18
Score : 250 points
Problem Statement
You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.
Constraints
- All inputs are integers.
- 1 \le K < N \le 2 \times 10^5
- 1 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 2 3 1 5 4 9
Sample Output 1
2
Consider removing exactly two elements from A=(3,1,5,4,9).
- For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
- In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.
Sample Input 2
6 5 1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
8 3 31 43 26 6 18 36 22 13
Sample Output 3
18