Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
ナオヒロ君は N+1 個の連続する整数を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。
残っている N 個の整数が順不同で A_1,\ldots,A_N として与えられるので、なくした整数を求めてください。
なお、なくした整数が一意に定まるような入力のみが与えられます。
制約
- 2 \leq N \leq 100
- 1 \leq A_i \leq 1000
- 入力は全て整数である
- なくした整数は一意に定まる
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 2 3 5
出力例 1
4
ナオヒロ君は初め 2,3,4,5 の 4 個の整数を持っており、4 をなくし、2,3,5 が残っていました。
なくした整数である 4 を出力します。
入力例 2
8 3 1 4 5 9 2 6 8
出力例 2
7
入力例 3
16 152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150
出力例 3
151
Score : 200 points
Problem Statement
Naohiro had N+1 consecutive integers, one of each, but he lost one of them.
The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.
The given input guarantees that the lost integer is uniquely determined.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq 1000
- All input values are integers.
- The lost integer is uniquely determined.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
3 2 3 5
Sample Output 1
4
Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.
Print the lost integer, 4.
Sample Input 2
8 3 1 4 5 9 2 6 8
Sample Output 2
7
Sample Input 3
16 152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150
Sample Output 3
151
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。
i 回目の操作では次の操作を行います。
- 左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
- そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。
Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。
制約
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
出力
K 個の整数を空白区切りで一行に出力せよ。 ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。
入力例 1
5 3 5 1 3 4 3 3 1 1 2
出力例 1
2 4 5
最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。
- 左から 3 番目のコマはマス 4 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。 コマはマス 1, 3, 5 にある状態になります。
- 左から 3 番目のコマはマス 5 にあります。 これは一番右のマスなので、何も行いません。 コマはマス 1, 3, 5 にある状態のままです。
- 左から 1 番目のコマはマス 1 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。 コマはマス 2, 3, 5 にある状態になります。
- 左から 1 番目のコマはマス 2 にあります。 これは一番右のマスでありませんが、その 1 つ右のマス（マス 3 ）にコマが置かれているため、何も行いません。 コマはマス 2, 3, 5 にある状態のままです。
- 左から 2 番目のコマはマス 3 にあります。 これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。 コマはマス 2, 4, 5 にある状態になります。
よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。
入力例 2
2 2 2 1 2 1 2
出力例 2
1 2
入力例 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
出力例 3
2 5 6 7 9 10
Score : 200 points
Problem Statement
There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them.
The i-th operation is as follows:
- If the L_i-th piece from the left is on its rightmost square, do nothing.
- Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.
Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.
Constraints
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
Output
Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.
Sample Input 1
5 3 5 1 3 4 3 3 1 1 2
Sample Output 1
2 4 5
At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:
- The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
- The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
- The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
- The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
- The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.
Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.
Sample Input 2
2 2 2 1 2 1 2
Sample Output 2
1 2
Sample Input 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
Sample Output 3
2 5 6 7 9 10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1 から N の番号がついた N 人の人がいます。人 i は数 A_i を持っています。
「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たす人のうち、持っている数が最大である人の番号を求めてください。
条件を満たす人が存在しない場合、代わりにそのことを報告してください。
制約
- 1 \leq N \leq 3\times 10^5
- 1 \leq A_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たす人が存在しない場合、-1 と出力せよ。
条件を満たす人が存在する場合、そのうち、持っている数が最大である人の番号を出力せよ。
入力例 1
9 2 9 9 7 9 2 4 5 8
出力例 1
9
「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たすのは人 4,7,8,9 の 4 人です。
これらの人が持っている数はそれぞれ 7,4,5,8 であり、最大の数を持っているのは人 9 です。
よって答えは 9 となります。
入力例 2
4 1000000000 1000000000 998244353 998244353
出力例 2
-1
条件を満たす人が存在しない場合、-1 を出力してください。
Score : 300 points
Problem Statement
There are N people, labeled 1 to N. Person i has an integer A_i.
Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.
If no person satisfies the condition, report that fact instead.
Constraints
- 1 \leq N \leq 3\times 10^5
- 1 \leq A_i \leq 10^9
- 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 no person satisfies the condition "None of the other N-1 people has the same integer as themselves," print -1.
Otherwise, among those who satisfy it, print the label of the person whose integer is the largest.
Sample Input 1
9 2 9 9 7 9 2 4 5 8
Sample Output 1
9
Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.
Sample Input 2
4 1000000000 1000000000 998244353 998244353
Sample Output 2
-1
If no person satisfies the condition, print -1.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N,Q と、長さ N の英小文字からなる文字列 S が与えられます。
以下で説明されるクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。
1 x: 「S の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行う。2 x: S の x 番目の文字を出力する。
制約
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S は英小文字からなる。
2 xの形式のクエリが 1 個以上与えられる。- N,Q,x はすべて整数。
入力
入力は以下の形式で標準入力から与えられる。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
それぞれのクエリは以下の形式で与えられる。ここで、t は 1 または 2 である。
t x
出力
2 x の形式の各クエリについて、答えを一行に出力せよ。
入力例 1
3 3 abc 2 2 1 1 2 2
出力例 1
b a
1 個目のクエリのとき、S は abc なので 2 文字目の b を出力します。
2 個目のクエリのとき、S は abc から cab に変わります。
3 個目のクエリのとき、S は cab なので 2 文字目の a を出力します。
入力例 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
出力例 2
c u c u
Score : 300 points
Problem Statement
You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.
Process Q queries. Each query is of one of the following two types.
1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.2 x: Print the x-th character of S.
Constraints
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S consists of lowercase English letters.
- At least one query in the format
2 x. - N, Q, x are all integers.
Input
Input is given from Standard Input in the following format:
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in the following format, where t is 1 or 2:
t x
Output
For each query in the format 2 x, print the answer in a single line.
Sample Input 1
3 3 abc 2 2 1 1 2 2
Sample Output 1
b a
In the 1-st query, S is abc, so the 2-nd character b should be printed.
In the 2-nd query, S is changed from abc to cab.
In the 3-rd query, S is cab, so the 2-nd character a should be printed.
Sample Input 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
Sample Output 2
c u c u
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。 最初、袋は空で、高橋君は Q 回の操作を行います。 それぞれの操作は以下の 3 種類のうちのいずれかです。
- 操作 1 : まだ何も書かれていないボール 1 つに整数 X_i を書き込み、袋に入れる。
- 操作 2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それに X_i を加えたものに書き換える。
- 操作 3 : 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの 1 つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。
1\leq i\leq Q について i 回目の操作の種類 P_i および操作 1 , 2 における X_i の値が与えられるので、操作 3 において記録された数を順に出力してください。
制約
- 1 \leq Q \leq 2\times 10^5
- 1 \leq P_i \leq 3
- 1 \leq X_i \leq 10^9
- 入力は全て整数である。
- P_i=3 であるような i が 1 つ以上存在する。
- P_i=3 であるとき、 i 回目の操作の直前の時点で、袋には 1 つ以上のボールが入っている。
入力
入力は以下の形式で標準入力から与えられる。
Q query_1 query_2 : query_Q
2 行目から Q+1 行目の各 query_i は次のいずれかの形で与えられる。
1 X_i
2 X_i
3
まず、1\leq P_i\leq 3 が与えられる。これは操作の種類を表す。 P_i=1 または P_i=2 ならば、その後に空白区切りで X_i が与えられる。
出力
Q 回の操作のうち操作の種類が P_i=3 であるような各操作について、記録された数を改行区切りで出力せよ。
入力例 1
5 1 3 1 5 3 2 2 3
出力例 1
3 7
高橋君は次のように操作を行います。
- 3 の書かれたボールを袋に入れる。
- 5 の書かれたボールを袋に入れる。
- 今、袋には 3 の書かれたボールと 5 の書かれたボールが入っているため、このうち小さい 3 の書かれたボールを取り出し、 3 を記録した後に捨てる。
- 今、袋には 5 の書かれたボールのみが入っているため、この数を 5+2=7 に書き換える。
- 今、袋には 7 の書かれたボールのみが入っているため、このボールを取り出し、 7 を記録した後に捨てる。
よって、記録された順に 3 , 7 を出力します。
入力例 2
6 1 1000000000 2 1000000000 2 1000000000 2 1000000000 2 1000000000 3
出力例 2
5000000000
答えが 32 bit整数に収まらないことがある事に注意してください。
Score : 400 points
Problem Statement
Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.
- Type 1: Write an integer X_i on a blank ball and put it in the bag.
- Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
- Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.
For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.
Constraints
- 1 \leq Q \leq 2\times 10^5
- 1 \leq P_i \leq 3
- 1 \leq X_i \leq 10^9
- All values in input are integers.
- There is one or more i such that P_i=3.
- If P_i=3, the bag contains at least one ball just before the i-th operation.
Input
Input is given from Standard Input in the following format:
Q query_1 query_2 : query_Q
Each query_i in the 2-nd through (Q+1)-th lines is in the following format:
1 X_i
2 X_i
3
The first number in each line is 1\leq P_i\leq 3, representing the type of the operation. If P_i=1 or P_i=2, it is followed by a space, and then by X_i.
Output
For each operation with P_i=3 among the Q operations, print the recorded integer in its own line.
Sample Input 1
5 1 3 1 5 3 2 2 3
Sample Output 1
3 7
Takahashi will do the following operations.
- Write 3 on a ball and put it in the bag.
- Write 5 on a ball and put it in the bag.
- The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
- The bag now contains just a ball with 5. Replace this integer with 5+2=7.
- The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.
Therefore, we should print 3 and 7, in the order they are recorded.
Sample Input 2
6 1 1000000000 2 1000000000 2 1000000000 2 1000000000 2 1000000000 3
Sample Output 2
5000000000
Note that the outputs may not fit into a 32-bit integer.