Задача A. Кролик ≡

Условие

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

Известно, что в начале дня масса кролика равна M кг. На завтрак кролик ест A морковок, на обед — B яблок, а на ужин — C бананов.

Съев морковку, яблоко или банан, кролик увеличит свою массу на 2, 3 или 4 кг соответственно.

Так как морковки — более привычная для кроликов еда, чем яблоки, а яблоки — более привычная еда, чем бананы, съеденная масса яблок не должна превышать съеденную массу морковок, а съеденная масса бананов не должна превышать съеденную массу яблок.

Если вышеуказанное условие не выполняется, кролику станет очень плохо и посетители зоопарка будут недовольны.

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

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

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

Входной файл содержит 4 целых числа: M, A, B и C.

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

В случае, если кролику стало плохо, выходной файл должен содержать число −1.

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

Ограничения

1 ≤ M, A, B, C ≤ 10⁶

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

10 5 3 2

37

10 3 3 2

-1

Задача B. Вокруг дома ≡

Условие

Васин дом имеет в плане форму прямоугольника. Северная и южная стороны имеют длину по A метров каждая, а западная и восточная — по B метров каждая.

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

Требуется написать программу, которая определит, вдоль какой стены будет идти Вася через t секунд после начала прогулки. Будем считать, что дойдя то угла, Вася немедленно за него поворачивает, поэтому на секундах с нулевой по A − 1-ю он находится у южной стены, на секунде номер A — у восточной, и так далее.

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

Входной файл содержит целые числа A B t.

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

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

• N — северная стена,
• W — западная стена,
• S — южная стена,
• E — восточная стена.

Ограничения

1 ≤ A, B, t ≤ 5*10⁸

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

10 5 18

N

1 8 18

S

Задача C. Занимательная физика ≡

Условие

Физик Антон построил цепочку S из частиц. Частицы обозначаются маленькими латинскими буквами от a до z. Если в цепочке встречается последовательность подряд идущих символов abc, то происходит взрыв. Причем взрывов случится ровно столько, сколько раз в цепочке встречается эта последовательность. Например, в цепочке aaabcabcсс произойдёт два взрыва.

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

В первом примере в исходной цепочке происходит один взрыв caabcc, Антон может поставить частицу v после буквы a, в подстроке abc и получим цепочку caavbcc, в которой взрывов нет. Также возможным ответом является строка caabvcc.

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

Первая строка содержит строку S, вторая единственный символ C.

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

Выходной файл должен содержать единственную строку — новую цепочку.

Ограничения

Количество букв в цепочке от 1 до 100. Все символы во входном файле это строчные буквы латинского алфавита.

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

caabcc
v

caavbcc

ab
a

aab

Задача D. Кусты вдоль берега ≡

Условие

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

Петр хорошо разбирается в ботанике и точно может определить сорт куста. В данной задаче будем считать, что сорт куста  — целое число от 0 до 10⁵.

Кусты растут через каждый метр. Сегодня Петр пробежал n метров, он запоминал все кусты которые были на его пути.

Придя домой он написал последовательность из n чисел a₁, …, a_n, где a_i  — сорт куста, растущего на расстоянии i от начала забега.

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

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

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

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

Далее следуют n чисел a_i  — сорта кустов, растущие на расстоянии i от начала забега.

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

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

Гарантируется что существует сорт с количеством кустов больше одного.

Ограничения

2 ≤ n ≤ 10⁵

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

5
1 2 3 1 3

1 4

4
2 1 2 1

1 3

6
1 2 3 2 2 4

2 5

2
22222 22222

1 2