ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1744. Рота Капитана

Algorithm (+)
Послано Vedernikoff Sergey (HSE: АОП) 20 сен 2010 03:51
Solved the problem with pure brute-force in 0.031 sec. BTW, my program works for much larger n's than in the problem statement.
I'm wondering whether there is more rigorous solution?
Re: Algorithm (+)
Послано Ripatti [Ufa] 28 окт 2010 01:58
There rigorous algo exists. It has O(N^2) complexity and about 10 lines of code.
Re: Algorithm (+)
Послано Vedernikoff Sergey (HSE: АОП) 28 окт 2010 12:04
My solution is not much longer - about 20 lines of code. But complexity is O(2^(N/2)*(1/2*N^2)!). But works fast for almost any N =)
Re: Algorithm (+)
Послано Ripatti [Ufa] 29 окт 2010 14:40
It means that you are very cool:D
For Petrozavodsk this problem was planned as solvable by brute force and some precalculation. Just for fun.
Re: Algorithm (+)
Послано Vedernikoff Sergey (HSE: АОП) 29 окт 2010 19:09
Thanks, but, probably, you could give some clue for algorithmic solution of the problem?
Re: Algorithm (+)
Послано Ripatti [Ufa] 30 окт 2010 19:04
Try to arrange soldiers in vertices of regular n-polygon and mind geometrically.