Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。
以下の条件を全て満たす整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するなら一つ求めてください。
- -10^8\le X_i\le 10^8 (1\le i\le N)
- \displaystyle \sum_{i=1}^N A_iX_i > 0
- \displaystyle \sum_{i=1}^N B_iX_i < 0
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le N\le 2\times 10^5
- 1\le A_i,B_i\le 10^5
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす X が存在しない場合は No と出力せよ。
そうでない場合、条件を全て満たす X を以下の形式で出力せよ。
Yes X_1 X_2 \ldots X_N
条件を満たす X が複数ある場合、どれを出力しても正答となる。
入力例 1
3 3 3 1 4 1 5 1 3 4 4 4 7 7 7 4 20 25 6 15 31 41 59 26
出力例 1
Yes 4 -5 1 No Yes 45 -10 -40 11
1 つ目のテストケースについて、 X=(4,-5,1) とすると
- \displaystyle \sum_{i=1}^3 A_iX_i=3\times 4+1\times (-5)+4\times 1=11>0
- \displaystyle \sum_{i=1}^3 B_iX_i=1\times 4+5\times (-5)+1\times 1=-20<0
となり条件を満たします。この他にも X=(3,-3,1) や X=(27,-40,22) などが条件を満たします。
Score : 500 points
Problem Statement
You are given sequences of positive integers of length N: A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N).
Determine whether there exists an integer sequence X=(X_1,X_2,\ldots,X_N) that satisfies all the following conditions, and if it exists, find one.
- -10^8\le X_i\le 10^8 (1\le i\le N)
- \displaystyle \sum_{i=1}^N A_iX_i > 0
- \displaystyle \sum_{i=1}^N B_iX_i < 0
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 2\times 10^5
- 1\le N\le 2\times 10^5
- 1\le A_i,B_i\le 10^5
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
Output your solutions for the test cases in order, separated by newlines.
For each test case, if there is no X that satisfies all conditions, output No.
Otherwise, output an X that satisfies all conditions in the following format:
Yes X_1 X_2 \ldots X_N
If there are multiple X that satisfy the conditions, you may output any of them.
Sample Input 1
3 3 3 1 4 1 5 1 3 4 4 4 7 7 7 4 20 25 6 15 31 41 59 26
Sample Output 1
Yes 4 -5 1 No Yes 45 -10 -40 11
For the first test case, if we set X=(4,-5,1), then
- \displaystyle \sum_{i=1}^3 A_iX_i=3\times 4+1\times (-5)+4\times 1=11>0
- \displaystyle \sum_{i=1}^3 B_iX_i=1\times 4+5\times (-5)+1\times 1=-20<0
which satisfies the conditions. Other examples that satisfy the conditions include X=(3,-3,1) and X=(27,-40,22).
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 A_1,A_2,A_3 が与えられます。
以下の条件を全て満たす正整数の組 (X_1,X_2) が存在するか判定し、存在する場合は一組求めてください。
- X_1 は十進法で A_1 桁の整数である。
- X_2 は十進法で A_2 桁の整数である。
- X_1 と X_2 の最小公倍数は十進法で A_3 桁の整数である。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 17^3
- 1\le A_1,A_2,A_3\le 17
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
A_1 A_2 A_3
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす (X_1,X_2) が存在しない場合は No と出力せよ。
そうでない場合、条件を全て満たす (X_1,X_2) を以下の形式で出力せよ。
Yes X_1 X_2
条件を満たす (X_1,X_2) が複数ある場合、どれを出力しても正答となる。
入力例 1
3 4 3 5 1 1 7 8 6 11
出力例 1
Yes 2025 200 No Yes 20250615 200200
1 つ目のテストケースについて、 (X_1,X_2)=(2025,200) とすると X_1,X_2 の最小公倍数は 16200 となり条件を満たすことが分かります。その他にも (X_1,X_2)=(2025,125),(7777,231) などが条件を満たします。
Score : 600 points
Problem Statement
You are given positive integers A_1,A_2,A_3.
Determine whether there exists a pair of positive integers (X_1,X_2) that satisfies all the following conditions, and if it exists, find one.
- X_1 is an integer with A_1 digits in decimal notation.
- X_2 is an integer with A_2 digits in decimal notation.
- The least common multiple of X_1 and X_2 is an integer with A_3 digits in decimal notation.
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 17^3
- 1\le A_1,A_2,A_3\le 17
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
A_1 A_2 A_3
Output
Output your solutions for the test cases in order, separated by newlines.
For each test case, if there is no (X_1,X_2) that satisfies all conditions, output No.
Otherwise, output a (X_1,X_2) that satisfies all conditions in the following format:
Yes X_1 X_2
If there are multiple (X_1,X_2) that satisfy the conditions, you may output any of them.
Sample Input 1
3 4 3 5 1 1 7 8 6 11
Sample Output 1
Yes 2025 200 No Yes 20250615 200200
For the first test case, if we set (X_1,X_2)=(2025,200), then the least common multiple of X_1,X_2 is 16200, which satisfies the conditions. Other examples that satisfy the conditions include (X_1,X_2)=(2025,125),(7777,231).
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
正整数 N と長さ N の正整数列 L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N) が与えられます。ここで、 L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N は全て互いに異なることが保証されます。
ある映画館には N 個の席が左右一列に並んでいます。左から i 番目の席を席 i と呼びます。
この映画館に人 1 から人 N までの N 人の人が訪れます。あなたは各人に席を 1 つずつ割り当てます。人 i に割り当てた席を P_i とすると、人 i は時刻 L_i に席 1,2,\ldots,P_i-1 を横切って席 P_i に座り、時刻 R_i に席 1,2,\ldots,P_i-1 を横切って席から離れます。
人 i の 不満度 を時刻 L_i から時刻 R_i までの間（ちょうど L_i,R_i は含まない）に他の人に席 P_i を横切られた回数とします。
人 1 から人 N までの N 人の不満度の総和が最小となる (1,2,\ldots,N) の順列 P のうち辞書順最小のものを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 500
- 1\le N\le 500
- 1\le L_i < R_i\le 2\times N
- L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N は全て互いに異なる
- 全てのテストケースにおける N の総和は 500 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
T 行出力せよ。
i 行目には i 番目のテストケースについて、人 1 から人 N までの N 人の不満度の総和が最小となる (1,2,\ldots,N) の順列 P のうち辞書順最小のものを半角スペース区切りで出力せよ。
入力例 1
3 3 1 5 2 3 4 6 4 1 5 2 6 3 7 4 8 6 6 10 2 11 7 8 1 9 3 4 5 12
出力例 1
2 1 3 1 2 3 4 2 4 1 5 3 6
1 つ目のテストケースについて、P=(2,1,3) とすると以下のように進みます：
- 時刻 1 ：人 1 が席 2 に座る。
- 時刻 2 ：人 2 が席 1 に座る。
- 時刻 3 ：人 2 が席 1 から離れる。
- 時刻 4 ：人 3 が席 3 に座る。人 1 の不満度が 1 増える。
- 時刻 5 ：人 1 が席 2 から離れる。
- 時刻 6 ：人 3 が席 3 から離れる。
この際の全員の不満度の総和は 1 です。
不満度の総和を 1 より小さくすることはできず、さらに P=(2,1,3) が不満度の総和が 1 となる P のうち辞書順最小です。したがって、 P=(2,1,3) が答えとなります。
2 つ目のテストケースについて、どのような順列 P に対しても全員の不満度の総和は 6 となります。
Score : 700 points
Problem Statement
You are given a positive integer N and sequences of positive integers of length N: L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N). It is guaranteed that L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N are all distinct.
A movie theater has N seats arranged in a row from left to right. The i-th seat from the left is called seat i.
N people, numbered 1 to N, visit this movie theater. You assign one seat to each person. Let P_i be the seat assigned to person i. Then, person i arrives at time L_i, crosses seats 1,2,\ldots,P_i-1 to sit in seat P_i, and leaves at time R_i, crossing seats 1,2,\ldots,P_i-1 to exit.
The dissatisfaction of person i is the number of times other people cross seat P_i during the time interval from time L_i to time R_i (not including exactly L_i and R_i).
Find the lexicographically smallest permutation P of (1,2,\ldots,N) that minimizes the total dissatisfaction of all people from 1 to N.
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 500
- 1\le N\le 500
- 1\le L_i < R_i\le 2\times N
- L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N are all distinct.
- The sum of N over all test cases is at most 500.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Output T lines.
The i-th line should contain the lexicographically smallest permutation P of (1,2,\ldots,N) that minimizes the total dissatisfaction of all people from 1 to N for the i-th test case, separated by spaces.
Sample Input 1
3 3 1 5 2 3 4 6 4 1 5 2 6 3 7 4 8 6 6 10 2 11 7 8 1 9 3 4 5 12
Sample Output 1
2 1 3 1 2 3 4 2 4 1 5 3 6
For the first test case, if we set P=(2,1,3), the process proceeds as follows:
- Time 1: Person 1 sits in seat 2.
- Time 2: Person 2 sits in seat 1.
- Time 3: Person 2 leaves seat 1.
- Time 4: Person 3 sits in seat 3. Person 1's dissatisfaction increases by 1.
- Time 5: Person 1 leaves seat 2.
- Time 6: Person 3 leaves seat 3.
The total dissatisfaction of all people in this case is 1.
It is impossible to make the total dissatisfaction smaller than 1, and furthermore, P=(2,1,3) is lexicographically smallest among all P with total dissatisfaction of 1. Therefore, P=(2,1,3) is the answer.
For the second test case, the total dissatisfaction of all people is 6 for any permutation P.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
正整数 M,K が与えられます。
以下の条件を全て満たす正整数 N と整数列 A=(A_1,A_2,\ldots, A_N) が存在するか判定し、存在するなら一つ求めてください。
- 1\le N\le M
- 0\le A_i < M (1\le i\le N)
- k\equiv A_i+A_j \pmod M を満たす添字の組 (i,j) が存在するような整数 0\le k < M がちょうど K 個存在する。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le K\le M\le 2\times 10^5
- 全てのテストケースにおける M の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
M K
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす N,A が存在しない場合は No を出力せよ。
そうでない場合、条件を全て満たす N と A を以下の形式で出力せよ。
Yes N A_1 A_2 \ldots A_N
条件を全て満たす N と A が複数ある場合、どれを出力しても正答となる。
入力例 1
3 6 5 3 2 8 3
出力例 1
Yes 3 3 1 4 No Yes 2 0 1
1 つ目のテストケースについて、 A=(3,1,4) とすると
- k=0 ： (i,j)=(1,1) とすると 0\equiv 3+3\pmod 6 が成立する。
- k=1 ： (i,j)=(1,3) とすると 1\equiv 3+4\pmod 6 が成立する。
- k=2 ： (i,j)=(3,3) とすると 2\equiv 4+4\pmod 6 が成立する。
- k=3 ： 条件を満たす添字の組 (i,j) は存在しない。
- k=4 ： (i,j)=(1,2) とすると 4\equiv 3+1\pmod 6 が成立する。
- k=5 ： (i,j)=(2,3) とすると 5\equiv 1+4\pmod 6 が成立する。
となり、条件を満たす 0\le k < 6 はちょうど 5 個であることが分かります。
Score : 700 points
Problem Statement
You are given positive integers M,K.
Determine whether there exist a positive integer N and an integer sequence A=(A_1,A_2,\ldots, A_N) that satisfy all the following conditions, and if they exist, find one.
- 1\le N\le M
- 0\le A_i < M (1\le i\le N)
- There are exactly K integers 0\le k < M such that there exists a pair of indices (i,j) satisfying k\equiv A_i+A_j \pmod M.
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 2\times 10^5
- 1\le K\le M\le 2\times 10^5
- The sum of M over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
M K
Output
Output your solutions for the test cases in order, separated by newlines.
For each test case, if there are no N,A that satisfy all conditions, output No.
Otherwise, output N and A that satisfy all conditions in the following format:
Yes N A_1 A_2 \ldots A_N
If there are multiple N and A that satisfy the conditions, you may output any of them.
Sample Input 1
3 6 5 3 2 8 3
Sample Output 1
Yes 3 3 1 4 No Yes 2 0 1
For the first test case, if we set A=(3,1,4), then
- k=0: Setting (i,j)=(1,1), we have 0\equiv 3+3\pmod 6.
- k=1: Setting (i,j)=(1,3), we have 1\equiv 3+4\pmod 6.
- k=2: Setting (i,j)=(3,3), we have 2\equiv 4+4\pmod 6.
- k=3: There is no pair of indices (i,j) that satisfies the condition.
- k=4: Setting (i,j)=(1,2), we have 4\equiv 3+1\pmod 6.
- k=5: Setting (i,j)=(2,3), we have 5\equiv 1+4\pmod 6.
Thus, there are exactly 5 values of 0\le k < 6 that satisfy the condition.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
正整数 N,M が与えられます。
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) であって、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを求めてください。
- 0\le A_i < 2^M (1\le i\le N)
- \operatorname{popcount}(A_i\oplus A_j) \le 2 (1\le i < j\le N)
ただし、非負整数 x,y に対し x\oplus y を x と y のビット単位 \mathrm{XOR} 演算、 \operatorname{popcount}(x) を x の popcount とします。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
popcount とは
非負整数 x について \operatorname{popcount}(x) とは、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 となります。
制約
- 1\le T\le 2\times 10^5
- 2\le N,M < 998244353
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M
出力
T 行出力せよ。 i 行目には i 番目のテストケースの答えを出力せよ。
入力例 1
3 2 3 7 2 2025 200
出力例 1
56 16384 549499339
1 つ目のテストケースについて考えます。
例えば A=(4,5) は各要素が 0 以上 2^3=8 未満で \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2 なので条件を満たします。一方、 A=(2,5) や A=(0,7) は条件を満たしません。
条件を満たす A は 56 通り存在するので、 1 行目には 56 を出力してください。
Score : 800 points
Problem Statement
You are given positive integers N,M.
Find the number, modulo 998244353, of non-negative integer sequences A=(A_1,A_2,\ldots,A_N) of length N that satisfy all the following conditions.
- 0\le A_i < 2^M (1\le i\le N)
- \operatorname{popcount}(A_i\oplus A_j) \le 2 (1\le i < j\le N)
Here, for non-negative integers x,y, we denote by x\oplus y the bitwise \mathrm{XOR} operation of x and y, and by \operatorname{popcount}(x) the popcount of x.
You are given T test cases, so find the answer for each.
What is bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers A, B, denoted A \oplus B, is defined as follows.
- When A \oplus B is written in binary, the digit in the 2^k (k \geq 0) place is 1 if exactly one of A, B has 1 in the 2^k place when written in binary, and 0 otherwise.
What is popcount?
For a non-negative integer x, \operatorname{popcount}(x) is the number of 1s when x is written in binary. 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 we have \operatorname{popcount}(13)=3.
Constraints
- 1\le T\le 2\times 10^5
- 2\le N,M < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 2 3 7 2 2025 200
Sample Output 1
56 16384 549499339
Consider the first test case.
For example, A=(4,5) satisfies the conditions because each element is between 0 and 2^3-1=7, and \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2. On the other hand, neither A=(2,5) nor A=(0,7) satisfies the conditions.
There are 56 sequences A that satisfy the conditions, so output 56 on the first line.