Задача 1. Расчетливая вязка ≡

Условие

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

Открыв книжку по вязанию, Варфоломей увидел, что весь шарф описан схемой, где каждый символ обозначает собственный вид петли. В сноске написано, что символ "." (ASCII 46) — означает, что на такую петлю уходит K миллиметров, а "/" (ASCII 47) и "|" (ASCII 124) — соответственно означают M, P миллиметров. В каждой строке схемы R петель, а всего строк T.

Так же известно, что в 1 клубочке пряжи любимого бабушкиного цвета H миллиметров.

Используя схему шарфика, а так же расход пряжи на каждый вид петли, вычислите, сколько Варфоломею нужно купить клубочков. Учтите, что если, например, что при наличии в 1 клубочке 100 миллиметров пряжи, а из расчетов выходит, что пряжи нужно 110 миллиметров, то 1 клубочка будет недостаточно, нужно покупать 2.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Формат входного файла

Первая строка входного файла содержит целые числа T, R — количество строк и символов в них. Вторая строка содержит информацию о затратах на каждый тип петли, а также, сколько миллиметров в 1 клубочке — K, M, P, H. Последующие T строк содержат по R символов.

Формат выходного файла

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

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

3 20
4 7 4 128
|...|//./|..|||..|./
../....||/...||.|/||
|||///||/.|||///|//.

3

Задача 2. Починить змея ≡

Условие

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

Даны три стороны треугольника: A, B и C. Можно ли составить новый невырожденный треугольник, сторонами которого будут высоты, проведëнные в данном треугольнике?

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

Входные данные содержат 3 вещественных числа A, B и C — стороны треугольников.

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

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

Ограничения

1 ≤ A, B, C ≤ 1000

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

7 9 15

YES

2.24 15 13.04

NO

Задача 3. Варфоломей в транспорте ≡

Условие

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

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

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

Входной файл содержит 2 целых числа K и F — количество монет у Варфоломея и стоимость проезда соответственно. Далее следуют K номиналов монет, которые являются элементами отсортированного по возрастанию массива.

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

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

Ограничения

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

9 11
1 2 3 4 5 6 7 8 9

2 9

9 100
1 2 3 4 5 6 7 8 9

-1

Задача 4. Сколько селёдок? ≡

Условие

Витя, Петя и Олег решили сходить на рыбалку за селёдками. В море селёдок много и каждая из них весит строго целое количество килограмм. Олег провёл классификацию рыбы и выяснил, что массы селёдок образуют последовательность, заданную следующим образом: x_i = x_i − 1 + i. Минимальный вес селёдки составляет один килограмм. Мальчики взяли с собой ведро, в которое помещается N килограмм рыбы. Разумеется, они хотели бы вернуться домой с полным ведром селёдок.

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

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

Входной файл содержит единственное число N — вместимость ведра в килограммах.

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

В выходной файл выведите число — минимальное число селёдок.

Ограничения

1 ≤ N ≤ 5 * 10¹¹

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

3

1

5

3

Задача 5. Безопасное место ≡

Условие

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

На поле N клеток и M монстров. Вы знаете расположение, направление и скорость движения всех монстров. Их интеллект оставляет желать лучшего, так как они всегда движутся в одном направлении с постоянной скоростью V_i - количество клеток в минуту. А если монстр упрётся в край карты, то он встанет на месте.

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

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

Первая строка входного файла содержит два целых числа N и M — размер карты и количество монстров соответственно.

Далее следует M строк, i-я строка содержит два целых числа A_i, V_i — номер клетки, в которой находится монстр в начале игры и его скорость движения. Если V_i отрицательна, то монстр движется в сторону убывания номеров клеток, и положительна в обратном случае.

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

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

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

 − 10⁶ ≤ V_i ≤ 10⁶, V_i ≠ 0

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

В первом примере артефакт можно поставить в 3 клетку и оно там будет в безопасности сколько угодно времени.

Во втором примере монстры стоят на клетках 1 и 5 в момент времени 0. Через 0.5 минуты первый монстр заходит на 2 клетку. Через 1 минуту от начала игры первый монстр заходит на 3 клетку, а второй монстр на 4 клетку. Таким образом, как 3, так и 4 является правильным ответом.

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

3 1
2 -1

3

5 2
1 2
5 -1

3