Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,\ldots です。
ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。
制約
- N は 1 以上 333 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
5
出力例 1
113
ちょうど 3 つのレピュニットの和として表せる整数を小さい順に並べると 3,13,23,33,113,\ldots です。例えば 113 は 113=1+1+111 と表せます。
3 つのレピュニットは相異ならなくてもよいことに注意してください。
入力例 2
19
出力例 2
2333
入力例 3
333
出力例 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:
N
Output
Print the answer.
Sample Input 1
5
Sample Output 1
113
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
19
Sample Output 2
2333
Sample Input 3
333
Sample Output 3
112222222233
Time Limit: 2 sec / Memory Limit: 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
3 5 3 1 4 2 2 3
出力例 1
15
1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。
入力例 2
4 100 6 2 1 5 3 9 8 7
出力例 2
100
チーズの重量の総和が 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
3 5 3 1 4 2 2 3
Sample Output 1
15
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
4 100 6 2 1 5 3 9 8 7
Sample Output 2
100
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
Time Limit: 2 sec / Memory Limit: 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 is1101, 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.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
正の整数 N が与えられます。 \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right] の値を求めてください。
ただし、実数 x に対して [x] で x 以下の最大の整数を表します。
制約
- 1 \leq N \leq 10^{12}
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
5
\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:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
5
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.
Time Limit: 2 sec / Memory Limit: 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
3 3 1 2 3 2 3 1 2 0 2 3
出力例 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
0
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
3 3 1 2 3 2 3 1 2 0 2 3
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
Sample Output 2
0