実行時間制限: 2 sec / メモリ制限: 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
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。
縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。
次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。
- j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
- i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。
次の条件を満たす非負整数の組 (s, t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。
- 縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。
ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。
制約
- 2 \leq H, W \leq 30
- A_{i,j},B_{i,j} は
#または. - H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
出力
条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。
入力例 1
4 3 ..# ... .#. ... #.. ... .#. ...
出力例 1
Yes
(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。
..# ... .#. ...
まず、縦方向のシフトを行います。A は次のようになります。
... .#. ... ..#
次に、再び縦方向のシフトを行います。A は次のようになります。
.#. ... ..# ...
最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。
#.. ... .#. ...
入力例 2
3 2 ## ## #. .. #. #.
出力例 2
No
どのように (s, t) を選んでも A と B を一致させることはできません。
入力例 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
出力例 3
Yes
入力例 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
出力例 4
Yes
Score : 200 points
Problem Statement
Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.
We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.
The following two operations are called a vertical shift and horizontal shift.
- For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
- For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.
Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.
- After applying a vertical shift s times and a horizontal shift t times, A is equal to B.
Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.
Constraints
- 2 \leq H, W \leq 30
- A_{i,j} is
#or., and so is B_{i,j}. - H and W are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
Output
Print Yes if there is a conforming integer pair (s, t); print No otherwise.
Sample Input 1
4 3 ..# ... .#. ... #.. ... .#. ...
Sample Output 1
Yes
By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.
..# ... .#. ...
We first apply a vertical shift to make A as follows.
... .#. ... ..#
Then we apply another vertical shift to make A as follows.
.#. ... ..# ...
Finally, we apply a horizontal shift to make A as follows, which equals B.
#.. ... .#. ...
Sample Input 2
3 2 ## ## #. .. #. #.
Sample Output 2
No
No choice of (s, t) makes A equal B.
Sample Input 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
Sample Output 3
Yes
Sample Input 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
xy 平面上に 1 から N までの番号が付いた N 個の点があります。
点 i は座標 (X_i,Y_i) にあり、相異なる 2 点は異なる位置に存在します。
この N 点から 3 点を選ぶとき、選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。
制約
- 入力は全て整数である
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
出力
答えを整数として出力せよ。
入力例 1
4 0 1 1 3 1 1 -1 -1
出力例 1
3
点を図示すると、以下のようになります。
三角形をなすような点の選び方は、 \{1,2,3\},\{1,3,4\},\{2,3,4\} の 3 つです。
入力例 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
出力例 2
1124
Score : 300 points
Problem Statement
In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.
Constraints
- All values in input are integers.
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
4 0 1 1 3 1 1 -1 -1
Sample Output 1
3
The figure below illustrates the points.
There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.
Sample Input 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
Sample Output 2
1124
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
座標平面上に 2\times1 の大きさのタイルが敷き詰められています。 タイルは、次の規則に従って敷き詰められています。
- 整数の組 (i,j) に対し、正方形 A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace は 1 つのタイルに含まれる。
- i+j が偶数のとき、A _ {i,j} と A _ {i + 1,j} は同じタイルに含まれる。
ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような 2 つの異なるタイルは存在しないとします。
原点の近くでは、タイルは以下のように敷き詰められています。
高橋君は、はじめ座標平面上の点 (S _ x+0.5,S _ y+0.5) にいます。
高橋君は、次の移動を好きなだけ繰り返します。
- 上下左右の方向と正の整数 n を選ぶ。その方向に n だけ進む。
高橋君が異なるタイルを通るたび、高橋君は通行料を 1 だけ支払います。
高橋君が点 (T _ x+0.5,T _ y+0.5) にたどり着くために支払わなければならない通行料の最小値を求めてください。
制約
- 0\leq S _ x\leq2\times10 ^ {16}
- 0\leq S _ y\leq2\times10 ^ {16}
- 0\leq T _ x\leq2\times10 ^ {16}
- 0\leq T _ y\leq2\times10 ^ {16}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
S _ x S _ y T _ x T _ y
出力
高橋君が支払わなければならない通行料の最小値を出力せよ。
入力例 1
5 0 2 5
出力例 1
5
例えば、以下のように移動することで支払う通行料を 5 にすることができます。
- 左に 1 進む。通行料を 0 支払う。
- 上に 1 進む。通行料を 1 支払う。
- 左に 1 進む。通行料を 0 支払う。
- 上に 3 進む。通行料を 3 支払う。
- 左に 1 進む。通行料を 0 支払う。
- 上に 1 進む。通行料を 1 支払う。
支払う通行料を 4 以下にすることはできないので、5 を出力してください。
入力例 2
3 1 4 1
出力例 2
0
通行料を支払わなくてよい場合もあります。
入力例 3
2552608206527595 5411232866732612 771856005518028 7206210729152763
出力例 3
1794977862420151
出力すべき値が 32\operatorname{bit} 整数の範囲に収まらない場合があることに注意してください。
Score : 350 points
Problem Statement
The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:
- For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
- When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.
Tiles include their boundaries, and no two different tiles share a positive area.
Near the origin, the tiles are laid out as follows:
Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.
He can repeat the following move as many times as he likes:
- Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.
Each time he enters a tile, he pays a toll of 1.
Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).
Constraints
- 0\leq S _ x\leq2\times10 ^ {16}
- 0\leq S _ y\leq2\times10 ^ {16}
- 0\leq T _ x\leq2\times10 ^ {16}
- 0\leq T _ y\leq2\times10 ^ {16}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
S _ x S _ y T _ x T _ y
Output
Print the minimum toll Takahashi must pay.
Sample Input 1
5 0 2 5
Sample Output 1
5
For example, Takahashi can pay a toll of 5 by moving as follows:
- Move left by 1. Pay a toll of 0.
- Move up by 1. Pay a toll of 1.
- Move left by 1. Pay a toll of 0.
- Move up by 3. Pay a toll of 3.
- Move left by 1. Pay a toll of 0.
- Move up by 1. Pay a toll of 1.
It is impossible to reduce the toll to 4 or less, so print 5.
Sample Input 2
3 1 4 1
Sample Output 2
0
There are cases where no toll needs to be paid.
Sample Input 3
2552608206527595 5411232866732612 771856005518028 7206210729152763
Sample Output 3
1794977862420151
Note that the value to be output may exceed the range of a 32-bit integer.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
長さ n の数列 S = (s_1, s_2, \dots, s_n) がすべての i (1 \leq i \leq n - 1) に対して s_i \leq s_{i+1} を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。
広義単調増加な長さ N の整数列 A = (a_1, a_2, \dots, a_N), B = (b_1, b_2, \dots, b_N) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C = (c_1, c_2, \dots, c_N) を考えます。
- すべての i (1 \leq i \leq N) に対して a_i \leq c_i \leq b_i が成り立つ。
整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 3000
- 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
- 整数列 A,B は広義単調増加である。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \dots a_N b_1 b_2 \dots b_N
出力
C としてあり得る数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 1 1 2 3
出力例 1
5
C としてあり得る数列は次の 5 個です。
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
数列 (2, 1) は広義単調増加でないため条件を満たさないことに注意してください。
入力例 2
3 2 2 2 2 2 2
出力例 2
1
C としてあり得る数列は次の 1 個です。
- (2, 2, 2)
入力例 3
10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100
出力例 3
978222082
個数を 998244353 で割ったあまりを求めることに注意してください。
Score : 400 points
Problem Statement
A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).
Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:
- a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).
Find the number, modulo 998244353, of sequences that can be C.
Constraints
- 1 \leq N \leq 3000
- 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
- The sequences A and B are non-decreasing.
- All values in input are integers.
Input
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
Print the number, modulo 998244353, of sequences that can be C.
Sample Input 1
2 1 1 2 3
Sample Output 1
5
There are five sequences that can be C, as follows.
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
Note that (2, 1) does not satisfy the condition since it is not non-decreasing.
Sample Input 2
3 2 2 2 2 2 2
Sample Output 2
1
There is one sequence that can be C, as follows.
- (2, 2, 2)
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100
Sample Output 3
978222082
Be sure to find the count modulo 998244353.