Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 行 N 列の行列 A=(a_{i,j}) が与えられます。ここで、a_{i,j} \in \{0,1\} が成り立ちます。
また、以下のような有向グラフがあります。
- 頂点数は NK で、各頂点には 1,2,\ldots,NK と番号が付けられている。
- 辺は A を縦 K 行横 K 列に並べて得られる NK 行 NK 列の行列 X=(x_{i,j}) によって表される(入出力例1にて A, K に対応する X が示されている)。具体的には、x_{i,j}=1 ならば頂点 i から頂点 j への有向辺が存在し、x_{i,j}=0 ならば存在しない。
i=1,2,\ldots,Q に対し、次の問題に答えてください。
- 頂点 s_i から頂点 t_i への経路の長さ(辺の本数)の最小値を求めよ。ただし、そのような経路が存在しない場合は代わりに
-1
と出力せよ。
制約
- 1 \leq N \leq 100
- 1 \leq K \leq 10^9
- a_{i,j} \in \{0,1\}
- 1 \leq Q \leq 100
- 1 \leq s_i,t_i \leq NK
- s_i \neq t_i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K a_{1,1} \ldots a_{1,N} \vdots a_{N,1} \ldots a_{N,N} Q s_1 t_1 \vdots s_Q t_Q
出力
Q 行出力せよ。x 行目には、i=x に対する問題の答えを出力せよ。
入力例 1
3 2 1 1 1 1 1 0 0 1 0 4 1 2 1 4 1 6 6 3
出力例 1
1 1 1 3
この例において、辺を表す行列 X は以下のようになります。
1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0
入力例 2
4 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 4000000000
出力例 2
-1
辺が 1 本も存在しません。
Score : 300 points
Problem Statement
You are given an N-by-N matrix A=(a_{i,j}), where a_{i,j} \in \{0,1\}.
We have the following directed graph.
- The graph has NK vertices numbered 1,2,\ldots,NK.
- The edges correspond to the NK-by-NK matrix X=(x_{i,j}) obtained by arranging K^2 copies of A in K rows and K columns (see Sample Input/Output 1 for an example). If x_{i,j}=1, there is a directed edge from vertex i to vertex j; if x_{i,j}=0, that edge does not exist.
Answer the following question for i=1,2,\ldots,Q.
- Find the shortest length (number of edges) of a path from vertex s_i to vertex t_i. If there is no such path, print
-1
instead.
Constraints
- 1 \leq N \leq 100
- 1 \leq K \leq 10^9
- a_{i,j} \in \{0,1\}
- 1 \leq Q \leq 100
- 1 \leq s_i,t_i \leq NK
- s_i \neq t_i
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K a_{1,1} \ldots a_{1,N} \vdots a_{N,1} \ldots a_{N,N} Q s_1 t_1 \vdots s_Q t_Q
Output
Print Q lines. The x-th line should contain the answer to the question for i=x.
Sample Input 1
3 2 1 1 1 1 1 0 0 1 0 4 1 2 1 4 1 6 6 3
Sample Output 1
1 1 1 3
Below is the matrix X representing the edges.
1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0
Sample Input 2
4 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 4000000000
Sample Output 2
-1
There is no edge.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
変数 a,b があり、初め a=A, b=B です。
高橋君は a,b がともに 1 以上の間、次の操作を繰り返すことにしました。
- a と b の最大公約数を g とする。そして、a,b をそれぞれ a-g,b-g に置き換える。
操作は何回行われますか。
制約
- 1 \leq A,B \leq 10^{12}
- A,B は整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
15 9
出力例 1
2
a=15,b=9 の状態から以下のように操作が行われます。
- g=3 とする。そして、a,b がそれぞれ 12(=15-3),6(=9-3) に置き換えられる。
- g=6 とする。そして、a,b がそれぞれ 6(=12-6),0(=6-6) に置き換えられる。b が 1 以上でなくなったため、操作の繰り返しはここで終了する。
入力例 2
1 1
出力例 2
1
入力例 3
12345678910 10987654321
出力例 3
36135
Score : 400 points
Problem Statement
We have variables a and b. Initially, a=A and b=B.
Takahashi will repeat the following operation while both a and b are greater than or equal to 1.
- Let g be the greatest common divisor of a and b, and replace a and b with a-g and b-g, respectively.
How many times will he perform the operation?
Constraints
- 1 \leq A,B \leq 10^{12}
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
15 9
Sample Output 1
2
We start with a=15,b=9 and perform the following.
- Let g=3, and replace a and b with 12(=15-3) and 6(=9-3), respectively.
- Let g=6, and replace a and b with 6(=12-6) and 0(=6-6), respectively. b is no longer greater than or equal to 1, so the iteration terminates.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
12345678910 10987654321
Sample Output 3
36135
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数列 A=(a_1,\ldots,a_N) が与えられます。
次の操作を 0 回以上 10^4 回以下繰り返すことで A の値をすべて等しくできるかを判定し、可能な場合は操作列の一例を示してください。
- (1,\ldots,N) の順列 (p_1,\ldots,p_N) を決め、A を (a_1+p_1,\ldots,a_N+p_N) に置き換える。
制約
- 2 \leq N \leq 50
- 1 \leq a_i \leq 50
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
A の値をすべて等しくできない場合は No
と出力せよ。
等しくできる場合、操作回数を M 回、i 回目の操作における順列を (p_{i,1},\ldots,p_{i,N}) として以下の形式で出力せよ。
Yes M p_{1,1} \ldots p_{1,N} \vdots p_{M,1} \ldots p_{M,N}
答えが複数存在する場合はどれを出力しても正解とみなされる。
入力例 1
2 15 9
出力例 1
Yes 8 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2
この出力例の通りに 8 回の操作を行うことで A は (24,24) となり、値がすべて等しくなります。
入力例 2
5 1 2 3 10 10
出力例 2
No
入力例 3
4 1 1 1 1
出力例 3
Yes 0
初めから A の値がすべて等しいです。
Score : 500 points
Problem Statement
You are given a sequence of positive integers: A=(a_1,\ldots,a_N).
Determine whether it is possible to make all elements of A equal by repeating the following operation between 0 and 10^4 times, inclusive. If it is possible, show one way to do so.
- Choose a permutation (p_1,\ldots,p_N) of (1,\ldots,N), and replace A with (a_1+p_1,\ldots,a_N+p_N).
Constraints
- 2 \leq N \leq 50
- 1 \leq a_i \leq 50
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
If it is impossible to make all elements of A equal, print No
.
If it is possible, print one way to do so in the following format, where M is the number of operations, and (p_{i,1},\ldots,p_{i,N}) is the permutation chosen in the i-th operation:
Yes M p_{1,1} \ldots p_{1,N} \vdots p_{M,1} \ldots p_{M,N}
If multiple solutions exist, you may print any of them.
Sample Input 1
2 15 9
Sample Output 1
Yes 8 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2
This sequence of 8 operations makes A = (24,24), where all elements are equal.
Sample Input 2
5 1 2 3 10 10
Sample Output 2
No
Sample Input 3
4 1 1 1 1
Sample Output 3
Yes 0
All elements of A are equal from the beginning.
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
数列 X があります。初め、X は空です。
高橋君は i=1,2,\ldots,N の順に次の操作をしました。
- X の末尾に l_i,l_i+1,\ldots,r_i をこの順番で追加する。
操作後の X の狭義単調増加部分列の長さの最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq l_i \leq r_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N l_1 r_1 \vdots l_{N} r_{N}
出力
答えを出力せよ。
入力例 1
4 1 1 2 4 10 11 7 10
出力例 1
8
操作後の X は (1,2,3,4,10,11,7,8,9,10) です。
この数列の 1,2,3,4,7,8,9,10 項目からなる部分列は狭義単調増加であり、かつこれが長さが最大のものです。
入力例 2
4 1 1 1 1 1 1 1 1
出力例 2
1
操作後の X は (1,1,1,1) です。
入力例 3
1 1 1000000000
出力例 3
1000000000
Score : 600 points
Problem Statement
We have a sequence X, which is initially empty.
Takahashi has performed the following operation for i=1,2,\ldots,N in this order.
- Append l_i,l_i+1,\ldots,r_i in this order to the end of X.
Find the greatest length of a strictly increasing subsequence of the final X.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq l_i \leq r_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N l_1 r_1 \vdots l_{N} r_{N}
Output
Print the answer.
Sample Input 1
4 1 1 2 4 10 11 7 10
Sample Output 1
8
The final X is (1,2,3,4,10,11,7,8,9,10).
The 1-st, 2-nd, 3-rd, 4-th, 7-th, 8-th, 9-th, and 10-th elements form a strictly increasing subsequence with the greatest length.
Sample Input 2
4 1 1 1 1 1 1 1 1
Sample Output 2
1
The final X is (1,1,1,1).
Sample Input 3
1 1 1000000000
Sample Output 3
1000000000
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
正整数 N と M 個の正整数の組 (a_0,b_0),\ldots,(a_{M-1},b_{M-1}) が与えられます( a_i,b_i は添え字が 0 から始まることに気を付けてください)。
また、以下のような非負整数列 X=(x_1,\ldots,x_N) があります。
- x_i は以下の手順で定まる。
- l=1,r=N,t=0 とする。
- m=\left \lfloor \dfrac{a_{t \bmod M} \times l + b_{t \bmod M} \times r}{a_{t \bmod M} +b_{t \bmod M}} \right \rfloor とする( \lfloor x \rfloor は x を超えない最大の整数)。m=i ならば x_i=t として手順を終了する。
- l \leq i \lt m ならば r=m-1、そうでなければ l=m+1 とする。 t の値を 1 増やし、2へ戻る。
i=1,2,\ldots,Q に対し、\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| の値を求めてください。
なお、本問の制約の下、答えが 10^{18} 以下であることが示せます。
制約
- 2 \leq N \leq 10^{15}
- 1 \leq M \leq 100
- 1 \leq a_i,b_i \leq 1000
- \max \left (\dfrac{a_i}{b_i},\dfrac{b_i}{a_i}\right ) \leq 2
- 1 \leq Q \leq 10^4
- 1 \leq c_i \lt d_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_0 b_0 \vdots a_{M-1} b_{M-1} Q c_1 d_1 \vdots c_Q d_Q
出力
Q 行出力せよ。x 行目には、i=x に対する問題の答えを出力せよ。
入力例 1
5 1 1 1 3 1 2 2 4 3 5
出力例 1
1 3 2
X=(1,2,0,1,2) です。例えば、x_1 は以下の手順で定まります。
- l=1,r=5(=N),t=0 とする。
- m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor) とする。
- l \leq 1 \lt m なので r=2(=m-1) とする。t の値を 1 増やして 1 とする。
- m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor ) とする。m=1 なので x_1=1(=t) として手順を終了する。
(c_i,d_i) への答えは、例えば (c_1,d_1) の場合、 \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1 となります。
入力例 2
1000000000000000 2 15 9 9 15 3 100 10000 5000 385723875 150 17095708
出力例 2
19792 771437738 34191100
Score : 900 points
Problem Statement
You are given a positive integer N, and M pairs of positive integers: (a_0,b_0),\ldots,(a_{M-1},b_{M-1}) (note that a_i and b_i start with index 0).
We have the following sequence of non-negative integers X=(x_1,\ldots,x_N).
- x_i is determined as follows.
- Let l=1, r=N, and t=0.
- Let m=\left \lfloor \dfrac{a_{t \bmod M} \times l + b_{t \bmod M} \times r}{a_{t \bmod M} +b_{t \bmod M}} \right \rfloor (\lfloor x \rfloor is the greatest integer not exceeding x). If m=i, let x_i=t and terminate.
- If l \leq i \lt m, let r=m-1; otherwise, let l=m+1. Increment t by 1 and return to step 2.
Find \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| for i=1,2,\ldots,Q.
It can be proved that the answers are at most 10^{18} under the constraints of this problem.
Constraints
- 2 \leq N \leq 10^{15}
- 1 \leq M \leq 100
- 1 \leq a_i,b_i \leq 1000
- \max \left (\dfrac{a_i}{b_i},\dfrac{b_i}{a_i}\right ) \leq 2
- 1 \leq Q \leq 10^4
- 1 \leq c_i \lt d_i \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M a_0 b_0 \vdots a_{M-1} b_{M-1} Q c_1 d_1 \vdots c_Q d_Q
Output
Print Q lines. The x-th line should contain the answer to the question for i=x.
Sample Input 1
5 1 1 1 3 1 2 2 4 3 5
Sample Output 1
1 3 2
We have X=(1,2,0,1,2). For example, x_1 is determined as follows.
- Let l=1, r=5(=N), and t=0.
- Let m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor).
- Since l \leq 1 \lt m, let r=2(=m-1). Increment t by 1 to 1.
- Let m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor ). Since m=1, let x_1=1(=t) and terminate.
The answer to the question for (c_1,d_1), for example, is \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1.
Sample Input 2
1000000000000000 2 15 9 9 15 3 100 10000 5000 385723875 150 17095708
Sample Output 2
19792 771437738 34191100
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
数列 X が次の条件を満たす時、X を良い数列と呼ぶことにします。
- 次の操作を 0 回以上繰り返すことで X を空の列に出来る。
- X の隣り合う 2 要素 x_i,x_{i+1} であって x_i \neq x_{i+1} を満たすものを選び、削除する。
2N 要素の数列 A=(a_1,\ldots,a_{2N}) が与えられます。
A を 1 個以上の連続部分列に分割する方法は 2^{2N-1} 通りありますが、そのうち各連続部分列がすべて良い数列であるようなものが何通りあるかを 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq a_i \leq 2N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_{2N}
出力
答えを出力せよ。
入力例 1
3 1 1 2 3 4 5
出力例 1
2
以下の 2 通りの分割方法が条件を満たします。
- (1,1,2,3,4,5)
- (1,1,2,3),(4,5)
入力例 2
1 1 2
出力例 2
1
入力例 3
1 1 1
出力例 3
0
入力例 4
12 4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15
出力例 4
2048
Score : 900 points
Problem Statement
A sequence X is called good when the following holds.
- X can be emptied by repeating the following operation zero or more times.
- Delete two adjacent elements x_i and x_{i+1} of X such that x_i \neq x_{i+1}.
You are given a sequence with 2N elements: A=(a_1,\ldots,a_{2N}).
Among the 2^{2N-1} ways to divide A into one or more contiguous subsequences, how many are such that all those contiguous subsequences are good? Find the count modulo 998244353.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq a_i \leq 2N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N a_1 \ldots a_{2N}
Output
Print the answer.
Sample Input 1
3 1 1 2 3 4 5
Sample Output 1
2
The following two divisions satisfy the condition.
- (1,1,2,3,4,5)
- (1,1,2,3),(4,5)
Sample Input 2
1 1 2
Sample Output 2
1
Sample Input 3
1 1 1
Sample Output 3
0
Sample Input 4
12 4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15
Sample Output 4
2048