print960. Обобщённые матрёшки

printОбобщённые матрёшки

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Матрёшки представляют собой вложенные друг в друга деревянные куклы строго убывающих размеров. Пусть, например, самая внешняя кукла имеет размер 5, в неё вложена кукла размером 3, а в неё, в свою очередь, вложена кукла размером 2. Мы будем описывать такую матрёшку в виде последовательности чисел -5 -3 -2 2 3 5. В обобщённой матрёшке в куклу размером `m` может быть непосредственно вложено несколько кукол размером `n_1,\ n_2,\ …,\ n_k`, при этом должно выполняться условие `n_1\ +\ n_2\ +\ …\ +\ n_k\ <\ m`. Например, последовательность
-9 -7 -2 2 -3 -2 -1 1 2 3 7 9
описывает обобщённую матрёшку, состоящую из шести кукол размером 1, 2 (две штуки), 3, 7 и 9. Обратите внимание, что кукла размером 7 непосредственно содержит две куклы – размером 2 и размером 3. Последовательность же
-9 -7 -2 2 -3 -1 -2 2 1 3 7 9
не может описывать обобщённую матрёшку, так как кукла размером 2 не может быть вложена в куклу размером 1. Последовательность
-9 -7 -2 2 -3 -2 -1 1 2 3 7 -2 2 9
также не может описывать обобщённую матрёшку, так как две куклы размерами 7 и 2 не могут уместиться в куклу размером 9. Последовательность же
-9 -7 -2 2 -3 -1 -2 3 2 1 7 9
вообще является некорректной.
Напишите программу, определяющую, описывает ли числовая последовательность обобщённую матрёшку.
Ввод
Входной файл содержит последовательность ненулевых целых чисел. Числа не превосходят по абсолютной величине `10^7`.
Вывод
Запишите в выходной файл фразу ":-) Matrioshka!", если последовательность описывает обобщённую матрёшку, или фразу ":-( Try again." в противном случае.

Пример ввода 1

-9 -7 -2 2 -3 -2 -1 1 2 3 7 9

Пример вывода 1

:-) Matrioshka!

Пример ввода 2

-9 -7 -2 2 -3 -1 -2 2 1 3 7 9

Пример вывода 2

:-( Try again.

Пример ввода 3

-9 -7 -2 2 -3 -1 -2 3 2 1 7 9

Пример вывода 3

:-( Try again.

Пример ввода 4

-100 -50 -6 6 50 100

Пример вывода 4

:-) Matrioshka!

Пример ввода 5

-100 -50 -6 6 45 100

Пример вывода 5

:-( Try again.

Пример ввода 6

-10 -5 -2 2 5 -4 -3 3 4 10

Пример вывода 6

:-) Matrioshka!

Пример ввода 7

-9 -5 -2 2 5 -4 -3 3 4 9

Пример вывода 7

:-( Try again.
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading