Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#26 2006-12-01 15:36:35
- bulpi
- Новий користувач
- Зареєстрований: 2006-12-01
- Повідомлень: 4
Re: Задача Mayor
Юрьев Александр написав:
вроде бы да
а, например, для 50?
Я пока реализовал алгоритм прямого (тупого 
) перебора. Больше N=10 не спрашивать... При N=1000 вариантов больше, чем звезд в видимой вселенной.
Поза форумом
#27 2006-12-01 15:41:08
- ppv
- Новий користувач
- Зареєстрований: 2006-11-30
- Повідомлень: 9
Re: Задача Mayor
для 50
2530373879400570618547163034787837890646
Поза форумом
#28 2006-12-01 18:04:10
- Sleapwalker
- Новий користувач
- Зареєстрований: 2006-11-25
- Повідомлень: 17
Re: Задача Mayor
Я в шоці, тест для n=1000 біля 0.2с, в мене не оптимізований йшов 4.5 с , а оптимізований 1с.
Close your eyes
Feel the ocean where passion lies
Silently the senses
Abandon all defences
Поза форумом
#29 2006-12-01 18:16:49
- }{AKER
- Новий користувач
- Зареєстрований: 2006-10-16
- Повідомлень: 4
Re: Задача Mayor
Люди, подкиньте идейку, как её хоть решать...
ICQ 381-521-040
Поза форумом
#30 2006-12-01 18:31:16
- Fizteh
- Новий користувач
- Зареєстрований: 2006-09-17
- Повідомлень: 99
Re: Задача Mayor
}{AKER написав:
Люди, подкиньте идейку, как её хоть решать...
Кинь мне на mipt2006@rambler.ru свое мыло, я тебе кину идею и само решение. Если хочешь конечно
Поза форумом
#31 2006-12-06 14:44:32
- JurasSic
- Новий користувач
- Зареєстрований: 2006-10-25
- Повідомлень: 21
Re: Задача Mayor
У меня тупым перебором для десяти 5 мин. считает,а дальше по геом прогрессии :-( :-( 
Поза форумом
#32 2006-12-06 19:13:54
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: Задача Mayor
Единственная проблема этой задачи, что маленький ТЛ сильно ограничивает разнообразие идей решений. У меня есть 3 решения на совершенно разных идеях которые на макс тесте работают за 0.13-0.6 сек в зависимости от идеи.
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#33 2006-12-06 21:26:20
- Ivan
- Олімпієць
- Зареєстрований: 2005-10-09
- Повідомлень: 218
Re: Задача Mayor
О прикольно, рассскажи еще два (я знаю типа динамики по краю)
ICQ 233-416-344
Поза форумом
#34 2006-12-07 17:52:33
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: Задача Mayor
По возрастанию скорости:
1. Решение через 3 реккурентности.
2. Динамика по краю.
3. Стоим матрицу переходов между состояниями и возводим в н-ю степень.
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#35 2006-12-07 20:06:25
- ppv
- Новий користувач
- Зареєстрований: 2006-11-30
- Повідомлень: 9
Re: Задача Mayor
2reiten:
Насчет 3 реккурентностей. можешь расписать?
Поза форумом
#36 2006-12-08 14:47:05
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: Задача Mayor
Выводятся они рассмотрением расстановок на бумаге.
f(n) - доска длинны н вида
Код:
######....######## ######....######## ######....########
g(n) - доска длинны н вида
Код:
######....######## ######....######## #####....########
h(n) - доска длинны н вида
Код:
######....######## #####....######## ######....########
Сами реккуренсности:
h(n)=f(n-1)+2*g(n-1)+f(n-2)+h(n-2)
g(n)=h(n-1)+f(n-2)+g(n-2)+2*f(n-1)+g(n-1)
f(n)=g(n)+f(n-1)+3*g(n-1)+3*f(n-2)+g(n-2)+h(n-2)
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом