E - X drawing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

上下左右に広がる N\times N のマス目があり、最初全てのマスは白く塗られています。このマス目の上から i 行目、左から j 列目のマスを (i,j) で表します。

高橋君は 1 以上 N 以下の整数 A, B を持っており、次のような操作を行います。

  • \max(1-A,1-B)\leq k\leq \min(N-A,N-B) をみたす全ての整数 k について、(A+k,B+k) を黒く塗る。
  • \max(1-A,B-N)\leq k\leq \min(N-A,B-1) をみたす全ての整数 k について、(A+k,B-k) を黒く塗る。

この操作を行った後のマス目について、P\leq i\leq Q かつ R\leq j\leq S をみたす各マス (i,j) がそれぞれ何色で塗られているか求めてください。

制約

  • 1 \leq N \leq 10^{18}
  • 1 \leq A \leq N
  • 1 \leq B \leq N
  • 1 \leq P \leq Q \leq N
  • 1 \leq R \leq S \leq N
  • (Q-P+1)\times(S-R+1)\leq 3\times 10^5
  • 入力は全て整数である。

入力

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

N A B
P Q R S

出力

Q-P+1 行出力せよ。
各行は # と . のみからなる長さ S-R+1 の文字列であり、 i 行目の文字列の j 番目の文字が # であることは (P+i-1,R+j-1) が黒く塗られていることを、 . であることは (P+i-1,R+j-1) が白く塗られていることをさす。


入力例 1

5 3 2
1 5 1 5

出力例 1

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

1 つめの操作で (2,1), (3,2), (4,3), (5,4) の 4 マスが、 2 つめの操作で (4,1), (3,2), (2,3), (1,4) の 4 マスが黒く塗られます。
よって、P=1, Q=5, R=1, S=5 より、上のように出力します。


入力例 2

5 3 3
4 5 2 5

出力例 2

#.#.
...#

操作によって、 (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5) の 9 マスが 黒く塗られます。
P=4, Q=5, R=2, S=5 より、上のように出力します。


入力例 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

出力例 3

#.#
.#.
#.#

入力が 32 bit 整数型に収まらないことがあることに注意してください。

Score : 300 points

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

  • For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
  • For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

  • 1 \leq N \leq 10^{18}
  • 1 \leq A \leq N
  • 1 \leq B \leq N
  • 1 \leq P \leq Q \leq N
  • 1 \leq R \leq S \leq N
  • (Q-P+1)\times(S-R+1)\leq 3\times 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B
P Q R S

Output

Print Q-P+1 lines.
Each line should contain a string of length S-R+1 consisting of # and .. The j-th character of the string in the i-th line should be # to represent that (P+i-1, R+j-1) is painted black, and . to represent that (P+i-1, R+j-1) is white.


Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.


Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.


Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

F - Make Them Narrow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

長さ N の数列 A が与えられます。
A のうち丁度 K 要素を自由に選んで消し、残った要素を順序を保って連結した数列を B とします。
( B の最大値 ) - ( B の最小値 ) としてありうる最小値を求めてください。

制約

  • 入力は全て整数
  • 1 \le K < N \le 2 \times 10^5
  • 1 \le A_i \le 10^9

入力

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

N K
A_1 A_2 \dots A_N

出力

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


入力例 1

5 2
3 1 5 4 9

出力例 1

2

A=(3,1,5,4,9) から丁度 2 要素を自由に選んで消すことを考えます。

  • 例えば 2 要素目の 1 、 5 要素目の 9 を消すと、消した後の数列 B=(3,5,4) となります。
    • このとき B の最大値は 5 、最小値は 3 なので ( B の最大値 ) - ( B の最小値 ) =2 となり、これは達成可能な最小値です。

入力例 2

6 5
1 1 1 1 1 1

出力例 2

0

入力例 3

8 3
31 43 26 6 18 36 22 13

出力例 3

18

Score : 250 points

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

  • All inputs are integers.
  • 1 \le K < N \le 2 \times 10^5
  • 1 \le A_i \le 10^9

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer as an integer.


Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

  • For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
    • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18
G - Diagonal Separation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 行 N 列のグリッドがあります。高橋君は以下の条件を満たすように各マスを黒または白のいずれかに塗り分けたいと考えています。

  • すべての行について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その行の左から i 個のマスは黒、それ以外は白で塗られている。
  • すべての列について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その列の上から i 個のマスは黒、それ以外は白で塗られている。

M 個のマスがすでに塗られています。そのうち i 個目は上から X_i 行目、左から Y_i 列目のマスで、C_i が B のとき黒で、 W のとき白で塗られています。

