A - Three Integers

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

黒板に 3 つの非負整数 A, B, C が書かれています． あなたは，以下の 2 つの操作を好きな順序で好きな回数繰り返すことができます．

  • 2 つの整数を選んで，それらから 1 を引く．
  • すべての整数から 1 を引く．

あなたの目標は，黒板に書かれている数をすべて 0 にすることです． 目標が達成可能であるかどうか判定し，また可能であるなら必要な最小の操作回数を求めてください．

制約

  • 0 \leq A, B, C \leq 10^{18}

入力

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

A B C

出力

目標が達成可能でない場合，-1 を出力せよ．可能である場合，必要な最小の操作回数を出力せよ．

入力例 1

2 2 3

出力例 1

3

例えば次のように操作を行うことで，すべての数を 0 にすることができます．

  • A と C から 1 を引く．黒板に書かれた数は 1, 2, 2 となる．
  • B と C から 1 を引く．黒板に書かれた数は 1, 1, 1 となる．
  • すべての数から 1 を引く．黒板に書かれた数は 0, 0, 0 となる．

入力例 2

0 0 1

出力例 2

-1

入力例 3

0 0 0

出力例 3

0

Score : 300 points

Problem Statement

Three non-negative integers A, B, and C are written on a blackboard. You can perform the following two operations any number of times in any order.

  • Subtract 1 from two of the written integers of your choice.
  • Subtract 1 from all of the written integers.

Your objective is to make all the numbers on the blackboard 0. Determine whether it is achievable. If it is, find the minimum number of times you need to perform an operation to achieve it.

Constraints

  • 0 \leq A, B, C \leq 10^{18}

Input

Input is given from Standard Input in the following format:

A B C

Output

If the objective is unachievable, print -1. If it is achievable, print the minimum number of times you need to perform an operation to achieve it.

Sample Input 1

2 2 3

Sample Output 1

3

Here is one way to make all the numbers 0.

  • Subtract 1 from A and C. Now the numbers are 1, 2, 2.
  • Subtract 1 from B and C. Now the numbers are 1, 1, 1.
  • Subtract 1 from all the numbers. Now the numbers are 0, 0, 0.

Sample Input 2

0 0 1

Sample Output 2

-1

Sample Input 3

0 0 0

Sample Output 3

0
B - Counting Grids

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N \times N のマス目の各マスに 1 から N^2 までの整数を 1 つずつ書き込む方法であって， どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を 998244353 で割ったあまりを求めてください．

  • そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する．
  • そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する．

制約

  • 1 \leq N \leq 500

入力

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

N

出力

答えを出力せよ．

入力例 1

2

出力例 1

8

例えば，以下のような書き込み方は条件を満たします．

13
42

この場合，左上のマスは左下のマスに書かれている数より小さい数が書かれているので， 1 つ目の条件を満たします．ただし，2 つ目の条件は満たしません．

入力例 2

5

出力例 2

704332752

入力例 3

100

出力例 3

927703658

Score : 500 points

Problem Statement

Find the number of ways, modulo 998244353, to fill the squares of an N \times N grid using each integer from 1 to N^2 once so that every square satisfies at least one of the following conditions.

  • In the same column, there is a square containing a number greater than that of the concerned square.
  • In the same row, there is a square containing a number less than that of the concerned square.

Constraints

  • 1 \leq N \leq 500

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

2

Sample Output 1

8

Here is one way to fill the grid to satisfy the requirement.

13
42

Here, the top-left square contains a number less than that of the bottom-left square, satisfying the first condition. It does not satisfy the second condition, however.

Sample Input 2

5

Sample Output 2

704332752

Sample Input 3

100

Sample Output 3

927703658
C - Piles of Pebbles

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

小石の山が N 個あります．最初，i 番目の山には A_i 個の小石があります．

これらを用いて，高橋君と青木君がゲームをします． 高橋君から始めて，交互に次の操作を行い，操作を行えなくなった方が負けとなります．

  • 山を 1 つ以上選び，選んだそれぞれの山から，高橋君の操作の場合は X 個ずつ，青木君の操作の場合は Y 個ずつ小石を取り除く． ただし，小石の個数が足りない山を選ぶことはできない．

二人が最適に行動したとき，どちらがゲームに勝つかを求めてください.

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X, Y \leq 10^9
  • 1 \leq A_i \leq 10^9

入力

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

N X Y
A_1 A_2 \cdots A_N

出力

このゲームに勝つのが高橋君の場合 First を，青木君の場合 Second を出力せよ．

入力例 1

2 1 1
3 3

出力例 1

First

例えば，以下のようなゲームの進行が考えられます．

  • 高橋君が両方の山から石を 1 つ取り除く．
  • 青木君が 1 番目の山から石を 1 つ取り除く．
  • 高橋君が 1 番目の山から石を 1 つ取り除く．
  • 青木君が 2 番目の山から石を 1 つ取り除く．
  • 高橋君が 2 番目の山から石を 1 つ取り除く．

