A - 2^N

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N が与えられます。2^N を出力してください。

制約

  • 0 \leq N \leq 30
  • N は整数である

入力

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

N

出力

答えを出力せよ。


入力例 1

3

出力例 1

8

2^3=8 です。


入力例 2

30

出力例 2

1073741824

Score : 100 points

Problem Statement

Given N, print 2^N.

Constraints

  • 0 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

3

Sample Output 1

8

We have 2^3=8.


Sample Input 2

30

Sample Output 2

1073741824
B - A Substring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる N 文字の文字列 S が与えられます。

S の先頭から A 文字、末尾から B 文字取り除いた N-A-B 文字の文字列を出力してください。

制約

  • 1\le N\le20
  • 0\le A
  • 0\le B
  • A+B\lt N
  • S は英小文字からなる N 文字の文字列
  • N,A,B はすべて整数

入力

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

N A B
S

出力

S の先頭から A 文字、末尾から B 文字取り除いた文字列を出力せよ。


入力例 1

7 1 3
atcoder

出力例 1

tco

atcoder の先頭から 1 文字、末尾から 3 文字取り除くと tco になります。


入力例 2

1 0 0
a

出力例 2

a

出力すべき文字列が S と等しい場合もあります。


入力例 3

20 4 8
abcdefghijklmnopqrst

出力例 3

efghijkl

Score : 100 points

Problem Statement

You are given an N-character string S consisting of lowercase English letters.

Output the string of N-A-B characters obtained by removing the first A characters and the last B characters from S.

Constraints

  • 1\le N\le20
  • 0\le A
  • 0\le B
  • A+B\lt N
  • S is a string of N characters consisting of lowercase English letters.
  • N, A, and B are all integers.

Input

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

N A B
S

Output

Output the string obtained by removing the first A characters and the last B characters from S.


Sample Input 1

7 1 3
atcoder

Sample Output 1

tco

Removing the first one character and the last three characters from atcoder gives tco.


Sample Input 2

1 0 0
a

Sample Output 2

a

The string to be output may be equal to S.


Sample Input 3

20 4 8
abcdefghijklmnopqrst

Sample Output 3

efghijkl
C - Commencement

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S が良い文字列であるとは、すべての 1 以上の整数 i について次の性質が成り立つことであるとします。

  • S にちょうど i 回現れる文字はちょうど 0 種類またはちょうど 2 種類ある

文字列 S が与えられるので、 S が良い文字列か判定してください。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

S が良い文字列ならば Yes を、そうでないならば No を出力せよ。


入力例 1

commencement

出力例 1

Yes

文字列 commencement にちょうど i 回現れる文字の種類数は以下のとおりです。

  • i=1: o, t の 2 種類
  • i=2: c, n の 2 種類
  • i=3: e, m の 2 種類
  • i\geq 4: 0 種類

よって、commencement は良い文字列の条件を満たします。


入力例 2

banana

出力例 2

No

文字列 banana にちょうど 1 回現れる文字は b の 1 種類だけであり、良い文字列の条件を満たしません。


入力例 3

ab

出力例 3

Yes

Score: 200 points

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

  • There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

  • S is a string of lowercase English letters with a length between 1 and 100, inclusive.

Input

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

S

Output

Print Yes if S is a good string, and No otherwise.


Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

  • i=1: two letters (o and t)
  • i=2: two letters (c and n)
  • i=3: two letters (e and m)
  • i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.


Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.


Sample Input 3

ab

Sample Output 3

Yes
D - AtCoder Janken 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の AtCoder ユーザーが集まり、 AtCoderじゃんけん2 を行います。i 人目のユーザー名は S_i 、レートは C_i です。

AtCoderじゃんけん2 は以下の手順で行われます。

  • それぞれのユーザーに、ユーザー名の辞書順に 0, 1, \dots ,N - 1 の番号を割り当てる。
  • N 人のレートの総和を T とする。番号 T \bmod N を割り当てられたユーザーが勝者となる。

勝者のユーザー名を出力してください。

辞書順とは?

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 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 N \leq 100
  • S_i は英小文字からなる長さ 3 以上 16 以下の文字列
  • S_1, S_2, \dots ,S_N は全て異なる
  • 1 \leq C_i \leq 4229
  • C_i は整数

入力

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

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

出力

答えを一行に出力せよ。


入力例 1

3
takahashi 2
aoki 6
snuke 5

出力例 1

snuke

3 人のレートの総和は 13 です。また、それぞれの名前を辞書順に並び替えると、 aoki snuke takahashi の順になるので aoki に番号 0 が、 snuke に 番号 1 が、 takahashi に番号 2 が割り当てられます。

13 \bmod 3 = 1 なので、番号 1 を割り当てられた snuke を出力します。


入力例 2

3
takahashi 2813
takahashixx 1086
takahashix 4229

出力例 2

takahashix

Score : 200 points

Problem Statement

N AtCoder users have gathered to play AtCoder RPS 2. The i-th user's name is S_i and their rating is C_i.

AtCoder RPS 2 is played as follows:

  • Assign the numbers 0, 1, \dots, N - 1 to the users in lexicographical order of their usernames.
  • Let T be the sum of the ratings of the N users. The user assigned the number T \bmod N is the winner.

Print the winner's username.

What is lexicographical order?

Lexicographical order, simply put, means "the order in which words appear in a dictionary." More precisely, the algorithm to determine the order of two distinct strings S and T consisting of lowercase English letters is as follows:

Here, "the i-th character of S" is denoted as S_i. If S is lexicographically smaller than T, we write S \lt T, and if S is larger, we write S \gt T.

  1. Let L be the length of the shorter string among S and T. Check if S_i and T_i match for i=1,2,\dots,L.
  2. If there exists 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, then S \lt T. Otherwise, S \gt T. The algorithm ends here.
  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, then S \lt T. If S is longer, then S \gt T. The algorithm ends here.

Constraints

  • 1 \leq N \leq 100
  • S_i is a string consisting of lowercase English letters with length between 3 and 16, inclusive.
  • S_1, S_2, \dots, S_N are all distinct.
  • 1 \leq C_i \leq 4229
  • C_i is an integer.

Input

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

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

Output

Print the answer on a single line.


Sample Input 1

3
takahashi 2
aoki 6
snuke 5

Sample Output 1

snuke

The sum of the ratings of the three users is 13. Sorting their names in lexicographical order yields aoki, snuke, takahashi, so aoki is assigned number 0, snuke is 1, and takahashi is 2.

Since 13 \bmod 3 = 1, print snuke, who is assigned number 1.


Sample Input 2

3
takahashi 2813
takahashixx 1086
takahashix 4229

Sample Output 2

takahashix
E - Make Isomorphic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N の N 個の頂点からなる単純無向グラフ G,H が与えられます。 G には M _ G 本の辺があり、i 本目 (1\leq i\leq M _ G) の辺は頂点 u _ i と頂点 v _ i を結んでいます。 H には M _ H 本の辺があり、i 本目 (1\leq i\leq M _ H) の辺は頂点 a _ i と頂点 b _ i を結んでいます。

あなたは、グラフ H に対して次の操作を 0 回以上の好きな回数繰り返すことができます。

  • 1\leq i\lt j\leq N を満たす整数の組 (i,j) をひとつ選ぶ。A _ {i,j} 円を支払って、頂点 i と頂点 j を結ぶ辺がなければ追加し、あれば取り除く。

G と H を同型にするために少なくとも何円支払う必要があるか求めてください。

単純無向グラフとは?

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

グラフの同型とは?

N 頂点のグラフ G と H が同型であるとは、ある (1,2,\ldots,N) の並べ替え (P _ 1,P _ 2,\ldots,P _ N) が存在して、どの 1\leq i\lt j\leq N に対しても

  • G に頂点 i, 頂点 j を結ぶ辺が存在するとき、かつそのときに限り H に頂点 P _ i, 頂点 P _ j を結ぶ辺が存在する
が成り立つことをいいます。

制約

  • 1\leq N\leq8
  • 0\leq M _ G\leq\dfrac{N(N-1)}2
  • 0\leq M _ H\leq\dfrac{N(N-1)}2
  • 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
  • (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
  • 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
  • (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
  • 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
  • 入力はすべて整数

入力

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

N
M _ G
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {M _ G} v _ {M _ G}
M _ H
a _ 1 b _ 1
a _ 2 b _ 2
\vdots
a _ {M _ H} b _ {M _ H}
A _ {1,2} A _ {1,3} \ldots A _ {1,N}
A _ {2,3} \ldots A _ {2,N}
\vdots
A _ {N-1,N}

出力

答えを出力せよ。


入力例 1

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

出力例 1

9

与えられたグラフはそれぞれ以下のようになります。

たとえば、H に対して次のような 4 つの操作を順に行うことで、9 円を支払ってG と H を同型にすることができます。

  • (i,j)=(1,3) として操作を行う。H には頂点 1 と頂点 3 を結ぶ辺があるので、1 円を支払ってこれを取り除く。
  • (i,j)=(2,5) として操作を行う。H には頂点 2 と頂点 5 を結ぶ辺はないので、2 円を支払ってこれを追加する。
  • (i,j)=(1,5) として操作を行う。H には頂点 1 と頂点 5 を結ぶ辺があるので、1 円を支払ってこれを取り除く。
  • (i,j)=(3,5) として操作を行う。H には頂点 3 と頂点 5 を結ぶ辺はないので、5 円を支払ってこれを追加する。

操作の結果、H は以下のようになります。

支払う金額を 8 円以下にして G と H を同型にすることはできないため、9 を出力してください。


入力例 2

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

出力例 2

3

たとえば、(i,j)=(2,3),(2,4),(3,4) とした 3 回の操作を行うことで G と H を同型にすることができます。


入力例 3

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

出力例 3

5

たとえば、(i,j)=(4,5) とした 1 回の操作を行うことで G と H を同型にすることができます。


入力例 4

2
0
0
371

出力例 4

0

G や H には辺が含まれていないこともあります。 また、一度も操作をする必要がないこともあります。


入力例 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

出力例 5

21214

Score : 300 points

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

  • Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multi-edges, where edges have no direction.

What does it mean for graphs to be isomorphic?

Two graphs G and H with N vertices are isomorphic if and only if there exists a permutation (P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) such that for all 1\leq i\lt j\leq N:

  • an edge exists between vertices i and j in G if and only if an edge exists between vertices P_i and P_j in H.

Constraints

  • 1\leq N\leq8
  • 0\leq M _ G\leq\dfrac{N(N-1)}2
  • 0\leq M _ H\leq\dfrac{N(N-1)}2
  • 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
  • (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
  • 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
  • (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
  • 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
  • All input values are integers.

Input

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

N
M _ G
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {M _ G} v _ {M _ G}
M _ H
a _ 1 b _ 1
a _ 2 b _ 2
\vdots
a _ {M _ H} b _ {M _ H}
A _ {1,2} A _ {1,3} \ldots A _ {1,N}
A _ {2,3} \ldots A _ {2,N}
\vdots
A _ {N-1,N}

Output

Print the answer.


Sample Input 1

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

  • Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
  • Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
  • Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
  • Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.


Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.


Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.


Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.


Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214