Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Identity Theft#90279

**Замечание: Время на тест и ограничение по памяти для этой задачи 3сек и 512MB, что, соответственно, в 1.5 и 2 раза больше чем по умолчанию.**

Каждая из \(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона имеет свой ID-номер в виде битовой строки (строки соcтоящей из символов '0' и '1'). Беси, старейшая корова, помнит ID-номера всех коров и любит спрашивать у коров их ID-номера.

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

ФД хочет избавиться от последней ситуации и добавить несколько битов к некоторым ID-номерам. За одну секунду он может добавить один бит в конец ID-номера любой коровы. Определите минимальное количество времени, которое потребуется чтобы избежать карантина по совпадению правильного ID-номера.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\), количество коров на ферме у ФД.

Далее следуют \(N\) строк. \(k\)-я строка содержит битовую строку, равную ID-номеру \(k\)-ой коровы.

Никакой и ID-номеров не пустой, и общая длина всех ID-номеров не более \(10^6\).

ФОРМАТ ВЫВОДА (на экран / stdout):

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

Бор

—Войти и решать

Auto-Complete#89922

Problem 1: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число K_i, которое означает, что приложение должно найти K_i-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести K_i-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число K_i за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – K_i-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем K_i завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.

Бор

—Войти и решать

Auto-Complete#89916

Problem 2: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число K_i, которое означает, что приложение должно найти K_i-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести K_i-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число K_i за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – K_i-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем K_i завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.

Бор

—Войти и решать

First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

Бор графы Топологическая сортировка

✓ 1✗ 1—Войти и решать

Контроль доступа#55448

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

Каждый IP-адрес − это 4-байтный номер, который записан байт за байтом в десятичной записи. Байты разделены точками следующим образом: <<byte0.byte1.byte2.byte3>> (кавычки добавлены для ясности). Каждый байт записывается как десятичное число от 0 до 255 (включительно) без ведущих нулей. IP-адреса организованы в IP-сети. IP сети описывается двумя 4-байтовыми числами - сетевым адресом и маской сети. И сетевой адрес и маска сети записаны в той же форме, что и IP-адреса. Для того чтобы понять смысл сетевого адреса и маски сети рассмотрим их двоичное представление. Двоичное представление IP адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (от старших к младшим), затем по 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3.

IP сеть содержит 2N IP-адресов, где 0≤N≤32. В маске сети первые 32–N бита установлены в единицы, и последние N бит установлены в ноль. Сетевой адрес имеет произвольные 32–N первых бит, а последние N бит установлен в ноль. IP сеть содержит все IP-адреса, первые 32−N бит которых равны 32–N
первых бит сетевого адреса с произвольными N последними битами. Например, IP сеть с сетевым адресом 194.85.160.176 и сетевая маска 255.255.255.248 содержит 8 IP-адресов, с 194.85.160.176 по 194.85.160.183 (включительно).

IP сети, как правило, обозначается как <<byte0.byte1.byte2.byte3/S>>, где <<byte0.byte1.byte2.byte3>> − сетевой адрес, S − это число бит, установленных в единицу в маске сети. Например, IP сети из предыдущего абзаца обозначается как 194.85.160.176/29. Список контроля доступа содержит упорядоченный список правил. Каждое правило имеет одну из следующих форм:

deny from <IP network> − запрещает доступ к ресурсу для любого IP из заданной сети.

deny from <IP address> − запрещает доступ к ресурсу для указанного IP-адреса.

allow from <IP network> − разрешает доступ к ресурсу для любого IP из заданной сети.

allow from <IP address> − разрешает доступ к ресурсу для указанного IP-адреса.

Когда кто-нибудь обращается к какому-либо ресурсу, первым делом проверяется IP-адрес обращающегося по списку контроля доступа. Правила проверяются в том порядке, в котором они перечислены, и применяется первое выполняющееся правило. Если ни одно из правил не соответствует IP-адресу запрашивающей стороны, то доступ предоставляется.

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

Входные данные
Первая строка ввода содержит число N − количество правил в списке контроля доступа (0≤N≤100000). Следующие N строк содержат правила по одному в строке. IP сеть всегда записывается как <<byte0.byte1.byte2.byte3/S>>. Следующая строка содержит число M − количество IP адресов, которые следует проверить (0≤M≤100000). Следующие M строк содержат по одному IP адресу в строке.

Выходные данные
Для каждого из M IP-адресов выведите <<A>>, если доступ будет предоставлен, и <<D>> иначе. Все символы следует выводить слитно, не разделяя пробелами.

Бор Дерево отрезков, RSQ, RMQ

✓ 1✗ 0—Войти и решать

T2005#53605

Клавиатура сотового телефона выглядит так:

1 — пробел	2 — abc	3 — def
4 — ghi	5 — jkl	6 — mno
7 — pqrs	8 — tuv	9 — wxyz

Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.

Если для ввода какого-то слова нужно нажать последовательность клавиш, которая может являться началом какого-то другого слова, то после ввода этого слова нужно нажать клавишу 1, что соответствует вводу пробела. При вводе пробела считается, что вы ввели все слово целиком (а не только какое-либо его начало). Если после ввода пробела оказалось, что в словаре такой последовательности клавиш удовлетворяет несколько слов, подставляется первое из них в алфавитном порядке. Если (опять же после ввода пробела) оказалось, что в словаре нет слова, которое может быть введено такой последовательностью клавиш, то все, что было введено после предыдущего пробела (введенного или автоматически подставленного, или, если в тексте ранее не встречалось ни одного пробела — от начала текста) удаляется. Если после ввода пробела (как нажатием "1", так и автоподстановкой) или в начале текста нажимается клавиша "1", то ее нажатие игнорируется.

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

Примечание: в тексте используются только маленькие латинские буквы и символ пробел.

Входные данные
Сначала на вход программы поступает число N — количество слов в словаре (2≤N≤100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.

Далее вводится число M — количество нажатий клавиш (1≤M≤20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".

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

Примечание:

2
a
z
2
5 1

Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел

Бор Задача на реализацию Конечные автоматы

✓ 2✗ 19—Войти и решать