AtCoder Beginner Contest 074

A - Bichrome Cells

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 100 点

問題文

N \times N のマス目があります。

このマス目の各マスを白色または黒色に塗ることにしました (すべてのマスをどちらか片方の色に塗ります)。

ちょうど A マスを白色に塗るとき、黒色に塗ることになるマスはいくつあるでしょうか。

制約

1≦N≦100
0 ≦ A ≦ N^2

入力

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

N
A

出力

黒色に塗ることになるマスの個数を出力せよ。

入力例 1

3
4

出力例 1

3 \times 3 のマス目にはマスが 9 個あります。そのうち 4 個を白く塗るので、残った 5 マスは黒く塗ることになります。

入力例 2

19
100

出力例 2

入力例 3

10
0

出力例 3

白く塗るマスの個数が 0 なので、すべてのマスが黒く塗られます。

Score : 100 points

Problem Statement

We have an N \times N square grid.

We will paint each square in the grid either black or white.

If we paint exactly A squares white, how many squares will be painted black?

Constraints

1 \leq N \leq 100
0 \leq A \leq N^2

Inputs

Input is given from Standard Input in the following format:

N
A

Outputs

Print the number of squares that will be painted black.

Sample Input 1

3
4

Sample Output 1

There are nine squares in a 3 \times 3 square grid. Four of them will be painted white, so the remaining five squares will be painted black.

Sample Input 2

19
100

Sample Output 2

Sample Input 3

10
0

Sample Output 3

As zero squares will be painted white, all the squares will be painted black.

B - Collecting Balls (Easy Version)

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 200 点

問題文

xy 平面上に N 個のボールがあります。このうち i 番目のボールの位置は (x_i, i) です。したがって、N 本の直線 y = 1, y = 2, ..., y = N の上にそれぞれ 1 個ずつボールがあることになります。

すぬけ君は、これらのボールを回収するために、タイプ A, B のロボットを N 台ずつ用意しました。さらに、タイプ A のロボットのうち i 台目のものを位置 (0, i) に、タイプ B のロボットのうち i 台目のものを位置 (K, i) に設置しました。したがって、N 本の直線 y = 1, y = 2, ..., y = N の上にそれぞれ 1 台のタイプ A のロボットと、1 台のタイプ B のロボットが設置されたことになります。

それぞれのタイプのロボットは起動されると以下のように動作します。

タイプ A のロボットは、位置 (0, a) で起動されると、直線 y = a 上にあるボールの位置まで移動し、ボールを回収してもとの位置 (0, a) に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。
タイプ B のロボットは、位置 (K, b) で起動されると、直線 y = b 上にあるボールの位置まで移動し、ボールを回収してもとの位置 (K, b) に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。

これら 2N 台のロボットのうちいくつかを起動してボールをすべて回収するとき、ロボットの移動距離の総和として考えられる値のうち最小のものを求めてください。

制約

1≦N≦100
1≦K≦100
0 < x_i < K
入力値はすべて整数である。

入力

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

N
K
x_1 x_2 ... x_N

出力

ロボットの移動距離の総和として考えられる値のうち最小のものを出力せよ。

入力例 1

1
10
2

出力例 1

ボールが 1 個だけあり、タイプ A および B のロボットが 1 つずつあります。

タイプ A のロボットを用いてボールを回収すると、ボールの位置までの移動距離は 2 であり、もとの位置に戻るための移動距離も 2 であるので、合計の移動距離は 4 となります。

同様にタイプ B のロボットを用いてボールを回収したときの移動距離の合計を計算すると 16 となります。

よって、タイプ A のロボットを用いて回収すると合計の移動距離が最小となり、そのときの移動距離である 4 を出力します。

入力例 2

2
9
3 6

出力例 2

1 つめのボールはタイプ A のロボットで、2 つめのボールはタイプ B のロボットで回収すると移動距離が最小となります。

入力例 3

5
20
11 12 9 17 12

出力例 3

Score : 200 points

Problem Statement

There are N balls in the xy-plane. The coordinates of the i-th of them is (x_i, i). Thus, we have one ball on each of the N lines y = 1, y = 2, ..., y = N.

In order to collect these balls, Snuke prepared 2N robots, N of type A and N of type B. Then, he placed the i-th type-A robot at coordinates (0, i), and the i-th type-B robot at coordinates (K, i). Thus, now we have one type-A robot and one type-B robot on each of the N lines y = 1, y = 2, ..., y = N.

When activated, each type of robot will operate as follows.

When a type-A robot is activated at coordinates (0, a), it will move to the position of the ball on the line y = a, collect the ball, move back to its original position (0, a) and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.
When a type-B robot is activated at coordinates (K, b), it will move to the position of the ball on the line y = b, collect the ball, move back to its original position (K, b) and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.

Snuke will activate some of the 2N robots to collect all of the balls. Find the minimum possible total distance covered by robots.

Constraints

1 \leq N \leq 100
1 \leq K \leq 100
0 < x_i < K
All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N
K
x_1 x_2 ... x_N

Outputs

Print the minimum possible total distance covered by robots.

Sample Input 1

1
10
2

Sample Output 1

There are just one ball, one type-A robot and one type-B robot.

If the type-A robot is used to collect the ball, the distance from the robot to the ball is 2, and the distance from the ball to the original position of the robot is also 2, for a total distance of 4.

Similarly, if the type-B robot is used, the total distance covered will be 16.

Thus, the total distance covered will be minimized when the type-A robot is used. The output should be 4.

Sample Input 2

2
9
3 6

Sample Output 2

The total distance covered will be minimized when the first ball is collected by the type-A robot, and the second ball by the type-B robot.

Sample Input 3

5
20
11 12 9 17 12

Sample Output 3

C - Sugar Water

Time Limit: 3 sec / Memory Limit: 256 MB

配点: 300 点

問題文

すぬけ君はビーカーに砂糖水を作ろうとしています。最初ビーカーは空です。すぬけ君は以下の 4 種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。

操作 1: ビーカーに水を 100A [g] 入れる。
操作 2: ビーカーに水を 100B [g] 入れる。
操作 3: ビーカーに砂糖を C [g] 入れる。
操作 4: ビーカーに砂糖を D [g] 入れる。

すぬけ君の実験環境下では、水 100 [g] あたり砂糖は E [g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F [g] 以下であり、ビーカーの中に砂糖を溶け残らせてはいけないとき、すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。答えが複数ある場合はどれを答えても構いません。

水 a [g] と砂糖 b [g] を混ぜた砂糖水の濃度は \frac{100b}{a + b} [%]です。また、この問題では、砂糖が全く溶けていない水も濃度 0 [%] の砂糖水と考えることにします。

制約

1 ≦ A < B ≦ 30
1 ≦ C < D ≦ 30
1≦ E ≦ 100
100A ≦ F ≦ 3,000
A, B, C, D, E, F はすべて整数である。

入力

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

A B C D E F

出力

整数を空白区切りで 2 つ出力せよ。 1 つ目は求める砂糖水の質量、2 つ目はそれに溶けている砂糖の質量とせよ。

入力例 1

1 2 10 20 15 200

出力例 1

110 10

この入力例の状況では、水 100 [g] あたり砂糖は 15 [g] 溶けます。また、ビーカーに物質を 200 [g] まで入れることができます。

操作 1 と操作 3 を 1 回ずつ行うことで 110 [g] の砂糖水を作ることができます。また、これ以上濃度の高い砂糖水を作ることはできません。たとえば、以下のような操作は条件を満たしません。

操作 1 と操作 4 を 1 回ずつ行うと、ビーカーに砂糖が溶け残ってしまいます。
操作 2 を 1 回と操作 3 を 3 回行うと、ビーカーの中の物質の量が 200 [g] を超えてしまいます。

入力例 2

1 2 1 2 100 1000

出力例 2

200 100

ほかに、たとえば以下の出力も正解となります。

400 200

一方、以下の出力は不正解となります。

300 150

なぜなら、砂糖が 150 [g] 溶けた 300 [g] の砂糖水を作るにはビーカーに水をちょうど 150 [g] 入れる必要がありますが、そのようなことは不可能だからです。

入力例 3

17 19 22 26 55 2802

出力例 3

2634 934

Score : 300 points

Problem Statement

Snuke is making sugar water in a beaker. Initially, the beaker is empty. Snuke can perform the following four types of operations any number of times. He may choose not to perform some types of operations.

Operation 1: Pour 100A grams of water into the beaker.
Operation 2: Pour 100B grams of water into the beaker.
Operation 3: Put C grams of sugar into the beaker.
Operation 4: Put D grams of sugar into the beaker.

In our experimental environment, E grams of sugar can dissolve into 100 grams of water.

Snuke will make sugar water with the highest possible density.

The beaker can contain at most F grams of substances (water and sugar combined), and there must not be any undissolved sugar in the beaker. Find the mass of the sugar water Snuke will make, and the mass of sugar dissolved in it. If there is more than one candidate, any of them will be accepted.

We remind you that the sugar water that contains a grams of water and b grams of sugar is \frac{100b}{a + b} percent. Also, in this problem, pure water that does not contain any sugar is regarded as 0 percent density sugar water.

Constraints

1 \leq A < B \leq 30
1 \leq C < D \leq 30
1 \leq E \leq 100
100A \leq F \leq 3 000
A, B, C, D, E and F are all integers.

Inputs

Input is given from Standard Input in the following format:

A B C D E F

Outputs

Print two integers separated by a space. The first integer should be the mass of the desired sugar water, and the second should be the mass of the sugar dissolved in it.

Sample Input 1

1 2 10 20 15 200

Sample Output 1

110 10

In this environment, 15 grams of sugar can dissolve into 100 grams of water, and the beaker can contain at most 200 grams of substances.

We can make 110 grams of sugar water by performing Operation 1 once and Operation 3 once. It is not possible to make sugar water with higher density. For example, the following sequences of operations are infeasible:

If we perform Operation 1 once and Operation 4 once, there will be undissolved sugar in the beaker.
If we perform Operation 2 once and Operation 3 three times, the mass of substances in the beaker will exceed 200 grams.

Sample Input 2

1 2 1 2 100 1000

Sample Output 2

200 100

There are other acceptable outputs, such as:

400 200

However, the output below is not acceptable:

300 150

This is because, in order to make 300 grams of sugar water containing 150 grams of sugar, we need to pour exactly 150 grams of water into the beaker, which is impossible.

Sample Input 3

17 19 22 26 55 2802

Sample Output 3

2634 934

D - Restoring Road Network

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 500 点

問題文

かつて存在した高橋王国には N 個の都市があり、いくつかの都市の組は道路で双方向に結ばれていました。道路の構造は以下のようであったことがわかっています。

都市間の移動は道路を通ってのみ行われ、どの都市からどの都市へも必要なら他の都市を経由することで移動できるようになっていた。
道路の長さは道路によって異なっていたかもしれないが、全て正整数であった。

考古学者のすぬけ君は、高橋王国の遺跡で整数からなる N \times N の表 A を発見しました。すぬけ君は、この表は高橋王国における都市間の道路に沿った最短距離を表した表ではないかと考えました。

すべての u, v について、A の u 行目 v 列目の整数 A_{u, v} が都市 u から都市 v への最短経路の長さとなるような道路の構造が存在するかどうか判定してください。さらに、存在する場合、そのような道路の構造のうち、存在する道路の長さの和が最小となるようなものについて、その和を求めてください。

制約

1≦N≦300
i ≠ j のとき、1 ≦ A_{i, j} = A_{j, i} ≦ 10^9
A_{i, i} = 0

入力

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

N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}