青木君がどのように操作を行っても高橋君が勝つことができるので，答えは First です．

入力例 2

2 1 2
3 3

出力例 2

Second

Score : 600 points

Problem Statement

There are N piles of pebbles. Initially, the i-th pile has A_i pebbles.

Takahashi and Aoki will play a game using these piles. They will alternately perform the following operation, with Takahashi going first, and the one who becomes unable to do so loses the game.

  • Choose one or more piles, and remove the following number of pebbles from each chosen pile: X pebbles if this operation is performed by Takahashi, and Y pebbles if performed by Aoki. Here, a pile with an insufficient number of pebbles cannot be chosen.

Determine the winner of the game if both players play optimally.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X, Y \leq 10^9
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N X Y
A_1 A_2 \cdots A_N

Output

If it is Takahashi who will win the game, print First; if it is Aoki, print Second.

Sample Input 1

2 1 1
3 3

Sample Output 1

First

Here is one possible progression of the game.

  • Takahashi removes 1 pebble from both piles.
  • Aoki removes 1 pebble from the 1-st pile.
  • Takahashi removes 1 pebble from the 1-st pile.
  • Aoki removes 1 pebble from the 2-nd pile.
  • Takahashi removes 1 pebble from the 2-nd pile.

No matter how Aoki plays, Takahashi can always win, so the answer is First.

Sample Input 2

2 1 2
3 3

Sample Output 2

Second
D - Bridges

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

1 以上 N 以下の整数からなる 2 つの数列 A_1,\ldots, A_M および B_1,\ldots,B_M があります．

0 と 1 からなる長さ M の文字列に対して，2N 頂点 (M+N) 辺からなる次のような無向グラフを対応させます:

  • i 番目の文字が 0 のとき，i 番目の辺は頂点 A_i と頂点 (B_i+N) を結ぶ辺である．
  • i 番目の文字が 1 のとき，i 番目の辺は頂点 B_i と頂点 (A_i+N) を結ぶ辺である．
  • (j+M) 番目の辺は頂点 j と頂点 (j+N) を結ぶ辺である．

ただし，i, j はそれぞれ 1 \leq i \leq M, 1 \leq j \leq N を満たす整数を動くものとします． また，頂点には 1 から 2N までの番号がついています．

対応する無向グラフに含まれる橋の個数が最小となるような，0 と 1 からなる長さ M の文字列を 1 つ求めてください．

橋について グラフの辺であって，その辺を除くと連結成分の個数が増えるようなものを橋と呼びます．

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N

入力

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

N M
A_1 A_2 \cdots A_M
B_1 B_2 \cdots B_M

出力

条件を満たすような文字列を 1 つ出力せよ．答えが複数存在する場合，いずれを出力してもかまわない．

入力例 1

2 2
1 1
2 2

出力例 1

01

01 に対応するグラフには橋が存在しません．

00 に対応するグラフでは頂点 1 と頂点 3 を結ぶ辺と頂点 2 と頂点 4 を結ぶ辺が橋となるので， 00 は条件を満たしません．

入力例 2

6 7
1 1 2 3 4 4 5
2 3 3 4 5 6 6

出力例 2

0100010

Score : 700 points

Problem Statement

We have two sequences A_1,\ldots, A_M and B_1,\ldots,B_M consisting of intgers between 1 and N (inclusive).

For a string of length M consisting of 0 and 1, consider the following undirected graph with 2N vertices and (M+N) edges corresponding to that string.

  • If the i-th character of the string is 0, the i-th edge connects Vertex A_i and Vertex (B_i+N).
  • If the i-th character of the string is 1, the i-th edge connects Vertex B_i and Vertex (A_i+N).
  • The (j+M)-th edge connects Vertex j and Vertex (j+N).

Here, i and j are integers such that 1 \leq i \leq M and 1 \leq j \leq N, and the vertices are numbered 1 to 2N.

Find one string of length M consisting of 0 and 1 such that the corresponding undirected graph has the minimum number of bridges.

Notes on bridges A bridge is an edge of a graph whose removal increases the number of connected components.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \cdots A_M
B_1 B_2 \cdots B_M

Output

Print one string that satisfies the requirement. If there are multiple such strings, you may print any of them.

Sample Input 1

2 2
1 1
2 2

Sample Output 1

01

The graph corresponding to 01 has no bridges.

In the graph corresponding to 00, the edge connecting Vertex 1 and Vertex 3 and the edge connecting Vertex 2 and Vertex 4 are bridges, so 00 does not satisfy the requirement.

Sample Input 2

6 7
1 1 2 3 4 4 5
2 3 3 4 5 6 6

Sample Output 2

