問題文

CODE THANKS FESTIVAL 2017 では、問題を 8 問解きます。
コンテスト参加者であるイルカの i(1≦i≦8) 問目の解答状況が t_i で与えられます。

t_i>0 の場合には、i 問目の問題をコンテスト開始 t_i 秒後に正解しています。
一方で、t_i = 0 の場合には、まだ正解していません。

コンテスト参加者の時間ペナルティは、最後に正解した問題に対する t_i に等しいです。
また、1 問も正解していない場合の時間ペナルティは 0 とします。

イルカの時間ペナルティを求めてください。

制約

• 0≦t_i≦10800 (1≦i≦8)
• t_i は整数である。

入力例 1

240
600
1800
3600
4800
7200
10000
0

出力例 1

10000

イルカは 8 問目を除いた 7 つの問題に正解しており、最後に正解したのは 7 問目であるため、t_7 = 10000 を出力します。

入力例 2

10400
10300
10100
9800
9500
8500
7000
5000

出力例 2

10400

逆順に問題を解いている場合もあります。

入力例 3

0
0
0
0
0
0
0
0

出力例 3

0

問題文

英小文字からなる文字列 S が与えられます。
S の後ろに英小文字からなる任意の文字列 T (空文字列も含む)を連結することで、回文にしたいです。
条件を満たす文字列 T のうち、T の最小の長さを求めてください。

制約

• 1≦|S|≦50 (|S| は文字列 S の長さ)
• 文字列 S は英小文字から成る。

入力例 1

abcde

出力例 1

4

T="dcba" とすると、文字列 S と 文字列 T を順番に連結した文字列は回文になります。
この文字列 T は条件を満たす中で最小の長さであるため、答えは 4 です。

入力例 2

level

出力例 2

0

文字列 S は回文であるため、文字列 T は空文字列でも条件を満たします。
空文字列の長さは 0 であるため、答えは 0 です。

入力例 3

codethanksfestival

出力例 3

17

入力例 4

abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcb

出力例 4

1

問題文

工場にプレゼントを作る機械が N 台あります。i(1≦i≦N) 番目の機械は、最初 a_i 秒でプレゼントを 1 個作れます。
しかし、ある機械でプレゼントを 1 個作るたびにその機械のみが劣化して、プレゼントを 1 個作るのにかかる時間が b_i 秒増えます。
したがって、i(1≦i≦N) 番目の機械で s_i 個目のプレゼントを作るのに　a_i + (s_i-1)×b_i 秒かかります。
また、工場に供給される電力が少ないため、複数の機械を同時に動かすことはできません。

イルカはプレゼント K 個をできる限り短い時間で製造したいです。
プレゼントの製造にかかる最小の合計時間を求めてください。

制約

• 1≦N≦10^5
• 1≦K≦10^5
• 1≦a_i≦10^9
• 0≦b_i≦10^9
• 入力は全て整数である。

入力例 1

3 3
1 3
2 0
3 4

出力例 1

5

工場にある機械を以下の回数で動かしたとき、5 秒で 3 個のプレゼントを作ることができます。

• 1 番目の機械: 1 回
• 2 番目の機械: 2 回
• 3 番目の機械: 0 回

入力例 2

10 100000
22 59
26 60
72 72
47 3
97 16
75 41
82 77
17 97
32 32
28 7

出力例 2

7521307799

オーバーフローに注意してください。

入力例 3

1 100000
1000000000 1000000000

出力例 3

5000050000000000000

問題文

あなたはバスツアーを計画しています。

バスツアーの参加者は必ず 1 グループ N 人で申し込みます。運転手を除いた各バスの定員は必ず M 人です。
このバスツアーは、全ての参加者がバスに乗り切れるようなバスの最小台数で行います。
同じグループに属する人が必ずしも同じバスに乗り込む必要はありません。

このバスツアーに参加するグループ数には上限がないため、申し込みを締め切るまでバスツアーに参加するグループ数は分かりません。
したがって、参加者の申し込み具合によってはバスに空席が生じてしまいます。
最大で何席の空席ができるでしょうか?

制約

• 1≦N≦10^9
• 1≦M≦10^9
• N と M は整数である。

