AtCoder Regular Contest 127

A - Leading 1s

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 x を 10 進表記した時，先頭に並ぶ 1 の個数を f(x) で表すことにします．例えば，f(1)=1,f(2)=0,f(10)=1,f(11)=2,f(101)=1 です．

整数 N が与えられるので，f(1)+f(2)+\cdots+f(N) の値を求めてください．

制約

1 \leq N \leq 10^{15}
入力される値はすべて整数である

入力

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

出力

答えを出力せよ．

入力例 1

出力例 1

f(2)=f(3)=\cdots =f(9)=0 です．答えは，f(1)+f(10)+f(11)=4 です．

入力例 2

出力例 2

入力例 3

987654321

出力例 3

123456789

Score : 300 points

Problem Statement

For an integer x, let f(x) be the number of leading ones in the decimal notation of x. For example, we have f(1)=1,f(2)=0,f(10)=1,f(11)=2,f(101)=1.

Given an integer N, find f(1)+f(2)+\cdots+f(N).

Constraints

1 \leq N \leq 10^{15}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

We have f(2)=f(3)=\cdots =f(9)=0. The answer is f(1)+f(10)+f(11)=4.

Sample Input 2

Sample Output 2

Sample Input 3

987654321

Sample Output 3

123456789

B - Ternary Strings

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N,L が与えられます．以下の条件をすべて満たす 3N 個の文字列の組 (S_1,S_2,\cdots,S_{3N}) を一つ求めてください．

S_i は 0, 1, 2 からなる長さ L の文字列である．
S_i はすべて互いに異なる．
すべての j (1 \leq j \leq L) および c=0, 1, 2 について，次が成り立つ．
- S_i のうち，j 文字目が c であるようなものはちょうど N 個存在する．
S_1,S_2,\cdots,S_{3N} の中で，辞書順で最も大きい文字列を t で表すことにする．このときの t は，t としてありうる文字列の中で辞書順最小の文字列である．

制約

1 \leq N \leq 5 \times 10^4
1 \leq L \leq 15
3N \leq 3^L
入力される値はすべて整数である

入力

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

N L

出力

以下の形式で答えを出力せよ．

S_1
S_2
\vdots
S_{3N}

なお，条件を満たす解が複数存在する場合，どれを出力しても正解とみなされる．

入力例 1

2 2

出力例 1

この出力例はすべての条件を満たしています．

例えば，2 文字目が 0 であるような文字列は 2 個存在しています．

また，この例では t=21 ですが，t がこれより辞書順で小さくなることはありません．

Score : 500 points

Problem Statement

Given are integers N and L. Find a tuple of 3N strings (S_1,S_2,\cdots,S_{3N}) that satisfies all of the following conditions.

S_i is a string of length L consisting of 0, 1, 2.
All S_i are pairwise distinct.
For every j (1 \leq j \leq L) and every c=0, 1, 2, the following holds.
- For exactly N of the strings S_i, the j-th character is c.
Let t be the lexicographically largest string among S_1,S_2,\cdots,S_{3N}. t for this tuple is the lexicographically smallest among all strings that t can be.

Constraints

1 \leq N \leq 5 \times 10^4
1 \leq L \leq 15
3N \leq 3^L
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N L

Output

Print the answer in the following format:

S_1
S_2
\vdots
S_{3N}

If there are multiple solutions satisfying the conditions, any of them will be accepted.

Sample Input 1

2 2

Sample Output 1

This Sample Output satisfies all conditions.

For example, there are two strings whose second character is 0.

Also, we have t=21 in this sample, and t is never lexicographically smaller than this.

C - Binary Strings

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

すぬけくんは黒板に 1 以上 (2^N-1) 以下の整数をすべて書きました．ただし，整数は 2 進表記で書きました．

黒板に書かれた整数を文字列として見た時，辞書順で X 番目に小さい文字列を求めてください．

なお，入力において N は 10 進法で与えられますが，X は 2 進法で与えられます．

制約

1 \leq N \leq 10^6
1 \leq X \leq 2^N-1
X は 2 進法で与えられる．

入力

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

N
X

出力

答えを出力せよ．

入力例 1

3
101

出力例 1

黒板に書かれた文字列を辞書順に並べると，1,10,100,101,11,110,111 です．また X=101(2\mathrm{進})=5(10\mathrm{進}) です．よって，答えは 11 になります．

入力例 2

10
10100011

出力例 2

1001001111

入力例 3

1000000
11111

出力例 3

1000000000000000000000000000000

Score : 500 points

Problem Statement

Snuke has written on a blackboard every integer from 1 through (2^N-1), in binary.

Find the X-th lexicographically smallest string when seeing the integers on the blackboard as strings.

Here, the input gives N in decimal, but X in binary.

Constraints

1 \leq N \leq 10^6
1 \leq X \leq 2^N-1
X is in binary.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print the answer.

Sample Input 1

3
101

Sample Output 1

The strings written on the blackboard in lexicographical order are 1, 10, 100, 101, 11, 110, 111. Additionally, we have X=101(\mathrm{binary})=5(\mathrm{decimal}). Thus, the answer is 11.

Sample Input 2

10
10100011

Sample Output 2

1001001111

Sample Input 3

1000000
11111

Sample Output 3

1000000000000000000000000000000

D - Sum of Min of Xor

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 (A_1,A_2,\cdots,A_N) および (B_1,B_2,\cdots,B_N) が与えられます．

\sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j) の値を求めてください．ただしここで，\oplus はビットごとの排他的論理和を表します．

制約

1 \leq N \leq 250000
0 \leq A_i,B_i < 2^{18}
入力される値はすべて整数である

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

答えを出力せよ．

入力例 1

3
1 2 3
4 5 6

