База знаний гимназии 1 им. Барсукова

Это старая версия документа.

---

1. Сообщение

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, …, Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться. Ограничения: цифр не более 100.

Ввод: В первой строке содержится последовательность цифр.

Вывод: Вывести одно число.

2. Калькулятор

Ограничение по времени: 3 сек

Имеется калькулятор, который выполняет три операции:

• Прибавить к числу X единицу.
• Умножить число X на 2.
• Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.

Формат входных данных

Программа получает на вход одно число, не превосходящее 10⁶.

Формат выходных данных

Одно число: наименьшее количество искомых операций.

3. Лесенка

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

Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.

Формат входных данных. Вводится одно число N (1≤N≤150).

Формат выходных данных. Выведите искомое количество лесенок.

Назовем строку S правильной скобочной последовательностью, если она состоит только из символов '{', '}', '[', ']', '(', ')' и выполнено хотя бы одно из следующих трех условий:

1) S — пустая строка;

2) S можно представить в виде S=S1+S2+S3+…+SN (N>1), где Si — непустые правильные скобочные последовательности, а знак »+» обозначает конкатенацию (приписывание) строк;

3) S можно представить в виде S='{'+C+'}' или S='['+C+']' или S='('+C+')', где C является правильной скобочной последовательностью.

4. Скобки

Дана строка, состоящая только из символов '{', '}', '[', ']', '(', ')'. Требуется определить, какое минимальное количество символов надо вставить в эту строку для того, чтобы она стала правильной скобочной последовательностью.

Формат входных данных. В первой строке входного файла записана строка, состоящая только из символов '{','}', '[',']', '(',')'. Длина строки не превосходит 100 символов.

Формат выходных данных. Вывести в первую строку выходного файла единственное неотрицательное целое число — ответ на поставленную задачу.