出力

条件を満たす道路の構造が存在しない場合、-1 と出力せよ。存在する場合、道路の長さの和の最小値を出力せよ。

入力例 1

出力例 1

条件を満たす道路の構造は以下のとおりです。

都市 1 と都市 2 の間は長さ 1 の道路によって結ばれている。
都市 2 と都市 3 の間は長さ 2 の道路によって結ばれている。
都市 3 と都市 1 の間は道路で結ばれていない。

入力例 2

出力例 2

-1

都市 1 から都市 2 へ、および都市 2 から都市 3 へそれぞれ距離 1 で移動できることから、都市 1 から都市 3 へは都市 2 を経由することで距離 2 で移動できることがわかります。一方、都市 1 と都市 3 の間の最短距離は 3 でなければなりません。

よって条件を満たす道路の構造は存在しないことがわかります。

入力例 3

5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

出力例 3

入力例 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

出力例 4

3000000000

Score : 500 points

Problem Statement

In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network:

People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
Different roads may have had different lengths, but all the lengths were positive integers.

Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom. He thought that it represented the shortest distances between the cities along the roads in the kingdom.

Determine whether there exists a road network such that for each u and v, the integer A_{u, v} at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v. If such a network exist, find the shortest possible total length of the roads.

Constraints

1 \leq N \leq 300
If i ≠ j, 1 \leq A_{i, j} = A_{j, i} \leq 10^9.
A_{i, i} = 0

Inputs

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}

Outputs

If there exists no network that satisfies the condition, print -1. If it exists, print the shortest possible total length of the roads.

Sample Input 1

Sample Output 1

The network below satisfies the condition:

City 1 and City 2 is connected by a road of length 1.
City 2 and City 3 is connected by a road of length 2.
City 3 and City 1 is not connected by a road.

Sample Input 2

Sample Output 2

-1

As there is a path of length 1 from City 1 to City 2 and City 2 to City 3, there is a path of length 2 from City 1 to City 3. However, according to the table, the shortest distance between City 1 and City 3 must be 3.

Thus, we conclude that there exists no network that satisfies the condition.

Sample Input 3

5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

Sample Output 3

Sample Input 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Sample Output 4

3000000000