AtCoder Beginner Contest 068

A - ABCxxx

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

このコンテスト、つまり AtCoder Beginner Contest の略称は、アルファベット 3 文字で ABC となっております。

そして、ABC のうち特定の回を指すときは、何回目の ABC かを 3 桁の数字で表して後ろに付け、ABC680 のように呼びます。例えば ABC680 は、680 回目の ABC のことを指します。

では、N 回目の ABC はどのように表すでしょうか、これを出力するプログラムを作成してください。

制約

100 ≦ N ≦ 999

入力

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

出力

N 回目の ABC の略称を出力する。

入力例 1

出力例 1

ABC100

100 回目の ABC は ABC100 です。

入力例 2

出力例 2

ABC425

入力例 3

出力例 3

ABC999

Score : 100 points

Problem Statement

This contest, AtCoder Beginner Contest, is abbreviated as ABC.

When we refer to a specific round of ABC, a three-digit number is appended after ABC. For example, ABC680 is the 680th round of ABC.

What is the abbreviation for the N-th round of ABC? Write a program to output the answer.

Constraints

100 ≤ N ≤ 999

Input

Input is given from Standard Input in the following format:

Output

Print the abbreviation for the N-th round of ABC.

Sample Input 1

Sample Output 1

ABC100

The 100th round of ABC is ABC100.

Sample Input 2

Sample Output 2

ABC425

Sample Input 3

Sample Output 3

ABC999

B - Break Number

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

高橋君は 2 で割れる数が好きです。

正整数 N が与えられるので、1 以上 N 以下の整数のうち、最も 2 で割れる回数が多いものを求めてください。答えは必ず 1 つに定まります。

なお、2 で割っていき、何回あまりが出ずに割れるかを、2 で割れる回数と呼ぶことにします。

例えば

6 ならば、6 -> 3で、1 回 2 で割れます。
8 ならば、8 -> 4 -> 2 -> 1で、3 回 2 で割れます。
3 ならば、0 回 2 で割れます。

制約

1 ≦ N ≦ 100

入力

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

出力

問題の答えを出力する。

入力例 1

出力例 1

4 は 2 回 2 で割ることができ、これは 1, 2, ..., 7 の中で最も多いです。

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

Score : 200 points

Problem Statement

Takahashi loves numbers divisible by 2.

You are given a positive integer N. Among the integers between 1 and N (inclusive), find the one that can be divisible by 2 for the most number of times. The solution is always unique.

Here, the number of times an integer can be divisible by 2, is how many times the integer can be divided by 2 without remainder.

For example,

6 can be divided by 2 once: 6 -> 3.
8 can be divided by 2 three times: 8 -> 4 -> 2 -> 1.
3 can be divided by 2 zero times.

Constraints

1 ≤ N ≤ 100

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

4 can be divided by 2 twice, which is the most number of times among 1, 2, ..., 7.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

C - Cat Snuke and a Voyage

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋キングダムには、高橋諸島という、N 個の島からなる諸島があります。便宜上、これらの島を島 1、島 2、 ...、島 N と呼ぶことにします。

これらの諸島の間では、船の定期便が M 種類運行されています。定期便はそれぞれ 2 つの島の間を行き来しており、i 種類目の定期便を使うと、島 a_i と島 b_i の間を行き来する事ができます。

すぬけくんは今島 1 にいて、島 N に行きたいと思っています。しかし、島 1 から島 N への定期便は存在しないことがわかりました。なので、定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。

これを代わりに調べてあげてください。

制約

3 ≦ N ≦ 200,000
1 ≦ M ≦ 200,000
1 ≦ a_i < b_i ≦ N
(a_i, b_i) \neq (1, N)
i \neq j ならば (a_i, b_i) \neq (a_j, b_j)

入力

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M

出力

定期便を 2 つ使いたどり着けるならば POSSIBLE、たどり着けないならば IMPOSSIBLE と出力する。

入力例 1

3 2
1 2
2 3

出力例 1

POSSIBLE

入力例 2

出力例 2

IMPOSSIBLE

島 4 へ行くには、定期便を 3 つ使う必要があります。

入力例 3

100000 1
1 99999

出力例 3

IMPOSSIBLE

入力例 4

出力例 4

POSSIBLE

島 1、島 4、島 5 と移動すれば 2 つの定期便で移動可能です。

Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands. For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands. Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N. However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000
1 ≤ M ≤ 200 000
1 ≤ a_i < b_i ≤ N
(a_i, b_i) \neq (1, N)
If i \neq j, (a_i, b_i) \neq (a_j, b_j).

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

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.

D - Decrease (Contestant ver.)

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

長さ N の非負整数列 a_i に対し、数列の最大値が N-1 以下になるまで以下の操作を繰り返し行うことを考えます。

数列のうち最も大きい要素を求める、複数ある場合はどれか 1 つ選ぶ。この要素の値を N 減らす。これ以外の要素の値を 1 増やす。

なお、この操作を行い続けると、いつかは数列の最大値が N-1 以下になることが証明できます。

ここで、整数 K が与えられるので、この操作を行う回数がちょうど K 回になるような数列 a_i を 1 つ求めてください。なお、この問題の入出力の制約下では、かならず 1 つは条件を満たすような数列が存在することが示せます。

制約

0 ≦ K ≦ 50 \times 10^{16}

入力

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

出力

以下の形式で数列を出力する。

N
a_1 a_2 ... a_N

ここで、2 ≦ N ≦ 50, 0 ≦ a_i ≦ 10^{16} + 1000 でなければならない。

入力例 1

出力例 1

4
3 3 3 3

入力例 2

出力例 2

3
1 0 3

入力例 3

出力例 3

2
2 2

[2, 2] -> [0, 3] -> [1, 1] と、2 回操作を行います。

入力例 4

出力例 4

7
27 0 0 0 0 0 0

入力例 5

1234567894848

出力例 5

10
1000 193 256 777 0 1 1192 1234567891011 48 425

Score : 600 points

Problem Statement

We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N-1 or smaller.

Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.

It can be proved that the largest element in the sequence becomes N-1 or smaller after a finite number of operations.

You are given an integer K. Find an integer sequence a_i such that the number of times we will perform the above operation is exactly K. It can be shown that there is always such a sequence under the constraints on input and output in this problem.

Constraints

0 ≤ K ≤ 50 \times 10^{16}

Input

Input is given from Standard Input in the following format:

Output

Print a solution in the following format:

N
a_1 a_2 ... a_N

Here, 2 ≤ N ≤ 50 and 0 ≤ a_i ≤ 10^{16} + 1000 must hold.

Sample Input 1

Sample Output 1

4
3 3 3 3

Sample Input 2

Sample Output 2

3
1 0 3

Sample Input 3

Sample Output 3

2
2 2

The operation will be performed twice: [2, 2] -> [0, 3] -> [1, 1].

Sample Input 4

Sample Output 4

7
27 0 0 0 0 0 0

Sample Input 5

1234567894848

Sample Output 5

10
1000 193 256 777 0 1 1192 1234567891011 48 425