AtCoder Beginner Contest 081

A - Placing Marbles

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。各マスには 0 か 1 が書かれており、マス i には s_i が書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。ビー玉が置かれるマスがいくつあるか求めてください。

制約

s_1, s_2, s_3 は 1 あるいは 0

入力

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

s_{1}s_{2}s_{3}

出力

答えを出力せよ。

入力例 1

出力例 1

マス 1,3 にビー玉が置かれます

入力例 2

出力例 2

ビー玉はどのマスにも置かれません

Score : 100 points

Problem Statement

Snuke has a grid consisting of three squares numbered 1, 2 and 3. In each square, either 0 or 1 is written. The number written in Square i is s_i.

Snuke will place a marble on each square that says 1. Find the number of squares on which Snuke will place a marble.

Constraints

Each of s_1, s_2 and s_3 is either 1 or 0.

Input

Input is given from Standard Input in the following format:

s_{1}s_{2}s_{3}

Output

Print the answer.

Sample Input 1

Sample Output 1

A marble will be placed on Square 1 and 3.

Sample Input 2

Sample Output 2

No marble will be placed on any square.

B - Shift only

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

黒板に N 個の正の整数 A_1, ..., A_N が書かれています．

すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約

1 \leq N \leq 200
1 \leq A_i \leq 10^9

入力

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

N
A_1 A_2 ... A_N

出力

すぬけ君は最大で何回操作を行うことができるかを出力せよ．

入力例 1

3
8 12 40

出力例 1

最初，黒板には [8, 12, 40] が書かれています．このとき，書かれている整数はすべて偶数なので，操作を行うことができます．

1 回操作を行った後，黒板には [4, 6, 20] が書かれています．再び，書かれている整数はすべて偶数なので，操作を行うことができます．

2 回操作を行った後，黒板には [2, 3, 10] が書かれています．この時，奇数 3 が書かれているため，これ以上操作を行うことはできません．

よって，すぬけ君は最大で 2 回操作を行うことができます．

入力例 2

4
5 6 8 10

出力例 2

最初から奇数 5 が書かれているため，すぬけ君は一回も操作を行うことができません．

入力例 3

6
382253568 723152896 37802240 379425024 404894720 471526144

出力例 3

Score : 200 points

Problem Statement

There are N positive integers written on a blackboard: A_1, ..., A_N.

Snuke can perform the following operation when all integers on the blackboard are even:

Replace each integer X on the blackboard by X divided by 2.

Find the maximum possible number of operations that Snuke can perform.

Constraints

1 \leq N \leq 200
1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of operations that Snuke can perform.

Sample Input 1

3
8 12 40

Sample Output 1

Initially, [8, 12, 40] are written on the blackboard. Since all those integers are even, Snuke can perform the operation.

After the operation is performed once, [4, 6, 20] are written on the blackboard. Since all those integers are again even, he can perform the operation.

After the operation is performed twice, [2, 3, 10] are written on the blackboard. Now, there is an odd number 3 on the blackboard, so he cannot perform the operation any more.

Thus, Snuke can perform the operation at most twice.

Sample Input 2

4
5 6 8 10

Sample Output 2

Since there is an odd number 5 on the blackboard already in the beginning, Snuke cannot perform the operation at all.

Sample Input 3

6
382253568 723152896 37802240 379425024 404894720 471526144

Sample Output 3

C - Not so Diverse

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋君は，N 個のボールを持っています．最初，i 番目のボールには，整数 A_i が書かれています．

高橋君は，いくつかのボールに書かれている整数を書き換えて，N 個のボールに書かれている整数が K 種類以下になるようにしたいです．

高橋君は，少なくとも何個のボールの整数を書き換える必要があるでしょうか？

制約

1 \leq K \leq N \leq 200000
1 \leq A_i \leq N
与えられる数値はすべて整数

入力

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

N K
A_1 A_2 ... A_N

出力

高橋君が，少なくとも何個のボールの整数を書き換える必要があるかを出力せよ．

入力例 1

5 2
1 1 2 2 5

出力例 1

