НачалоПодразделы
Другие разделы
| 954. Олимпиада |
| 955. Оффшорное программирование |
| 956. Многоугольник |
| 957. Стена |
| 958. Сортировка списка |
| 959. Разбиение матрицы |
| 961. Узелки |
| 962. Цепные дроби |
| 963. Унарная система счисления |
| 964. Башня |
Дата и время
22/12/2024 15:12:56
960. Обобщённые матрёшки
Обобщённые матрёшки
Стеки, очередиОлимпиадные задачи на русском языке
| 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.
