Разбор случаев

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

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

Формат входных данных
Входные данные содержат четыре строки, каждая из них содержит вес одной из гирь — натуральное число, не превышающее \(100\).

Формат выходных данных
Если уравновесить весы невозможно, выведите единственное число \(-1\).

Иначе выведите две строки. На первой строке выведите веса гирь, которые необходимо разместить на левой чаше весов. На второй строке выведите веса гирь, которые необходимо разместить на правой чаше весов.

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

Петя живёт в Санкт-Петербурге и увлекается метеорологией. Из научного интереса он решил подтвердить или опровергнуть мнение о том, что в Санкт-Петербурге постоянно идёт дождь. Для этого Петя завёл дневник дождя и раз в неделю в воскресенье оставляет в нём запись с информацией о том, идёт ли дождь. Каждую запись Петя подписывает номером текущего дня в месяце, дни в месяце нумеруются с 1 до числа дней в этом месяце (от 28 до 31 в разных месяцах).

Сегодня Петя открыл дневник, чтобы сделать очередную запись, и обнаружил, что он сделал последнюю запись две недели назад, а в прошлое воскресенье забыл занести информацию в дневник. Петя помнит, что неделю назад шёл дождь, и он решил сделать две записи: за сегодняшний день и за прошлое воскресенье. Он знает номер текущего дня в месяце \(n\) и видит, каким числом \(m\) подписана запись две недели назад. Каким числом Петя должен подписать запись за прошлую неделю?

Формат входных данных
В первой строке вывода даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 31\)) — номер текущего дня месяца и число, которым подписана запись две недели назад.

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

Выведите единственное число – каким числом должна быть подписана запись неделю назад.

Дима купил кладовку размера \(X\times Y \times Z\), где \(X, Y, Z\) — это длина, ширина и высота в метрах соответственно. Но она оказалась без окон, без дверей и с голыми стенами. В магазине продается два типа обоев. В наличии имеется \(S_1\) квадратных метров обоев первого типа, стоимостью \(C_1\) рублей за квадратный метр, а второго типа — \(S_2\) квадратных метров стоимостью \(C_2\) рублей за квадратный метр.

Дима хочет сделать дверь размера \(A \times B\), где \(A\) — ширина, а \(B\) — высота, в одной из стен (обои на дверь клеить не надо). Также он хочет, чтобы на стенах, расположенных друг напротив друга, были наклеены одинаковые обои. То есть обе стены размером \(X \times Z\) должны быть оклеены одним типом обоев. Аналогично, обе стены размером \(Y \times Z\) также должны быть оклеены одним типом обоев. Определите, получится ли у него поклеить обои, и если получится, то какая минимальная сумма в рублях ему потребуется.

Формат входных данных
В первой строке вводится три целых числа \(X\), \(Y\) и \(Z\) (\(1 \leq X, Y, Z \leq 10\,000\)) — длина, ширина и высота комнаты.

Во второй строке вводится четыре целых числа \(S_1\), \(C_1\), \(S_2\) и \(C_2\) (\(1 \leq S_1, C_1, S_2, C_2 \leq 10^{8}\)) — количество квадратных метров обоев первого типа на складе, стоимость квадратного метра обоев первого типа, количество квадратных метров обоев второго типа и стоимость квадратного метра обоев второго типа.

В третьей строке вводится два числа \(A\) и \(B\) (\(1 \leq A, B \leq 10\,000\)) — ширина и высота двери.

Формат выходных данных
Определите, сможет ли Дима оклеить кладовку обоями. Если это невозможно, то выведите -1. Иначе выведите минимальную сумму в рублях, которую Дима потратит на покупку обоев.

Решения, верно работающие при \(X=Y=Z\), будут оцениваться не менее чем в 30 баллов.

Примечание
В первом примере Дима установит дверь в стену размером \(5 \times 10\) и наклеит первый вид обоев на все стены.

Во втором примере Дима установит дверь в стену \(5 \times 10\), наклеит первый вид обоев на стены \(6 \times 10\) и второй вид обоев на стены \(5 \times 10\).

В третьем примере высота двери слишком большая.

В четвертом примере суммарная площадь доступных обоев меньше, чем площадь стен.

В крайних клетках полоски шириной в одну клетку и длиной в N клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № N. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?

Входные данные
Единственная строка входных данных содержит целое число N — длину клетчатой полосы (2 ≤ N ≤ 2 · 10⁹ ).
Выходные данные
Если лягушка и кузнечик могут оказаться в одной клетке, требуется вывести одно целое число — минимальное количество секунд, через которое они встретятся. Если они не смогут оказаться в одной клетке, требуется вывести число «-1» (без кавычек).
 

Примеры

№	Входные данные	Выходные данные
1	5	1
2	9	2

Замечание
В первом примере лягушка может прыгнуть из клетки 1 в клетки 3 и 4, а кузнечик может прыгнуть из клетки 5 в клетки 3 и 4. Поэтому через 1 секунду они могут оказаться в одной клетке.
Во втором примере лягушка и кузнечик могут встретиться через 2 секунды. Например, лягушка прыгает в клетку 3, затем в клетку 6, а кузнечик прыгает в клетку 8, затем в клетку 6.
 

