実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) および正整数 P,Q,R,S が与えられます。
ここで、P,Q,R,S は、1\leq P\leq Q<R\leq S \leq N および Q-P=S-R をみたしています。
数列 A の P 番目から Q 番目の項までと R 番目から S 番目の項までを入れ替えた数列を B=(B_1, B_2,\ldots, B_N) とします。
数列 B を出力してください。
制約
- 1\leq N \leq 100
- 1\leq A_i\leq 100
- 1\leq P\leq Q<R\leq S \leq N
- Q-P=S-R
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P Q R S A_1 A_2 \ldots A_N
出力
B_1, B_2,\ldots, B_N を空白区切りで出力せよ。
入力例 1
8 1 3 5 7 1 2 3 4 5 6 7 8
出力例 1
5 6 7 4 1 2 3 8
数列 A=(1,2,3,4,5,6,7,8) の 1 番目から 3 番目の項 (1,2,3) と 5 番目から 7 番目までの項 (5,6,7) を 入れ替えると, B=(5,6,7,4,1,2,3,8) となります。 よってこれを空白区切りで出力します。
入力例 2
5 2 3 4 5 2 2 1 1 1
出力例 2
2 1 1 2 1
数列には同じ整数が複数回現れる事もあります。
入力例 3
2 1 1 2 2 50 100
出力例 3
100 50
入力例 4
10 2 4 7 9 22 75 26 45 72 81 47 29 97 2
出力例 4
22 47 29 97 72 81 75 26 45 2
Score : 100 points
Problem Statement
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.
Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.
Constraints
- 1\leq N \leq 100
- 1\leq A_i\leq 100
- 1\leq P\leq Q<R\leq S \leq N
- Q-P=S-R
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P Q R S A_1 A_2 \ldots A_N
Output
Print B_1, B_2,\ldots, B_N, with spaces in between.
Sample Input 1
8 1 3 5 7 1 2 3 4 5 6 7 8
Sample Output 1
5 6 7 4 1 2 3 8
Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.
Sample Input 2
5 2 3 4 5 2 2 1 1 1
Sample Output 2
2 1 1 2 1
The same integer may occur multiple times in the sequence.
Sample Input 3
2 1 1 2 2 50 100
Sample Output 3
100 50
Sample Input 4
10 2 4 7 9 22 75 26 45 72 81 47 29 97 2
Sample Output 4
22 47 29 97 72 81 75 26 45 2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は N 個の料理を食べようとしています。
i 番目に食べようとしている料理は、S_i = sweet のとき甘い料理であり、S_i = salty のとき塩辛い料理です。
高橋君は甘い料理を 2 つ連続で食べると気持ち悪くなってしまい、その後料理が食べられなくなってしまいます。
高橋君がすべての料理を食べることができるか判定してください。
制約
- N は 1 以上 100 以下の整数
- S_i は
sweetまたはsalty
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
高橋君がすべての料理を食べることができるならば Yes を、できないならば No を出力せよ。
入力例 1
5 salty sweet salty salty sweet
出力例 1
Yes
高橋君は甘い料理を 2 つ連続で食べることがないので、気持ち悪くなることなくすべての料理を食べることができます。
入力例 2
4 sweet salty sweet sweet
出力例 2
Yes
高橋君は気持ち悪くなってしまいますが、すべての料理を食べることができます。
入力例 3
6 salty sweet sweet salty sweet sweet
出力例 3
No
高橋君は 3 番目の料理を食べると気持ち悪くなってしまい、4 番目以降の料理が食べられなくなります。
Score : 100 points
Problem Statement
Takahashi is planning to eat N dishes.
The i-th dish he plans to eat is sweet if S_i = sweet, and salty if S_i = salty.
If he eats two sweet dishes consecutively, he will feel sick and be unable to eat any more dishes.
Determine whether he can eat all the dishes.
Constraints
- N is an integer between 1 and 100, inclusive.
- Each S_i is
sweetorsalty.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print Yes if Takahashi can eat all the dishes, and No otherwise.
Sample Input 1
5 salty sweet salty salty sweet
Sample Output 1
Yes
He will not eat two sweet dishes consecutively, so he can eat all the dishes without feeling sick.
Sample Input 2
4 sweet salty sweet sweet
Sample Output 2
Yes
He will feel sick but can still eat all the dishes.
Sample Input 3
6 salty sweet sweet salty sweet sweet
Sample Output 3
No
He feels sick when eating the 3rd dish and cannot eat the 4th and subsequent dishes.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
アイドルグループ Bit♡Beat では、新曲のカップリングとしてメンバーの中から 2 人のユニット（選抜）を組むことになりました。
グループには N 人のメンバーがおり、それぞれのメンバーにスキル値が定まっています。 i 人目のメンバー (1\le i\le N) のスキル値は A_i です。
プロデューサーであるあなたは、スキル値の合計が ちょうど S になるような 2 人のメンバーの選び方を探しています。
スキル値の合計がちょうど S になるような 2 人のメンバーの選び方が何通りあるか求めてください。
制約
- 2\le N\le 5\times 10^5
- 1\le S \le 10^9
- 1\le A_i\le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N S A_1 A_2 \ldots A_N
出力
スキル値の合計がちょうど S になるような 2 人のメンバーの選び方が何通りあるか出力せよ。
入力例 1
5 11 5 6 9 2 2
出力例 1
3
1 人目と 2 人目がユニットを組むと、スキル値の合計は 5+6=11 となります。
このほかにも、 3 人目と 4 人目、3 人目と 5 人目がユニットを組んでも条件を満たします。
条件を満たす 2 人のメンバーの選び方は 3 通りであるため、 3 を出力してください。
入力例 2
10 1000000000 1 1 1 1 1 1 1 1 1 1
出力例 2
0
条件を満たす 2 人のメンバーの選び方が存在しない場合もあります。
入力例 3
6 14 7 7 7 7 7 7
出力例 3
15
入力例 4
15 8 3 4 10 9 1 1 1 7 8 9 9 3 8 9 7
出力例 4
6
実行時間制限: 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
配点 : 300 点
問題文
整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。
- N 桁の正整数である。
- X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1
制約
- N は整数
- 2 \le N \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
4
出力例 1
203
4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。
入力例 2
2
出力例 2
25
入力例 3
1000000
出力例 3
248860093
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.
- X is an N-digit positive integer.
- Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.
Constraints
- N is an integer.
- 2 \le N \le 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
4
Sample Output 1
203
Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.
Sample Input 2
2
Sample Output 2
25
Sample Input 3
1000000
Sample Output 3
248860093
Be sure to find the count modulo 998244353.