Без имени

Задания школьного этапа всероссийской олимпиады школьников по информатике в 2016-2017 учебном году среди 9-11 классов.

Олимпиада по информатике для 9-11 классов проводится в компьютерной форме на базе сайта «Школа программиста» (https://acmp. ru/) со встроенной проверяющей системой. Для участия в олимпиаде необходимо зарегистрироваться на сайте и перейти в раздел "Архив задач", где на текущий момент Вам необходимо будет решить 5 задач различной сложности со следующими ID номерами:

0276 0045 0091 0360 0308 Разбиение на части

(Время: 1 сек. Память: 16 Мб Сложность: 21%)

Необходимо представить целое число N в виде суммы M примерно равных целых чисел. Будем считать, что числа примерно равны, если они отличаются друг от друга не более чем на единицу.

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

Во входном файле INPUT. TXT записаны два натуральных числа N и M через пробел, каждое из которых не превосходит 30000.

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

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

Примеры

№	INPUT. TXT	OUTPUT. TXT
1	13 4	3 3 3 4
2	72 8	9 9 9 9 9 9 9 9

Произведение цифр

Произведение цифр

(Время: 1 сек. Память: 16 Мб Сложность: 42%)

Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.

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

В единственной строке входного файла INPUT. TXT записано одно целое число N (0 ≤ N ≤ 109).

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

В выходной файл OUTPUT. TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

Примеры

№	INPUT. TXT	OUTPUT. TXT
1	10	25
2	13	-1
3	90	259

Две последовательности

Две последовательности

(Время: 1 сек. Память: 16 Мб Сложность: 29%)

Определим последовательности an и bn следующим образом: a1 = 2, a2 = 3, a3 = 4, a4 = 7, an = bn−1 + bn−3, n > 4, bn — последовательность чисел, не входящих в an, записанных в возрастающем порядке.

Таким образом, последовательность an будет выглядеть следующим образом: 2, 3, 4, 7, 13, 15,..., а последовательность bn – 1, 5, 6, 8, 9, 10,....

Ваша задача состоит в том, чтобы найти an и bn.

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

Входной файл содержит целое число n (1 ≤ n ≤ 10000).

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

В первой строке выходного файла выведите an, во второй – bn.

Примеры

№	INPUT. TXT	OUTPUT. TXT
1	4	7 8
2	10	25 16
3	6578	19731 9868

Максимальная тройка

Максимальная тройка

(Время: 3 сек. Память: 16 Мб Сложность: 33%)

В данной двумерной целочисленной таблице размером N Ч N требуется найти три элемента, сумма которых максимальна. При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.

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

Входной файл INPUT. TXT содержит в первой строке число N (1 < N ≤ 2000). В следующих N строках записано по N чисел – элементы таблицы. Элементы матрицы по абсолютной величине не превышают 100.

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

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

Пример

№	INPUT. TXT	OUTPUT. TXT
1	3 1 1 1 2 2 1 2 1 0	6

Вода

Вода

(Время: 1 сек. Память: 16 Мб Сложность: 70%)

Имеется три ведра, емкости которых известны и не равны. Самое большое ведро полное, остальные пусты. Требуется добиться, чтобы в самом большом ведре был заданный объем воды. За один шаг вода переливается из одного ведра в другое до тех пор, пока либо не закончится вода в ведре-источнике, либо не наполнится доверху вода в ведре-получателе.

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

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

Во входном файле INPUT. TXT записаны 4 числа: емкости ведер B1, B2, B3 (1000 ≥ B1 > B2 > B3 > 0) и требуемое количество воды T в первом ведре (B1 > T > 0).

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

В выходной файл OUTPUT. TXT выведите либо минимальное количество переливаний, либо если задача не имеет решения, то слово IMPOSSIBLE.

Примеры

№	INPUT. TXT	OUTPUT. TXT
1	10 8 4 4	3
2	10 8 4 5	IMPOSSIBLE