第二回 AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1))

A - Affinity for Artifacts

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

魔法使いのすぬけ君は 1 から N の番号がついた N 個の魔法のランプを持っています。 i 番目のランプのコストは a_i です。はじめ、どのランプも灯っていません。

すぬけ君はMPという整数値を持っており、はじめは X です。すぬけ君がコスト x のランプを灯すとMPが x だけ減少します。すぬけ君が 1 つランプを灯すごとに、コストが 1 以上であるすべてのランプについてコストが 1 小さくなります。

ランプを灯す順序は N! 通りありますが、このうちMPが 0 未満になることがないような場合の数を 998244353 で割ったあまりを求めてください。

制約

1 \le N \le 100
0 \le a_i \le 10^{9}
0 \le X \le 10^9
入力される値は全て整数

入力

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

N X
a_1 a_2 \dots a_N

出力

答えを出力してください。

入力例 1

3 1
0 1 2

出力例 1

MPが 0 未満になることがない順序の一例を説明します。

はじめに 1 番のランプを灯します。MPが 0 だけ減少します。
次に 3 番のランプを灯します。MPが 1 だけ減少します。
最後に 2 番のランプを灯します。MPが 0 だけ減少します。

ランプのコストが 0 未満にならないことに注意してください。

入力例 2

6 8
2 1 4 8 1 4

出力例 2

入力例 3

20 50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

出力例 3

63942667

998244353 で割ったあまりを求めることを忘れずに。

Score : 800 points

Problem Statement

Snuke the wizard has N magical lamps numbered 1 to N. The cost of the i-th lamp is a_i. Initially, none of the lamps are lit.

Snuke has an integer value called MP, which is initially X. When Snuke lights a lamp with cost x, his MP decreases by x. Each time Snuke lights one lamp, the cost of all lamps with cost at least 1 decreases by 1.

There are N! possible orders to light the lamps. Find the number, modulo 998244353, of such orders where MP never becomes negative.

Constraints

1 \le N \le 100
0 \le a_i \le 10^{9}
0 \le X \le 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
a_1 a_2 \dots a_N

Output

Print the answer.

Sample Input 1

3 1
0 1 2

Sample Output 1

We explain one order where MP never becomes negative.

First, light lamp 1. MP decreases by 0.
Next, light lamp 3. MP decreases by 1.
Finally, light lamp 2. MP decreases by 0.

Note that the cost of a lamp never becomes negative.

Sample Input 2

6 8
2 1 4 8 1 4

Sample Output 2

Sample Input 3

20 50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Sample Output 3

63942667

Do not forget to find the remainder modulo 998244353.

B - Balanced Neighbors 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

整数 N が与えられます。頂点に 1 から N の番号がついた N 頂点の単純連結無向グラフであって、以下の条件を満たすものが存在するかどうかを判定し、存在するならばその例を 1 つ示してください。

ある整数 X が存在して、任意の頂点 v について、v から 1 回または 2 回辺を辿ることで到達できる v 以外の頂点の番号の総和は X となる

制約

2 \le N \le 200
入力される値は全て整数

入力

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

出力

問題文中の条件を満たす N 頂点の単純連結無向グラフが存在しない場合 -1 を出力せよ。存在する場合、1 行目に辺の本数 M を出力せよ。続く M 行のうち i 行目には 2 つの整数を出力せよ。これらは i 番目の辺の端点の頂点番号を表す。

構成されたグラフが条件を満たすならば正解となる。

入力例 1

出力例 1

入力例 2

出力例 2

-1

条件を満たすグラフが存在しない場合 -1 を出力してください。

Score : 800 points

Problem Statement

You are given an integer N. Determine whether there exists a simple connected undirected graph with N vertices numbered 1 to N that satisfies the following condition, and if it exists, show one such graph.

There exists an integer X such that for any vertex v, the sum of the numbers of all vertices other than v that can be reached from v by traversing an edge once or twice is X.

Constraints

2 \le N \le 200
All input values are integers.

Input

The input is given from Standard Input in the following format:

Output

If there does not exist a simple connected undirected graph with N vertices satisfying the condition in the problem statement, print -1. If it exists, print the number of edges M on the first line. On the i-th of the following M lines, print two integers. These represent the vertex numbers of the endpoints of the i-th edge.

Any constructed graph that satisfies the condition will be accepted.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

If there does not exist a graph satisfying the condition, print -1.

C - Combine to Make Non-decreasing

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

長さ N の整数列 A=(A_1, A_2, \cdots, A_N) が与えられます。すぬけ君は A が広義単調増加列になるようにしたいです。

すぬけ君は 0 回以上以下の操作を行うことができます。

A の隣接する 2 つの要素を選ぶ
この 2 つの要素を取り除き、代わりにこの 2 つのビット単位 \mathrm{OR} を取った値を元の位置に挿入する

