C - Splitting Pile

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

すぬけくんとアライグマは N 枚のカードの山を作りました。カードの山の上から i 番目のカードには整数 a_i が書かれています。

N 枚のカードを分け合うことにしました。 すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。 このとき、すぬけくんもアライグマも 1 枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ x,y として、|x-y| を最小化したいです。 |x-y| としてありうる値の最小値を求めなさい。

制約

  • 2 \leq N \leq 2 \times 10^5
  • -10^{9} \leq a_i \leq 10^{9}
  • a_i は整数

入力

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

N
a_1 a_2 ... a_{N}

出力

答えを出力せよ。

入力例 1

6
1 2 3 4 5 6

出力例 1

1

すぬけくんが上から 4 枚のカードを、アライグマが残った 2 枚のカードを取ったとき、x=10,y=11 となって、|x-y| は 1 となり、これが最小です。

入力例 2

2
10 -10

出力例 2

20

すぬけくんは上から 1 枚のカードを、アライグマは残った 1 枚を取るしかありえません。このとき x=10,y=-10 となって、|x-y| は 20 となります。

Score : 300 points

Problem Statement

Snuke and Raccoon have a heap of N cards. The i-th card from the top has the integer a_i written on it.

They will share these cards. First, Snuke will take some number of cards from the top of the heap, then Raccoon will take all the remaining cards. Here, both Snuke and Raccoon have to take at least one card.

Let the sum of the integers on Snuke's cards and Raccoon's cards be x and y, respectively. They would like to minimize |x-y|. Find the minimum possible value of |x-y|.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • -10^{9} \leq a_i \leq 10^{9}
  • a_i is an integer.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Print the answer.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

1

If Snuke takes four cards from the top, and Raccoon takes the remaining two cards, x=10, y=11, and thus |x-y|=1. This is the minimum possible value.

Sample Input 2

2
10 -10

Sample Output 2

20

Snuke can only take one card from the top, and Raccoon can only take the remaining one card. In this case, x=10, y=-10, and thus |x-y|=20.
D - Fennec VS. Snuke

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

フェネックとすぬけくんがボードゲームで遊んでいます。

このボードゲームには 1 番から N 番までの番号がついた N 個のマスと、マスどうしをつなぐ N-1 本の道が存在しています。 a_i 番のマスと b_i 番のマスは i 番目の道を介して隣り合っています。どの 2 つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。

はじめに 1 番のマスは黒く、N 番のマスは白く塗られています。その他のマスはまだ色が塗られていません。 先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。 自分の手番において、2 人はそれぞれ以下のような行動を行います。

  • フェネック：黒く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 黒く 塗る。
  • すぬけくん：白く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 白く 塗る。

手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq a_i, b_i \leq N
  • 与えられるグラフは木

入力

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

N
a_1 b_1
:
a_{N-1} b_{N-1}

出力

勝者がフェネックならば Fennec と、すぬけくんならば Snuke と出力せよ。

入力例 1

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

出力例 1

Fennec

例えばフェネックがはじめに 2 番のマスを黒く塗ると、すぬけくんがどのようにマスを白く塗ったとしてもフェネックが勝者となります。

入力例 2

4
1 4
4 2
2 3

出力例 2

Snuke

Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.

Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored. Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell. More specifically, each player performs the following action in her/his turn:

  • Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
  • Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.

A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq a_i, b_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

Sample Input 1

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

Sample Output 1

Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke
E - Awkward Response

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

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

すぬけくんはお気に入りの正の整数 N を持っています。あなたは 「n はお気に入りの正の整数か？」と最大 64 回すぬけくんに質問することができます。 N を特定してください。

すぬけくんはひねくれ者なので「n はお気に入りの正の整数か？」と質問されたとき、n が以下の 2 つの条件のどちらかを満たすとき Yes と、それ以外のとき No と答えます。

  • n \leq N かつ str(n) \leq str(N)を満たす
  • n > N かつ str(n) > str(N) を満たす

ここで、str(x) は正の整数 x を十進表記(先頭に 0 をつけない)の文字列として表したものです。例えば str(123) = 123，str(2000) = 2000 です。 なお、この問題において文字列同士は辞書順で比較されます。例えば 11111 < 123，123456789 < 9 が成立します。

制約

  • 1 \leq N \leq 10^{9}

入出力

各質問は、標準出力に以下の形式で出力せよ：

? n

ここで n は 1 以上 10^{18} 以下の整数でなければならない。

次に、質問の答えが標準入力から以下の形式で与えられる：

ans

ここで ans は Y または N である．Y ならば、質問の答えが Yes であることを、N ならば No であることを示す。

最後に、答えを以下の形式で出力せよ：

! n

ここで n=N でなくてはならない。

