Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#1 2005-12-18 17:10:17
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
фух.
фух...освободился от проектов, олимпиад и прочего....наконец-то...приступаем к задачам....просьба всем кто может, помогать понять условие, у меня 5 часов, чтобы решить все задачи, которые еще даже не видел 
,
Поза форумом
#2 2005-12-18 17:11:49
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
так-с.....с первой задачей понял, как там и что, и понял, что мне на нее надо минимум час....ДСП вроде несложная, о результатах сообщу позже
Поза форумом
#3 2005-12-18 17:22:06
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
DSP готова. гхм...быстро я . Читаем building. вроде тоже несложная.
Поза форумом
#4 2005-12-18 17:23:47
- Anna
- Олімпієць
- Звідки: Киев
- Зареєстрований: 2005-11-06
- Повідомлень: 122
Re: фух.
такими темпами ты не 5ч на задаци потратишь, а 1... 
Хорошо смеется тот, кто смеется последним...
Поза форумом
#5 2005-12-18 17:25:15
- Джулгаков Дмитрий
- Олімпієць
- Звідки: Харьков
- Зареєстрований: 2005-11-03
- Повідомлень: 61
Re: фух.
Интересно, сможешь ли также быстро решить PrimeNum ? Она хоть и простая, но с приколом
Поза форумом
#6 2005-12-18 17:35:08
- Victor Barinov
- Олімпієць
- Зареєстрований: 2005-12-03
- Повідомлень: 21
Re: фух.
Интересно, какой же прикол в PrimeNum? Лично я решил ее одной из первых... Может я чего-то не понял в условии?
Поза форумом
#7 2005-12-18 17:35:51
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
блин..building решил, зацикливается) сейчас исправим....5 мин дайте)
Поза форумом
#8 2005-12-18 17:44:15
- Джулгаков Дмитрий
- Олімпієць
- Звідки: Харьков
- Зареєстрований: 2005-11-03
- Повідомлень: 61
Re: фух.
Ну и какая у тебя сложность решения. Сколько работает на тесте 2 3 5 1600 ???
Поза форумом
#9 2005-12-18 17:46:11
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
building пофиксил. время n*n
dsp, время n.
Боюсь, что авторское решение билдинга n.
Поза форумом
#10 2005-12-18 17:47:24
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
читаю primenum....
Поза форумом
#11 2005-12-18 17:56:03
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
мля....условие не то...опять читаю primenum.
Поза форумом
#12 2005-12-18 17:57:38
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
кто-то решил building за линейное время??!
Поза форумом
#13 2005-12-18 18:22:40
- Victor Barinov
- Олімпієць
- Зареєстрований: 2005-12-03
- Повідомлень: 21
Re: фух.
Джулгаков Дмитрий написав:
Ну и какая у тебя сложность решения. Сколько работает на тесте 2 3 5 1600 ???
На этот тест, моя прога выдала 1399680000. Произошло это довольно быстро (думаю меньше чем 0.1сек). Если назову сложность алгоритма, то назову и решение. Но скажем так, у меня где-то 40000 итераций циклов. А циклы дают не очень большие константы. А у тебя быстрее работает?
Поза форумом
#14 2005-12-18 18:25:42
- Victor Barinov
- Олімпієць
- Зареєстрований: 2005-12-03
- Повідомлень: 21
Re: фух.
DeusEx написав:
кто-то решил building за линейное время??!
Что значит линейное?
Думаю можно решить за O(n^4), где n - сторона поля. А если оптимизировать, то сложность улучшается довольно хорошо, думаю что до O(n^3), но не уверен.
Поза форумом
#15 2005-12-18 18:29:33
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
линейное это O(n^1)
Сколько работает на тесте 2 3 5 1600 ??? - это к какой задаче? в дсп и билдинг числа до 200.
Відредаговано DeusEx (2005-12-18 18:30:22)
Поза форумом
#16 2005-12-18 18:33:04
- Anna
- Олімпієць
- Звідки: Киев
- Зареєстрований: 2005-11-06
- Повідомлень: 122
Re: фух.
он имел в виду PrimeNum
Хорошо смеется тот, кто смеется последним...
Поза форумом
#17 2005-12-18 18:34:38
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: фух.
Building пишется за O(N^2) - это оптимум. Меньше ни алгоритма, наверное, нет, да и весь ввод за меньшее не обработать:)
А вот DSP за O(N) !!!!!????????????????Impossible.
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#18 2005-12-18 18:35:14
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
а....PrimeNum сейчас решаю....м...уже идеи есть, думаю решу в теч.30-60 мин;).
Поза форумом
#19 2005-12-18 18:36:23
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: фух.
В DSP явный O(N^3)!!!!
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#20 2005-12-18 18:37:07
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
DSP вообще решается в заданное кол-во операций . N в данном случае константа.)
Відредаговано DeusEx (2005-12-18 18:38:18)
Поза форумом
#21 2005-12-18 18:39:40
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
просьба удалить этот пост.
Відредаговано DeusEx (2005-12-18 18:41:53)
Поза форумом
#22 2005-12-18 18:40:41
- DeusEx
- Олімпієць
- Зареєстрований: 2005-11-17
- Повідомлень: 127
Re: фух.
reiten написав:
Ты посмотри на ограничения. Будь нам линия, в DSP дали бы ограничение в 20000, а не в 200.
не обязательно, тут время не абсолютное, а в 2 раза больше чем авторское. Т.е. даже если ограничение 20, надо решить так же как автор.
Поза форумом
#23 2005-12-18 18:41:16
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: фух.
А, ну тогда все понятно. Хотя там худшее время можно спустить до O(N^3).
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#24 2005-12-18 18:42:37
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: фух.
Кстати, в каком ты классе?
я в 10-м.
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом