A - Digit Machine

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 桁の数字が表示される画面と、ボタンからなる機械があります。

画面に数字 k が表示されているとき、ボタンを 1 回押すと画面の数字が a_k に変わります。

0 が表示されている状態からボタンを 3 回押すと、画面には何が表示されますか?

制約

  • 0\leq a_i \leq 9
  • 入力は全て整数である

入力

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

a_0 a_1 \dots a_9

出力

答えを出力せよ。


入力例 1

9 0 1 2 3 4 5 6 7 8

出力例 1

7

画面に表示される数字は、0 \rightarrow 9 \rightarrow 8 \rightarrow 7 と変化します。


入力例 2

4 8 8 8 0 8 8 8 8 8

出力例 2

4

画面に表示される数字は、0 \rightarrow 4 \rightarrow 0 \rightarrow 4 と変化します。


入力例 3

0 0 0 0 0 0 0 0 0 0

出力例 3

0

Score : 100 points

Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

  • 0\leq a_i \leq 9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a_0 a_1 \dots a_9

Output

Print the answer.


Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

7

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.


Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

4

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.


Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

0
B - 123233

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

6 桁の正整数 N が与えられます。
この整数が以下の条件を全て満たすか判定してください。

  • N の各桁のうち、 1 は丁度 1 つである。
  • N の各桁のうち、 2 は丁度 2 つである。
  • N の各桁のうち、 3 は丁度 3 つである。

制約

  • N は 100000 \le N \le 999999 を満たす整数

入力

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

N

出力

N が問題文中の条件を全て満たすなら Yes 、そうでないなら No と 1 行に出力せよ。


入力例 1

123233

出力例 1

Yes

123233 は問題文中の条件を満たすので、 Yes と出力します。


入力例 2

123234

出力例 2

No

123234 は問題文中の条件を満たさないので、 No と出力します。


入力例 3

323132

出力例 3

Yes

入力例 4

500000

出力例 4

No

Score : 100 points

Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

  • Among the digits of N, the digit 1 appears exactly once.
  • Among the digits of N, the digit 2 appears exactly twice.
  • Among the digits of N, the digit 3 appears exactly three times.

Constraints

  • N is an integer satisfying 100000 \le N \le 999999.

Input

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

N

Output

Print Yes if N satisfies all the conditions described in the problem statement, and No otherwise, in one line.


Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.


Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.


Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No
C - Spot the Difference

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

縦 N マス、横 N マスのグリッドが 2 個与えられます。それぞれグリッド A, グリッド B と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド A の上から i 行目、左から j 列目に書かれている文字は A_{i, j} です。
グリッド B の上から i 行目、左から j 列目に書かれている文字は B_{i, j} です。

2 つのグリッドは 1 ヵ所だけ書かれている文字が異なります。すなわち、A_{i, j} \neq B_{i, j} である N 以下の正整数の組 (i, j) はちょうど 1 個存在します。この (i, j) を求めてください。

制約

  • 1 \leq N \leq 100
  • A_{i, j}, B_{i, j} は全て英小文字
  • A_{i, j} \neq B_{i, j} である (i, j) がちょうど 1 個存在する

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

出力

A_{i, j} \neq B_{i, j} である N 以下の正整数の組を (i, j) とする。この時、(i, j) を以下の形式で出力せよ。

i j

入力例 1

3
abc
def
ghi
abc
bef
ghi

出力例 1

2 1

A_{2, 1} = d、B_{2, 1} = b なので A_{2, 1} \neq B_{2, 1} が成り立つため、(i, j) = (2, 1) は問題文の条件を満たします。


入力例 2

1
f
q

出力例 2

1 1

入力例 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

出力例 3

5 9

Score: 150 points

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

  • 1 \leq N \leq 100
  • A_{i, j} and B_{i, j} are all lowercase English letters.
  • There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Output

Let (i, j) be the pair of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Print (i, j) in the following format:

i j

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.


Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9
D - Vacation Together

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の人がいます。
N 人の人の今後 D 日間の予定が与えられます。人 i の予定は長さ D の文字列 S_i で表されて、S_i の j 文字目が o ならば j 日目は暇であることを、x ならばそうでないことを意味します。

D 日間のうち全員が暇であるような 連続する 何日かを選ぶことを考えます。
選べる日数は最大で何日ですか?ただし、選べる日が存在しない場合は 0 日と答えてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N, D は整数
  • S_i は o と x からなる長さ D の文字列

