AtCoder Beginner Contest 075

A - One out of Three

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

3 つの整数 A,B,C が与えられます。
A,B,C のうち 2 つは同じ整数であり、残りの 1 つだけ異なる整数です。
例えば、A=5,B=7,C=5 の場合、A,C の 2 つは同じ整数であり、B は 1 つだけ異なる整数です。
3 つの整数のうち、1 つだけ異なる整数を求めてください。

制約

-100≦A,B,C≦100
A,B,C は整数
入力は問題文の条件を満たす

入力

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

A B C

出力

A,B,C のうち、1 つだけ異なる整数を出力せよ。

入力例 1

5 7 5

出力例 1

問題文の例と同じです。

入力例 2

1 1 7

出力例 2

この場合は、C が求める整数です。

入力例 3

-100 100 100

出力例 3

-100

Score : 100 points

Problem Statement

You are given three integers, A, B and C.
Among them, two are the same, but the remaining one is different from the rest.
For example, when A=5,B=7,C=5, A and C are the same, but B is different.
Find the one that is different from the rest among the given three integers.

Constraints

-100 \leq A,B,C \leq 100
A, B and C are integers.
The input satisfies the condition in the statement.

Input

Input is given from Standard Input in the following format:

A B C

Output

Among A, B and C, print the integer that is different from the rest.

Sample Input 1

5 7 5

Sample Output 1

This is the same case as the one in the statement.

Sample Input 2

1 1 7

Sample Output 2

In this case, C is the one we seek.

Sample Input 3

-100 100 100

Sample Output 3

-100

B - Minesweeper

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

H × W のマス目が与えられます。
入力において、全てのマスは文字で表されており、.は空きマス、 # は爆弾マスに対応します。
マス目は H 個の文字列 S_1,...,S_H で表されます。
文字列 S_i の j 文字目は、マス目の上から i 番目、左から j 番目のマスに対応します。(1≦i≦H,1≦j≦W)

イルカは各空きマスの上下左右および斜めの 8 方向で隣接しているマスに爆弾マスが何個あるか気になっています。
そこで、各空きマスに対応する . を、その空きマスの周囲8方向に隣接するマスにおける爆弾マスの個数を表す数字で置き換えることにしました。

以上の規則で置き換えられた後のマス目を出力してください。

制約

1≦H,W≦50
S_i は # と . からなる長さ W の文字列

入力

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

H W 
S_1
:
S_H

出力

置き換えられた後のマス目を H 行の文字列で出力せよ。
i 行目に出力する文字列 T_i の長さは W であり、 T_i の j 文字目は、置き換えられた後のマス目の上から i 番目、左から j 番目のマスに対応させよ。(1≦i≦H,1≦j≦W)

入力例 1

3 5
.....
.#.#.
.....

出力例 1

11211
1#2#1
11211

例として、上から 1 番目、左から 1 番目の空きマスに注目します。
この空きマスの周囲の 8 マスに含まれる爆弾マスは、上から 2 番目、左から 2 番目のマスのみです。したがって、上から 1 番目、左から 1 番目の空きマスは 1 に置き換えられています。

入力例 2

3 5
#####
#####
#####

出力例 2

#####
#####
#####

空きマスが存在しない場合があります。

入力例 3

6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#...

出力例 3

#####3
#8#7##
####5#
4#65#2
#5##21
#4#310

Score : 200 points

Problem Statement

You are given an H × W grid.
The squares in the grid are described by H strings, S_1,...,S_H.
The j-th character in the string S_i corresponds to the square at the i-th row from the top and j-th column from the left (1 \leq i \leq H,1 \leq j \leq W).
. stands for an empty square, and # stands for a square containing a bomb.

Dolphin is interested in how many bomb squares are horizontally, vertically or diagonally adjacent to each empty square.
(Below, we will simply say "adjacent" for this meaning. For each square, there are at most eight adjacent squares.)
He decides to replace each . in our H strings with a digit that represents the number of bomb squares adjacent to the corresponding empty square.

Print the strings after the process.

Constraints

1 \leq H,W \leq 50
S_i is a string of length W consisting of # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the H strings after the process.
The i-th line should contain a string T_i of length W, where the j-th character in T_i corresponds to the square at the i-th row from the top and j-th row from the left in the grid (1 \leq i \leq H, 1 \leq j \leq W).

Sample Input 1

3 5
.....
.#.#.
.....

Sample Output 1

11211
1#2#1
11211

For example, let us observe the empty square at the first row from the top and first column from the left.
There is one bomb square adjacent to this empty square: the square at the second row and second column.
Thus, the . corresponding to this empty square is replaced with 1.

Sample Input 2

3 5
#####
#####
#####

Sample Output 2

#####
#####
#####

It is possible that there is no empty square.

Sample Input 3

6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#...

Sample Output 3

#####3
#8#7##
####5#
4#65#2
#5##21
#4#310

C - Bridge

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

自己ループと二重辺を含まない N 頂点 M 辺の無向連結グラフが与えられます。
i(1≦i≦M) 番目の辺は頂点 a_i と頂点 b_i を結びます。

グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられた M 本のうち橋である辺の本数を求めてください。

ノート

自己ループ とは、a_i=b_i(1≦i≦M) であるような辺 i のことをいいます。
二重辺 とは、a_i=a_j かつ b_i=b_j(1≦i<j≦M) であるような辺の組 i,j のことをいいます。
無向グラフが連結であるとは、グラフの任意の二頂点間に経路が存在することをいいます。

制約

2≦N≦50
N-1≦M≦min(N(N−1)⁄2,50)
1≦a_i<b_i≦N
与えられるグラフは自己ループと二重辺を含まない。
与えられるグラフは連結である。

入力

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

出力

M 本の辺のうち、橋である辺の本数を出力せよ。

入力例 1

出力例 1

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

図の赤い辺が橋であり、その数は 4 本です。

入力例 2

出力例 2

橋である辺が存在しない場合もあります。

入力例 3

出力例 3

全ての辺が橋である場合もあります。

Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.
The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.

An edge whose removal disconnects the graph is called a bridge.
Find the number of the edges that are bridges among the M edges.

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).
Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).
An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50
N-1 \leq M \leq min(N(N−1)⁄2,50)
1 \leq a_i<b_i \leq N
The given graph does not contain self-loops and double edges.
The given graph is connected.

Input

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 edges that are bridges among the M edges.

Sample Input 1

Sample Output 1

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

Sample Output 2

It is possible that there is no bridge.

Sample Input 3

Sample Output 3

It is possible that every edge is a bridge.

D - Axis-Parallel Rectangle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

2次元座標上に N 個の点があります。
i(1≦i≦N) 番目の点の座標は (x_i,y_i) です。
長方形の内部に N 点のうち K 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。

制約

2≦K≦N≦50
-10^9≦x_i,y_i≦10^9 (1≦i≦N)
x_i≠x_j (1≦i<j≦N)
y_i≠y_j (1≦i<j≦N)
入力値はすべて整数である。(21:50 追記)

入力

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

N K  
x_1 y_1
:  
x_{N} y_{N}

出力

条件を満たす長方形の中で最小面積となるような長方形の面積を出力せよ。

入力例 1

出力例 1

条件を満たす最小面積となる長方形の 1 つは　(1,1),(8,1),(1,4),(8,4) の 4 つの頂点で構成されます。
その面積は (8-1) × (4-1) = 21 であるため、21 と出力します。

入力例 2

出力例 2

入力例 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

出力例 3

3999999996000000001

オーバーフローに注意してください。

Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.
The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).
Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.
Here, points on the sides of the rectangle are considered to be in the interior.
Find the minimum possible area of such a rectangle.

Constraints

2 \leq K \leq N \leq 50
-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)
x_i≠x_j (1 \leq i<j \leq N)
y_i≠y_j (1 \leq i<j \leq N)
All input values are integers. (Added at 21:50 JST)

Input

Input is given from Standard Input in the following format:

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.

Sample Input 1

Sample Output 1

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).
Its area is (8-1) × (4-1) = 21.

Sample Input 2

Sample Output 2

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.