0100010
E - Reversi

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 頂点からなる木があります． 各頂点には 1 から N までの番号がついており， i 番目の辺は頂点 A_i と頂点 B_i を結んでいます． また，各頂点にはリバーシの石が 1 つずつ置かれています． 各頂点に置かれている石の状態は文字列 S によって与えられ， S の i 番目の文字が B のとき，頂点 i に置かれている石の表は黒色， S の i 番目の文字が W のとき，頂点 i に置かれている石の表は白色です．

以下の操作を N 回行い，すべての頂点から石を取り除くことが可能かどうか判定してください． また可能ならば，列 P_1,P_2,\ldots,P_N であって，頂点 P_1,P_2,\ldots,P_N をこの順に選ぶことが可能なもののうち，辞書順で最小のものを求めてください．

  • 表が白色の石が置かれている頂点を 1 つ選び，その頂点から石を取り除く． そして，その頂点と隣接する頂点に置かれている石をすべて裏返す．
リバーシの石について リバーシの石は一方の面が黒色，もう一方の面が白色になっており，裏返すと表の色が入れ替わります．
数列の辞書順とは？

相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します．

以下では S の i 番目の要素を S_i のように表します．また， S が T より辞書順で小さい場合は S \lt T ，大きい場合は S \gt T と表します．

  1. S と T のうち長さが短い方の文字列の長さを L とします．i=1,2,\dots,L に対して S_i と T_i が一致するか調べます．
  2. S_i \neq T_i である i が存在する場合，そのような i のうち最小のものを j とします．そして，S_j と T_j を比較して， S_j が T_j より（数として）小さい場合は S \lt T ，大きい場合は S \gt T と決定して，アルゴリズムを終了します．
  3. S_i \neq T_i である i が存在しない場合， S と T の長さを比較して，S が T より短い場合は S \lt T ，長い場合は S \gt T と決定して，アルゴリズムを終了します．

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは木である．
  • S は B と W の文字からなる長さ N の文字列である．

入力

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
S

出力

目標が達成可能でない場合，-1 を出力せよ．可能である場合，以下の形式で答えを出力せよ．

P_1 P_2 \cdots P_N

入力例 1

4
1 2
2 3
3 4
WBWW

出力例 1

1 2 4 3

入力例 2

4
1 2
2 3
3 4
BBBB

出力例 2

-1

この場合，一度も操作を行うことができません．

Score : 700 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex A_i and Vertex B_i. Additionally, each vertex has a reversi piece on it. The status of the piece on each vertex is given by a string S: if the i-th character of S is B, the piece on Vertex i is placed with the black side up; if the i-th character of S is W, the piece on Vertex i is placed with the white side up.

Determine whether it is possible to perform the operation below N times to remove the pieces from all vertices. If it is possible, find the lexicographically smallest possible sequence P_1, P_2, \ldots, P_N such that Vertices P_1, P_2, \ldots, P_N can be chosen in this order during the process.

  • Choose a vertex containing a piece with the white side up, and remove the piece from that vertex. Then, flip all pieces on the vertices adjacent to that vertex.
Notes on reversi pieces A reversi piece has a black side and a white side, and flipping it changes which side faces up.
What is the lexicographical order on sequences?

The following is an algorithm to determine the lexicographical order between different sequences S and T.

Below, let S_i denote the i-th element of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

  1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j is less than T_j (as a number), we determine that S \lt T and quit; if S_j is greater than T_j, we determine that S \gt T and quit.
  3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is a tree.
  • S is a string of length N consisting of the characters B and W.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
S

Output

If the objective is unachievable, print -1. If it is achievable, print the answer in the following format:

P_1 P_2 \cdots P_N

Sample Input 1

4
1 2
2 3
3 4
WBWW

Sample Output 1

1 2 4 3

Sample Input 2

4
1 2
2 3
3 4
BBBB

Sample Output 2

-1

In this case, you cannot perform the operation at all.
F - Counting Subsets

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

正の整数 N が与えられるので，次の条件を満たす\{1,2,\ldots,N\} の部分集合 S の個数を 998244353 で割ったあまりを求めてください．

  • N 以下の正の整数はすべて S のいくつかの相異なる要素の和として表せる．さらに，そのような表し方は高々 2 通りである．

制約

  • 1 \leq N \leq 1500

入力

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

N

出力

答えを出力せよ．

入力例 1

3

出力例 1

2

\{1,2\} と \{1,2,3\} が条件を満たす部分集合です．

入力例 2

5

出力例 2

5

入力例 3

1000

出力例 3

742952024

Score : 1200 points

Problem Statement

Given a positive integer N, find the number, modulo 998244353, of subsets S of \{1, 2, \ldots, N\} that satisfy the following condition.

  • Every positive integer at most N can be represented as the sum of some distinct elements of S, and there are at most two such representations.

Constraints

  • 1 \leq N \leq 1500

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

3

Sample Output 1

2

The subsets \{1,2\} and \{1,2,3\} satisfy the condition.

Sample Input 2

5

Sample Output 2

5

Sample Input 3

1000

Sample Output 3

742952024