Олимпиады для начинающих 02

Подборка из нескольких задач для подготовки к олимпиаде по информатике.


Содержание



Морской бой

Чтобы разнообразить игру «морской бой» Боря решил добавить в неё новый тип кораблей. Эти корабли состоят из двух прямоугольников. Первый прямоугольник имеет ширину w1 и высоту h1, а второй прямоугольник — w2 и h2 соответственно. Прямоугольники располагаются один над другим и выровнены по левому краю (см. рисунки после примеров): введем на поле систему координат так, чтобы левая нижняя клеточка первого прямоугольника имела координаты (1, 1). Тогда верхняя правая клеточка первого прямоугольника имеет координаты (w1, h1), левая нижняя клеточка второго прямоугольника имеет координаты (1, h1 + 1), а правая верхняя клеточка второго прямоугольника имеет координаты (w2, h1 + h2).

По правилам морского боя, после уничтожения корабля необходимо отметить все клеточки, соседние по стороне или углу с клеточками, в которых есть корабль, потому что в этих клеточках уже не могут стоять другие корабли. При этом отмечаются только не принадлежащие кораблю клетки.

Определите, сколько клеток надо будет отметить после уничтожения корабля, придуманного Борей. Поле, на котором, происходит игра, бесконечно во все стороны.

Входные данные

В четырех строках заданы четыре целых числа w1, h1, w2 и h2 (1 ⩽ w1, h1, w2, h2 ⩽ 108) — ширина первого прямоугольника, высота первого прямоугольника, ширина второго прямоугольника и высота второго прямоугольника, соответственно.

Выходные данные

Выведите одно целое число — количество клеток, которые необходимо закрасить после уничтожения корабля.

Пример входных и выходных данных

input.txt output.txt
2
1
2
1
12
2
2
1
2
16

Примечание

В первом примере поле выглядит так (красным обозначен первый прямоугольник, синим обозначен второй прямоугольник, зеленым обозначены отмеченные точки):
В первом примере поле выглядит так
Во втором примере поле выглядит так:
Во втором примере поле выглядит так


Автобусы

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a, …, второй — в моменты времени 0, b, 2b, 3b, …, а третий в моменты времени 0, c, 2c, 3c, ….

Момент времени называется подходящим для пересадки, если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a = 1, b = 2, c = 1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t — 1)-й включительно, во второй день — c t-го по (2t — 1)-й включительно, в третий — с 2t-го по (3t — 1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдtт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные

В пяти строках заданы пять целых чисел a, b, c, t и d (1 ⩽ a, b, c ⩽ 106, 1 ⩽ t, d ⩽ 109) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные

Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Пример входных и выходных данных

input.txt output.txt
1
2
1
3
1
2
2
3
4
7
2

1
2
3
4
3
3

0

Примечание

В первом примере сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки.

Во втором примере рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.

В третьем примере нет ни одного подходящего для пересадки момента времени.



Оставить комментарий