Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。
S の先頭から a 文字目と b 文字目を入れ替えて得られる文字列を出力してください。
制約
- S は英小文字からなる文字列
- S の長さ |S| は、 2 \leq |S| \leq 10 を満たす
- 1 \leq a < b \leq |S|
- a, b は整数
入力
入力は以下の形式で標準入力から与えられる。
S a b
出力
答えを出力せよ。
入力例 1
chokudai 3 5
出力例 1
chukodai
chokudai の 3 文字目 o と 5 文字目 u を入れ替えると chukodai となります。
入力例 2
aa 1 2
出力例 2
aa
この入力例では、S の 1 文字目と 2 文字目を入れ替えて得られる文字列は、元の S と同じになります。
入力例 3
aaaabbbb 1 8
出力例 3
baaabbba
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Swap the a-th and b-th characters from the beginning of S and print the resulting string.
Constraints
- S is a string consisting of lowercase English letters.
- The length of S, |S|, satisfies 2 \leq |S| \leq 10.
- 1 \leq a < b \leq |S|
- a and b are integers.
Input
Input is given from Standard Input in the following format:
S a b
Output
Print the answer.
Sample Input 1
chokudai 3 5
Sample Output 1
chukodai
After swapping the 3-rd character o and 5-th character u of chokudai, we have chukodai.
Sample Input 2
aa 1 2
Sample Output 2
aa
In this sample, after swapping the 1-st and 2-nd characters of S, we have the same string as S.
Sample Input 3
aaaabbbb 1 8
Sample Output 3
baaabbba
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
AtCoder 社は、オンラインショップでグッズを販売しています。
高橋君はそこで N 種類の商品を購入することにしました。
1 以上 N 以下の整数 i について、i 種類目の商品は 1 個 P_i 円で、高橋君は Q_i 個購入します。
また、高橋君は送料を支払う必要があります。
送料は購入する商品の合計金額が S 円以上なら 0 円、そうでないならば K 円です。
高橋君が支払う金額は購入する商品の合計金額と送料の和です。
高橋君が支払う金額を求めてください。
制約
- 1\leq N\leq 100
- 1\leq S\leq 10000
- 1\leq K\leq 10000
- 1\leq P_i\leq 10000
- 1\leq Q_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N S K P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
出力
高橋君がオンラインショッピングで支払う金額を出力せよ。
入力例 1
2 2000 500 1000 1 100 6
出力例 1
2100
高橋君は 1 個 1000 円の商品を 1 個と、 1 個 100 円の商品を 6 つ購入します。
よって、購入する商品の合計金額は 1000\times 1+100\times 6=1600 円となります。
このとき購入する商品の合計金額は 2000 円未満であるため、送料は 500 円となります。
よって、高橋君の支払う金額は 1600+500=2100 円となります。
入力例 2
3 2000 500 1000 1 100 6 5000 1
出力例 2
6600
購入する商品の合計金額は 1000\times 1+100\times 6+5000\times 1=6600 円となります。
このとき購入する商品の合計金額は 2000 円以上であるため、送料は 0 円となります。
よって、高橋君の支払う金額は 6600+0=6600 円となります。
入力例 3
2 2000 500 1000 1 1000 1
出力例 3
2000
1 個あたりの価格が同じ商品が複数存在することもあります。
Score : 100 points
Problem Statement
AtCoder Inc. sells merchandise through its online shop.
Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.
Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.
He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.
Constraints
- 1\leq N\leq 100
- 1\leq S\leq 10000
- 1\leq K\leq 10000
- 1\leq P_i\leq 10000
- 1\leq Q_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S K P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
Output
Print the amount Takahashi will pay for online shopping.
Sample Input 1
2 2000 500 1000 1 100 6
Sample Output 1
2100
Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.
Sample Input 2
3 2000 500 1000 1 100 6 5000 1
Sample Output 2
6600
The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.
Sample Input 3
2 2000 500 1000 1 1000 1
Sample Output 3
2000
There may be multiple products with the same price per item.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
実数 X が小数点以下第 3 位まで与えられます。
実数 X を以下の条件を満たすように出力してください。
- 小数点以下の部分について、末尾に
0を付けない - 末尾に過剰な小数点を付けない
制約
- 0 \le X < 100
- X は小数点以下第 3 位まで与えられる
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
1.012
出力例 1
1.012
1.012 はそのまま出力しても構いません。
入力例 2
12.340
出力例 2
12.34
12.340 を末尾に 0 を付けずに出力すると 12.34 となります。
入力例 3
99.900
出力例 3
99.9
99.900 を末尾に 0 を付けずに出力すると 99.9 となります。
入力例 4
0.000
出力例 4
0
0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。
Score : 150 points
Problem Statement
A real number X is given to the third decimal place.
Print the real number X under the following conditions.
- The decimal part must not have trailing
0s. - There must not be an unnecessary trailing decimal point.
Constraints
- 0 \le X < 100
- X is given to the third decimal place.
Input
The input is given from Standard Input in the following format:
X
Output
Output the answer.
Sample Input 1
1.012
Sample Output 1
1.012
1.012 can be printed as it is.
Sample Input 2
12.340
Sample Output 2
12.34
Printing 12.340 without the trailing 0 results in 12.34.
Sample Input 3
99.900
Sample Output 3
99.9
Printing 99.900 without the trailing 0s results in 99.9.
Sample Input 4
0.000
Sample Output 4
0
Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
座標平面上に N 枚の長方形のシートが張られています。
各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。
1 枚以上のシートによって覆われている領域 の面積を S とすると、
S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。
制約
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
出力
1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。
入力例 1
3 0 5 1 3 1 4 0 5 2 5 2 4
出力例 1
20
3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。
入力例 2
2 0 100 0 100 0 100 0 100
出力例 2
10000
異なるシートが同じ領域を覆っている事があることに注意してください。
入力例 3
3 0 1 0 1 0 3 0 5 5 10 0 10
出力例 3
65
Score : 200 points
Problem Statement
There are N rectangular sheets spread out on a coordinate plane.
Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.
Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.
Constraints
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
Output
Print the area S of the region covered by one or more sheets as an integer.
Sample Input 1
3 0 5 1 3 1 4 0 5 2 5 2 4
Sample Output 1
20
The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.
Sample Input 2
2 0 100 0 100 0 100 0 100
Sample Output 2
10000
Note that different sheets may cover the same region.
Sample Input 3
3 0 1 0 1 0 3 0 5 5 10 0 10
Sample Output 3
65
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から 頂点 A_i に伸びます。 ( i \neq A_i であることは制約より保証されます )
同一頂点を複数回含まない有向閉路をひとつ求めてください。
なお、この問題の制約下で答えが存在することが示せます。
注釈
この問題では、有向閉路とは以下の条件を全て満たす頂点の列 B=(B_1,B_2,\dots,B_M) であるとします。
- M \ge 2
- B_i から B_{i+1} に辺が伸びている。 ( 1 \le i \le M-1 )
- B_M から B_1 に辺が伸びている。
- i \neq j ならば B_i \neq B_j
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N
- A_i \neq i
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
以下の形式で出力せよ。
M B_1 B_2 \dots B_M
M は出力する有向閉路の頂点数であり、 B_i は有向閉路の i 番目の頂点である。
出力は以下の条件を満たす必要がある。
- 2 \le M
- B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
- B_{1} = A_{B_M}
- B_i \neq B_j ( i \neq j )
答えとして考えられるものが複数ある場合、どれを出力しても正解となる。
入力例 1
7 6 7 2 1 3 4 5
出力例 1
4 7 5 3 2
7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 は確かに有向閉路になっています。
この入力に対応するグラフは以下の通りです。

