Problem A. Box
Statement
Ivan works at a factory that produces heavy machinery. He has
a simple job — he knocks up wooden boxes of different sizes
to pack machinery for delivery to the customers. Each box
is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets
to make a box. Each pallet is used for one side of the box.
Joe delivers pallets for Ivan. Joe is not very smart and
often makes mistakes — he brings Ivan pallets that do not fit
together to make a box. But Joe does not trust Ivan. It always
takes a lot of time to explain Joe that he has made a mistake.
Fortunately, Joe adores everything related to computers and sincerely
believes that computers never make mistakes. Ivan has decided to
use this for his own advantage. Ivan asks you to write
a program that given sizes of six rectangular pallets
tells whether it is possible to make a box out of them.
Input file format
Input file consists of six lines. Each line describes one pallet and
contains two integer numbers
w and
h —
width and height of the pallet in millimeters respectively.
Output file format
Write a single word `
POSSIBLE' to the output file if it is possible
to make a box using six given pallets for its sides. Write a single word
`
IMPOSSIBLE' if it is not possible to do so.
Constraints
1 ≤ w, h ≤ 10000
Sample tests
| No. |
Input file (box.in) |
Output file (box.out) |
|---|
| 1 |
1345 2584
2584 683
2584 1345
683 1345
683 1345
2584 683
|
POSSIBLE
|
| 2 |
1234 4567
1234 4567
4567 4321
4322 4567
4321 1234
4321 1234
|
IMPOSSIBLE
|
Задача B. Квадраты
Условие
Рассмотрим целочисленную решетку размера N x N.
Пусть некоторые ее узлы покрашены в белый, а некоторые - в черный цвет.
Требуется определить количество квадратов на заданной решетке, то есть квадтаров,
вершины которых совпадают с узлами заданной решетки и покрашены в одинаковый цвет.
Например, на решетке размера 4 x 4, изображенной на рисунке 1 такой квадрат один, он показан на рисунке 2.
Формат входного файла
Первая строка входного файла содержит число
N - размер решетки.
Следующие
N строк содержат по
N символов из множества {"0", "1"} и задают решетку.
Если точка с координатами (i, j) покрашена в белый цвет, то j-ый символ i-ой строки есть "0",
а если в черный, то "1".
Формат выходного файла
Количество квадратов на решетке из входного файла.
Ограничения
2 ≤
N ≤ 50.
Примеры тестов
| № |
Входной файл (f.in) |
Выходной файл (f.out) |
|---|
| 1 |
4
0100
0011
1000
0111
|
1
|
Задача C. Забор в парке
Условие
В бесконечном квадратном парке деревья образуют квадратную решётку с шагом 1 метр.
Часть парка было решено оградить забором, который представляет собой многоугольник с
заданными координатами вершин. Деревья, которые в точности попадают на
вершины или стороны многоугольника, придётся срубить. Необходимо выяснить количество таких деревьев.
Программа должна, получив на входе число вершин многоугольника N и их
целочисленные координаты (x1, y1), …,
(xN, yN), определить количество точек с целочисленными
координатами, лежащих на границе этого многоугольника.
Стороны многоугольника не самопересекаются.
Формат входного файла
Входной файл содержит число
N, за которым следует
N пар координат
x1 y1 …
xN yN
Формат выходного файла
Выходной файл должен содержать единственное число — количество точек.
Ограничения
3 ≤
N ≤ 1000,
0 ≤
xi,
yi ≤ 10
7,
исходные данные таковы, что результат не превосходит 2
31−1.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
0 0 2 0 0 2
|
6
|
Задача D. Поезда
Условие
В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство
железнодорожной компании решило изменить график движения поездов.
Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения:
сначала T1 минут поезд идет со скоростью V1 метров в минуту,
затем T2 минут со скоростью V2 м/мин, ...,
наконец, TN минут со скоростью VN м/мин.
В течение интервала Ti (1 ≤ i ≤ N) поезд может стоять.
По действующей инструкции обеспечения безопасности движения расстояние между началами
следующих друг за другом поездов никогда не должно быть менее L метров.
Напишите программу, определяющую минимально допустимый интервал в минутах между
отправлениями поездов, позволяющий им двигаться по установленному графику без опасного сближения.
Формат входного файла
В первых двух строках входного файла содержатся натуральные числа, задающие минимально
допустимое расстояние
L и количество участков пути
N.
Далее следуют
N пар целых чисел
T1,
V1, ...,
TN,
VN, описывающих график движения.
Формат выходного файла
В выходной файл требуется вывести искомый интервал между отправлениями поездов в минутах,
не менее чем с тремя верными знаками после десятичной точки.
Ограничения
100 ≤
L ≤ 10000, 1 ≤
N ≤ 1000,
1 ≤
Ti ≤ 1000, 0 ≤
Vi ≤ 1000.
Примеры тестов
| № |
Входной файл (train.in) |
Выходной файл (train.out) |
|---|
| 1 |
1000
4
10 0
30 80
15 0
20 100
|
27.5
|
