Задача 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. Варфоломей и кошка ≡

Условие

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

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

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

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

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

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

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

8
I3f I ever were to lose you
I'7d surely lose myself
Everythi9ng I have found dear
I've not fo2und by myself
Try and sometimes you'll succeed
To make this1 man of me
All my stolen 6missing parts
I've no need for anymore

3 7 9 2 1 6

Задача 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. Безопасное место ≡

Условие

я В некоторой 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