Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
高橋キングダムには、高橋諸島という、N 個の島からなる諸島があります。 便宜上、これらの島を島 1、島 2、 ...、島 N と呼ぶことにします。
これらの諸島の間では、船の定期便が M 種類運行されています。 定期便はそれぞれ 2 つの島の間を行き来しており、i 種類目の定期便を使うと、 島 a_i と島 b_i の間を行き来する事ができます。
すぬけくんは今島 1 にいて、島 N に行きたいと思っています。 しかし、島 1 から島 N への定期便は存在しないことがわかりました。 なので、定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。
これを代わりに調べてあげてください。
制約
- 3 ≦ N ≦ 200,000
- 1 ≦ M ≦ 200,000
- 1 ≦ a_i < b_i ≦ N
- (a_i, b_i) \neq (1, N)
- i \neq j ならば (a_i, b_i) \neq (a_j, b_j)
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 a_2 b_2 : a_M b_M
出力
定期便を 2 つ使いたどり着けるならば POSSIBLE、たどり着けないならば IMPOSSIBLE と出力する。
入力例 1
3 2 1 2 2 3
出力例 1
POSSIBLE
入力例 2
4 3 1 2 2 3 3 4
出力例 2
IMPOSSIBLE
島 4 へ行くには、定期便を 3 つ使う必要があります。
入力例 3
100000 1 1 99999
出力例 3
IMPOSSIBLE
入力例 4
5 5 1 3 4 5 2 3 2 4 1 4
出力例 4
POSSIBLE
島 1、島 4、島 5 と移動すれば 2 つの定期便で移動可能です。
Score : 300 points
Problem Statement
In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands. For convenience, we will call them Island 1, Island 2, ..., Island N.
There are M kinds of regular boat services between these islands. Each service connects two islands. The i-th service connects Island a_i and Island b_i.
Cat Snuke is on Island 1 now, and wants to go to Island N. However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.
Help him.
Constraints
- 3 ≤ N ≤ 200 000
- 1 ≤ M ≤ 200 000
- 1 ≤ a_i < b_i ≤ N
- (a_i, b_i) \neq (1, N)
- If i \neq j, (a_i, b_i) \neq (a_j, b_j).
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 a_2 b_2 : a_M b_M
Output
If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
POSSIBLE
Sample Input 2
4 3 1 2 2 3 3 4
Sample Output 2
IMPOSSIBLE
You have to use three boat services to get to Island 4.
Sample Input 3
100000 1 1 99999
Sample Output 3
IMPOSSIBLE
Sample Input 4
5 5 1 3 4 5 2 3 2 4 1 4
Sample Output 4
POSSIBLE
You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
長さ N の非負整数列 a_i に対し、数列の最大値が N-1 以下になるまで以下の操作を繰り返し行うことを考えます。
- 数列のうち最も大きい要素を求める、複数ある場合はどれか 1 つ選ぶ。この要素の値を N 減らす。これ以外の要素の値を 1 増やす。
なお、この操作を行い続けると、いつかは数列の最大値が N-1 以下になることが証明できます。
ここで、整数 K が与えられるので、この操作を行う回数がちょうど K 回になるような数列 a_i を 1 つ求めてください。なお、この問題の入出力の制約下では、かならず 1 つは条件を満たすような数列が存在することが示せます。
制約
- 0 ≦ K ≦ 50 \times 10^{16}
入力
入力は以下の形式で標準入力から与えられる。
K
出力
以下の形式で数列を出力する。
N a_1 a_2 ... a_N
ここで、2 ≦ N ≦ 50, 0 ≦ a_i ≦ 10^{16} + 1000 でなければならない。
入力例 1
0
出力例 1
4 3 3 3 3
入力例 2
1
出力例 2
3 1 0 3
入力例 3
2
出力例 3
2 2 2
[2, 2] -> [0, 3] -> [1, 1] と、2 回操作を行います。
入力例 4
3
出力例 4
7 27 0 0 0 0 0 0
入力例 5
1234567894848
出力例 5
10 1000 193 256 777 0 1 1192 1234567891011 48 425
Score : 600 points
Problem Statement
We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N-1 or smaller.
- Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.
It can be proved that the largest element in the sequence becomes N-1 or smaller after a finite number of operations.
You are given an integer K. Find an integer sequence a_i such that the number of times we will perform the above operation is exactly K. It can be shown that there is always such a sequence under the constraints on input and output in this problem.
Constraints
- 0 ≤ K ≤ 50 \times 10^{16}
Input
Input is given from Standard Input in the following format:
K
Output
Print a solution in the following format:
N a_1 a_2 ... a_N
Here, 2 ≤ N ≤ 50 and 0 ≤ a_i ≤ 10^{16} + 1000 must hold.
Sample Input 1
0
Sample Output 1
4 3 3 3 3
Sample Input 2
1
Sample Output 2
3 1 0 3
Sample Input 3
2
Sample Output 3
2 2 2
The operation will be performed twice: [2, 2] -> [0, 3] -> [1, 1].
Sample Input 4
3
Sample Output 4
7 27 0 0 0 0 0 0
Sample Input 5
1234567894848
Sample Output 5
10 1000 193 256 777 0 1 1192 1234567891011 48 425
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
長さ N の非負整数列 a_i に対し、数列の最大値が N-1 以下になるまで以下の操作を繰り返し行うことを考えます。なお、この操作はD問題で考える操作と同一です。
- 数列のうち最も大きい要素を求める、複数ある場合はどれか 1 つ選ぶ。この要素の値を N 減らす。これ以外の要素の値を 1 増やす。
なお、この操作を行い続けると、いつかは数列の最大値が N-1 以下になることが証明できます。
ここで、数列 a_i が与えられるので、何回操作を行うことになるかを求めてください。
制約
- 2 ≦ N ≦ 50
- 0 ≦ a_i ≦ 10^{16} + 1000
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
何回操作を行うことになるかを出力する。
入力例 1
4 3 3 3 3
出力例 1
0
入力例 2
3 1 0 3
出力例 2
1
入力例 3
2 2 2
出力例 3
2
入力例 4
7 27 0 0 0 0 0 0
出力例 4
3
入力例 5
10 1000 193 256 777 0 1 1192 1234567891011 48 425
出力例 5
1234567894848
Score : 600 points
Problem Statement
We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N-1 or smaller. (The operation is the same as the one in Problem D.)
- Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.
It can be proved that the largest element in the sequence becomes N-1 or smaller after a finite number of operations.
You are given the sequence a_i. Find the number of times we will perform the above operation.
Constraints
- 2 ≤ N ≤ 50
- 0 ≤ a_i ≤ 10^{16} + 1000
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the number of times the operation will be performed.
Sample Input 1
4 3 3 3 3
Sample Output 1
0
Sample Input 2
3 1 0 3
Sample Output 2
1
Sample Input 3
2 2 2
Sample Output 3
2
Sample Input 4
7 27 0 0 0 0 0 0
Sample Output 4
3
Sample Input 5
10 1000 193 256 777 0 1 1192 1234567891011 48 425
Sample Output 5
1234567894848
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 800 点
問題文
N 頂点 N 辺の有向グラフを考えます。頂点には番号 1, 2, ..., N が振られているものとします。
このグラフは (p_1, 1), (p_2, 2), ..., (p_N, N) の N 本の辺からなり、弱連結です。 なお、この問題では頂点 u から頂点 v へ入り込む辺を (u, v) と表します。また、弱連結とは、辺を無向辺として見るとグラフ全体が連結になっているという意味です。
このグラフの頂点に、以下の条件を満たすように値を割り当てたいです。頂点 i に割り当てる値を a_i とします。
- a_i は、0 以上の非負整数である。
- すべての辺 (i, j) について、a_i \neq a_j である。
- すべての頂点 i と整数 x(0 ≦ x < a_i) について、辺 (i, j) が存在し、かつ x = a_j を満たすような頂点 j が存在する。
この条件をみたすような割り当て方が存在するか判定してください。
制約
- 2 ≦ N ≦ 200,000
- 1 ≦ p_i ≦ N
- p_i \neq i
- グラフは弱連結
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 ... p_N
出力
うまく値を割り当てられるならば POSSIBLE、割り当てられないならば IMPOSSIBLE を出力する。
入力例 1
4 2 3 4 1
出力例 1
POSSIBLE
{a_i} = {0, 1, 0, 1} か、{a_i} = {1, 0, 1, 0} と割り当てることができます。
入力例 2
3 2 3 1
出力例 2
IMPOSSIBLE
入力例 3
4 2 3 1 1
出力例 3
POSSIBLE
{a_i} = {2, 0, 1, 0} と割り当てることができます。
入力例 4
6 4 5 6 5 6 4
出力例 4
IMPOSSIBLE
Score : 800 points
Problem Statement
There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.
The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.
We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.
- Each a_i is a non-negative integer.
- For each edge (i, j), a_i \neq a_j holds.
- For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.
Determine whether there exists such an assignment.
Constraints
- 2 ≤ N ≤ 200 000
- 1 ≤ p_i ≤ N
- p_i \neq i
- The graph is weakly connected.
Input
Input is given from Standard Input in the following format:
N p_1 p_2 ... p_N
Output
If the assignment is possible, print POSSIBLE; otherwise, print IMPOSSIBLE.
Sample Input 1
4 2 3 4 1
Sample Output 1
POSSIBLE
The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.
Sample Input 2
3 2 3 1
Sample Output 2
IMPOSSIBLE
Sample Input 3
4 2 3 1 1
Sample Output 3
POSSIBLE
The assignment is possible: {a_i} = {2, 0, 1, 0}.
Sample Input 4
6 4 5 6 5 6 4
Sample Output 4
IMPOSSIBLE