高橋君はまだ塗られていない残りの N^2-M 個のマスの色をうまく決めることで条件を満たすことができるか判定してください。

制約

  • 1\leq N\leq 10^9
  • 1\leq M\leq \min(N^2,2\times 10^5)
  • 1\leq X_i,Y_i\leq N
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • C_i は B または W
  • 入力される数値はすべて整数

入力

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

N M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

出力

条件を満たすことができるとき Yes を、そうでないとき No を出力せよ。


入力例 1

4 3
4 1 B
3 2 W
1 3 B

出力例 1

Yes

例えば以下の図のように色を塗り分けると条件を満たすことができます。すでに塗られているマスを赤色の線で囲んでいます。


入力例 2

2 2
1 2 W
2 2 B

出力例 2

No

塗られていない残りの 2 つのマスをどのように塗っても,条件を満たすことはできません。


入力例 3

1 1
1 1 W

出力例 3

Yes

入力例 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

出力例 4

No

Score : 425 points

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

  • For every row, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
  • For every column, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

  • 1\leq N\leq 10^9
  • 1\leq M\leq \min(N^2,2\times 10^5)
  • 1\leq X_i,Y_i\leq N
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • C_i is B or W.
  • All input numbers are integers.

Input

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

N M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

Output

If it is possible to satisfy the conditions, print Yes; otherwise, print No.


Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.


Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.


Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No
H - Critical Hit

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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
I - Visible Buildings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

1 から N の番号がついた N 棟のビルが数直線上に建っています。
ビル i は座標 X_i にあり、高さは H_i です。ビルの高さ方向以外の大きさは無視できるものとします。

座標 x の高さ h の地点 P からビル i が見えるとは、ビル i 上のある点 Q であって、線分 PQ が他のビルと共有点を持たないものが存在することと定めます。

座標 0 から全てのビルを見ることができない高さの最大値を求めてください。ただし、高さは非負の値を取るとし、高さ 0 で全てのビルを見ることができる場合はかわりに -1 と答えてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq X_1 < \dots < X_N \leq 10^9
  • 1 \leq H_i \leq 10^9
  • 入力は全て整数である

入力

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

N
X_1 H_1
\vdots
X_N H_N

出力

座標 0、高さ 0 の地点から全てのビルを見ることができる場合は -1 と出力せよ。
そうでないとき、座標 0 から全てのビルを見ることができない高さの最大値を出力せよ。真の解との絶対誤差または相対誤差が 10^{-9} 以下のとき正解と判定される。


入力例 1

3
3 2
5 4
7 5

出力例 1

1.500000000000000000

座標 0 高さ 1.5 の位置ではビル 3 を見ることができません。高さが 1.5 より僅かでも高ければビル 3 を含む全てのビルを見ることができるため、答えは 1.5 です。

図


入力例 2

2
1 1
2 100

出力例 2

-1

-1.000 などの出力では不正解となることに注意してください。


入力例 3

3
1 1
2 2
3 3

出力例 3

0.000000000000000000

入力例 4

4
10 10
17 5
20 100
27 270

出力例 4

17.142857142857142350

Score : 525 points

Problem Statement

There are N buildings numbered 1 to N on a number line.
Building i is at coordinate X_i and has height H_i. The size in directions other than height is negligible.

From a point P with coordinate x and height h, building i is considered visible if there exists a point Q on building i such that the line segment PQ does not intersect with any other building.

Find the maximum height at coordinate 0 from which it is not possible to see all buildings. Height must be non-negative; if it is possible to see all buildings at height 0 at coordinate 0, report -1 instead.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq X_1 < \dots < X_N \leq 10^9
  • 1 \leq H_i \leq 10^9
  • All input values are integers.

Input

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

N
X_1 H_1
\vdots
X_N H_N

Output

If it is possible to see all buildings from coordinate 0 and height 0, print -1. Otherwise, print the maximum height at coordinate 0 from which it is not possible to see all buildings. Answers with an absolute or relative error of at most 10^{-9} from the true answer will be considered correct.


Sample Input 1

3
3 2
5 4
7 5

Sample Output 1

1.500000000000000000

From coordinate 0 and height 1.5, building 3 cannot be seen. If the height is even slightly greater than 1.5, all buildings including building 3 can be seen. Thus, the answer is 1.5.

Figure


Sample Input 2

2
1 1
2 100

Sample Output 2

-1

Note that -1.000 or similar outputs would be considered incorrect.


Sample Input 3

3
1 1
2 2
3 3

Sample Output 3

0.000000000000000000

Sample Input 4

4
10 10
17 5
20 100
27 270

Sample Output 4

17.142857142857142350