A - Insert

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A と整数 K,X が与えられます。
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を出力してください。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 100
  • 1 \le A_i,X \le 100

入力

入力は以下の形式で標準入力から与えられる。

N K X
A_1 A_2 \dots A_N

出力

整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を、以下の形式で出力せよ。

B_1 B_2 \dots B_{N+1}

入力例 1

4 3 7
2 3 5 11

出力例 1

2 3 5 7 11

K=3, X=7, A=(2,3,5,11) のとき、 B=(2,3,5,7,11) です。

入力例 2

1 1 100
100

出力例 2

100 100

入力例 3

8 8 3
9 9 8 2 4 4 3 5

出力例 3

9 9 8 2 4 4 3 5 3

Score : 100 points

Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

  • All input values are integers.
  • 1 \le K \le N \le 100
  • 1 \le A_i, X \le 100

Input

The input is given from Standard Input in the following format:

N K X
A_1 A_2 \dots A_N

Output

Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A, in the following format:

B_1 B_2 \dots B_{N+1}

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3
B - Legendary Players

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

AtCoder では、レーティング上位 10 人のハンドルネームには金色の冠が、上位 1 人のハンドルネームには白金色の冠が表示されます。

このコンテストが開始した時点で、アルゴリズム部門での上位 10 人に入っているプレイヤーのハンドルネームとレーティングは以下のようになっています。

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

上記のプレイヤーのハンドルネーム S が与えられるので、その人のレーティングを出力してください。

制約

  • S はアルゴリズム部門でレーティング上位 10 人に入っているプレイヤーのハンドルネームのいずれかと等しい。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

対応するプレイヤーのレーティングを 1 行で出力せよ。

入力例 1

tourist

出力例 1

3858

このコンテストが開始した時点において、 tourist さんのアルゴリズム部門のレーティングは 3858 です。

入力例 2

semiexp

出力例 2

3481

このコンテストが開始した時点において、 semiexp さんのアルゴリズム部門のレーティングは 3481 です。

Score : 100 points

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

  • S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Input

The input is given from Standard Input in the following format:

S

Output

Print the rating of the corresponding player in one line.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.
C - LOOKUP

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S,T が与えられるので、 T が S の(連続する)部分文字列かどうか判定してください。

なお、文字列 X に以下の操作を 0 回以上施して文字列 Y が得られる時、またその時に限り Y は X の(連続する)部分文字列であると言います。

  • 以下の 2 つの操作から 1 つを選択して、その操作を行う。
    • X の先頭の 1 文字を削除する。
    • X の末尾の 1 文字を削除する。

例えば tag は voltage の(連続する)部分文字列ですが、 ace は atcoder の(連続する)部分文字列ではありません。

制約

  • S,T は英小文字からなる
  • 1 \le |S|,|T| \le 100 ( |X| は文字列 X の長さ )

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

T が S の(連続する)部分文字列なら Yes 、そうでないなら No と出力せよ。

入力例 1

voltage
tag

出力例 1

Yes

tag は voltage の(連続する)部分文字列です。

入力例 2

atcoder
ace

出力例 2

No

ace は atcoder の(連続する)部分文字列ではありません。

入力例 3

gorilla
gorillagorillagorilla

出力例 3

No

入力例 4

toyotasystems
toyotasystems

出力例 4

Yes

S=T である場合もあります。

Score : 200 points

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

  • Do one of the following.
    • Delete the first character in X.
    • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

  • S and T consist of lowercase English letters.
  • 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Input

The input is given from Standard Input in the following format:

S
T

Output

If T is a (contiguous) substring of S, print Yes; otherwise, print No.

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.
D - Qualification Contest

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • 1 \leq K \leq N \leq 100
  • K, N は整数
  • S_i は英小文字からなる長さ 10 以下の文字列
  • i \neq j ならば S_i \neq S_j

入力

入力は以下の形式で標準入力から与えられる。

N K
S_1
S_2
\vdots
S_N

