Архив форума

не понимаю только как при такой структуре данных отслеживать, какой запрос был дан раньше? туплю? :)))так я тоже "за", но начинать там все придется с нуля:))))

При чем тут "раньше"? Надо лишь число запросов, больших заданной величины быстро находить. Удалять можно всегда любой из подходящих запросов.

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

P.S. Кстати, где можно найти разборы задач? Интересно же, как их предполагалось решать:)))

Может сказка с реального контеста поможет Илье перестать тупить :):
(особенно второй абзац)

Задача J. Аукцион
Идея — П. Атнашев
Подготовка — П. Атнашев, П. Егоров

В стране очередное помешательство. Все хотят смотреть новые серии модного сериала как можно раньше. Даже раньше, чем их покажут по платным каналам, не говоря уж об обычных. Сейчас это возможно: делаешь заказ, и тебе будут приходить диски с очередной серией на пару дней раньше. Но диски в дефиците – их просто не успевают тиражировать. Поэтому их продают на электронных аукционах. Зрители заявляют цену, по которой они готовы получать новые серии (от 0.01 до 10000.00 рублей). За неделю до выхода новой серии появляется партия дисков (K штук) и их выставляют на аукцион по цене X рублей. Первые K покупателей, предложивших цену X или большую, получают по одному диску. Если таких покупателей оказывается меньше, чем K, то непроданные диски отправляются на свалку – все равно эту серию скоро покажут по телевидению.

Вне зависимости от того, достался ли покупателю диск из очередной партии, его заявка остается в силе и действует до тех пор, пока он в явном виде не отзовет ее.

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

Ввод. Во входных данных содержится журнал, в каждой строке которого находится описание одной операции. Операции бывают трёх видов:
- BID X – покупатель делает заявку на покупку диска по цене X рублей.
- DEL X – покупатель снимает заявку на покупку по цене X рублей.
- SALE X K – продавец выставляет на продажу K дисков по цене X рублей.

Максимальное количество операций в журнале — 100000. Последняя строка журнала содержит команду 'QUIT'. Журнал не содержит внутренних противоречий (например, первая запись DEL X не может встретиться раньше первой записи BID X и т.д.).

Вывод. Требуется вывести одно число – прибыль аукциона в рублях.

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

Что-то у меня TL получается. :( Когда использую структуру Расковалова, то на 5 тесте, когда сбалансированные дервья (рандомизованные) - на 7.
0,5 секунды - не мало? ;)

а у меня вообще WA test 2

Автор задачи - Атнашев :D
У него есть решение, не такое, как у Дена написано, а еще быстрее, оно укладывется :D .

Кончится ЧУ, наверно выложим разбор в открытый доступ.

кстати команда называется SALE:)
а у меня TL Test6:)))

На Тимусе мое решение зашло за 0.3 с. В форум иcходники не выложу, но пошлю на мыло с удовольствием.

0.3 с - это уже на грани, поскольку программа естественно на С с регистровыми переменными. :) А как быть тем, кто пишет на Delphi?
Вышли на мыло alex58@mail.ru. Большое спасибо!

Очень хотелось бы. Если листочки с разбором раздаются, то ничего не помешает выложить разбор?

Ну это как-то не принято (публиковать). По крайней мере я о таком еще не слышал.

А листочки раздаются для упрощения процедуры разбора задач. Просто песня получилась - раздали бумажки, полчаса паузы, потом жюри: "По задаче такой-то вопросы есть? Как, совсем нет? Ну ладно, надо же хоть что-то сказать - раскажем историю задачи и типичные ошибки". И так по 7 минут на задачу. Классно, всем рекомендую :)

попробую угадать: N*log N+N+K*sqrt(N) ? N-число строк ввода, K - число "SALE" строк. угадал? или у него еще моднее?

Хорошо, не хотите публиковать - пришлите, а то в Екатеринбург ездить за листочком неудобно. :)
PS Получил от Дена решение. Ничего нового не увидел. На Delphi такое по-прежнему не сдается. :(((

Моднее. Там цена разбивается на биты :) и на этой основе строится дерево :). sqrt не фигурирует. Бумажку с рабором можно поспрашивать на кафедре мат.экономики завтра.

да ну их, эти деревья, букеты-то глючат :)

Спасибо. Задача сдалась. :) Правда дерево получилось размером 2 млн, поэтому чтобы хранить в нем числа до 100000 и уместиться в ML 5 Мб пришлось старший бит числа хранить отдельно. Это так и планировалось или я - дурак?

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

хм.. да нет их как раз 10000*100=1 млн
а у меня все равно TL test5. что все-таки значит побитовое разделение числа?

Я не значения храню, а количество заявок с одинаковой ценой.

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