他の正解となる出力の例は以下の通りです。
4 2 7 5 3
3 4 1 6
グラフが連結であるとは限らないことに注意してください。
入力例 2
2 2 1
出力例 2
2 1 2
1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方存在するケースです。
この場合、 1 \rightarrow 2 \rightarrow 1 は確かに有向閉路になっています。
この入力に対応するグラフは以下の通りです。
図中 1 \leftrightarrow 2 で 1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方あることを表現しています。

入力例 3
8 3 7 4 7 3 3 8 2
出力例 3
3 2 7 8
この入力に対応するグラフは以下の通りです。

Score : 350 points
Problem Statement
There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.
Notes
The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:
- M \geq 2
- The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
- The edge from vertex B_M to vertex B_1 exists.
- If i \neq j, then B_i \neq B_j.
Constraints
- All input values are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N
- A_i \neq i
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print a solution in the following format:
M B_1 B_2 \dots B_M
M is the number of vertices, and B_i is the i-th vertex in the directed cycle.
The following conditions must be satisfied:
- 2 \le M
- B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
- B_{1} = A_{B_M}
- B_i \neq B_j ( i \neq j )
If multiple solutions exist, any of them will be accepted.
Sample Input 1
7 6 7 2 1 3 4 5
Sample Output 1
4 7 5 3 2
7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.
Here is the graph corresponding to this input:

Here are other acceptable outputs:
4 2 7 5 3
3 4 1 6
Note that the graph may not be connected.
Sample Input 2
2 2 1
Sample Output 2
2 1 2
This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.
Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3
8 3 7 4 7 3 3 8 2
Sample Output 3
3 2 7 8
Here is the graph corresponding to this input:

Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A の異なる 2 要素の和として表せる値の中に偶数が存在するか判定し、存在する場合その最大値を求めてください。
制約
- 2\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- A の要素は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の異なる 2 要素の和として表せる値の中に偶数が存在しない場合、-1 を出力せよ。
偶数が存在する場合、その最大値を出力せよ。
入力例 1
3 2 3 4
出力例 1
6
A の異なる 2 要素の和として表せる値は 5,6,7 です。この中に偶数は存在し、その最大値は 6 です。
入力例 2
2 1 0
出力例 2
-1
A の異なる 2 要素の和として表せる値は 1 です。この中に偶数は存在しないので、 -1 を出力してください。
Score : 300 points
Problem Statement
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.
Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.
Constraints
- 2\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- The elements of A are distinct.
- 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
Output
Print -1 if there is no even number represented as the sum of two different elements of A.
If such an even number exists, print the maximum such number.
Sample Input 1
3 2 3 4
Sample Output 1
6
The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.
Sample Input 2
2 1 0
Sample Output 2
-1
The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
すぬけ君は蛇を観察しており、どこからどこまでが頭・胴・尾なのかが気になっています。 すぬけ君は蛇を N 個のブロックに区切り、それぞれのブロックについて頭らしさ・胴らしさ・尾らしさを評価しました。 そして、らしさの合計が最大になる分け方を考えることにしました。
長さ N の整数列 A = (A_1, A_2, \ldots, A_N), B = (B_1, B_2, \ldots, B_N), C = (C_1, C_2, \ldots, C_N) が与えられます。
整数の組 (x, y) が 1 \leq x < y < N を満たすとき、\displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i の値として取り得る最大値を求めてください。
制約
- 3 \leq N \leq 3 \times 10^5
- 1 \leq A_i, B_i, C_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
5 1 4 2 4 3 2 3 4 2 2 3 2 4 4 3
出力例 1
16
(x, y) = (2, 3) とすると \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16 となります。
入力例 2
3 1 1 1 1 1 1 1 1 1
出力例 2
3
入力例 3
6 2 10 7 7 7 11 5 7 9 10 9 12 6 6 7 10 12 7
出力例 3
50
Score : 400 points
Problem Statement
Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.
You are given length-N integer sequences A = (A_1, A_2, \ldots, A_N), B = (B_1, B_2, \ldots, B_N), and C = (C_1, C_2, \ldots, C_N).
Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.
Constraints
- 3 \leq N \leq 3 \times 10^5
- 1 \leq A_i, B_i, C_i \leq 10^6
- 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 B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
Output
Output the answer.
Sample Input 1
5 1 4 2 4 3 2 3 4 2 2 3 2 4 4 3
Sample Output 1
16
With (x, y) = (2, 3), we have \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16.
Sample Input 2
3 1 1 1 1 1 1 1 1 1
Sample Output 2
3
Sample Input 3
6 2 10 7 7 7 11 5 7 9 10 9 12 6 6 7 10 12 7
Sample Output 3
50
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N の番号がついた N+1 個のマスがあります。 高橋君はマス 0 からスタートし、マス N を目指します。
この双六では、1 から M までの M 種類の目が等確率で出るルーレットを使います。 高橋君はルーレットを回して出た目の数だけ進みます。もし、マス N を超えて進むことになる場合、マス N を超えた分だけ引き返します。
例えば、 N=4 で高橋君がマス 3 にいるとき、ルーレットを回して出た目が 4 の場合は、マス 4 を 3+4-4=3 マス超えてしまいます。そのため、 3 マスだけマス 4 から引き返し、マス 1 に移動します。
高橋君がマス N に到達するとゴールとなり、双六を終了します。
高橋君がルーレットを K 回まで回す時、ゴールできる確率を \text{mod } 998244353 で求めてください。
確率 \text{mod } 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
2 2 1
出力例 1
499122177
1 回ルーレットを回してゴールできるのは、ルーレットで 2 が出るときです。よってゴールできる確率は \frac{1}{2} です。
このとき、2\times 499122177 \equiv 1 \pmod{998244353} が成り立つので、答えとして 499122177 を出力してください。
入力例 2
10 5 6
出力例 2
184124175
入力例 3
100 1 99
出力例 3
0
Score : 500 points
Problem Statement
Takahashi is playing sugoroku, a board game.
The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.
The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.
For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 4 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.
When Takahashi arrives at square N, he wins and the game ends.
Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.
How to print a probability modulo 998244353
It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction \frac{y}{x}, it is guaranteed that x is not divisible by 998244353.
Here, there is a unique integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353}. Print this z.
Constraints
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 2 1
Sample Output 1
499122177
Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is \frac{1}{2}.
We have 2\times 499122177 \equiv 1 \pmod{998244353}, so the answer to be printed is 499122177.
Sample Input 2
10 5 6
Sample Output 2
184124175
Sample Input 3
100 1 99
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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, printnaninstead; if you can have as large a score as you want when you are at town Y_i, printinfinstead.
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