例えば，5 番目のボールに書かれている整数を 2 に変更すると，ボールに書かれている整数は 1, 2 の 2 種類となります．一方，まったく書き換えを行わずに，ボールに書かれている整数の種類数を 2 以下にすることはできないので，1 を出力します．

入力例 2

4 4
1 1 2 2

出力例 2

最初，ボールに書かれている整数の種類数は 2 なので，まったく書き換えを行う必要はありません．

入力例 3

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

出力例 3

Score : 300 points

Problem Statement

Takahashi has N balls. Initially, an integer A_i is written on the i-th ball.

He would like to rewrite the integer on some balls so that there are at most K different integers written on the N balls.

Find the minimum number of balls that Takahashi needs to rewrite the integers on them.

Constraints

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

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 ... A_N

Output

Print the minimum number of balls that Takahashi needs to rewrite the integers on them.

Sample Input 1

5 2
1 1 2 2 5

Sample Output 1

For example, if we rewrite the integer on the fifth ball to 2, there are two different integers written on the balls: 1 and 2. On the other hand, it is not possible to rewrite the integers on zero balls so that there are at most two different integers written on the balls, so we should print 1.

Sample Input 2

4 4
1 1 2 2

Sample Output 2

Already in the beginning, there are two different integers written on the balls, so we do not need to rewrite anything.

Sample Input 3

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

Sample Output 3

D - Non-decreasing

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

すぬけ君は長さ N の数列 a を持っています。a の (1-indexedでの) i 番目の数は a_{i} です。

すぬけ君は以下の操作を何度でも行うことができます。

操作：1 以上 N 以下の整数 x,y を選び、a_y に a_x を加算する。

すぬけ君はこの操作を 0 回以上 2N 回以下行って a が下記の条件を満たすようにしたいです。そのような操作手順の一例を示してください。なお、この問題の制約下で、条件を満たすような操作の手順が必ず存在することが証明できます。

条件：a_1 \leq a_2 \leq ... \leq a_{N}

制約

2 \leq N \leq 50
-10^{6} \leq a_i \leq 10^{6}
与えられる入力は全て整数

入力

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

N
a_1 a_2 ... a_{N}

出力

操作回数(これを m とする)を 1 行目に出力せよ。続く m 行のうち i 行目には i 番目の操作で選んだ数 x,y を空白区切りで出力せよ。 m が 0 以上 2N 以下であり、m 回の操作後に a が条件を満たしていれば正解となる。

入力例 1

3
-2 5 -1

出力例 1

2
2 3
3 3

1 番目の操作により a = (-2,5,4) となります
2 番目の操作により a = (-2,5,8) となり、条件を満たします

入力例 2

2
-1 -3

出力例 2

1
2 1

1 番目の操作により a = (-4,-3) となり、条件を満たします

入力例 3

5
0 0 0 0 0

出力例 3

すでに条件を満たしています

Score : 600 points

Problem Statement

Snuke has an integer sequence, a, of length N. The i-th element of a (1-indexed) is a_{i}.

He can perform the following operation any number of times:

Operation: Choose integers x and y between 1 and N (inclusive), and add a_x to a_y.

He would like to perform this operation between 0 and 2N times (inclusive) so that a satisfies the condition below. Show one such sequence of operations. It can be proved that such a sequence of operations always exists under the constraints in this problem.

Condition: a_1 \leq a_2 \leq ... \leq a_{N}

Constraints

2 \leq N \leq 50
-10^{6} \leq a_i \leq 10^{6}
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Let m be the number of operations in your solution. In the first line, print m. In the i-th of the subsequent m lines, print the numbers x and y chosen in the i-th operation, with a space in between. The output will be considered correct if m is between 0 and 2N (inclusive) and a satisfies the condition after the m operations.

Sample Input 1

3
-2 5 -1

Sample Output 1

2
2 3
3 3

After the first operation, a = (-2,5,4).
After the second operation, a = (-2,5,8), and the condition is now satisfied.

Sample Input 2

2
-1 -3

Sample Output 2

1
2 1

After the first operation, a = (-4,-3) and the condition is now satisfied.

Sample Input 3

5
0 0 0 0 0

Sample Output 3

The condition is satisfied already in the beginning.