Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 32 33 34 35 36 37 38 >> Отображать по:
#3900
Система защиты
  
Темы: [Хеш]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

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

Система контроля после сканирования получает изображение в виде цифрового массива N × M, в котором цифра 1 соответствует черному цвету, а цифра 0 — белому. Затем система ищет контрольные элементы в полученном массиве.

Контрольный элемент представляется массивом размером L × L цифр, каждая из которых равна 0 или 1. В библиотеке — K контрольных элементов. Элемент библиотеки должен точно совпадать с какой-либо частью изображения. При сравнении изображения и контрольных элементов повороты не допускаются.

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

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

В первой строке входных данных записаны через пробел числа N, M, K, L (N ≤ 100 000, M ≤ 1 000, L ≤ 50, K ≤ 20).

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

В последующих N строках записаны по M цифр в каждой, соответствующих изображению.

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

Выходной файл должны состоять из К строк.

В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 — если элемент не обнаружен).

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

Примечание

Каждый тест оценивается независимо от других.

Примеры
Входные данные
10 10 2 3
010
111
010

100
011
001

0010010010
0100001111
0000000100
0000100000
0001111000
0000101000
0100000010
0001000110
0011111000
0101000000
Выходные данные
1 2
2 1
#111114
Волшебные грибы
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

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

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

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

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

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

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

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

Примечание

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

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

Примеры
Входные данные
8
1
2
3
4
5
6
7
8
Выходные данные
Yes
Yes
Yes
No
Yes
No
No
Yes
#111123
Доставка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Город Прямой Рог, который пока что не находится на территории Российской Федерации, представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы. В компании работает два курьера. В начале рабочего дня заказы распределяются между ними, и каждый отправляется по своему маршруту. Компании необходимо так спланировать распределение заказов, чтобы суммарное расстояние, которое будет пройдено курьерами на момент выполнения последнего заказа, была минимальным. Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.

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

Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100 000) — количество заказов. Далее следует N строк, каждая из которых содержит одно целое число — расстояние от офиса до адресата. Если расстояние положительное — то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 108.

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

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

Примеры тестов

Входные данные
5
1
-1
2
-2
3
Выходные данные
5

Подзадача 1.
\(N \le 100\). Решение оценивается в \(20\) баллов.
Подзадача 2.
\(N \le 2\,000\). Решение оценивается в \(30\) баллов.
Подзадача 3.
Дополнительные ограничения отсутствуют. Решение оценивается в \(50\) баллов.

#111225
Мозаика
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

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

Примечание

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

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

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

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

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

Примеры
Входные данные
4
2 2
1 2
1 3
2 3
2
2 3
2 4
Выходные данные
0 0
4 2
#111226
Театр начинается с актеров
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Участники олимпиады пришли в казанский театр на спектакль, где играют N неизвестных для них актеров. В фойе театра висят портреты всех актеров труппы, которая в полном составе задействована в спектакле. Портреты не подписаны. Зрителям раздали программки, в которых для каждого действия спектакля приводится список фамилий участвующих в нем актеров, но не указаны их роли. Театрал Виталий решил узнать, как выглядит каждый из актеров, упомянутых в программке. Для этого в антракте после каждого действия он выходил в фойе и сопоставлял портреты с увиденными актерами. Требуется написать программу, которая по заданному числу актеров N и списку фамилий актеров, участвующих в каждом из M действий, определяет номер действия, после которого впервые становится возможным установить соответствие между фамилией актера из программки и его портретом.

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

Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров Ki, участвующих в i–ом действии (1 ≤ Ki ≤ N, K1 + K2 + ... + KM ≤ 100 000), а затем Ki различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.

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

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

Примечание

В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1. Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.

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

  1. (оценивается в 30 баллов) Количество актеров N не превосходит 100, количество действий M не превосходит 100, K1 + K2 + ... + KM ≤ 100.

  2. (оценивается в 30 баллов) Количество актеров N не превосходит 10 000, количество действий M не превосходит 10 000, K1 + K2 + ... + KM ≤ 10 000.

  3. (оценивается в 40 баллов) Количество актеров N не превосходит 100 000, количество действий M не превосходит 100 000, K1 + K2 + ... + KM ≤ 100 000.

Примеры
Входные данные
3 3
2 1 2
2 3 2
2 1 2
Выходные данные
2 2 1
Входные данные
5 3
3 1 2 3
3 2 1 3
2 1 3
Выходные данные
0 3 0 0 0
Входные данные
4 3
1 1
1 3
1 2
Выходные данные
1 3 2 3
Страница: << 32 33 34 35 36 37 38 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест