Страница: << 5 6 7 8 9 10 11 >> Отображать по:

#3395

Снова в космос

Темы: [Хеш]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2011, Задача C ]

К 50-летию первого пилотируемого полета в космос решено создать новый тип космического корабля многоразового использования “Восторг”. Прямоугольная часть его корпуса (далее прямоугольник) должна быть облицована квадратными термозащитными плитками разных цветов одного и того же размера. Прямоугольник состоит из \(r\) рядов по \(c\) плиток в каждом. Плитки должны образовывать заданный рисунок.

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

Главный конструктор хочет выбрать такой размер панели \(a\times b\) и сдвиг \(s\), чтобы этими панелями можно было выложить заданный рисунок, и площадь панели была минимальна.

Пример панелей с \(a = 2\), \(b = 3\), \(s = 1\).

Требуется написать программу, которая по заданному расположению плиток в прямоугольнике рассчитывает размеры минимальной по площади панели, которую можно использовать при его облицовке, а также величину сдвига вправо (\(0 \leq s < b\)) каждого следующего ряда относительно предыдущего.

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

Первая строка входного файла содержит два целых числа: \(r\) и \(c\) – размеры прямоугольника в плитках. В последующих \(r\) строках указаны цвета плиток фрагмента. Каждый из \(k \leq 26\) цветов обозначен одной из первых \(k\) прописных букв латинского алфавита. Гарантируется, что для этого прямоугольника можно подобрать панель размера \(a\times b\), такую, что \(2a \leq r\) и \(2b \leq c\).

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

ВВ выходной файл необходимо вывести три целых числа \(a\), \(b\) и \(s\), удовлетворяющих условиям задачи. Если решений несколько, разрешается вывести любое из них.

Комментарий

Во втором примере облицовка прямоугольника соответствуют следующему рисунку (выступающие за границы прямоугольника части панелей не показаны):

Подзадачи и система оценки

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

Подзадача 1 (10 баллов)

В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 20.

Подзадача 2 (15 баллов)

В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 200.

Подзадача 3 (20 баллов)

В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 1961.

Подзадача 4 (10 баллов)

Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 20.

Подзадача 5 (15 баллов)

Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 200.

Подзадача 6 (15 баллов)

Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 500.

Подзадача 7 (15 баллов)

Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 1961.

Примеры

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

2 4
ABAB
ABAB

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

1 2 0

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

5 7
DCADCAD
BABBABB
ADCADCA
BBABBAB
CADCADC

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

2 3 1

#3866

Поврежденный XML

Темы: [Простые задачи на перебор] [Стек]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2012, 1 день, Задача C ]

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.

XML-строка называется корректной, если она может быть получена по следующим правилам:

Пустая строка является корректной XML-строкой.
A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

<a></a>

являются корректными XML-строками, а такие строки как:

<a></b>

<a><b>

не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

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

Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).

Строка во входном файле заканчивается переводом строки.

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

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

Примеры входных и выходных файлов

input	output
<a></b>	<a></a>
<a><aa>	<a></a>
<a><>a>	<a></a>
<a/</a>	<a></a>

#3871

«Abracadabra»

Темы: [Хеш] [Бор] [Бинарный поиск в массиве] [Строки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2012, 2 день, Задача D ]

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t₁, t₂, …, t_n и набор из m строк-образцов s₁, s₂, …, s_m. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

Последующие n строк содержат слова t₁, t₂, …, t_n_, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 10⁶. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

Последующие m строк содержат строки-образцы s₁, s₂, …, s_m, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 10⁶. Никакая строка-образец не является пустой строкой.

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

Выходной файл должен содержать m чисел, по одному на строке.

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

Система оценки

Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.

Примеры

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

4
abacaba
abracadabra
aa
abra
3
a
abra
abac

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

4
2
0

#111114

Волшебные грибы

Темы: [Хеш]

Источники: [ Личные олимпиады, Индивидуальная олимпиада по информатике и программированию (ИОИП), Заключительный этап 2012, Задача C ]

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

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

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

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу a_i — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.

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

Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.

Примечание

Решения, работающие для чисел, не превышающих 2⁶³ - 1, будут оцениваться из 30 баллов.

Решения, также работающие для входных данных, не превышающих 15 килобайт, будут оцениваться из еще 30 баллов.

Примеры

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

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

Yes
Yes
Yes
No
Yes
No
No
Yes

#111225

Мозаика

Темы: [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача E ]

Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

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

В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа A_i и B_i , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ A_i, B_i ≤ 10⁹, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N₁ и N₂ – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).

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

Выходной файл должен содержать K строк, каждая из которых содержит два разделённых пробелом числа – номера элементов мозаики, образующих негармоничную пару в соответствующем наборе. Если решений несколько, можно вывести любое из них. Если в наборе негармоничная пара отсутствует, требуется вывести в соответствующей строке 0 0.

Примечание

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

(оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.
(оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.
(оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.
(оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

Примеры

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

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

0 0
4 2

Страница: << 5 6 7 8 9 10 11 >> Отображать по:

Выбрано

Отменить

Добавить в контест