A - K-City

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

K 市には、東西方向に n 本の通りがあり、南北方向に m 本の通りがあります。 東西方向のそれぞれの通りは、南北方向のそれぞれの通りと交わっています。 東西南北を通りに囲まれた最小の領域を「街区」と呼びます。 K 市にある街区の個数を求めてください。

制約

  • 2 ≤ n, m ≤ 100

入力

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

n m

出力

K 市にある街区の個数を出力せよ。

入力例 1

3 4

出力例 1

6

次図の 6 個です。

9179be829dc9810539213537d4c7398c.png

入力例 2

2 2

出力例 2

1

次図の 1 個です。

997bfafa99be630b54d037225a5c68ea.png

Score : 100 points

Problem Statement

In K-city, there are n streets running east-west, and m streets running north-south. Each street running east-west and each street running north-south cross each other. We will call the smallest area that is surrounded by four streets a block. How many blocks there are in K-city?

Constraints

  • 2 ≤ n, m ≤ 100

Input

Input is given from Standard Input in the following format:

n m

Output

Print the number of blocks in K-city.

Sample Input 1

3 4

Sample Output 1

6

There are six blocks, as shown below:

9179be829dc9810539213537d4c7398c.png

Sample Input 2

2 2

Sample Output 2

1

There are one block, as shown below:

997bfafa99be630b54d037225a5c68ea.png
B - i18n

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

internationalization という英単語は、i18n と略されることがあります。 これは、先頭文字 i と末尾文字 n の間に 18 文字が挟まっていることに由来します。

長さ 3 以上の英小文字のみからなる文字列 s が与えられます。 同様の規則によって s を略してください。

制約

  • 3 ≤ |s| ≤ 100 (ただし、|s| は s の長さを表す。)
  • s は英小文字のみからなる。

入力

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

s

出力

s を略したものを出力せよ。

入力例 1

internationalization

出力例 1

i18n

入力例 2

smiles

出力例 2

s4s

入力例 3

xyz

出力例 3

x1z

Score : 200 points

Problem Statement

The word internationalization is sometimes abbreviated to i18n. This comes from the fact that there are 18 letters between the first i and the last n.

You are given a string s of length at least 3 consisting of lowercase English letters. Abbreviate s in the same way.

Constraints

  • 3 ≤ |s| ≤ 100 (|s| denotes the length of s.)
  • s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s

Output

Print the abbreviation of s.

Sample Input 1

internationalization

Sample Output 1

i18n

Sample Input 2

smiles

Sample Output 2

s4s

Sample Input 3

xyz

Sample Output 3

x1z
C - 4-adjacent

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

長さ N の数列 a = (a_1, a_2, ..., a_N) があります。 各 a_i は正の整数です。

すぬけ君の目標は、a の要素を自由に並べ替え、次の条件が成り立つようにすることです。

  • 各 1 ≤ i ≤ N - 1 について、a_i と a_{i + 1} の積は 4 の倍数である。

すぬけ君が目標を達成できるか判定してください。

制約

  • 2 ≤ N ≤ 10^5
  • a_i は整数である。
  • 1 ≤ a_i ≤ 10^9

入力

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

N
a_1 a_2 ... a_N

出力

すぬけ君が目標を達成できるならば Yes を、できないならば No を出力せよ。

入力例 1

3
1 10 100

出力例 1

Yes

例えば、(1, 100, 10) と並べ替えればよいです。

入力例 2

4
1 2 3 4

出力例 2

No

どのように並べ替えても、条件が成り立つようにできません。

入力例 3

3
1 4 1

出力例 3

Yes

最初から条件が成り立っています。

入力例 4

2
1 1

出力例 4

No

入力例 5

6
2 7 1 8 2 8

出力例 5

Yes

Score : 400 points

Problem Statement

We have a sequence of length N, a = (a_1, a_2, ..., a_N). Each a_i is a positive integer.

Snuke's objective is to permute the element in a so that the following condition is satisfied:

  • For each 1 ≤ i ≤ N - 1, the product of a_i and a_{i + 1} is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

  • 2 ≤ N ≤ 10^5
  • a_i is an integer.
  • 1 ≤ a_i ≤ 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If Snuke can achieve his objective, print Yes; otherwise, print No.

Sample Input 1

3
1 10 100

Sample Output 1

Yes

One solution is (1, 100, 10).

Sample Input 2

4
1 2 3 4

Sample Output 2

No

It is impossible to permute a so that the condition is satisfied.

Sample Input 3

3
1 4 1

Sample Output 3

Yes

The condition is already satisfied initially.

Sample Input 4

2
1 1

Sample Output 4

No

Sample Input 5

6
2 7 1 8 2 8

Sample Output 5

Yes
D - Grid Coloring

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

縦 H 行、横 W 列のマス目があります。 すぬけ君は、このマス目を色 1, 2, ..., N で塗り分けようとしています。 このとき、次の条件が成り立つようにします。

  • 各 i (1 ≤ i ≤ N) について、色 i のマスはちょうど a_i 個存在する。 ただし、a_1 + a_2 + ... + a_N = H W である。
  • 各 i (1 ≤ i ≤ N) について、色 i のマスは上下左右に連結である。 すなわち、どの色 i のマスからどの色 i のマスへも、上下左右に隣り合う色 i のマスのみを辿って行き来できる。

条件を満たす塗り分け方をひとつ求めてください。 解は必ず存在することが示せます。

制約

  • 1 ≤ H, W ≤ 100
  • 1 ≤ N ≤ H W
  • a_i ≥ 1
  • a_1 + a_2 + ... + a_N = H W

入力

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

H W
N
a_1 a_2 ... a_N

出力

条件を満たす塗り分け方をひとつ出力せよ。 塗り分け方は次のフォーマットで出力せよ。 ただし、c_{i j} は、上から i 行目、左から j 列目のマスの色である。

c_{1 1} ... c_{1 W}
:
c_{H 1} ... c_{H W}

入力例 1

2 2
3
2 1 1

出力例 1

1 1
2 3

例えば、次の塗り分け方は条件を満たしません。 色 1 のマスが上下左右に連結でないからです。

1 2
3 1

入力例 2

3 5
5
1 2 3 4 5

出力例 2

1 4 4 4 3
2 5 4 5 3
2 5 5 5 3

入力例 3

1 1
1
1

出力例 3

1

Score : 400 points

Problem Statement

We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, ..., N. Here, the following conditions should be satisfied:

  • For each i (1 ≤ i ≤ N), there are exactly a_i squares painted in Color i. Here, a_1 + a_2 + ... + a_N = H W.
  • For each i (1 ≤ i ≤ N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.

Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.

Constraints

  • 1 ≤ H, W ≤ 100
  • 1 ≤ N ≤ H W
  • a_i ≥ 1
  • a_1 + a_2 + ... + a_N = H W

Input

Input is given from Standard Input in the following format:

H W
N
a_1 a_2 ... a_N

Output

Print one way to paint the squares that satisfies the conditions. Output in the following format:

c_{1 1} ... c_{1 W}
:
c_{H 1} ... c_{H W}

Here, c_{i j} is the color of the square at the i-th row from the top and j-th column from the left.

Sample Input 1

2 2
3
2 1 1

Sample Output 1

1 1
2 3

Below is an example of an invalid solution:

1 2
3 1

This is because the squares painted in Color 1 are not 4-connected.

Sample Input 2

3 5
5
1 2 3 4 5

Sample Output 2

1 4 4 4 3
2 5 4 5 3
2 5 5 5 3

Sample Input 3

1 1
1
1

Sample Output 3

1