A が広義単調増加列となったときの長さとしてありうる値の最大値を求めてください。

ビット単位 \mathrm{OR} 演算とは

非負整数 A, B のビット単位 \mathrm{OR}、A\ \mathrm{OR}\ B は以下のように定義されます。

A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。

例えば、3\ \mathrm{OR}\ 5 = 7 となります (二進表記すると: 011\ \mathrm{OR}\ 101 = 111)。

広義単調増加列とは

数列 a=(a_1,a_2, \cdots, a_n) が a_1 \le a_2 \le \ldots \le a_n を満たすとき、またそのときに限り、a は広義単調増加列であるといいます。

制約

1 \le N \le 2 \times 10^5
1 \le A_i <2^{30}
入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 1 2

出力例 1

1 回目の操作で 1 番目と 2 番目の要素を選んだ場合 A=(3,2) となり A は広義単調増加列ではありません。
1 回目の操作で 2 番目と 3 番目の要素を選んだ場合 A=(3,3) となり A は広義単調増加列となります。

入力例 2

4
4 1 2 3

出力例 2

入力例 3

20
105327673 847116534 928167271 478716741 244808645 744985167 772409400 950055714 32441819 24475691 74630537 632066724 170250355 937572655 791196964 469960355 264764288 1061830134 183233398 643628719

出力例 3

Score : 800 points

Problem Statement

You are given an integer sequence of length N, A=(A_1, A_2, \cdots, A_N). Snuke wants to make A a non-decreasing sequence.

He can perform the following operation zero or more times.

Choose two adjacent elements of A
Remove these two elements and insert the bitwise \mathrm{OR} of these two values at the original position

Find the maximum possible value of the length of A when A becomes a non-decreasing sequence.

What is bitwise \mathrm{OR}?

The bitwise \mathrm{OR} of non-negative integers A and B, A\ \mathrm{OR}\ B, is defined as follows.

When A\ \mathrm{OR}\ B is written in binary, the digit in the 2^k place (k \geq 0) is 1 if at least one of the digits in the 2^k place of A and B written in binary is 1, and 0 otherwise.

For example, 3\ \mathrm{OR}\ 5 = 7 (in binary: 011\ \mathrm{OR}\ 101 = 111).

What is a non-decreasing sequence?

A sequence a=(a_1,a_2, \cdots, a_n) is a non-decreasing sequence if and only if a_1 \le a_2 \le \ldots \le a_n holds.

Constraints

1 \le N \le 2 \times 10^5
1 \le A_i <2^{30}
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 1 2

Sample Output 1

If the 1-st and 2-nd elements are chosen in the first operation, A=(3,2) and A is not a non-decreasing sequence.
If the 2-nd and 3-rd elements are chosen in the first operation, A=(3,3) and A is a non-decreasing sequence.

Sample Input 2

4
4 1 2 3

Sample Output 2

Sample Input 3

20
105327673 847116534 928167271 478716741 244808645 744985167 772409400 950055714 32441819 24475691 74630537 632066724 170250355 937572655 791196964 469960355 264764288 1061830134 183233398 643628719

Sample Output 3

D - Devourers and Cake

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

先手太郎君と後手次郎君はお母さんへのプレゼントに長方形のケーキを買ってきました。先手太郎君と後手次郎君はおなかが空いたので、お母さん用の 1 ピースを残して全て食べてしまうことにしました。

N 行 M 列に並ぶピースからなるケーキがあります。上から i 行目、左から j 列目のピースには、s_{i,j} が 1 のときイチゴが載っており、0 のときイチゴが載っていません。

先手太郎君からはじめて、二人は残りのピースが 1 個になるまで交互にケーキに操作を行います。二人が行うことができる操作は以下の通りです。ただし、残りの全てのピースを食べてしまうような操作を行うことはできません。

上から 1 行目に並ぶピースを全て食べる
下から 1 行目に並ぶピースを全て食べる
左から 1 列目に並ぶピースを全て食べる
右から 1 列目に並ぶピースを全て食べる

先手太郎君はイチゴが載っているピースを、後手次郎君はイチゴが載っていないピースを残したいです。先手太郎君が適切に操作を行ったとき、後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができるかどうかを判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \le T \le 10^5
1 \le N,M \le 10^{3}
1<NM
s_{i} は 0 と 1 のみからなる長さ M の文字列
全てのテストケースにおける NM の総和は 10^6 以下

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N M
s_1
s_2
\vdots
s_N

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、先手太郎君が適切に操作を行ったとき、後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができるなら First を、そうでなければ Second を出力せよ。

入力例 1

出力例 1

Second
First
First
Second

1 番目のテストケースについて、先手太郎君がどのような操作を行っても後手二郎君はイチゴの載っていないピースを残すことができます。

2 番目のテストケースについて、先手太郎君が適切に操作を行うことで後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができます。

残りの全てのピースを食べてしまうような操作は選べないことに注意してください。

