Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
ARC 国の消費税率は t パーセントです。ただし t は正の整数です。
ARC 国には整数屋さんがあります。整数屋さんでは各正の整数 A を税抜き価格 A 円で取り扱っており、その税込み価格は \left\lfloor\frac{100+t}{100}A\right\rfloor 円です。ただし実数 x に対し、\lfloor x\rfloor は x 以下の最大の整数を表します。
あらゆる正の整数を取り扱っている整数屋さんですが、その税込み価格としては現れない正の整数の金額が存在します。そのような金額のうち、小さい方から N 番目のものを求めてください。
制約
- 1\leq t\leq 50
- 1\leq N\leq 10^{9}
入力
入力は以下の形式で標準入力から与えられます。
t N
出力
答えを出力してください。
入力例 1
10 1
出力例 1
10
この例では、消費税率は 10 パーセントです。
- 整数 9 の税込み価格は \left\lfloor \frac{110}{100}\times 9\right\rfloor = \lfloor 9.9\rfloor = 9 円です。
- 整数 10 の税込み価格は \left\lfloor \frac{110}{100}\times 10\right\rfloor = \lfloor 11\rfloor = 11 円です。
これらから、10 円という金額は税込み価格として現れないことが分かります。この金額が、税込み価格として現れない最小の金額となります。
入力例 2
3 5
出力例 2
171
消費税率が 3 パーセントの場合、税込み価格として現れない金額は、小さい方から順に 34, 68, 102, 137, 171, \ldots となります。
入力例 3
1 1000000000
出力例 3
100999999999
Score : 300 points
Problem Statement
The consumption tax rate in the Republic of ARC is t percent, where t is a positive integer.
There is a shop called Seisu-ya (integer shop) there. It sells each positive integer A for A yen (Japanese currency) excluding tax, that is, \left\lfloor\frac{100+t}{100}A\right\rfloor yen including tax. Here, \lfloor x\rfloor denotes the largest integer not greater than x for a real number x.
Although Seisu-ya sells every positive integer, there are some positive integer values that cannot be the tax-included price of an integer. Among those values, find the N-th smallest value.
Constraints
- 1\leq t\leq 50
- 1\leq N\leq 10^{9}
Input
Input is given from Standard Input in the following format:
t N
Output
Print the answer.
Sample Input 1
10 1
Sample Output 1
10
In this sample, the consumption tax rate is 10 percent.
- The integer 9 is sold for \left\lfloor \frac{110}{100}\times 9\right\rfloor = \lfloor 9.9\rfloor = 9 yen including tax.
- The integer 10 is sold for \left\lfloor \frac{110}{100}\times 10\right\rfloor = \lfloor 11\rfloor = 11 yen including tax.
From above, we can see that 10 is not the tax-included price of any integer, and this is the minimum such value.
Sample Input 2
3 5
Sample Output 2
171
If the consumption tax rate is 3 percent, the smallest values that cannot be the tax-included price of an integer are 34, 68, 102, 137, 171, \ldots
Sample Input 3
1 1000000000
Sample Output 3
100999999999
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
ARC 国には N 人の国民がおり、全国民が競技プログラミングのプレイヤーです。各国民にはその競技プログラミングの実力によって、1, 2, \ldots, K のいずれかひとつの段位が与えられています。
ARC 国では国勢調査が行われて、その結果、段位 i の国民はちょうど A_i 人居ることが分かりました。ARC 国の国王はこの統計データをより理解しやすい形にするために、なるべく各段位の人数の割合を保ったまま、ARC 国の状況を M 人の村に例えることにしました。
M 人の村における段位 i の村民の人数 B_i を上手く定めることで、\max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| を最小にしてください。ただし、次が成り立つ必要があります。
- 各 B_i は非負整数で、\sum_{i=1}^K B_i = M を満たす
そのような B = (B_1, B_2, \ldots, B_K) の定め方を、ひとつ出力してください。
制約
- 1\leq K\leq 10^5
- 1\leq N, M\leq 10^9
- 各 A_i は非負整数で、\sum_{i=1}^K A_i = N を満たす
入力
入力は以下の形式で標準入力から与えられます。
K N M A_1 A_2 \ldots A_K
出力
条件を満たす整数列 B の各要素を、空白で区切って 1 行で出力してください。
B_1 B_2 \ldots B_K
条件を満たす整数列が複数存在する場合は、どれを出力しても正解となります。
入力例 1
3 7 20 1 2 4
出力例 1
3 6 11
この出力において、\max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \max\left(\left|\frac{3}{20}-\frac{1}{7}\right|, \left|\frac{6}{20}-\frac{2}{7}\right|, \left|\frac{11}{20}-\frac{4}{7}\right|\right) = \max\left(\frac{1}{140}, \frac{1}{70}, \frac{3}{140}\right) = \frac{3}{140} となっています。
入力例 2
3 3 100 1 1 1
出力例 2
34 33 33
和を M = 100 にしなければならないので、B_1 = B_2 = B_3 = 33 では 条件が満たされないことに注意してください。
なおこの例においては、34 33 33
の他、33 34 33
や 33 33 34
という出力も正解となります。
入力例 3
6 10006 10 10000 3 2 1 0 0
出力例 3
10 0 0 0 0 0
入力例 4
7 78314 1000 53515 10620 7271 3817 1910 956 225
出力例 4
683 136 93 49 24 12 3
Score : 400 points
Problem Statement
The Republic of ARC has N citizens, all of whom play competitive programming. Each citizen is given a dan (grade) which is 1, 2, \ldots, or K, according to their skill.
A national census has revealed that there are exactly A_i citizens with dan i. To make this data easier to understand, the king has decided to describe the country as if it were a village of M people.
Set the number of people with dan i in the village, B_i, so that \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| is minimized, while satisfying the following:
- each B_i is a non-negative integer, satisfying \sum_{i=1}^K B_i = M.
Print one such way to set B = (B_1, B_2, \ldots, B_K).
Constraints
- 1\leq K\leq 10^5
- 1\leq N, M\leq 10^9
- Each A_i is a non-negative integer satisfying \sum_{i=1}^K A_i = N.
Input
Input is given from Standard Input in the following format:
K N M A_1 A_2 \ldots A_K
Output
Print the elements in your integer sequence B satisfying the requirement in one line, with spaces in between.
B_1 B_2 \ldots B_K
If multiple sequences satisfy the requirement, any of them will be accepted.
Sample Input 1
3 7 20 1 2 4
Sample Output 1
3 6 11
In this output, we have \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \max\left(\left|\frac{3}{20}-\frac{1}{7}\right|, \left|\frac{6}{20}-\frac{2}{7}\right|, \left|\frac{11}{20}-\frac{4}{7}\right|\right) = \max\left(\frac{1}{140}, \frac{1}{70}, \frac{3}{140}\right) = \frac{3}{140}.
Sample Input 2
3 3 100 1 1 1
Sample Output 2
34 33 33
Note that B_1 = B_2 = B_3 = 33 does not satisfy the requirement, since the sum must be M = 100.
In this sample, other than 34 33 33
, printing 33 34 33
or 33 33 34
will also be accepted.
Sample Input 3
6 10006 10 10000 3 2 1 0 0
Sample Output 3
10 0 0 0 0 0
Sample Input 4
7 78314 1000 53515 10620 7271 3817 1910 956 225
Sample Output 4
683 136 93 49 24 12 3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正の整数 N が与えられます。整数列 A = (A_1, A_2, \ldots, A_N) であって、次の条件をすべて満たすものをひとつ出力してください。
- 1\leq A_i\leq 10000
- i\neq j に対して、A_i\neq A_j かつ \gcd(A_i, A_j) > 1
- \gcd(A_1, A_2, \ldots, A_N) = 1
なお、この問題の制約のもとで、条件を満たす整数列が存在することが証明できます。
制約
- 3\leq N\leq 2500
入力
入力は以下の形式で標準入力から与えられます。
N
出力
条件を満たす整数列 A の各要素を、空白で区切って 1 行で出力してください。
A_1 A_2 \ldots A_N
条件を満たす整数列が複数存在する場合は、どれを出力しても正解となります。
入力例 1
4
出力例 1
84 60 105 70
- \gcd(84,60) = 12
- \gcd(84,105) = 21
- \gcd(84,70) = 14
- \gcd(60,105) = 15
- \gcd(60,70) = 10
- \gcd(105,70) = 35
- \gcd(84,60,105,70) = 1
が成り立ち、すべての条件が満たされていることが確認できます。
Score : 500 points
Problem Statement
Given is a positive integer N. Print an integer sequence A = (A_1, A_2, \ldots, A_N) satisfying all of the following:
- 1\leq A_i\leq 10000;
- A_i\neq A_j and \gcd(A_i, A_j) > 1 for i\neq j;
- \gcd(A_1, A_2, \ldots, A_N) = 1.
We can prove that, under the Constraints of this problem, such an integer sequence always exists.
Constraints
- 3\leq N\leq 2500
Input
Input is given from Standard Input in the following format:
N
Output
Print the elements in your integer sequence A satisfying the conditions in one line, with spaces in between.
A_1 A_2 \ldots A_N
If multiple sequences satisfy the conditions, any of them will be accepted.
Sample Input 1
4
Sample Output 1
84 60 105 70
All of the conditions are satisfied, since we have:
- \gcd(84,60) = 12
- \gcd(84,105) = 21
- \gcd(84,70) = 14
- \gcd(60,105) = 15
- \gcd(60,70) = 10
- \gcd(105,70) = 35
- \gcd(84,60,105,70) = 1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
素数 P および正の整数 a, b が与えられます。 P 項からなる整数列 A = (A_1, A_2, \ldots, A_P) であって、次の条件をすべて満たすものが存在するかを判定してください。 存在する場合には、そのようなものをひとつ出力してください。
- 1\leq A_i\leq P - 1
- A_1 = A_P = 1
- (A_1, A_2, \ldots, A_{P-1}) は、(1, 2, \ldots, P-1) を並べ替えたものである
- 任意の 2\leq i\leq P に対して、次のうち少なくともひとつが成り立つ:
- A_{i} \equiv aA_{i-1}\pmod{P}
- A_{i-1} \equiv aA_{i}\pmod{P}
- A_{i} \equiv bA_{i-1}\pmod{P}
- A_{i-1} \equiv bA_{i}\pmod{P}
制約
- 2\leq P\leq 10^5
- P は素数
- 1\leq a, b \leq P - 1
入力
入力は以下の形式で標準入力から与えられます。
P a b
出力
問題の条件を満たす整数列 A が存在するならば Yes
を、そうでなければ No
を出力してください。
Yes
の場合には、2 行目にそのような整数列 A の各要素を、空白で区切って 1 行で出力してください。
A_1 A_2 \ldots A_P
条件を満たす整数列が複数存在する場合は、どれを出力しても正解となります。
入力例 1
13 4 5
出力例 1
Yes 1 5 11 3 12 9 7 4 6 8 2 10 1
P = 13 を法として、
- A_2\equiv 5A_1
- A_2\equiv 4A_3
- \vdots
- A_{13}\equiv 4A_{12}
が成り立ち、この整数列は条件を満たすことが確認できます。
入力例 2
13 1 2
出力例 2
Yes 1 2 4 8 3 6 12 11 9 5 10 7 1
入力例 3
13 9 3
出力例 3
No
入力例 4
13 1 1
出力例 4
No
Score : 700 points
Problem Statement
Given are a prime number P and positive integers a and b. Determine whether there is a sequence of P integers, A = (A_1, A_2, \ldots, A_P), satisfying all of the conditions below, and print one such sequence if it exists.
- 1\leq A_i\leq P - 1.
- A_1 = A_P = 1.
- (A_1, A_2, \ldots, A_{P-1}) is a permutation of (1, 2, \ldots, P-1).
- For every 2\leq i\leq P, at least one of the following holds.
- A_{i} \equiv aA_{i-1}\pmod{P}
- A_{i-1} \equiv aA_{i}\pmod{P}
- A_{i} \equiv bA_{i-1}\pmod{P}
- A_{i-1} \equiv bA_{i}\pmod{P}
Constraints
- 2\leq P\leq 10^5
- P is a prime.
- 1\leq a, b \leq P - 1
Input
Input is given from Standard Input in the following format:
P a b
Output
If there is an integer sequence A satisfying the conditions, print Yes
; otherwise, print No
.
In the case of Yes
, print the elements in your sequence A satisfying the requirement in the next line, with spaces in between.
A_1 A_2 \ldots A_P
If multiple sequences satisfy the requirement, any of them will be accepted.
Sample Input 1
13 4 5
Sample Output 1
Yes 1 5 11 3 12 9 7 4 6 8 2 10 1
This sequence satisfies the conditions, since we have the following modulo P = 13:
- A_2\equiv 5A_1
- A_2\equiv 4A_3
- \vdots
- A_{13}\equiv 4A_{12}
Sample Input 2
13 1 2
Sample Output 2
Yes 1 2 4 8 3 6 12 11 9 5 10 7 1
Sample Input 3
13 9 3
Sample Output 3
No
Sample Input 4
13 1 1
Sample Output 4
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) に対して 次の問題を考え、その答えを f(P) と書くことにします。
(N+2)\times (N+2) のマス目があり、行には上から順に 0, 1, \ldots, N+1 の番号が、列には左から順に 0, 1, \ldots, N+1 の番号がつけられています。i 行目・j 列目のマスを (i,j) と表します。
(0,0) を出発して、右または下の隣り合うマスへの移動を繰り返すことで、(N+1,N+1) まで移動する経路を考えます。ただし、1\leq i\leq N に対してマス (i, P_i) は通ってはいけません。このような経路は何通りあるでしょうか?
正の整数 N および整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。各 A_i は、-1 であるか、あるいは 1 以上 N 以下の整数です。
(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) であって、A_i\neq -1 \implies P_i = A_i を満たすものを考えます。そのようなすべての P に対する f(P) の総和を、998244353 で割った余りを求めてください。
制約
- 1\leq N\leq 200
- A_i = -1 あるいは 1\leq A_i\leq N
- i\neq j に対し、A_i\neq -1, A_j\neq -1 ならば A_i\neq A_j
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \ldots A_N
出力
答えを出力してください。
入力例 1
4 1 -1 4 -1
出力例 1
41
2 つの順列 P = (1,2,4,3) および P = (1,3,4,2) に対する f(P) の和が求めるものです。それぞれの P の場合に、マス目において通れないマスを図示すると、次のようになります(通れるマス・通れないマスをそれぞれ .
#
で表しています)。
...... ...... .#.... .#.... ..#... ...#.. ....#. ....#. ...#.. ..#... ...... ...... P=(1,2,4,3) P=(1,3,4,2)
- 順列 P = (1,2,4,3) の場合には f(P) = 18 です。
- 順列 P = (1,3,4,2) の場合には f(P) = 23 です。
これらの和である 41 が答えとなります。
入力例 2
4 4 3 2 1
出力例 2
2
この例では、計算対象となる順列 P は P = (4,3,2,1) のひとつです。
入力例 3
3 -1 -1 -1
出力例 3
48
- 順列 P = (1,2,3) の場合には f(P) = 10 です。
- 順列 P = (1,3,2) の場合には f(P) = 6 です。
- 順列 P = (2,1,3) の場合には f(P) = 6 です。
- 順列 P = (2,3,1) の場合には f(P) = 12 です。
- 順列 P = (3,1,2) の場合には f(P) = 12 です。
- 順列 P = (3,2,1) の場合には f(P) = 2 です。
これらの和である 48 が答えとなります。
Score : 800 points
Problem Statement
Let us consider the problem below for a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N), and denote the answer by f(P).
We have an (N+2)\times (N+2) grid, where the rows are numbered 0, 1, \ldots, N+1 from top to bottom and the columns are numbered 0, 1, \ldots, N+1 from left to right. Let (i,j) denote the square at the i-th row and j-th column.
Consider paths from (0, 0) to (N+1, N+1) where we repeatedly move one square right or one square down. However, for each 1\leq i\leq N, we must not visit the square (i, P_i). How many such paths are there?
You are given a positive integer N and an integer sequence A = (A_1, A_2, \ldots, A_N), where each A_i is -1 or an integer between 1 and N (inclusive).
Consider all permutations P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) satisfying A_i\neq -1 \implies P_i = A_i. Find the sum of f(P) over all such P, modulo 998244353.
Constraints
- 1\leq N\leq 200
- A_i = -1 or 1\leq A_i\leq N.
- A_i\neq A_j if A_i\neq -1 and A_j\neq -1, for i\neq j.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 1 -1 4 -1
Sample Output 1
41
We want to find the sum of f(P) over two permutations P = (1,2,4,3) and P = (1,3,4,2). The figure below shows the impassable squares for each of them, where .
and #
represent a passable and impassable square, respectively.
...... ...... .#.... .#.... ..#... ...#.. ....#. ....#. ...#.. ..#... ...... ...... P=(1,2,4,3) P=(1,3,4,2)
- For P = (1,2,4,3), we have f(P) = 18.
- For P = (1,3,4,2), we have f(P) = 23.
The answer is the sum of them: 41.
Sample Input 2
4 4 3 2 1
Sample Output 2
2
In this sample, we want to compute f(P) for just one permutation P = (4,3,2,1).
Sample Input 3
3 -1 -1 -1
Sample Output 3
48
- For P = (1,2,3), we have f(P) = 10.
- For P = (1,3,2), we have f(P) = 6.
- For P = (2,1,3), we have f(P) = 6.
- For P = (2,3,1), we have f(P) = 12.
- For P = (3,1,2), we have f(P) = 12.
- For P = (3,2,1), we have f(P) = 2.
The answer is the sum of them: 48.
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
正の整数 M と、N 項からなる整数列 A = (A_1,A_2,\ldots,A_N) が与えられます。N+1 項からなる整数列 X = (X_1,X_2, \ldots, X_{N+1}) であって、次の条件をすべて満たすものの個数を \bmod 998244353 で求めてください。
- 1\leq X_i\leq M (1\leq i\leq N+1)
- A_iX_i\leq X_{i+1} (1\leq i\leq N)
制約
- 1\leq N\leq 1000
- 1\leq M\leq 10^{18}
- 1\leq A_i\leq 10^9
- \prod_{i=1}^N A_i \leq M
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 A_2 \ldots A_N
出力
条件を満たす整数列の個数を \bmod 998244353 で出力してください。
入力例 1
2 10 2 3
出力例 1
7
条件を満たす整数列 X は、以下の 7 個です:
- (1, 2, 6), (1,2,7), (1,2,8), (1,2,9), (1,2,10), (1,3,9), (1,3,10)
入力例 2
2 10 3 2
出力例 2
9
条件を満たす整数列 X は、以下の 9 個です:
- (1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 3, 10), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 10)
入力例 3
7 1000 1 2 3 4 3 2 1
出力例 3
225650129
入力例 4
5 1000000000000000000 1 1 1 1 1
出力例 4
307835847
Score : 1000 points
Problem Statement
Given is a positive integer M and a sequence of N integers: A = (A_1,A_2,\ldots,A_N). Find the number, modulo 998244353, of sequences of N+1 integers, X = (X_1,X_2, \ldots, X_{N+1}), satisfying all of the following conditions:
- 1\leq X_i\leq M (1\leq i\leq N+1)
- A_iX_i\leq X_{i+1} (1\leq i\leq N)
Constraints
- 1\leq N\leq 1000
- 1\leq M\leq 10^{18}
- 1\leq A_i\leq 10^9
- \prod_{i=1}^N A_i \leq M
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Print the number of integer sequences satisfying the conditions, modulo 998244353.
Sample Input 1
2 10 2 3
Sample Output 1
7
Seven sequences below satisfy the conditions.
- (1, 2, 6), (1,2,7), (1,2,8), (1,2,9), (1,2,10), (1,3,9), (1,3,10)
Sample Input 2
2 10 3 2
Sample Output 2
9
Nine sequences below satisfy the conditions.
- (1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 3, 10), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 10)
Sample Input 3
7 1000 1 2 3 4 3 2 1
Sample Output 3
225650129
Sample Input 4
5 1000000000000000000 1 1 1 1 1
Sample Output 4
307835847