Вывод формулы

В детском саду Сластена N детей. Анна Николаевна выстраивает детей в линию, затем раздает 1 конфету первому ребенку, 2 конфеты второму ребенку, ..., N конфет N-му ребенку. Сколько всего конфет потребуется Анне Николаевне?

Входные данные
На вход подается целое число N (\(1 <= N <=100\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

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

 

Ручка стоила K рублей. Первого сентября стоимость ручки увеличилась ровно на P процентов. Определите, сколько ручек можно купить на S рублей после подорожания.
Программа получает на вход три целых положительных числа. Первое число K – стоимость ручки в рублях до подорожания. Второе число P – величина подорожания ручки
в процентах. Третье число S – имеющаяся сумма денег. Числа K и S не превосходят 10⁷ , число P не превосходит 100.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	33 5 100	2	Ручка стоила 33 рубля. После подорожания на 5 % ручка будет стоить 34 рубля 65 копеек (заметим, что, поскольку первоначальная цена ручки была целым числом рублей, после подорожания стоимость ручки будет выражаться целым числом рублей и копеек). На 100 рублей после подорожания можно купить 2 ручки.

Маша любит чётные числа, а Миша – нечётные. Поэтому они всегда радуются, если встречают числа, которые им нравятся.
Сегодня им встретились все целые числа от A до B включительно. Маша решила посчитать сумму всех чётных чисел от A до B, а Миша – сумму всех нечётных, после чего они начали спорить, у кого получилась сумма больше. Помогите им – найдите разность
между суммой Маши и суммой Миши.
Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10⁹.
Программа должна вывести одно число – разность между суммой чётных чисел и суммой нечётных чисел от A до B.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6	2	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 = 8, разность равна 2.
2	3 7	-5	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 + 7 = 15, разность равна −5.

Бесконечную таблицу, строки и столбцы которой пронумерованы целыми числами начиная с 1 сверху вниз и слева направо, заполняют целыми числами 1, 2, 3 и т.д. Числа выписываются в
соседние клетки по границам квадратов увеличивающегося размера (см. рисунок).


Формат входных данных
Программа получает на вход одно целое число n, 1 ≤ n ≤ 10¹⁸
Формат выходных данных
Программа должна вывести два целых числа: номер строки и номер столбца, в которых находится число n в этой таблице. Запись выводимых чисел должна содержать только цифры, вывод
действительных чисел в ответе считается неверным.

Примеры

№	Входные данные	Выходные данные
1	15	4 2

Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один
ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от 1 до n, то можно обозначить за s_i номер ребёнка человека с номером i и сказать, что s_i = 0 в случае, если у человека с номером i детей нет.
Будем считать, что человек a входит в родословную человека b, если либо a = b, либо если у b известны родители, и a входит в родословную одного из родителей b.

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

Формат входных данных
В единственной строке заданы два целых числа n и k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — количество людей в родословной и количество перекосов в ней.

Формат выходных данных
В первой строке выведите «YES» (без кавычек), если существует родословная с n людьми и k перекосами, и «NO» (без кавычек) в противном случае.
Если требуемая родословная существует, то во второй строке выведите n целых чисел s1, s2, . . . , sn (0 ≤ s_i ≤ n), задающих номера детей каждого из n человек в родословной. Если искомых родословных несколько, выведите любую.

Примеры

№	Входные данные	Выходные данные
1	3 0	YES 0 1 1
2	5 1	YES 0 1 1 3 3
3	3 2	NO

Замечание

В первом примере подойдет единственная родословная, которую можно составить из трёх человек (человек и два его родителя).

Во втором примере подойдет следующая родословная:


В этом случае в родословную человека 1 входят пять человек (люди 1, 2, 3, 4, 5), в родословную человека 2 входит один человек (только 2), в родословную человека 3 входят три человека (3, 4, 5), в родословную человека 4 входит один человек (только 4) и в родословную человека 5 входит один
человек (только 5). В этом случае происходит перекос родословной в человеке 1.
В третьем примере можно показать, что не существует родословной из трёх людей с двумя перекосами.
 

Среди открытого банка задач ЕГЭ по математике есть следующая: по заданным натуральным числам l, r и m вас просят найти целые числа a, b и c, каждое из которых не меньше l и не больше r, и такие, что будет существовать натуральное число n (целое число, большее нуля) такое, что
n · a + b − c = m.
Паша еще только начал готовиться к ЕГЭ и не совсем понимает, как решать подобную задачу. Помогите ему для разных вариантов этой задачи находить подходящие a, b и c.

Формат входных данных
В единственной строке заданы три целых числа l, r и m (1 ≤ l ≤ r ≤ 500 000, 1 ≤ m ≤ 1010).

Формат выходных данных
Выведите три целых числа a, b и c такие, что l ≤ a, b, c ≤ r и существует такое натуральное число n, что n · a + b − c = m. Гарантируется, что такие числа существуют. Если подходящих решений несколько, выведите любое из них.
 

Примеры

№	Входные данные	Выходные данные
1	4 6 13	4 6 5
2	2 3 1	2 2 3

Замечание
В первом примере можно выбрать n = 3, тогда n · 4 + 6 − 5 = 13 = m. Так же возможны такие ответы: a = 4, b = 5, c = 4 (при этом n = 3); a = 5, b = 4, c = 6 (при этом n = 3); a = 6, b = 6, c = 5 (при этом n = 2); a = 6, b = 5, c = 4 (при этом n = 2).
Во втором примере n = 1, тогда n · 2 + 2 − 3 = 1 = m. Число n = 0 не могло быть выбрано, так как число n обязательно должно быть натуральным.

Сегодня Дима целый день старался и выписывал на длинную бумажную ленту своё любимое целое положительное число n, состоящее из l цифр. К сожалению, лента получилась настолько длинной, что в итоге не влезла в Димин шкаф.

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

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

Входные данные
Первая строка содержит одно целое число l (2 ≤ l ≤ 100000) — длину любимого числа Димы.

Вторая строка содержит целое положительное число n, изначально записанное на ленте — любимое число Димы.

Число n состоит ровно из l цифр, при этом запись не содержит ведущих нулей. Также Дима гарантирует, что существует хотя бы один способ разрезать число, удовлетворяющий всем требованиям выше.

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

Примечание
В первом примере Дима может разрезать число 1234567 на числа 1234 и 567. Их сумма равна 1801.

Во втором примере Дима может разрезать число 101 на числа 10 и 1. Их сумма равна 11.

Примеры

№	Входные данные	Выходные данные
1	7 1234567	1801
2	3 101	11

В воинской части города Шатров продолжаются занятия по строевой подготовке. Молодой прапорщик Андрей Юрьевич уже приноровился проводить эти занятия, но тут его начальник Павел Андреевич стал давать ему новые, более сложные задания.

Как известно, обычно все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Но Павлу Андреевичу это показалось слишком скучным и он потребовал от Андрея Юрьевича выстроить солдат в другом порядке. Случайный порядок ему показался слишком хаотичным, поэтому он потребовал построения, в котором будет ровно k инверсий. Инверсией называется такая пара солдат, что более высокий из них стоит в шеренге раньше более низкого.

К счастью для Андрея Юрьевича, все солдаты разного роста и для каждого он знает, какой он по росту среди всех солдат. Исходя из этого, каждому солдату Андрей Юрьевич присвоил номер: первый номер получил самый низкий, а последний — самый высокий солдат.

Например, в построении (3, 1, 2) есть две инверсии — пары (3, 1) и (3, 2), в которых более высокий солдат стоит раньше более низкого.

Андрей Юрьевич поручил Вам помочь ему в построении солдат в требуемом порядке, и для этого вы должны написать программу, находящую расстановку n солдат в порядке, в котором есть ровно k инверсий.

Входные данные
Первая и единственная строка входного файла содержит два целых числа n и k (1 ≤ n ≤ 100 000) — количество солдат в строю и требуемое количество инверсий.

Гарантируется, что существует построение солдат с требуемым числом инверсий, то есть 0 ≤ k ≤ n(n - 1) / 2.

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

Примеры

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

Как известно, личная олимпиада по информатике проходит в два тура. На каждом из туров участники получают какие-то баллы, при этом итоговый балл определяется как сумма полученных баллов. Известны баллы, которые каждый участник получил на каждом из туров. Жюри хочет фальсифицировать итоги олимпиады так, чтобы победил «нужный» участник.

При этом жюри может делать следующие «подтасовки» (можно делать несколько «подтасовок» применительно как к одному и тому же, так и к разным турам):

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

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

Входные данные
Во входном файле записано сначала число участников N (1 ≤ N ≤ 1000), затем N пар чисел — результаты каждого участника за 1-й и за 2-й туры (результат участника за тур — это вещественное число от 0 до 100) не более, чем с 3 знаками после десятичной точки.

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

Примеры

№	Входные данные	Выходные данные
1	4 45 90 70 80 0 0 75 75	2 2 4

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

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

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

Программа получает на вход натуральное число N (2 ≤ N ≤ 10⁸) – максимально допустимую массу ювелирного изделия.

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

Если задача имеет множество решений, необходимо вывести любое из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3	2	Пусть x – изделие, массу которого необходимо определить. Нужно на одну чашу весов положить x, а на другую чашу весов – гирьку в 2. Если x будет легче, то x = 1, при равенстве – x = 2, если x тяжелее, то x = 3.
2	5	3 4	Покажем, как при помощи гирек в 3 и 4 определить все массы от 1 до 5. Массы 3 и 4 можно определить при помощи равенств x = 3 и x = 4. Массу 1 можно определить при помощи равенства x + 3 = 4 (на одну чашу кладется изделие и гирька массой 3, на другую чашу – гирька массой 4). Массу 2 можно определить, например, по условию x < 3 (на одну чашу весов кладется изделие, на другую – гирька массой 3), а также проверив при помощи ранее описанного алгоритма, что x ≠ 1 . Массу 5 можно определить при помощи взвешивания x > 4.

Однажды утром во время традиционной инспекции картофельного поля кот Матроскин обнаружил на одном из кустиков колорадского жука. Придя в ужас, он тут же помчался расспрашивать дядю Фёдора (как наиболее образованного из друзей) о том, как эти жуки размножаются и как с ними бороться.

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно k колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

Зная координаты куста картофеля, на который Матроскин установил отпугиватель, посчитайте, через сколько часов после появления первого колорадского жука на поле он подействует. Матроскин поставил ловушку в первый час после появления жука на поле.

Входные данные
Вам даны три числа: x и y — координаты кустика картофеля, на который Матроскин установил отпугиватель, и k — параметр отпугивателя (1<=k<=10⁹, |x|<=10⁹, |y|<=10⁹  ). Тот из кустов, на котором был найден первый жук, имеет координаты (0, 0) . Координаты всех кустов поля не превосходят 10⁹+1 по модулю.

Выходные данные
Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры

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

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 

Городская площадь имеет размер n х m и покрыта квадратной плиткой размером 1 х 1. При плановой замене плитки выяснилось, что новой плитки недостаточно для покрытия всей площади, поэтому было решено покрыть плиткой только дорожку по краю площади, а в центре площади разбить прямоугольную клумбу (см. рисунок к примеру). При этом дорожка должна иметь одинаковую ширину по всем сторонам площади. Определите максимальную ширину дорожки, которую можно выложить из имеющихся плиток.

Формат входных данных
Первая и вторая строки входных данных содержат по одному числу n и m (3 ≤ n ≤ 2 x 10⁹  , 3 ≤ m ≤ 2 x 10⁹) - размеры площади.
Третья строка содержит количество имеющихся плиток t, 1 ≤ t < nm.
Формат выходных данных
Программа должна вывести единственное число - максимальную ширину дорожки, которую
можно выложить из имеющихся плиток.
 

Ввод	Вывод
6 7 38	2

Замечание
Пояснение к примеру. Площадь имеет размеры 6 х 7, из 38 плиток можно выложить дорожку шириной в 2 плитки.

Некоторые уроки в школе для Вани и Пети  очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности \(| p - q |\) еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

1. Пусть a, b — числа, НОД которых надо найти.

2. Если b = 0, то число a — искомый НОД.

3. Если b > a, то необходимо поменять местами числа a и b.

4. Присвоить числу a значение a – b.

5. Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: c, d (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

 

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

 

На вход программе подаются два целых числа n, m, каждое в отдельной строке \(0<n<=12, 0<=m<60\) , указывающие момент времени "n часов m минут". Определите наименьшее число полных минут, которое должно пройти до того момента, когда часовая и минутная стрелки ни циферблате совпадут, не обязательно на каком-то делении. Вещественную арифметику не использовать.

Задачу необходимо решить без использования условных операторов (в том числе без тернарного оператора ?: в С++) и\или циклов. Кроме того, нельзя использовать операции сравнения и логический (булевский) тип данных.

Примеры

№	Входные данные	Выходные данные
1	2 50	26
2	3 0	16

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

Ввод	Вывод
4321	4334

Имеется 10 колб с водой и известен объем воды в каждой из них. За одно «касание» можно взять одну колбу и часть воды (или всю воду) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество «касаний» можно уравнять объемы воды во всех колбах? Каждая колба может вместить любой объем воды.
Формат входных данных
Программа получает на вход 10 целых чисел a_i , каждое записанное в отдельной строке — объем воды в каждой из колб. Все числа — целые, от 0 до 100. 
Формат выходных
данных Выведите одно целое число — минимальное количество «касаний», за которое можно уравнять объемы воды во всех колбах.
 

Ввод	Вывод
30 26 2 3 4 5 6 7 8 9	2

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

В некоторой компании работают три сотрудника — Алексей, Виктор и Сергей. Их месячный оклад составляет A, B и C рублей соответственно. При этом Алексей работает на полную ставку, а Виктор и Сергей — на половину ставки, то есть работают вдвое меньше, чем Алексей.

По итогам месяца директор компании хочет распределить между этими сотрудниками премиальный фонд, который составляет N рублей. При этом директор хочет распределить премиальный фонд таким образом, чтобы итоговая зарплата (сумма оклада и премии) у этих сотрудников оказалась пропорциональна проведённому на работе времени, то есть зарплата Алексея должна оказаться ровно в два раза больше, чем зарплата Виктора и Сергея. Более формально, если премия Алексея составит x рублей, премия Виктора — y рублей, премия Сергея — z рублей, то A + x = 2 (B + y) = 2 (C + z), x + y + z ≤ N. При этом бухгалтерия требует, чтобы размер премии (как и размер оклада) выражался целым числом рублей, а директор хочет распределить максимально большую часть премиального фонда, то есть сумма x + y + z должна быть максимально возможной, не превышая при этом N.

Напишите программу, которая определит, какую премию нужно назначить каждому из сотрудников.
Программа получает на вход сначала три целых числа A, B, С, записанные в отдельных строках, — размеры окладов Алексея, Виктора и Сергея (A > 0, B > 0, С > 0). В четвёртой строке входных данных записано одно целое число N — размер премиального фонда (N ≥ 0).
Программа должна вывести три числа — размер премии Алексея, Виктора и Сергея. Если премиальный фонд нельзя распределить так, чтобы выполнялись требуемые условия, программа должна вывести одно число 0.
 

Ввод	Вывод	Примечание
7 3 4 12	5 3 2	С учетом премии зарплата Алексея составит 12 рублей, Виктора и Сергея — 6 рублей.
20 10 11 2	0	Добиться нужного соотношения премиальных выплат невозможно.

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

Бизнес-центр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. На каждом этаже работает ровно один сотрудник. Все сотрудники утром приезжают на парковку, которая расположена в подвальном помещении, на один этаж ниже первого. Бизнес-центр оборудован лифтом, который вмещает неограниченное число людей, но вредный лифтёр сегодня готов отвезти всех сотрудников только на один какой-то этаж.

У каждого сотрудника есть выбор: он может пойти вверх пешком по лестнице, на подъём на один этаж при этом будет уходить A секунд. Либо он может сесть в лифт, который отвезёт всех сотрудников на какой-то выбранный ими вместе этаж. Выйдя из лифта, сотрудник может подняться до своего этажа (также тратя A секунд на подъём на один этаж), либо спуститься до нужного этажа вниз, тратя B секунд на спуск на один этаж. Лифт тратит C секунд на подъём на один этаж.
Определите минимальное время, за которое все сотрудники разойдутся по своим этажам, если они наилучшим образом выберут этаж, на который едет лифт, и свою стратегию поведения (подниматься по лестнице или ехать на лифте, а затем идти по лестнице).

Первая строка входных данных содержит число N – количество этажей в бизнесцентре. Следующие три строки содержат числа A, B, С – время, необходимое сотруднику на подъём на один этаж, на спуск на один этаж и время, необходимое лифту на подъём на один этаж. Все числа – целые положительные, не превосходящие 2×10⁹ , при этом A ≥ B, A ≥ С. Программа должна вывести единственное целое число – минимальное время, за которое все сотрудники могут добраться до своего этажа.
 

Ввод	Вывод	Примечание
6 20 10 5	45	В здании 6 этажей. Сотрудник поднимается на один этаж за 20 секунд, спускается за 10 секунд. Лифт поднимается на один этаж за 5 секунд. Чтобы быстрее всем добраться до мест, лифт едет на 5-й этаж за 25 секунд. Сотрудник, который работает на 6-м этаже, выходит из лифта и поднимается за 20 секунд, всего его путь занимает 45 секунд. Сотрудник, работающий на 3-м этаже, едет на лифте и спускается на 2 этажа, это также занимает 45 секунд. Сотрудники с 4 и 5-го этажей также едут на лифте, их путь будет быстрее 45 секунд. На 1 и 2-й этажи сотрудники поднимаются пешком по лестнице за 20 и 40 секунд соответственно. Итого все сотрудники добираются до своих этажей не более чем за 45 секунд.