Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Сторінок: 1
- Список
- » Третий тур NetOI-2006
- » Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
#1 2007-01-04 20:26:04
- FireTiger
- Новий користувач
- Звідки: Донецк
- Зареєстрований: 2006-09-27
- Повідомлень: 86
Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
Здесь я предлагаю обсудить решение задачи NewFerry
Если вы собрались написать сообщение в этой теме пожалуйста прочитайте следующие правила:
1. Постить только после окончания приёма решений. (без комментариев)
2. Постите код только если вас об этом попросили. (обилие кода делает тему нечитабельной)
3. Обсуждайте только задачу, которая указана в теме.
Надеюсь эти простые правила сделают обмен мнениями более плодотворным.
Відредаговано FireTiger (2007-01-04 20:37:14)
ICQ 339203772 - Если что-нибудь срочно необходимо - стучитесь, я отвечу!
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.
Поза форумом
#2 2007-01-05 09:56:17
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
Ідея слідуюча: перебор + алгоритм Дейстри.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#3 2007-01-05 12:01:35
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
Будуємо всі комбінації для N бізнесменів (комбінації вважаються різними, якщо при накладанні одна на одну вони не співпадають). Отримані комбінації позначимо через F[i] і NF[i] -- обернена кобінація до F[i].Для кожної F[i] i NF[i] перевіряємо відсутність змов, і якщо змови відсутні, то комбінацію назвемо коректною, в іншому випадку некоректною, тоді Можна предсавити граф із 2*length(F) вершин. Тепер застосувавши алгоритм дейстри (з деякими модифікаціями: йдемо тільки по коректним вершинах і при переправі в лодці не було змов) для знаходження мінімального маршрту між вершиною F[0] і F[length(A)] ми отримаємо розвязок задачі, де F[0] - пуста множина, F[length(A)] - множина, яка містить всі N елементів.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#5 2007-01-05 12:10:37
- alex_kasycky
- Олімпієць
- Зареєстрований: 2005-10-09
- Повідомлень: 92
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
xXx написав:
а сложность?
У меня перебор+Дейкстра. Сложность O((2^N)*N^2)
Этот аккаунт не работает... мой новый аккаунт - alexkasycky
Поза форумом
#6 2007-01-05 12:12:14
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
O((2*length(F)^2)). Якщо оптимізувати, то при найнесприятливому випадку O((2length(F))*924). length(F) не перевищує 5000.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#8 2007-01-05 12:29:08
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
В мене прога працює макс. 0.4 сек.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#10 2007-01-05 12:59:58
- Буник
- Новий користувач
- Зареєстрований: 2006-11-19
- Повідомлень: 37
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
Для тесту 12 1 1 1 1 1 1 1 1 1 1 1 1 0 ? Круто.
Поза форумом
#11 2007-01-05 14:54:28
- alex_kasycky
- Олімпієць
- Зареєстрований: 2005-10-09
- Повідомлень: 92
Re: Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)
Народ, киньте тестов плиз.
Этот аккаунт не работает... мой новый аккаунт - alexkasycky
Поза форумом
Сторінок: 1
- Список
- » Третий тур NetOI-2006
- » Обсуждение решения задачи NewFerry (только после 23:59 04.01.07)