入力

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

N D
S_1
S_2
\vdots
S_N

出力

選べる日数の最大値を出力せよ。選べる日が存在しない場合は 0 を出力せよ。


入力例 1

3 5
xooox
oooxx
oooxo

出力例 1

2

2 日目と 3 日目は全員が暇な日なので選ぶことができます。
この 2 日間を選ぶと、連続する日にちを選ぶ方法の中で日数を最大にすることができます。


入力例 2

3 3
oxo
oxo
oxo

出力例 2

1

選ぶ日にちは連続している必要があるのに注意してください。(1 日目と 3 日目は全員が暇な日なので選ぶことができますが、この 2 つを同時に選ぶことはできません)


入力例 3

3 3
oox
oxo
xoo

出力例 3

0

選べる日が存在しない場合は 0 を出力してください。


入力例 4

1 7
ooooooo

出力例 4

7

入力例 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

出力例 5

5

Score : 200 points

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N and D are integers.
  • S_i is a string of length D consisting of o and x.

Input

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

N D
S_1
S_2
\vdots
S_N

Output

Print the maximum number of days that can be chosen, or 0 if no day can be chosen.


Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.


Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)


Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.


Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5
E - Rotation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N,Q と、長さ N の英小文字からなる文字列 S が与えられます。

以下で説明されるクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。

  • 1 x: 「S の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行う。
  • 2 x: S の x 番目の文字を出力する。

制約

  • 2 \le N \le 5 \times 10^5
  • 1 \le Q \le 5 \times 10^5
  • 1 \le x \le N
  • |S|=N
  • S は英小文字からなる。
  • 2 x の形式のクエリが 1 個以上与えられる。
  • N,Q,x はすべて整数。

入力

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

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

それぞれのクエリは以下の形式で与えられる。ここで、t は 1 または 2 である。

t x

出力

2 x の形式の各クエリについて、答えを一行に出力せよ。


入力例 1

3 3
abc
2 2
1 1
2 2

出力例 1

b
a

1 個目のクエリのとき、S は abc なので 2 文字目の b を出力します。 2 個目のクエリのとき、S は abc から cab に変わります。 3 個目のクエリのとき、S は cab なので 2 文字目の a を出力します。


入力例 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

出力例 2

c
u
c
u

Score : 300 points

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

  • 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
  • 2 x: Print the x-th character of S.

Constraints

  • 2 \le N \le 5 \times 10^5
  • 1 \le Q \le 5 \times 10^5
  • 1 \le x \le N
  • |S|=N
  • S consists of lowercase English letters.
  • At least one query in the format 2 x.
  • N, Q, x are all integers.

Input

Input is given from Standard Input in the following format:

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is in the following format, where t is 1 or 2:

t x

Output

For each query in the format 2 x, print the answer in a single line.


Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.


Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u
F - Perfect Standings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋くんは、プログラミングコンテストを主催することにしました。

コンテストは A 問題、B 問題、C 問題、D 問題、E 問題の 5 問からなり、それぞれの配点は a 点、b 点、c 点、d 点、e 点です。

コンテストには 31 人が参加し、全員が 1 問以上解きました。

より具体的には、文字列 ABCDE の空でない(連続するとは限らない)部分列すべてについて、その部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題をすべて解き、それ以外の問題は解きませんでした。

例えば、A さんは A 問題のみを、BCE さんは B 問題、C 問題、E 問題を解きました。

参加者の名前を、取った点数が大きいほうから順に出力してください。 ただし、参加者が取った点数は、その参加者が解いた問題の配点の合計です。

ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力してください。

辞書順で小さいとは?

辞書順とは、一言で説明すると「単語が辞書に載っている順番」を意味します。

より厳密には、英大文字からなる相異なる文字列 S,T について、S が T より辞書順で小さいとは、以下の条件のどちらかが成り立つことを意味します。

  • S の長さ |S| が T の長さより短く、T の先頭 |S| 文字が S と一致する
  • ある整数 1\leq i\leq\min\lbrace|S|,|T|\rbrace が存在して、次の 2 つの条件を両方を満たす
    • 1\leq j\lt i を満たすすべての整数 j に対して S の j 文字目と T の j 文字目が等しい
    • S の i 文字目が T の i 文字目よりアルファベット順で小さい

