Time Limit: 2 sec / Memory Limit: 256 MB
配点：100 点
問題文
E869120 は 1 円硬貨を A 枚と 500 円硬貨を無限枚持っています.
これらの硬貨だけを使うことによって, ちょうど N 円を支払うことができるかを判定しなさい.
制約
- N は 1 以上 10000 以下の整数
- A は 0 以上 1000 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N A
出力
E869120 の持っている 1 円硬貨と 500 円硬貨だけで, ちょうど N 円を支払うことができるならば Yes, そうでないならば No を出力しなさい.
入力例 1
2018 218
出力例 1
Yes
500 円硬貨 4 枚と 1 円硬貨 18 枚で, 2018 円を支払うことができるので, 答えは Yes です.
入力例 2
2763 0
出力例 2
No
1 円硬貨を 1 枚も持っていないとき, 500 円硬貨だけを使うことになるので, 500 の倍数の金額を支払うことしかできません. 2763 は 500 の倍数ではないので, この金額を支払うことはできません.
入力例 3
37 514
出力例 3
Yes
Score: 100 points
Problem Statement
E869120 has A 1-yen coins and infinitely many 500-yen coins.
Determine if he can pay exactly N yen using only these coins.
Constraints
- N is an integer between 1 and 10000 (inclusive).
- A is an integer between 0 and 1000 (inclusive).
Input
Input is given from Standard Input in the following format:
N A
Output
If E869120 can pay exactly N yen using only his 1-yen and 500-yen coins, print Yes; otherwise, print No.
Sample Input 1
2018 218
Sample Output 1
Yes
We can pay 2018 yen with four 500-yen coins and 18 1-yen coins, so the answer is Yes.
Sample Input 2
2763 0
Sample Output 2
No
When we have no 1-yen coins, we can only pay a multiple of 500 yen using only 500-yen coins. Since 2763 is not a multiple of 500, we cannot pay this amount.
Sample Input 3
37 514
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 256 MB
配点：200 点
問題文
N 枚のカードがあります. i 枚目のカードには, a_i という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
制約
- N は 1 以上 100 以下の整数
- a_i \ (1 \leq i \leq N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N a_1 a_2 a_3 ... a_N
出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.
入力例 1
2 3 1
出力例 1
2
最初, Alice は 3 が書かれたカードを取ります. 次に, Bob は 1 が書かれたカードを取ります. 得点差は 3 - 1 = 2 となります.
入力例 2
3 2 7 4
出力例 2
5
最初, Alice は 7 が書かれたカードを取ります. 次に, Bob は 4 が書かれたカードを取ります. 最後に, Alice は 2 が書かれたカードを取ります. 得点差は, 7 - 4 + 2 = 5 点となります.
入力例 3
4 20 18 2 18
出力例 3
18
Score: 200 points
Problem Statement
We have N cards. A number a_i is written on the i-th card.
Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first.
The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.
Constraints
- N is an integer between 1 and 100 (inclusive).
- a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
N a_1 a_2 a_3 ... a_N
Output
Print Alice's score minus Bob's score when both players take the optimal strategy to maximize their scores.
Sample Input 1
2 3 1
Sample Output 1
2
First, Alice will take the card with 3. Then, Bob will take the card with 1. The difference of their scores will be 3 - 1 = 2.
Sample Input 2
3 2 7 4
Sample Output 2
5
First, Alice will take the card with 7. Then, Bob will take the card with 4. Lastly, Alice will take the card with 2. The difference of their scores will be 7 - 4 + 2 = 5. The difference of their scores will be 3 - 1 = 2.
Sample Input 3
4 20 18 2 18
Sample Output 3
18
Time Limit: 2 sec / Memory Limit: 256 MB
配点：300 点
問題文
3 \times 3 のグリッドがあります. 上から i 番目で左から j 番目のマスを (i, j) で表すとき, マス (i, j) には数 c_{i, j} が書かれています.
高橋君によると, 整数 a_1, a_2, a_3, b_1, b_2, b_3 の値が決まっており, マス (i, j) には数 a_i + b_j が書かれているらしいです.
高橋君の情報が正しいか判定しなさい.
制約
- c_{i, j} \ (1 \leq i \leq 3, 1 \leq j \leq 3) は 0 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
c_{1,1} c_{1,2} c_{1,3}
c_{2,1} c_{2,2} c_{2,3}
c_{3,1} c_{3,2} c_{3,3}
出力
高橋君の情報が正しい場合 Yes, そうでない場合 No と出力してください.
入力例 1
1 0 1 2 1 2 1 0 1
出力例 1
Yes
a_1=0,a_2=1,a_3=0,b_1=1,b_2=0,b_3=1 などの組み合わせがありうるので, 高橋君の情報は正しいです.
入力例 2
2 2 2 2 1 2 2 2 2
出力例 2
No
このグリッドの場合、高橋君の情報は間違っています.
入力例 3
0 8 8 0 8 8 0 8 8
出力例 3
Yes
入力例 4
1 8 6 2 9 7 0 7 7
出力例 4
No
Score: 300 points
Problem Statement
We have a 3 \times 3 grid. A number c_{i, j} is written in the square (i, j), where (i, j) denotes the square at the i-th row from the top and the j-th column from the left.
According to Takahashi, there are six integers a_1, a_2, a_3, b_1, b_2, b_3 whose values are fixed, and the number written in the square (i, j) is equal to a_i + b_j.
Determine if he is correct.
Constraints
- c_{i, j} \ (1 \leq i \leq 3, 1 \leq j \leq 3) is an integer between 0 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
c_{1,1} c_{1,2} c_{1,3}
c_{2,1} c_{2,2} c_{2,3}
c_{3,1} c_{3,2} c_{3,3}
Output
If Takahashi's statement is correct, print Yes; otherwise, print No.
Sample Input 1
1 0 1 2 1 2 1 0 1
Sample Output 1
Yes
Takahashi is correct, since there are possible sets of integers such as: a_1=0,a_2=1,a_3=0,b_1=1,b_2=0,b_3=1.
Sample Input 2
2 2 2 2 1 2 2 2 2
Sample Output 2
No
Takahashi is incorrect in this case.
Sample Input 3
0 8 8 0 8 8 0 8 8
Sample Output 3
Yes
Sample Input 4
1 8 6 2 9 7 0 7 7
Sample Output 4
No
Time Limit: 2 sec / Memory Limit: 256 MB
配点：400 点
問題文
縦 H マス, 横 W マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から i 番目で左から j 番目のマスを (i, j) で表す.
すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス (1, 1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って (H, W) にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス (1, 1) と (H, W) の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H, W) にたどり着くことが出来ない場合、-1 と出力しなさい.
ただし, 各マスの色の情報は文字 s_{i, j} として与えられる. マス (i, j) が最初白で塗られている場合 s_{i, j} は . であり, マス (i, j) が最初黒で塗られている場合 s_{i, j} は # である.
制約
- H は 2 以上 50 以下の整数
- W は 2 以上 50 以下の整数
- s_{i, j} は
.または#(1 \leq i \leq H, 1 \leq j \leq W) - s_{1, 1}, s_{H, W} は
.である
入力
入力は以下の形式で標準入力から与えられる.
H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
: :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}
出力
すぬけ君が取る可能性のある最大のスコアを出力しなさい. ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H, W) にたどり着くことが出来ない場合、-1 と出力しなさい.
入力例 1
3 3 ..# #.. ...
出力例 1
2
下の図のようにマス目の色を変えれば, スコア 2 を達成できます.
入力例 2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
出力例 2
209
Score: 400 points
Problem statement
We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).
Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.
Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.
When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.
The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.
Constraints
- H is an integer between 2 and 50 (inclusive).
- W is an integer between 2 and 50 (inclusive).
- s_{i, j} is
.or#(1 \leq i \leq H, 1 \leq j \leq W). - s_{1, 1} and s_{H, W} are
..
Input
Input is given from Standard Input in the following format:
H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
: :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}
Output
Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.
Sample Input 1
3 3 ..# #.. ...
Sample Output 1
2
The score 2 can be achieved by changing the color of squares as follows:
Sample Input 2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
Sample Output 2
209