Еще две задачки

[kirpich_spb]

Еще две интересные задачки. У первой решение совсем простое, а вот над второй придется думать (я вот довольно долго решал).

1. Продолжить последовательность: 1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314
   
2. Дан массив длины n+1, содержащий числа от 1 до n. Используя лишь O(logn) памяти, найти за линейное время какое-нибудь

Comments

[anna_frid]

Первая действительно простая.

[volchonka]

первая неинтересная.
а вот что настроение слайдоделательное - это правильно. а то твои закатыванья глаз и стоны "йа устал, йа ухожу" в прошлое воскресенье напугали )

[kirpich_spb]

Не говорил я так! =) Это надо было понимать так: "Я, блин, заколебался, уже эти слайды делать." У меня сейчас дня три-четыре на все уходит. Хотел вот выцыганить себе недельку на отдых, но не вышло.

[volchonka]

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

[kirpich_spb]

То есть не особо умело я на жалость давил, да?.. Ну, я действительно тогда не особо выспался и подумал, что лучше перенести лекцию на неделю, но подготовить ее получше, а не в последнюю ночь по-студенчески. А вы, злые дети, не только не прониклись, но еще и смеетесь. Так что будет вам опять лекция, сделанная на коленке. =)

[rus4]

Я правильно понимаю, что хранение одного числа занимает как раз O(log n) памяти? То есть можно помнить одновременно не больше чем постоянное количество чисел?

[kirpich_spb]

Да, Федя, именно так.

[kirpich_spb]

Так а первая задача для тебя настолько проста, что ты даже не стал писать, как остальные, что она скучная? =)

[rus4]

первую я знал

[shurik_s]

Я надеюсь 2n+1 это линейное время? ;) Если да то очевидно...
А первая забавная, хоть и простая.

[kirpich_spb]

Да, линейное, конечно. Хм... Так а как ты решил? Может, я какого-то простого решения и не заметил.

[shurik_s]

Идея классическая, как в задаче про поиск одного не повторяющегося числа.

[kirpich_spb]

А что за идея? На всякий случай поясню: в моем массиве сосвем не обязательно только одно число повторяется. Повторов может быть много.

[anonymous]

[max_b]

Собственно, q нам вовсе не нужно, так что шаг 4) лишний.

[kirpich_spb]

Да, Макс, точно! Быстро ты ее решил. Я вот несколько месяцев решение искал.

Вынужден твой ответ заскринить, тем не менее. =)