AtCoder Daily Training HARD 2024/06/19 18:00start

E - Repunit Trio

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,\ldots です。

ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。

制約

N は 1 以上 333 以下の整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

ちょうど 3 つのレピュニットの和として表せる整数を小さい順に並べると 3,13,23,33,113,\ldots です。例えば 113 は 113=1+1+111 と表せます。

3 つのレピュニットは相異ならなくてもよいことに注意してください。

入力例 2

出力例 2

入力例 3

出力例 3

112222222233

Score : 300 points

Problem Statement

A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.

Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

N is an integer between 1 and 333, inclusive.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.

Note that the three repunits do not have to be distinct.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

112222222233

F - Cheese

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に N 種類のチーズがあります。
i 種類目のチーズは 1 [g] あたりのおいしさが A_i で、 B_i [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で W [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。

制約

入力は全て整数
1 \le N \le 3 \times 10^5
1 \le W \le 3 \times 10^8
1 \le A_i \le 10^9
1 \le B_i \le 1000

入力

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

N W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

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

入力例 1

出力例 1

1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。

入力例 2

出力例 2

チーズの重量の総和が W [g] に満たないケースもあります。

入力例 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

出力例 3

2357689932073

Score : 300 points

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

All values in input are integers.
1 \le N \le 3 \times 10^5
1 \le W \le 3 \times 10^8
1 \le A_i \le 10^9
1 \le B_i \le 1000

Input

Input is given from Standard Input in the following format:

N W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

Sample Output 2

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

G - Popcount and XOR

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

非負整数 a,b,C が与えられます。次の 5 つの条件をすべて満たす非負整数の組 (X,Y) が存在するか判定し、存在するならひとつ出力してください。

0\leq X\lt2 ^ {60}
0\leq Y\lt2 ^ {60}
\operatorname{popcount}(X)=a
\operatorname{popcount}(Y)=b
X\oplus Y=C

ただし、\oplus はビットごとの排他的論理和を表します。

条件を満たす (X,Y) が複数存在する場合、どれを出力しても構いません。

popcount とは？

非負整数 x について x の popcount とは、x を 2 進法で表記したときの 1 の個数です。より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。

例えば、13 を 2 進法で表記すると 1101 なので、 \operatorname{popcount}(13)=3 となります。

ビットごとの排他的論理和とは？

非負整数 x,y について x,y のビットごとの排他的論理和 x\oplus y は以下のように定義されます。

x\oplus y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位は、x,y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位の数のうち一方のみが 1 であれば 1 、そうでなければ 0 となる。

例えば、9,3 を 2 進法で表記するとそれぞれ 1001, 0011 なので、9\oplus3=10 となります（10 を 2 進法で表記すると 1010 です）。

制約

0\leq a\leq60
0\leq b\leq60
0\leq C\lt2 ^ {60}
入力はすべて整数

入力

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

a b C

出力

条件を満たす非負整数の組が存在するならば、そのような (X,Y) をひとつ選び X,Y をこの順に空白を区切りとして出力せよ。存在しないならば、-1 を出力せよ。

入力例 1

3 4 7

出力例 1

28 27

(X,Y)=(28,27) は条件を満たします。 X,Y を 2 進法で表記するとそれぞれ 11100 と 11011 になります。

X を 2 進法で表記すると 11100 になるので、\operatorname{popcount}(X)=3 です。
Y を 2 進法で表記すると 11011 になるので、\operatorname{popcount}(Y)=4 です。
X\oplus Y を 2 進法で表記すると 00111 となり、X\oplus Y=7 です。

条件を満たす非負整数の組が複数存在する場合どれを出力しても構わないため、例えば 42 45 と出力しても正解になります。

入力例 2

34 56 998244353

出力例 2

-1

条件を満たす非負整数の組は存在しません。

入力例 3

39 47 530423800524412070

出力例 3

540431255696862041 10008854347644927

出力すべき値が 32\operatorname{bit} 整数に収まらない場合があります。

Score: 400 points

Problem Statement

You are given non-negative integers a, b, and C. Determine if there is a pair of non-negative integers (X, Y) that satisfies all of the following five conditions. If such a pair exists, print one.

0 \leq X < 2^{60}
0 \leq Y < 2^{60}
\operatorname{popcount}(X) = a
\operatorname{popcount}(Y) = b
X \oplus Y = C

Here, \oplus denotes the bitwise XOR.

If multiple pairs (X, Y) satisfy the conditions, you may print any of them.

What is popcount?

For a non-negative integer x, the popcount of x is the number of 1s in the binary representation of x. More precisely, for a non-negative integer x such that \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), we have \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.

For example, 13 in binary is 1101, so \operatorname{popcount}(13)=3.

What is bitwise XOR?

For non-negative integers x, y, the bitwise exclusive OR x \oplus y is defined as follows.

The 2^k's place \ (k\geq0) in the binary representation of x \oplus y is 1 if exactly one of the 2^k's places \ (k\geq0) in the binary representations of x and y is 1, and 0 otherwise.

For example, 9 and 3 in binary are 1001 and 0011, respectively, so 9 \oplus 3 = 10 (in binary, 1010).

Constraints

0 \leq a \leq 60
0 \leq b \leq 60
0 \leq C < 2^{60}
All input values are integers.

Input

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

a b C

Output

If there is a pair of non-negative integers that satisfies the conditions, choose one such pair (X, Y) and print X and Y in this order, with a space in between. If no such pair exists, print -1.

Sample Input 1

3 4 7

Sample Output 1

28 27

The pair (X, Y) = (28, 27) satisfies the conditions. Here, X and Y in binary are 11100 and 11011, respectively.

X in binary is 11100, so \operatorname{popcount}(X) = 3.
Y in binary is 11011, so \operatorname{popcount}(Y) = 4.
X \oplus Y in binary is 00111, so X \oplus Y = 7.

If multiple pairs of non-negative integers satisfy the conditions, you may print any of them, so printing 42 45, for example, would also be accepted.

Sample Input 2

34 56 998244353

Sample Output 2

-1

No pair of non-negative integers satisfies the conditions.

Sample Input 3

39 47 530423800524412070

Sample Output 3

540431255696862041 10008854347644927

Note that the values to be printed may not fit in 32-bit integers.

H - Fraction Floor Sum

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

正の整数 N が与えられます。 \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right] の値を求めてください。

