Встроенная очередь команд

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Встроенная очередь команд (Native Command Queuing, NCQ) - это технология, использующаяся в SATA-устройствах для повышения быстродействия. NCQ позволяет устройству накапливать запросы, оптимизировать порядок их выполнения с учётом внутренней архитектуры устройства (минимизация количества перемещений головок, простоя в ожидании нужного сектора на треке). В этой задаче мы пренебрежем значением ряда факторов и будем учитывать только лишь время перемещения считывающей головки SATA-устройства. Изначально будем считать, что головка расположена в позиции 0. Скорость ее перемещения равна 1 (одна позиция в миллисекунду). Вам заданы команды в виде (x_i, t_i), где x_i - позиция из которой надо прочесть (или записать) информацию, а t_i - время поступления запроса. Запросы не обязательно должны быть обработаны в порядке их поступления. Главное, чтобы головка устройства заняла позицию x_i в момент времени t_i или позже. Время чтения/записи будем считать пренебрежимо малым. Найдите наименьшее время, за которое устройство обработает все поступившие команды.

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

В первой строке входного файла записано целое число n (1 ≤ n ≤ 2000) - количество поступивших команд. Далее перечислены сами команды - по одной в строке. Команды задаются парами целых чисел x_i, t_i (-10⁶ ≤ x_i ≤ 10⁶; 0 ≤ t_i ≤ 10⁶).

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

Выведите единственное число - наименьшее время обработки всех команд.

Пример(ы)

input.txt	output.txt
2 4 5 1 7	8

 

input.txt	output.txt
1 1 1000	1000

Неточный поиск

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Задача поиска заданной подстроки в тексте имеет неоспоримое значение и ее решение реализовано в большинстве языков программирования в виде функциональности стандартной библиотеки. Однако, зачастую необходимо решать задачу неточного поиска. Назовем расстоянием между двумя строками a и b наименьшее количество операций, необходимое для того, чтобы строку a перевести в строку b. Разрешенные операции: замена любого символа любым другим, вставка любого символа в произвольную позицию в строке и удаление произвольного символа. Например, расстояние между строками "кот" и "конь" равно 2. Ваша задача в заданном тексте найти подстроку, которая имеет расстояние до заданной не более d.

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

В первой строке входного файла записана строка в которой следует осуществлять поиск. Длина строки не менее 1 символа и не более 2*10⁶. Далее содержится строка, содержащая образец поиска. Его длина не менее 1 символа и не более 50 символов. Заданные строки содержат строчные и прописные буквы латинского алфавита и цифры. Последняя строка содержит целое число d (0 ≤ d ≤ 50) - наибольшее расстояние между образцом поиска и искомой подстрокой.

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

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

Пример(ы)

input.txt	output.txt
thisisthetesttext tester 2	9 5

 

input.txt	output.txt
thesecondsampletestforproblemaboutthestrings pattern 4	12 5

505. Клуб "Двоичный кот"

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

В первой строке входного файла записана пара целых чисел n и m (1 ≤ n ≤ 1000; 1 ≤ m ≤ 1000), где n - количество записей в журнале охраны, а m - количество запросов спецслужбы. Далее в n строках содержатся описания записей в формате "hh:mm:ss имя", где hh:mm:ss время в стандартном формате (ровно 8 символов), а "имя" это имя человека зашедшего или вышедшего из клуба. Имя состоит из строчных или прописных букв латинского алфавита и имеет длину от 1 до 16 символов включительно. Записи расположены в порядке неубывания времен событий. Далее содержится m строк. Каждая строка содержит запись вида "hh:mm:ss" задающую момент времени, которым интересуются сотрудники госбезопасности. Все времена во входном файле ограничены одними сутками.

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

Выведите m строк в выходной файл. Каждая строка должна содержать список людей, которые находятся в клубе в соответствующий момент времени. Список должен начинаться с количества людей, а затем должна следовать последовательность имен. Элементы списка следует разделять пробелами. Имена в списках можно выводить в любом порядке. Так как сотрудники госбезопасности не хотят упустить кого-либо из списка, то если именно в эту секунду посетитель зашел в клуб, считайте, что он находится в клубе в эту секунду. Если посетитель именно в эту секунду вышел из клуба, то следует считать, что он его еще покинуть не успел, то есть посетитель еще находится в клубе.

Пример(ы)

input.txt	output.txt
4 2 00:00:19 Mike 00:00:26 Kate 02:42:11 Mike 02:42:11 Kate 00:00:20 04:00:00	1 Mike 0

 

input.txt	output.txt
7 3 06:00:00 Athos 06:00:00 Porthos 06:00:00 Aramis 07:00:00 Athos 07:00:00 Porthos 07:00:00 Aramis 07:10:00 dArtagnan 06:00:00 06:30:00 07:00:00	3 Aramis Athos Porthos 3 Aramis Athos Porthos 3 Aramis Athos Porthos