出力

答えを改行区切りで出力せよ。

入力例 1

5 3
abc
aaaaa
xyz
a
def

出力例 1

aaaaa
abc
xyz

このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。

上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。

入力例 2

4 4
z
zyx
zzz
rbg

出力例 2

rbg
z
zyx
zzz

入力例 3

3 1
abc
arc
agc

出力例 3

abc

Score : 200 points

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

What is lexicographical order?

Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.

Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.

  1. Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
  3. If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.

Constraints

  • 1 \leq K \leq N \leq 100
  • K and N are integers.
  • S_i is a string of length 10 consisting of lowercase English letters.
  • S_i \neq S_j if i \neq j.

Input

The input is given from Standard Input in the following format:

N K
S_1
S_2
\vdots
S_N

Output

Print the nicknames, separated by newlines.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc
E - Pigeonhole Query

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N 匹の鳩がおり、 1 から N までの番号がつけられています。また、 N 個の巣があり、 1 から N までの番号がつけられています。はじめ、鳩 i は巣 i にいます (1\leq i\leq N)。

Q 個のクエリが与えられるので順に処理してください。 クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 P H : 鳩 P を巣 H に移動させる。
  • 2 : 複数の鳩がいる巣の個数を出力する。

制約

  • 2\leq N\leq 10^6
  • 1\leq Q\leq 3\times 10^5
  • 1\leq P,H\leq N
  • 1 つ目の形式のクエリについて、鳩 P は移動する前に巣 H にいない
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 P H

2

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2

出力例 1

0
1
1
2

初め、鳩 1,2,3,4 はそれぞれ巣 1,2,3,4 にいます。

  • 1 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 1,1,1,1 匹います。鳩が複数いる巣は存在しないので 0 を出力します。
  • 2 つ目のクエリについて、鳩 1 を巣 2 に移動します。
  • 3 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,1,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
  • 4 つ目のクエリについて、鳩 3 を巣 2 に移動します。
  • 5 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,3,0,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
  • 6 つ目のクエリについて、鳩 3 を巣 4 に移動します。
  • 7 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,0,2 匹います。鳩が複数いる巣は巣 2,4 の 2 つなので 2 を出力します。

入力例 2

5 10
2
1 4 3
1 4 5
2
1 3 1
2
1 2 3
1 2 5
1 1 3
2

出力例 2

0
1
2
1

Score : 300 points

Problem Statement

There are N pigeons numbered from 1 to N, and there are N nests numbered from 1 to N. Initially, pigeon i is in nest i for 1\leq i\leq N.

You are given Q queries, which you must process in order. There are two types of queries, each given in one of the following formats:

  • 1 P H : Move pigeon P to nest H.
  • 2 : Output the number of nests that contain more than one pigeon.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 3\times 10^5
  • 1 \leq P, H \leq N
  • For a query of the first type, pigeon P is not in nest H before the move.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following two formats:

1 P H

2

Output

Print the answer to each query on a new line according to the instructions in the problem statement.

Sample Input 1

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2

Sample Output 1

0
1
1
2

Initially, pigeons 1,2,3,4 are in nests 1,2,3,4, respectively.

  • For the 1st query, the counts of pigeons in nests 1,2,3,4 are 1,1,1,1. No nests contain multiple pigeons, output 0.
  • For the 2nd query, move pigeon 1 to nest 2.
  • For the 3rd query, the counts become 0,2,1,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
  • For the 4th query, move pigeon 3 to nest 2.
  • For the 5th query, the counts become 0,3,0,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
  • For the 6th query, move pigeon 3 to nest 4.
  • For the 7th query, the counts become 0,2,0,2, respectively. Two nests (nests 2 and 4) contain multiple pigeons, so output 2.

Sample Input 2

5 10
2
1 4 3
1 4 5
2
1 3 1
2
1 2 3
1 2 5
1 1 3
2

Sample Output 2

0
1
2
1