Score : 800 points

Problem Statement

Taro the First and Jiro the Second bought a rectangular cake as a present for their mother. They were hungry, so they decided to eat all of the cake except for one piece for their mother.

There is a cake consisting of pieces arranged in N rows and M columns. The piece at the i-th row from the top and j-th column from the left has a strawberry on it when s_{i,j} is 1, and does not have a strawberry when it is 0.

Starting with Taro the First, the two alternately perform an operation on the cake until only one piece remains. The operations they can perform are as follows. However, they cannot perform an operation that eats all remaining pieces.

Eat all pieces in the first row from the top
Eat all pieces in the first row from the bottom
Eat all pieces in the first column from the left
Eat all pieces in the first column from the right

Taro the First wants to leave a piece with a strawberry, and Jiro the Second wants to leave a piece without a strawberry. Determine whether Taro the First can leave a piece with a strawberry no matter how Jiro the Second operates, when Taro operates appropriately.

You are given T test cases; find the answer for each of them.

Constraints

1 \le T \le 10^5
1 \le N,M \le 10^{3}
1<NM
s_{i} is a string of length M consisting of 0 and 1.
The sum of NM over all test cases is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N M
s_1
s_2
\vdots
s_N

Output

Print T lines.

On the i-th line, for the i-th test case, print First if Taro the First can leave a piece with a strawberry no matter how Jiro the Second operates when Taro operates appropriately, and Second otherwise.

Sample Input 1

Sample Output 1

Second
First
First
Second

For the first test case, no matter what operation Taro performs, Jiro can leave a piece without a strawberry.

For the second test case, if Taro operates appropriately, he can leave a piece with a strawberry no matter how Jiro operates.

Note that they cannot choose an operation that eats all remaining pieces.

E - Erase and Append

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

0 と 1 のみからなる長さ N の文字列 s,t が与えられます。以下の操作を 0 回以上 N+1 回以下行うことで s を t と一致させることが可能かどうかを判定し、可能な場合は操作列の一例を示してください。

操作：以下を順番に行う

1 \le a,b \le N かつ |a-b|=1 を満たす整数 a,b を選ぶ
s の先頭から a 番目の文字を s の末尾に追加する
s の先頭から b 番目の文字を取り除き、残りの文字を元の順序を保って連結する

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \le T \le 10^{5}
2 \le N \le 2 \times 10^{5}
s,t は長さ N の 0 と 1 のみからなる文字列
全てのテストケースにおける N の総和は 2 \times 10^{5} 以下

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
s
t

出力

与えられたテストケースに対し与えられた順に答えを出力せよ。操作を 0 回以上 N+1 回以下行うことで s を t と一致させることが不可能ならば -1 を出力せよ。可能ならば、はじめに操作回数 K を出力し、続く K 行のうち j 行目には j 回目の操作で選ぶ 2 つの整数 a_j,b_j を空白区切りで出力せよ。

入力例 1

出力例 1

1 番目のテストケースにおいて s は 00101, t は 00010 です。

a,b として 2,3 を選び、2 番目の文字である 0 を s の末尾に追加した後、3 番目の文字を取り除くことで s と t を一致させることができます。
操作で選ぶ整数 a,b について |a-b|=1 である必要がある点に注意してください。

2 番目のテストケースにおいて、0 回の操作により s と t を一致させることができます。

3 番目のテストケースにおいて、どのように操作を行っても s と t は一致させることはできません。

Score : 800 points

Problem Statement

You are given strings s and t of length N consisting of 0 and 1. Determine whether it is possible to make s match t by performing the following operation at least 0 and at most N+1 times, and if possible, show one such sequence of operations.

Operation: Perform the following in order.

Choose integers a and b satisfying 1 \le a,b \le N and |a-b|=1
Append the a-th character from the beginning of s to the end of s
Remove the b-th character from the beginning of s and concatenate the remaining characters in their original order

You are given T test cases; find the answer for each of them.

Constraints

1 \le T \le 10^{5}
2 \le N \le 2 \times 10^{5}
s and t are strings of length N consisting of 0 and 1.
The sum of N over all test cases is at most 2 \times 10^{5}.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
s
t

Output

Print the answers for the given test cases in the order they are given. If it is impossible to make s match t by performing the operation at least 0 and at most N+1 times, print -1. If possible, first print the number of operations K, and on the j-th of the following K lines, print the two integers a_j and b_j chosen in the j-th operation, separated by a space.

Sample Input 1

Sample Output 1

In the first test case, s is 00101 and t is 00010.

By choosing 2 and 3 as a and b, appending the 2-nd character 0 to the end of s, and then removing the 3-rd character, we can make s and t match.
Note that the integers a and b chosen in the operation must satisfy |a-b|=1.

In the second test case, s and t can be made to match with zero operations.

In the third test case, no matter how the operations are performed, s and t cannot be made to match.