Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ 3 の文字列 S が与えられます。
S に 1 度だけ含まれる文字を 1 つ出力してください。
但し、そのような文字が存在しない場合は代わりに -1 と出力してください。
制約
- S は英小文字のみからなる 3 文字の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。正解が複数ある場合、どれを出力してもよい。
入力例 1
pop
出力例 1
o
pop に o は 1 度だけ含まれます。
入力例 2
abc
出力例 2
a
abc に a, b, c はどれも 1 度だけ含まれるので、どれを出力しても構いません。
入力例 3
xxx
出力例 3
-1
xxx に 1 度だけ含まれる文字はありません。
Score : 100 points
Problem Statement
You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.
Constraints
- S is a string of length 3 consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer. If multiple solutions exist, you may print any of them.
Sample Input 1
pop
Sample Output 1
o
o occurs only once in pop.
Sample Input 2
abc
Sample Output 2
a
a, b, and c occur once each in abc, so you may print any of them.
Sample Input 3
xxx
Sample Output 3
-1
No character occurs only once in xxx.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
以下の条件を全て満たす長さ N の文字列を求めてください。
- 各文字は
-または=である - 回文である
- 文字列中に
=は 1 個または 2 個含まれる。 2 個含まれる場合、それらの=は隣接している
なお、そのような文字列はちょうど 1 つ存在します。
制約
- 1 \leq N \leq 100
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
-==-
入力例 2
7
出力例 2
---=---
Score : 100 points
Problem Statement
Find a length-N string that satisfies all of the following conditions:
- Each character is
-or=. - It is a palindrome.
- It contains exactly one or exactly two
=s. If it contains two=s, they are adjacent.
Such a string is unique.
Constraints
- 1 \leq N \leq 100
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
-==-
Sample Input 2
7
Sample Output 2
---=---
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 国では、1 年が N か月からなる暦を使っています。 i 月 (1\leq i\leq N) は、i 月 1 日から i 月 D _ i 日までの D _ i 日からなります。
AtCoder 国において、1 年のうち日付がゾロ目になる日が何日あるか求めてください。
ただし、i 月 j 日 (1\leq i\leq N,1\leq j\leq D _ i) の日付がゾロ目になるとは、1 種類の数字だけを用いて i と j を十進法で表すことができることをいいます。
制約
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D _ 1 D _ 2 \ldots D _ N
出力
答えを出力せよ。
入力例 1
12 31 29 31 30 31 30 31 31 30 31 30 31
出力例 1
13
AtCoder 国では、 1 月 1 日、1 月 11 日、2 月 2 日、2 月 22 日、3 月 3 日、4 月 4 日、5 月 5 日、6 月 6 日、7 月 7 日、8 月 8 日、9 月 9 日、11 月 1 日、11 月 11 日の合計 13 日の日付がゾロ目になります。
入力例 2
10 10 1 2 3 4 5 6 7 8 100
出力例 2
1
AtCoder 国では、1 月 1 日のみが日付がゾロ目になります。
入力例 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
出力例 3
15
Score : 200 points
Problem Statement
AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.
How many days in a year of AtCoder have "repdigits" dates?
Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.
Constraints
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D _ 1 D _ 2 \ldots D _ N
Output
Print the answer.
Sample Input 1
12 31 29 31 30 31 30 31 31 30 31 30 31
Sample Output 1
13
In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 100
Sample Output 2
1
In AtCoder Kingdom, only January 1 has a repdigit date.
Sample Input 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
Sample Output 3
15
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1 から N の番号がついた N 頭の馬が競争をしました。
全ての馬は同時にスタートし、 i 番の馬はスタートからゴールまで T_i 秒かかりました。
1,2,3 着の馬の番号を求めてください。なお、 T_i は相異なることが保証されます。
制約
- 3\leq N \leq 32
- 1\leq T_i \leq 200
- T_i は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T_1 \dots T_N
出力
1,2,3 着の馬の番号をそれぞれ空白区切りでこの順に出力せよ。
入力例 1
4 100 110 105 95
出力例 1
4 1 3
4,1,3,2 番の順にゴールしました。1,2,3 着の番号である 4,1,3 をこの順に空白区切りで出力してください。
入力例 2
8 72 74 69 70 73 75 71 77
出力例 2
3 4 7
Score : 200 points
Problem Statement
N horses numbered 1 to N had a race.
All horses started simultaneously, and horse i took T_i seconds from the start to the goal.
Find the numbers of the horses that finished in 1st, 2nd, and 3rd places. It is guaranteed that all T_i are distinct.
Constraints
- 3\leq N \leq 32
- 1\leq T_i \leq 200
- All T_i are distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T_1 \dots T_N
Output
Output the numbers of the horses that finished in 1st, 2nd, and 3rd places, in this order, separated by spaces.
Sample Input 1
4 100 110 105 95
Sample Output 1
4 1 3
The horses finished in the order 4, 1, 3, 2. Output the numbers for 1st, 2nd, and 3rd places, which are 4, 1, 3, in this order, separated by spaces.
Sample Input 2
8 72 74 69 70 73 75 71 77
Sample Output 2
3 4 7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ヘビの待ち行列があります。最初、列は空です。
クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 3 種類です。
- タイプ 1 :
1 lの形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。 - タイプ 2 :
2の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。 - タイプ 3 :
3 kの形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。
制約
- 1 \leq Q \leq 3 \times 10^{5}
- タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
- タイプ 2 のクエリにおいて、列が空でないことが保証される
- タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。
1 l
2
3 k
出力
タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。
入力例 1
7 1 5 1 7 3 2 1 3 1 4 2 3 3
出力例 1
5 10
- 1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
- 2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
- 3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
- 4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
- 5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
- 6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
- 7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。
入力例 2
3 1 1 2 1 3
出力例 2
タイプ 3 のクエリが 1 つもない場合もあります。
入力例 3
10 1 15 1 10 1 5 2 1 5 1 10 1 15 2 3 4 3 2
出力例 3
20 5
Score : 300 points
Problem Statement
There is a queue of snakes. Initially, the queue is empty.
You are given Q queries, which should be processed in the order they are given. There are three types of queries:
- Type 1: Given in the form
1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length. - Type 2: Given in the form
2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m. - Type 3: Given in the form
3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.
Constraints
- 1 \leq Q \leq 3 \times 10^{5}
- For a query of type 1, 1 \leq l \leq 10^{9}
- For a query of type 2, it is guaranteed that the queue is not empty.
- For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq 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
Here, \text{query}_i is the i-th query in one of the following forms:
1 l
2
3 k
Output
Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.
Sample Input 1
7 1 5 1 7 3 2 1 3 1 4 2 3 3
Sample Output 1
5 10
- 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
- 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
- 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
- 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
- 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
- 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
- 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.
Sample Input 2
3 1 1 2 1 3
Sample Output 2
It is possible that there are no queries of type 3.
Sample Input 3
10 1 15 1 10 1 5 2 1 5 1 10 1 15 2 3 4 3 2
Sample Output 3
20 5