AtCoder Regular Contest 139

A - Trailing Zeros

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正の整数 x に対して、 x を 2 進表記したときの末尾に連なる 0 の個数を \mathrm{ctz}(x) と定めます。
たとえば 8 の 2 進表記は 1000 なので \mathrm{ctz}(8)=3 で、5 の 2 進表記は 101 なので \mathrm{ctz}(5)=0 です。

非負整数からなる数列 T = (T_1,T_2,\dots,T_N) が与えられます。
正の整数からなる数列 A = (A_1,A_2,\dots,A_N) を以下の条件を満たすように自由に構成します。

A_1 \lt A_2 \lt \cdots \lt A_{N-1} \lt A_N である。すなわち A は狭義単調増加である。
1 \leq i \leq N を満たす全ての整数 i に対して \mathrm{ctz}(A_i) = T_i が成り立つ。

このとき A_N としてあり得る値の最小値を答えてください。

制約

1 \leq N \leq 10^5
0 \leq T_i \leq 40
入力される値はすべて整数

入力

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

N
T_1 T_2 \dots T_N

出力

答えを出力せよ。

入力例 1

4
0 1 3 2

出力例 1

たとえば A_1=3,A_2=6,A_3=8,A_4=12 は条件を満たします。
A_4 を 11 以下にすることはできないので答えは 12 になります。

入力例 2

5
4 3 2 1 0

出力例 2

入力例 3

1
40

出力例 3

1099511627776

答えが 32 bit 整数に収まらない場合があるのに注意してください。

入力例 4

8
2 0 2 2 0 4 2 4

出力例 4

Score : 300 points

Problem Statement

For a positive integer x, let \mathrm{ctz}(x) be the number of trailing zeros in the binary representation of x.
For example, we have \mathrm{ctz}(8)=3 because the binary representation of 8 is 1000, and \mathrm{ctz}(5)=0 because the binary representation of 5 is 101.

You are given a sequence of non-negative integers T = (T_1,T_2,\dots,T_N).
Consider making a sequence of positive integers A = (A_1, A_2, \dots, A_N) of your choice so that it satisfies the following conditions.

A_1 \lt A_2 \lt \cdots \lt A_{N-1} \lt A_N holds. In other words, A is strictly increasing.
\mathrm{ctz}(A_i) = T_i holds for every integer i such that 1 \leq i \leq N.

What is the minimum possible value of A_N here?

Constraints

1 \leq N \leq 10^5
0 \leq T_i \leq 40
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 T_2 \dots T_N

Output

Print the answer.

Sample Input 1

4
0 1 3 2

Sample Output 1

For example, A_1=3,A_2=6,A_3=8,A_4=12 satisfy the conditions.
A_4 cannot be 11 or less, so the answer is 12.

Sample Input 2

5
4 3 2 1 0

Sample Output 2

Sample Input 3

1
40

Sample Output 3

1099511627776

Note that the answer may not fit into a 32-bit integer.

Sample Input 4

8
2 0 2 2 0 4 2 4

Sample Output 4

B - Make N

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 P=0 があります。以下の 3 種類の操作を任意の回数選んで行うことで P=N とするとき、コストの総和の最小値を求めてください。

P を 1 増やす。この操作はコストが X かかる。
P を A 増やす。この操作はコストが Y かかる。
P を B 増やす。この操作はコストが Z かかる。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \le T \le 100
1 \le N,A,B,X,Y,Z \le 10^9
入力は全て整数である。

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられます。

N\ A\ B\ X\ Y\ Z

出力

T 行出力してください。i 行目には、\mathrm{case}_i に対する答えを出力してください。

入力例 1

5
10 3 5 2 3 6
10 3 5 1 1000000000 1000000000
139 2 139 1 1 1
139 1 1 1 1 1
139 7 10 3845 26982 30923

出力例 1

1 個目のテストケースでは、例えば以下のようにするとコスト 11 で P=10 とでき、これが最適です。

P を 3 増やす。P=3 となる。コストが 3 かかる。
P を 1 増やす。P=4 となる。コストが 2 かかる。
P を 3 増やす。P=7 となる。コストが 3 かかる。
P を 3 増やす。P=10 となる。コストが 3 かかる。

Score : 500 points

Problem Statement

We have an integer P=0. Find the minimum total cost to make P=N by doing the following three kinds of operations any number of times in any order.

Increase P by 1, at a cost of X.
Increase P by A, at a cost of Y.
Increase P by B, at a cost of Z.

Solve each of the T test cases given to you.

Constraints

1 \le T \le 100
1 \le N,A,B,X,Y,Z \le 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is in the following format:

N\ A\ B\ X\ Y\ Z

Output

Print T lines, the i-th of which should contain the answer to \mathrm{case}_i.

Sample Input 1

5
10 3 5 2 3 6
10 3 5 1 1000000000 1000000000
139 2 139 1 1 1
139 1 1 1 1 1
139 7 10 3845 26982 30923

Sample Output 1

In the first test case, below is one way to make P=10 at the cost of 11, which is optimal.

