| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Задачи городской олимпиады Спб |
| Автор: powerfox 5.2.2006, 17:09 |
| Сегодня В Лэти прошёл городской тур олимпиады школьников по программированию(куда я прошёл), задача A мне не далась, хотя около двух часов грыз её(из четырёх). Чувствовал, что я близок к решению, но видно суждено было Бонду застрять в лифте навсегда. Думаю, что надо как-то использовать прогрессии. Извиняюсь за качество сканирования - vuescan глючит. |
| Автор: Partizan 5.2.2006, 18:38 |
| ....не знаю конечно насколько это верно, но так с ходу кажется, что он точно выйдет из лифта, если нажимать кнопки поочерёдно след кол-во раз: 1) 1-ю кнопку 1! раз 2) 2-ю кнопку 2! раз 3) 1-ю кнопку 3! раз и т.д. пока он не выберется.... чем больше n, тем больший факториал придётся посчитать  возможно не совсем экономично с точки зрения ресурсов времени и памяти, однако на первый взгляд - одно из решений.... |
| Автор: Partizan 5.2.2006, 19:42 |
| можно доказать(думаю методом мат. индукции), что общее количество нажатий на клавиши меньше какого-то факториала(опять же навскидку (n+2)!)... а этот факториал можно представить в виде полинома от n... |
| Автор: powerfox 5.2.2006, 20:02 | ||||
А если первая кнопка окажется кнопкой движения вверх? Тогда он будет ехать всё выше и выше...
Это школьная олимпиада - про полиномы я не слышал, такое же задание было и у 10-х, 9-х классов. Я пробовал сделать так: Жмём кнопку 1 раз, и предполагаем, что n=1, тогда эта кнопка движет вверх, теперь жмём 2 раза вторую кнопку(B), если двери не открылись, тогда n!=1, ->мы не знаем какая кнопка, что значит. Делаем опять предположения... Вот здесь вся проблема, что нельзя вернуться к исходному состоянию + незнание кнопок --> простой прогрессией или фактериалом не отделаться. Кстати там непросто факториал, движение вверх описывается формулой n(n+j), если я правильно помню(завтра разберу черновики). |
| Автор: Mayk 5.2.2006, 20:18 | ||
А это как? |
| Автор: powerfox 5.2.2006, 20:27 |
| Единственно, что было про полином - будет круто, если число нажатий < полинома n. |
| Автор: Partizan 5.2.2006, 21:00 | ||||||||||||||
ну как.... факториал есть произведение 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 этажей...то есть на это же самое число... я так подамал предложенный мной алгоритм формально удовлетворяет всем условиям задачи.... |
| Автор: Mayk 5.2.2006, 21:30 | ||
степень которого зависит от аргумента n. Что-то здесь не так. |
| Автор: Partizan 5.2.2006, 21:35 |
| в условии сказано полином от n.... вот он так и зависит от n... так, что и и основание и показатель зависят от n.. согласен, смущает немного... |
| Автор: maxim1000 5.2.2006, 22:14 |
| под полиномиальной зависимостью обычно понимают, что количество не больше значения некоторого полинома p(n), коэффициенты и степень которого не зависит от n |
| Автор: powerfox 5.2.2006, 22:49 | ||
Если предположить, что n=3, а первая кнопка отправляет лифт вверх - выйдет, что он в космос улетит. |
| Автор: Partizan 6.2.2006, 01:30 | ||||
это как? предположим она даёт указание лифту ехать вверх... тогда 1) 1! вверх в итоге он на 6 этаже 2) 2! вниз - он на 4-м 3) 3! вверх он на (4+6*3) = 22 этаж 4) 4! вниз - он выйдет из лифта на 4!-2 шаге... |
| Автор: powerfox 6.2.2006, 12:22 |
| Круто, жаль я на олимпиаде не додумал до такого(факториалы никогда не использовал в решении). Задача в пару строк, а я 2 часа потратил на какие-то ветвления. |
| Автор: Partizan 6.2.2006, 13:43 |
| а ответы для проверки есть?... в частности интересует алгоритм, в котором число нажатий меньше полинома, потому как меня тоже смущает то, что в предложенном мной решении степень полинома также зависит от n... |
| Автор: powerfox 6.2.2006, 16:11 |
| Должны скоро разместить на http://neerc.ifmo.ru/school/index.html Буду ждать, особенно результатов(ожидаются к 27 числу) |
