AtCoder Daily Training ALL 2026/08/05 16:00start

A - ^{-1}

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

配点 : 100 点

問題文

(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。

制約

1 \leq N \leq 100
1 \leq X \leq N
P は (1,2,…,N) を並び替えてできる数列
入力はすべて整数

入力

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

N X
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

4 3
2 3 1 4

出力例 1

P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。

入力例 2

5 2
3 5 1 4 2

出力例 2

入力例 3

6 6
1 2 3 4 5 6

出力例 3

Score : 100 points

Problem Statement

You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.

Constraints

1 \leq N \leq 100
1 \leq X \leq N
P is a permutation of (1,2,…,N).
All values in the input are integers.

Input

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

N X
P_1 P_2 \ldots P_N

Output

Print the answer.

Sample Input 1

4 3
2 3 1 4

Sample Output 1

We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.

Sample Input 2

5 2
3 5 1 4 2

Sample Output 2

Sample Input 3

6 6
1 2 3 4 5 6

Sample Output 3

B - Potions

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

配点 : 100 点

問題文

ナオヒロ君はモンスターを飼っています。モンスターの現在の体力は H です。
また、ナオヒロ君は N 種類の傷薬を持っています。傷薬は効き目の弱い順に 1 から N までの番号がついています。
傷薬 n をモンスターに与えると、モンスターの体力が P_n 増加します。ここで、P_1 \lt P_2 \lt \dots \lt P_N が成り立ちます。

ナオヒロ君は傷薬を 1 つモンスターに与えることで、モンスターの体力を X 以上にしたいです。
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力してください。(制約下においてそのような傷薬が存在することが保証されています。)

制約

2 \leq N \leq 100
1 \leq H \lt X \leq 999
1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
入力される値はすべて整数

入力

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

N H X
P_1 P_2 \dots P_N

出力

目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力せよ。

入力例 1

3 100 200
50 200 999

出力例 1

それぞれの傷薬をモンスターに 1 つ与えたときのモンスターの体力の変化は以下の通りです。

傷薬 1 をモンスターに与えるとモンスターの体力は 100 + 50 = 150 になります。
傷薬 2 をモンスターに与えるとモンスターの体力は 100 + 200 = 300 になります。
傷薬 3 をモンスターに与えるとモンスターの体力は 100 + 999 = 1099 になります。

与えた後に体力が X = 200 以上になっている傷薬は、傷薬 2 と傷薬 3 です。このうち最も効き目の弱い傷薬である傷薬 2 が答えになります。

入力例 2

2 10 21
10 999

出力例 2

入力例 3

10 500 999
38 420 490 585 613 614 760 926 945 999

出力例 3

Score : 100 points

Problem Statement

Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.

He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)

Constraints

2 \leq N \leq 100
1 \leq H \lt X \leq 999
1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
All input values are integers.

Input

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

N H X
P_1 P_2 \dots P_N

Output

Print the number of the least effective potion that can achieve the purpose.

Sample Input 1

3 100 200
50 200 999

Sample Output 1

Below is the change in the monster's health when one of the potions is given to the monster.

If potion 1 is given, the monster's health becomes 100 + 50 = 150.
If potion 2 is given, the monster's health becomes 100 + 200 = 300.
If potion 3 is given, the monster's health becomes 100 + 999 = 1099.

The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.

Sample Input 2

2 10 21
10 999

Sample Output 2

Sample Input 3

10 500 999
38 420 490 585 613 614 760 926 945 999

Sample Output 3

C - Prefix and Suffix

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

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)

S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。

S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。

制約

1 \leq N \leq M \leq 100
S は英小文字からなる長さ N の文字列
T は英小文字からなる長さ M の文字列

入力

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

N M
S
T

出力

問題文の指示に従って答えを出力せよ。

入力例 1

3 7
abc
abcdefg

出力例 1

S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。

入力例 2

3 4
abc
aabc

出力例 2

S は T の接尾辞ですが接頭辞ではありません。

入力例 3

3 3
abc
xyz

出力例 3

S は T の接頭辞でも接尾辞でもありません。

入力例 4

3 3
aaa
aaa

出力例 4

S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

1 \leq N \leq M \leq 100
S is a string of length N consisting of lowercase English letters.
T is a string of length M consisting of lowercase English letters.

Input

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

N M
S
T

Output

Print the answer according to the instructions in the problem statement.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

S and T may coincide, in which case S is both a prefix and a suffix of T.

D - The Honest Woodcutters

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

配点 : 200 点

問題文

N 人の木こり 1,2,\dots,N が斧を 1 個ずつ持っています。全員が斧を池に落としてしまいました。
池に N 個の斧 1,2,\dots,N が沈んでいました。
各木こり i は「自分が持っていた斧は斧 A_i である」と主張しています。
一方、この池の女神は、各斧 i を持っていたのは木こり B_i であることを知っています。

N 人の木こり全員が本当のことを言っているかどうかを判定してください。

制約

1 \leq N \leq 100
1 \leq A_i \leq N
1 \leq B_i \leq N
A_i \neq A_j\;(i \neq j)
B_i \neq B_j\;(i \neq j)
入力される値はすべて整数

入力

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

N  
A_1 A_2 \dots A_N  
B_1 B_2 \dots B_N

出力

N 人の木こり全員が本当のことを言っているならば Yes を、そうでないならば No を出力せよ。

入力例 1

3
3 1 2
2 3 1

出力例 1

Yes

N 人の木こり全員が本当のことを言っています。

入力例 2

4
1 2 3 4
1 3 2 4

出力例 2

No

木こり 2,3 の 2 人は嘘をついています。

入力例 3

5
2 4 5 1 3
4 1 5 2 3

出力例 3

Yes

Score : 200 points

Problem Statement

N woodcutters 1, 2, \dots, N each have one axe. All of them dropped their axes into a pond.
N axes 1, 2, \dots, N were found sunk in the pond.
Each woodcutter i claims that "I owned axe A_i."
On the other hand, the goddess of this pond knows that the woodcutter who owned axe i is woodcutter B_i.

Determine whether all N woodcutters are telling the truth.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq N
1 \leq B_i \leq N
A_i \neq A_j\;(i \neq j)
B_i \neq B_j\;(i \neq j)
All input values are integers.

Input

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

N  
A_1 A_2 \dots A_N  
B_1 B_2 \dots B_N

Output

Output Yes if all N woodcutters are telling the truth, and No otherwise.

Sample Input 1

3
3 1 2
2 3 1

Sample Output 1

Yes

All N woodcutters are telling the truth.

Sample Input 2

4
1 2 3 4
1 3 2 4

Sample Output 2

No

Woodcutters 2 and 3 are lying.

Sample Input 3

5
2 4 5 1 3
4 1 5 2 3

Sample Output 3

Yes

E - Perfect Standings

実行時間制限: 2 sec / メモリ制限: 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

F - Cycle Graph?

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

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1,2,\dots,N の番号が、辺には 1,2,\dots,M の番号がつけられており、辺 i は頂点 A_i と頂点 B_i を結んでいます。

このグラフがサイクルグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

サイクルグラフとは

頂点に 1, 2, \dots, N の番号が付けられた N 頂点のグラフがサイクルグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

i = 1, 2, \dots, N-1 に対して、頂点 v_i と v_{i+1} を結ぶ辺が存在する
頂点 v_N と v_1 を結ぶ辺が存在する
それら以外の辺は存在しない

制約

3\leq N \leq 2\times 10^5
0 \leq M \leq 2\times 10^5
1 \leq A_i, B_i \leq N
与えられるグラフは単純
入力は全て整数

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

与えられたグラフがサイクルグラフであるなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えられたグラフは以下の通りであり、これはサイクルグラフです。

入力例 2

出力例 2

No

与えられたグラフは以下の通りであり、これはサイクルグラフではありません。

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N and the edges are numbered 1,2,\dots,M. Edge i connects vertices A_i and B_i.

Determine whether this graph is a cycle graph.

Definition of simple undirected graph

A simple undirected graph is a graph with undirected edges without self-loops or multi-edges.

Definition of cycle graph

An N-vertex graph with vertices labeled 1,2,\dots,N is a cycle graph when there exists a permutation (v_1,v_2,\dots,v_N) of (1,2,\dots,N) such that:

For each i = 1,2,\dots,N-1, there is an edge between vertices v_i and v_{i+1}.
There is an edge between vertices v_N and v_1.
No other edges exist.

Constraints

3 \le N \le 2\times 10^5
0 \le M \le 2\times 10^5
1 \le A_i, B_i \le N
The given graph is simple.
All input values are integers.

Input

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

N M
A_1 B_1
\vdots
A_M B_M

Output

Output Yes if the given graph is a cycle graph; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The given graph is as follows, and this is a cycle graph.

Sample Input 2

Sample Output 2

No

The given graph is as follows, and this is not a cycle graph.

G - Step Up Robot

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

配点 : 400 点

問題文

無限に続く階段があります。一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。

0 段目に階段登りロボットがいます。階段登りロボットは、一回の動作で A _ 1,A _ 2,\ldots,A _ N 段ぶん階段をのぼることができます。つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A _ 1 段目、i+A _ 2 段目、⋯、i+A _ N 段目のいずれかにいることができます。それ以外の段数を一回の動作でのぼることはできません。階段登りロボットは階段を下ることもできません。

階段の B _ 1,B _ 2,\ldots,B _ M 段目にはモチが設置されています。モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど X 段目にのぼりたいです。階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。

制約

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

出力

階段登りロボットが階段のちょうど X 段目にのぼることができるとき Yes を、そうでないとき No を 1 行に出力せよ。

入力例 1

出力例 1

Yes

例えば、次のようにして 15 段目に到達することができます。

階段を 3 段のぼる。ロボットは 3 段目に移動する。
階段を 4 段のぼる。ロボットは 7 段目に移動する。
階段を 5 段のぼる。ロボットは 12 段目に移動する。
階段を 3 段のぼる。ロボットは 15 段目に移動する。

入力例 2

出力例 2

No

どのように移動しても階段登りロボットが階段のちょうど 8 段目にいることはできません。

入力例 3

4
2 5 7 8
5
2 9 10 11 19
20

出力例 3

Yes

Score : 400 points

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.

There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the X-th step. Determine whether it is possible to do so.

Constraints

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
All values in the input are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

Output

In a single line, print Yes if the robot can step onto the X-th step, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For example, the robot can reach the 15-th step as follows.

Climb up 3 steps. The robot is now on the 3-rd step.
Climb up 4 steps. The robot is now on the 7-th step.
Climb up 5 steps. The robot is now on the 12-th step.
Climb up 3 steps. The robot is now on the 15-th step.

Sample Input 2

Sample Output 2

No

No matter how the robot moves, it cannot step onto the 8-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

H - Our clients, please wait a moment

実行時間制限: 2 sec / メモリ制限: 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

出力例 1

以下のように移動することで合計 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

入力例 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

Sample Output 1

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

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 - Shortest Path Query

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

配点 : 525 点

問題文

3 行 N 列のグリッドが与えられます。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) には S_{i,j} が # ならば壁マスで、 . ならば空きマスであり通行可能です。

Q 個のクエリが与えられるので、順に処理してください。

各クエリでは整数 r,c が与えられるので、マス (r,c) の状態を反転させてください。つまり、マス (r,c) が壁マスならば空きマスにし、空きマスならば壁マスにしてください。その後、以下の問題の答えを出力してください。

マス (1,1) から上下左右に隣接する空きマスに移動する操作を繰り返してマス (3,N) に移動することを考えます。このとき、マス (3,N) に到達できるか判定し、到達できる場合は操作回数の最小値を求めてください。

制約

2\le N\le 2\times 10^5
S_{i,j} は # または .
S_{1,1}=S_{3,N}= .
1\le Q\le 2\times 10^5
1\le r\le 3
1\le c\le N
(r,c) \neq (1,1),(3,N)
N,Q,r,c は整数

入力

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

N
S_{1,1}S_{1,2}\ldots S_{1,N}
S_{2,1}S_{2,2}\ldots S_{2,N}
S_{3,1}S_{3,2}\ldots S_{3,N}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下の形式で与えられる。

r c

出力

Q 行出力せよ。

i 行目 (1\le i\le Q) には、 i 番目のクエリにおいてマス (1,1) からマス (3,N) に到達不可能ならば -1 を、到達可能ならば操作回数の最小値を出力せよ。

入力例 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

出力例 1

6
10
-1

1 つ目のクエリではマス (1,2) の状態を反転させます。その結果、各マスの状態は以下のようになります。

.....
.#.#.
...#.

このとき、マス (1,1) から順にマス (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) と移動することで 6 回の操作でマス (3,5) に到達することができます。

2 つ目のクエリではマス (1,2) の状態を反転させます。その結果、各マスの状態は以下のようになります。

.#...
.#.#.
...#.

このとき、マス (1,1) から順にマス (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) と移動することで 10 回の操作でマス (3,5) に到達することができます。

3 つ目のクエリではマス (2,3) の状態を反転させます。その結果、各マスの状態は以下のようになります。

.#...
.###.
...#.

このとき、どのように操作してもマス (1,1) からマス (3,5) に到達することはできません。

入力例 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

出力例 2

Score : 525 points

Problem Statement

You are given a grid with three rows and N columns. Denote the cell at the i-th row from the top and j-th column from the left as cell (i,j). Cell (i,j) is a wall cell if S_{i,j} is #, and an empty cell and passable if it is ..

You are given Q queries, which you should process in order.

Each query gives integers r and c, and you should flip the state of cell (r,c). That is, if cell (r,c) is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem:

Consider moving from cell (1,1) to cell (3,N) by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell (3,N) is reachable, and if reachable, find the minimum number of moves.

Constraints

2\le N\le 2\times 10^5
S_{i,j} is # or ..
S_{1,1}=S_{3,N}= .
1\le Q\le 2\times 10^5
1\le r\le 3
1\le c\le N
(r,c) \neq (1,1),(3,N)
N,Q,r,c are integers.

Input

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

N
S_{1,1}S_{1,2}\ldots S_{1,N}
S_{2,1}S_{2,2}\ldots S_{2,N}
S_{3,1}S_{3,2}\ldots S_{3,N}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

r c

Output

Print Q lines.

On the i-th line (1\le i\le Q), if cell (3,N) is unreachable from cell (1,1) in the i-th query, print -1; if reachable, print the minimum number of moves.

Sample Input 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

Sample Output 1

6
10
-1

In the first query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.....
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in six moves.

In the second query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.#...
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in ten moves.

In the third query, flip the state of cell (2,3). As a result, the state of each cell becomes:

.#...
.###.
...#.

At this time, no matter how you move, you cannot reach cell (3,5) from cell (1,1).

Sample Input 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

Sample Output 2