Задача A. Безопасное пересечение дороги
Условие
Пешеход переходит дорогу, состоящую из
K полос автомобильного движения. Он заметил
N автомобилей, каждый из
которых движется по своей полосе движения
wi и пересечет место перехода дороги через
bi секунд.
Пешеход может останавливаться между полосами дороги, а так же в начале и в конце пути. При этом,
если он уже начал переходить полосу, то он не может остановиться и пересечение очередной
полосы движения займет у него время
t. В начальный момент времени пешеход находится на
краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны.
Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть он идет прямо и не
поворачивает. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее
полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной
i, если момент времени
bi он оказался на полосе
wi. Но если он в это время находился между полосами или в начале и в конце
пути, то машина его не задевает.
Формат входного файла
Во входном файле содержатся числа
K, N, t, за которыми следует
N пар чисел
wi и
bi
Формат выходного файла
В выходной файл выведите единственное число - минимальное время, за которое переход может перейти дорогу.
В приведенном ниже примере пешеход начинает переходить полосу 1 в начальный момент времени и заканчивает
ее переходить через 10 секунд, как раз, когда по этой полосе проезжает машина 2. После этого он ждет
5 секунд и переходит вторую полосу.
Ограничения
0 ≤ N ≤ 2*105,
1 ≤ K ≤ 2*105,
1 ≤ t ≤ 103,
0 ≤ bi ≤ 109
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2 3 10
2 15
1 10
2 30
|
25
|
Problem B. Divide by Squares
Statement
Divide by Squares is played on a rectangular grid.
Some of the squares in the grid are numbered.
The objective is to divide the grid into rectangular
and square pieces such that each piece contains exactly one number,
and that number represents the area of the rectangle (from Wikipedia).
On the pictures you can see a sample of the puzzle and its solution.
You are to write program that solves this puzzle.
Input file format
The first line of the input file contains three integers,
separated by spaces — the height
H, the width
W of the grid,
and total amount
K of numbers on the grid.
Each of the next
K lines contains three integers,
separated by spaces — position
(i, j) of the number and the number itself.
The puzzle in the input has at least one solution.
Output file format
The output file must contain
K lines.
For each number in the input you should print four integers on corresponding line —
coordinates of left upper corner of the rectangle that contains
this number and its height and width. You have to print arbitrary solution.
Constraints
1 ≤ H ≤ 10, 1 ≤ W ≤ 10, 1 ≤ K ≤ W*H
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
4 4 4
2 1 4
2 3 6
3 1 4
4 4 2
|
1 1 2 2
1 3 3 2
3 1 2 2
4 3 1 2
|
