Думаю, ни для кого ни секрет, что программирование заключается не столько в знании какой-то технологии, сколько в умении составлять алгоритмы для решения сложных задач. У кого-то из вас, возможно, даже есть какой-то опыт олимпиад по программированию, где эти задачи, мягко говоря, бывают очень даже и очень :) Да, они зачастую абстрактны и оторваны от жизни, но это же не их основная задача. А основная их задача в том, чтобы развивать голову и не давать мозгам ржаветь. Вот и я вам предлагаю размять мозги перед встречей новогодних праздников :)
Задачка изначально была совсем не новогодняя, но я решил, что надо ее видоизменить в связи с праздниками, а заодно и запутать вам возможность поиска ответа в великом и ужасном ;)
Итак, представьте себе: Жил да был на свете Дед Мороз (он же – Санта Клаус). Да, это тот самый дедушка, который на Новый год приносят хорошим деткам конфеты и мандарины, а взрослым – iPod’ы и Wii. Что, вам не принесли? Ну, значит плохо себя вели ;)
Так вот, у Деда Мороза есть олени, много оленей (N). Чтобы не запутаться в них, он их пронумеровал положительными целыми числами, причем так, что нет двух оленей с одинаковыми номерами. Правда, номера могут начинаться не с 1 и иметь пропуски в числах. И вот стоят эти олени в длинном хлеву в стойлах, один за другим, без какой-либо последовательности (номера идут в произвольном порядке). Дед Мороз может ходить мимо этих стойл только в одном направлении, то есть заходит с одной стороны и идет до самого конца, потом обходим хлев снаружи и заходит снова со входа. И вот у нашего дедушки появился новый олень (Снегурочка подарила на день рождения, например). И захотел дедушка наконец-то навести порядок в своих оленях и присвоить новому оленю самый маленький номер из тех, что у него нет. Ну, чтобы заполнить пробелы. То есть ему нужно обойти своих подопечных (только в одну сторону, сколько угодно раз), определить минимальный положительный номер, которого нет у существующих оленей, и присвоить его новоприбывшему.
Однако, дедушка стар, и ваша задача – помочь ему найти это число за минимальное количество проходов по хлеву. На беду, у дедушки еще одна проблема – у него не очень хорошая память, он может запомнить лишь несколько чисел (для определенности положим не больше 5), а писать он не умеет. Зато дедушка умеет считать :) Складывать, вычитать, умножать и делить. Думаю, он умеет еще извлекать корни и решать интегральные уравнения третьего порядка, но к нашей задаче это отношения не имеет :)
Вот, собственно, и все. Прошу алгоритмы в комментарии, товарищи программисты и не только. Чур, код не писать, покажите, на что вы способны без компилятора ;)
PS. С наступающими вас! Пусть 2009 год даст новые идеи и мечты, а также энергию и устремление для их реализации! И, конечно, счастья, здоровья и любви вам и вашим близким!
Вот заходит дедушка в хлев, и чимчикует в самый конец. Смотрит на первого оленя: "нумер надцать". Смотрит на воторого:
ReplyDelete- Ага, у этого парнокопытного нумер меньше чем у предыдущего. Запомню-ка я его нумер.
И так, дойдя до конца, дедуля будет знать у какого из оленей самый маленький... номер :).
Ежели этот номер больше 1, то достаточно просто назначить подарку номер первый. Но, о горе, что делать, если нумер сий, таки 1? Дедуля не промах. Его центральный сторедж вмещает целых пять нумеров. Так пусть и запоминает последнии пять, самых мелких. Если где-то промеж ними найдется пробел - туда втулять нового оленя нужно.
Но, не будем упрощать дедушке жизнь, и пусть таки они все идут последовательно. Запомним последний номер и погоним дедушку по второму кругу. Теперь будет идти поиск минимума, большего чем последней запомненный.
Процесс продложится в лучшем случае 1 раз, а в худшем случае порядка N/4 раза.. Этот худший случай можно попробовать обойти, заплатив дополнительным прогоном дедушки по хлеву и подсчету суммы нумеров, с замахом на арихметическую прогрессию (или даже скрестить его с первым пробегом и пожертвовать одной яйчейкой памяти). Хотя учитывая размер памяти дедули стоит усомниться в его алгебраических способностях.
На вскидку. Если есть и требуется решение О(1) - скажи, буду думать :).
Нет, ну такой вариант тоже имеет право на жизнь :) Но все же он не самый оптимальный. Его сложность - O(N/4). Сложность же правильного решения - O(log<2>N). Для большого N разница очевидна. Попробуй другие способы :)
ReplyDeleteДа, просьба к тем, кто уверен в своем решении, просто отписать мне, что вы решили задачку, и не писать само решение, чтобы остальным было интереснее :) В подтверждение решения ответьте также на вопрос, какие виды арифметических действий вы использовали для решения.
НЕ! Нормальный мужик (а тем более такой знатный как Дедуля) никогда не сделает хаоса из своего автопарка! Следовательно изначально у него все олени были пронумерованы по порядку (даже если это не простая последовательность чисел типа 1,2,3... а какие-нибудь числа фибоначи или еще что-нить вывод один - в нумерации оленей есть логика). Но, допустим в прошлом году пару оленьих сил дедушкиного мазератти подстрелила система ПРО США, двое умерли от сердечного приступа на фоне кризиса и штуки три просто сдохло от чумки. И тут внучка подарила деду еще одного оленя... Не V12 конечно, но не выгонять жеж животину...
ReplyDeleteСобссно решение:
1. Дед заходит в стойло и гладит каждого оленя в отдельности, рассказывая какой тот хороший.
2. Дед выходит из стойла, понимает, что чего-то не хватает, обязательно матюкается и зовет внучку рабораться. Она ведь молодая, вот пусть ищет недостающие элементы ряда чисел :)
В итоге имеем минимальную сложность алгоритма, и максимальное удовлетвоорение от процесса!
Называется, какой вопрос - такой и ответ. Надо было задать вопрос по всей строгости, с машиной и перфокартами, а не придумывать что-то особенное :) За креатив - однозначно 5 баллов (!), а вот решение не зачтено ;)
ReplyDeleteМне кажется, деду достаточно обычных познаний в двоичной математике...
ReplyDeleteТ.е. дед заранее задумывает число НОЛЬ в котором в бинарном представлении N разрядов (например 00000, если Н = 5).
После этого он идёт по ряду, и на каждый номер, который он встречает, взводит соотв. бит в своём числе, т.е. встретил 1 - проставил 00001, встретил 5 - проставил 10001, встретил номер больше 5-и - проигнорировал.
Т.о. после первого же прохода дед увидит либо хотя бы один 0 - выберет из них самый "маленький" - значит этот разряд он и может занять своим оленем. Если все еденицы - значит придётся занимать номер N + 1.
Такой вот вариант, вроде недалёк от оптимального.
Конечно, шикарное решение со сложностью O(1), но к сожалению у дедушки память не резиновая :) Уже для N=32 (ну, или 64, в зависимости от разрядности) уже даже компьютер загнется, когда попытается представить это число в одном регистре. Не то что наш дедушка :) Решение есть, оно простое и очень красивое.
ReplyDeleteДед Мороз наверно растерял часть оленей, раз у него пропуски в ID.
ReplyDeleteЯ с такой задачей столкнулся в 2003-м на Firebird - ID кто-то сделал таким, что где-то в районе 32 млн. начались проблемы :)
Тогда мы просто портировали данные в новую структуру, а ради интереса я написал что-то на SQL для "утрамбовки" ID. Да только LINQ2Deer пока в стадии тестирования нептунианскими эльфами, да и как писать запросы к стойлу оленей, непонятно. :)
Сразу в голову приходит то, что предложил anvaka. Еще вертится что-то по поводу объединения оленей в порции по 10 шт. и нахождения минимума среди них, но шампанское к сожалению не дает довести мысль до конца.
С Новым Годом! И пусть все олени будут правильно посчитаны! :)
Тссс. Не говори никому про LINQ2Deer - это же коммерческая тайна дедушки! Вот зарелизится он, тогда обсудим :)
ReplyDeleteОбъединение оленей в порции - это уже шаг на пути к настоящему решению. Но вот как объединять и что с ними потом делать - вот где загадка :)
Спасибо за поздравления :) Настоящий правильный ответ еще не получен. Ну, кто же будет первым?
Ладно, тогда решение "для детсадовцев" так сказать...
ReplyDelete(Вообще плохо, что в условии не указано хотя бы ориентировочное кол-во оленей всего, а то ссылки на плохую память дедушки делаются, но если оленей три триллиона, я думаю ему никакая плохая память не поможет).
Допустим оленей всего 200. Дед запоминает до 5 небольших чисел.
Дедушка идёт по ряду, запоминает кол-во встретившихся оленей в каждой порции по 40. Ну, типа, 40 оленей в первой сороковке, 38 во второй и тд..
Ищет первую неполную сороковку, и делит её снова на 5 частей - т.е. по 8.
Делает второй заход, сканирует каждую порцию по 8 в избранном диапазоне. И опять по тому же приципу... вроде немного заходов, но сколько именно - посчитать счаз не берусь. Штуки 3-4 для двухсот оленей, 4-5 для тыщи, и тд.
Надеюсь, такого рода подсчёт не помешает дедуле вовремя успеть воспользоваться своими оленями... времени то уже меньше 10-и часов осталось... :-)
Привет, Саша.
ReplyDeleteМетод "разделяй и властвуй" ;-) (Читаем Кормена)
Дедушка берет средний порядковый номер оленя на очередном проходе(между минимальным и максимальным) и считает количество оленей, попадающихся в образовавшиеся 2 группы. Далее смотрим сколько оленей в левой подгруппе. Если их там столько сколько если бы они шли подряд без пропуска, то левую подгруппу исключаем из рассмотрения и со следующего захода рассматриваем уже правую. В противном случае отсекаем правую подгруппу. За каждый проход ровно половина отсекается, таким образом сложность алгоритма логарифмическая.
Всех с Новым годом :-)
Наконец-то! Молодцы, успели до Нового года :) Теперь Дед Мороз может отправлять дарить детям подарки.
ReplyDeletemormat, интересное у тебя решение для "детсадовцев" ;) На самом деле, алгоритм верный, только делить все же нужно не на 5, а на 2 части, т.к. регистров памяти всего 5 (в принципе, один даже лишний). В одни записываем N, во второй - середину, в 3 и 4 - количество элементов в каждой из двух групп. Теоретически можно попробовать делить на 3 части, будет еще быстрее, но тогда конец мы не знаем (3 на суммы, 2 на разделители) и, в случае, если недостача в последней группе, его надо высчитывать отдельно для следующей итерации. Так что я бы остановился все же на двух группах.
Привет, Жень :) Давно не общались. Приятно тебя здесь видеть. Сразу видно олимпиадное прошлое и алгоритмический бекграунд ;) За знание названия алгоритма отдельное спасибо от Снегурочки :)
Еще раз всех с праздниками! Спасибо, что поучаствовали в задачке :)