実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 問の問題が出題されるプログラミングコンテストがあります。 i = 1, 2, \ldots, N について、i 問目の配点は S_i です。
配点が X 以下である問題すべての配点の合計を出力してください。
制約
- 入力される値は全て整数
- 4 \leq N \leq 8
- 100 \leq S_i \leq 675
- 100 \leq X \leq 675
入力
入力は以下の形式で標準入力から与えられる。
N X S_1 S_2 \ldots S_N
出力
答えを出力せよ。
入力例 1
6 200 100 675 201 200 199 328
出力例 1
499
配点が 200 以下である問題は、1, 4, 5 問目の全 3 問であり、それらの配点の合計は S_1 + S_4 + S_5 = 100 + 200 + 199 = 499 です。
入力例 2
8 675 675 675 675 675 675 675 675 675
出力例 2
5400
入力例 3
8 674 675 675 675 675 675 675 675 675
出力例 3
0
Score : 100 points
Problem Statement
There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.
Print the total score for all problems with a score of X or less.
Constraints
- All input values are integers.
- 4 \leq N \leq 8
- 100 \leq S_i \leq 675
- 100 \leq X \leq 675
Input
The input is given from Standard Input in the following format:
N X S_1 S_2 \ldots S_N
Output
Print the answer.
Sample Input 1
6 200 100 675 201 200 199 328
Sample Output 1
499
Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.
Sample Input 2
8 675 675 675 675 675 675 675 675 675
Sample Output 2
5400
Sample Input 3
8 674 675 675 675 675 675 675 675 675
Sample Output 3
0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ N の英小文字からなる文字列 S と英小文字 c_1,c_2 が与えられます。
S の文字のうち c_1 であるもの 以外 を全て c_2 に置き換えた文字列を求めてください。
制約
- 1\le N\le 100
- N は整数
- c_1,c_2 は英小文字
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N c_1 c_2 S
出力
答えを出力せよ。
入力例 1
3 b g abc
出力例 1
gbg
S= abc のうち、 b でない a と c を g に置き換えた結果 gbg になります。したがって、 gbg を出力してください。
入力例 2
1 s h s
出力例 2
s
置き換えた後の文字列が元の文字列と変わらない場合もあります。
入力例 3
7 d a atcoder
出力例 3
aaaadaa
入力例 4
10 b a acaabcabba
出力例 4
aaaabaabba
Score : 100 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters, along with lowercase English letters c_1 and c_2.
Find the string obtained by replacing every character of S that is not c_1 with c_2.
Constraints
- 1\le N\le 100
- N is an integer.
- c_1 and c_2 are lowercase English letters.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given in the following format from Standard Input:
N c_1 c_2 S
Output
Print the answer.
Sample Input 1
3 b g abc
Sample Output 1
gbg
Replacing a and c (which are not b) with g in S= abc results in gbg, so print gbg.
Sample Input 2
1 s h s
Sample Output 2
s
It is possible that the resulting string after replacement is the same as the original string.
Sample Input 3
7 d a atcoder
Sample Output 3
aaaadaa
Sample Input 4
10 b a acaabcabba
Sample Output 4
aaaabaabba
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字のみからなる N 個の文字列 S_1,S_2,\ldots,S_N が与えられます。
1 以上 N 以下の 相異なる 整数 i,j であって、S_i と S_j をこの順に連結した文字列が回文となるようなものが存在するか判定してください。
ただし、長さ M の文字列 T が回文であるとは、任意の 1\leq i\leq M について、T の i 文字目と (M+1-i) 文字目が一致していることをいいます。
制約
- 2\leq N\leq 100
- 1\leq \lvert S_i\rvert \leq 50
- N は整数
- S_i は英小文字のみからなる文字列
- S_i はすべて異なる。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
問題文の条件をみたす i,j が存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
5 ab ccef da a fe
出力例 1
Yes
(i,j)=(1,4) とすると、S_1=ab と S_4=a をこの順に連結した文字列は aba となり、
これは回文であるため条件をみたしています。
よって、Yes を出力します。
また、(i,j)=(5,2) としても、S_5=fe と S_2=ccef をこの順に連結した文字列は feccef となり、やはり条件をみたしています。
入力例 2
3 a b aba
出力例 2
No
S_1, S_2, S_3 のうち、どの相異なる 2 つの文字列を繋げても回文となりません。
よって、No を出力します。
問題文における i,j は相異なる必要があることに注意してください。
入力例 3
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
出力例 3
Yes
Score : 200 points
Problem Statement
You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.
A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.
Constraints
- 2\leq N\leq 100
- 1\leq \lvert S_i\rvert \leq 50
- N is an integer.
- S_i is a string consisting of lowercase English letters.
- All S_i are distinct.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If there are i and j that satisfy the condition in the problem statement, print Yes; otherwise, print No.
Sample Input 1
5 ab ccef da a fe
Sample Output 1
Yes
If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.
Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.
Sample Input 2
3 a b aba
Sample Output 2
No
No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated.
Thus, print No.
Note that the i and j in the statement must be distinct.
Sample Input 3
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Sample Output 3
Yes
実行時間制限: 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
配点 : 300 点
問題文
空の整数列 A=() があります。クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 2 種類です。
- タイプ 1 :
1 c xの形式で与えられる。A の末尾に x を c 個追加する。 - タイプ 2 :
2 kの形式で与えられる。A の先頭 k 要素を削除し、削除した k 個の整数の総和を出力する。このとき、k はその時点での A の長さ以下であることが保証される。
制約
- 1 \leq Q \leq 2 \times 10^{5}
- タイプ 1 のクエリにおいて、 1 \leq c \leq 10^{9}
- タイプ 1 のクエリにおいて、 1 \leq x \leq 10^{9}
- タイプ 2 のクエリにおいて、その時点での A の長さを n として、 1 \leq k \leq \min(10^{9},n)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
ただし、 \text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。
1 c x
2 k
出力
タイプ 2 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 2 のクエリに対する答えを出力せよ。
入力例 1
5 1 2 3 1 4 5 2 3 1 6 2 2 5
出力例 1
11 19
- 1 個目のクエリ: A の末尾に 3 を 2 個追加する。このとき、A=(3,3) となる。
- 2 個目のクエリ: A の末尾に 5 を 4 個追加する。このとき、A=(3,3,5,5,5,5) となる。
- 3 個目のクエリ: A の先頭 3 要素を削除する。このとき、削除した 3 個の整数の総和は 3+3+5=11 となるため 11 と出力する。削除後、A=(5,5,5) となる。
- 4 個目のクエリ: A の末尾に 2 を 6 個追加する。このとき、A=(5,5,5,2,2,2,2,2,2) となる。
- 5 個目のクエリ: A の先頭 5 要素を削除する。このとき、削除した 5 個の整数の総和は 5+5+5+2+2=19 となるため 19 と出力する。削除後、A=(2,2,2,2) となる。
入力例 2
10 1 75 22 1 81 72 1 2 97 1 84 82 1 2 32 1 39 57 2 45 1 40 16 2 32 2 42
出力例 2
990 804 3024
入力例 3
10 1 160449218 954291757 2 17217760 1 353195922 501899080 1 350034067 910748511 1 824284691 470338674 2 180999835 1 131381221 677959980 1 346948152 208032501 1 893229302 506147731 2 298309896
出力例 3
16430766442004320 155640513381884866 149721462357295680
Score : 300 points
Problem Statement
There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:
- Type 1: Given in the format
1 c x. Add c copies of x to the end of A. - Type 2: Given in the format
2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.
Constraints
- 1 \leq Q \leq 2 \times 10^{5}
- In type 1 queries, 1 \leq c \leq 10^{9}.
- In type 1 queries, 1 \leq x \leq 10^{9}.
- In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
- All input values are integers.
Input
The input is given from standard input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
where \text{query}_i represents the i-th query and is in one of the following formats:
1 c x
2 k
Output
Let q be the number of type 2 queries. Output q lines. The i-th line should contain the answer to the i-th type 2 query.
Sample Input 1
5 1 2 3 1 4 5 2 3 1 6 2 2 5
Sample Output 1
11 19
- 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
- 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
- 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
- 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
- 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).
Sample Input 2
10 1 75 22 1 81 72 1 2 97 1 84 82 1 2 32 1 39 57 2 45 1 40 16 2 32 2 42
Sample Output 2
990 804 3024
Sample Input 3
10 1 160449218 954291757 2 17217760 1 353195922 501899080 1 350034067 910748511 1 824284691 470338674 2 180999835 1 131381221 677959980 1 346948152 208032501 1 893229302 506147731 2 298309896
Sample Output 3
16430766442004320 155640513381884866 149721462357295680