Opencup.ru: GP of Ural (XV Открытый чемпионат Урала по спортивному программированию)

13 лет назад, # |

← Rev. 2 →

За sqrt(n) посчитаем все делители числа, их будет не больше 150-200.

Затем, идём по буквам (n) и перебором всех делителей выбираем минимально возможную букву.

→ Ответить

http://pastebin.com/Y3z1dL3q

13 лет назад, # ^ |

Код решения на Джаве:

→ Ответить

13 лет назад, # ^ |

Мы точно так же сделали, только без страшных слов функция Гранди. Ещё бы доказать неплохо было, почему такая тупая жадность - и проходит...

→ Ответить

ArtDitel

13 лет назад, # ^ |

Как оказалось, она проходит, не из-за ошибки авторов, а из-за того, что для данных ограничений всегда есть раскраска менее чем из 26 цветов. Они это специально проверили для всех n

→ Ответить

13 лет назад, # ^ |

+10

Это понятно, что раскраска всегда есть. Непонятно, почему можно жадно красить.

→ Ответить

map	13 лет назад, # ^ \| +8 "Как оказалось, она проходит, не из-за ошибки авторов, а из-за того, что для данных ограничений всегда есть раскраска менее чем из 26 цветов. Они это специально проверили для всех n." Это не есть доказательство верности алгоритма. → Ответить

ArtDitel

13 лет назад, # ^ |

Бред. В общем случае это NP-полная задача, однако для данных ограничений ответ существует всегда и находится простейшим жадным алгоритмом. Для этого необходимо заведомо сгенерировать все делители числа n, и далее, крася по очередности людей в любой доступный цвет, мы перебираем всех его соседей (и левых и правых) и запрещаем им цвет, в который мы покрасили данного человека

→ Ответить

13 лет назад, # ^ |

Ну такое же решение же.

Или может я не понял, есть ли разница между запретом цветов и минимально возможным цветом?

→ Ответить

ArtDitel

13 лет назад, # ^ |

Неправильно в том, что ответ всегда есть. И функция Гранди - вообще из другой оперы

→ Ответить

13 лет назад, # ^ |

Ок, понял, извиняюсь.

→ Ответить

zeliboba

13 лет назад, # ^ |

все равно не понятно, почему это должно работать. Не всегда, когда есть корректная раскраска будет работать жадник.

→ Ответить

zeliboba

13 лет назад, # ^ |

P.S. Мы, правда, тоже написали жадник

→ Ответить

natalia

13 лет назад, # ^ |

+29

Мы решали по-другому. Выбираем наименьшее число k, на которое не делится n. Это число не больше 13. Разбиваем круг на две равные/почти равные половинки и в каждой половинке красим числа в один цвет с интервалом k. Для разных половинок используем разные цвета. Доказательство правильности такой раскраски тривиально.

→ Ответить

cerealguy

13 лет назад, # |

← Rev. 2 →

НОК чисел до 13 больше максимального n
http://pastie.org/1828216

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-8

-= Извиняюсь за тупость =-

→ Ответить

vilcheuski

13 лет назад, # |

Как же решается задача N о пикселях. Все свои тесты проходит. А выдаёт WA4 . Спасибо.

→ Ответить

http://pastebin.com/59xDxfBU

13 лет назад, # ^ |

← Rev. 2 →

Разобьём круг на 4 сектора. Посчитаем для каждого сектора.

Затем, разобъём сектор по x на r столбиков. Для каждого столбика нужно посчитать его высоту, она равна sqrt(r*r-i*i), где i = 0...r

Если число целое, то тогда в этот столбик можно уместить ровно sqrt(r*r-i*i) пикселей, иначе sqrt(r*r-i*i) + 1.

Код решения:

Фигово я, короче, объясняю :)

→ Ответить

map	13 лет назад, # ^ \| 0 Задача N http://pastie.org/1828285 → Ответить

13 лет назад, # |

Подскажите, пожалуйста, как A (про книгу) и G (про аквариум) решались.

→ Ответить

Egor

13 лет назад, # ^ |

А - чтобы можно было поменять состояние i-й страницы надо чтобы i-1я страница была включена, а меньшие - выключены. Рекурсия с мемоизацией

G - если нету нулей, то суммы противоположных уровней должны быть равны. Считается несложно. Дальше идет разбор случаев с 0, почитать эту и остальные сданные нами задачи можно здесь

→ Ответить

Nyatl

13 лет назад, # ^ |

+15

В A разве не поиск обратного кода Грея?

→ Ответить

riadwaw

13 лет назад, # ^ |

G. Если нулей нет. Проверить все легко.

a+c=b+d условие возможности.

V=(a+c+b+d)/4*k^2=(a+c)/2*k^2

Дальше интереснее.

3 нуля. ambiguous

2 нуля напротив- еррор

2 нуля рядом ambiguous

1 ноль. по 3 точкам проверим где должна быть четвертая.(а+с=б+д)

Если больше 0 - error

Иначе посчитаем объем так, как в первой части, заметим что некий тетраэдр с тремя прямыми углами при одной вершине, снизу от аквариума был посчитан зря(отсчитан с минусом в направленном объеме), добавим его.

→ Ответить

riadwaw

13 лет назад, # ^ |

← Rev. 2 →

A -

напишем 000000

из него можно сделать 1 ход.

Далее на каждом шаге можно сделать 2 хода, один из них обратно, второй в какую-то ситуацию с измененным 1 битом.

Закончится на 000001, из которой только ход назад

Заметим, что это стандартный код Грея. Посчитаем номера позиций, данных в условии. Ответ: модуль разницы этих номеров.

→ Ответить

cerealguy

13 лет назад, # ^ |

A - это коды Грея http://pastie.org/1828286

→ Ответить

Chmel_Tolstiy

13 лет назад, # |

Расскажите кто-нить Д. Спасибо.

→ Ответить

Egor	13 лет назад, # ^ \| +5 Раздвоим вершины. В получившемся двудольном графе найдем минимальное вершинное покрытие и дадим каждой вершине в нем k/2 Доказывать не умею :) → Ответить

13 лет назад, # ^ |

Можно чуть поподробнее? Что в данном случае есть раздваиваемые вершины и откуда куда там пускать рёбра? Вопрос, возможно, идиотский, но мне вот, например, реально непонятно :-[

→ Ответить

Egor	13 лет назад, # ^ \| 0 Пусть у каждой вершины будет синия и красная ипостась в новом графе. Тогда ребро между двумя вершинами в новом графе будет проходить между синей и красной вершиной если между соотвествующими вершинами было ребро в начальном графе → Ответить

13 лет назад, # ^ |

← Rev. 2 →

А! О... Ъ.

→ Ответить

Egor	13 лет назад, # ^ \| +5 Посмотри ссылку выше Я ее только придумал, писал Пашка → Ответить

13 лет назад, # ^ |

А откуда логарифм? Нам надо найти паросочетание в двудольном графе с 2N вершинами и 2M рёбрами.

→ Ответить

13 лет назад, # ^ |

Нету логарифма, это у меня сегодня просто день неадеквата %)

→ Ответить

13 лет назад, # ^ |

Доказывается несложно. Надо только доказать, что для случая k = 1 всегда есть полуцелый оптимум. Это можно сделать с помощью потоковых соображений (задачу можно переформулировать в терминах стоимостного потока), либо непосредственно (в точке оптимума хотя бы n линейно независимых неравенств должны обратиться в равенства, нарисуем это как граф, чётных циклов там не бывает, нечётные циклы дают полуцелое решение - как-то так).

→ Ответить

Hohol

13 лет назад, # ^ |

Как переформулировать задачу в терминах потока?

→ Ответить

13 лет назад, # ^ |

Да, 3 месяца спустя суровый вопрос :)
По идее там для каждой переменной надо создать 2 вершины, а каждое неравенство порождает 2 дуги. Т.к. для соединённых дугой остаточной сети вершин есть неравенство на потенциалы и стоимость дуги, то правильно расставив дуги можно получить те неравенства, которые требуются, точнее попробуйте продумать сами. Но вообще это довольно известное сведение, можно и загуглить.

→ Ответить

alloff

13 лет назад, # |

скажите,пожалуйста,как решалась задача I.какие там такие фишки особенные?

→ Ответить

freopen

13 лет назад, # ^ |

Никаких. Ищем все отрезки, на которых одна из палок падает и строим объединение. Чтобы левая палка упала влево, надо разрубить ее слева от первой стойки, или справа не дальше, чем длина от края до первой стойки. Чтобы левая палка упала вправо, ей надо упасть с какой-то стойки(т.е. палка будет касаться этой стойки, когда упадет). Тогда надо отступить от этой стойки как минимум на расстояние равное расстоянию от левого края до стойки (при этом нельзя разрубить правее следующей стойки). Справа также.

→ Ответить

alloff

13 лет назад, # ^ |

странно,у меня с таким алгоритмом ва5.

можно ли посмотреть Ваш код?

→ Ответить

freopen

13 лет назад, # ^ |

Пожалуйста, вот он.

→ Ответить

frost_nova

13 лет назад, # |

А как решалась F? Достаточно простое решение через суффиксный массив, мы так и не смогли запихать в ТЛ (хотя локально работало 4с).

→ Ответить