AtCoder Beginner Contest 134

A - Dodecagon

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

半径 a の円に内接する正十二角形の面積は 3a^2 であることが知られています。

整数 r が与えられるので、半径 r の円に内接する正十二角形の面積を求めて下さい。

制約

1 \leqq r \leqq 100
r は整数である。

入力

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

出力

正十二角形の面積を表す整数を出力してください。

入力例 1

出力例 1

正十二角形の面積は 3 \times 4^2 = 48 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 100 points

Problem Statement

It is known that the area of a regular dodecagon inscribed in a circle of radius a is 3a^2.

Given an integer r, find the area of a regular dodecagon inscribed in a circle of radius r.

Constraints

1 \leq r \leq 100
r is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print an integer representing the area of the regular dodecagon.

Sample Input 1

Sample Output 1

The area of the regular dodecagon is 3 \times 4^2 = 48.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

B - Golden Apple

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

一列に並んだ N 本の林檎の木のうちいずれかに黄金の林檎が実ると言われています。

そこで、何人かの監視員を配置してどの林檎の木もいずれかの監視員に監視された状態にしたいです。

それぞれの監視員は N 本の木のうちいずれかに配置します。便宜上、これらの木に 1 から N までの番号をつけます。番号 i の木に配置された監視員は、番号が i-D 以上 i+D 以下のすべての林檎の木を監視します。

条件を満たすために少なくとも何人の監視員を配置する必要があるか求めてください。

制約

入力は全て整数である。
1 \leq N \leq 20
1 \leq D \leq 20

入力

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

N D

出力

条件を満たすために配置する必要のある監視員の人数の最小値を出力せよ。

入力例 1

6 2

出力例 1

例えば、番号 3, 4 の木に 1 人ずつ監視員を配置すれば条件を満たすことができます。

入力例 2

14 3

出力例 2

入力例 3

20 4

出力例 3

Score : 200 points

Problem Statement

There are N apple trees in a row. People say that one of them will bear golden apples.

We want to deploy some number of inspectors so that each of these trees will be inspected.

Each inspector will be deployed under one of the trees. For convenience, we will assign numbers from 1 through N to the trees. An inspector deployed under the i-th tree (1 \leq i \leq N) will inspect the trees with numbers between i-D and i+D (inclusive).

Find the minimum number of inspectors that we need to deploy to achieve the objective.

Constraints

All values in input are integers.
1 \leq N \leq 20
1 \leq D \leq 20

Input

Input is given from Standard Input in the following format:

N D

Output

Print the minimum number of inspectors that we need to deploy to achieve the objective.

Sample Input 1

6 2

Sample Output 1

We can achieve the objective by, for example, placing an inspector under Tree 3 and Tree 4.

Sample Input 2

14 3

Sample Output 2

Sample Input 3

20 4

Sample Output 3

C - Exception Handling

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の数列 A_1, A_2, ..., A_N が与えられます。 1 以上 N 以下の各整数 i に対し、次の問いに答えてください。

数列中の A_i を除く N - 1 個の要素のうちの最大の値を求めよ。

制約

2 \leq N \leq 200000
1 \leq A_i \leq 200000
入力中のすべての値は整数である。

入力

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

N
A_1
:
A_N

出力

N 行出力せよ。i 行目 (1 \leq i \leq N) に、数列中の A_i を除く N - 1 個の要素のうちの最大の値を出力すること。

入力例 1

出力例 1

4
3
4

数列中の A_1 を除く 2 個の要素、A_2 = 4 と A_3 = 3 のうちの最大の値は 4 です。
数列中の A_2 を除く 2 個の要素、A_1 = 1 と A_3 = 3 のうちの最大の値は 3 です。
数列中の A_3 を除く 2 個の要素、A_1 = 1 と A_2 = 4 のうちの最大の値は 4 です。

入力例 2

2
5
5

出力例 2

5
5

Score : 300 points

Problem Statement

You are given a sequence of length N: A_1, A_2, ..., A_N. For each integer i between 1 and N (inclusive), answer the following question:

Find the maximum value among the N-1 elements other than A_i in the sequence.

Constraints

2 \leq N \leq 200000
1 \leq A_i \leq 200000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the maximum value among the N-1 elements other than A_i in the sequence.

Sample Input 1

Sample Output 1

4
3
4

The maximum value among the two elements other than A_1, that is, A_2 = 4 and A_3 = 3, is 4.
The maximum value among the two elements other than A_2, that is, A_1 = 1 and A_3 = 3, is 3.
The maximum value among the two elements other than A_3, that is, A_1 = 1 and A_2 = 4, is 4.

Sample Input 2

2
5
5

Sample Output 2

5
5

D - Preparing Boxes

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個の空の箱が横一列に並んでいます。左から i \ (1 \leq i \leq N) 番目の箱には整数 i が書かれています。

すぬけさんは、それぞれの箱に対してボールを 1 個入れるか何も入れないかを選ぶことができます。

ここで、以下の条件を満たすようなボールの入れ方を、いいボールの入れ方と定めます。

1 以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの個数の和を 2 で割った余りが a_i である。

