НачалоПодразделы
Дата и время
22/12/2024 15:44:34
Лето 4
A. Олимпиада B. Оффшорное программирование C. Многоугольник D. Стена E. Сортировка списка F. Разбиение матрицы G. Обобщённые матрёшки H. Узелки I. Цепные дроби J. Унарная система счисления K. Башня
G. Обобщённые матрёшки
Стеки, очередиОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 4G) |
| 09/07/2008 | Лето 2008 - 4 (G) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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.
