Все зависят насколько большие числа задают прямую и окружность, хотя если использовать длинную арифметику, то за счет времени выполнения можно добиться сколь угодного точного результата.
3 2010-04-22 16:43:59
Re: far manager (2 ответов, оставленных в Feedback)
надо установить плагин Colorer
попробуй этот
4 2010-03-19 03:36:59
Re: timus 1557 (4 ответов, оставленных в Problems)
да, идея правильная, и по времени должно пройти <количество ребер в остовном> * <поиск всех мостов> получается O(N * (N + M)) ~ 200 000 000, вроде нормально для двух секунд.
5 2010-03-19 03:28:02
Re: Импульсные сигналы (3 ответов, оставленных в Problems)
ага, как сказал уже coder.ua можно легко определить по формуле T - <расстояние до i вершины от начальной> + 1 сколько раз будет пускать импульс вершина i. Но хочется уточнить что для ребра U->V надо не только увеличивать count(U), но и также count(V).
6 2010-03-19 03:08:23
Тема: Отпрака сообщений (6 ответов, оставленных в Offtopic)
А можно чтоб по crtl+enter отправлялось сообщении, очень не хватает))
7 2010-03-19 03:07:23
Re: ACM SEERC 2009. The Computer Game Problem (11 ответов, оставленных в Problems)
если она есть онлайн, кинь ссыль, попробую поднять и может тебе по коду будет понятней
8 2010-03-19 03:05:41
Re: ACM SEERC 2009. The Computer Game Problem (11 ответов, оставленных в Problems)
* o o o * -> 1 0 0 0 2
после добавление строки * o o o * комбинация останется такой же 1 0 0 0 2,
после добавление * * * * * комбинация превратся в 1 1 1 1 1,
потом если снова будет добавлять * o o o * комбинация будет уже такой 1 0 0 0 1,
а потом если добавим * o * o * комбинация станет такой 1 0 2 0 1,
добавим * o * * * комбинация станет 1 0 1 1 1.
9 2010-03-19 02:53:41
Re: Постройка цикла Гамильтона на дереве. (4 ответов, оставленных в Problems)
а можно ссыль на задачку, попробуемс)
10 2010-03-19 02:50:32
Re: Deliteli (6 ответов, оставленных в Algo)
Факторизовать можно быстрее. Найти все простые числа до корня, тем же решетом Эратосфена, и перебирать не все числа до корня, а только их.
Хотя построение решета займет тоже самое время, но это будет предпроцесс, так что если надо находить для множества чисел, то это будет выгодно.
11 2010-03-07 23:32:08
Re: Постройка цикла Гамильтона на дереве. (4 ответов, оставленных в Problems)
идея: запускаем обход в глубину, и просчитываем f[x] - если поддерево с корнем в вершине x превратить в гамильтоновый цикл, то сколько ребер понадобится. Ну и просчитывается она как сумма всех f[его потомков] + <количество потомков> - 2 (что-то наверное типа такого, надо больше примеров рассмотреть, видней будет). Ну и изначально стиреть вершины у которых степень вершины равна двум (это можно прям в двс обрабатывать), это тип если мы вошли в такую вершину, то точно знаем куда выйдем.
12 2010-03-07 23:02:53
Re: ACM SEERC 2009. The Computer Game Problem (11 ответов, оставленных в Problems)
зачем дописывать под одной клетке? дописывай сразу строку, т.е. все возможные варианты 2^, и пробуй дописать все возможные строки, и количество компонент вродь как не надо, в конце же должна одна компонента остаться, один тип, а при добавление строки мы контролируем чтобы не распадалось на две компоненты и в дальнейшем могло слиться в одну. ну и как сказал alt нужно повернуть, но мне кажется оптимизированное решение должно и без поворота успеть, там с поворотам нехорошие случаи возникают.
13 2010-03-02 06:58:51
Re: Коровы (3 ответов, оставленных в Problems)
Возможно идея неправильная или не оптимальная, потому как она обещает работать не только для двух коровников.
Допустим мы научились для заданного расстояния определять, а можно ли так расставить коровники чтобы максимально расстояние не превышало заданного, т.е. мы максимальное расстояния знать не будем, мы только можем отвечать можно или нельзя.
Тогда если мы это умеем можно воспользоваться дихотомией (двоичным поиском) для поиска минимального такого расстояния которое нам подходит. Ведь если для какого либо расстояние можно расположить коровники, то и для любого большего тоже можно расположить, и наоборот - если для какого либо нельзя, то и для меньшего тоже нельзя.
Теперь осталась научиться определять можно или нельзя. Пока идея только такая - идем обходом в глубину (обход начинаем из любой вершины) и определяем надо ли в текущей вершине(лужайке) ставить коровник.
Как определяем:
Допустим в текущем поддереве нет коровника, тогда коровник поставиться в текущую лужайку если высота дерева (расстояние до максимально удаленной лужайки в текущем поддереве) равна заданному расстоянию, тогда ставим.
Если уже есть коровник, тогда среди тех лужаек которые не могут за заданное расстояние добраться до коровника находим максимально удалённую и также ставим если оно равно заданному. Максимальна удаленная лужайку будет листом. Допустим мы хотим найти максимально удаленную для текущей вершины (лужайки). Надо проверить только те вершины которые являются максимально удаленными вершинами потомков текущей вершины.
Можно заметить что первый случай легко может быть обработан во втором.
14 2010-03-02 04:51:51
Re: ACM SEERC 2009. The Computer Game Problem (11 ответов, оставленных в Problems)
На примере этой задачи:
Представь что ты начинаешь заполнять свои точки сверху вниз. Тогда для каждой строки тебе важно знать что находилось только на предыдущей строке, и не больше (т.к. связи с предпредыдущей быть не может). Получается динамика вида F[I, J], где I - номер строки, J - "рваный" профиль, и F[I, J] - количество таких способов. J - это маска, только уже не битовая. В данной задаче, как я вижу (я пока ещё не писал), J это разбитие текущей строки по группам. Например для битовой 1010111 соответствует массиву 1 0 2 0 3 3 3, а после того как перейдем по 1110101 получится массив 1 1 1 0 2 0 2. Надо только в этом случае правильно рассмотреть все возможные и невозможные случаи перехода.
P.S. Но это как я понял, возможно и не так.
15 2010-03-02 04:15:38
Re: Коровы (3 ответов, оставленных в Problems)
Можно наибольшее расстояние перебирать дихотомией и смотреть возможно ли для заданного макс. расстояния расстановка коровников. Так как у нас дерево, то проверять расстановку скорей всего можно за линейно (например поиском в глубину + жадный).