Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 x_1, x_2, x_3 が与えられます.あなたはこれらの整数に対して,次の操作を何度でも行うことができます(0 回でもよい):
- (1,2,3) の順列 (i,j,k) をひとつ選ぶ.つまり 1\leq i,j,k\leq 3 であるような整数の組 (i,j,k) であって i\neq j, i\neq k, j\neq k となるものを選ぶ.
- その後,x_i を x_i+3,x_j を x_j+5,x_k を x_k+7 で同時に置き換える.
あなたの目的は,x_1=x_2=x_3 が成り立つようにすることです.このことが可能であるか否かを判定してください.可能な場合には,それを達成するための最小の操作回数を出力してください.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 2\times 10^5
- 1\leq x_1, x_2, x_3 \leq 10^9
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
x_1 x_2 x_3
出力
T 行出力してください.i 行目には i 番目のテストケースについて,次の値を出力してください.
- x_1=x_2=x_3 が成り立つようにすることが可能ならば,それを達成するための最小の操作回数.
- x_1=x_2=x_3 が成り立つようにすることが不可能ならば,-1.
入力例 1
4 2 8 8 1 1 1 5 5 10 10 100 1000
出力例 1
2 0 -1 315
ひとつめのテストケースについて,次のように操作を行うことで x_1=x_2=x_3 が成り立つようにできます.
- (i,j,k) = (3,2,1) として操作を行う.(x_1,x_2,x_3) は (9,13,11) に置き換わる.
- (i,j,k) = (2,3,1) として操作を行う.(x_1,x_2,x_3) は (16,16,16) に置き換わる.
Score : 300 points
Problem Statement
You are given integers x_1, x_2, and x_3. For these integers, you can perform the following operation any number of times, possibly zero.
- Choose a permutation (i,j,k) of (1,2,3), that is, a triple of integers (i,j,k) such that 1\leq i,j,k\leq 3 and i\neq j, i\neq k, j\neq k.
- Then, simultaneously replace x_i with x_i+3, x_j with x_j+5, and x_k with x_k+7.
Your objective is to satisfy x_1=x_2=x_3. Determine whether it is achievable. If it is, print the minimum number of times you need to perform the operation to achieve it.
You have T test cases to solve.
Constraints
- 1\leq T\leq 2\times 10^5
- 1\leq x_1, x_2, x_3 \leq 10^9
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each test case is in the following format:
x_1 x_2 x_3
Output
Print T lines. The i-th line should contain the following value for the i-th test case.
- The minimum number of times you need to perform the operation to satisfy x_1=x_2=x_3, if it is possible to satisfy this.
- -1, otherwise.
Sample Input 1
4 2 8 8 1 1 1 5 5 10 10 100 1000
Sample Output 1
2 0 -1 315
For the first test case, you can do the following to satisfy x_1=x_2=x_3.
- Perform the operation with (i,j,k) = (3,2,1), replacing (x_1,x_2,x_3) with (9,13,11).
- Perform the operation with (i,j,k) = (2,3,1), replacing (x_1,x_2,x_3) with (16,16,16).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
0 でない整数 x_1, \ldots, x_N が与えられます.i,j,k を 1\leq i < j < k\leq N を満たす整数とするとき,\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる最小値と最大値を求めてください.
制約
- 3\leq N\leq 2\times 10^5
- -10^6\leq x_i \leq 10^6
- x_i\neq 0
入力
入力は以下の形式で標準入力から与えられます.
N x_1 \ldots x_N
出力
\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる最小値と最大値を,それぞれ 1 行目,2 行目に出力してください.
絶対誤差または相対誤差が 10^{-12} 以内であれば,正解と判定されます.
入力例 1
4 -2 -4 4 5
出力例 1
-0.175000000000000 -0.025000000000000
\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる値は次の 4 通りです.
- (i,j,k) = (1,2,3):\dfrac{(-2) + (-4) + 4}{(-2)\cdot (-4)\cdot 4} = -\dfrac{1}{16}.
- (i,j,k) = (1,2,4):\dfrac{(-2) + (-4) + 5}{(-2)\cdot (-4)\cdot 5} = -\dfrac{1}{40}.
- (i,j,k) = (1,3,4):\dfrac{(-2) + 4 + 5}{(-2)\cdot 4\cdot 5} = -\dfrac{7}{40}.
- (i,j,k) = (2,3,4):\dfrac{(-4) + 4 + 5}{(-4)\cdot 4\cdot 5} = -\dfrac{1}{16}.
これらの最小値は -\dfrac{7}{40},最大値は -\dfrac{1}{40} です.
入力例 2
4 1 1 1 1
出力例 2
3.000000000000000 3.000000000000000
入力例 3
5 1 2 3 4 5
出力例 3
0.200000000000000 1.000000000000000
Score : 500 points
Problem Statement
You are given non-zero integers x_1, \ldots, x_N. Find the minimum and maximum values of \dfrac{x_i+x_j+x_k}{x_ix_jx_k} for integers i, j, k such that 1\leq i < j < k\leq N.
Constraints
- 3\leq N\leq 2\times 10^5
- -10^6\leq x_i \leq 10^6
- x_i\neq 0
Input
The input is given from Standard Input in the following format:
N x_1 \ldots x_N
Output
Print the minimum value of \dfrac{x_i+x_j+x_k}{x_ix_jx_k} in the first line and the maximum value in the second line.
Your output will be considered correct when the absolute or relative error is at most 10^{-12}.
Sample Input 1
4 -2 -4 4 5
Sample Output 1
-0.175000000000000 -0.025000000000000
\dfrac{x_i+x_j+x_k}{x_ix_jx_k} can take the following four values.
- (i,j,k) = (1,2,3): \dfrac{(-2) + (-4) + 4}{(-2)\cdot (-4)\cdot 4} = -\dfrac{1}{16}.
- (i,j,k) = (1,2,4): \dfrac{(-2) + (-4) + 5}{(-2)\cdot (-4)\cdot 5} = -\dfrac{1}{40}.
- (i,j,k) = (1,3,4): \dfrac{(-2) + 4 + 5}{(-2)\cdot 4\cdot 5} = -\dfrac{7}{40}.
- (i,j,k) = (2,3,4): \dfrac{(-4) + 4 + 5}{(-4)\cdot 4\cdot 5} = -\dfrac{1}{16}.
Among them, the minimum is -\dfrac{7}{40}, and the maximum is -\dfrac{1}{40}.
Sample Input 2
4 1 1 1 1
Sample Output 2
3.000000000000000 3.000000000000000
Sample Input 3
5 1 2 3 4 5
Sample Output 3
0.200000000000000 1.000000000000000
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 x に対し,その各桁の和を f(x) と表すことにします.例えば f(158) = 1 + 5 + 8 = 14,f(2023) = 2 + 0 + 2 + 3 = 7,f(1) = 1 です.
正整数列 A = (A_1, \ldots, A_N) が与えられます.\sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) を求めてください.
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i < 10^{15}
入力
入力は以下の形式で標準入力から与えられます.
N A_1 \ldots A_N
出力
\sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) を出力してください.
入力例 1
2 53 28
出力例 1
36
\sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1)+f(A_1+A_2)+f(A_2+A_1)+f(A_2+A_2)=7+9+9+11=36 です.
入力例 2
1 999999999999999
出力例 2
135
\sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1) = 135 です.
入力例 3
5 123 456 789 101 112
出力例 3
321
Score : 500 points
Problem Statement
For a positive integer x, let f(x) denote the sum of its digits. For instance, f(158) = 1 + 5 + 8 = 14, f(2023) = 2 + 0 + 2 + 3 = 7, and f(1) = 1.
You are given a sequence of positive integers A = (A_1, \ldots, A_N). Find \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j).
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A_i < 10^{15}
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j).
Sample Input 1
2 53 28
Sample Output 1
36
We have \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1)+f(A_1+A_2)+f(A_2+A_1)+f(A_2+A_2)=7+9+9+11=36.
Sample Input 2
1 999999999999999
Sample Output 2
135
We have \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1) = 135.
Sample Input 3
5 123 456 789 101 112
Sample Output 3
321
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
正整数 n および,5 以上の素数 p が与えられます.
次の条件をすべて満たす整数の組 (x,y,z) を 1 つ求めてください.
- 1\leq x < y < z \leq p - 1.
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.
なお,このような組 (x,y,z) は必ず存在することが証明できます.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 10^5
- 1\leq n\leq 10^9
- p は 5\leq p\leq 10^9 を満たす素数
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
n p
出力
T 行出力してください.i 行目には i 番目のテストケースの解を (x,y,z) とするとき,x,y,z をこの順に空白区切りで出力してください.
解が複数存在する場合,どれを出力しても正解となります.
入力例 1
3 1 7 2 7 10 998244353
出力例 1
1 4 6 1 2 5 20380119 21549656 279594297
ひとつめのテストケースについて,
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413
- x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281
であり,6413\equiv 281\pmod{7} なので,条件を満たしていることが確認できます.
Score : 800 points
Problem Statement
You are given a positive integer n, and a prime number p at least 5.
Find a triple of integers (x,y,z) that satisfies all of the following conditions.
- 1\leq x < y < z \leq p - 1.
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.
It can be proved that such a triple (x,y,z) always exists.
You have T test cases to solve.
Constraints
- 1\leq T\leq 10^5
- 1\leq n\leq 10^9
- p is a prime number satisfying 5\leq p\leq 10^9.
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each case is in the following format:
n p
Output
Print T lines. The i-th line should contain x,y,z with spaces in between where (x,y,z) is a solution for the i-th test case.
If multiple solutions exist, you may print any of them.
Sample Input 1
3 1 7 2 7 10 998244353
Sample Output 1
1 4 6 1 2 5 20380119 21549656 279594297
For the first test case:
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413, and
- x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281.
We have 6413\equiv 281\pmod{7}, so the conditions are satisfied.
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
2 行 N 列のマス目があります.上から i 行目,左から j 列目のマスを (i,j) で表します.(i,j) には正整数 x_{i,j} が書かれています.
2 つのマスは,辺を共有するときに隣接するといいます.
マス X から Y へのパスとは,相異なるマスからなる列 (P_1, \ldots, P_n) であって,P_1 = X, P_n = Y であり,任意の 1\leq i \leq n-1 に対して P_i と P_{i+1} が隣接するものをいいます.さらに,そのパスの重みを P_1, \ldots, P_n に書かれている整数の総和として定義します.
2 つのマス X, Y に対して,X から Y へのパスの重みとしてありうる最小値を f(X, Y) と書くことにします.すべてのマスの 2 つ組 (X,Y) に対する f(X, Y) の総和を 998244353 で割った余りを求めてください.
制約
- 1\leq N\leq 2\times 10^5
- 1\leq x_{i,j} \leq 10^9
入力
入力は以下の形式で標準入力から与えられます.
N x_{1,1} \ldots x_{1,N} x_{2,1} \ldots x_{2,N}
出力
すべてのマスの 2 つ組 (X,Y) に対する f(X, Y) の総和を 998244353 で割った余りを出力してください.
入力例 1
1 3 5
出力例 1
24
次の 4 通りの値の総和を求めます.
- X = (1,1), Y = (1,1) のとき:f(X, Y) = 3.
- X = (1,1), Y = (2,1) のとき:f(X, Y) = 8.
- X = (2,1), Y = (1,1) のとき:f(X, Y) = 8.
- X = (2,1), Y = (2,1) のとき:f(X, Y) = 5.
入力例 2
2 1 2 3 4
出力例 2
76
入力例 3
5 1 1000000000 1 1 1 1 1 1 1000000000 1
出力例 3
66714886
Score : 800 points
Problem Statement
We have a grid with 2 rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. (i,j) has a postive integer x_{i,j} written on it.
Two squares are said to be adjacent when they share a side.
A path from square X to Y is a sequence (P_1, \ldots, P_n) of distinct squares such that P_1 = X, P_n = Y, and P_i and P_{i+1} are adjacent for every 1\leq i \leq n-1. Additionally, the weight of that path is the sum of integers written on P_1, \ldots, P_n.
For two squares X and Y, let f(X, Y) denote the minimum weight of a path from X to Y. Find the sum of f(X, Y) over all pairs of squares (X,Y), modulo 998244353.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq x_{i,j} \leq 10^9
Input
The input is given from Standard Input in the following format:
N x_{1,1} \ldots x_{1,N} x_{2,1} \ldots x_{2,N}
Output
Print the sum of f(X, Y) over all pairs of squares (X,Y), modulo 998244353.
Sample Input 1
1 3 5
Sample Output 1
24
You should find the sum of the following four values.
- For X = (1,1), Y = (1,1): f(X, Y) = 3.
- For X = (1,1), Y = (2,1): f(X, Y) = 8.
- For X = (2,1), Y = (1,1): f(X, Y) = 8.
- For X = (2,1), Y = (2,1): f(X, Y) = 5.
Sample Input 2
2 1 2 3 4
Sample Output 2
76
Sample Input 3
5 1 1000000000 1 1 1 1 1 1 1000000000 1
Sample Output 3
66714886
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
非負整数 x, k に対して,x の 10^k の位とは,\bigl\lfloor \frac{x}{10^k}\bigr\rfloor を 10 で割った余りのことをいいます.例えば 123 の 10^0, 10^1, 10^2, 10^3 の位はそれぞれ 3, 2, 1, 0 です.
正整数 N, M, K および非負整数列 A = (A_1, \ldots, A_N), B = (B_1, \ldots, B_N) が与えられます.
次の手順によって A を並べ替えることを考えます.
- 次を M 回行う:
- 0\leq k \leq K - 1 となる整数 k をひとつ選ぶ.
- その後,A を 10^k の位に関して安定ソートする.つまり,d=0,1,\ldots,9 に対して,A の部分列 A^{(d)} を A の要素のうち 10^k の位が d であるようなもの全体として定め,A^{(0)}, A^{(1)}, \ldots, A^{(9)} をこの順に連結してできる列で A を置き換える.
このような手順は K^M 通りありますが,その結果 A が B に等しくなるものの個数を 998244353 で割った余りを求めてください.
制約
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 10^9
- 1\leq K\leq 18
- 0\leq A_i < 10^K
- 0\leq B_i < 10^K
- A と B は多重集合として一致する.つまり任意の整数 x に対して,x が A に現れる回数は x が B に現れる回数と一致する.
入力
入力は以下の形式で標準入力から与えられます.
N M K A_1 \ldots A_N B_1 \ldots B_N
出力
A が B に等しくなるような手順の個数を 998244353 で割った余りを出力してください.
入力例 1
3 2 3 74 42 54 42 54 74
出力例 1
5
1 回目に選ぶ k を k_1,2 回目に選ぶ k を k_2 とします.例えば k_1 = 0, k_2 = 1 のとき A は次のように変化します.
- 10^{k_1} = 10^0 の位に関する安定ソートにより,A は (42,74,54) になる.
- 10^{k_2} = 10^1 の位に関する安定ソートにより,A は (42,54,74) になる.
すべての手順および,その結果の A は以下の通りです:
- (k_1, k_2) = (0,0):A = (42,74,54).
- (k_1, k_2) = (0,1):A = (42,54,74).
- (k_1, k_2) = (0,2):A = (42,74,54).
- (k_1, k_2) = (1,0):A = (42,54,74).
- (k_1, k_2) = (1,1):A = (42,54,74).
- (k_1, k_2) = (1,2):A = (42,54,74).
- (k_1, k_2) = (2,0):A = (42,74,54).
- (k_1, k_2) = (2,1):A = (42,54,74).
- (k_1, k_2) = (2,2):A = (74,42,54).
入力例 2
2 1 1 2 3 3 2
出力例 2
0
条件を満たす手順は存在しません.
入力例 3
5 100 4 0 12 34 56 78 0 12 34 56 78
出力例 3
982924732
4^{100} 通りの手順すべてが条件を満たします.
Score : 900 points
Problem Statement
For non-negative integers x and k, the k-th lowest digit of x is the remainder when \bigl\lfloor \frac{x}{10^k}\bigr\rfloor is divided by 10. For instance, the 0-th, 1-st, 2-nd, and 3-rd lowest digits of 123 are 3, 2, 1, and 0, respectively.
You are given positive integers N, M, K, and sequences of non-negative integers A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N).
Consider rearranging A by the following process.
- Do the following M times.
- Choose an integer k such that 0\leq k \leq K - 1.
- Then, perform a stable sort on A by k-th lowest digit. That is, let A^{(d)} be the subsequence of A composed of all elements of A whose k-th lowest digits are d, and replace A with the concatenation of A^{(0)}, A^{(1)}, \ldots, A^{(9)} in this order.
There are K^M ways to execute this process. How many of them end up making A equal B? Find this count modulo 998244353.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 10^9
- 1\leq K\leq 18
- 0\leq A_i < 10^K
- 0\leq B_i < 10^K
- A and B are equal as multisets. That is, every integer x occurs the same number of times in A and B.
Input
The input is given from Standard Input in the following format:
N M K A_1 \ldots A_N B_1 \ldots B_N
Output
Print the number, modulo 998244353, of ways to execute the process that end up making A equal B.
Sample Input 1
3 2 3 74 42 54 42 54 74
Sample Output 1
5
Let k_1 and k_2 be the k chosen in the first and second iterations, respectively. For instance, if k_1 = 0 and k_2 = 1, then A changes as follows.
- A stable sort by k_1-th (0-th) lowest digit makes A = (42,74,54).
- A stable sort by k_2-th (1-st) lowest digit makes A = (42,54,74).
Here are all the ways to execute the process and the resulting A.
- (k_1, k_2) = (0,0): A = (42,74,54).
- (k_1, k_2) = (0,1): A = (42,54,74).
- (k_1, k_2) = (0,2): A = (42,74,54).
- (k_1, k_2) = (1,0): A = (42,54,74).
- (k_1, k_2) = (1,1): A = (42,54,74).
- (k_1, k_2) = (1,2): A = (42,54,74).
- (k_1, k_2) = (2,0): A = (42,74,54).
- (k_1, k_2) = (2,1): A = (42,54,74).
- (k_1, k_2) = (2,2): A = (74,42,54).
Sample Input 2
2 1 1 2 3 3 2
Sample Output 2
0
There is no way to satisfy the condition.
Sample Input 3
5 100 4 0 12 34 56 78 0 12 34 56 78
Sample Output 3
982924732
All 4^{100} ways satisfy the condition.