AtCoder Beginner Contest 065

A - Expired?

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

高橋君は胃が強いので、賞味期限を X 日まで過ぎた食品を食べてもお腹を壊しません。賞味期限を X+1 日以上過ぎた食品を食べると、お腹を壊します。

また、賞味期限を過ぎずに食べると、おいしく感じます。そうでない場合、おいしく感じません。

高橋君は、賞味期限の A 日前に食品を買ってきて、買ってから B 日後に食べました。

高橋君が食品をおいしく感じた場合 delicious を、おいしくは感じなかったがお腹は壊さなかった場合 safe を、お腹を壊した場合 dangerous を出力するプログラムを作成してください。

制約

1 ≦ X,A,B ≦ 10^9

入力

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

X A B

出力

高橋君が食品をおいしく感じた場合 delicious を、おいしくは感じなかったがお腹は壊さなかった場合 safe を、お腹を壊した場合 dangerous を出力せよ。

入力例 1

4 3 6

出力例 1

safe

賞味期限を 3 日過ぎて食べるので、おいしくは感じませんが、お腹も壊しません。

入力例 2

6 5 1

出力例 2

delicious

賞味期限を過ぎていないので、おいしく感じます。

入力例 3

3 7 12

出力例 3

dangerous

賞味期限を 5 日過ぎて食べるので、お腹を壊します。

Score : 100 points

Problem Statement

Takahashi has a strong stomach. He never gets a stomachache from eating something whose "best-by" date is at most X days earlier. He gets a stomachache if the "best-by" date of the food is X+1 or more days earlier, though.

Other than that, he finds the food delicious if he eats it not later than the "best-by" date. Otherwise, he does not find it delicious.

Takahashi bought some food A days before the "best-by" date, and ate it B days after he bought it.

Write a program that outputs delicious if he found it delicious, safe if he did not found it delicious but did not get a stomachache either, and dangerous if he got a stomachache.

Constraints

1 ≤ X,A,B ≤ 10^9

Input

Input is given from Standard Input in the following format:

X A B

Output

Print delicious if Takahashi found the food delicious; print safe if he neither found it delicious nor got a stomachache; print dangerous if he got a stomachache.

Sample Input 1

4 3 6

Sample Output 1

safe

He ate the food three days after the "best-by" date. It was not delicious or harmful for him.

Sample Input 2

6 5 1

Sample Output 2

delicious

He ate the food by the "best-by" date. It was delicious for him.

Sample Input 3

3 7 12

Sample Output 3

dangerous

He ate the food five days after the "best-by" date. It was harmful for him.

B - Trained?

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。

AtCoder 社のトレーニング設備には N 個のボタンがついており、ちょうど 1 個のボタンが光っています。ボタンには、1 から N までの番号がついています。ボタン i が光っているときにそのボタンを押すと、ボタン i の明かりが消え、その後ボタン a_i が光ります。i=a_i であることもあります。光っていないボタンを押しても、何も起こりません。

最初、ボタン 1 が光っています。高橋君は、ボタン 2 が光っている状態で、トレーニングをやめたいと思っています。

そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

制約

2 ≦ N ≦ 10^5
1 ≦ a_i ≦ N

入力

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

N
a_1
a_2
:
a_N

出力

ボタン 2 を光らせることが不可能な場合、-1 を出力せよ。そうでない場合、ボタン 2 を光らせるために必要なボタンを押す回数の最小値を出力せよ。

入力例 1

出力例 1

ボタン 1,3 の順に押せばよいです。

入力例 2

出力例 2

-1

ボタン 1 を押すとボタン 3 、ボタン 3 を押すとボタン 1 が光るので、ボタン 2 が光ることはありません。

入力例 3

出力例 3

Score : 200 points

Problem Statement

Takahashi wants to gain muscle, and decides to work out at AtCoder Gym.

The exercise machine at the gym has N buttons, and exactly one of the buttons is lighten up. These buttons are numbered 1 through N. When Button i is lighten up and you press it, the light is turned off, and then Button a_i will be lighten up. It is possible that i=a_i. When Button i is not lighten up, nothing will happen by pressing it.

Initially, Button 1 is lighten up. Takahashi wants to quit pressing buttons when Button 2 is lighten up.

Determine whether this is possible. If the answer is positive, find the minimum number of times he needs to press buttons.

Constraints

2 ≤ N ≤ 10^5
1 ≤ a_i ≤ N

Input

Input is given from Standard Input in the following format:

N
a_1
a_2
:
a_N

Output

Print -1 if it is impossible to lighten up Button 2. Otherwise, print the minimum number of times we need to press buttons in order to lighten up Button 2.

Sample Input 1

Sample Output 1

Press Button 1, then Button 3.

Sample Input 2

Sample Output 2

-1

Pressing Button 1 lightens up Button 3, and vice versa, so Button 2 will never be lighten up.

Sample Input 3

Sample Output 3

C - Reconciled?

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

犬をそれぞれ A,B とし、猿をそれぞれ C,D とすると、ACBD,ADBC,BCAD,BDAC,CADB,CBDA,DACB,DBCA の 8 通りの並べ方があります。

入力例 2

3 2

出力例 2

入力例 3

1 8

出力例 3

入力例 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

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

Sample Input 3

1 8

Sample Output 3

Sample Input 4

100000 100000

Sample Output 4

530123477

D - Built?

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

出力例 1

街 1 と 2 、街 2 と 3 の間に道を造ると、かかるお金は 2+1=3 円になります。

入力例 2

出力例 2

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

Sample Output 1

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