Increase P by 3, making P=3, at a cost of 3.
Increase P by 1, making P=4, at a cost of 2.
Increase P by 3, making P=7, at a cost of 3.
Increase P by 3, making P=10, at a cost of 3.

C - One Three Nine

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

正の整数 N,M が与えられます。

以下を満たす整数の組の列 ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) を素晴らしい整数の組の列ということとします。

1 \le X_i \le N
1 \le Y_i \le M
i \neq j ならば X_i+3Y_i \neq X_j+3Y_j かつ 3X_i+Y_i \neq 3X_j+Y_j

素晴らしい整数の組の列のうち、長さ K が最大であるものを 1 個構築してください。

制約

1 \le N,M \le 10^5
入力は全て整数である。

入力

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

N M

出力

以下の形式で出力してください。

K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

ここで、K は素晴らしい整数の組の列の長さの最大値とします。そして、((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) は素晴らしい整数の組の列である必要があります。答えが複数存在する場合、どれを出力しても正解とみなされます。

入力例 1

3 4

出力例 1

N=3,M=4 の時、長さ 11 以上の素晴らしい整数の組の列は存在せず、かつ上記の出力は素晴らしい整数の組の列であるためこの出力は正当です。

Score : 700 points

Problem Statement

You are given positive integers N and M.

Let us call a sequence of pairs of integers ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) wonderful when it satisfies the following.

1 \le X_i \le N
1 \le Y_i \le M
X_i+3Y_i \neq X_j+3Y_j and 3X_i+Y_i \neq 3X_j+Y_j, if i \neq j.

Make a wonderful sequence of pairs of integers whose length, K, is the maximum possible.

Constraints

1 \le N,M \le 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print your answer in the following format:

K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

Here, K should be the maximum possible length of a wonderful sequence of pairs of integers, and ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) should be a wonderful sequence of pairs of integers. If multiple solutions exist, printing any of them is accepted.

Sample Input 1

3 4

Sample Output 1

For N=3, M=4, there is no wonderful sequence of pairs of integers whose length is 11 or longer, and the above sequence of pairs of integers is wonderful, so this output is valid.

D - Priority Queue 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

要素数が N の整数の多重集合 A=\lbrace A_1,A_2,...,A_N \rbrace が与えられます。A の要素は全て 1 以上 M 以下であることが保証されています。

以下の操作を K 回繰り返します。

1 以上 M 以下の整数を選び、A に追加する。その後、A の中で X 番目に小さい値を 1 個削除する。

A の中で X 番目に小さい値とは、A の要素を単調非減少になるように一列に並べたとき、先頭から X 番目にくる値のことです。

1 以上 M 以下の値を K 回選ぶ方法は M^K 通りありますが、その全てに対して操作終了後の A の要素の総和を求めたとします。これらの M^K 個の値の総和を 998244353 で割ったあまりを求めてください。

制約

1 \le N,M,K \le 2000
1 \le X \le N+1
1 \le A_i \le M
入力は全て整数である。

入力

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

N M K X
A_1 A_2 \dots A_N

出力

答えを出力してください。

入力例 1

2 4 2 1
1 3

出力例 1

初め A=\{1,3\} です。操作の例としては以下のようなものが考えられます。

A に 4 を追加する。A=\{1,3,4\} となる。A の 1 番目に小さい値を削除する。A=\{3,4\} となる。
A に 3 を追加する。A=\{3,3,4\} となる。A の 1 番目に小さい値を削除する。A=\{3,4\} となる。

この場合、操作後の A の要素の総和は 3+4=7 となります。

入力例 2

5 9 6 3
3 7 1 9 9

出力例 2

15411789

Score : 700 points

Problem Statement

You are given a multiset of integers with N elements: A=\lbrace A_1,A_2,...,A_N \rbrace. It is guaranteed that every element of A is between 1 and M (inclusive).

Let us repeat the following operation K times.

Choose an integer between 1 and M (inclusive) and add it to A. Then, delete the X-th smallest value in A.

Here, the X-th smallest value in A is the X-th value from the front in the sequence of the elements of A sorted in non-decreasing order.

There are M^K ways to choose an integer K times between 1 and M. Assume that, for each of these ways, we have found the sum of the elements of A after the operations with the corresponding choices. Find the sum, modulo 998244353, of the M^K values computed.

Constraints

1 \le N,M,K \le 2000
1 \le X \le N+1
1 \le A_i \le M
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K X
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

2 4 2 1
1 3

Sample Output 1

We start with A=\{1,3\}. Here is an example of how we do the operations.

Add 4 to A, making A=\{1,3,4\}. Then, delete the 1-st smallest value, making A=\{3,4\}.
Add 3 to A, making A=\{3,3,4\}. Then, delete the 1-st smallest value, making A=\{3,4\}.

In this case, the sum of the elements of A after the operations is 3+4=7.

Sample Input 2

5 9 6 3
3 7 1 9 9

Sample Output 2

15411789

