A - Century

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le N \le 3000

N

2021

21

200

### 出力例 2

2

Score : 100 points

### Problem Statement

In what century is the year N?

What is century? A century is a period of 100 years. For example, the 1-st century consists of the years 1 through 100, the 2-nd century consists of the years 101 through 200, and so on.

### Constraints

• 1 \le N \le 3000

### Input

Input is given from Standard Input in the following format:

N

### Output

Print the answer as an integer.

2021

### Sample Output 1

21

This year 2021 is in the 21-st century.

200

### Sample Output 2

2

The year 200 is in the 2-nd century.

B - 200th ABC-200

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 整数 N200 の倍数であれば、N200 で割る。
• そうでなければ、整数 N を、N の後ろに文字列として 200 を付け加えた整数に置き換える。
• 例えば、7 を置き換えると 7200 に、1234 を置き換えると 1234200 になります。

### 制約

• 入力は全て整数
• 1 \le N \le 10^5
• 1 \le K \le 20

N K

2021 4

### 出力例 1

50531

N=20214 回操作を行うと、N の値は操作を行うごとに 2021 \rightarrow 2021200 \rightarrow 10106 \rightarrow 10106200 \rightarrow 50531 となります。

40000 2

1

8691 20

### 出力例 3

84875488281

Score : 200 points

### Problem Statement

You are given an integer N.
Do the following operation K times on it and print the resulting integer.

• If N is a multiple of 200, divide it by 200.
• Otherwise, see N as a string and append 200 to the end of it.
• For example, 7 would become 7200 and 1234 would become 1234200.

### Constraints

• All values in input are integers.
• 1 \le N \le 10^5
• 1 \le K \le 20

### Input

Input is given from Standard Input in the following format:

N K

### Output

Print the answer as an integer.

2021 4

### Sample Output 1

50531

Applying the operation on N=2021 results in N becoming 2021 \rightarrow 2021200 \rightarrow 10106 \rightarrow 10106200 \rightarrow 50531.

40000 2

1

8691 20

### Sample Output 3

84875488281

The answer may not fit into the signed 32-bit integer type.

C - Ringo's Favorite Numbers 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i,j) の個数を求めてください。

• 1 \le i < j \le N
• A_i - A_j200 の倍数である。

### 制約

• 入力は全て整数
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9

### 入力

N
A_1 A_2 \dots A_N

### 入力例 1

6
123 223 123 523 200 2000

### 出力例 1

4

(i,j)=(1,3),(1,4),(3,4),(5,6)4 つが条件を満たします。

5
1 2 3 4 5

0

### 入力例 3

8
199 100 200 400 300 500 600 200

### 出力例 3

9

Score : 300 points

### Problem Statement

Ringo loves the integer 200. Solve the problem below for him.
Given a sequence A of N positive integers, find the pair of integers (i, j) satisfying all of the following conditions:

• 1 \le i < j \le N;
• A_i - A_j is a multiple of 200.

### Constraints

• All values in input are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

### Output

Print the answer as an integer.

### Sample Input 1

6
123 223 123 523 200 2000

### Sample Output 1

4

For example, for (i, j) = (1, 3), A_1 - A_3 = 0 is a multiple of 200.
We have four pairs satisfying the conditions: (i,j)=(1,3),(1,4),(3,4),(5,6).

5
1 2 3 4 5

### Sample Output 2

0

There may be no pair satisfying the conditions.

### Sample Input 3

8
199 100 200 400 300 500 600 200

### Sample Output 3

9
D - Happy Birthday! 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の正整数からなる数列 A = (A_1, A_2, \dots, A_N) が与えられます。 以下の条件を全て満たす 2 つの数列 B = (B_1, B_2, \dots, B_x),\ C = (C_1, C_2, \dots, C_y) が存在するか判定し、存在する場合はひとつ出力してください。

