Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
配列 A_1, \ldots, A_N があり、はじめ全ての i について A_i = i です。手順 \mathrm{shuffle}(L, R) を以下として定義します。
- R = L + 1 なら、A_L と A_R の値を入れ替えて終了する。
- そうでないなら、\mathrm{shuffle}(L, R - 1) を実行してから \mathrm{shuffle}(L + 1, R) を実行する。
\mathrm{shuffle}(1, N) を行うとします。手順終了後の A_K の値を出力してください。
各入力ファイルについて、テストケースを T 個解いてください。
制約
- 1 \leq T \leq 1000
- 2 \leq N \leq 10^{18}
- 1 \leq K \leq N
入力
入力は、標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは、以下の形式である。
N K
出力
T 行出力せよ。i 行目に、i 個目のテストケースの答えを出力すること。
入力例 1
7 2 1 2 2 5 1 5 2 5 3 5 4 5 5
出力例 1
2 1 2 4 1 5 3
N=2 のときは、以下を行って A=(2,1) を得ます。
- \mathrm{shuffle}(1, 2) を実行し、A_1 と A_2 を入れ替える。
N=5 のときは、以下を行って A=(2,4,1,5,3) を得ます。
- \mathrm{shuffle}(1, 5) を実行する。
- \mathrm{shuffle}(1, 4) を実行する。
- \mathrm{shuffle}(1, 3) を実行する。
- \vdots
- \mathrm{shuffle}(2, 4) を実行する。
- \vdots
- \mathrm{shuffle}(1, 3) を実行する。
- \mathrm{shuffle}(2, 5) を実行する。
- \mathrm{shuffle}(2, 4) を実行する。
- \vdots
- \mathrm{shuffle}(3, 5) を実行する。
- \vdots
- \mathrm{shuffle}(2, 4) を実行する。
- \mathrm{shuffle}(1, 4) を実行する。
Score : 500 points
Problem Statement
There is an array A_1, \ldots, A_N, and initially A_i = i for all i. Define the following routine \mathrm{shuffle}(L, R):
- If R = L + 1, swap values of A_L and A_R and terminate.
- Otherwise, run \mathrm{shuffle}(L, R - 1) followed by \mathrm{shuffle}(L + 1, R).
Suppose we run \mathrm{shuffle}(1, N). Print the value of A_K after the routine finishes.
For each input file, solve T test cases.
Constraints
- 1 \leq T \leq 1000
- 2 \leq N \leq 10^{18}
- 1 \leq K \leq N
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N K
Output
Print T lines. The i-th line should contain the answer for the i-th case.
Sample Input 1
7 2 1 2 2 5 1 5 2 5 3 5 4 5 5
Sample Output 1
2 1 2 4 1 5 3
For N=2, we do the following and get A=(2,1).
- Run \mathrm{shuffle}(1, 2), and swap A_1 and A_2.
For N=5, we do the following and get A=(2,4,1,5,3).
- Run \mathrm{shuffle}(1, 5):
- Run \mathrm{shuffle}(1, 4):
- Run \mathrm{shuffle}(1, 3):
- \vdots
- Run \mathrm{shuffle}(2, 4):
- \vdots
- Run \mathrm{shuffle}(1, 3):
- Run \mathrm{shuffle}(2, 5):
- Run \mathrm{shuffle}(2, 4):
- \vdots
- Run \mathrm{shuffle}(3, 5):
- \vdots
- Run \mathrm{shuffle}(2, 4):
- Run \mathrm{shuffle}(1, 4):
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
左側に N 個の頂点 v_1, \ldots, v_N、右側に N + 1 個の頂点 u_1, \ldots, u_{N + 1} を持つグラフがあります。各頂点 v_i (1 \leq i \leq N) は各頂点 u_j (1 \leq j \leq N + 1) と結ばれています。すなわち、グラフは N(N + 1) 本の辺を持ちます。
各辺を、N 種類の色 1, \ldots, N のうちいずれか一つで塗ります。k = 1, \ldots, N のいずれに対しても、色 k の辺がちょうど 2k 本あってそれらが単純パスをなすとき、塗り方を適切であるとします。
形式的には、各 k = 1, \ldots, N について相異なる頂点の列 w_0, \ldots, w_{2k} が存在して以下をすべて満たすとき、塗り方は適切です。
- 各 i = 0, \ldots, 2k - 1 について、頂点 w_i と w_{i + 1} は色 k の辺で結ばれている。
- 色 k の辺は他に存在しない。
適切な塗り方をいずれか一つ、あるいはそれが存在しないことを見出してください。
各入力ファイルについて、テストケースを T 個解いてください。
制約
- 1 \leq T \leq 100
- 1 \leq N \leq 100
入力
入力は、標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは、以下の形式である。
N
出力
それぞれのケースについて、適切な塗り方が存在しないなら、No
を出力せよ。そうでないなら、以下の形式で適切な塗り方を一つ出力せよ。
Yes C_{1, 1} C_{1, 2} \ldots C_{1, N + 1} \vdots C_{N, 1} C_{N, 2} \ldots C_{N, N + 1}
ここで、C_{i, j} は v_i と u_j を結ぶ辺の色である。
適切な塗り方が複数ある場合は、いずれを出力してもよい。
入力例 1
2 1 2
出力例 1
Yes 1 1 No
Score : 800 points
Problem Statement
There is a graph with N vertices v_1, \ldots, v_N on the left, and N + 1 vertices u_1, \ldots, u_{N + 1} on the right. Each vertex v_i (1 \leq i \leq N) is connected to each vertex u_j (1 \leq j \leq N + 1), that is, the graph contains N(N + 1) edges.
We color every edge with one of the N colors 1, \ldots, N. A coloring is suitable if for each k = 1, \ldots, N there are exactly 2k edges of color k, and those edges form a simple path.
Formally, for each k = 1, \ldots, N there should exist a sequence of distinct vertices w_0, \ldots, w_{2k} such that all of the following is true:
- For each i = 0, \ldots, 2k - 1, vertices w_i and w_{i + 1} are connected with an edge of color k,
- No other edges of color k exist.
Find any suitable coloring, or determine that it doesn't exist.
For each input file, solve T test cases.
Constraints
- 1 \leq T \leq 100
- 1 \leq N \leq 100
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N
Output
For each test case, if a suitable coloring does not exist, print No
. Otherwise, print a suitable coloring description in the following format:
Yes C_{1, 1} C_{1, 2} \ldots C_{1, N + 1} \vdots C_{N, 1} C_{N, 2} \ldots C_{N, N + 1}
Here, C_{i, j} is the color of the edge between v_i and u_j.
If there are many suitable colorings, print any of them.
Sample Input 1
2 1 2
Sample Output 1
Yes 1 1 No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
ある店を訪れる N 人の客がおり、彼らを 1,\ldots,N と呼びます。客 i は時刻 A_i に店に入り、時刻 B_i に店を出ます。この店の行列は「先入れ先出し」方式であり、A_i も B_i も単調増加です。また、A_i や B_i は全て異なります。
店の入口に、客が名前を書くリストがあります。それぞれの客は、入店時か退店時に一度だけ自分の名前をリストの末尾に書きます。最終的に名前が書かれる順序は何通りありうるでしょうか。 この数を 998\,244\,353 で割った余りを求めてください。
制約
- 1 \leq N \leq 5 \cdot 10^5
- 1 \leq A_i < B_i \leq 2N
- A_i < A_{i + 1} (1 \leq i \leq N - 1)
- B_i < B_{i + 1} (1 \leq i \leq N - 1)
- A_i \neq B_j (i \neq j)
- 入力中の値は全て整数である。
入力
入力は、標準入力から以下の形式で与えられる。
N A_1 B_1 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 1 3 2 5 4 6
出力例 1
3
ありうる順序は (1, 2, 3), (2, 1, 3), (1, 3, 2) です。
入力例 2
4 1 2 3 4 5 6 7 8
出力例 2
1
ありうる順序は (1, 2, 3, 4) のみです。
Score : 800 points
Problem Statement
There are N customers named 1,\ldots,N visiting a shop. Customer i arrives at time A_i and leaves at time B_i. The queue order is first in-first out, so A_i are increasing, and B_i are increasing. Additionally, all A_i and B_i are pairwise distinct.
At the entrance there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo 998\,244\,353.
Constraints
- 1 \leq N \leq 5 \cdot 10^5
- 1 \leq A_i < B_i \leq 2N
- A_i < A_{i + 1} (1 \leq i \leq N - 1)
- B_i < B_{i + 1} (1 \leq i \leq N - 1)
- A_i \neq B_j (i \neq j)
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 1 3 2 5 4 6
Sample Output 1
3
The possible orders are (1, 2, 3), (2, 1, 3), (1, 3, 2).
Sample Input 2
4 1 2 3 4 5 6 7 8
Sample Output 2
1
The only possible order is (1, 2, 3, 4).
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
正の整数 N, M と N \times M 正整数行列 A_{i, j} があります。二つの(狭義)単調増加正整数列 X = (X_1, \ldots, X_N), Y = (Y_1, \ldots, Y_M) に対し、ペナルティ D(X, Y) を \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}| と定義します。
D(X, Y) を最小化する二つの(狭義)単調増加正整数列 X, Y を求めてください。
制約
- 1 \leq N, M \leq 5
- 1 \leq A_{i, j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- 入力中の値は全て整数である。
入力
入力は、標準入力から以下の形式で与えられる。
N M A_{1,1} \ldots A_{1,M} \vdots A_{N,1} \ldots A_{N,M}
出力
答えを以下の形式で出力せよ。
D_{min} X_1 \ldots X_N Y_1 \ldots Y_M
ここで、D_{min} は最小のペナルティであり、また以下の条件が満たされなければならない。
- D(X, Y) は D_{min} に等しい。
- X_i < X_{i + 1} (1 \leq i \leq N - 1)
- Y_j < Y_{j + 1} (1 \leq j \leq M - 1)
- 1 \leq X_i \leq 2\cdot 10^9 (1 \leq i \leq N)
- 1 \leq Y_j \leq 2\cdot 10^9 (1 \leq j \leq M)
最後の二条件を満たす最適解が存在することは証明できる。
入力例 1
1 1 853922530
出力例 1
0 31415 27182
入力例 2
3 3 4 4 4 4 4 4 4 4 4
出力例 2
5 1 2 3 1 2 3
入力例 3
3 4 4674 7356 86312 100327 8737 11831 145034 167690 47432 66105 809393 936462
出力例 3
357 129 216 1208 39 55 670 775
Score : 1000 points
Problem Statement
There are positive integers N, M, and an N \times M positive integer matrix A_{i, j}. For two (strictly) increasing positive integer sequences X = (X_1, \ldots, X_N) and Y = (Y_1, \ldots, Y_M), we define the penalty D(X, Y) as \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}|.
Find two (strictly) increasing positive integer sequences X and Y such that D(X, Y) is the smallest possible.
Constraints
- 1 \leq N, M \leq 5
- 1 \leq A_{i, j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N M A_{1,1} \ldots A_{1,M} \vdots A_{N,1} \ldots A_{N,M}
Output
Output your answer in the following format:
D_{min} X_1 \ldots X_N Y_1 \ldots Y_M
Here, D_{min} is the smallest possible penalty and the following conditions should be satisfied:
- D(X, Y) should be equal to D_{min}.
- X_i < X_{i + 1} (1 \leq i \leq N - 1).
- Y_j < Y_{j + 1} (1 \leq j \leq M - 1).
- 1 \leq X_i \leq 2\cdot 10^9 (1 \leq i \leq N).
- 1 \leq Y_j \leq 2\cdot 10^9 (1 \leq j \leq M).
One can show that there is an optimal solution satisfying the last two conditions.
Sample Input 1
1 1 853922530
Sample Output 1
0 31415 27182
Sample Input 2
3 3 4 4 4 4 4 4 4 4 4
Sample Output 2
5 1 2 3 1 2 3
Sample Input 3
3 4 4674 7356 86312 100327 8737 11831 145034 167690 47432 66105 809393 936462
Sample Output 3
357 129 216 1208 39 55 670 775
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
非負整数 X があり、はじめその値は S です。以下の操作を任意の順に何度でも行うことができます。
- X に 1 を足す。この操作のコストは A である。
- 1 以上 N 以下の i を選び、X を X \oplus Y_i に置き換える。この操作のコストは C_i である。ここで、\oplus はビット単位 \mathrm{XOR} 演算を表す。
与えられた非負整数 T に X を等しくするのに必要な最小の合計コストを求めるか、それが不可能であることを報告してください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR}、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に、k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 8
- 0 \leq S, T < 2^{40}
- 0 \leq A \leq 10^5
- 0 \leq Y_i < 2^{40} (1 \leq i \leq N)
- 0 \leq C_i \leq 10^{16} (1 \leq i \leq N)
- 入力中の値は全て整数である。
入力
入力は、標準入力から以下の形式で与えられる。
N S T A Y_1 C_1 \vdots Y_N C_N
出力
課題が達成不可能なら、-1
を出力せよ。
そうでないなら、必要な最小の合計コストを出力せよ。
入力例 1
1 15 0 1 8 2
出力例 1
5
以下の方法で X を T と等しくすることができます。
- i=1 を選んで X を X \oplus 8 に置き換え、X=7 とする。この操作のコストは 2 である。
- X に 1 を足し、X=8 とする。この操作のコストは 1 である。
- i=1 を選んで X を X \oplus 8 に置き換え、X=0 とする。この操作のコストは 2 である。
入力例 2
3 21 10 100 30 1 12 1 13 1
出力例 2
3
入力例 3
1 2 0 1 1 1
出力例 3
-1
入力例 4
8 352217 670575 84912 239445 2866 537211 16 21812 6904 50574 8842 380870 5047 475646 8924 188204 2273 429397 4854
出力例 4
563645
Score : 1400 points
Problem Statement
There is a non-negative integer X initially equal to S. One can perform the following operations, in any order, any number of times:
- Add 1 to X. This has a cost of A.
- Choose i between 1 and N, and replace X with X \oplus Y_i. This has a cost of C_i. Here, \oplus denotes bitwise \mathrm{XOR}.
Find the smallest total cost to make X equal to a given non-negative integer T, or report that this is impossible.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq 8
- 0 \leq S, T < 2^{40}
- 0 \leq A \leq 10^5
- 0 \leq Y_i < 2^{40} (1 \leq i \leq N)
- 0 \leq C_i \leq 10^{16} (1 \leq i \leq N)
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N S T A Y_1 C_1 \vdots Y_N C_N
Output
If the task is impossible, print -1
.
Otherwise, print the smallest total cost.
Sample Input 1
1 15 0 1 8 2
Sample Output 1
5
You can make X equal to T in the following manner:
- Choose i=1 and replace X with X \oplus 8 to get X=7. This has a cost of 2.
- Add 1 to X to get X=8. This has a cost of 1.
- Choose i=1 and replace X with X \oplus 8 to get X=0. This has a cost of 2.
Sample Input 2
3 21 10 100 30 1 12 1 13 1
Sample Output 2
3
Sample Input 3
1 2 0 1 1 1
Sample Output 3
-1
Sample Input 4
8 352217 670575 84912 239445 2866 537211 16 21812 6904 50574 8842 380870 5047 475646 8924 188204 2273 429397 4854
Sample Output 4
563645
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
正の整数 N, M があります。
0
と 1
からなる文字列 s は、以下を全て満たすときに良いといわれます。
- s は空でない。
- s に含まれる
1
の個数は N の倍数である。 - s に含まれる
0
の個数は M の倍数である。
良い文字列は、より短い良い文字列を(連続した)部分文字列として含まないときに完璧であるといわれます。例えば、N = 3, M = 2 のとき、文字列 111
, 00
, 10101
は完璧ですが、0000
, 11001
は完璧ではありません。
任意の N, M について、完璧な文字列の個数は有限であることが示せます。与えられた N, M について、この個数を 998\,244\,353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 40
- 入力中の値は全て整数である。
入力
入力は、標準入力から以下の形式で与えられる。
N M
出力
答えを出力せよ。
入力例 1
2 2
出力例 1
4
完璧な文字列は 00
, 0101
, 1010
, 11
です。
入力例 2
3 2
出力例 2
7
完璧な文字列は 00
, 01011
, 01101
, 10101
, 10110
, 11010
, 111
です。
入力例 3
23 35
出力例 3
212685109
Score : 2000 points
Problem Statement
There are positive integers N and M.
A binary string s is called good if all of the followings are satisfied:
- s is non-empty.
- The number of
1
s in s is a multiple of N. - The number of
0
s in s is a multiple of M.
A good string is called perfect if it doesn't contain shorter good (contiguous) substrings. For example, if N = 3 and M = 2, then strings 111
, 00
and 10101
are perfect, but 0000
and 11001
are not.
One can show that for any N, M the number of perfect strings is finite. Find this number modulo 998\,244\,353.
Constraints
- 1 \leq N, M \leq 40
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 2
Sample Output 1
4
The perfect strings are 00
, 0101
, 1010
, 11
.
Sample Input 2
3 2
Sample Output 2
7
The perfect strings are 00
, 01011
, 01101
, 10101
, 10110
, 11010
, 111
.
Sample Input 3
23 35
Sample Output 3
212685109