入力例 1

5 4

出力例 1

3

申し込みが 1 グループだった場合、参加者 5 人に対して定員 4 名のバス 2 台で バスツアーを行うため、3 席の空席が生じます。

入力例 2

1000000 10

出力例 2

0

申し込みグループ数に関わらず、常にバスが満員である場合もあります。

入力例 3

500000000 1000000000

出力例 3

500000000

問題文

これはインタラクティブな問題です。

イルカは街中でコインが入った N 個の袋を見つけました。
i(1≦i≦N) 番目の袋の中に重さ w_i グラムのコインが 10000 枚入っています。

ここで、イルカは街で偽物コインが多く流通していることを思い出しました。
N 個の袋のうち、いくつかの袋は偽物コインだけが入った袋かもしれません。
イルカは本物コインの袋を探そうとしています。

これらのコインの見た目は全く同じですが、本物コインと偽物コインでその重さが異なります。
本物コインの重さは 9 グラム、または 11 グラムであり、偽物コインの重さは 8 グラム、10 グラム、または 12 グラムであることが知られています。
イルカは袋に入っているコインの重さ w_i を全く知りません。

イルカは友達のシャチから、はかりを借りることにしました。
はかりを利用して、コインの計測は以下の手順で行います。

• それぞれの袋について、整数 0≦s_i≦10000 (1≦i≦N) を決めます。
• i 番目の袋から s_i 枚のコインを取り出して、はかりに乗せます。
• その後に計測を行い、はかりの上に乗せたコインの重さの合計を知ることができます。
• 最後に、はかりに乗せたコインを元の袋に戻します。

しかし、シャチはとても忙しいのでイルカは 高々 10 回のコイン計測しかできません。
どの袋に本物コインが含まれているかを判定してください。

制約

• 1≦N≦50
• 8≦w_i≦12
• N と w_i は全て整数

入出力

最初に、標準入力から N が以下の形式で与えられる:

N 

次に、あなたはクエリを質問して、コインの計測を行う。
このクエリは高々 10 回まで出力することができる。
各クエリでは、はかりの上に乗せるコインの枚数を以下の形式で標準出力へ出力しなければならない:

? s_1 s_2 … s_N

ここで s_i は、 はかりの上に乗せる i 番目の袋のコインの枚数であり、0 以上 10000 以下の整数でなければならない。

その後、クエリの答えが標準入力から以下の形式で与えられる:

ans

ここで ans は非負の整数であり、はかりの計測結果が ans グラムであることを表す。

最後に、答えを以下の形式で出力しなければならない：

! a_1 a_2 … a_N

ここで a_i は i 番目の袋に入っているコインが本物コインなら 1、偽物コインなら 0 でなければならない。
なお、答えの出力はコインの計測を行う質問クエリの回数制限に含まれない。

ジャッジ

• 出力の最後に改行を含めて出力しなければならない。そのあと、標準出力を flush しなければならない。 そうでないときは TLE の可能性がある。
• 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
• 出力の答えが間違っている場合の挙動は定義されていない (WAとは限らない)。

サンプル

このサンプルでは N = 5, w_1 = 8, w_2 = 9, w_3 = 10, w_4 = 11, w_5 = 12 で、答えは 0 1 0 1 0 である。

問題文

N 個の正の整数が与えられ、i(1≦i≦N) 番目の正の整数は a_i です。
N 個の整数のうち 0 個以上を選んで、選んだ全ての整数のビットごとの排他的論理和を計算します。
計算結果が K となるような整数の選び方の個数を 10^9+7 で割った余りを求めてください。
ただし、0 個選んだときのビットごとの排他的論理和は 0 とします。

制約

• 1≦N≦10^5
• 0≦K≦10^5
• 1≦a_i (1≦i≦N)
• a_1 + … + a_N≦10^5
• 入力は全て整数である。

入力例 1

4 3
1
2
1
2

出力例 1

4

選んだ全ての整数についてビットごとの排他的論理和が K = 3 となるような選び方は以下の 4 通りです。

• \{a_1,a_2\}
• \{a_1,a_4\}
• \{a_2,a_3\}
• \{a_3,a_4\}

入力例 2

4 0
1
1
1
1

