CODE FESTIVAL 2017 qual B

A - XXFESTIVAL

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

りんごさんは、とある祭りに参加しようとしています。

その祭りの名称が FESTIVAL で終わる文字列 S として入力に与えられるので、りんごさんが何の祭りに参加しようしているのかを出力して下さい。

ただし、s の祭りの名称は s の末尾に FESTIVAL を 1 つだけ追加した文字列であるとします。例えば CODEFESTIVAL は CODE の祭りです。

制約

9 \leq |S| \leq 50
S は大文字アルファベットのみからなる
S は FESTIVAL で終わる

入力

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

出力

りんごさんが何の祭りに参加しようしているのかを出力せよ。

入力例 1

CODEFESTIVAL

出力例 1

CODE

問題文中の例の通りです。

入力例 2

CODEFESTIVALFESTIVAL

出力例 2

CODEFESTIVAL

CODEFESTIVAL の末尾に FESTIVAL を追加した文字列であるので、これは CODEFESTIVAL の祭りとなります。

入力例 3

YAKINIKUFESTIVAL

出力例 3

YAKINIKU

Score : 100 points

Problem Statement

Rng is going to a festival.

The name of the festival is given to you as a string S, which ends with FESTIVAL, from input. Answer the question: "Rng is going to a festival of what?" Output the answer.

Here, assume that the name of "a festival of s" is a string obtained by appending FESTIVAL to the end of s. For example, CODEFESTIVAL is a festival of CODE.

Constraints

9 \leq |S| \leq 50
S consists of uppercase English letters.
S ends with FESTIVAL.

Input

Input is given from Standard Input in the following format:

Output

Print the answer to the question: "Rng is going to a festival of what?"

Sample Input 1

CODEFESTIVAL

Sample Output 1

CODE

This is the same as the example in the statement.

Sample Input 2

CODEFESTIVALFESTIVAL

Sample Output 2

CODEFESTIVAL

This string is obtained by appending FESTIVAL to the end of CODEFESTIVAL, so it is a festival of CODEFESTIVAL.

Sample Input 3

YAKINIKUFESTIVAL

Sample Output 3

YAKINIKU

B - Problem Set

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

りんごさんは CODEFESTIVAL の予選の問題セットを組もうとしています。

りんごさんは N 個の問題案を持っており、i 個目の問題案の難易度は D_i です。

予選の問題セットには M 問の問題が必要で、i 問目の問題に使う問題案の難易度はちょうど T_i でなければなりません。ただし、1 つの問題案を複数の問題に使うことはできません。

りんごさんが新しく問題案を作ることなく予選の問題セットを完成させることができるかを判定して下さい。

制約

1 \leq N \leq 200,000
1 \leq D_i \leq 10^9
1 \leq M \leq 200,000
1 \leq T_i \leq 10^9
入力される値は全て整数である

部分点

N \leq 100 かつ M \leq 100 を満たすデータセットに正解した場合は、100 点が与えられる。

入力

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

N
D_1 D_2 ... D_N
M
T_1 T_2 ... T_M

出力

りんごさんが新しく問題案を作ることなく予選の問題セットを完成させることができる場合は YES、できない場合は NO を出力せよ。

入力例 1

出力例 1

YES

入力例 2

7
100 200 500 700 1200 1600 2000
6
100 200 500 700 1600 1600

出力例 2

NO

この入力では、難易度 1600 の問題案が足りていません。

入力例 3

1
800
5
100 100 100 100 100

出力例 3

NO

入力例 4

15
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
9
5 4 3 2 1 2 3 4 5

出力例 4

YES

Score : 200 points

Problem Statement

Rng is preparing a problem set for a qualification round of CODEFESTIVAL.

He has N candidates of problems. The difficulty of the i-th candidate is D_i.

There must be M problems in the problem set, and the difficulty of the i-th problem must be T_i. Here, one candidate of a problem cannot be used as multiple problems.

Determine whether Rng can complete the problem set without creating new candidates of problems.

Constraints

1 \leq N \leq 200,000
1 \leq D_i \leq 10^9
1 \leq M \leq 200,000
1 \leq T_i \leq 10^9
All numbers in the input are integers.

