Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
すぬけくんは 3 匹のヤギにクッキーを渡したいです。
すぬけくんは A 枚のクッキーが入った缶と、B 枚のクッキーが入った缶を持っています。 すぬけくんは A, B, A+B のいずれかの枚数のクッキーをヤギたちに渡すことができます。
3 匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能かどうか判定してください。
制約
- 1 \leq A,B \leq 100
- A,B はいずれも整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
3 匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能ならば Possible と、そうでなければ Impossible と出力せよ。
入力例 1
4 5
出力例 1
Possible
9 枚のクッキーを渡すことで、3 匹のヤギは 3 枚ずつ食べることが可能です。
入力例 2
1 1
出力例 2
Impossible
クッキーは 2 枚しかないので、どのように渡しても 3 匹のヤギが同じ枚数食べることはできません。
Score : 100 points
Problem Statement
Snuke is giving cookies to his three goats.
He has two cookie tins. One contains A cookies, and the other contains B cookies. He can thus give A cookies, B cookies or A+B cookies to his goats (he cannot open the tins).
Your task is to determine whether Snuke can give cookies to his three goats so that each of them can have the same number of cookies.
Constraints
- 1 \leq A,B \leq 100
- Both A and B are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
If it is possible to give cookies so that each of the three goats can have the same number of cookies, print Possible; otherwise, print Impossible.
Sample Input 1
4 5
Sample Output 1
Possible
If Snuke gives nine cookies, each of the three goats can have three cookies.
Sample Input 2
1 1
Sample Output 2
Impossible
Since there are only two cookies, the three goats cannot have the same number of cookies no matter what Snuke gives to them.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
すぬけくんは N 本の棒を持っています。 i 番目の棒の長さは l_i です。
すぬけくんは K 本の棒を選んでつなげて、ヘビのおもちゃを作りたいです。
ヘビのおもちゃの長さは選んだ棒たちの長さの総和で表されます。 ヘビのおもちゃの長さとしてありうる長さのうち、最大値を求めなさい。
制約
- 1 \leq K \leq N \leq 50
- 1 \leq l_i \leq 50
- l_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N K
l_1 l_2 l_3 ... l_{N}
出力
答えを出力せよ。
入力例 1
5 3 1 2 3 4 5
出力例 1
12
長さ 3,4,5 の棒を選んでつなげると、長さ 12 のヘビのおもちゃを作ることが可能で、これがありうる長さのうち最大の値です。
入力例 2
15 14 50 26 27 21 41 7 42 35 7 5 5 36 39 1 45
出力例 2
386
Score : 200 points
Problem Statement
Snuke has N sticks. The length of the i-th stick is l_i.
Snuke is making a snake toy by joining K of the sticks together.
The length of the toy is represented by the sum of the individual sticks that compose it. Find the maximum possible length of the toy.
Constraints
- 1 \leq K \leq N \leq 50
- 1 \leq l_i \leq 50
- l_i is an integer.
Input
Input is given from Standard Input in the following format:
N K
l_1 l_2 l_3 ... l_{N}
Output
Print the answer.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
12
You can make a toy of length 12 by joining the sticks of lengths 3, 4 and 5, which is the maximum possible length.
Sample Input 2
15 14 50 26 27 21 41 7 42 35 7 5 5 36 39 1 45
Sample Output 2
386
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.
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