Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
すぬけ君は、犬を N 匹と猿を M 匹飼っています。すぬけ君は、この N+M 匹を一列に並べようと思っています。
文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。
このような並べ方は何通りあるでしょうか。犬と猿は 10^9+7 以上の数を理解できないので、並べ方の個数を 10^9+7 で割ったあまりを求めてください。 ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。
制約
- 1 ≦ N,M ≦ 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
並べ方の個数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
2 2
出力例 1
8
犬をそれぞれ A,B とし、猿をそれぞれ C,D とすると、ACBD,ADBC,BCAD,BDAC,CADB,CBDA,DACB,DBCA の 8 通りの並べ方があります。
入力例 2
3 2
出力例 2
12
入力例 3
1 8
出力例 3
0
入力例 4
100000 100000
出力例 4
530123477
Score : 300 points
Problem Statement
Snuke has N dogs and M monkeys. He wants them to line up in a row.
As a Japanese saying goes, these dogs and monkeys are on bad terms. ("ken'en no naka", literally "the relationship of dogs and monkeys", means a relationship of mutual hatred.) Snuke is trying to reconsile them, by arranging the animals so that there are neither two adjacent dogs nor two adjacent monkeys.
How many such arrangements there are? Find the count modulo 10^9+7 (since animals cannot understand numbers larger than that). Here, dogs and monkeys are both distinguishable. Also, two arrangements that result from reversing each other are distinguished.
Constraints
- 1 ≤ N,M ≤ 10^5
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of possible arrangements, modulo 10^9+7.
Sample Input 1
2 2
Sample Output 1
8
We will denote the dogs by A and B, and the monkeys by C and D. There are eight possible arrangements: ACBD, ADBC, BCAD, BDAC, CADB, CBDA, DACB and DBCA.
Sample Input 2
3 2
Sample Output 2
12
Sample Input 3
1 8
Sample Output 3
0
Sample Input 4
100000 100000
Sample Output 4
530123477
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
平面上に、N 個の街があります。i 個目の街は、座標 (x_i,y_i) にあります。同じ座標に、複数の街があるかもしれません。
座標 (a,b) にある街と座標 (c,d) にある街の間に道を造るのには、min(|a-c|,|b-d|) 円かかります。街と街の間以外に、道を造ることはできません。
任意の 2 つの街の間を、道を何本か通って行き来できるようにするためは、最低で何円必要でしょうか。
制約
- 2 ≦ N ≦ 10^5
- 0 ≦ x_i,y_i ≦ 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 : x_N y_N
出力
任意の 2 つの街の間を道を何本か通って行き来できるようにするためにかかるお金の最小値を出力せよ。
入力例 1
3 1 5 3 9 7 8
出力例 1
3
街 1 と 2 、街 2 と 3 の間に道を造ると、かかるお金は 2+1=3 円になります。
入力例 2
6 8 3 4 9 12 19 18 1 13 5 7 6
出力例 2
8
Score : 500 points
Problem Statement
There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.
You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.
Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?
Constraints
- 2 ≤ N ≤ 10^5
- 0 ≤ x_i,y_i ≤ 10^9
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 : x_N y_N
Output
Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.
Sample Input 1
3 1 5 3 9 7 8
Sample Output 1
3
Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.
Sample Input 2
6 8 3 4 9 12 19 18 1 13 5 7 6
Sample Output 2
8
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
すぬけ君は、パズルゲームで遊んでいます。 このパズルゲームでは、R × C の長方形の盤面に、1 から N までの整数が 2 つずつ書かれています。 整数 i が書かれている座標は、(x_{i,1},y_{i,1}) と (x_{i,2},y_{i,2}) です。
すぬけ君の目的は、1 から N までのすべての整数に対し、同じ整数の書かれている座標同士を曲線で結ぶことです。 このとき、曲線が長方形の外に出たり、互いに交わったりしてはいけません。
このようなことが可能かどうか判定してください。
制約
- 1 ≦ R,C ≦ 10^8
- 1 ≦ N ≦ 10^5
- 0 ≦ x_{i,1},x_{i,2} ≦ R(1 ≦ i ≦ N)
- 0 ≦ y_{i,1},y_{i,2} ≦ C(1 ≦ i ≦ N)
- 与えられるどの 2 点も異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
R C N
x_{1,1} y_{1,1} x_{1,2} y_{1,2}
:
x_{N,1} y_{N,1} x_{N,2} y_{N,2}
出力
すぬけ君が目的を達成できるなら YES を、そうでないなら NO を出力せよ。
入力例 1
4 2 3 0 1 3 1 1 1 4 1 2 0 2 2
出力例 1
YES
上図のように整数同士を結べば、目的を達成することができます。
入力例 2
2 2 4 0 0 2 2 2 0 0 1 0 2 1 2 1 1 2 1
出力例 2
NO
入力例 3
5 5 7 0 0 2 4 2 3 4 5 3 5 5 2 5 5 5 4 0 3 5 1 2 2 4 4 0 5 4 1
出力例 3
YES
入力例 4
1 1 2 0 0 1 1 1 0 0 1
出力例 4
NO
Score : 700 points
Problem Statement
Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions R × C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (x_{i,1},y_{i,1}) and (x_{i,2},y_{i,2}).
The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N. Here, the curves may not go outside the board or cross each other.
Determine whether this is possible.
Constraints
- 1 ≤ R,C ≤ 10^8
- 1 ≤ N ≤ 10^5
- 0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)
- 0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)
- All given points are distinct.
- All input values are integers.
Input
Input is given from Standard Input in the following format:
R C N
x_{1,1} y_{1,1} x_{1,2} y_{1,2}
:
x_{N,1} y_{N,1} x_{N,2} y_{N,2}
Output
Print YES if the objective is achievable; print NO otherwise.
Sample Input 1
4 2 3 0 1 3 1 1 1 4 1 2 0 2 2
Sample Output 1
YES
The above figure shows a possible solution.
Sample Input 2
2 2 4 0 0 2 2 2 0 0 1 0 2 1 2 1 1 2 1
Sample Output 2
NO
Sample Input 3
5 5 7 0 0 2 4 2 3 4 5 3 5 5 2 5 5 5 4 0 3 5 1 2 2 4 4 0 5 4 1
Sample Output 3
YES
Sample Input 4
1 1 2 0 0 1 1 1 0 0 1
Sample Output 4
NO
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
椅子が M 個数直線上に並んでおり、i 番目の椅子 (1 ≦ i ≦ M) は座標 i にあります。
高橋君が N 人います。高橋君たちはゲームのやりすぎで全員腰を痛めたため、どこかの椅子に座る必要があります。 各々の高橋君たちが座る椅子にはこだわりがあって、i 人目の高橋君は座標 L_i 以下、もしくは座標 R_i 以上の椅子に座りたいです。当然ながら、同じ椅子には 1 人しか座れません。
このままでは、高橋君たち全員を椅子に座らせることができないかもしれません。 高橋君たちの健康管理に気を遣っている青木君は、椅子をできるだけ少ない数追加することで、 高橋君たち全員のこだわりを満たすように高橋君たちを椅子に座らせることができるようにしたいです。
椅子は、任意の実数座標に追加できます。追加する必要のある椅子の最小の個数を求めてください。
制約
- 1 ≦ N,M ≦ 2 × 10^5
- 0 ≦ L_i < R_i ≦ M + 1(1 ≦ i ≦ N)
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M L_1 R_1 : L_N R_N
出力
追加する必要のある椅子の最小の個数を出力せよ。
入力例 1
4 4 0 3 2 3 1 3 3 4
出力例 1
0
4 人の高橋君を順に座標 3,2,1,4 にある椅子に座らせることができるため、椅子を追加する必要はありません。
入力例 2
7 6 0 7 1 5 3 6 2 7 1 6 2 6 3 7
出力例 2
2
座標 0 と 2.5 に椅子を追加すれば、7 人の高橋君を順に座標 0,5,3,2,6,1,2.5 に座らせることができます。
入力例 3
3 1 1 2 1 2 1 2
出力例 3
2
入力例 4
6 6 1 6 1 6 1 5 1 5 2 6 2 6
出力例 4
2
Score : 1000 points
Problem Statement
There are M chairs arranged in a line. The coordinate of the i-th chair (1 ≤ i ≤ M) is i.
N people of the Takahashi clan played too much games, and they are all suffering from backaches. They need to sit in chairs and rest, but they are particular about which chairs they sit in. Specifically, the i-th person wishes to sit in a chair whose coordinate is not greater than L_i, or not less than R_i. Naturally, only one person can sit in the same chair.
It may not be possible for all of them to sit in their favorite chairs, if nothing is done. Aoki, who cares for the health of the people of the Takahashi clan, decides to provide additional chairs so that all of them can sit in chairs at their favorite positions.
Additional chairs can be placed at arbitrary real coordinates. Find the minimum required number of additional chairs.
Constraints
- 1 ≤ N,M ≤ 2 × 10^5
- 0 ≤ L_i < R_i ≤ M + 1(1 ≤ i ≤ N)
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N M L_1 R_1 : L_N R_N
Output
Print the minimum required number of additional chairs.
Sample Input 1
4 4 0 3 2 3 1 3 3 4
Sample Output 1
0
The four people can sit in chairs at the coordinates 3, 2, 1 and 4, respectively, and no more chair is needed.
Sample Input 2
7 6 0 7 1 5 3 6 2 7 1 6 2 6 3 7
Sample Output 2
2
If we place additional chairs at the coordinates 0 and 2.5, the seven people can sit at coordinates 0, 5, 3, 2, 6, 1 and 2.5, respectively.
Sample Input 3
3 1 1 2 1 2 1 2
Sample Output 3
2
Sample Input 4
6 6 1 6 1 6 1 5 1 5 2 6 2 6
Sample Output 4
2