Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
A
,B
のみからなる長さ n\ (2\leq n) の文字列 T=T_1T_2\dots T_n に対し、長さ n-1 の文字列 f(T) を以下のように定めます。
- T_i={}
A
が成り立つ i\ (1\leq i \leq n-1) 全体を a_1 < a_2 < \dots < a_{m} とし、 T_i={}B
が成り立つ i\ (1\leq i \leq n-1) 全体を b_1 < b_2 < \dots < b_k とする。このとき、 f(T)=T_{a_1+1}T_{a_2+1}\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots T_{b_k+1} と定める。
例えば文字列 T={}ABBABA
について、T_i={}A
が成り立つ i\ (1\leq i \leq 5) 全体は i=1,4 , T_i={}B
が成り立つ i\ (1\leq i \leq 5) 全体は i=2,3,5 であるため、f(T) は T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA
になります。
A
,B
のみからなる長さ N の文字列 S が与えられます。
S を f(S) で置き換えることを N-1 回行った後の S を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- S は
A
,B
のみからなる長さ N の文字列 - 入力される数値はすべて整数
- 1 つの入力に含まれるテストケースについて、 N の総和は 3 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられます。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各ケースは以下の形式で与えられます。
N S
出力
T 行出力してください。i 行目には i 番目のテストケースに対する答えを出力してください。
入力例 1
3 2 AB 3 AAA 4 ABAB
出力例 1
B A A
1 つ目のテストケースについて、S は AB
{}\rightarrow {}B
と変化します。
2 つ目のテストケースについて、S は AAA
{} \rightarrow {}AA
{} \rightarrow {}A
と変化します。
3 つ目のテストケースについて、S は ABAB
{}\rightarrow {}BBA
{} \rightarrow {}BA
{} \rightarrow {}A
と変化します。
Score : 400 points
Problem Statement
For a string T=T_1T_2\dots T_n of length n\ (2\leq n) consisting of A
and B
, we define a string f(T) of length n-1 as follows.
- Let a_1 < a_2 < \dots < a_{m} be the indices i\ (1\leq i \leq n-1) such that T_i={}
A
, and b_1 < b_2 < \dots < b_k be the indices i\ (1\leq i \leq n-1) such that T_i={}B
. Then, let f(T)=T_{a_1+1}T_{a_2+1}\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots T_{b_k+1}.
For example, for the string T={}ABBABA
, the indices i\ (1\leq i \leq 5) with T_i={}A
are i=1,4, and the indices i\ (1\leq i \leq 5) with T_i={}B
are i=2,3,5, so f(T) is T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA
.
You are given a string S of length N consisting of A
and B
.
Find S after replacing S with f(S) (N-1) times.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- S is a string of length N consisting of
A
andB
. - All numbers in the input are integers.
- The sum of N over the test cases in a single input file is at most 3 \times 10^5.
Input
The input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each case is given in the following format:
N S
Output
Print T lines. The i-th line should contain the answer to the i-th test case.
Sample Input 1
3 2 AB 3 AAA 4 ABAB
Sample Output 1
B A A
In the first test case, S changes as AB
{}\rightarrow {}B
.
In the second test case, S changes as AAA
{} \rightarrow {}AA
{} \rightarrow {}A
.
In the third test case, S changes as ABAB
{}\rightarrow {}BBA
{} \rightarrow {}BA
{} \rightarrow {}A
.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
1 から N までの整数からなる順列 A=(A_1,A_2,\dots,A_N) があります。はじめ A_i=i\ (1\leq i \leq N) です。
高橋君はこの順列に対し以下のような操作を K 回行います。
- 0 \leq k < N を満たす整数 k を選ぶ。A の後ろ k 項を前 N-k 項に挿入する。より正確には、A を以下の条件を満たす長さ N の好きな順列 A' で置き換える。
- (A_1,A_2,\dots,A_{N-k}) は A' の(連続とは限らない)部分列である。
- (A_{N-k+1},A_{N-k+2},\dots,A_{N}) は A' の(連続とは限らない)部分列である。
i 回目の操作で選んだ k を k_i としたとき、一連の操作にかかるコストは \sum_{i=1}^{K}k_iC_i です。
高橋君は K 回の操作の後、A=(P_1,P_2,\dots,P_N) が成り立つように操作を行いたいです。
そのように一連の操作を行うことが可能か判定してください。可能な場合、そのような一連の操作にかかるコストの最小値を求めてください。
制約
- 2 \leq N \leq 100
- 1 \leq K \leq 100
- 1 \leq C_i \leq 10^9
- (P_1,P_2,\dots,P_N) は 1 から N までの整数からなる順列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K C_1 C_2 \dots C_K P_1 P_2 \dots P_N
出力
K 回の操作の後、A=(P_1,P_2,\dots,P_N) が成り立つように操作を行うことが不可能な場合、 -1
を出力してください。可能な場合、そのような一連の操作のコストの最小値を出力してください。
入力例 1
4 1 3 3 1 2 4
出力例 1
6
操作で k=2 とし、A_3=3 を A_1,A_2 より前に、 A_4=4 を A_1,A_2 の後に挿入することで A=(3,1,2,4) とすることができ、 A=(P_1,P_2,P_3,P_4) が成り立ちます。この操作のコストは 2 \times C_1 = 6 です。
操作後、 A=(P_1,P_2,P_3,P_4) が成り立つように操作するとき、コストの最小値は 6 であることが証明できます。
入力例 2
4 1 3 4 3 2 1
出力例 2
-1
操作後、A=(P_1,P_2,P_3,P_4) が成り立つように操作することはできません。
入力例 3
20 10 874735445 684260477 689935252 116941558 915603029 923404262 843759669 656978932 286318130 255195090 11 15 20 10 6 8 18 2 12 4 9 13 19 3 16 7 14 17 5 1
出力例 3
7372920743
[English Translation]
Score : 700 points
Problem Statement
There is a permutation A=(A_1,A_2,\dots,A_N) of the integers from 1 to N. Initially, we have A_i=i\ (1\leq i \leq N).
Takahashi will perform the following operation on this sequence K times.
- Choose an integer k such that 0 \leq k < N. Take the last k terms of A and insert them among the first N-k. More precisely, replace A with any permutation A' of the N integers that satisfies the following conditions.
- (A_1,A_2,\dots,A_{N-k}) is a (not necessarily contiguous) subsequence of A'.
- (A_{N-k+1},A_{N-k+2},\dots,A_{N}) is a (not necessarily contiguous) subsequence of A'.
The cost of the series of operations is \sum_{i=1}^{K}k_iC_i, where k_i is the k chosen in the i-th operation.
Takahashi wants to perform K operations so that A=(P_1,P_2,\dots,P_N) afterward.
Determine whether it is possible to perform such a series of operations. If it is possible, find its minimum cost.
Constraints
- 2 \leq N \leq 100
- 1 \leq K \leq 100
- 1 \leq C_i \leq 10^9
- (P_1,P_2,\dots,P_N) is a permutation of the integers from 1 to N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K C_1 C_2 \dots C_K P_1 P_2 \dots P_N
Output
If it is impossible to perform K operations so that A=(P_1,P_2,\dots,P_N) holds afterward, print -1
. If it is possible, print the minimum cost of such a series of operations.
Sample Input 1
4 1 3 3 1 2 4
Sample Output 1
6
By choosing k=2, and inserting A_3=3 before A_1,A_2 and A_4=4 after A_1,A_2, we can make A=(3,1,2,4), which satisfies A=(P_1,P_2,P_3,P_4). The cost of this operation is 2 \times C_1 = 6.
It can be proved that the minimum cost of performing operations so that A=(P_1,P_2,P_3,P_4) afterward is 6.
Sample Input 2
4 1 3 4 3 2 1
Sample Output 2
-1
It is impossible to perform operations so that A=(P_1,P_2,P_3,P_4) afterward.
Sample Input 3
20 10 874735445 684260477 689935252 116941558 915603029 923404262 843759669 656978932 286318130 255195090 11 15 20 10 6 8 18 2 12 4 9 13 19 3 16 7 14 17 5 1
Sample Output 3
7372920743
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下の条件を満たす正整数 X を小さいほうから順に K 個求めてください。
- A の空でない(連続とは限らない)部分列であって、要素の和が X であるものが存在しない
制約
- 1 \leq N \leq 60
- 1 \leq K \leq 1000
- 1 \leq A_i \leq 10^{15}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K A_1 A_2 \dots A_N
出力
条件を満たす K 個の正整数を昇順に、空白区切りで出力してください。
入力例 1
3 3 1 2 5
出力例 1
4 9 10
A の部分列としては (1),(2),(1,2),(5),(1,5),(2,5),(1,2,5) が考えられ、要素の和はそれぞれ 1,2,3,5,6,7,8 です。よって X=1,2,3,5,6,7,8 に対しては、要素の和が X であるような A の部分列が存在します。
一方 X=4,9,10 に対しては、要素の和が X であるような A の部分列は存在しません。
入力例 2
20 10 324 60 1 15 60 15 1 60 319 1 327 1 2 60 2 345 1 2 2 15
出力例 2
14 29 44 59 74 89 104 119 134 149
Score : 800 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N).
Find the K smallest positive integers X that satisfy the following condition.
- There is no non-empty (not necessarily contiguous) subsequence of A whose elements sum to X.
Constraints
- 1 \leq N \leq 60
- 1 \leq K \leq 1000
- 1 \leq A_i \leq 10^{15}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the K smallest positive integers satisfying the conditions in ascending order, separated by spaces.
Sample Input 1
3 3 1 2 5
Sample Output 1
4 9 10
The subsequences of A are (1),(2),(1,2),(5),(1,5),(2,5),(1,2,5), and their respective sums are 1,2,3,5,6,7,8. Therefore, for X=1,2,3,5,6,7,8, there are subsequences of A whose elements sum to X.
On the other hand, for X=4,9,10, there is no subsequence of A whose elements sum to X.
Sample Input 2
20 10 324 60 1 15 60 15 1 60 319 1 327 1 2 60 2 345 1 2 2 15
Sample Output 2
14 29 44 59 74 89 104 119 134 149
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
二次元平面の原点 (0,0) にメモ帳を持った高橋君がいます。メモ帳には N 個の偶数 D_i\ (1\leq i \leq N) が書かれています。
これから高橋君は二次元平面上で以下の行動を N 回行います。
- メモ帳に書かれている偶数を 1 つ選んで消す。選んだ偶数を d としたとき、マンハッタン距離でちょうど d だけ離れた点へ移動する。より正確には、現在高橋君がいる点の座標を (x,y) としたとき、|x-x'|+|y-y'|=d を満たす点 (x',y') へ移動する。
N 回の行動を行った後、高橋君は原点 (0,0) に戻っていなければなりません。
そのように N 回の行動を行うことができるか判定してください。可能な場合、i 回目の行動を終えた後高橋君がいる座標を (x_i,y_i) としたときの \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) の最小値を求めてください(この値は整数になることが証明できます)。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq D_i \leq 2 \times 10^5
- D_i\ (1\leq i \leq N) は偶数
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N D_1 D_2 \dots D_N
出力
上記のように N 回の行動を行うことが不可能な場合、-1
を出力してください。可能な場合、\displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) の最小値を整数で出力してください。
入力例 1
3 2 4 6
出力例 1
4
高橋君が 1 回目から 3 回目の行動でそれぞれ 2,6,4 をメモ帳から消し、 (0,0)\rightarrow (0,2) \rightarrow (-4,0) \rightarrow (0,0) と移動すると \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) は 4 になり、これが最小です。
入力例 2
5 2 2 2 2 6
出力例 2
3
高橋君が 1 回目から 5 回目の行動でそれぞれ 2,2,6,2,2 をメモ帳から消し、 (0,0)\rightarrow (\frac{1}{2},\frac{3}{2})\rightarrow (0,3) \rightarrow (0,-3) \rightarrow (-\frac{1}{2},-\frac{3}{2}) \rightarrow (0,0) と移動すると \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) は 3 になり、これが最小です。
高橋君は格子点以外にも移動できます。
入力例 3
2 2 200000
出力例 3
-1
高橋君は上記のように N 回行動した後、原点に戻ることはできません。
Score : 1100 points
Problem Statement
Takahashi, with a notepad, is standing at the origin (0,0) of a two-dimensional plane. His notepad has N even numbers D_i\ (1\leq i \leq N) written.
Takahashi will perform the following actions N times on the plane.
- He chooses and erases one even number written on the notepad. Let d be the chosen even number. He then moves to a point exactly d distance away in terms of Manhattan distance. More precisely, if Takahashi is currently at the coordinates (x,y), he moves to a point (x',y') such that |x-x'|+|y-y'|=d.
After performing N actions, Takahashi must return to the origin (0,0).
Determine if it is possible to perform N actions in such a way. If it is possible, find the minimum value of \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|), where (x_i,y_i) are the coordinates where Takahashi is located after the i-th action (we can prove that this value is an integer).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq D_i \leq 2 \times 10^5
- D_i\ (1\leq i \leq N) is even.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D_1 D_2 \dots D_N
Output
If it is impossible to perform N actions as described above, print -1
. If it is possible, print the minimum value of \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) as an integer.
Sample Input 1
3 2 4 6
Sample Output 1
4
If Takahashi erases 2,6,4 from his notepad for the first to third actions, respectively, and moves as (0,0)\rightarrow (0,2) \rightarrow (-4,0) \rightarrow (0,0), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 4, which is the minimum.
Sample Input 2
5 2 2 2 2 6
Sample Output 2
3
If Takahashi erases 2,2,6,2,2 from his notepad for the first to fifth actions, respectively, and moves as (0,0)\rightarrow (\frac{1}{2},\frac{3}{2})\rightarrow (0,3) \rightarrow (0,-3) \rightarrow (-\frac{1}{2},-\frac{3}{2}) \rightarrow (0,0), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 3, which is the minimum.
Takahashi can also move to non-grid points.
Sample Input 3
2 2 200000
Sample Output 3
-1
Takahashi cannot return to the origin after performing N actions as described above.
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 1300 点
問題文
奇数 N 、および非負整数 K が与えられます。
以下の条件をすべて満たす整数の組の列 ((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) の数を 998244353 で割った余りを求めてください。
- (L_1,R_1,L_2,R_2,\dots,L_N,R_N) は 1 から 2N までの整数の順列
- L_1 \leq L_2 \leq \dots \leq L_N
- L_i \leq R_i \ (1 \leq i \leq N)
- L_i+1=R_i が成り立つような i\ (1\leq i \leq N) はちょうど K 個存在する
- 1 から N までの番号が付いた N 頂点の根付き二分木 T であって、以下が成り立つものが存在する
- T において頂点 i,j には祖先・子孫の関係がある \iff 区間 [L_i,R_i],[L_j,R_j] が共通部分を持つ
ただし、根付き二分木とは、全ての頂点の子の個数が 0 個か 2 個であるような根付き木のことを指します。また、木 T において頂点 j が根と頂点 i を結ぶ単純パス上に存在する、または頂点 i が根と頂点 j を結ぶ単純パス上に存在するとき、T において頂点 i,j には祖先・子孫の関係があるといいます。
制約
- 1 \leq N < 2 \times 10^5
- 0 \leq K \leq N
- N は奇数
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K
出力
答えを出力してください。
入力例 1
3 1
出力例 1
2
例えば (L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6) の場合、L_i+1=R_i が成り立つのは i=2 の 1 個のみです。また、5 番目の条件で述べられている木については、頂点 1 が根であり、その子が頂点 2,3 であるような根付き木が該当します。
入力例 2
1 0
出力例 2
0
入力例 3
521 400
出力例 3
0
入力例 4
199999 2023
出力例 4
283903125
Score: 1300 points
Problem Statement
You are given an odd number N and a non-negative integer K.
Find the number, modulo 998244353, of sequences of integer pairs ((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) satisfying all of the following conditions.
- (L_1,R_1,L_2,R_2,\dots,L_N,R_N) is a permutation of the integers from 1 to 2N.
- L_1 \leq L_2 \leq \dots \leq L_N.
- L_i \leq R_i \ (1 \leq i \leq N).
- There are exactly K indices i\ (1\leq i \leq N) such that L_i+1=R_i.
- There is a rooted binary tree T with N vertices numbered from 1 to N such that the following holds:
- vertices i and j have an ancestor-descendant relationship in T \iff intervals [L_i,R_i] and [L_j,R_j] intersect.
Here, a rooted binary tree is a rooted tree where each vertex has 0 or 2 children. Vertices i and j are said to have an ancestor-descendant relationship in a tree T if either vertex j exists on the simple path connecting the root to vertex i, or vice versa.
Constraints
- 1 \leq N < 2 \times 10^5
- 0 \leq K \leq N
- N is odd.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
2
For example, if (L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6), then i=2 is the only pair with L_i+1=R_i. Also, the fifth condition is satisfied by a tree where vertex 1 is the root, and its children are vertices 2 and 3.
Sample Input 2
1 0
Sample Output 2
0
Sample Input 3
521 400
Sample Output 3
0
Sample Input 4
199999 2023
Sample Output 4
283903125
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
1 以上 M 以下の整数が書かれているカードからなる山札が N 個あります。 i\ (1\leq i \leq N) 番目の山札は K_i 枚のカードからなり、上から j 枚目のカードに書かれている整数は A_{i,j}\ (1\leq j \leq K_i) です。
カードに書かれている整数ははじめ、以下の制約を満たします。
- 各整数 x\ (1\leq x \leq M) について、x が書かれているカードは N 個の山札のうちちょうど 2 つの山札に 1 枚ずつ存在する
- 各山札の一番上のカードに書かれている整数は互いに相異なる
N 個の山札に対し以下のような操作を考えます。
- カードが残っている山札を 1 つ選び、一番上のカードを捨てる。ただし、カードを捨てた後、カードが残っている各山札の一番上のカードに書かれている整数は互いに相異なっていなければならない
最大で何回操作を行えるか求めてください。
制約
- 2 \leq N \leq M
- 2 \leq M \leq 2 \times 10^5
- 1 \leq K_i \leq M
- 1 \leq A_{i,j} \leq M
- 各整数 x\ (1\leq x \leq M) に対し、x=A_{i,j} が成り立つ i,j の組はちょうど 2 つ存在し、2 つの i は互いに相異なる
- A_{i,1}\ (1\leq i \leq N) は互いに相異なる
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M K_1 A_{1,1} A_{1,2} \dots A_{1,K_1} K_2 A_{2,1} A_{2,2} \dots A_{2,K_2} \vdots K_N A_{N,1} A_{N,2} \dots A_{N,K_N}
出力
答えを出力してください。
入力例 1
2 4 4 1 2 3 4 4 3 2 1 4
出力例 1
1
はじめに 1 番目の山札に対して操作すると、山札のカードに書かれている整数は上から順に 2,3,4 となります。この状態から 1 番目の山札に対して操作すると、1 番目の山札も 2 番目の山札も一番上のカードに書かれている整数が 3 になってしまうため、1 番目の山札に操作できません。同様に 2 番目の山札に対しても操作できません。よってはじめに 1 番目の山札に対して操作した場合、操作できるのは 1 回だけです。
はじめに 2 番目の山札に対して操作した場合も操作できるのは 1 回だけなので、答えは 1 です。
入力例 2
4 6 2 6 4 3 2 5 3 4 3 1 5 6 3 4 1 2
出力例 2
12
適切に操作をすることで全てのカードを捨てることができます。
入力例 3
3 3 2 1 2 2 2 3 2 3 1
出力例 3
0
1 回も操作できないこともあります。
入力例 4
12 40 4 35 39 11 21 7 31 29 16 15 30 32 34 4 21 27 38 40 11 17 28 26 23 33 22 3 36 8 1 20 1 30 4 40 38 24 6 8 8 36 9 10 5 7 20 4 10 5 10 9 3 22 33 23 26 28 17 4 15 16 29 31 11 19 13 12 18 25 2 39 35 7 14 37 3 4 1 14 13 24 27 11 2 25 18 12 13 19 32 37 6 34
出力例 4
53
Score : 2000 points
Problem Statement
There are N decks of cards, each card in which has an integer between 1 and M, inclusive, written on it. The i-th deck (1\leq i \leq N) contains K_i cards, and the number written on the j-th card from the top is A_{i,j}\ (1\leq j \leq K_i).
Initially, the integers written on the cards satisfy the following conditions:
- For each integer x\ (1\leq x \leq M), there are exactly two cards with x written on them, each in a different deck.
- The integers written on the top cards of all the decks are pairwise different.
We can perform the following operation on the N decks:
- Choose a deck that still has cards and discard the top card. After discarding, the integers written on the top cards of the decks that still have cards must remain pairwise different.
Determine the maximum number of times this operation can be performed.
Constraints
- 2 \leq N \leq M
- 2 \leq M \leq 2 \times 10^5
- 1 \leq K_i \leq M
- 1 \leq A_{i,j} \leq M
- For each integer x\ (1\leq x \leq M), there are exactly two pairs (i,j) such that x=A_{i,j}, and the two values of i are different.
- A_{i,1}\ (1\leq i \leq N) are pairwise different.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K_1 A_{1,1} A_{1,2} \dots A_{1,K_1} K_2 A_{2,1} A_{2,2} \dots A_{2,K_2} \vdots K_N A_{N,1} A_{N,2} \dots A_{N,K_N}
Output
Print the answer.
Sample Input 1
2 4 4 1 2 3 4 4 3 2 1 4
Sample Output 1
1
If you initially perform the operation on the first deck, the numbers on the cards of this deck become 2, 3, 4 in order from the top. After this, you may not perform the operation again on the first deck because both the first and second decks would have 3 on their top cards. Similarly, you cannot perform the operation on the second deck either. Therefore, if you start by performing the operation on the first deck, you can only do it once.
Even if you start by performing the operation on the second deck, you can only do it once. Therefore, the answer is 1.
Sample Input 2
4 6 2 6 4 3 2 5 3 4 3 1 5 6 3 4 1 2
Sample Output 2
12
By operating properly, it is possible to discard all the cards.
Sample Input 3
3 3 2 1 2 2 2 3 2 3 1
Sample Output 3
0
There are cases when no operation can be performed.
Sample Input 4
12 40 4 35 39 11 21 7 31 29 16 15 30 32 34 4 21 27 38 40 11 17 28 26 23 33 22 3 36 8 1 20 1 30 4 40 38 24 6 8 8 36 9 10 5 7 20 4 10 5 10 9 3 22 33 23 26 28 17 4 15 16 29 31 11 19 13 12 18 25 2 39 35 7 14 37 3 4 1 14 13 24 27 11 2 25 18 12 13 19 32 37 6 34
Sample Output 4
53