Сегодня В Лэти прошёл городской тур олимпиады школьников по программированию(куда я прошёл), задача A мне не далась, хотя около двух часов грыз её(из четырёх). Чувствовал, что я близок к решению, но видно суждено было Бонду застрять в лифте навсегда.
Думаю, что надо как-то использовать прогрессии.

Извиняюсь за качество сканирования - vuescan глючит.

Присоединённый файл ( Кол-во скачиваний: 82 )
 olymp2.jpg 62,12 Kb

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

1) 1-ю кнопку 1! раз
2) 2-ю кнопку 2! раз
3) 1-ю кнопку 3! раз и т.д. пока он не выберется....

чем больше n, тем больший факториал придётся посчитать

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

можно доказать(думаю методом мат. индукции), что общее количество нажатий на клавиши меньше какого-то факториала(опять же навскидку (n+2)!)... а этот факториал можно представить в виде полинома от n...

А если первая кнопка окажется кнопкой движения вверх? Тогда он будет ехать всё выше и выше...
Это школьная олимпиада - про полиномы я не слышал, такое же задание было и у 10-х, 9-х классов.

Я пробовал сделать так:
Жмём кнопку 1 раз, и предполагаем, что n=1, тогда эта кнопка движет вверх, теперь жмём 2 раза вторую кнопку(B), если двери не открылись, тогда n!=1, ->мы не знаем какая кнопка, что значит. Делаем опять предположения... Вот здесь вся проблема, что нельзя вернуться к исходному состоянию + незнание кнопок --> простой прогрессией или фактериалом не отделаться.
Кстати там непросто факториал, движение вверх описывается формулой n(n+j), если я правильно помню(завтра разберу черновики).

А это как?

Единственно, что было про полином - будет круто, если число нажатий < полинома n.

ну как.... факториал есть произведение 1*2*3*...*n
(n+2)! = (n+2)*(n+1)*(n)*....*(n-k+1) , где k от 1 до n...думаю очевидно что после перемножения будет получен полином...
Добавлено @ 21:04

ж) алгоритму без разницы какая кнопка куда везёт лифт...
ммм...попробуйте применить алгоритм к конкретным значениям n, допустим 2 или 3....или 4.... для каждого значения n проверьте алгоритм для двух предположений(первая кнопка вверх/первая кнопка вниз)
Добавлено @ 21:06


полином = многочлен...запутать вас походу решили жестоко....и испугать страшным словом полином...
Добавлено @ 21:12


я тоже не знал что подумать n(n+j) или просто n... несколько раз перечитав задание, я решил, что лифт поднимается вверх постоянно на одно и то же количество этажей...- на n....
там помоему в условии и написано... Бонд проснулся на этаже n.... то есть у нас есть какоето число n.... а дальше ... лифт поднимается вверх на n этажей...то есть на это же самое число...

я так подамал предложенный мной алгоритм формально удовлетворяет всем условиям задачи....

степень которого зависит от аргумента n. Что-то здесь не так.

в условии сказано полином от n.... вот он так и зависит от n... так, что и и основание и показатель зависят от n.. согласен, смущает немного...

под полиномиальной зависимостью обычно понимают, что количество не больше значения некоторого полинома p(n), коэффициенты и степень которого не зависит от n

Если предположить, что n=3, а первая кнопка отправляет лифт вверх - выйдет, что он в космос улетит.

это как?

предположим она даёт указание лифту ехать вверх...
тогда
1) 1! вверх в итоге он на 6 этаже
2) 2! вниз - он на 4-м
3) 3! вверх он на (4+6*3) = 22 этаж
4) 4! вниз - он выйдет из лифта на 4!-2 шаге...

Круто, жаль я на олимпиаде не додумал до такого(факториалы никогда не использовал в решении). Задача в пару строк, а я 2 часа потратил на какие-то ветвления.

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

Должны скоро разместить на http://neerc.ifmo.ru/school/index.html
Буду ждать, особенно результатов(ожидаются к 27 числу)