出力例 1

\min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
\min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
\min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1

よって，答えは 1+2+1=4 になります．

入力例 2

4
1 2 3 4
1 2 3 4

出力例 2

入力例 3

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

出力例 3

Score : 700 points

Problem Statement

Given are sequences of N integers each: (A_1,A_2,\cdots,A_N) and (B_1,B_2,\cdots,B_N).

Find \sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j), where \oplus denotes the bitwise XOR.

Constraints

1 \leq N \leq 250000
0 \leq A_i,B_i < 2^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

Print the answer.

Sample Input 1

3
1 2 3
4 5 6

Sample Output 1

\min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
\min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
\min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1

Thus, the answer is 1+2+1=4.

Sample Input 2

4
1 2 3 4
1 2 3 4

Sample Output 2

Sample Input 3

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

Sample Output 3

E - Priority Queue

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ A+B の整数列 (X_1,X_2,\cdots,X_{A+B}) が与えられます． X はちょうど A 個の 1 とちょうど B 個の 2 を含みます．

すぬけくんは集合 s を持っており，最初 s は空です．彼は今から，A+B 回の操作を行います． i 回目の操作は以下のような行動です．

X_i=1 の時: 1 \leq v \leq A を満たす整数 v を選び，s に追加する．ただし，今までの操作で選んだことのある整数は v として選べない．
X_i=2 の時: s の中で最大値となる要素を削除する．なお，この操作の直前に s が空でないことは入力から保証される．

最終的な s としてありうる集合は何通りあるでしょうか？答えを 998244353 で割った余りを求めてください．

制約

1 \leq A \leq 5000
0 \leq B \leq A-1
1 \leq X_i \leq 2
X_i=1 を満たす i がちょうど A 個存在する．
X_i=2 を満たす i がちょうど B 個存在する．
X_i=2 の操作を行う直前で s は空ではない．
入力される値はすべて整数である．

入力

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

A B
X_1 X_2 \cdots X_{A+B}

出力

答えを 998244353 で割った余りを出力せよ．

入力例 1

3 1
1 1 2 1

出力例 1

最終的な s としてありうる状態は，s=\{1,2\},\{1,3\} の 2 通りです．

例えば，以下のように操作すると，最終的に s=\{1,3\} となります．

i=1: s に 2 を追加する．
i=2: s に 1 を追加する．
i=3: s から 2 を削除する．
i=4: s に 3 を追加する．

入力例 2

20 6
1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 1 1 1

出力例 2

Score : 800 points

Problem Statement

Given is a sequence of A+B integers (X_1,X_2,\cdots,X_{A+B}), which contains exactly A ones and exactly B twos.

Snuke has a set s, which is initially empty. He is going to do A+B operations. The i-th operation is as follows.

If X_i=1: Choose an integer v such that 1 \leq v \leq A and add it to s. Here, v must not be an integer that was chosen in a previous operation.
If X_i=2: Delete from s the element with the largest value. The input guarantees that s is not empty just before this operation.

How many sets are there that can be the final state of s? Find the count modulo 998244353.

Constraints

1 \leq A \leq 5000
0 \leq B \leq A-1
1 \leq X_i \leq 2
X_i=1 for exactly A indices i.
X_i=2 for exactly B indices i.
s will not be empty just before an operation with X_i=2.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B
X_1 X_2 \cdots X_{A+B}

Output

Print the answer modulo 998244353.

Sample Input 1

3 1
1 1 2 1

Sample Output 1

There are two possible final states of s: s=\{1,2\},\{1,3\}.

For example, the following sequence of operations results in s=\{1,3\}.

i=1: Add 2 to s.
i=2: Add 1 to s.
i=3: Delete 2 from s.
i=4: Add 3 to s.

Sample Input 2

20 6
1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 1 1 1

Sample Output 2

F - ±AB

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

整数 A,B,V,M が与えられます．ここで，A と B は互いに素であることが保証されます．また，あなたは整数 x を持っています．最初，x=V です．

あなたは，以下の 4 種類の操作を好きな順序で好きな回数繰り返すことができます．

x の値を，x+A で置き換える．
x の値を，x-A で置き換える．
x の値を，x+B で置き換える．
x の値を，x-B で置き換える．

ただし，操作のどの瞬間においても，0 \leq x \leq M が成立している必要があります．

この条件の元で，x がとりうる値が何種類あるかを求めてください．

一つの入力ファイルにつき，T 個のテストケースを解いてください．

制約

1 \leq T \leq 10^5
1 \leq A < B \leq M \leq 10^9
A と B は互いに素である．
0 \leq V \leq M
入力される値はすべて整数である．

入力

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

T
case_1
case_2
\vdots
case_3

各ケースは以下の形式で与えられる．

A B V M

出力

各ケースについて答えを出力せよ．

入力例 1

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

出力例 1

1 つ目のテストケースでは，x=0,2,3,5 の 4 通りの値が考えられます．

Score : 1000 points

Problem Statement

Given are integers A, B, V, and M, where A and B are guaranteed to be coprime. Additionally, you have an integer x. Initially, x=V.

You can do the following four kinds of operations any number of times in any order.

Replace the value of x with x+A.
Replace the value of x with x-A.
Replace the value of x with x+B.
Replace the value of x with x-B.

Here, 0 \leq x \leq M must hold at any moment during this process.

Under this condition, find how many different values x can take.

For each input file, solve T test cases.

Constraints

1 \leq T \leq 10^5
1 \leq A < B \leq M \leq 10^9
A and B are coprime.
0 \leq V \leq M
All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_3

Each case is in the following format:

A B V M

Output

Print the answer for each case.

Sample Input 1

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

Sample Output 1

In the first case, x can take four values: x=0,2,3,5.