Задачи олимпиады "Муниципальный этап Всероссийской олимпиады школьников Красноярского края по информатике, 7-8 классы"

Задача A. Точки и прямоугольники

Введем на плоскости декартову прямоугольную систему координат и рассмотрим прямоугольник, один угол которого находится в начале координат, а противоположный ему – в точке (W, H). Рассмотрим второй прямоугольник, который находится строго внутри первого и вершины которого находятся в точках с целыми координатами, Обозначим ширину второго прямоугольника как w, высоту – как h. Стороны обоих прямоугольников параллельны осям координат.

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

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

Входной файл INPUT.TXT содержит четыре целых числа: W , H, w и h (3 ≤ W, H ≤ 10⁹,1 ≤ w ≤ W−2, 1 ≤ h ≤ H−2).

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

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Примеры

Задача B. Светофор

А Вы знаете, как работает светофор? Пожалуй, что каждый школьник знаком с этим устройством, но не каждый точно может описать алгоритм его работы. Если сомневаетесь, то спросите себя: «Сколько раз мигает зеленый сигнал светофора?».

Рассмотрим самый обычный вертикальный автомобильный светофор, состоящий из трех секций для индикации (сверху вниз) красного, желтого и зеленого сигналов. Напомним его функционал. Каждая секция может отражать два цвета: соответствующий ей цвет во включенном состоянии и черный цвет в выключенном состоянии. Когда светофор исправен, то ему доступно 6 возможных состояний. В обычном рабочем режиме мы имеем следующий алгоритм работы:

1. горит только зеленый сигнал;
2. зеленый сигнал мигает;
3. гаснет зеленый, загорается желтый;
4. гаснет желтый, загорается красный;
5. загорается желтый и горит вместе с красным;
6. гаснут желтый и красный и все повторяется с пункта 1.

Еще следует не забывать о том, что светофор может работать в режиме нерегулируемого перекрестка, когда присутствует только желтый мигающий сигнал.

По текущей индикации сигналов светофора следует определить его следующее состояние, в которое он должен перейти, либо определить, что светофор неисправен.

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

Входной файл INPUT.TXT содержит в трех строках описание текущего состояния светофора. Первая строка описывает верхнюю секцию, вторая – среднюю, третья – нижнюю. Состояние каждой из секций определяется ее цветом: black (черный), red (красный), yellow (желтый) и green (зеленый). Если некоторый цвет мигает, то его название записывается в верхнем регистре, иначе – в нижнем.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу в том же формате, если светофор исправен. В случае неисправности светофора выведите «error».

Примеры

Задача C. Пирожки

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

Помогите Пете определить максимально возможное количество пирожков, которые он может купить.

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

Первая строка входного файла INPUT.TXT содержит числа P₁, P₂ и P₃ – стоимость пирожков с картошкой, капустой и рисом соответственно. Во второй строке определены значения N₁, N₂ и N₃ – количество соответствующих пирожков в продаже. В третьей строке записано число R – количество денег у Пети. Все числа во входных данных целые неотрицательные, не превосходящие 10¹⁸.

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

В выходной файл OUTPUT.TXT выведите одно целое число - ответ на задачу.

Примеры

Задача D. Сжатие бинарных последовательностей

Последовательность из символов «0» и «1» называется бинарной. Они широко применяются в информатике и других науках. Одно из неудобств бинарных последовательностей – их трудно запоминать. Для решения этой проблемы были предложены разные способы их сжатия. Программист Слава использует следующий способ: просматривая последовательность слева направо, он заменяет «1» на «a», «01» на «b», «001» на «c», …, «00000000000000000000000001» на «z». Напишите программу, которая поможет Славе автоматизировать этот способ сжатия.

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

Входной файл INPUT.TXT содержит бинарную последовательность – строку из символов «0» и «1» длиной от 1 до 255 символов. Гарантируется, что к ней применим указанный способ сжатия.

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

В выходной файл OUTPUT.TXT выведите одну строку из английских строчных букв от «a» до «z» – сжатие заданной бинарной последовательности.

Примеры

Задача E. Бег по эскалатору

Пусть N человек бегут вниз по эскалатору, причем i-ый пробегает одну ступеньку за t_i секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены «обгоны», то есть если человек A в процессе бега догнал человека B, который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B. Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно.

Ваша задача написать программу, которая поможет работникам станции рассчитать, когда закончит свой бег по эскалатору каждый бегущий человек.

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

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10⁵). В следующих N строках перечислены пары чисел t_i, w_i (1 ≤ t_i, w_i ≤ 10⁶) – время пробега одной ступени и количество ступеней до конца эскалатора для i-го человека. Гарантируется, что изначально всем людям осталось бежать различное число ступеней.

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

В i-ой строке выходного файла OUTPUT.TXT выведите время в секундах, через которое i-ый человек сойдет с эскалатора.

Пример