• 1 ≤ x, y ≤ N
• 1 \le B_1 < B_2 < \dots < B_{x} \le N
• 1 \le C_1 < C_2 < \dots < C_{y} \le N
• BC は、異なる数列である。
• x ≠ y のとき、または、ある整数 i\ (1 ≤ i ≤ \min(x, y)) が存在して B_i ≠ C_i であるとき、BC は異なるものとする。
• A_{B_1} + A_{B_2} + \dots + A_{B_x}200 で割った余りと A_{C_1} + A_{C_2} + \dots + A_{C_y}200 で割った余りが等しい。

### 制約

• 入力はすべて整数
• 2 \le N \le 200
• 1 \le A_i \le 10^9

### 入力

N
A_1 A_2 \dots A_N

### 出力

Yes
x B_1 B_2 \dots B_x
y C_1 C_2 \dots C_y

なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

### 入力例 1

5
180 186 189 191 218

### 出力例 1

Yes
1 1
2 3 4

B=(1),C=(3,4) とすると、A_1 = 180,\ A_3 + A_4 = 380 となり、この 2 つを 200 で割った余りは等しくなります。

yEs
4 2 3 4 5
3 1 2 5

2
123 523

Yes
1 1
1 2

### 入力例 3

6
2013 1012 2765 2021 508 6971

### 出力例 3

No

Score : 400 points

### Problem Statement

You are given a sequence of N positive integers: A = (A_1, A_2, \dots, A_N). Determine whether there is a pair of sequences B = (B_1, B_2, \dots, B_x), C = (C_1, C_2, \dots, C_y) satisfying all of the conditions, and print one such pair if it exists.

• 1 ≤ x, y ≤ N.
• 1 \le B_1 < B_2 < \dots < B_{x} \le N.
• 1 \le C_1 < C_2 < \dots < C_{y} \le N.
• B and C are different sequences.
• Here, we consider B and C different when x ≠ y or there is an integer i\ (1 ≤ i ≤ \min(x, y)) such that B_i ≠ C_i.
• A_{B_1} + A_{B_2} + \dots + A_{B_x} and A_{C_1} + A_{C_2} + \dots + A_{C_y} are equal modulo 200.

### Constraints

• All values in input are integers.
• 2 \le N \le 200
• 1 \le A_i \le 10^9

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

### Output

If there is no pair of sequences B, C satisfying the conditions, print a single line containing No.
Otherwise, print your choice of B and C in the following format:

Yes
x B_1 B_2 \dots B_x
y C_1 C_2 \dots C_y

The checker is case-insensitive: you can use either uppercase or lowercase letters.

### Sample Input 1

5
180 186 189 191 218

### Sample Output 1

Yes
1 1
2 3 4

For B=(1),C=(3,4), we have A_1 = 180,\ A_3 + A_4 = 380, which are equal modulo 200.
There are other solutions that will also be accepted, such as:

yEs
4 2 3 4 5
3 1 2 5

2
123 523

Yes
1 1
1 2

### Sample Input 3

6
2013 1012 2765 2021 508 6971

### Sample Output 3

No

If there is no pair of sequences satisfying the conditions, print a single line containing No.

E - Patisserie ABC 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

「ABC洋菓子店」で働くパティシエである高橋君は、ケーキを作って AtCoder Beginner Contest 200 を祝うことにしました。

その後、高橋君は、できた N^3 個のケーキを以下の順序で並べました。

• 「綺麗さ」+「おいしさ」+「人気度」が小さいものを、より左に並べる。
• ここまでで順序がつかなければ、「綺麗さ」が小さいものを、より左に並べる。
• ここまでで順序がつかなければ、「おいしさ」が小さいものを、より左に並べる。

このとき、左から K 番目にあるケーキの各パラメータの値を求めてください。

### 制約

• 入力は全て整数
• 1 \le N \le 10^6
• 1 \le K \le N^3

N K

2 5

### 出力例 1

1 2 2

(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)

### 入力例 2

1000000 1000000000000000000

