Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君は野球ゲームを作っています。
高橋君はバッターの打率を指定された桁数の分だけ表示するプログラムを作ることにしました。
整数 A, B があります。ここで A, B は 1 \leq A \leq 10, 0 \leq B \leq A を満たします。
このとき、文字列 S を次のように定義します。
- \dfrac{B}{A} を小数点第 4 位で四捨五入した値を「整数部 1 桁」「
.」「小数部 3 桁」の順に末尾ゼロを省略せずに表記した文字列。
例えば A=7, B = 4 の場合は、\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots で、これを小数点第 4 位で四捨五入した値は 0.571 です。よって S は 0.571 になります。
A, B が入力として与えられるので S を出力してください。
制約
- 1 \leq A \leq 10
- 0 \leq B \leq A
- A, B は整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
S を問題文の指示に従った形式で出力せよ。問題文の指示と異なる形式で出力した場合は誤答となることに注意せよ。
入力例 1
7 4
出力例 1
0.571
問題文本文でも説明した通り、\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots で、これを小数点第 4 位で四捨五入した値は 0.571 です。よって S は 0.571 になります。
入力例 2
7 3
出力例 2
0.429
\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots で、これを小数点第 4 位で四捨五入した値は 0.429 です。(繰り上がりが発生するのに注意してください。)
よって S は 0.429 となります。
入力例 3
2 1
出力例 3
0.500
\dfrac{B}{A} = \dfrac{1}{2} = 0.5 で、これを小数点第 4 位で四捨五入した値も同様に 0.5 です。
よって S は 0.500 となります。小数部を 3 桁並べる必要があるのに注意してください。
入力例 4
10 10
出力例 4
1.000
入力例 5
1 0
出力例 5
0.000
Score : 100 points
Problem Statement
Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.
There are integers A and B, which satisfy 1 \leq A \leq 10 and 0 \leq B \leq A.
Let S be the string obtained as follows.
- Round off \dfrac{B}{A} to three decimal digits, then write the integer part (1 digit),
.(the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.
For example, if A=7 and B=4, then \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.
You are given A and B as the input and asked to print S.
Constraints
- 1 \leq A \leq 10
- 0 \leq B \leq A
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print S in the format specified in the Problem Statement. Note that answers in different formats will be considered wrong.
Sample Input 1
7 4
Sample Output 1
0.571
As explained in the Problem Statement, \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.
Sample Input 2
7 3
Sample Output 2
0.429
\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots rounded off to three decimal digits is 0.429. (Note that it got rounded up.)
Thus, S is 0.429.
Sample Input 3
2 1
Sample Output 3
0.500
\dfrac{B}{A} = \dfrac{1}{2} = 0.5 rounded off to three decimal digits is again 0.5.
Thus, S is 0.500. Note that it must have three decimal places.
Sample Input 4
10 10
Sample Output 4
1.000
Sample Input 5
1 0
Sample Output 5
0.000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。
1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。
- j 列目に置かれている箱の個数。言い換えると、C_{i,j} が
#であるような整数 i の個数。
X_1, X_2, \dots, X_W をすべて求めてください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W は整数
- C_{i, j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
出力
X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。
X_1 X_2 \dots X_W
入力例 1
3 4 #..# .#.# .#.#
出力例 1
1 2 0 3
1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。
入力例 2
3 7 ....... ....... .......
出力例 2
0 0 0 0 0 0 0
箱が置かれているマスが存在しない場合もあります。
入力例 3
8 3 .#. ### .#. .#. .## ..# ##. .##
出力例 3
2 7 4
入力例 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
出力例 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
Score : 200 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.
For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.
- X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is
#.
Find all of X_1, X_2, \dots, X_W.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H and W are integers.
- C_{i, j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
Output
Print X_1, X_2, \dots, X_W in the following format:
X_1 X_2 \dots X_W
Sample Input 1
3 4 #..# .#.# .#.#
Sample Output 1
1 2 0 3
In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).
Sample Input 2
3 7 ....... ....... .......
Sample Output 2
0 0 0 0 0 0 0
There may be no square that contains a box.
Sample Input 3
8 3 .#. ### .#. .#. .## ..# ##. .##
Sample Output 3
2 7 4
Sample Input 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
Sample Output 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
あなたはアメーバの観察記録をつけました。
最初 1 匹のアメーバがおり、番号は 1 です。
観察記録は時系列順に N 個あり、i 番目の観察記録は「番号 A_i のアメーバが分裂して消滅し、新たに 2 匹のアメーバが生まれ、それらにそれぞれ 2i,2i+1 と番号をつけた」というものです。
このとき、アメーバ A_i を アメーバ 2i,2i+1 の親と呼びます。
各 k=1,\ldots,2N+1 について、アメーバ k から何代親を遡るとアメーバ 1 になるか求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 観察記録は矛盾していない。すなわち
- 1\leq A_i \leq 2i-1
- A_i は相異なる整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
2N+1 行出力せよ。k 行目にはアメーバ k から何代親を遡るとアメーバ 1 になるかを出力せよ。
入力例 1
2 1 2
出力例 1
0 1 1 2 2
アメーバ 1 からアメーバ 2,3 が生まれ、アメーバ 2 からアメーバ 4,5 が生まれました。
- アメーバ 1 は 0 代遡るとアメーバ 1 になります。
- アメーバ 2 は 1 代遡るとアメーバ 1 になります。
- アメーバ 3 は 1 代遡るとアメーバ 1 になります。
- アメーバ 4 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。
- アメーバ 5 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。
入力例 2
4 1 3 5 2
出力例 2
0 1 1 2 2 3 3 2 2
Score : 300 points
Problem Statement
You observed amoebae and kept some records.
Initially, there was one amoeba, numbered 1.
You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.
For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?
Constraints
- 1 \leq N \leq 2\times 10^5
- The records are consistent. That is:
- 1\leq A_i \leq 2i-1.
- A_i are distinct integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print 2N+1 lines. The k-th line should contain the generation distance between amoeba 1 and amoeba k.
Sample Input 1
2 1 2
Sample Output 1
0 1 1 2 2
From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.
- Amoeba 1 is zero generations away from amoeba 1.
- Amoeba 2 is one generation away from amoeba 1.
- Amoeba 3 is one generation away from amoeba 1.
- Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
- Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.
Sample Input 2
4 1 3 5 2
Sample Output 2
0 1 1 2 2 3 3 2 2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の正整数列 A = (A_1, A_2, \dots, A_N) および整数 x, y が与えられます。
次の条件をすべて満たすように、xy 座標平面上に N+1 個の点 p_1, p_2, \dots, p_N, p_{N+1} を配置することができるか判定してください。(同じ座標に 2 個以上の点を配置してもよいです。)
- p_1 = (0, 0)
- p_2 = (A_1, 0)
- p_{N+1} = (x, y)
- 点 p_i と点 p_{i+1} の距離は A_i (1 \leq i \leq N)
- 線分 p_i p_{i+1} と線分 p_{i+1} p_{i+2} のなす角は 90 度 (1 \leq i \leq N - 1)
制約
- 2 \leq N \leq 10^3
- 1 \leq A_i \leq 10
- |x|, |y| \leq 10^4
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N x y A_1 A_2 \dots A_N
出力
問題文の条件をすべて満たすように p_1, p_2, \dots, p_N, p_{N+1} を配置することができる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 -1 1 2 1 3
出力例 1
Yes
xy 座標平面に p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 1), p_4 = (-1, 1) として点を配置したのが以下の図です。これは問題文の条件をすべて満たしています。
入力例 2
5 2 0 2 2 2 2 2
出力例 2
Yes
p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 2), p_4 = (0, 2), p_5 = (0, 0), p_6 = (2, 0) とすれば問題文の条件をすべて満たすことができます。同じ座標に複数の点を置いてもよいのに注意してください。
入力例 3
4 5 5 1 2 3 4
出力例 3
No
入力例 4
3 2 7 2 7 4
出力例 4
No
入力例 5
10 8 -7 6 10 4 1 5 9 8 6 5 1
出力例 5
Yes
Score : 400 points
Problem Statement
You are given a sequence A = (A_1, A_2, \dots, A_N) of length N consisting of positive integers, and integers x and y.
Determine whether it is possible to place N+1 points p_1, p_2, \dots, p_N, p_{N+1} in the xy-coordinate plane to satisfy all of the following conditions. (It is allowed to place two or more points at the same coordinates.)
- p_1 = (0, 0).
- p_2 = (A_1, 0).
- p_{N+1} = (x, y).
- The distance between the points p_i and p_{i+1} is A_i. (1 \leq i \leq N)
- The segments p_i p_{i+1} and p_{i+1} p_{i+2} form a 90 degree angle. (1 \leq i \leq N - 1)
Constraints
- 2 \leq N \leq 10^3
- 1 \leq A_i \leq 10
- |x|, |y| \leq 10^4
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N x y A_1 A_2 \dots A_N
Output
If it is possible to place p_1, p_2, \dots, p_N, p_{N+1} to satisfy all of the conditions in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 -1 1 2 1 3
Sample Output 1
Yes
The figure below shows a placement where p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 1), and p_4 = (-1, 1). All conditions in the Problem Statement are satisfied.
Sample Input 2
5 2 0 2 2 2 2 2
Sample Output 2
Yes
Letting p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 2), p_4 = (0, 2), p_5 = (0, 0), and p_6 = (2, 0) satisfies all the conditions. Note that multiple points may be placed at the same coordinates.
Sample Input 3
4 5 5 1 2 3 4
Sample Output 3
No
Sample Input 4
3 2 7 2 7 4
Sample Output 4
No
Sample Input 5
10 8 -7 6 10 4 1 5 9 8 6 5 1
Sample Output 5
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 次元平面上に N 個の街と M 個の宝箱があります。街 i は座標 (X_i,Y_i) に、宝箱 i は座標 (P_i,Q_i) にあります。
高橋君は原点を出発し、N 個の街全てを訪れたのち原点に戻る旅行をしようと考えています。
宝箱を訪れる必要はありませんが、宝箱の中にはそれぞれブースターが 1 つあり、ブースターを拾うごとに移動速度が 2 倍になります。
高橋君の最初の移動速度が単位時間あたり 1 であるとき、旅行にかかる時間の最小値を求めてください。
制約
- 1 \leq N \leq 12
- 0 \leq M \leq 5
- -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
- (0,0),(X_i,Y_i),(P_i,Q_i) は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 Y_1 \vdots X_N Y_N P_1 Q_1 \vdots P_M Q_M
出力
答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
2 1 1 1 0 1 1 0
出力例 1
2.5000000000
以下のように移動するのが最適解の一つです。
- 原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
- 宝箱 1 から街 1 までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
- 街 1 から街 2までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
- 街 2から原点までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
入力例 2
2 1 1 1 0 1 100 0
出力例 2
3.4142135624
以下のように移動するのが最適解の一つです。
- 原点 から街 1 までの距離 1.41\ldots を速さ 1 で移動する。時間が 1.41\ldots かかる
- 街 1 から街 2 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
- 街 2 から原点までの距離 1 を速さ 1 で移動する。時間が 1 かかる
入力例 3
1 2 4 4 1 0 0 1
出力例 3
4.3713203436
以下のように移動するのが最適解の一つです。
- 原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
- 宝箱 1 から宝箱 2 までの距離 1.41\ldots を速さ 2 で移動する。時間が 0.707\ldots かかる
- 宝箱 2 から街 1 までの距離 5 を速さ 4 で移動する。時間が 1.25 かかる
- 街 1 から原点までの距離 5.65\ldots を速さ 4 で移動する。時間が 1.41\ldots かかる
Score : 500 points
Problem Statement
In a two-dimensional plane, there are N towns and M chests. Town i is at the coordinates (X_i,Y_i), and chest i is at the coordinates (P_i,Q_i).
Takahashi will go on a trip where he starts at the origin, visits all N towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by 2.
Takahashi's initial moving speed is 1. Find the shortest time needed to complete the trip.
Constraints
- 1 \leq N \leq 12
- 0 \leq M \leq 5
- -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
- (0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 Y_1 \vdots X_N Y_N P_1 Q_1 \vdots P_M Q_M
Output
Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{-6}.
Sample Input 1
2 1 1 1 0 1 1 0
Sample Output 1
2.5000000000
Here is one optimal way to complete the trip.
- Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
- Go the distance 1 from chest 1 to town 1 at a speed of 2, taking a time of 0.5.
- Go the distance 1 from town 1 to town 2 at a speed of 2, taking a time of 0.5.
- Go the distance 1 from town 2 to the origin at a speed of 2, taking a time of 0.5.
Sample Input 2
2 1 1 1 0 1 100 0
Sample Output 2
3.4142135624
Here is one optimal way to complete the trip.
- Go the distance 1.41\ldots from the origin to town 1 at a speed of 1, taking a time of 1.41\ldots.
- Go the distance 1 from town 1 to town 2 at a speed of 1, taking a time of 1.
- Go the distance 1 from town 2 to the origin at a speed of 1, taking a time of 1.
Sample Input 3
1 2 4 4 1 0 0 1
Sample Output 3
4.3713203436
Here is one optimal way to complete the trip.
- Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
- Go the distance 1.41\ldots from chest 1 to chest 2 at a speed of 2, taking a time of 0.707\ldots.
- Go the distance 5 from chest 2 to town 1 at a speed of 4, taking a time of 1.25.
- Go the distance 5.65\ldots from town 1 to the origin at a speed of 4, taking a time of 1.41\ldots.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
数直線上を N 匹の魚が泳いでいます。
魚 i の重さは W_i であり、時刻 0 に座標 X_i にいて、正方向に速さ V_i で移動しています。
高橋君は 0 以上の実数 t を自由に選び、時刻 t に一度だけ以下の行動を行います。
行動：実数 x を自由に選ぶ。現在の座標が x 以上 x+A 以下である魚を全て捕まえる。
捕まえることができる魚の重さの合計の最大値を求めてください。
制約
- 1 \leq N \leq 2000
- 1 \leq A \leq 10^4
- 1 \leq W_i\leq 10^4
- 0 \leq X_i\leq 10^4
- 1 \leq V_i\leq 10^4
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A W_1 X_1 V_1 W_2 X_2 V_2 \vdots W_N X_N V_N
出力
答えを出力せよ。
入力例 1
3 10 100 0 100 1 10 30 10 20 10
出力例 1
111
時刻 0.25 に魚 1,2,3 はそれぞれ座標 25, 17.5, 22.5 にいます。よって、この時刻に x=16 として行動すると全ての魚を捕まえることができます。
入力例 2
3 10 100 100 100 1 10 30 10 20 10
出力例 2
100
時刻 0 に x=100 として行動するのが最適解の一つです。
入力例 3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
出力例 3
1110
時刻 1 に x=100 として行動するのが最適解の一つです。
Score : 500 points
Problem Statement
On a number line, there are N fish swimming.
Fish i, which has a weight of W_i, is at the coordinate X_i at time 0 and moves at a speed of V_i in the positive direction.
Takahashi will choose an arbitrary real number t greater than or equal to 0 and do the following action at time t just once.
Action: Choose an arbitrary real number x. Catch all fish whose coordinates are between x and x+A, inclusive.
Find the maximum total weight of fish that he can catch.
Constraints
- 1 \leq N \leq 2000
- 1 \leq A \leq 10^4
- 1 \leq W_i\leq 10^4
- 0 \leq X_i\leq 10^4
- 1 \leq V_i\leq 10^4
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A W_1 X_1 V_1 W_2 X_2 V_2 \vdots W_N X_N V_N
Output
Print the answer.
Sample Input 1
3 10 100 0 100 1 10 30 10 20 10
Sample Output 1
111
At time 0.25, fish 1, 2, and 3 are at the coordinates 25, 17.5, and 22.5, respectively. Thus, the action done at this time with x=16 catches all the fish.
Sample Input 2
3 10 100 100 100 1 10 30 10 20 10
Sample Output 2
100
One optimal choice is to do the action at time 0 with x=100.
Sample Input 3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
Sample Output 3
1110
One optimal choice is to do the action at time 1 with x=100.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H 行、横 W 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。
マス (i,j) は S_{i,j}= # のとき障害物が置かれており、S_{i,j}= . のとき何も置かれていません。
高橋君はグリッド内にいくつか監視カメラを設置しようとしています。
監視カメラは障害物のないマスに上下左右の 4 方向のいずれかの向きで置くことができます。
1 つのマスに複数台の監視カメラを設置することも可能です。
各監視カメラは、監視カメラの置かれたマス、及び、監視カメラの向いている向きにある直線上のマスを、障害物に遮られない範囲で監視することができます。
障害物の置かれていない全てのマスを監視するためには、最小でいくつの監視カメラを設置する必要がありますか？
制約
- 1 \leq H,W \leq 300
- S_{i,j} は
.または#である
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
3 3 ... .#. ...
出力例 1
4
例えば、マス (1,1) に右向きと下向き、マス (3,3) に上向きと左向きの合計 4 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。
入力例 2
3 5 ...## .#... ...#.
出力例 2
5
例えば、マス (1,1) に右向きと下向き、マス (3,3) に左向き、マス (2,5) に左向きと下向きの合計 5 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。
マス (2,5) に左向きに設置したカメラは、マス (2,2) の障害物に遮られるため、マス (2,1) を監視できないことに注意してください。
入力例 3
14 107 ........................................................................................................... ........................................................................................................... ..#########..###....###########..###.......###...###########..####.......###...###########...###########... ..########..###....###########....###.....###...###########...#####......###..###########...###########.... ..#######..###.....###.............###...###....###...........######.....###..###...........###............ ..######..###......###..............###.###.....###...........###.###....###..###...........###............ ..#####..###.......############......#####......############..###..###...###..###...........############... ..####....###......############.......###.......############..###...###..###..###...........############... ..###......###.....###................###.......###...........###....###.###..###...........###............ ..##........###....###................###.......###...........###.....######..###...........###............ ..#..........###...############.......###.......############..###......#####..############..############... ..............###...###########.......###........###########..###.......####...###########...###########... ........................................................................................................... ...........................................................................................................
出力例 3
91
Score : 600 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Square (i, j) is occupied by an obstacle if S_{i,j}= #, and is empty if S_{i,j}= ..
Takahashi will install some surveillance cameras in the grid.
A surveillance camera can be placed at a square without an obstacle, in one of the four directions: up, down, left, or right.
Multiple surveillance cameras may be placed at the same square.
Each surveillance camera monitors the square it is placed at, and the squares in the direction it is placed in, as far as there is no obstacle in between.
At least how many surveillance cameras are needed to monitor all squares without an obstacle?
Constraints
- 1 \leq H,W \leq 300
- S_{i,j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
Output
Print the answer.
Sample Input 1
3 3 ... .#. ...
Sample Output 1
4
For example, if we install two surveillance cameras at square (1, 1) facing right and down, and another two at square (3, 3) facing up and left, all squares without an obstacle will be monitored.
Sample Input 2
3 5 ...## .#... ...#.
Sample Output 2
5
For example, if we install two surveillance cameras at square (1, 1) facing right and down, another at square (3, 3) facing left, and another two at square (2, 5) facing left and down, all squares without an obstacle will be monitored.
Note that the camera at square (2, 5) facing left cannot monitor square (2, 1), since there is an obstacle in between at square (2, 2).
Sample Input 3
14 107 ........................................................................................................... ........................................................................................................... ..#########..###....###########..###.......###...###########..####.......###...###########...###########... ..########..###....###########....###.....###...###########...#####......###..###########...###########.... ..#######..###.....###.............###...###....###...........######.....###..###...........###............ ..######..###......###..............###.###.....###...........###.###....###..###...........###............ ..#####..###.......############......#####......############..###..###...###..###...........############... ..####....###......############.......###.......############..###...###..###..###...........############... ..###......###.....###................###.......###...........###....###.###..###...........###............ ..##........###....###................###.......###...........###.....######..###...........###............ ..#..........###...############.......###.......############..###......#####..############..############... ..............###...###########.......###........###########..###.......####...###########...###########... ........................................................................................................... ...........................................................................................................
Sample Output 3
91
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ M の非負整数列 B=(B_1,B_2,\dots,B_M), C=(C_1,C_2,\dots,C_M) に対して、B と C の XOR 和 S(B,C) を長さ M の非負整数列 (B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M}) として定義します。ここで \oplus はビットごとの排他的論理和を意味します。
例えば B = (1, 2, 3), C = (3, 5, 7) のとき S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4) です。
非負整数列 A = (A_1, A_2, \dots, A_N) が与えられます。A の i 番目から j 番目までの要素からなる A の連続部分列を A(i, j) と表します。
以下に説明するクエリが Q 個与えられるので全て処理してください。
各クエリでは 1 以上 N 以下の整数 a, b, c, d, e, f が与えられます。これらの整数は a \leq b, c \leq d, e \leq f, b-a=d-c を満たします。このとき、S(A(a, b), A(c, d)) が A(e, f) よりも辞書順で真に小さければ Yes を、そうでなければ No を出力してください。
ビットごとの排他的論理和とは？
整数 A, B のビットごとの排他的論理和 A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
数列の辞書順とは？
数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
- |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
- ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
制約
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^{18}
- 1 \leq Q \leq 5 \times 10^4
- 1 \leq a \leq b \leq N
- 1 \leq c \leq d \leq N
- 1 \leq e \leq f \leq N
- b - a = d - c
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで \text{query}_i は i 番目のクエリを意味する。
N Q
A_1 A_2 \dots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
クエリは次の形式で与えられる。
a b c d e f
出力
Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。
入力例 1
4 5 1 2 3 1 1 3 2 4 1 4 1 2 2 3 3 4 1 1 2 2 3 4 1 2 2 3 3 3 1 4 1 4 1 1
出力例 1
No No Yes No Yes
1 番目のクエリについて、A(1, 3) = (1, 2, 3), A(2, 4) = (2, 3, 1) なので S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2) です。これは A(1, 4) = (1, 2, 3, 1) よりも辞書順で大きいので答えは No になります。
2 番目のクエリについて、S(A(1,2),A(2,3)) = (3, 1), A(3,4) = (3, 1) であり両者は等しく、答えは No になります。
入力例 2
10 10 725560240 9175925348 9627229768 7408031479 623321125 4845892509 8712345300 1026746010 4844359340 2169008582 5 6 5 6 2 6 5 6 1 2 1 1 3 8 3 8 1 6 5 10 1 6 1 7 3 4 1 2 5 5 7 10 4 7 2 3 3 6 1 4 7 9 4 5 3 4 8 9 2 6 1 5 5 8 4 8 1 5 1 9
出力例 2
Yes Yes Yes Yes No No No No No No
Score : 600 points
Problem Statement
For sequences B=(B_1,B_2,\dots,B_M) and C=(C_1,C_2,\dots,C_M), each of length M, consisting of non-negative integers, let the XOR sum S(B,C) of B and C be defined as the sequence (B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M}) of length M consisting of non-negative integers. Here, \oplus represents bitwise XOR.
For instance, if B = (1, 2, 3) and C = (3, 5, 7), we have S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4).
You are given a sequence A = (A_1, A_2, \dots, A_N) of non-negative integers. Let A(i, j) denote the contiguous subsequence composed of the i-th through j-th elements of A.
You will be given Q queries explained below and asked to process all of them.
Each query gives you integers a, b, c, d, e, and f, each between 1 and N, inclusive. These integers satisfy a \leq b, c \leq d, e \leq f, and b-a=d-c. If S(A(a, b), A(c, d)) is strictly lexicographically smaller than A(e, f), print Yes; otherwise, print No.
What is bitwise XOR?
The exclusive logical sum a \oplus b of two integers a and b is defined as follows.- The 2^k's place (k \geq 0) in the binary notation of a \oplus b is 1 if exactly one of the 2^k's places in the binary notation of a and b is 1; otherwise, it is 0.
What is lexicographical order on sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is said to be strictly lexicographically smaller than a sequence B = (B_1, \ldots, B_{|B|}) if and only if 1. or 2. below is satisfied.
- |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- There is an integer 1\leq i\leq \min\{|A|,|B|\} that satisfies both of the following.
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^{18}
- 1 \leq Q \leq 5 \times 10^4
- 1 \leq a \leq b \leq N
- 1 \leq c \leq d \leq N
- 1 \leq e \leq f \leq N
- b - a = d - c
- All values in the input are integers.
Input
The input is given from Standard Input in the following format, where \text{query}_i represents the i-th query:
N Q
A_1 A_2 \dots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
The queries are in the following format:
a b c d e f
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
4 5 1 2 3 1 1 3 2 4 1 4 1 2 2 3 3 4 1 1 2 2 3 4 1 2 2 3 3 3 1 4 1 4 1 1
Sample Output 1
No No Yes No Yes
For the first query, we have A(1, 3) = (1, 2, 3) and A(2, 4) = (2, 3, 1), so S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2). This is lexicographcially larger than A(1, 4) = (1, 2, 3, 1), so the answer is No.
For the second query, we have S(A(1,2),A(2,3)) = (3, 1) and A(3,4) = (3, 1), which are equal, so the answer is No.
Sample Input 2
10 10 725560240 9175925348 9627229768 7408031479 623321125 4845892509 8712345300 1026746010 4844359340 2169008582 5 6 5 6 2 6 5 6 1 2 1 1 3 8 3 8 1 6 5 10 1 6 1 7 3 4 1 2 5 5 7 10 4 7 2 3 3 6 1 4 7 9 4 5 3 4 8 9 2 6 1 5 5 8 4 8 1 5 1 9
Sample Output 2
Yes Yes Yes Yes No No No No No No