Задачи (сложные)

Задача 1. Запросы сумм

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

В первой строке файла содержатся два числа: количество элементов в
массиве V: 10 ≤ N ≤ 500000 и количество запросов 1 ≤ M ≤ 500000. Каждый
элемент массива лежит в интервале [0…232).

Каждый запрос – отдельная строка, состоящая из кода запроса, который
может быть равен 1 или 2 и аргументов запроса.

Запрос с кодом один содержит два аргумента, начало L и конец отрезка
R массива. В ответ на этот запрос программа должна вывести значения суммы
элементов массива от V[L] до V[R] включительно.

Запрос с кодом два содержит тоже два аргумента, первый из которых
есть номер элемента массива V, а второй – его новое значение.

Количество выведенных строк должно совпадать с количеством
запросов первого типа.



Задача 2. Поиск множеств

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

В первой строке файла содержится три числа: N – количество эталонных
множеств, M – размер каждого из множеств и K – количество пробных
множеств.

Каждое из множеств содержит целые числа от 0 до 109, числа могут повторяться.

Требуется для каждого из пробных множеств вывести в отдельной
строке цифру ‘1’, если это множество в точности совпадает с каким-либо из
эталонных множеств и цифру ‘0’, если оно ни с одним не совпадает, то есть
выведено должно быть в точности K строк.

5 ≤ N ≤ 50000
3 ≤ M ≤ 1000
5 ≤ K ≤ 50000



Задача 3. Телефонная книга

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

Необходимо разработать программу, которая является промежуточным
звеном в реализации телефонной книги. На вход подается N ≤ 1000 команд
вида

ADD User Number
DELETE User
EDITPHONE User Number
PRINT User

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

Необходимо вывести протокол работы телефонной книги




Задача 4. Анаграммы

Ограничение по времени: 0.5 секунд
Ограничение по памяти: 256 мегабайт

Как известно, анаграммами называются слова, которые могут
получиться друг из друга путем перестановки букв, например LOOP, POOL,
POLO. Будем называть все слова такого рода комплектом.

На вход программы подается число слов 1 ≤ N ≤ 100000. В каждой из
очередных N строк присутствует одно слово, состоящее из заглавных букв
латинского алфавита. Все слова имеют одинаковую длину 3 ≤ L ≤ 10000.

Требуется определить число комплектов во входном множестве.

Формат входных данных:

N
W1
W2
…
WN

Формат выходных данных:

NumberOfComplects




Задача 5. Кеширующий сервер

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


Дормидонт работает в компании, которая занимается обработкой
больших данных. Обрабатываемые данные находятся где-то в распределенной
системе. Количество различных данных в системе ограничено и каждое
данное имеет свой номер. Эти данные регулярно требуются различным
клиентам и, поскольку время обращения к ним достаточно велико, для
ускорения обработки информации Дормидонту поручено написать часть
middlware — сервер-посредник, к которому и обращаются теперь клиенты за
данными. Так как система — распределенная, а сервер — нет, все требуемые
данные на сервер не помещаются, но он имеет возможность запоминать
результаты своих запросов к распределенной системе. Для этого на сервере
выделена ограниченная память на N запросов. Важно, что клиент не имеет
возможности обращаться к распределенной системе и результат запроса к
распределенной системе всегда должны оказаться на сервере.

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

Формат входных данных:

На вход программы подается размер памяти под кеширование запросов
1 ≤ N ≤ 100000, количество запросов 1 ≤ M ≤ 100000 и ровно M запросов с
номерами 0 ≤ Ri ≤ 1018 . Количество различных номеров запросов ограничено
и не превосходит 100000.

Формат выходных данных:

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

0

	Комментарий модератора
	Правила форума: ... 4.3 Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят. ... 5.16 Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос - одна тема. Тема закрыта.

0