<ПРЕД Задача:
СЛЕД>
Задачу решили 227 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Кэширование значений функции

Time limit = 2 секунд(ы)

Memory limit = 64 Mb

Вы на грани вылета из института. И неудивительно — на французский Вы не ходили, по курсу теории групп и представлений Вы не захотели получать трояк и пошли на пересдачу, на которую не пришли, так как вместо этого пошли с подругой на фильм "Очарованная". Далее физкультура и ещё матан, теормех, ... Эх!!!

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

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

Нужно просто написать кэширующую версию функции get_user(int user_id), которая возвращает профайлы пользователей, хранящиеся в базе данных.

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

Когда функция вызывается с некоторым аргументом user_id необходимо проверить, есть ли пользователь с таким идентификатором в списке, и если есть, вернуть закэшированный профайл, предварительно переместив его в самое начало списка. Если такого пользователя нет, то нужно обратиться к базе данных и поместить пользователя в начало списка. Если размер списка стал больше M (а именно, M + 1), необходимо удалить из него последний элемент.

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

Вы хотите изучить, как меняется польза от кэширования в зависимости от значения M на последовательности реальных данных.

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

Вход Первая строка входа содержит размер кэша M, 0 < M ≤ 500000. Затем идёт последовательность целых чисел из диапазона [0,  20000000], разделённых пробельными символами. Количество чисел не больше 500000.

Выход Для каждого введённого числа необходимо вывести 0, если использовалось закэшированное значение, а иначе — 1. Другими словами, для каждого введенного числа нужно выводить 0, если среди последних M уникальных чисел его нет, а если есть — выводить 0. Цифры разделяйте пробелом.

Вход#1
10
1 2 3 4 5
Выход#1
1 1 1 1 1
Вход#2
4
7 7 7 7 7
Выход#2
1 0 0 0 0
Вход#3
5
1 2 3 1 4 5 6 7 2 5 1 3 2
Выход#3
1 1 1 0 1 1 1 1 1 0 1 1 0



Автор:
Артем Ворожцов, индивидуальное первенство МФТИ по программированию, 21 сентября 2008 года
20 сентября 2008

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.235.66.217