AtCoder Daily Training MEDIUM 2023/11/28 17:30start

C - Base 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

0 と 1 からなる長さ 64 の数列 A=(A_0,A_1,\dots,A_{63}) が与えられます。

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} を求めてください。

制約

A_i は 0 または 1

入力

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

A_0 A_1 \dots A_{63}

出力

答えを整数として出力せよ。

入力例 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13 です。

入力例 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

出力例 2

766067858140017173

Score : 200 points

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

A_i is 0 or 1.

Input

The input is given from Standard Input in the following format:

A_0 A_1 \dots A_{63}

Output

Print the answer as an integer.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

D - 1D Pawn

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。 i 回目の操作では次の操作を行います。

左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。

Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。

制約

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
入力はすべて整数

入力

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

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

出力

K 個の整数を空白区切りで一行に出力せよ。ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。

入力例 1

5 3 5
1 3 4
3 3 1 1 2

出力例 1

2 4 5

最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。

左から 3 番目のコマはマス 4 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。コマはマス 1, 3, 5 にある状態になります。
左から 3 番目のコマはマス 5 にあります。これは一番右のマスなので、何も行いません。コマはマス 1, 3, 5 にある状態のままです。
左から 1 番目のコマはマス 1 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。コマはマス 2, 3, 5 にある状態になります。
左から 1 番目のコマはマス 2 にあります。これは一番右のマスでありませんが、その 1 つ右のマス（マス 3 ）にコマが置かれているため、何も行いません。コマはマス 2, 3, 5 にある状態のままです。
左から 2 番目のコマはマス 3 にあります。これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。コマはマス 2, 4, 5 にある状態になります。

よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。

入力例 2

2 2 2
1 2
1 2

出力例 2

1 2

入力例 3

10 6 9
1 3 5 7 8 9
1 2 3 4 5 6 5 6 2

出力例 3

2 5 6 7 9 10

Score : 200 points

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

If the L_i-th piece from the left is on its rightmost square, do nothing.
Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

Output

Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

10 6 9
1 3 5 7 8 9
1 2 3 4 5 6 5 6 2

Sample Output 3

2 5 6 7 9 10

E - Four Variables

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N が与えられます。
正整数の組 (A,B,C,D) であって、AB + CD = N を満たすものの個数を求めてください。

なお、本問の制約の下、答えが 9 \times 10^{18} 以下であることが証明できます。

制約

2 \leq N \leq 2 \times 10^5
N は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

(A,B,C,D) として以下の 8 個が考えられます。

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

2 \leq N \leq 2 \times 10^5
N is an integer.

Input

The input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

Here are the eight desired quadruples.

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

F - K Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A=(a_1,\ldots,a_N) があります。また、整数 K が与えられます。

あなたは次の操作を 0 回以上何度でも行えます。

1 \leq i \leq N-K を満たす整数 i を選び、a_i と a_{i+K} の値を入れ替える。

A を昇順に並べ替えることが出来るかどうかを判定してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq K \leq N-1
1 \leq a_i \leq 10^9
入力はすべて整数

入力

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

N K
a_1 \ldots a_N

出力

A を昇順に並び替えることが出来るならば Yes と、出来ないならば No と出力せよ。

入力例 1

5 2
3 4 1 3 4

出力例 1

Yes

次のように操作をすることで A を昇順に並び替えることが出来ます。

i=1 とし、a_1 と a_3 の値を入れ替える。数列は (1,4,3,3,4) となる。
i=2 とし、a_2 と a_4 の値を入れ替える。数列は (1,3,3,4,4) となる。

入力例 2

5 3
3 4 1 3 4

出力例 2

No

入力例 3

7 5
1 2 3 4 5 5 10

出力例 3

Yes

操作を行う必要が無い場合もあります。

Score : 300 points

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq K \leq N-1
1 \leq a_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 \ldots a_N

Output

If it is possible to sort A in ascending order, print Yes; otherwise, print No.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

G - AND and SUM

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

T 個のテストケースについて、以下の問題を解いてください。

非負整数 a,s が与えられます。以下の条件を両方とも満たす非負整数の組 (x,y) は存在しますか？

x\ \text{AND}\ y=a

x+y=s

\text{AND} とは

非負整数 n, m の bit ごとの論理積 n\ \text{AND}\ m は、以下のように定義されます。

n\ \text{AND}\ m を二進表記した際の 2^k \, (k \geq 0) の位の数は、n, m を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。

例えば、4\ \text{AND}\ 6 = 4 となります（二進表記すると: 100\ \text{AND}\ 110 = 100）。

制約

1 \leq T \leq 10^5
0 \leq a,s \lt 2^{60}
入力はすべて整数

入力

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

その後、 T 個のテストケースが続く。各テストケースは以下の形式で与えられる。

a s

出力

T 行出力せよ。i\ (1 \leq i \leq T) 行目には、i 番目に与えられるテストケースについて問題文中の条件を両方とも満たす非負整数の組 (x,y) が存在するなら Yes を、存在しないなら No を出力せよ。

入力例 1

2
1 8
4 2

出力例 1

Yes
No

1 番目のテストケースにおいては、(x,y)=(3,5) などが条件を満たします。

2 番目のテストケースにおいては、条件を満たす非負整数の組 (x,y) は存在しません。

入力例 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

出力例 2

No
Yes
Yes
No

Score : 400 points

Problem Statement

Solve the following problem for T test cases.

Given are non-negative integers a and s. Is there a pair of non-negative integers (x,y) that satisfies both of the conditions below?

x\ \text{AND}\ y=a

x+y=s

What is bitwise \mathrm{AND}?

The bitwise \mathrm{AND} of integers A and B, A\ \mathrm{AND}\ B, is defined as follows:

When A\ \mathrm{AND}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if those of A and B are both 1, and 0 otherwise.

For example, we have 4\ \mathrm{AND}\ 6 = 4 (in base two: 100\ \mathrm{AND}\ 110 = 100).

Constraints

1 \leq T \leq 10^5
0 \leq a,s \lt 2^{60}
All values in input are integers.

Input

Input is given from Standard Input. The first line is in the following format:

Then, T test cases follow. Each test case is in the following format:

a s

Output

Print T lines. The i-th line (1 \leq i \leq T) should contain Yes if, in the i-th test case, there is a pair of non-negative integers (x,y) that satisfies both of the conditions in the Problem Statement, and No otherwise.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as (x,y)=(3,5) satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No