ただし、実数 x に対して [x] で x 以下の最大の整数を表します。

制約

1 \leq N \leq 10^{12}
N は整数である。

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

\left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5 です。

入力例 2

10000000000

出力例 2

231802823220

入力や出力が 32 bit 整数型に収まらないことがあることに注意してください。

Score : 500 points

Problem Statement

Given is a positive integer N. Find the value \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right].

Here, for a real number x, [x] denotes the largest integer not exceeding x.

Constraints

1 \leq N \leq 10^{12}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

We have \left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5.

Sample Input 2

10000000000

Sample Output 2

231802823220

Note that the input and output may not fit into a 32-bit integer type.

I - Cumulative Cumulative Cumulative Sum

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N,Q および A=(A_1,\ldots,A_N) が与えられます。
以下のクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。

1 x v : A_x を v に更新する。
2 x : B_i=\sum_{j=1}^{i}A_j、C_i=\sum_{j=1}^{i}B_j、D_i=\sum_{j=1}^{i}C_j としたときの D_x を \bmod\ 998244353 で出力する。

制約

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A_i \leq 10^9
1 \leq x \leq N
0 \leq v \leq 10^9
入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。ここで {\rm query}_i は i 番目に処理するクエリである。

N Q
A_1 A_2 \ldots A_N
{\rm query}_1
{\rm query}_2
\vdots
{\rm query}_Q

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 x v

2 x

出力

クエリへの答えを改行区切りで出力せよ。

入力例 1

出力例 1

15
9

1 番目のクエリの時点で A=(1,2,3) であるため、B=(1,3,6)、C=(1,4,10)、D=(1,5,15) となり、D_3=15 です。

3 番目のクエリの時点で A=(1,0,3) であるため、B=(1,1,4)、C=(1,2,6)、D=(1,3,9) となり、D_3=9 です。

入力例 2

2 1
998244353 998244353
2 1

出力例 2

Score : 500 points

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

1 x v: update A_x to v.
2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A_i \leq 10^9
1 \leq x \leq N
0 \leq v \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format, where {\rm query}_i denotes the i-th query to be processed:

N Q
A_1 A_2 \ldots A_N
{\rm query}_1
{\rm query}_2
\vdots
{\rm query}_Q

Each query is given in one of the following two formats:

1 x v

2 x

Output

Print the answer to the queries, with newlines in between.

Sample Input 1

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1