AtCoder Beginner Contest 079

A - Good Integer

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

1118 のような、3 つ以上の同じ数字が連続して並んだ 4 桁の整数を 良い整数 とします。

4 桁の整数 N が与えられるので、N が 良い整数 かどうかを答えてください。

制約

1000≦N≦9999
入力は整数からなる

入力

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

出力

N が 良い整数 ならば Yes を、そうでなければ No を出力せよ。

入力例 1

出力例 1

Yes

1 が 3 つ連続して並んでいるので 良い整数 です。

入力例 2

出力例 2

Yes

全ての数字が同じ場合も 良い整数 になります。

入力例 3

出力例 3

No

Score : 100 points

Problem Statement

We call a 4-digit integer with three or more consecutive same digits, such as 1118, good.

You are given a 4-digit integer N. Answer the question: Is N good?

Constraints

1000 ≤ N ≤ 9999
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

If N is good, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

N is good, since it contains three consecutive 1.

Sample Input 2

Sample Output 2

Yes

An integer is also good when all the digits are the same.

Sample Input 3

Sample Output 3

No

B - Lucas Number

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

今、日本は 11 月 18 日ですが、11 と 18 は隣り合うリュカ数です。

整数 N が与えられるので、N 番目のリュカ数を求めてください。

ただし、リュカ数は i 番目のリュカ数を L_i とすると、

L_0=2
L_1=1
L_i=L_{i-1}+L_{i-2} (i≧2)

と定義される数とします。

制約

1≦N≦86
答えは 10^{18} より小さいことが保証される
入力は整数からなる

入力

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

出力

N 番目のリュカ数を出力せよ。

入力例 1

出力例 1

L_0=2
L_1=1
L_2=L_0+L_1=3
L_3=L_1+L_2=4
L_4=L_2+L_3=7
L_5=L_3+L_4=11

より、5 番目のリュカ数は 11 です。

入力例 2

出力例 2

939587134549734843

Score : 200 points

Problem Statement

It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.

You are given an integer N. Find the N-th Lucas number.

Here, the i-th Lucas number L_i is defined as follows:

L_0=2
L_1=1
L_i=L_{i-1}+L_{i-2} (i≥2)

Constraints

1≤N≤86
It is guaranteed that the answer is less than 10^{18}.
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the N-th Lucas number.

Sample Input 1

Sample Output 1

L_0=2
L_1=1
L_2=L_0+L_1=3
L_3=L_1+L_2=4
L_4=L_2+L_3=7
L_5=L_3+L_4=11

Thus, the 5-th Lucas number is 11.

Sample Input 2

Sample Output 2

939587134549734843

C - Train Ticket

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。

切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。

A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。

なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。

制約

0≦A,B,C,D≦9
入力は整数からなる
答えが存在しない入力は与えられない

入力

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

ABCD

出力

作った式を、=7 の部分を含めて出力せよ。

ただし、記号は半角で出力せよ。

また、数字と記号の間に空白を入れてはならない。

入力例 1

出力例 1

1+2+2+2=7

1 + 2 + 2 + 2 = 7 が条件を満たします。

入力例 2

出力例 2

0-2+9+0=7

この他に、0 - 2 + 9 - 0 = 7 が条件を満たします。

入力例 3

出力例 3

3+2+4-2=7

Score : 300 points

Problem Statement

Sitting in a station waiting room, Joisino is gazing at her train ticket.

The ticket is numbered with four digits A, B, C and D in this order, each between 0 and 9 (inclusive).

In the formula A op1 B op2 C op3 D = 7, replace each of the symbols op1, op2 and op3 with + or - so that the formula holds.

The given input guarantees that there is a solution. If there are multiple solutions, any of them will be accepted.

Constraints

0≤A,B,C,D≤9
All input values are integers.
It is guaranteed that there is a solution.

Input

Input is given from Standard Input in the following format:

ABCD

Output

Print the formula you made, including the part =7.

Use the signs + and -.

Do not print a space between a digit and a sign.

Sample Input 1

Sample Output 1

1+2+2+2=7

This is the only valid solution.

Sample Input 2

Sample Output 2

0-2+9+0=7

0 - 2 + 9 - 0 = 7 is also a valid solution.

Sample Input 3

Sample Output 3

3+2+4-2=7

D - Wall

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 400 点

問題文

魔法少女のjoisinoお姉ちゃんは、この世にあるすべての数字を 1 に変えてやろうと思い立ちました。

1 つの数字を i から j(0≦i,j≦9) に書き変えるには魔力 c_{i,j} が必要です。

今、目の前にある壁は縦方向に H、横方向に W のマス目になっていて、1 つ以上のマス目に 0 以上 9 以下の整数が 1 つずつ書かれています。

上から i(1≦i≦H) 番目、左から j(1≦j≦W) 番目のマスの情報として A_{i,j} が与えられ、

A_{i,j}≠-1 の場合はマスに A_{i,j} が書かれている
A_{i,j}=-1 の場合はマスに数字が書かれていない

ことを意味します。

この壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小量を求めてください。

制約

1≦H,W≦200
1≦c_{i,j}≦10^3 (i≠j)
c_{i,j}=0 (i=j)
-1≦A_{i,j}≦9
入力は整数からなる
壁には一つ以上の整数が書かれている

入力

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

H W
c_{0,0} ... c_{0,9}
:
c_{9,0} ... c_{9,9}
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}

出力

壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小量を出力せよ。

入力例 1

2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8

出力例 1

8 を 1 に変えるとき、 8 を 4 に変え、その後 4 を 9 に、9 を 1 に変えると必要な魔力が最小となります。

壁には 8 が 2 つ書かれているので、必要な魔力の最小量は 6×2=12です。

入力例 2

5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 2

壁に書かれている数字を全く変える必要がない場合に注意してください。

入力例 3

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

出力例 3

Score : 400 points

Problem Statement

Joisino the magical girl has decided to turn every single digit that exists on this world into 1.

Rewriting a digit i with j (0≤i,j≤9) costs c_{i,j} MP (Magic Points).

She is now standing before a wall. The wall is divided into HW squares in H rows and W columns, and at least one square contains a digit between 0 and 9 (inclusive).

You are given A_{i,j} that describes the square at the i-th row from the top and j-th column from the left, as follows:

If A_{i,j}≠-1, the square contains a digit A_{i,j}.
If A_{i,j}=-1, the square does not contain a digit.

Find the minimum total amount of MP required to turn every digit on this wall into 1 in the end.

Constraints

1≤H,W≤200
1≤c_{i,j}≤10^3 (i≠j)
c_{i,j}=0 (i=j)
-1≤A_{i,j}≤9
All input values are integers.
There is at least one digit on the wall.

Input

Input is given from Standard Input in the following format:

H W
c_{0,0} ... c_{0,9}
:
c_{9,0} ... c_{9,9}
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}

Output

Print the minimum total amount of MP required to turn every digit on the wall into 1 in the end.

Sample Input 1

2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8

Sample Output 1

To turn a single 8 into 1, it is optimal to first turn 8 into 4, then turn 4 into 9, and finally turn 9 into 1, costing 6 MP.

The wall contains two 8s, so the minimum total MP required is 6×2=12.

Sample Input 2

5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

Note that she may not need to change any digit.

Sample Input 3

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