E - Wazir

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 番目、左から j 番目のマスを (i,j) と表します。
このグリッドはトーラスであるとみなします。つまり、上下左右の 4 方向に隣り合っているマス同士に加えて、以下のマス同士も隣り合っているとみなします。

すべての 1 \leq i \leq H を満たす整数 i について (i,1) と (i,W)
すべての 1 \leq j \leq W を満たす整数 j について (1,j) と (H,j)

グリッドのマスにいくつかのコマを置くことを考えます。ただし各マスに置けるコマは高々 1 個であり、コマを置いたマス同士が隣り合ってはいけません。
コマを置ける個数の最大値を L とします。コマを L 個置く方法が何通りあるかを 998244353 で割ったあまりを求めてください。

制約

2 \leq H \leq 10^5
2 \leq W \leq 10^{10}
H,W は整数

入力

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

H W

出力

答えを出力せよ。

入力例 1

3 2

出力例 1

条件を満たす配置は次の 6 通りです。ここで、# はコマが置かれているマス、. はコマが置かれていないマスを意味します。

#.   #.   .#   .#   ..   ..
.#   ..   #.   ..   #.   .#
..   .#   ..   #.   .#   #.

入力例 2

139 424

出力例 2

148734121

入力例 3

12345 1234567890

出力例 3

227996418

Score : 800 points

Problem Statement

We have a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Assume that this grid is a torus; that is, in addition to the pairs of squares horizontally or vertically adjacent to each other, assume the following pairs of squares to be adjacent to each other.

(i,1) and (i,W), for every integer i such that 1 \leq i \leq H.
(1,j) and (H,j), for every integer j such that 1 \leq j \leq W.

Consider placing some number of pieces on the squares in the grid. Here, there can be at most one piece on each square, and there cannot be two pieces on adjacent squares.
Let L be the maximum number of pieces that can be placed. Find the number of ways, modulo 998244353, to place L pieces.

Constraints

2 \leq H \leq 10^5
2 \leq W \leq 10^{10}
H and W are integers.

Input

Input is given from Standard Input in the following format:

H W

Output

Print the answer.

Sample Input 1

3 2

Sample Output 1

The following six placements satisfy the condition. Here, # and . represent a square with and without a piece, respectively.

#.   #.   .#   .#   ..   ..
.#   ..   #.   ..   #.   .#
..   .#   ..   #.   .#   #.

Sample Input 2

139 424

Sample Output 2

148734121

Sample Input 3

12345 1234567890

Sample Output 3

227996418

F - Many Xor Optimization Problems

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

PCT 君は以下の問題を作りました。

Xor Optimization Problem
長さ N の非負整数列 A_1,A_2,...,A_N が与えられる。A の要素を好きな個数選ぶとき、選んだ値の \mathrm{XOR} が取りうる最大値はいくらか？

この問題は、Nyaan さんにとっては簡単だったため PCT 君は以下のように改題しました。

Many Xor Optimization Problems
長さ N かつ全ての要素が 0 以上 2^M-1 以下である整数列は 2^{NM} 通り存在しますが、その全てに対して Xor Optimization Problem を解いた時の解の総和を 998244353 で割ったあまりを求めてください。

Many Xor Optimization Problems を解いてください。

\mathrm{XOR} とは

非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。

A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

1 \le N,M \le 250000
入力は全て整数である。

入力

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

N M

出力

答えを出力してください。

入力例 1

2 1

出力例 1

長さが 2 かつ全ての要素が 0 以上 1 以下である整数列全てに対して Xor Optimization Problem を解きます。

A=(0,0) の時の解は 0
A=(0,1) の時の解は 1
A=(1,0) の時の解は 1
A=(1,1) の時の解は 1

よって、0+1+1+1=3 が解となります。

入力例 2

3 4

出力例 2

入力例 3

1234 5678

出力例 3

495502261

Score : 1000 points

Problem Statement

PCT made the following problem.

Xor Optimization Problem
You are given a sequence of non-negative integers of length N: A_1,A_2,...,A_N. When it is allowed to choose any number of elements in A, what is the maximum possible \mathrm{XOR} of the chosen values?

Nyaan thought it was too easy and revised it to the following.

Many Xor Optimization Problems
There are 2^{NM} sequences of length N consisting of integers between 0 and 2^M-1. Find the sum, modulo 998244353, of the answers to Xor Optimization Problem for all those sequences.

Solve Many Xor Optimization Problems.

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:

When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.

For example, we have 3 \oplus 5 = 6 (in base two: 011 \oplus 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.

Constraints

1 \le N,M \le 250000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

2 1

Sample Output 1

We are to solve Xor Optimization Problem for all sequences of length 2 consisting of integers between 0 and 1.

The answer for A=(0,0) is 0.
The answer for A=(0,1) is 1.
The answer for A=(1,0) is 1.
The answer for A=(1,1) is 1.

Thus, the final answer is 0+1+1+1=3.

Sample Input 2

3 4

Sample Output 2

Sample Input 3

1234 5678

Sample Output 3

495502261