いいボールの入れ方は存在するでしょうか。存在するならば 1 つ求めてください。

制約

入力は全て整数である。
1 \leq N \leq 2 \times 10^5
a_i は 0 または 1 である。

入力

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

N
a_1 a_2 ... a_N

出力

いいボールの入れ方が存在しないなら -1 を出力せよ。

存在するならば、そのような入れ方のうちの 1 つを以下の形式で出力せよ。

M
b_1 b_2 ... b_M

ここで M はボールを入れる箱の個数を表し、b_1,\ b_2,\ ...,\ b_M はボールを入れる箱に書かれた整数を任意の順番に並べたものである。

入力例 1

3
1 0 0

出力例 1

1
1

1 が書かれた箱だけにボールを入れることを考えます。

1 の倍数が書かれた箱は、1 が書かれた箱、2 が書かれた箱、3 が書かれた箱の 3 個です。これらの箱に入っているボールの個数の和は 1 です。
2 の倍数が書かれた箱は、2 が書かれた箱の 1 個だけです。これらの箱に入っているボールの個数の和は 0 です。
3 の倍数が書かれた箱は、3 が書かれた箱の 1 個だけです。これらの箱に入っているボールの個数の和は 0 です。

以上より、1 が書かれた箱だけにボールを入れるのは、与えられた条件を満たすいいボールの入れ方です。

入力例 2

5
0 0 0 0 0

出力例 2

ボールを 1 つも入れない入れ方が、いい入れ方になる場合もあります。

Score : 400 points

Problem Statement

There are N empty boxes arranged in a row from left to right. The integer i is written on the i-th box from the left (1 \leq i \leq N).

For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.

We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:

For every integer i between 1 and N (inclusive), the total number of balls contained in the boxes with multiples of i written on them is congruent to a_i modulo 2.

Does there exist a good set of choices? If the answer is yes, find one good set of choices.

Constraints

All values in input are integers.
1 \leq N \leq 2 \times 10^5
a_i is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If a good set of choices does not exist, print -1.

If a good set of choices exists, print one such set of choices in the following format:

M
b_1 b_2 ... b_M

where M denotes the number of boxes that will contain a ball, and b_1,\ b_2,\ ...,\ b_M are the integers written on these boxes, in any order.

Sample Input 1

3
1 0 0

Sample Output 1

1
1

Consider putting a ball only in the box with 1 written on it.

There are three boxes with multiples of 1 written on them: the boxes with 1, 2, and 3. The total number of balls contained in these boxes is 1.
There is only one box with a multiple of 2 written on it: the box with 2. The total number of balls contained in these boxes is 0.
There is only one box with a multiple of 3 written on it: the box with 3. The total number of balls contained in these boxes is 0.

Thus, the condition is satisfied, so this set of choices is good.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

Putting nothing in the boxes can be a good set of choices.

E - Sequence Decomposing

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 個の整数からなる数列 A = \{ A_1, A_2, \cdots, A_N \} が与えられます。 N 個それぞれの整数に対して、色を 1 つ選んでその色を塗ります。この時、以下の条件を満たす必要があります:

A_i と A_j (i < j) が同じ色で塗られているならば A_i < A_j が成立する

条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。

制約

1 \leq N \leq 10^5
0 \leq A_i \leq 10^9

入力

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

N
A_1
:
A_N

出力

条件を満たすように色を塗る時、用いる色の数の最小値を出力せよ。

入力例 1

出力例 1

例えば、2, 3 を赤色、1, 4, 5 を青色で塗れば 2 色で条件を満たす塗り方が出来ます。

入力例 2

出力例 2

全ての整数を異なる色で塗るしかありません。

Score : 500 points

Problem Statement

You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}. For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

If A_i and A_j (i < j) are painted with the same color, A_i < A_j.

Find the minimum number of colors required to satisfy the condition.

Constraints

1 \leq N \leq 10^5
0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

Sample Output 1

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

Sample Output 2

We have to paint all the integers with distinct colors.

F - Permutation Oddness

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

{1,\ 2,\ ...,\ n} の順列 p = {p_1,\ p_2,\ ...,\ p_n} の「奇妙さ」を \sum_{i = 1}^n |i - p_i| と定義します。

奇妙さが k であるような {1,\ 2,\ ...,\ n} の順列の個数を 10^9+7 で割った余りを求めてください。

制約

入力は全て整数である。
1 \leq n \leq 50
0 \leq k \leq n^2

入力

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

n k

出力

奇妙さが k であるような {1,\ 2,\ ...,\ n} の順列の個数を 10^9+7 で割った余りを出力せよ。

入力例 1

3 2

出力例 1

{1,\ 2,\ 3} の順列は 6 個存在します。その中で奇妙さが 2 であるのは {2,\ 1,\ 3} と {1,\ 3,\ 2} の 2 つです。

入力例 2

39 14

出力例 2

74764168

Score : 600 points

Problem Statement

Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.

Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Constraints

All values in input are integers.
1 \leq n \leq 50
0 \leq k \leq n^2

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2: {2,\ 1,\ 3} and {1,\ 3,\ 2}.

Sample Input 2

39 14

Sample Output 2

74764168