例えば、S= AB ,T= ABC とすると、ひとつめの条件が成り立つため S は T より小さいです。 また、S= ABD ,T= ACD とすると、ふたつめの条件が i=2 で成り立つため S は T より小さいです。

制約

  • 100\leq a\leq b\leq c\leq d\leq e\leq 2718
  • 入力はすべて整数

入力

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

a b c d e

出力

31 行出力せよ。 i 行目 (1\leq i\leq 31) には、i 番目に高い得点を獲得した参加者の名前を出力せよ。 同じ得点を獲得した参加者については、それらのうち辞書順で小さい名前をもつ参加者を先に出力せよ。


入力例 1

400 500 600 700 800

出力例 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

それぞれの参加者の得点は以下のようになります。

例えば、ADE さんと BCE さんは同じ得点を獲得していますが、ADE さんのほうが辞書順で小さい名前をもつため、ADE さんを先に出力してください。


入力例 2

800 800 900 900 1000

出力例 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

入力例 3

128 256 512 1024 2048

出力例 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A

Score : 300 points

Problem Statement

Takahashi decided to hold a programming contest.

The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.

There are 31 participants, and all of them solved at least one problem.

More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.

For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.

Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.

If two participants obtained the same score, print the one whose name is lexicographically smaller first.

What does "lexicographically smaller" mean?

In short, "lexicographically smaller" refers to the order in which words would appear in a dictionary.

More precisely, for distinct strings S,T consisting of uppercase English letters, S is lexicographically smaller than T if either of the following conditions holds:

  • The length |S| of S is less than the length of T, and the first |S| characters of T match S.
  • There exists an integer 1\leq i\leq\min\{ |S|,|T|\} that satisfy both of the following two conditions:
    • For every integer j with 1\leq j\lt i, the j-th character of S equals the j-th character of T.
    • The i-th character of S is alphabetically smaller than the i-th character of T.

For example, if S= AB and T= ABC, the first condition holds, so S is lexicographically smaller than T. If S= ABD and T= ACD, the second condition holds for i=2, so S is lexicographically smaller than T.

Constraints

  • 100\leq a\leq b\leq c\leq d\leq e\leq 2718
  • All input values are integers.

Input

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

a b c d e

Output

Print 31 lines. The i-th line (1\leq i\leq 31) should contain the name of the participant who obtained the i-th highest score. If multiple participants have the same score, print them in lexicographical order.


Sample Input 1

400 500 600 700 800

Sample Output 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.


Sample Input 2

800 800 900 900 1000

Sample Output 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

Sample Input 3

128 256 512 1024 2048

Sample Output 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A
G - Avoid K Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

A, B, ? からなる N 文字の文字列 S が与えられます。

正整数 K が与えられます。 A, B からなる文字列 T が次の条件を満たすとき、T は良い文字列であるということにします。

  • T の長さ K の連続する部分文字列で、回文であるものが存在しない。

S に含まれる ? の個数を q 個とします。 q 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は 2 ^ q 通りありますが、その中に良い文字列がいくつあるか求めてください。

ただし、答えは非常に大きくなる場合があるので、998244353 で割った余りを求めてください。

制約

  • 2\leq K\leq N\leq 1000
  • K\leq 10
  • S は A, B, ? からなる文字列
  • S の長さは N
  • N,K は整数

入力

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

N K
S

出力

答えを出力せよ。


入力例 1

7 4
AB?A?BA

出力例 1

1

与えられた文字列の中に ? は 2 個あります。 2 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は次の 4 通りあります。

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

このうち、最初の ABAAABA 以外の 3 つの文字列は、長さ 4 の回文 ABBA を連続する部分文字列として含むため、良い文字列ではありません。

よって、1 を出力してください。


入力例 2

40 7
????????????????????????????????????????

出力例 2

116295436

良い文字列の個数を 998244353 で割った余りを求めることに注意してください。


入力例 3

15 5
ABABA??????????

出力例 3

0

? をどのように置き換えても良い文字列にならないこともあります。


入力例 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

出力例 4

259240

Score : 450 points

Problem Statement

You are given a string S of length N consisting of characters A, B, and ?.

You are also given a positive integer K. A string T consisting of A and B is considered a good string if it satisfies the following condition:

  • No contiguous substring of length K in T is a palindrome.

Let q be the number of ? characters in S. There are 2^q strings that can be obtained by replacing each ? in S with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo 998244353.