ジャッジ

  • 出力のあと、標準出力を flush せよ。従わない場合 TLE の可能性がある。
  • 答えを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
  • 出力の答えが間違っている場合の挙動は定義されていない(WA とは限らない)。

入出力例

これは N=123 のときの入出力例です。

Input Output
? 1
Y
? 32
N
? 1010
N
? 999
Y
! 123
  • 1 \leq 123 かつ str(1) \leq str(123) なので答えは Yes です
  • 32 \leq 123 ですが、str(32) > str(123) なので答えは No です
  • 1010 > 123 ですが、str(1010) \leq str(123) なので答えは No です
  • 999 \geq 123 かつ str(999) > str(123) なので答えは Yes です
  • N は 123 であると 4 回の質問で回答できたため正解となります

Score : 800 points

Problem Statement

This is an interactive task.

Snuke has a favorite positive integer, N. You can ask him the following type of question at most 64 times: "Is n your favorite integer?" Identify N.

Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:

  • Both n \leq N and str(n) \leq str(N) hold.
  • Both n > N and str(n) > str(N) hold.

Here, str(x) is the decimal representation of x (without leading zeros) as a string. For example, str(123) = 123 and str(2000) = 2000. Strings are compared lexicographically. For example, 11111 < 123 and 123456789 < 9.

Constraints

  • 1 \leq N \leq 10^{9}

Input and Output

Write your question to Standard Output in the following format:

? n

Here, n must be an integer between 1 and 10^{18} (inclusive).

Then, the response to the question shall be given from Standard Input in the following format:

ans

Here, ans is either Y or N. Y represents "Yes"; N represents "No".

Finally, write your answer in the following format:

! n

Here, n=N must hold.

Judging

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample

Below is a sample communication for the case N=123:

Input Output
? 1
Y
? 32
N
? 1010
N
? 999
Y
! 123
  • Since 1 \leq 123 and str(1) \leq str(123), the first response is "Yes".
  • Since 32 \leq 123 but str(32) > str(123), the second response is "No".
  • Since 1010 > 123 but str(1010) \leq str(123), the third response is "No".
  • Since 999 \geq 123 and str(999) > str(123), the fourth response is "Yes".
  • The program successfully identifies N=123 in four questions, and thus passes the case.
F - Mole and Abandoned Mine

Time Limit: 4 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

モグラは 1 から N の番号がついた N 個の頂点と M 本の辺からなる単純連結無向グラフで表されるような廃坑に住むことにしました。 i 番目の辺は頂点 a_i と b_i をつないでおり、取り除くために c_i 円かかります。

モグラはいくつかの辺を取り除いて、頂点 1 から頂点 N へ同じ頂点を 2 回以上訪れないように移動する経路がただ 1 通りのみ存在するようにしたいです。これを達成するために必要な資金の最小値を求めなさい。

制約

  • 2 \leq N \leq 15
  • N-1 \leq M \leq N(N-1)/2
  • 1 \leq a_i, b_i \leq N
  • 1 \leq c_i \leq 10^{6}
  • 与えられるグラフに多重辺や自己ループは存在しない
  • 与えられるグラフは連結

入力

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

N M
a_1 b_1 c_1
:
a_M b_M c_M

出力

答えを出力せよ。

入力例 1

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100

出力例 1

200

以下の図において、赤い破線で表されている辺は取り除かれた辺です。以下の図のように 2 つの辺を取り除くことで 200 円で達成することが可能です。

45c15676bb602ca3b762561fc014ecd0.png

入力例 2

2 1
1 2 1

出力例 2

0

はじめから、頂点 1 から頂点 N へのパスが 1 通りしかないこともあります。

入力例 3

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491

出力例 3

133677

Score : 900 points

Problem Statement

Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of N vertices numbered 1 through N and M edges. The i-th edge connects Vertices a_i and b_i, and it costs c_i yen (the currency of Japan) to remove it.

Mole would like to remove some of the edges so that there is exactly one path from Vertex 1 to Vertex N that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.

Constraints

  • 2 \leq N \leq 15
  • N-1 \leq M \leq N(N-1)/2
  • 1 \leq a_i, b_i \leq N
  • 1 \leq c_i \leq 10^{6}
  • There are neither multiple edges nor self-loops in the given graph.
  • The given graph is connected.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
:
a_M b_M c_M

Output

Print the answer.

Sample Input 1

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100

Sample Output 1

200

By removing the two edges represented by the red dotted lines in the figure below, the objective can be achieved for a cost of 200 yen.

45c15676bb602ca3b762561fc014ecd0.png

Sample Input 2

2 1
1 2 1

Sample Output 2

0

It is possible that there is already only one path from Vertex 1 to Vertex N in the beginning.

Sample Input 3

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491

Sample Output 3

133677