AtCoder Beginner Contest 054

A - One Card Poker

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

AliceとBobは、2人で1枚ポーカーを行います。
1枚ポーカーは、トランプを用いて行う2人ゲームです。

今回使用するトランプでは、各カードに 1 から 13 までの数が書かれています。
カードの強さは、カードに書かれている数で決まり，強さの基準は以下の通りです。
弱 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < 11 < 12 < 13 < 1 強

1枚ポーカーは以下の手順で行います。

各プレイヤーは、トランプからカードを1枚選んで、自分の手札とします。
両プレイヤーは、手札を見せ合います。強いカードを持っているプレイヤーが勝ちです。
なお、両プレイヤーの持っているカードの強さが同じ場合は引き分けです。

2人の対戦を眺めていたあなたは、AliceとBobの手札を知ることができます。
Aliceが持っているカードに書かれている数は A 、Bobが持っているカードカードに書かれている数は B です。
2人の代わりに、勝敗を判定するプログラムを作ってください。

制約

1≦A≦13
1≦B≦13
A,B は整数である。

入力

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

A B

出力

Aliceが勝つならAliceを、Bobが勝つならBobを、引き分けならDrawを出力せよ。

入力例 1

8 6

出力例 1

Alice

Aliceが持っているカードに書かれている数は 8、Bobが持っているカードに書かれている数は 6 です。
したがって、強いカードを持っているのはAliceなので、Alice を出力します。

入力例 2

1 1

出力例 2

Draw

2人とも同じ数が書かれているカードを持っているので、引き分けです。

入力例 3

13 1

出力例 3

Bob

Score : 100 points

Problem Statement

Alice and Bob are playing One Card Poker.
One Card Poker is a two-player game using playing cards.

Each card in this game shows an integer between 1 and 13, inclusive.
The strength of a card is determined by the number written on it, as follows:

Weak 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < 11 < 12 < 13 < 1 Strong

One Card Poker is played as follows:

Each player picks one card from the deck. The chosen card becomes the player's hand.
The players reveal their hands to each other. The player with the stronger card wins the game.
If their cards are equally strong, the game is drawn.

You are watching Alice and Bob playing the game, and can see their hands.
The number written on Alice's card is A, and the number written on Bob's card is B.
Write a program to determine the outcome of the game.

Constraints

1≦A≦13
1≦B≦13
A and B are integers.

Input

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

A B

Output

Print Alice if Alice will win. Print Bob if Bob will win. Print Draw if the game will be drawn.

Sample Input 1

8 6

Sample Output 1

Alice

8 is written on Alice's card, and 6 is written on Bob's card. Alice has the stronger card, and thus the output should be Alice.

Sample Input 2

1 1

Sample Output 2

Draw

Since their cards have the same number, the game will be drawn.

Sample Input 3

13 1

Sample Output 3

Bob

B - Template Matching

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

縦 N 行、横 N 列に画素が並んだ画像Aと、縦 M 行、横 M 列に画素が並んだテンプレート画像Bが与えられます。
画素は画像を構成する最小単位であり、ここでは 1×1 の正方形とします。
また、与えられる画像は全て2値画像であり、各画素の色は白と黒の2種類で表されます。

入力において、全ての画素は文字で表されており、.は白色の画素、 # は黒色の画素に対応します。
画像Aは N 個の文字列 A_1,...,A_N で表されます。
文字列 A_i の j 文字目は、画像Aの上から i 番目、左から j 番目の画素に対応します。(1≦i,j≦N)
同様に、テンプレート画像Bは M 個の文字列 B_1,...,B_M で表されます。
文字列 B_i の j 文字目は、テンプレート画像Bの上から i 番目、左から j 番目の画素に対応します。(1≦i,j≦M)

画像の平行移動のみ許されるとき、テンプレート画像Bが画像Aの中に含まれているかを判定してください。

制約

1≦M≦N≦50
A_i は # と . からなる長さ N の文字列
B_i は # と . からなる長さ M の文字列

入力

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

N M
A_1
A_2
:  
A_N
B_1
B_2
:  
B_M

出力

画像Aの中にテンプレート画像Bを含む場合は Yes、含まない場合は No を出力せよ。

入力例 1

3 2
#.#
.#.
#.#
#.
.#

出力例 1

Yes

テンプレート画像Bが、画像A中の左上の 2 × 2 の部分画像と右下の 2 × 2 の部分画像に一致するため、Yes と出力します。

入力例 2

4 1
....
....
....
....
#

出力例 2

No

画像Aは白色の画素、テンプレート画像Bは黒色の画素で構成されるため、含まれることはありません。

Score : 200 points

Problem Statement

You are given an image A composed of N rows and N columns of pixels, and a template image B composed of M rows and M columns of pixels.
A pixel is the smallest element of an image, and in this problem it is a square of size 1×1.
Also, the given images are binary images, and the color of each pixel is either white or black.

In the input, every pixel is represented by a character: . corresponds to a white pixel, and # corresponds to a black pixel.
The image A is given as N strings A_1,...,A_N.
The j-th character in the string A_i corresponds to the pixel at the i-th row and j-th column of the image A (1≦i,j≦N).
Similarly, the template image B is given as M strings B_1,...,B_M.
The j-th character in the string B_i corresponds to the pixel at the i-th row and j-th column of the template image B (1≦i,j≦M).

Determine whether the template image B is contained in the image A when only parallel shifts can be applied to the images.

Constraints

1≦M≦N≦50
A_i is a string of length N consisting of # and ..
B_i is a string of length M consisting of # and ..

