Задача A. Том Сойер и билетики ≡

Условие

"Одного только не хватало мистеру Уолтерсу для полного счастья: возможности вручить наградную Библию и похвастать чудом учености. У некоторых школьников имелись желтые билетики, но ни у кого не было столько, сколько надо, — он уже опросил всех первых учеников. И в ту самую минуту, когда всякая надежда покинула его, вперед выступил Том Сойер с девятью желтыми билетиками, девятью красными и десятью синими и потребовал себе Библию", Марк Твен, "Приключения Тома Сойера".

Для получения одной награды нужно предъявить y желтых билетиков. Один желтый билетик можно заменить r красными. Один красный билетик можно заменить b синими. У Тома сейчас y_T, r_T и b_T билетиков соответственно желтого, красного и синего цвета. Сколько наград Том может получить?

Формат входных данных

Первая строка входного файла содержит три натуральных числа, записанных через пробел: y, r и b. Вторая строка содержит три неотрицательных целых числа, записанных через пробел: y_T, r_T и b_T.

Формат выходных данных

Выведите одно неотрицательное целое число - наибольшее количество наград, которые может получить Том.

Ограничения

1 ≤ y, r, b ≤ 10⁹

0 ≤ y_T, r_T, b_T ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Примеры тестов

10 10 10
9 9 10

1

Задача B. Задача из ЕГЭ ≡

Условие

Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме "Системы счисления" ему часто приходится решать примеры типа "сколько значащих нулей (или единиц) содержит двоичная запись значения выражения 2^a + 2^b − 2^c?" Помогите Тимофею по известным a, b и c узнать ответ на задачу.

Формат входных данных

Первая строка входного файла содержит четыре неотрицательных целых числа, записанных через пробел: a, b, c и d. Числа a, b и c соответствуют показателям степеней двоек в задании. Число d равно либо 0, либо 1 - цифра, количество которых в значении выражения нужно узнать.

Формат выходных данных

Выведите одно неотрицательное целое число - ответ на задачу.

Ограничения

0 ≤ b, c < a ≤ 10¹⁸

0 ≤ d ≤ 1

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при b = с, получат не менее 10 баллов.

Пояснение к примеру

В примере нужно узнать количество единиц в двоичной записи значения выражения 2⁴ + 2³ − 2². Вычислим: 16 + 8 − 4 = 20. 20₁₀ = 10100₂. Всего две единицы.

Примеры тестов

4 3 2 1

2

Задача C. Время - деньги ≡

Условие

Владелец магазина сохраняет информацию о проданных товарах в формате "Время продажи - стоимость продажи". Например, запись об одной покупке выглядит так: 9 − 00 12 − 50. Это значит, что ровно в девять часов утра ученик Тимофей купил жевательную резинку за двенадцать рублей пятьдесят копеек. Но однажды случилось СТРАШНОЕ, и все записи "Время - деньги" перепутались и перемешались... Теперь владелец имеет две записи (9 − 00 и 12 − 50) и не может проверить честность своего кассира - ведь вполне может быть, что в двенадцать пятьдесят тот же Тимофей купил Чупа-Чупс за девять рублей. И да - магазин работает круглосуточно и в нем имеются товары любой небесплатной стоимости.

Помогите владельцу определить минимальную и максимальную возможные суммы продажи за одни сутки (это значит, что если запись соответствует времени, то она должна находиться в границах от "0-00" до "23-59").

Формат входных данных

В первой строке входного файла записано одно натуральное четное число: n – количество записей. В последующих n строках хранятся записи в формате x − yy, где x - неотрицательное целое число, выражающее либо стоимость покупки в рублях, либо время покупки в часах, yy - две цифры (либо добавочная стоимость покупки в копейках, либо время покупки в минутах). Запись x − yy разделена символом "-" (ASCII-код 45).

Формат выходных данных

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

Гарантируется, что существует по крайней мере один корректный способ восстановить все продажи.

Ограничения

2 ≤ n ≤ 10⁵

0 ≤ x ≤ 99

00 ≤ yy ≤ 99

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n = 2, баллы: 20.

Подзадача 2: нет ограничений, баллы: 80.

Примеры тестов

2
12-50
9-00

9-00
12-50

4
0-00
10-00
20-00
30-00

40-00
50-00

4
2-00
3-00
2-00
5-00

4-00
8-00

Задача D. Натуральный ряд ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день ученые открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофею для завершения доказательства теоремы требуется определить: сколько существует различных непрерывных подпоследовательностей ряда натуральных чисел, которые в сумме дают заданное число n?

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число - ответ на задачу.

Ограничения

1 ≤ n ≤ 10¹²

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере нужно найти количество непрерывных подпоследовательностей ряда натуральных чисел, дающих в сумме число 15. Перечислим их:

1) 1 + 2 + 3 + 4 + 5 = 15

2) 4 + 5 + 6 = 15

3) 7 + 8 = 15

4) 15 = 15

Всего 4 подпоследовательности.

Примеры тестов

15

4

Задача E. Следы жизни ≡

Условие

Одиноки ли мы во вселенной? Ответ на этот вопрос может дать космический зонд "VList2020", приблизившийся к орбите безымянной планеты. Зонд сделал два снимка одного и того же участка поверхности с интервалом в 24 часа и переслал их на Землю для анализа. На первом снимке разочарованные исследователи увидели только ровный безжизненный пейзаж, а вот на втором обнаружились оставленные кем-то следы!

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

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m - размер фотографии. В следующих n строках длиной m содержится описание снимка. На каждой позиции строки находится один из четырех символов:

"." (ASCII-код 46) - пустое место, нет участка цепочки следов;

"-" (ASCII-код 45) - участок горизонтальной цепочки следов;

"|" (ASCII-код 124) - участок вертикальной цепочки следов;

"/" (ASCII-код 47) - участок диагональной цепочки следов.

Формат выходных данных

Выведите одно неотрицательное целое число - минимальное возможное количество цепочек следов на снимке.

Ограничения

1 ≤ n ≤ 100

1 ≤ m ≤ 1000

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 20 баллов.

Решения, верно работающие при 1 ≤ n, m ≤ 10, получат не менее 40 баллов.

Пояснения к примерам

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

Примеры тестов

4 5
--/--
./|..
/.|..
..|..

3

4 5
-|---
||...
||---
||../

5