Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
上下左右に広がる H 行 W 列のマス目があり、各マスにはコマが置かれているか、何も置かれていないかのどちらかです。
マス目の状態は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって表され、
S_i の j 文字目が #
のとき上から i 行目かつ左から j 列目のマスにはコマが置かれていることを、
S_i の j 文字目が .
のとき上から i 行目かつ左から j 列目のマスには何も置かれていないことを表しています。
マス目上のマスのうち、コマが置かれているようなものの個数を求めてください。
制約
- 1\leq H,W \leq 10
- H,W は整数
- S_i は
#
と.
のみからなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
コマが置かれているマスの個数を整数で出力せよ。
入力例 1
3 5 #.... ..... .##..
出力例 1
3
- 上から 1 行目かつ左から 1 列目のマス
- 上から 3 行目かつ左から 2 列目のマス
- 上から 3 行目かつ左から 3 列目のマス
の計 3 つのマスにコマが置かれているため、3 を出力します。
入力例 2
1 10 ..........
出力例 2
0
どのマスにもコマは置かれていないため、0 を出力します。
入力例 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
出力例 3
16
Score : 100 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #
, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is .
, the square at the i-th row from the top and j-th column from the left is empty.
How many squares in the grid have pieces on them?
Constraints
- 1\leq H,W \leq 10
- H and W are integers.
- S_i is a string of length W consisting of
#
and.
.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the number of squares with pieces as an integer.
Sample Input 1
3 5 #.... ..... .##..
Sample Output 1
3
The following three squares have pieces on them:
- the square at the 1-st row from the top and 1-st column from the left;
- the square at the 3-rd row from the top and 2-nd column from the left;
- the square at the 3-rd row from the top and 3-rd column from the left.
Thus, 3 should be printed.
Sample Input 2
1 10 ..........
Sample Output 2
0
Since no square has a piece on it, 0 should be printed.
Sample Input 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
Sample Output 3
16
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 N と長さ N の数列 S=(S_1,\ldots,S_N) が与えられます。
長さ N の数列 A=(A_1,\ldots,A_N) であって、k=1,\ldots,N の全てについて以下の条件を満たすものを求めてください。
- A_1+A_2+\ldots+A_k = S_k
なお、このような数列 A は必ず存在し、一意に定まります。
制約
- 1 \leq N \leq 10
- -10^9\leq S_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \ldots S_N
出力
全ての条件を満たす数列 A=(A_1,\ldots,A_N) の各要素を、順に空白区切りで出力せよ。
入力例 1
3 3 4 8
出力例 1
3 1 4
- A_1=3=S_1
- A_1+A_2=3+1=4=S_2
- A_1+A_2+A_3=3+1+4=8=S_3
であり、たしかに全ての条件を満たしています。
入力例 2
10 314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482
出力例 2
314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381
Score : 200 points
Problem Statement
You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.
Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:
- A_1+A_2+\ldots+A_k = S_k.
Such a sequence A always exists and is unique.
Constraints
- 1 \leq N \leq 10
- -10^9\leq S_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N S_1 \ldots S_N
Output
Print the elements of a sequence A=(A_1,\ldots,A_N) that satisfies all the conditions in order, separated by spaces.
Sample Input 1
3 3 4 8
Sample Output 1
3 1 4
The sequence in the output actually satisfies all the conditions:
- A_1=3=S_1;
- A_1+A_2=3+1=4=S_2;
- A_1+A_2+A_3=3+1+4=8=S_3.
Sample Input 2
10 314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482
Sample Output 2
314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。
挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。
制約
- 1 \leq |S| \leq 5\times 10^5
- S は英小文字からなる
- T は S に英小文字を 1 つ挿入して作られた文字列である
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。
入力例 1
atcoder atcorder
出力例 1
5
T の先頭から 5 番目の文字 r
が挿入された文字です。
入力例 2
million milllion
出力例 2
5
T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。
入力例 3
vvwvw vvvwvw
出力例 3
3
Score : 300 points
Problem Statement
You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.
Find the position of the inserted character in T.
If there are multiple candidates, find any of them.
Constraints
- 1 \leq |S| \leq 5\times 10^5
- S consists of lowercase English letters.
- T is obtained by inserting a lowercase English letter into S.
Input
The input is given from Standard Input in the following format:
S T
Output
Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.
Sample Input 1
atcoder atcorder
Sample Output 1
5
The 5-th character from the beginning of T, r
, is inserted.
Sample Input 2
million milllion
Sample Output 2
5
One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.
Sample Input 3
vvwvw vvvwvw
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
2 以上の整数 K が与えられます。
正の整数 N であって、N! が K の倍数となるようなもののうち最小のものを求めてください。
ただし、N! は N の階乗を表し、問題の制約下で、そのような N が必ず存在することが証明できます。
制約
- 2\leq K\leq 10^{12}
- K は整数
入力
入力は以下の形式で標準入力から与えられる。
K
出力
N! が K の倍数となるような最小の正整数 N を出力せよ。
入力例 1
30
出力例 1
5
- 1!=1
- 2!=2\times 1=2
- 3!=3\times 2\times 1=6
- 4!=4\times 3\times 2\times 1=24
- 5!=5\times 4\times 3\times 2\times 1=120
より、N! が 30 の倍数となる最小の正整数 N は 5 です。よって、5 を出力します。
入力例 2
123456789011
出力例 2
123456789011
入力例 3
280
出力例 3
7
Score : 400 points
Problem Statement
You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.
Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.
Constraints
- 2\leq K\leq 10^{12}
- K is an integer.
Input
The input is given from Standard Input in the following format:
K
Output
Print the minimum positive integer N such that N! is a multiple of K.
Sample Input 1
30
Sample Output 1
5
- 1!=1
- 2!=2\times 1=2
- 3!=3\times 2\times 1=6
- 4!=4\times 3\times 2\times 1=24
- 5!=5\times 4\times 3\times 2\times 1=120
Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.
Sample Input 2
123456789011
Sample Output 2
123456789011
Sample Input 3
280
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
最初、体力が N であるモンスターが 1 体います。
高橋君はモンスターに対し、モンスターの体力が 1 以上残っている限り繰り返し攻撃を行います。
高橋君は 1 回の攻撃で、\frac{P}{100} の確率でモンスターの体力を 2 減らし、 1-\frac{P}{100} の確率でモンスターの体力を 1 減らします。
モンスターの体力が 0 以下になるまでに行う攻撃回数の期待値を \text{mod } 998244353 で出力してください(注記参照)。
注記
求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を出力してください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq P \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
高橋君の攻撃回数の期待値を \text{mod } 998244353 で出力せよ。
入力例 1
3 10
出力例 1
229596204
高橋君は 1 回の攻撃で、 \frac{10}{100}=\frac{1}{10} の確率でモンスターの体力を 2 減らし、 1-\frac{10}{100}=\frac{9}{10} の確率でモンスターの体力を 1 減らします。
- 最初、モンスターの体力は 3 です。
- 1 回目の攻撃の後、\frac{9}{10}の確率でモンスターの体力は 2、\frac{1}{10}の確率でモンスターの体力は 1 となります。
- 2 回目の攻撃の後、\frac{81}{100}の確率でモンスターの体力は 1、\frac{18}{100} の確率でモンスターの体力は 0、\frac{1}{100} の確率でモンスターの体力は -1 となります。 \frac{18}{100}+\frac{1}{100}=\frac{19}{100} の確率で体力は 0 以下となり、高橋君は 2 回で攻撃をやめます。
- 2 回目の攻撃の後で体力が 1 残っている場合、3 回目の攻撃の後でモンスターの体力は必ず 0 以下となり、高橋君は 3 回で攻撃をやめます。
よって、期待値は 2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100} となります。229596204 \times 100 \equiv 281\pmod{998244353} であるため、229596204 を出力します。
入力例 2
5 100
出力例 2
3
高橋君は 1 回の攻撃で、つねにモンスターの体力を 2 減らします。 2 回目の攻撃が終わった時点では体力が 5-2\times 2=1 残っているため、3 回目の攻撃を行う必要があります。
入力例 3
280 59
出力例 3
567484387
Score : 500 points
Problem Statement
There is a monster with initial stamina N.
Takahashi repeatedly attacks the monster while the monster's stamina remains 1 or greater.
An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{P}{100} and by 1 with probability 1-\frac{P}{100}.
Find the expected value, modulo 998244353 (see Notes), of the number of attacks before the monster's stamina becomes 0 or less.
Notes
We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can show that there exists a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print such R.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq P \leq 100
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P
Output
Find the expected value, modulo 998244353, of the number of Takahashi's attacks.
Sample Input 1
3 10
Sample Output 1
229596204
An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{10}{100}=\frac{1}{10} and by 1 with probability \frac{100-10}{100}=\frac{9}{10}.
- The monster's initial stamina is 3.
- After the first attack, the monster's stamina is 2 with probability \frac{9}{10} and 1 with probability \frac{1}{10}.
- After the second attack, the monster's stamina is 1 with probability \frac{81}{100}, 0 with probability \frac{18}{100}, and -1 with probability \frac{1}{100}. With probability \frac{18}{100}+\frac{1}{100}=\frac{19}{100}, the stamina becomes 0 or less, and Takahashi stops attacking after two attacks.
- If the stamina remains 1 after two attacks, the monster's stamina always becomes 0 or less by the third attack, so he stops attacking after three attacks.
Therefore, the expected value is 2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100}. Since 229596204 \times 100 \equiv 281\pmod{998244353}, print 229596204.
Sample Input 2
5 100
Sample Output 2
3
Takahashi's attack always reduces the monster's stamina by 2. After the second attack, the stamina remains 5-2\times 2=1, so the third one is required.
Sample Input 3
280 59
Sample Output 3
567484387
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1,\ldots,N の番号がついた N 個の街と、1,\ldots,M の番号がついた M 本の道路があります。
道路 i は街 A_i と B_i を結んでいます。道路を通行すると、所持している ポイント が次の通り増減します。
- 道路 i を使って、街 A_i から街 B_i に移動するときにはポイントが C_i 増加し、街 B_i から街 A_i に移動するときにはポイントが C_i 減少する。
所持しているポイントは負にもなりえます。
次の Q 個の質問に答えてください。
- 所持しているポイントが 0 である状態で街 X_i から移動を始めたとき、街 Y_i にいる状態で所持しているポイントの最大値を出力せよ。
ただし、街 X_i から街 Y_i に到達できないときはnan
、街 Y_i にいる状態で所持しているポイントをいくらでも増やせるときはinf
を代わりに出力せよ。
制約
- 2\leq N \leq 10^5
- 0\leq M \leq 10^5
- 1\leq Q \leq 10^5
- 1\leq A_i,B_i,X_i,Y_i \leq N
- 0\leq C_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M Q A_1 B_1 C_1 \vdots A_M B_M C_M X_1 Y_1 \vdots X_Q Y_Q
出力
問題文の指示通りに Q 行出力せよ。
i 行目には i 番目の質問に対する答えを出力せよ。
入力例 1
5 5 3 1 2 1 1 2 2 3 4 1 4 5 1 3 5 2 5 3 1 2 3 1
出力例 1
-2 inf nan
1 番目の質問では、道路 5 を使って街 5 から街 3 に移動すると、ポイントを -2 所持している状態で街 3 にいることができます。
これ以上ポイントを大きくすることはできないので答えは -2 になります。
2 番目の質問では、「道路 2 を使って街 1 から街 2 に移動し、道路 1 を使って街 2 から街 1 に移動する」 という行動を好きなだけ繰り返したあと、道路 2 を使って街 1 から街 2 に移動することで、 街 2 にいる状態で所持しているポイントをいくらでも増やすことができます。
3 番目の質問では、街 3 から移動を始めて街 1 へ到達することはできません。
入力例 2
2 1 1 1 1 1 1 1
出力例 2
inf
始点と終点が同じ街である道路や、始点と終点が同じ街である質問が含まれることもあります。
入力例 3
9 7 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9
出力例 3
inf nan nan inf -9
Score : 500 points
Problem Statement
There are N towns numbered 1,\ldots,N and M roads numbered 1,\ldots,M.
Road i connects towns A_i and B_i. When you use a road, your score changes as follows:
- when you move from town A_i to town B_i using road i, your score increases by C_i; when you move from town B_i to town A_i using road i, your score decreases by C_i.
Your score may become negative.
Answer the following Q questions.
- If you start traveling from town X_i with initial score 0, find the maximum possible score when you are at town Y_i.
Here, if you cannot get from town X_i to town Y_i, printnan
instead; if you can have as large a score as you want when you are at town Y_i, printinf
instead.
Constraints
- 2\leq N \leq 10^5
- 0\leq M \leq 10^5
- 1\leq Q \leq 10^5
- 1\leq A_i,B_i,X_i,Y_i \leq N
- 0\leq C_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M Q A_1 B_1 C_1 \vdots A_M B_M C_M X_1 Y_1 \vdots X_Q Y_Q
Output
Print Q lines as specified in the Problem Statement.
The i-th line should contain the answer to the i-th question.
Sample Input 1
5 5 3 1 2 1 1 2 2 3 4 1 4 5 1 3 5 2 5 3 1 2 3 1
Sample Output 1
-2 inf nan
For the first question, if you use road 5 to move from town 5 to town 3, you can have a score -2 when you are at town 3.
Since you cannot make the score larger, the answer is -2.
For the second question, you can have as large a score as you want when you are at town 2 if you travel as follows: repeatedly "use road 2 to move from town 1 to town 2 and then use road 1 to move from town 2 to town 1" as many times as you want, and finally use road 2 to move from town 1 to town 2.
For the third question, you cannot get from town 3 to town 1.
Sample Input 2
2 1 1 1 1 1 1 1
Sample Output 2
inf
The endpoints of a road may be the same, and so may the endpoints given in a question.
Sample Input 3
9 7 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9
Sample Output 3
inf nan nan inf -9
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下のような、無限に広い六角形のグリッドがあります。
六角形のマスは 2 つの整数 i,j を用いて (i,j) と表されます。
マス (i,j) は以下の 6 つのマスと辺で隣接しています。
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
2 つのマス X,Y の距離を、辺で隣接しているマスをたどってマス X からマス Y まで移動するときの、移動回数の最小値と定めます。
例えばマス (0,0) とマス (1,1) の距離は 1、マス (2,1) とマス (-1,-1) の距離は 3 です。
N 個のマス (X_1,Y_1),\ldots,(X_N,Y_N) が与えられます。
この N マスの中から 1 つ以上のマスを選ぶ方法のうち、選んだマスのうちどの 2 マスの距離も D 以下になるようなものは何通りありますか?
998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 300
- -10^9\leq X_i,Y_i \leq 10^9
- 1\leq D \leq 10^{10}
- (X_i,Y_i) は相異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N D X_1 Y_1 \vdots X_N Y_N
出力
答えを出力せよ。
入力例 1
3 1 0 0 0 1 1 0
出力例 1
5
選ぶマスの集合として考えられるのは \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\} の 5 通りです。
入力例 2
9 1 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
出力例 2
33
入力例 3
5 10000000000 314159265 358979323 846264338 -327950288 -419716939 937510582 -97494459 -230781640 628620899 862803482
出力例 3
31
Score : 600 points
Problem Statement
We have an infinite hexagonal grid shown below.
A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
Let us define the distance between two cells X and Y by the minimum number of moves required to travel from cell X to cell Y by repeatedly moving to an adjacent cell.
For example, the distance between cells (0,0) and (1,1) is 1, and the distance between cells (2,1) and (-1,-1) is 3.
You are given N cells (X_1,Y_1),\ldots,(X_N,Y_N).
How many ways are there to choose one or more from these N cells so that the distance between any two of the chosen cells is at most D?
Find the count modulo 998244353.
Constraints
- 1 \leq N \leq 300
- -10^9\leq X_i,Y_i \leq 10^9
- 1\leq D \leq 10^{10}
- (X_i,Y_i) are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N D X_1 Y_1 \vdots X_N Y_N
Output
Print the answer.
Sample Input 1
3 1 0 0 0 1 1 0
Sample Output 1
5
There are five possible sets of the chosen cells: \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}, and \{(0,0),(1,0)\}.
Sample Input 2
9 1 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
Sample Output 2
33
Sample Input 3
5 10000000000 314159265 358979323 846264338 -327950288 -419716939 937510582 -97494459 -230781640 628620899 862803482
Sample Output 3
31
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の文字列 S_1,S_2,\ldots, S_N が与えられます。
M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2} とおきます。
また、文字列 S と整数 L, R に対し、S[L, R] で S の L 文字目から R 文字目までの文字からなる部分文字列を表します。
整数の三つ組からなる長さ M の列 ((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M)) は以下の条件をみたします:
- M 個の要素は相異なる。
- すべての 1 \leq i \leq M に対して、1 \leq K_i \leq N かつ 1 \leq L_i \leq R_i \leq |S_{K_i}| である。
- すべての 1 \leq i \leq j \leq M に対して、辞書順で S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j] である。
1 以上 M 以下の整数 Q 個 x_1,x_2,\ldots, x_Q が与えられます。各 1 \leq i \leq Q に対して、(K_{x_i}, L_{x_i}, R_{x_i}) としてあり得るものを 1 つずつ求めてください。なお、条件をみたす三つ組の列が必ず 1 つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる x_i の間で、条件をみたす三つ組の列が共通のものである必要もありません。
辞書順とは
2 つの文字列 S, T が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で S \leq T であると言います。- |S| \leq |T| かつ S = T[1, |S|] である。
- ある 1\leq k\leq \min(|S|, |T|) が存在し、1\leq i\leq k-1 について、S と T の i 文字目は等しく、S の k 文字目は T の k 文字目よりアルファベット順で真に小さい。
制約
- 1 \leq N \leq 10^5
- 1 \leq \lvert S_i\rvert \leq 10^5
- \displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5
- 1 \leq Q \leq 2\times 10^5
- 1 \leq x_1<x_2<\cdots<x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}
- N,Q,x_1,x_2,\ldots,x_Q は整数
- S_i は英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N Q x_1 x_2 \ldots x_Q
出力
Q 行出力せよ。i 行目には、条件をみたす (K_{x_i}, L_{x_i}, R_{x_i}) としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。
入力例 1
2 abab cab 2 5 14
出力例 1
1 3 4 2 1 1
M=16 であり、条件をみたす三つ組の列としては、
(1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3) が考えられます。
この順で並べた時の (K_i,L_i, R_i) に対応する S_{K_i}[L_i, R_i] の列は、(a
, a
, a
, ab
, ab
, ab
, aba
, abab
, b
, b
, b
, ba
, bab
, c
, ca
, cab
)となります。
なお、5 番目の要素 (1,3,4) を、4 番目や 6 番目の要素と入れ替えた列も条件をみたすため、 (K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3) も正解となります。
入力例 2
3 a a ba 2 1 2
出力例 2
1 1 1 1 1 1
M=5 であり、条件をみたす三つ組の列としては、
(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2) や (2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2)
が考えられます。
出力する (K_{x_i}, L_{x_i}, R_{x_i}) について、x_i 番目の要素が (K_{x_i}, L_{x_i}, R_{x_i}) であるような条件をみたす列は異なる i の間で共通のものである必要が ない、 すなわち、「任意の 1\leq i\leq Q について x_i 番目の要素が (K_{x_i}, L_{x_i}, R_{x_i}) である」 ような列は 必ずしも存在する必要がない ことに注意してください。
入力例 3
10 gxgpuamkx szhkbpphykin ezplvfja mopodotkrj rimlvumuar nexcfyce eurgvjyos dhvuyfvt nrdyluacvra ggwnpnzij 6 74 268 310 380 455 489
出力例 3
3 1 2 4 4 5 4 3 7 9 6 6 6 6 6 2 2 12
Score : 600 points
Problem Statement
You are given N strings S_1,S_2,\ldots, S_N.
Let M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}.
For a string S and integers L and R, let us denote by S[L, R] the substring consisting of the L-th through R-th characters of S.
A sequence of triples of integers ((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M)) of length M satisfies the following conditions:
- The M elements are pairwise distinct.
- For all 1 \leq i \leq M, it holds that 1 \leq K_i \leq N and 1 \leq L_i \leq R_i \leq |S_{K_i}|.
- For all 1 \leq i \leq j \leq M, it holds that S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j] in the lexicographical order.
You are given Q integers x_1,x_2,\ldots, x_Q between 1 and M, inclusive. For each 1 \leq i \leq Q, find a possible instance of (K_{x_i}, L_{x_i}, R_{x_i}). We can prove that there always exists a sequence of triples that satisfies the conditions. If multiple triples satisfy the conditions, print any of them. In addition, among different x_i's, the conforming sequence of triples does not have to be common.
What is the lexicographical order?
Two strings S and T are said to be S \leq T in the lexicographical order if and only if one of the following conditions is satisfied:- |S| \leq |T| and S = T[1, |S|].
- There exists 1\leq k\leq \min(|S|, |T|) such that the i-th characters of S and T are the same for all 1\leq i\leq k-1, and the k-th character of S is alphabetically strictly smaller than that of T.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq \lvert S_i\rvert \leq 10^5
- \displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5
- 1 \leq Q \leq 2\times 10^5
- 1 \leq x_1<x_2<\cdots<x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}
- N,Q,x_1,x_2,\ldots,x_Q are integers.
- S_i is a string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N Q x_1 x_2 \ldots x_Q
Output
Print Q lines. The i-th line should contain an instance of conforming (K_{x_i}, L_{x_i}, R_{x_i}), separated by spaces. If multiple triples satisfy the conditions, print any of them.
Sample Input 1
2 abab cab 2 5 14
Sample Output 1
1 3 4 2 1 1
We have M=16. One possible sequence of triples that satisfies the conditions is
((1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3)).
The corresponding sequence of S_{K_i}[L_i, R_i] for these (K_i,L_i, R_i) in this order is (a
, a
, a
, ab
, ab
, ab
, aba
, abab
, b
, b
, b
, ba
, bab
, c
, ca
, cab
).
Note that the sequence satisfies the conditions even if we swap the 5-th element (1,3,4) with the 4-th or 6-th one, so (K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3) will also be accepted.
Sample Input 2
3 a a ba 2 1 2
Sample Output 2
1 1 1 1 1 1
We have M=5. The sequence of triples that satisfies the conditions can be
(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2) or (2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2),
for example.
Note that, for (K_{x_i}, L_{x_i}, R_{x_i}) that you print, the conforming sequence whose x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) does not have to be common among different i; in other words, there does not necessarily have to exist a sequence whose "x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) for all 1\leq i\leq Q."
Sample Input 3
10 gxgpuamkx szhkbpphykin ezplvfja mopodotkrj rimlvumuar nexcfyce eurgvjyos dhvuyfvt nrdyluacvra ggwnpnzij 6 74 268 310 380 455 489
Sample Output 3
3 1 2 4 4 5 4 3 7 9 6 6 6 6 6 2 2 12