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

C - Christmas Trees

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

配点 : 250 点

問題文

東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に x\mathrm{\,m} のところにある地点の座標は x と定められています。特に、基準となる地点から西に x\mathrm{\,m} のところにある地点の座標は -x です。

すぬけ君は今から、座標が A である地点を基点にして M\mathrm{\,m} おきにクリスマスツリーを立てます。すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。

高橋君と青木君はそれぞれ座標が L,R\ (L\leq R) である地点に立っています。高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を求めてください。

制約

-10^{18}\leq A \leq 10^{18}
1\leq M \leq 10^9
-10^{18}\leq L\leq R \leq 10^{18}
入力は全て整数

入力

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

A M L R

出力

高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を出力せよ。

入力例 1

5 3 -1 6

出力例 1

すぬけ君は、座標が \dots,-4,-1,2,5,8,11,14\dots である地点にクリスマスツリーを立てます。これらのうち高橋君と青木君の間にあるのは、座標が -1,2,5 である地点に立てられる 3 本です。

入力例 2

-2 2 1 1

出力例 2

高橋君と青木君が同じ地点に立っていることもあります。

入力例 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

出力例 3

273142010859

Score : 250 points

Problem Statement

There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.

Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.

Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Constraints

-10^{18}\leq A \leq 10^{18}
1\leq M \leq 10^9
-10^{18}\leq L\leq R \leq 10^{18}
All input values are integers.

Input

Input is given from Standard Input in the following format:

A M L R

Output

Print the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Sample Input 1

5 3 -1 6

Sample Output 1

Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.

Sample Input 2

-2 2 1 1

Sample Output 2

Sometimes, Takahashi and Aoki are standing at the same point.

Sample Input 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

Sample Output 3

273142010859

D - Glass and Mug

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

配点 : 200 点

問題文

AtCoder 社はグラスとマグカップを販売しています。

高橋君は容量が G ml のグラスと、容量が M ml のマグカップを 1 つずつ持っています。
ここで、G,M は G<M をみたします。

最初、グラスとマグカップはいずれも空です。
以下の操作を K 回繰り返した後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか求めてください。

グラスが水で満たされているとき、すなわちグラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。
そうでなく、マグカップが空であるとき、マグカップを水で満たす。
上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。

制約

1\leq K\leq 100
1\leq G<M\leq 1000
G,M,K は整数

入力

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

K G M

出力

操作を K 回行った後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか、この順に空白区切りで出力せよ。

入力例 1

5 300 500

出力例 1

200 500

操作は次の順で行われます。最初、グラスとマグカップはいずれも空です。

マグカップを水で満たす。グラスには 0 ml, マグカップには 500 ml 入った状態になる。
グラスが満たされるまでマグカップからグラスに水を移す。グラスには 300 ml, マグカップには 200 ml 入った状態になる。
グラスの水をすべて捨てる。グラスには 0 ml, マグカップには 200 ml 入った状態になる。
マグカップが空になるまでマグカップからグラスに水を移す。グラスには 200 ml, マグカップには 0 ml 入った状態になる。
マグカップを水で満たす。グラスには 200 ml, マグカップには 500 ml 入った状態になる。

よって、5 回の操作の後でグラスには 200 ml, マグカップには 500 ml 入った状態になります。ゆえに、200, 500 を空白区切りでこの順に出力します。

入力例 2

5 100 200

出力例 2

0 0

Score : 200 points

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
Otherwise, if the mug is empty, fill the mug with water.
Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

1\leq K\leq 100
1\leq G<M\leq 1000
G, M, and K are integers.

Input

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

K G M

Output

Print the amounts, in milliliters, of water in the glass and the mug, in this order, separated by a space, after performing the operation K times.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

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.