C - 2D Plane 2N Points

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

二次元平面に，赤い点と青い点が N 個ずつあります。 i 個目の赤い点の座標は (a_i, b_i) で，i 個目の青い点の座標は (c_i, d_i) です。

赤い点と青い点は，赤い点の x 座標が青い点の x 座標より小さく， また赤い点の y 座標も青い点の y 座標より小さいとき，仲良しペアになれます。

あなたは最大で何個の仲良しペアを作ることができますか？ ただし，1 つの点が複数のペアに所属することはできません。

制約

  • 入力は全て整数
  • 1 \leq N \leq 100
  • 0 \leq a_i, b_i, c_i, d_i < 2N
  • a_1, a_2, ..., a_N, c_1, c_2, ..., c_N はすべて異なる
  • b_1, b_2, ..., b_N, d_1, d_2, ..., d_N はすべて異なる

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

出力

仲良しペアの個数の最大値を出力せよ。

入力例 1

3
2 0
3 1
1 3
4 2
0 4
5 5

出力例 1

2

例えば， (2, 0) と (4, 2) をペアにし， (3, 1) と (5, 5) をペアにすればよいです。

入力例 2

3
0 0
1 1
5 2
2 3
3 4
4 5

出力例 2

2

例えば， (0, 0) と (2, 3) をペアにし， (1, 1) と (3, 4) をペアにすればよいです。

入力例 3

2
2 2
3 3
0 0
1 1

出力例 3

0

一つもペアが作れない場合もあります。

入力例 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

出力例 4

5

入力例 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

出力例 5

4

Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points. The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 100
  • 0 \leq a_i, b_i, c_i, d_i < 2N
  • a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.
  • b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4
D - Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

2 つの長さ N の非負整数列 a_1, ..., a_N, b_1, ..., b_N が与えられます。

1 \leq i, j \leq N となるように整数 i, j を選ぶ方法は N^2 通りありますが，この N^2 通りの i, j それぞれについて，a_i + b_j を計算し，紙に書き出します。 つまり，紙に N^2 個の整数を書きます。

この N^2 個の整数のxorを計算してください。

xorの説明

整数 c_1, c_2, ..., c_m のxor X は，以下のように定義されます。

  • X を 2 進数表記したときの 2^k(0 \leq k, k は整数)の位の値は，c_1, c_2, ...c_m のうち，2 進数表記したときの 2^k の位の値が 1 となるものの個数が奇数個ならば 1，偶数個ならば 0 となります

例えば，3 と 5 のxorの値は，3 の 2 進数表記が 011，5 の 2 進数表記が 101 のため，2 進数表記が 110 の 6 となります。

制約

  • 入力は全て整数
  • 1 \leq N \leq 200,000
  • 0 \leq a_i, b_i < 2^{28}

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

出力

求めた結果を出力せよ。

入力例 1

2
1 2
3 4

出力例 1

2

紙には 4(1+3), 5(1+4), 5(2+3), 6(2+4) の 2^2 = 4 つの数が書かれます。

入力例 2

6
4 6 0 0 3 3
0 5 6 5 0 3

出力例 2

8

入力例 3

5
1 2 3 4 5
1 2 3 4 5

出力例 3

2

入力例 4

1
0
0

出力例 4

0

Score : 500 points

Problem Statement

You are given two integer sequences, each of length N: a_1, ..., a_N and b_1, ..., b_N.

There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N. For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper. That is, we will write N^2 integers in total.

Compute the XOR of these N^2 integers.

Definition of XOR

The XOR of integers c_1, c_2, ..., c_m is defined as follows:

  • Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.

For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 200,000
  • 0 \leq a_i, b_i < 2^{28}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

Output

Print the result of the computation.

Sample Input 1

2
1 2
3 4

Sample Output 1

2

On the sheet, the following four integers will be written: 4(1+3), 5(1+4), 5(2+3) and 6(2+4).

Sample Input 2

6
4 6 0 0 3 3
0 5 6 5 0 3

Sample Output 2

8

Sample Input 3

5
1 2 3 4 5
1 2 3 4 5

Sample Output 3

2

Sample Input 4

1
0
0

Sample Output 4

0
E - Both Sides Merger

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

あなたは，長さ N の数列 a_1, a_2, ..., a_N を持っています。

あなたは，この数列の長さが 1 になるまで，繰り返し以下の操作を行います。

  • まず，数列の要素を 1 つ選ぶ。
  • もしその要素が数列の端だった場合，その要素を削除する。
  • もしその要素が数列の端でない場合，その要素を，選んだ要素の両隣の要素の和に書き換える。そしてその後，両隣の要素を削除する。

あなたは，最終的な数列の要素の値を最大化したいです。

最終的な数列の要素の値の最大値と，それを達成する手順を求めてください。

制約

  • 入力は全て整数
  • 2 \leq N \leq 1000
  • |a_i| \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

出力

  • 1 行目には，最終的な数列の要素の値の最大値を出力せよ。
  • 2 行目には，操作の回数を出力せよ。
  • 2+i 行目には，i 回目の操作で選ぶ要素が，その時点の数列で左から何番目かを出力せよ。
  • 最大値を達成する手順が複数存在する場合，そのうちどれを出力しても良い。

入力例 1

5
1 4 3 7 5

出力例 1

11
3
1
4
2

数列は以下のように変化します。

  • 1 回目の操作後の数列 : 4, 3, 7, 5
  • 2 回目の操作後の数列 : 4, 3, 7
  • 3 回目の操作後の数列 : 11(4+7)

入力例 2

4
100 100 -1 100

出力例 2

200
2
3
1
  • 1 回目の操作後の数列 : 100, 200(100+100)
  • 2 回目の操作後の数列 : 200

入力例 3

6
-1 -2 -3 1 2 3

出力例 3

4
3
2
1
2
  • 1 回目の操作後の数列 : -4, 1, 2, 3
  • 2 回目の操作後の数列 : 1, 2, 3
  • 3 回目の操作後の数列 : 4

入力例 4

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 4

5000000000
4
2
2
2
2

Score : 700 points

Problem Statement

You have an integer sequence of length N: a_1, a_2, ..., a_N.

You repeatedly perform the following operation until the length of the sequence becomes 1:

  • First, choose an element of the sequence.
  • If that element is at either end of the sequence, delete the element.
  • If that element is not at either end of the sequence, replace the element with the sum of the two elements that are adjacent to it. Then, delete those two elements.

You would like to maximize the final element that remains in the sequence.

Find the maximum possible value of the final element, and the way to achieve it.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 1000
  • |a_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

  • In the first line, print the maximum possible value of the final element in the sequence.
  • In the second line, print the number of operations that you perform.
  • In the (2+i)-th line, if the element chosen in the i-th operation is the x-th element from the left in the sequence at that moment, print x.
  • If there are multiple ways to achieve the maximum value of the final element, any of them may be printed.

Sample Input 1

5
1 4 3 7 5

Sample Output 1

11
3
1
4
2

The sequence would change as follows:

  • After the first operation: 4, 3, 7, 5
  • After the second operation: 4, 3, 7
  • After the third operation: 11(4+7)

Sample Input 2

4
100 100 -1 100

Sample Output 2

200
2
3
1
  • After the first operation: 100, 200(100+100)
  • After the second operation: 200

Sample Input 3

6
-1 -2 -3 1 2 3

Sample Output 3

4
3
2
1
2
  • After the first operation: -4, 1, 2, 3
  • After the second operation: 1, 2, 3
  • After the third operation: 4

Sample Input 4

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

5000000000
4
2
2
2
2
F - Two Faced Edges

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 1100 点

問題文

N 頂点 M 辺の単純な有向グラフが与えられます。 頂点には 1, 2, ..., N の番号が，辺には 1, 2, ..., M の番号が付いています。 辺 i は頂点 a_i から頂点 b_i へ伸びています。

それぞれの辺について，もしその辺を反転させたらグラフの強連結成分の個数が変わるかどうかを求めてください。

なお，辺 i を反転させるとは，グラフから辺 i を削除し， 新たに頂点 b_i から頂点 a_i へ伸びる辺を追加する操作を意味します。

制約

  • 2 \leq N \leq 1000
  • 1 \leq M \leq 200,000
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • i \neq j ならば a_i \neq a_j または b_i \neq b_j

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1
a_2 b_2
:
a_M b_M

出力

M 行出力せよ。i 行目には，辺 i を反転させたらグラフの強連結成分の個数が変わる場合 diff，変わらない場合 same と出力せよ。

入力例 1

3 3
1 2
1 3
2 3

出力例 1

same
diff
same

辺を反転させない場合強連結成分の個数は 3 個ですが，辺 2 を反転させると強連結成分の個数は 1 個になります。

入力例 2

2 2
1 2
2 1

出力例 2

diff
diff

辺を反転させた結果，グラフに多重辺が生じる場合もあります。

入力例 3

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

出力例 3

same
same
same
same
same
diff
diff
diff
diff

Score : 1100 points

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1, 2, ..., N, and the edges are numbered 1, 2, ..., M. Edge i points from Vertex a_i to Vertex b_i.

For each edge, determine whether the reversion of that edge would change the number of the strongly connected components in the graph.

Here, the reversion of Edge i means deleting Edge i and then adding a new edge that points from Vertex b_i to Vertex a_i.

Constraints

  • 2 \leq N \leq 1000
  • 1 \leq M \leq 200,000
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • If i \neq j, then a_i \neq a_j or b_i \neq 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

Print M lines. In the i-th line, if the reversion of Edge i would change the number of the strongly connected components in the graph, print diff; if it would not, print same.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

same
diff
same

The number of the strongly connected components is 3 without reversion of edges, but it will become 1 if Edge 2 is reversed.

Sample Input 2

2 2
1 2
2 1

Sample Output 2

diff
diff

Reversion of an edge may result in multiple edges in the graph.

Sample Input 3

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

Sample Output 3

same
same
same
same
same
diff
diff
diff
diff