Страница: << 27 28 29 30 31 32 33 >> Отображать по:
#3590
Палиндромика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.

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

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

В единственной строке входного файла содержится строка, предложенная игрокам. Строка состоит из маленьких латинских букв. Длина строки не превышает 250 символов.

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

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

Примеры
Входные данные
3
uho
Выходные данные
1
Входные данные
6
ababab
Выходные данные
2
#3672
Форд Транкингс и язык Велулу
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Мистер Форд Транкингс, известный археолог, недавно обнаружил в самом сердце Африки остатки загадочного поселения. Через несколько недель исследования он и его коллеги поняли, что они нашли нечто необычное. Племена Велулу, которые жили там 20 000 лет назад, по-видимому, достигли высокого уровня развития. У них даже был алфавит! Но большинство из них стало жертвой ледникового периода и все их културные достижения были утрачены. Только несколько счастливчиков из племени выжили и попытались возрадить исчезнувшую цивилизацию. Теперь они известны под именем грозных зусулов, но об этом в другой раз...

Нынешняя задача состоит в расшифровке текстов Велулу. Основная проблема заключается в том, что в их алфавите нет пробелов. Поэтому все тексты слипаются в одну последовательность букв, которые сложно разобрать.

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

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

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

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

Первая строка входного файла содержит числа \(N\), \(M\) и \(K\), где \(1 \leq N \leq 5000\) — количество слов в велульском словаре, \(1 \leq M \leq 10\) — количество правил построения предожения, а \(1 \leq K \leq 10\) — количество различных частей речи.

В вельском языке не так много букв. Так что археологи закодировали их маленькими латинскими буквами. В каждой из \(N\) следующих строк содержится слово (не длиннее 20 символов), затем число \(k_i\) (\(1 \leq k_i \leq 10\)) — количество частей речи, которыми может быть это слово, а затем \(k_i\) чисел \(a_{ij}\) обозначающие допустимые части речи. Все числа \(a_{ij}\) даны в возрастающем порядке. Слова в словаре даны в произвольном порядке (не успели упорядочить). Каждое слово встречается в словаре только один раз.

Следующие \(M\) строк содержат правила конструирования предожений. Каждое правило описывается количеством слов в предложении \(l_i\) (\(1 \leq l_i \leq 10\)) и, затем, перечислены \(l_i\) чисел, являюзихся идентификаторами частей речи. Правила не повторяются.

Последняя строка ввода содержит текст, который надо расшифровать. Текст не пуст и его длина не превышает 1000 символов.

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

Первая строка должна содержать количество вариантов расшифровки. Если их больше чем \(10^{18}\) выведите строку «TOO MANY» вместо количества.

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

Если вариантов несколько — выведите любой из них.

Примеры
Входные данные
5 2 2
ba 1 2
za 2 1 2
a 2 1 2
caba 1 1
ab 1 1
2 1 2
3 2 2 1
abazabacaba
Выходные данные
2
a ba. za ba caba.
#3674
Игра на бирже
  
#3711
Большой, белый, очень прямоугольный
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

В прямоугольной таблице клетки раскрашены в белый и черный цвета. Найти в ней прямоугольную область белого цвета, состоящую из наибольшего количества ячеек.

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

Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.

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

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

Примеры
Входные данные
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
Выходные данные
9
#3717
Числа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность чисел a1, a2, ..., an. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Пример начальной последовательности:

1 50 51 50 1

удаляем четвертое число, штраф 50·(1 + 51) = 2600, получаем

1 50 51 1

удаляем третье число, штраф 51·(50 + 1) = 2601, получаем

1 50 1

удаляем второе число, штраф 50·(1 + 1) = 100.

Итого, штраф 5301.

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

В первой строке входного файла расположено одно число n (1 ≤ n ≤ 100) — количество чисел в последовательности.

Во второй строке находятся n целых чисел a1, a2, ... an; никакое из чисел по модулю не превосходит 100.

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

Выведите в выходной файл одно число — минимальный суммарный штраф.

Примеры
Входные данные
5
1 50 51 50 1
Выходные данные
5301
Страница: << 27 28 29 30 31 32 33 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест