CODE FESTIVAL 2016 qual A

A - CODEFESTIVAL 2016

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

このコンテストの名前は CODE FESTIVAL です。しかし、高橋君はいつも CODEFESTIVAL と書き間違えてしまいます。つまり、CODE と FESTIVAL の間の半角スペースを省いてしまいます。

そこで高橋君は、省いてしまった半角スペースを復元するプログラムを作ることにしました。

長さ 12 の文字列 s が与えられます。 s の前半 4 文字と後半 8 文字の間に半角スペースを 1 つ挿入し、出力してください。

制約

s は長さ 12 である。
s は英大文字のみからなる。

入力

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

出力

s の前半 4 文字と後半 8 文字の間に半角スペースを 1 つ挿入し、出力せよ。出力の末尾には改行を入れること。

入力例 1

CODEFESTIVAL

出力例 1

CODE FESTIVAL

CODEFESTIVAL の前半 4 文字と後半 8 文字の間に半角スペースを 1 つ挿入すると、CODE FESTIVAL となります。

入力例 2

POSTGRADUATE

出力例 2

POST GRADUATE

入力例 3

ABCDEFGHIJKL

出力例 3

ABCD EFGHIJKL

Score : 100 points

Problem Statement

This contest is CODE FESTIVAL. However, Mr. Takahashi always writes it CODEFESTIVAL, omitting the single space between CODE and FESTIVAL.

So he has decided to make a program that puts the single space he omitted.

You are given a string s with 12 letters. Output the string putting a single space between the first 4 letters and last 8 letters in the string s.

Constraints

s contains exactly 12 letters.
All letters in s are uppercase English letters.

Input

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

Output

Print the string putting a single space between the first 4 letters and last 8 letters in the string s. Put a line break at the end.

Sample Input 1

CODEFESTIVAL

Sample Output 1

CODE FESTIVAL

Putting a single space between the first 4 letters and last 8 letters in CODEFESTIVAL makes it CODE FESTIVAL.

Sample Input 2

POSTGRADUATE

Sample Output 2

POST GRADUATE

Sample Input 3

ABCDEFGHIJKL

Sample Output 3

ABCD EFGHIJKL

B - Friendly Rabbits

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

N 匹のうさぎがいます。うさぎには 1 から N まで番号が振られています。

各 1≤i≤N について、うさぎ i はうさぎ a_i が好きです。ただし、自分自身が好きなうさぎはいません。すなわち、a_i≠i です。

うさぎ i とうさぎ j のペア (i，j) (i＜j) が次の条件を満たすとき、ペア (i，j) は仲良しであるといいます。

うさぎ i はうさぎ j が好きであり、うさぎ j はうさぎ i が好きである。

仲良しなペアの個数を求めてください。

制約

2≤N≤10^5
1≤a_i≤N
a_i≠i

入力

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

N
a_1 a_2 ... a_N

出力

仲良しなペアの個数を出力してください。

入力例 1

4
2 1 4 3

出力例 1

仲良しなペアは (1，2) と (3，4) の 2 個です。

入力例 2

3
2 3 1

出力例 2

仲良しなペアはありません。

入力例 3

5
5 5 5 5 1

出力例 3

仲良しなペアは (1，5) の 1 個です。

Score : 200 points

Problem Statement

There are N rabbits, numbered 1 through N.

The i-th (1≤i≤N) rabbit likes rabbit a_i. Note that no rabbit can like itself, that is, a_i≠i.

For a pair of rabbits i and j (i＜j), we call the pair (i，j) a friendly pair if the following condition is met.

Rabbit i likes rabbit j and rabbit j likes rabbit i.

Calculate the number of the friendly pairs.

Constraints

2≤N≤10^5
1≤a_i≤N
a_i≠i

Input

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

N
a_1 a_2 ... a_N

Output

Print the number of the friendly pairs.

Sample Input 1

4
2 1 4 3

Sample Output 1

There are two friendly pairs: (1，2) and (3，4).

Sample Input 2

3
2 3 1

Sample Output 2

There are no friendly pairs.

Sample Input 3

5
5 5 5 5 1

Sample Output 3

There is one friendly pair: (1，5).

C - Next Letter

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

高橋君は、英小文字のみからなる文字列 s を持っています。高橋君は s に対して、次の操作をちょうど K 回行います。

s から好きな位置の文字をひとつ選び、その文字を次のアルファベットへ変える。ただし、z の次のアルファベットは a であるとする。

例えば、aaz の 2 文字目を選んで操作を行うと、aaz → abz となります。続けて、abz の 3 文字目を選んで操作を行うと、abz → aba となります。

高橋君は、操作をちょうど K 回行った後の s を、辞書順でできるだけ小さくしたいと考えています。操作をちょうど K 回行った後の s のうち、辞書順で最小のものを求めてください。

制約

1≤|s|≤10^5 である。ただし、|s| は s の長さを表す。
s は英小文字のみからなる。
1≤K≤10^9

入力

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

s
K

出力

操作をちょうど K 回行った後の s のうち、辞書順で最小のものを出力せよ。

入力例 1

xyz
4

出力例 1

aya

例えば、xyz → yyz → zyz → ayz → aya と操作を行えばよいです。

入力例 2

a
25

出力例 2

操作はちょうど K 回行わなければなりません。

入力例 3

codefestival
100

出力例 3

aaaafeaaivap

Score : 400 points

Problem Statement

Mr. Takahashi has a string s consisting of lowercase English letters. He repeats the following operation on s exactly K times.

Choose an arbitrary letter on s and change that letter to the next alphabet. Note that the next letter of z is a.

For example, if you perform an operation for the second letter on aaz, aaz becomes abz. If you then perform an operation for the third letter on abz, abz becomes aba.

Mr. Takahashi wants to have the lexicographically smallest string after performing exactly K operations on s. Find the such string.

Constraints

1≤|s|≤10^5
All letters in s are lowercase English letters.
1≤K≤10^9

Input

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

s
K

Output

Print the lexicographically smallest string after performing exactly K operations on s.

Sample Input 1

xyz
4

Sample Output 1

aya

For example, you can perform the following operations: xyz, yyz, zyz, ayz, aya.

Sample Input 2

a
25

Sample Output 2

You have to perform exactly K operations.

Sample Input 3

codefestival
100

Sample Output 3

aaaafeaaivap

D - Grid and Integers

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

縦 R 行、横 C 列のマス目があります。上から r 行目、左から c 列目にあるマスを (r，c) と呼びます。

高橋君は N 箇所のマスに非負整数を書き込みました。具体的には、各 1≤i≤N について、マス (r_i，c_i) に非負整数 a_i を書き込みました。その後、高橋君は居眠りを始めました。

マス目を見つけた青木君は、残りすべてのマスに整数を書き込み、高橋君を驚かせようとしています。高橋君を驚かせるためには、マス目が次の条件を満たさなければなりません。

条件 1 : 各マスには非負整数が書き込まれている。
条件 2 : 縦 2 行、横 2 列の正方形をどこから取り出しても、(左上の整数) + (右下の整数) = (右上の整数) + (左下の整数) が常に成り立つ。

残りすべてのマスに書き込む整数を工夫することで、マス目が条件を満たすようにできるか判定してください。

制約

2≤R，C≤10^5
1≤N≤10^5
1≤r_i≤R
1≤c_i≤C
(r_i，c_i) はすべて相異なる。
a_i は整数である。
0≤a_i≤10^9

入力

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

R C
N
r_1 c_1 a_1
r_2 c_2 a_2
:
r_N c_N a_N

出力

残りすべてのマスに書き込む整数を工夫することで、マス目が条件を満たすようにできるならば、Yes を出力せよ。できないならば、No を出力せよ。

入力例 1

出力例 1

Yes

図のように整数を書き込めばよいです。

入力例 2

出力例 2

No

マス目には次の 2 個の正方形があります。

マス (1，1)，(1，2)，(2，1)，(2，2) からなる正方形
マス (1，2)，(1，3)，(2，2)，(2，3) からなる正方形

左側の正方形において条件 2 が成り立つためには、空きマスの整数は 40 でなければなりません。すると、右側の正方形において条件 2 が成り立たなくなります。

入力例 3

出力例 3

No

条件 2 が成り立つためには、空きマスの整数は -10 でなければなりません。すると、条件 1 が成り立たなくなります。

入力例 4

出力例 4

Yes

例えば、図のように整数を書き込めばよいです。

入力例 5

出力例 5

No

既にすべてのマスに整数が書き込まれており、条件 2 が成り立っていません。

Score : 800 points

Problem Statement

There is a grid with R rows and C columns. We call the cell in the r-th row and c-th column (r，c).

Mr. Takahashi wrote non-negative integers into N of the cells, that is, he wrote a non-negative integer a_i into (r_i，c_i) for each i (1≤i≤N). After that he fell asleep.

