Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
すぬけ君は空の数列 a を持っています。
すぬけ君は a に対して N 回操作を行います。
i 回目の操作では 1 \leq j \leq i を満たす整数 j を選び、a の先頭から j 番目に j を挿入することができます。
長さ N の数列 b が与えられます。N 回の操作後に a が b と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 100
- 1 \leq b_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N b_1 \dots b_N
出力
N 回の操作後に a と b が一致するような操作手順が存在しないならば -1 を出力せよ。
存在するならば操作手順を N 行に出力せよ。i 行目では i 回目の操作で選んだ整数を出力せよ。考えられる操作手順が複数存在する場合は、そのうちのどれを出力してもよい。
入力例 1
3 1 2 1
出力例 1
1 1 2
- 各操作後、a は以下のように変化します。
- 1 回目の操作後:(1)
- 2 回目の操作後:(1,1)
- 3 回目の操作後:(1,2,1)
入力例 2
2 2 2
出力例 2
-1
- 数列の先頭に 2 を挿入することはできないため、達成不可能です。
入力例 3
9 1 1 1 2 2 1 2 3 2
出力例 3
1 2 2 3 1 2 2 1 1
Score : 400 points
Problem Statement
Snuke has an empty sequence a.
He will perform N operations on this sequence.
In the i-th operation, he chooses an integer j satisfying 1 \leq j \leq i, and insert j at position j in a (the beginning is position 1).
You are given a sequence b of length N. Determine if it is possible that a is equal to b after N operations. If it is, show one possible sequence of operations that achieves it.
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- 1 \leq b_i \leq N
Input
Input is given from Standard Input in the following format:
N b_1 \dots b_N
Output
If there is no sequence of N operations after which a would be equal to b, print -1.
If there is, print N lines. In the i-th line, the integer chosen in the i-th operation should be printed. If there are multiple solutions, any of them is accepted.
Sample Input 1
3 1 2 1
Sample Output 1
1 1 2
In this sequence of operations, the sequence a changes as follows:
- After the first operation: (1)
- After the second operation: (1,1)
- After the third operation: (1,2,1)
Sample Input 2
2 2 2
Sample Output 2
-1
2 cannot be inserted at the beginning of the sequence, so this is impossible.
Sample Input 3
9 1 1 1 2 2 1 2 3 2
Sample Output 3
1 2 2 3 1 2 2 1 1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 N が与えられます。 頂点に 1 から N の番号がついた N 頂点の無向グラフであって、以下の 2 つの条件を満たすものを 1 つ構成してください。
- 単純かつ連結
- ある整数 S が存在して、任意の頂点についてその頂点に隣接する頂点の番号の値の和は S となる
この問題の制約下でそのようなグラフが少なくとも 1 つ存在することが証明できます。
制約
- 入力は全て整数である。
- 3 \leq N \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N
出力
1 行目に構成したグラフの辺の本数 M を出力せよ。続く M 行のうち i 行目には、2 つの整数 a_i と b_i を出力せよ。これらは i 番目の辺の端点を表す。
構成されたグラフが条件を満たすならば正解となる。
入力例 1
3
出力例 1
2 1 3 2 3
- どの頂点も、隣接する頂点の番号の和が 3 となっています。
Score : 700 points
Problem Statement
You are given an integer N. Build an undirected graph with N vertices with indices 1 to N that satisfies the following two conditions:
- The graph is simple and connected.
- There exists an integer S such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is S.
It can be proved that at least one such graph exists under the constraints of this problem.
Constraints
- All values in input are integers.
- 3 \leq N \leq 100
Input
Input is given from Standard Input in the following format:
N
Output
In the first line, print the number of edges, M, in the graph you made. In the i-th of the following M lines, print two integers a_i and b_i, representing the endpoints of the i-th edge.
The output will be judged correct if the graph satisfies the conditions.
Sample Input 1
3
Sample Output 1
2 1 3 2 3
- For every vertex, the sum of the indices of the vertices adjacent to that vertex is 3.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 頂点 M 本の辺からなる単純かつ連結な無向グラフが与えられます。 頂点には 1 から N の番号が、辺には 1 から M の番号がついています。
辺 i は頂点 a_i と b_i を双方向につなぐ辺です。
全ての辺をちょうど 1 回ずつ使って 3 つのサーキットを作ることが可能かどうかを判定してください。
注釈
サーキットとは辺素だが頂点素とは限らない閉路のことをいう。
制約
- 入力はすべて整数である。
- 1 \leq N,M \leq 10^{5}
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは単純かつ連結。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 : a_M b_M
出力
全ての辺をちょうど 1 回ずつ使って 3 つのサーキットを作ることが可能ならば Yes を、不可能ならば No を出力せよ。
入力例 1
7 9 1 2 1 3 2 3 1 4 1 5 4 5 1 6 1 7 6 7
出力例 1
Yes
- 以下の図のように、全ての辺をちょうど 1 回ずつ使って 3 つのサーキットを作ることができます。
入力例 2
3 3 1 2 2 3 3 1
出力例 2
No
- 3 つのサーキットを作る必要があります。
入力例 3
18 27 17 7 12 15 18 17 13 18 13 6 5 7 7 1 14 5 15 11 7 6 1 9 5 4 18 16 4 6 7 2 7 11 6 3 12 14 5 2 10 5 7 8 10 15 3 15 9 8 7 15 5 16 18 15
出力例 3
Yes
Score : 800 points
Problem Statement
You are given a simple connected undirected graph consisting of N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M.
Edge i connects Vertex a_i and b_i bidirectionally.
Determine if three circuits (see Notes) can be formed using each of the edges exactly once.
Notes
A circuit is a cycle allowing repetitions of vertices but not edges.
Constraints
- All values in input are integers.
- 1 \leq N,M \leq 10^{5}
- 1 \leq a_i, b_i \leq N
- The given graph is simple and connected.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 : a_M b_M
Output
If three circuits can be formed using each of the edges exactly once, print Yes; if they cannot, print No.
Sample Input 1
7 9 1 2 1 3 2 3 1 4 1 5 4 5 1 6 1 7 6 7
Sample Output 1
Yes
- Three circuits can be formed using each of the edges exactly once, as follows:
Sample Input 2
3 3 1 2 2 3 3 1
Sample Output 2
No
- Three circuits are needed.
Sample Input 3
18 27 17 7 12 15 18 17 13 18 13 6 5 7 7 1 14 5 15 11 7 6 1 9 5 4 18 16 4 6 7 2 7 11 6 3 12 14 5 2 10 5 7 8 10 15 3 15 9 8 7 15 5 16 18 15
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
\{ 1, \ldots, N \} の順列 p = (p_1, \ldots, p_N) が与えられます。 あなたは、次の 2 種類の操作を好きな順序で繰り返し行うことができます。
- コスト A を支払う。 整数 l と r (1 \leq l < r \leq N) を自由に選び、(p_l, \ldots, p_r) を左にひとつシフトする。 すなわち、p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r をそれぞれ p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l へ置き換える。
- コスト B を支払う。 整数 l と r (1 \leq l < r \leq N) を自由に選び、(p_l, \ldots, p_r) を右にひとつシフトする。 すなわち、p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r をそれぞれ p_r, p_l, \ldots, p_{r - 2}, p_{r - 1} へ置き換える。
p を昇順にソートするために必要な総コストの最小値を求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 5000
- 1 \leq A, B \leq 10^9
- (p_1 \ldots, p_N) は \{ 1, \ldots, N \} の順列である。
入力
入力は以下の形式で標準入力から与えられる。
N A B p_1 \cdots p_N
出力
p を昇順にソートするために必要な総コストの最小値を出力せよ。
入力例 1
3 20 30 3 1 2
出力例 1
20
(p_1, p_2, p_3) を左にひとつシフトすると、p = (1, 2, 3) となります。
入力例 2
4 20 30 4 2 3 1
出力例 2
50
例えば、次のように操作を行えばよいです。
- (p_1, p_2, p_3, p_4) を左にひとつシフトする。 すると、p = (2, 3, 1, 4) となる。
- (p_1, p_2, p_3) を右にひとつシフトする。 すると、p = (1, 2, 3, 4) となる。
このとき、総コストは 20 + 30 = 50 です。
入力例 3
1 10 10 1
出力例 3
0
入力例 4
4 1000000000 1000000000 4 3 2 1
出力例 4
3000000000
入力例 5
9 40 50 5 3 4 7 6 1 2 9 8
出力例 5
220
Score : 1000 points
Problem Statement
You are given a permutation p = (p_1, \ldots, p_N) of \{ 1, \ldots, N \}. You can perform the following two kinds of operations repeatedly in any order:
- Pay a cost A. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the left by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l, respectively.
- Pay a cost B. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the right by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}, respectively.
Find the minimum total cost required to sort p in ascending order.
Constraints
- All values in input are integers.
- 1 \leq N \leq 5000
- 1 \leq A, B \leq 10^9
- (p_1 \ldots, p_N) is a permutation of \{ 1, \ldots, N \}.
Input
Input is given from Standard Input in the following format:
N A B p_1 \cdots p_N
Output
Print the minimum total cost required to sort p in ascending order.
Sample Input 1
3 20 30 3 1 2
Sample Output 1
20
Shifting (p_1, p_2, p_3) to the left by one results in p = (1, 2, 3).
Sample Input 2
4 20 30 4 2 3 1
Sample Output 2
50
One possible sequence of operations is as follows:
- Shift (p_1, p_2, p_3, p_4) to the left by one. Now we have p = (2, 3, 1, 4).
- Shift (p_1, p_2, p_3) to the right by one. Now we have p = (1, 2, 3, 4).
Here, the total cost is 20 + 30 = 50.
Sample Input 3
1 10 10 1
Sample Output 3
0
Sample Input 4
4 1000000000 1000000000 4 3 2 1
Sample Output 4
3000000000
Sample Input 5
9 40 50 5 3 4 7 6 1 2 9 8
Sample Output 5
220
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
M を正整数とします。
2 N 個の整数 a_1, a_2, \ldots, a_{2 N} が与えられます。 ここで、各 i について 0 \leq a_i < M です。
2 N 個の整数を N 組のペアに分けることを考えます。 このとき、各整数はちょうど 1 つのペアに属さなければなりません。
ペア (x, y) の 醜さ を (x + y) \mod M と定義します。 N 組のペアの醜さの最大値を Z としたとき、Z の最小値を求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^9
- 0 \leq a_i < M
入力
入力は以下の形式で標準入力から与えられる。
N M
a_1 a_2 \cdots a_{2N}
出力
N 組のペアの醜さの最大値を Z としたとき、Z の最小値を出力せよ。
入力例 1
3 10 0 2 3 4 5 9
出力例 1
5
例えば、(0, 5), (2, 3), (4, 9) とペアを作ればよいです。 このとき、ペアの醜さはそれぞれ 5, 5, 3 となります。
入力例 2
2 10 1 9 1 9
出力例 2
0
(1, 9), (1, 9) とペアを作ればよいです。 このとき、ペアの醜さはともに 0 です。
Score : 1200 points
Problem Statement
Let M be a positive integer.
You are given 2 N integers a_1, a_2, \ldots, a_{2 N}, where 0 \leq a_i < M for each i.
Consider dividing the 2 N integers into N pairs. Here, each integer must belong to exactly one pair.
We define the ugliness of a pair (x, y) as (x + y) \mod M. Let Z be the largest ugliness of the N pairs. Find the minimum possible value of Z.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^9
- 0 \leq a_i < M
Input
Input is given from Standard Input in the following format:
N M
a_1 a_2 \cdots a_{2N}
Output
Print the minimum possible value of Z, where Z is the largest ugliness of the N pairs.
Sample Input 1
3 10 0 2 3 4 5 9
Sample Output 1
5
One solution is to form pairs (0, 5), (2, 3) and (4, 9), with ugliness 5, 5 and 3, respectively.
Sample Input 2
2 10 1 9 1 9
Sample Output 2
0
Pairs (1, 9) and (1, 9) should be formed, with ugliness both 0.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1800 点
問題文
円形のピザがあります。 すぬけ君は、なるべくこのピザの 1/3 に近い分量食べたいです。
すぬけ君は、以下のようにピザを切って食べることにしました。
まず、すぬけ君はピザに N 回ナイフを入れて N 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。
次に、すぬけ君は一個以上のいくつかの 連続する ピースをなるべく合計量が 1/3 に近くなるように選んで食べます。 (合計量を x とすると、 |x - 1/3| が最小となるように連続するピースを選びます。)
このとき、 |x - 1/3| の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod 10^9 + 7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。ここで、x, y は整数であり、x は 10^9 + 7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、xz \equiv y \pmod{10^9 + 7} を満たすような 0 以上 10^9 + 6 以下の唯一の整数 z を出力してください。
制約
- 2 \leq N \leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
N
出力
|x - 1/3| の期待値を注記で述べるように mod 10^9 + 7 で出力せよ。
入力例 1
2
出力例 1
138888890
期待値は \frac{5}{36} です。
入力例 2
3
出力例 2
179012347
期待値は \frac{11}{162} です。
入力例 3
10
出力例 3
954859137
入力例 4
1000000
出力例 4
44679646
Score : 1800 points
Problem Statement
We have a round pizza. Snuke wants to eat one third of it, or something as close as possible to that.
He decides to cut this pizza as follows.
First, he divides the pizza into N pieces by making N cuts with a knife. The knife can make a cut along the segment connecting the center of the pizza and some point on the circumference of the pizza. However, he is very poor at handling knives, so the cuts are made at uniformly random angles, independent from each other.
Then, he chooses one or more consecutive pieces so that the total is as close as possible to one third of the pizza, and eat them. (Let the total be x of the pizza. He chooses consecutive pieces so that |x - 1/3| is minimized.)
Find the expected value of |x - 1/3|. It can be shown that this value is rational, and we ask you to print it modulo 10^9 + 7, as described in Notes.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- 2 \leq N \leq 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the expected value of |x - 1/3| modulo 10^9 + 7, as described in Notes.
Sample Input 1
2
Sample Output 1
138888890
The expected value is \frac{5}{36}.
Sample Input 2
3
Sample Output 2
179012347
The expected value is \frac{11}{162}.
Sample Input 3
10
Sample Output 3
954859137
Sample Input 4
1000000
Sample Output 4
44679646