Constraints

  • 2 \leq K \leq N \leq 1000
  • K \leq 10
  • S is a string consisting of A, B, and ?.
  • The length of S is N.
  • N and K are integers.

Input

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

N K
S

Output

Print the answer.


Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.


Sample Input 2

40 7
????????????????????????????????????????

Sample Output 2

116295436

Ensure to find the number of good strings modulo 998244353.


Sample Input 3

15 5
ABABA??????????

Sample Output 3

0

It is possible that there is no way to replace the ?s to obtain a good string.


Sample Input 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

Sample Output 4

259240
H - Our clients, please wait a moment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

ある国には都市が N 個あります。
あなたは、都市 1 にある営業所から 0 個以上の都市を経由して都市 N にある訪問先へ移動しようとしています。
移動手段は社用車と電車の 2 種類があります。都市 i から都市 j へ移動するときの所要時間は以下の通りです。

  • 社用車を使った場合 : D_{i,j} \times A 分
  • 電車を使った場合 : D_{i,j} \times B + C 分

ただし、社用車から電車に乗り換えることはできますが、電車から社用車に乗り換えることはできません。
また、乗り換えは各都市のみで行え、乗り換えに時間はかかりません。

都市 1 から都市 N に移動するのにかかる時間は最短で何分ですか?

制約

  • 2 \leq N \leq 1000
  • 1 \leq A, B, C \leq 10^6
  • D_{i,j} \leq 10^6
  • D_{i,i} = 0
  • D_{i,j} = D_{j,i} > 0 (i \neq j)
  • 入力される数値はすべて整数

入力

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

N A B C
D_{1,1} D_{1,2} \ldots D_{1,N}
D_{2,1} D_{2,2} \ldots D_{2,N}
\vdots
D_{N,1} D_{N,2} \ldots D_{N,N}

出力

答えを整数として出力せよ。


入力例 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

出力例 1

78

以下のように移動することで合計 78 分で都市 1 から都市 4 に移動することができます。

  • 都市 1 から都市 3 まで社用車で移動する。この移動には 2 \times 8 = 16 分かかる。
  • 都市 3 から都市 2 まで社用車で移動する。この移動には 3 \times 8 = 24 分かかる。
  • 都市 2 から都市 4 まで電車で移動する。この移動には 5 \times 5 + 13 = 38 分かかる。

78 分未満の時間で都市 1 から都市 4 に移動することはできません。


入力例 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

出力例 2

1

入力例 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

出力例 3

168604826785

Score : 450 points

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

  • D_{i,j} \times A minutes by company car, and
  • D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

  • 2 \leq N \leq 1000
  • 1 \leq A, B, C \leq 10^6
  • D_{i,j} \leq 10^6
  • D_{i,i} = 0
  • D_{i,j} = D_{j,i} > 0 (i \neq j)
  • All input values are integers.

Input

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

N A B C
D_{1,1} D_{1,2} \ldots D_{1,N}
D_{2,1} D_{2,2} \ldots D_{2,N}
\vdots
D_{N,1} D_{N,2} \ldots D_{N,N}

Output

Print the answer as an integer.


Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

  • Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
  • Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
  • Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.


Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785
I - 1122 Subsequence

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

正整数からなる(空でも良い)数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
(1122 数列の定義はD問題と共通です。)

  • \lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
  • 1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1} と X_{2i} は等しい。
  • 各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられるので、A の (連続でなくても良い)部分列 であって、1122 数列であるようなもののうち最長のものの長さを出力してください。

制約

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i \leq 20
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

A の(連続でなくても良い)部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。


入力例 1

7
1 3 3 1 2 2 1

出力例 1

4

例えば A の部分列として、1,4,5,6 項目をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。


入力例 2

1
20

出力例 2

0

Score : 525 points

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem D.)

  • \lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
  • For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
  • Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a subsequence (not necessarily contiguous) of A that is a 1122 sequence.

Constraints

  • 1\leq N \leq 2 \times 10^5
  • 1\leq A_i \leq 20
  • 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 maximum length of a (not necessarily contiguous) subsequence of A that is a 1122 sequence.


Sample Input 1

7
1 3 3 1 2 2 1

Sample Output 1

4

For example, choosing the 1-st, 4-th, 5-th, and 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer subsequence that satisfies the conditions for a 1122 sequence, so the answer is 4.


Sample Input 2

1
20

Sample Output 2

0