Mr. Aoki found the grid and tries to surprise Mr. Takahashi by writing integers into all remaining cells. The grid must meet the following conditions to really surprise Mr. Takahashi.

Condition 1: Each cell contains a non-negative integer.
Condition 2: For any 2×2 square formed by cells on the grid, the sum of the top left and bottom right integers must always equal to the sum of the top right and bottom left integers.

Determine whether it is possible to meet those conditions by properly writing integers into all remaining cells.

Constraints

2≤R，C≤10^5
1≤N≤10^5
1≤r_i≤R
1≤c_i≤C
(r_i，c_i) ≠ (r_j，c_j) (i≠j)
a_i is an integer.
0≤a_i≤10^9

Input

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

R C
N
r_1 c_1 a_1
r_2 c_2 a_2
:
r_N c_N a_N

Output

Print Yes if it is possible to meet the conditions by properly writing integers into all remaining cells. Otherwise, print No.

Sample Input 1

Sample Output 1

Yes

You can write integers as follows.

Sample Input 2

Sample Output 2

No

There are two 2×2 squares on the grid, formed by the following cells:

Cells (1，1), (1，2), (2，1) and (2，2)
Cells (1，2), (1，3), (2，2) and (2，3)

You have to write 40 into the empty cell to meet the condition on the left square, but then it does not satisfy the condition on the right square.

Sample Input 3

Sample Output 3

No

You have to write -10 into the empty cell to meet condition 2, but then it does not satisfy condition 1.

Sample Input 4

Sample Output 4

Yes

You can write integers as follows.

Sample Input 5

Sample Output 5

No

All cells already contain a integer and condition 2 is not satisfied.

E - LRU Puzzle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1200 点

問題文

配列が N 個あります。最初、どの配列も長さ M で、整数が (1，2，...，M) の順に並んでいます。

高橋君は、これら N 個の配列に対して、計 Q 回の操作を行うことにしました。 i (1≤i≤Q) 回目の操作では、次のような操作を行います。

N 個の配列のうち好きなものをひとつ選ぶ。その配列において、整数 a_i (1≤a_i≤M) を先頭へ移動する。例えば、a_i=2 のとき、配列 (5，4，3，2，1) を選んで操作を行うと、この配列は (2，5，4，3，1) へ変わる。

高橋君の目標は、計 Q 回の操作の後、N 個の配列がまったく同じになっていることです。計 Q 回の操作の後、N 個の配列がまったく同じになるようにできるか判定してください。

制約

2≤N≤10^5
2≤M≤10^5
1≤Q≤10^5
1≤a_i≤M

入力

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

N M
Q
a_1 a_2 ... a_Q

出力

計 Q 回の操作の後、N 個の配列がまったく同じになるようにできるならば、Yes を出力せよ。できないならば、No を出力せよ。

入力例 1

2 2
3
2 1 2

出力例 1

Yes

例えば、図のように操作を行えばよいです。

入力例 2

3 2
3
2 1 2

出力例 2

No

入力例 3

2 3
3
3 2 1

出力例 3

Yes

例えば、図のように操作を行えばよいです。

入力例 4

3 3
6
1 2 2 3 3 3

出力例 4

No

Score : 1200 points

Problem Statement

There are N arrays. The length of each array is M and initially each array contains integers (1，2，...，M) in this order.

Mr. Takahashi has decided to perform Q operations on those N arrays. For the i-th (1≤i≤Q) time, he performs the following operation.

Choose an arbitrary array from the N arrays and move the integer a_i (1≤a_i≤M) to the front of that array. For example, after performing the operation on a_i=2 and the array (5，4，3，2，1), this array becomes (2，5，4，3，1).

Mr. Takahashi wants to make N arrays exactly the same after performing the Q operations. Determine if it is possible or not.

Constraints

2≤N≤10^5
2≤M≤10^5
1≤Q≤10^5
1≤a_i≤M

Input

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

N M
Q
a_1 a_2 ... a_Q

Output

Print Yes if it is possible to make N arrays exactly the same after performing the Q operations. Otherwise, print No.

Sample Input 1

2 2
3
2 1 2

Sample Output 1

Yes

You can perform the operations as follows.

Sample Input 2

3 2
3
2 1 2

Sample Output 2

No

Sample Input 3

2 3
3
3 2 1

Sample Output 3

Yes

You can perform the operations as follows.

Sample Input 4

3 3
6
1 2 2 3 3 3

Sample Output 4

No