Partial Score

100 points will be awarded for passing the test set satisfying N \leq 100 and M \leq 100.

Input

Input is given from Standard Input in the following format:

N
D_1 D_2 ... D_N
M
T_1 T_2 ... T_M

Output

Print YES if Rng can complete the problem set without creating new candidates of problems; print NO if he cannot.

Sample Input 1

Sample Output 1

YES

Sample Input 2

7
100 200 500 700 1200 1600 2000
6
100 200 500 700 1600 1600

Sample Output 2

NO

Not enough 1600s.

Sample Input 3

1
800
5
100 100 100 100 100

Sample Output 3

NO

Sample Input 4

15
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
9
5 4 3 2 1 2 3 4 5

Sample Output 4

YES

C - 3 Steps

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 500 点

問題文

りんごさんは N 頂点の連結な無向グラフを持っています。このグラフにはすでに M 本の辺があり、i 本目の辺は頂点 A_i と頂点 B_i を繋いでいます。

りんごさんは以下の操作を行うことで、辺を追加しようと思っています。

操作：頂点 u から辺をちょうど 3 本辿ることによって頂点 v に辿り着けるような u,v (u \neq v) をとり、頂点 u と頂点 v の間に辺を追加する。ただし、すでに頂点 u と頂点 v の間に辺が存在する場合は辺を追加することはできない。

りんごさんが追加できる辺の本数の最大値を求めて下さい。

制約

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i,B_i \leq N
多重辺や自己ループは存在しない
与えられるグラフは連結である

入力

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

N M
A_1 B_1
A_2 B_2
:
A_M B_M

出力

追加できる辺の本数の最大値を出力せよ。

入力例 1

出力例 1

下の図のように辺を追加していくと 4 本の辺を追加することができ、これ以上辺を追加することはできません。

入力例 2

出力例 2

例えば、以下のような順番で辺を追加することによって 5 本の辺を追加することができます。

頂点 5 と頂点 3 の間に辺を追加する。
頂点 5 と頂点 2 の間に辺を追加する。
頂点 4 と頂点 1 の間に辺を追加する。
頂点 4 と頂点 2 の間に辺を追加する。
頂点 4 と頂点 3 の間に辺を追加する。

Score : 500 points

Problem Statement

Rng has a connected undirected graph with N vertices. Currently, there are M edges in the graph, and the i-th edge connects Vertices A_i and B_i.

Rng will add new edges to the graph by repeating the following operation:

Operation: Choose u and v (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.

Find the maximum possible number of edges that can be added.

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i,B_i \leq N
The graph has no self-loops or multiple edges.
The graph is connected.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Find the maximum possible number of edges that can be added.

Sample Input 1

Sample Output 1

If we add edges as shown below, four edges can be added, and no more.

Sample Input 2

Sample Output 2

Five edges can be added, for example, as follows:

Add an edge connecting Vertex 5 and Vertex 3.
Add an edge connecting Vertex 5 and Vertex 2.
Add an edge connecting Vertex 4 and Vertex 1.
Add an edge connecting Vertex 4 and Vertex 2.
Add an edge connecting Vertex 4 and Vertex 3.

D - 101 to 010

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 700 点

問題文

N 個のセルが一列に並んでいます。何個かのセルはトークンを含んでいるかもしれません。あなたは、 0 と 1 からなる文字列 s が与えられます。 s の i 文字目が 1 のとき、(左から) i 番目のセルはトークンを一個含んでいます。そうでないとき、トークンを含んでいません。

すぬけ君は、以下の操作をできる限り行いたいです。各操作では、三個の連続するセルを選びます。セルを左から X, Y, Z とします。操作を行うためには、 X と Z の両方がトークンを含み、 Y はトークンを含んでいてはなりません。次に、すぬけ君はこれらの二個のトークンを取り除き、新しいトークンを Y に一個置きます。

最適な操作の方法をしたとき、すぬけ君は何回操作を行えますか？

制約

1 \leq N \leq 500,000
|s| = N
s の各文字は 0 または 1 である。

入力

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

N
s

出力

答えを出力せよ。

入力例 1

7
1010101

出力例 1

例えば、以下の方法で操作を二回行うことができます:

最後の三個のセルに対し操作を行う。トークンを表す文字列は 1010010 となる。
最初の三個のセルに対し操作を行う。トークンを表す文字列は 0100010 となる。

操作の順番が重要であることに注意してください。たとえば、最初に中央の三個のセルを選ぶと、それ以上操作を行えなくなります。

入力例 2

50
10101000010011011110001001111110000101010111100110

出力例 2

Score : 700 points

Problem Statement

N cells are arranged in a row. Some of them may contain tokens. You are given a string s that consists of 0s and 1s. If the i-th character of s is 1, the i-th cell (from left) contains a token. Otherwise, it doesn't contain a token.

Snuke wants to perform the following operation as many times as possible. In each operation, he chooses three consecutive cells. Let's call the cells X, Y, Z from left to right. In order for the operation to be valid, both X and Z must contain tokens and Y must not contain a token. Then, he removes these two tokens and puts a new token on Y.

How many operations can he perform if he performs operations in the optimal way?

Constraints

1 \leq N \leq 500,000
|s| = N
Each character in s is either 0 or 1.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the answer.

Sample Input 1

7
1010101

Sample Output 1

For example, he can perform two operations in the following way:

Perform an operation on the last three cells. Now the string that represents tokens becomes 1010010.
Perform an operation on the first three cells. Now the string that represents tokens becomes 0100010.

Note that the choice of operations matters. For example, if he chooses three cells in the middle first, he can perform no more operations.

Sample Input 2

50
10101000010011011110001001111110000101010111100110

Sample Output 2

E - Popping Balls

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1600 点

問題文

A + B 個のボールが一列に並べられています。左から A 個のボールは赤で、右から B 個のボールは青で塗られています。

あなたは、以下の操作を行います:

最初に、 1 \leq s, t \leq A + B を満たす整数 s, t を選びます。
次に、以下のステップを A + B 回繰り返します: 各ステップでは、あなたは左から 1 番目または s 番目 (存在すれば) または t 番目 (存在すれば、すべて 1-based) のボールを選び、すぬけ君にあげます。

すぬけ君に何通りの方法でボールをあげることができるでしょうか？ Mod 10^9 + 7 で求めてください。

ここで、ある整数 k に対し、 k 番目にすぬけ君にあげるボールの色が異なるとき、二つの方法は異なるとみなします。特に、 s, t の選択は関係ありません。また、同じ色の二つのボールは区別しません。

制約

1 \leq A, B \leq 2000

入力

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

A B

出力

答えを出力せよ。

入力例 1

3 3

出力例 1

3 個の赤いボールと 3 個の青いボールをあげる方法は 20 通りあります。それらのすべての方法が可能であることが分かります。

以下は操作の例です (r は赤を、 b は青をあらわします):

s = 3, t = 4 を選ぶ。
最初、列は rrrbbb となっています。
3 番目のボール (r) を取り除きすぬけ君にあげます。列は rrbbb となっています。
4 番目のボール (b) を取り除きすぬけ君にあげます。列は rrbb となっています。
1 番目のボール (r) を取り除きすぬけ君にあげます。列は rbb となっています。
3 番目のボール (b) を取り除きすぬけ君にあげます。列は rb となっています。
1 番目のボール (r) を取り除きすぬけ君にあげます。列は b となっています。
1 番目のボール (b) を取り除きすぬけ君にあげます。列は空になります。

この方法では、すぬけ君は rbrbrb の順でボールを受け取ります。

入力例 2

4 4

出力例 2

4 個の赤いボールと 4 個の青いボールをあげる方法は 70 通りあります。そのうち、 bbrrbrbr, brbrbrbr, brrbbrbr だけが不可能です。

入力例 3

7 9

出力例 3

入力例 4

1987 1789

出力例 4

456315553

Score : 1600 points

Problem Statement

A + B balls are arranged in a row. The leftmost A balls are colored red, and the rightmost B balls are colored blue.

You perform the following operation:

First, you choose two integers s, t such that 1 \leq s, t \leq A + B.
Then, you repeat the following step A + B times: In each step, you remove the first ball or the s-th ball (if it exists) or the t-th ball (if it exists, all indices are 1-based) from left in the row, and give it to Snuke.

In how many ways can you give the balls to Snuke? Compute the answer modulo 10^9 + 7.

Here, we consider two ways to be different if for some k, the k-th ball given to Snuke has different colors. In particular, the choice of s, t doesn't matter. Also, we don't distinguish two balls of the same color.

Constraints

1 \leq A, B \leq 2000

Input

Input is given from Standard Input in the following format:

A B

Output

Print the answer.

Sample Input 1

3 3

Sample Output 1

There are 20 ways to give 3 red balls and 3 blue balls. It turns out that all of them are possible.

Here is an example of the operation (r stands for red, b stands for blue):

You choose s = 3, t = 4.
Initially, the row looks like rrrbbb.
You remove 3rd ball (r) and give it to Snuke. Now the row looks like rrbbb.
You remove 4th ball (b) and give it to Snuke. Now the row looks like rrbb.
You remove 1st ball (r) and give it to Snuke. Now the row looks like rbb.
You remove 3rd ball (b) and give it to Snuke. Now the row looks like rb.
You remove 1st ball (r) and give it to Snuke. Now the row looks like b.
You remove 1st ball (b) and give it to Snuke. Now the row is empty.

This way, Snuke receives balls in the order rbrbrb.

Sample Input 2

4 4

Sample Output 2

There are 70 ways to give 4 red balls and 4 blue balls. Among them, only bbrrbrbr, brbrbrbr, and brrbbrbr are impossible.

Sample Input 3

7 9

Sample Output 3

Sample Input 4

1987 1789

Sample Output 4

456315553

F - Largest Smallest Cyclic Shift

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1600 点

問題文

文字列 S に対し、 f(S) を S の巡回シフトのうち辞書順最小のものとします。たとえば、 S = babca のとき、 S の巡回シフト (babca, abcab, bcaba, cabab, ababc) のうち最小の ababc が f(S) となります。

あなたは、三個の整数 X, Y, Z が与えられます。あなたは、 a をちょうど X 個、b をちょうど Y 個、c をちょうど Z 個含む文字列 T を構成したいです。そのような文字列が複数存在する場合は、 f(T) を辞書順で最大化したいです。

f(T) の辞書順での最大値を求めてください。

制約

1 \leq X + Y + Z \leq 50
X, Y, Z は非負整数である。

入力

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

X Y Z

出力

答えを出力せよ。

入力例 1

2 2 0

出力例 1

abab

T は a 二個と b 二個からならなければなりません。

T = aabb のとき f(T) = aabb.
T = abab のとき f(T) = abab.
T = abba のとき f(T) = aabb.
T = baab のとき f(T) = aabb.
T = baba のとき f(T) = abab.
T = bbaa のとき f(T) = aabb.

となるので、 f(T) の最大値は abab です。

入力例 2

1 1 1

出力例 2

acb

Score : 1600 points

Problem Statement

For a string S, let f(S) be the lexicographically smallest cyclic shift of S. For example, if S = babca, f(S) = ababc because this is the smallest among all cyclic shifts (babca, abcab, bcaba, cabab, ababc).

You are given three integers X, Y, and Z. You want to construct a string T that consists of exactly X as, exactly Y bs, and exactly Z cs. If there are multiple such strings, you want to choose one that maximizes f(T) lexicographically.

Compute the lexicographically largest possible value of f(T).

Constraints

1 \leq X + Y + Z \leq 50
X, Y, Z are non-negative integers.

Input

Input is given from Standard Input in the following format:

X Y Z

Output

Print the answer.

Sample Input 1

2 2 0

Sample Output 1

abab

T must consist of two as and two bs.

If T = aabb, f(T) = aabb.
If T = abab, f(T) = abab.
If T = abba, f(T) = aabb.
If T = baab, f(T) = aabb.
If T = baba, f(T) = abab.
If T = bbaa, f(T) = aabb.

Thus, the largest possible f(T) is abab.

Sample Input 2

1 1 1

Sample Output 2

acb