### 出力例 2

1000000 1000000 1000000

9 47

### 出力例 3

3 1 4

Score : 500 points

### Problem Statement

Takahashi, a pastry chef at ABC Confiserie, has decided to make cakes to celebrate AtCoder Beginner Contest 200.

A cake made by Takahashi has three parameters: beauty, taste, and popularity, each of which is represented by an integer between 1 and N (inclusive).

He has made a cake of beauty i, taste j, and popularity k for every triple (i,j,k)\ (1 \le i,j,k \le N).
Then, he has arranged these N^3 cakes in a row, as follows:

• The cakes are in ascending order of sum of beauty, taste, and popularity from left to right.
• For two cakes with the same sum of beauty, taste, and popularity, the cake with the smaller beauty is to the left.
• For two cakes with the same sum and the same beauty, the cake with the smaller taste is to the left.

Find the beauty, taste, and popularity of the K-th cake from the left.

### Constraints

• All values in input are integers.
• 1 \le N \le 10^6
• 1 \le K \le N^3

### Input

Input is given from Standard Input in the following format:

N K

### Output

Print three integers representing the cake's beauty, taste, popularity, in this order, with spaces in between.

2 5

### Sample Output 1

1 2 2

The cakes are in the following order:

(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2).

Here, each triple of integers represents the beauty, taste, and popularity of a cake.

### Sample Input 2

1000000 1000000000000000000

### Sample Output 2

1000000 1000000 1000000

The values in input may be large.

9 47

### Sample Output 3

3 1 4
F - Minflip Summation

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

0, 1, ? のみからなる文字列 S があります。この文字列を K 個連結したものを T とします。
この文字列の ? を全て 01 に置き換えた文字列は、S の中に含まれる ? の数を q 個とすると、全部で 2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を (10^9+7) で割った余りを求めてください。

? を置き換えた後の文字列を T' とします。T' に以下の操作を繰り返し行うことで全ての文字を同じにするとき、必要な最小の操作回数は何回ですか？

• 1 \le l \le r \le |T'| となる整数 l,r を選ぶ。そして、T'l 文字目から r 文字目(両端含む)までの各文字を、0 であれば 1 に、1 であれば 0 に変更する。

### 制約

• 1 \le |S| \le 10^5
• 1 \le K \le 10^9

S
K

101
2

### 出力例 1

2

1 回以下の操作で全ての文字列を同じにすることはできません。

?0?
1

3

### 入力例 3

10111?10??1101??1?00?1?01??00010?0?1??
998244353

### 出力例 3

235562598

Score : 600 points

### Problem Statement

We have a string S consisting of 0, 1, and ?. Let T be the concatenation of K copies of S.
By replacing each ? in T with 0 or 1, we can obtain 2^{Kq} strings, where q is the number of ?s in S. Solve the problem below for each of these strings and find the sum of all the answers, modulo (10^9+7).

Let T' be the string obtained by replacing ? in T. We will repeatedly do the operation below to make all the characters in T the same. At least how many operations are needed for this?

• Choose integers l and r such that 1 \le l \le r \le |T'|, and invert the l-th through r-th characters of T: from 0 and 1 and vice versa.

### Constraints

• 1 \le |S| \le 10^5
• 1 \le K \le 10^9

### Input

Input is given from Standard Input in the following format:

S
K

### Output

Print the answer as an integer.

101
2

### Sample Output 1

2

We have T= 101101, which does not contain ?, so we just need to solve the problem for the only T'= 101101.
We can make all the characters the same in two operations as, for example, 101101 \rightarrow 110011 \rightarrow 111111.
We cannot make all the characters the same in one or fewer operations.

?0?
1

### Sample Output 2

3

We have four candidates for T': 000, 001, 100, and 101.

### Sample Input 3

10111?10??1101??1?00?1?01??00010?0?1??
998244353

### Sample Output 3

235562598

Since the answer can be enormous, find it modulo (10^9+7).