Страница: << 11 12 13 14 15 16 17 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

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

(ABC)(пауза)(ABC)

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

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.

Мобила

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

В первой строке задана длина оригинального сообщения \(N\). Вторая строка содержит полученное SMS-сообщение. 1 <= \(N\) <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

Вывести число сообщений из \(N\) букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.

Примеры
Входные данные
8
ADGJMPTW
Выходные данные
1
Входные данные
9
ADGJMPTW
Выходные данные
0
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.

Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.

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

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


Примеры
Ввод 1          Ввод 2            Ввод 3
3  4 9 1  3     4  1 2 2 7  3     5  3 4 8 1 7  2
Вывод 1         Вывод 2           Вывод 3
14              5                 18
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Обеденный перерыв Гомера Симпсона составляет \(T\) миллисекунд. Один гамбургер Гомер съедает за \(N\) миллисекунд, один чизбургер - за \(M\). Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая \(T\). При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: \(1 \le M, N, T \le 1 000 000\), все числа целые.

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

В первой строке находятся три числа - \(M\), \(N\) и \(T\), разделённые пробелами.

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

Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.

Примеры
Входные данные
1 2 1000
Выходные данные
1000
Входные данные
2 1 1000
Выходные данные
1000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

  • Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
  • Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
  • Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.

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

Ограничения: длина исходной последовательности от 1 до 100.

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

В первой строке находится последовательность символов от A до Z.

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

В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.

Примеры
Входные данные
AAAAAAAAAABABABCCD
Выходные данные
9(A)3(AB)CCD
Входные данные
NEERCYESYESYESNEERCYESYESYES
Выходные данные
2(NEERC3(YES))
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определённого числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцеплений на каждом конце. У компании также есть один локомотив.

Сцепления и для локомотива, и для вагонов обозначены буквой A или B. Повернуть вагон или локомотив противоположной стороной невозможно.

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

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

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

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

В первой строке через пробел N - число вагонов, находящихся в распоряжении компании, и K - требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцеплений вагонов. Описания даны как AB, AA, BB или BA.

Ограничения: 1 <= K <= N <= 40.

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

В первой строке выводится слово "YES", если можно сформировать хотя бы один поезд, или "NO" - в противном случае.

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

Примеры
Входные данные
4 4
AB
AA
AB
BA
BA
Выходные данные
YES
2
Входные данные
4 4
BA
AA
AB
BA
BA
Выходные данные
NO

Страница: << 11 12 13 14 15 16 17 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест