Страница: << 14 15 16 17 18 19 20 >> Отображать по:
#909
Восстановление скобок
  

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

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

На вход программы поступает заданный шаблон длиной не более 80 символов.

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

Выведите искомое количество способов восстановления скобок. Исходные данные будут таковы, что это количество не превзойдет \(2\times 10^9\).

Примеры
Входные данные
???????????
Выходные данные
0
#911
Дизайнерский лифт
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:
- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж
Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

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

Первая строка содержит число N – высоту небоскреба (1 <= N <= 500 000).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

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

Выведите единственное число — оценку адекватности Артемия Индюкова.

Примеры
Входные данные
15
4 7 9
Выходные данные
9
#912
Без трех единиц
  

Определите количество последовательностей из нулей и единиц длины N (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.

Вводится натуральное число N, не превосходящее 40.

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

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231 − 1.

Примеры
Входные данные
3
Выходные данные
7
#913
Взрывоопасность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Одно число \(1\le N\le20\).

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

Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

Примеры
Входные данные
2
Выходные данные
3
#914
Взрывоопасность-2
  

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров \(N\) определить число безопасных стопок.

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

Одно число \(1\le N\le20\).

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

Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, AC, BA, BB, BC, CA, CB и CC. Стопки типа AA являются взрывоопасными.

Примеры
Входные данные
2
Выходные данные
8
Страница: << 14 15 16 17 18 19 20 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест