• 2018-10-06
• 16
• 0

# A. Cashier

## Description:

Vasya has recently got a job as a cashier at a local store. His day at work is L minutes long. Vasya has already memorized n regular customers, the i-th of which comes after t_{i} minutes after the beginning of the day, and his service consumes l_{i} minutes. It is guaranteed that no customer will arrive while Vasya is servicing another customer.
Vasya is a bit lazy, so he likes taking smoke breaks for a minutes each. Those breaks may go one after another, but Vasya must be present at work during all the time periods he must serve regular customers, otherwise one of them may alert his boss. What is the maximum number of breaks Vasya can take during the day?

## Input:

The first line contains three integers n, L and a (0 \le n \le 10^{5}, 1 \le L \le 10^{9}, 1 \le a \le L).
The i-th of the next n lines contains two integers t_{i} and l_{i} (0 \le t_{i} \le L – 1, 1 \le l_{i} \le L). It is guaranteed that t_{i} + l_{i} \le t_{i + 1} and t_{n} + l_{n} \le L.

## Output

Output one integer  — the maximum number of breaks.

2 11 3
0 1
1 1

3

0 5 2

2

1 3 2
1 2

## Sample Output:

0

### 题目链接

Vasya总共工作L分钟，抽一根烟要a分钟，在有顾客时Vasya不能抽烟，求Vasya最多能抽几根烟。

# B. Forgery

## Description:

Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn’t give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor’s handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor’s signature is impossible to forge. Or is it?
For simplicity, the signature is represented as an n\times m grid, where every cell is either filled with ink or empty. Andrey’s pen can fill a 3\times3 square without its central cell if it is completely contained inside the grid, as shown below.

xxx
x.x
xxx
Determine whether is it possible to forge the signature on an empty n\times m grid.

## Input:

The first line of input contains two integers n and m (3 \le n, m \le 1000).
Then n lines follow, each contains m characters. Each of the characters is either ‘.’, representing an empty cell, or ‘#’, representing an ink filled cell.

## Output

If Andrey can forge the signature, output “YES”. Otherwise output “NO”.
You can print each letter in any case (upper or lower).

3 3
###
#.#
###

YES

3 3
###
###
###

NO

4 3
###
###
###
###

YES

5 7
…….
.#####.
.#.#.#.
.#####.
…….

## Sample Output:

YES

### 题目链接

N*M的一个签名形状，Andrey每次只能在一个3*3的正方形内填充除中心方格以外的所有方格，求最后Andrey能否画出签名（’#’全部填充，’.’全部不填充）。

# C. Sequence Transformation

## Description:

Let’s call the following process a transformation of a sequence of length n.
If the sequence is empty, the process ends. Otherwise, append the greatest common divisor (GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence of n integers: the greatest common divisors of all the elements in the sequence before each deletion.
You are given an integer sequence 1, 2, \dots, n. Find the lexicographically maximum result of its transformation.
A sequence a_1, a_2, \ldots, a_n is lexicographically larger than a sequence b_1, b_2, \ldots, b_n, if there is an index i such that a_j = b_j for all j < i, and a_i > b_i.

## Input:

The first and only line of input contains one integer n (1\le n\le 10^6).

## Output

Output n integers  — the lexicographically maximum result of the transformation.

3

1 1 3

2

1 2

1

1

# D. Nature Reserve

## Description:

There is a forest that we model as a plane and live n rare animals. Animal number i has its lair in the point (x_{i}, y_{i}). In order to protect them, a decision to build a nature reserve has been made.
The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river.
For convenience, scientists have made a transformation of coordinates so that the river is defined by y = 0. Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.

## Input:

The first line contains one integer n (1 \le n \le 10^5) — the number of animals.
Each of the next n lines contains two integers x_{i}, y_{i} (-10^7 \le x_{i}, y_{i} \le 10^7) — the coordinates of the i-th animal’s lair. It is guaranteed that y_{i} \neq 0. No two lairs coincide.

## Output

If the reserve cannot be built, print -1. Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed 10^{-6}.

1
0 1

0.5

3
0 1
0 2
0 -3

-1

2
0 1
1 1

0.625