Расставьте на шахматной доске размером N x N минимальное количество шахматных слонов так, чтобы они контролировали все поле (любая клетка должна находиться на одной диагонали хотя бы с одним слоном; считается, что слон контролирует и ту клетку, на которой стоит).

Входные данные
Вводится одно число - размер поля.

Выходные данные
Программа должна вывести одно число - минимальное количество слонов, которые можно расставить на данной доске так, чтобы они контролировали все поле.
 

Примеры

№	Входные данные	Выходные данные
1	3	3
2	1	1

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы,
затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)
Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.
Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 3	7	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до
N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы.

• Первая группа: 1.
• Вторая группа: 2, 7, 9.
• Третья группа: 3, 4, 10.
• Четвёртая группа: 5, 6, 8.

Вы уже догадались, что, поскольку любое число делится на 1, одна группа всегда будет состоять только из числа 1, но в остальном подобное разбиение можно выполнить различными способами. От вас требуется определить минимальное число групп, на которое можно разбить все числа от 1 до N в соответствии с приведённым выше условием.
Программа получает на вход одно натуральное число N, не превосходящее 10⁹, и должна вывести одно число – искомое минимальное количество групп.

Примеры

№	Входные данные	Выходные данные
1	10	4

Посередине озера плавает плот, имеющий форму прямоугольника. Стороны плота направлены вдоль параллелей и меридианов. Введём систему координат, в которой ось OX направлена на восток, а ось ОY – на север. Пусть юго-западный угол плота имеет координаты (x₁, y₁), северо-восточный угол – координаты (x₂, y₂).
Пловец находится в точке с координатами (x, y). Определите, к какой стороне плота (северной, южной, западной или восточной) или к какому углу плота (северо-западному, северо-восточному, юго-западному, юго-восточному) пловцу нужно плыть, чтобы как можно скорее добраться до плота.
Программа получает на вход шесть чисел в следующем порядке: x₁, y₁ (координаты юго-западного угла плота), x₂, y₂ (координаты северо-восточного угла плота), x, y (координаты пловца). Все числа целые и по модулю не превосходят 100. Гарантируется, что x₁ < x₂, y₁ < y₂, x ≠ x₁, x ≠ x₂, y ≠ y₁, y ≠ y₂, координаты пловца находятся вне плота.
Если пловцу следует плыть к северной стороне плота, программа должна вывести символ «N», к южной – символ «S», к западной – символ «W», к восточной – символ «E». Если пловцу следует плыть к углу плота, нужно вывести одну из следующих строк: «NW», «NE», «SW», «SE».
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	-1 -2 5 3 -4 6	NW

Легенда гласит, что Карл Фридрих Гаусс, учась в школе, смог быстро посчитать сумму целых чисел от 1 до 100, заметив, что 1 + 100 = 2 + 99 = … = 50 + 51. Теперь решите задачу посложнее: можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0? Например, для N = 3 сумма –1 –2 +3 будет равна 0, а для N = 2 этого сделать нельзя. Программа получает на вход целое неотрицательное число N, не превосходящее 10⁵.
Программа должна вывести последовательность из N символов «+» или «–», соответствующих знакам, которые нужно расставить перед числами от 1 до N так, чтобы сумма получившихся чисел была равна 0. Если задача имеет несколько решений, нужно вывести один (лобой) ответ. Если задача не имеет решения для данного N, нужно вывести
одно слово «IMPOSSIBLE».
 

Ввод	Вывод	Примечание
3	--+	Правильным ответом будет также «++-»
2	IMPOSSIBLE

Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g. ‘9’ consumes twice more power than ‘7’.


Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light n segments, and she wants to light exactly n segments.
Input
The single line of the input contains one integer n — the number of segments that should be lit (2 ≤ n ≤ 10⁶ ).
Output
Output a single integer — the maximum possible sum of digits that can be displayed simultaneously.

Input	Output
4	4
7	11
6	14

In the first example, a single ‘4’ should be displayed (‘7’ has greater value, but has only three segments). In the second example ‘4’ and ‘7’ should be displayed, in the third one — two ‘7’s.

Пете подарили n гирь и чашечные весы. Каждая гиря весит a_i грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наибольшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.

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

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

В первой строке  находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 4 2 1 1 8 1 5 2 2 1	20
6 20 2 3 2 2 1 5 1 1 1 3 2	32
4 3 2 10 2 8 2 9 2	30

Пете подарили n гирь и чашечные весы. Каждая гиря весит a_i грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.

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

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

В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 4 2 1 1 8 1 5 2 2 1	0
6 20 2 3 2 2 1 5 1 1 1 3 2	6
4 3 2 10 2 8 2 9 2	4

У Артура есть два натуральных числа — x и y (x < y). Помогите ему найти натуральное число z такое, что:

• z > x;
• z > y;
• z не делится на x;
• z не делится на y;
• z делится на y - x;
• z минимально.

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

В первой строке находятся числа x и y (x, y ≤ 10⁶)

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

Выведите число z или '0', если его не существует.

Ввод:
1 2

Вывод:
0