出力例 2

8

選んだ全ての整数についてビットごとの排他的論理和が K = 0 となるような選び方は以下の 8 通りです。

• \{\} (選んだ整数が 0 個の場合)
• \{a_1,a_2\}
• \{a_1,a_3\}
• \{a_1,a_4\}
• \{a_2,a_3\}
• \{a_2,a_4\}
• \{a_3,a_4\}
• \{a_1,a_2,a_3,a_4\}

入力例 3

13 3
2
7
1
8
2
8
1
8
2
8
4
5
9

出力例 3

512

問題文

イルカの手元には 1 から N までの番号が付いた N 種類の薬品があります。
また、薬品の取り扱いについて書かれたリストが手元にあります。
このリストには M 個の項目があり、リストの上から i(1≦i≦M) 番目の項目には「番号 a_i と 番号 b_i の薬品を混合すると毒が発生する。」と書いてあります。

イルカは、リストに基づいて毒が発生しないように、できる限り多くの種類の薬品を混合したいと考えています。
イルカは最大で何種類の薬品を混合できますか?

制約

• 1≦N≦40
• 0≦M≦N(N-1)/2
• 1≦a_i<b_i≦N
• a_i≠a_j または b_i≠b_j (1≦i<j≦M)
• 入力は全て整数である。

入力例 1

4 1
1 2

出力例 1

3

番号 1 と番号 2 の薬品を混合すると毒が発生するので、全ての薬品を混合することはできません。
一方で、番号 1 と番号 3 と番号 4 の薬品を混合した場合には、毒が発生しません。
したがって、最大 3 種類の薬品が使えるので、3 と出力します。

入力例 2

1 0

出力例 2

1

入力例 3

20 16
1 8
1 16
2 19
3 5
3 10
5 7
5 13
6 9
7 8
7 11
7 14
7 15
8 12
9 12
9 17
15 20

出力例 3

12

問題文

最初、\{1\},\{2\},…,\{N\} という N 個の集合が与えられます。
この後に、集合を併合する操作が M 回行われます。
時刻 i(1≦i≦M) 回目の操作では 要素 a_i を持つ集合と 要素 b_i を持つ集合を併合します。
ただし、要素 a_i と要素 b_i が既に同じ集合に属している場合には何も起こりません。

次に、Q 個の質問クエリが与えられ、j(1≦j≦Q) 番目の質問クエリの内容は以下の通りです。

• ｢要素 x_j と 要素 y_j が同じ集合に併合されるのは何回目の操作後ですか?｣

M 回の操作後に 要素 x_j と 要素 y_j が 同じ集合に属さない場合には、-1 を出力してください。
そうでない場合、K(1≦K≦M) 回目の操作後に要素 x_j と 要素 y_j が同じ集合に属するので、最小の K を出力してください。

制約

• 2≦N≦10^5
• 0≦M≦10^5
• 1≦a_i,b_i≦N
• a_i≠b_i
• 1≦Q≦10^5
• 1≦x_j,y_j≦N
• x_j≠y_j
• 入力は全て整数である。

入力例 1

7 5
1 2
3 4
2 1
2 3
4 1
5
1 2
3 4
1 4
2 3
6 7

出力例 1

1
2
4
4
-1

まず、7 つの集合 \{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\} があります。
この後に、集合を併合する操作が 5 回あり、各操作の後の集合の状態は以下の通りです。

• 1 回目の操作の後 \{1,2\},\{3\},\{4\},\{5\},\{6\},\{7\}
• 2 回目の操作の後 \{1,2\},\{3,4\},\{5\},\{6\},\{7\}
• 3 回目の操作の後 \{1,2\},\{3,4\},\{5\},\{6\},\{7\}
• 4 回目の操作の後 \{1,2,3,4\},\{5\},\{6\},\{7\}
• 5 回目の操作の後 \{1,2,3,4\},\{5\},\{6\},\{7\}

入力例 2

7 6
1 2
1 3
1 4
1 5
1 6
1 7
3
1 3
4 5
6 7

出力例 2

2
4
6

入力例 3

10 0
5
1 2
4 3
5 6
8 7
9 10

出力例 3

-1
-1
-1
-1
-1