AtCoder Regular Contest 086

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.

E - Smuggling Marbles

Time Limit: 3 sec / Memory Limit: 512 MB

配点 : 1000 点

問題文

すぬけ君は N+1 頂点の根付き木を持っています。この木の頂点には 0 から N までの番号がついており、頂点 0 はこの木の根です。頂点 i(1 \leq i \leq N) の親は頂点 p_i です。

すぬけ君はこの木の他に、空の箱とビー玉を使って遊んでいます。この遊びはいくつかの頂点にビー玉をそれぞれ 1 つ置いたのち、以下の手順で進行します。

頂点 0 にビー玉が置かれているならば、そのビー玉を箱に移す。
全てのビー玉を現在の頂点から親の頂点に(同時に)移す。
2 つ以上のビー玉が置かれている頂点それぞれについて、その頂点に置かれているビー玉を全て取り除く。
ビー玉が置かれている頂点が存在するならば手順 1 へ、そうでなければ遊びを終了する。

ビー玉の置き方は 2^{N+1} 通りあります。これらそれぞれの場合について 遊びが終了したときに箱に入っているビー玉 の数を求め、その和を {\rm mod} 1,000,000,007 で求めてください。

制約

1 \leq N < 2 \times 10^{5}
0 \leq p_i < i

部分点

400 点分のデータセットでは N < 2000 が成立する

入力

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

N
p_1 p_2 ... p_{N}

出力

答えを出力せよ。

入力例 1

2
0 0

出力例 1

頂点 1 と頂点 2 のどちらにもビー玉を置いたとき、手順 2 により頂点 0 に複数のビー玉が置かれてしまいます。このとき、これらのビー玉は取り除かれるため箱に移動されることはありません。

入力例 2

5
0 1 1 0 4

出力例 2

入力例 3

31
0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23

出力例 3

730395550

答えを { \rm mod} 1,000,000,007 で求めてください。

Score : 1000 points

Problem Statement

Snuke has a rooted tree with N+1 vertices. The vertices are numbered 0 through N, and Vertex 0 is the root of the tree. The parent of Vertex i (1 \leq i \leq N) is Vertex p_i.

Besides this tree, Snuke also has an box which is initially empty and many marbles, and playing with them. The play begins with placing one marble on some of the vertices, then proceeds as follows:

If there is a marble on Vertex 0, move the marble into the box.
Move each marble from the vertex to its parent (all at once).
For each vertex occupied by two or more marbles, remove all the marbles from the vertex.
If there exists a vertex with some marbles, go to Step 1. Otherwise, end the play.

There are 2^{N+1} ways to place marbles on some of the vertices. For each of them, find the number of marbles that will be in the box at the end of the play, and compute the sum of all those numbers modulo 1,000,000,007.

Constraints

1 \leq N < 2 \times 10^{5}
0 \leq p_i < i

Partial Scores

In the test set worth 400 points, N < 2{,}000.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_{N}

Output

Print the answer.

Sample Input 1

2
0 0

Sample Output 1

When we place a marble on both Vertex 1 and 2, there will be multiple marbles on Vertex 0 by step 2. In such a case, these marbles will be removed instead of being moved to the box.

Sample Input 2

5
0 1 1 0 4

Sample Output 2

Sample Input 3

31
0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23

Sample Output 3

730395550

Be sure to compute the sum modulo 1,000,000,007.

F - Shift and Decrement

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1200 点

問題文

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

すぬけ君は，次のいずれかの操作を，好きな順番で，合わせて K 回まで行うことができます．

操作 A: 黒板に書かれている整数すべてを，2 で割って小数点以下を切り捨てたものに置き換える．
操作 B: 黒板に書かれている整数すべてを，1 を引いたものに置き換える．ただし，黒板に 0 が一つでも書かれている場合はこの操作を行うことができない．

すぬけ君が操作を行った後の黒板上の整数の書かれ方として，異なるものは何通りあるかを mod 1,000,000,007 で求めてください．

制約

1 \leq N \leq 200
1 \leq A_i \leq 10^{18}
1 \leq K \leq 10^{18}
A_i, K は整数

入力

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

N K
A_1 A_2 ... A_N

出力

すぬけ君が操作を行った後の黒板上の整数の書かれ方として，異なるものは何通りあるかを mod 1,000,000,007 で出力せよ．

入力例 1

2 2
5 7

出力例 1

黒板上の整数の書かれ方としては，(1, 1), (1, 2), (2, 3), (3, 5), (4, 6), (5, 7) の 6 通りがあります．例えば，(1, 2) は操作 A, 操作 B の順に操作を行うことで得ることができます．

入力例 2

3 4
10 13 22

出力例 2

入力例 3

1 100
10

出力例 3

入力例 4

10 123456789012345678
228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613

出力例 4

164286011

Score : 1200 points

Problem Statement

There are N non-negative integers written on the blackboard: A_1, ..., A_N.

Snuke can perform the following two operations at most K times in total in any order:

Operation A: Replace each integer X on the blackboard with X divided by 2, rounded down to the nearest integer.
Operation B: Replace each integer X on the blackboard with X minus 1. This operation cannot be performed if one or more 0s are written on the blackboard.

Find the number of the different possible combinations of integers written on the blackboard after Snuke performs the operations, modulo 1,000,000,007.

Constraints

1 \leq N \leq 200
1 \leq A_i \leq 10^{18}
1 \leq K \leq 10^{18}
A_i and K are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 ... A_N

Output

Print the number of the different possible combinations of integers written on the blackboard after Snuke performs the operations, modulo 1,000,000,007.

Sample Input 1

2 2
5 7

Sample Output 1

There are six possible combinations of integers on the blackboard: (1, 1), (1, 2), (2, 3), (3, 5), (4, 6) and (5, 7). For example, (1, 2) can be obtained by performing Operation A and Operation B in this order.

Sample Input 2

3 4
10 13 22

Sample Output 2

Sample Input 3

1 100
10

Sample Output 3

Sample Input 4

10 123456789012345678
228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613

Sample Output 4

164286011