Input

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

N M
A_1
A_2
:  
A_N
B_1
B_2
:  
B_M

Output

Print Yes if the template image B is contained in the image A. Print No otherwise.

Sample Input 1

3 2
#.#
.#.
#.#
#.
.#

Sample Output 1

Yes

The template image B is identical to the upper-left 2 × 2 subimage and the lower-right 2 × 2 subimage of A. Thus, the output should be Yes.

Sample Input 2

4 1
....
....
....
....
#

Sample Output 2

No

The template image B, composed of a black pixel, is not contained in the image A composed of white pixels.

C - One-stroke Path

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

自己ループと二重辺を含まない N 頂点 M 辺の重み無し無向グラフが与えられます。
i (1≦i≦M) 番目の辺は頂点 a_i と頂点 b_i を結びます。
ここで、自己ループは a_i = b_i (1≦i≦M) となる辺のことを表します。
また、二重辺は a_i=a_j かつ b_i=b_j (1≦i<j≦M) となる辺のことを表します。
頂点 1 を始点として、全ての頂点を1度だけ訪れるパスは何通りありますか。
ただし、パスの始点と終点の頂点も訪れたものとみなします。

例として、図1のような無向グラフが与えられたとします。

図1：無向グラフの例

このとき、図2で表されるパスは条件を満たします。

図2：条件を満たすパスの例

しかし、図3で表されるパスは条件を満たしません。全ての頂点を訪れていないからです。

図3：条件を満たさないパスの例1

また、図4で表されるパスも条件を満たしません。始点が頂点 1 ではないからです。

図4：条件を満たさないパスの例2

制約

2≦N≦8
0≦M≦N(N-1)/2
1≦a_i<b_i≦N
与えられるグラフは自己ループと二重辺を含まない。

入力

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

出力

問題文の条件を満たすパスが何通りあるか出力せよ。

入力例 1

出力例 1

与えられるグラフは以下の図で表されます。

条件を満たすパスは以下の 2 通りです。

入力例 2

出力例 2

このテストケースは問題文の例と同じです。

Score : 300 points

Problem Statement

You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.
Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).
How many different paths start from vertex 1 and visit all the vertices exactly once?
Here, the endpoints of a path are considered visited.

For example, let us assume that the following undirected graph shown in Figure 1 is given.

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

Figure 2: an example of a path that satisfies the condition

However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.

Figure 3: an example of a path that does not satisfy the condition

Neither the following path shown in Figure 4, because it does not start from vertex 1.

Figure 4: another example of a path that does not satisfy the condition

Constraints

2≦N≦8
0≦M≦N(N-1)/2
1≦a_i<b_i≦N
The given graph contains neither self-loops nor double edges.

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.

Sample Input 1

Sample Output 1

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

Sample Output 2

This test case is the same as the one described in the problem statement.

D - Mixing Experiment

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

イルカは、微量の物質Cを生成したいと考えています。
物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が M_a:M_b となる溶液を用意する必要があります。
しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。
薬局では、N 種類の薬品を取り扱っており、各薬品 i の在庫はちょうど1つです。
各薬品 i は、タイプAの物質 a_i グラム、タイプBの物質 b_i グラム含んでおり、価格 c_i 円で売られています。
イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。
物質Cを生成するために、必要な最小予算を求めてください。
薬局で売られている薬品の組み合わせで、物質Cを生成できない場合はそれを報告してください。

制約

1≦N≦40
1≦a_i,b_i≦10
1≦c_i≦100
1≦M_a,M_b≦10
gcd(M_a,M_b)=1
a_i、b_i、c_i、M_a、M_bは整数である。

入力

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

N M_a M_b  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_N b_N c_N

出力

物質Cを生成するために必要な最小予算を出力せよ。物質Cを生成できない場合には -1 を出力せよ。

入力例 1

出力例 1

最小予算となる組み合わせは、薬品 1 と薬品 2 を混合する場合です。
この場合、混合した溶液中に物質Aは 3 グラム、物質Bは 3 グラム含まれており、混合比は 3:3=1:1 となって条件を満たします。
このときの合計価格は 3 円となります。

入力例 2

1 1 10
10 10 10

出力例 2

-1

物質Aと物質Bの混合比が 1:10 となる薬品の組み合わせはないので、-1を出力します。　　　

Score : 400 points

Problem Statement

Dolphin is planning to generate a small amount of a certain chemical substance C.
In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of M_a:M_b.
He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.
The pharmacy sells N kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.
The package of chemical i contains a_i grams of the substance A and b_i grams of the substance B, and is sold for c_i yen (the currency of Japan).
Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.
Find the minimum amount of money required to generate the substance C.
If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.

Constraints

1≦N≦40
1≦a_i,b_i≦10
1≦c_i≦100
1≦M_a,M_b≦10
gcd(M_a,M_b)=1
a_i, b_i, c_i, M_a and M_b are integers.

Input

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

N M_a M_b  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_N b_N c_N

Output

Print the minimum amount of money required to generate the substance C. If it is not possible to generate the substance C, print -1 instead.

Sample Input 1

Sample Output 1

The amount of money spent will be minimized by purchasing the packages of chemicals 1 and 2.
In this case, the mixture of the purchased chemicals will contain 3 grams of the substance A and 3 grams of the substance B, which are in the desired ratio: 3:3=1:1.
The total price of these packages is 3 yen.

Sample Input 2

1 1 10
10 10 10

Sample Output 2

-1

The ratio 1:10 of the two substances A and B cannot be satisfied by purchasing any combination of the packages. Thus, the output should be -1.