У кого будет желание - напишите разбор тренировки.
В первую очередь интересно D (как нужно было искать максимальный LCM), A, C, G.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Условия G я так и не понял, сколько ни читал. Может кто-нибудь перевести его на русский?
Не совсем.
В этой задаче граф представлялся в виде узлов и ниток.
И несколько узлов по типу бус могли нанизываться на несколько ниток.
Вот кол-во таких ниток необходимо было найти. Это очень похоже, но через одну вершину могло проходить несколько ниток.
для начала, давайте найдем такое разбиение числа n на слагаемые, чтобы их LCM было максимальным. Это делается так:
пусть p1, ..., pn - это простые числа меньшие 10000. будем искать динамикой факторизацию нашего LCM. динамика такая - d(n, v), т.е. нам нужно разбить число n на слагаемые, но так, чтобы lcm были только простые множители большие или равные pv. тогда мы перебираем, в какой степени pv войдет в lcm, пусть это i. тогда мы делаем так d(n, v) = max(pvi * d(n - pvi, v + 1)).
еще есть один переход это d(n, v) = max(d(n, v), d(n, v + 1)), который всего лишь означает, что мы не будем брать это простое число.
ну а терминальные состояния динамики это такие, когда кончились простые числа или n = 0. в этом случае возвращаем 1.
отлично, теперь получили последовательность xi, ..., xk, которые в сумме дают n. отсортируем их, и будем поочередно откусывать префикс длины xi от тождественной перестановки, делать циклический сдвиг (понятно, в какую сторону), и выводить ответ. с оставшимся куском сделаем тоже самое с xi + 1 и т.д. Так мы получим ответ - нужную перестановку.
83724831478115383622262752790863851979860
82140399546460688951570703826229121845328
63125113007409531931972405106926383184266
36506681182400
... я перенес на для того, чтобы сообщение не уползало.
да уж, число-то 140 знаков...
но есть большой косяк - это асимптотика и память. простых чисел до 10000 - примерно 1300 штук. получается динамика размером 107 примерно. вобщем, ничего страшного, но тут нужны были BigInteger, и поэтому это все очень печально.
а будем делать вот так... заметим, что из этих 1300 чисел только первые k используются где-либо. Я не знаю, чему точно оно равно, но я взял k = 100 и у меня прошло. Подумайте сами, почему это отсечение имеет смысл. Получаем динамику 10000*100. и то, она на макс-тесте ест примерно 90 метров памяти, и считается секунду.
А чтобы узнать сколько простых хватит, можно запустить динамику 1300 * 10000 и найти максимальное простое которое используется :)
может косяк в чем-то другом?
например для n = 9999, первые 9 чисел ответа такие:
1 2 3 4 5 6 7 8 10
Как A делать? Можно сделать обход начиная с элементов с известным состоянием и вычислить состояние некоторых других (там где оно однозначно получается). А как быть с остальными ?
Сначала научимся играть в Staircase nim. Правила такие: на каждой ступеньке конечной лестницы лежит некоторое (возможно, нулевое) количество камней. Ступеньки занумерованы, начиная с единицы. За один ход можно взять какое-то (положительное) число камней с любой из ступенек и переложить ровно на одну ступеньку вниз. С пола ("нулевой ступеньки") камни брать нельзя. Проигрывает тот, кто не может сделать ход.
Решение: Граф игры конечный и ациклический, поэтому существует функция Шпрага-Гранди. Оказывается, что она равна xor'у размеров всех кучек камней на ступеньках с нечётными номерами. Действительно, перекладывать камни с чётных ступенек не имеет смысла, т.к. противник переложит то же число камней ещё на ступеньку ниже, и значение нашего xor'а не изменится, а переложить что-то с нечётной ступеньки на чётную – это всё равно что взять сколько-то камней из соответствующей кучки в обычном ниме. Теперь нужно определить, какие ходы будут выигрышными. Пусть g > 0 – значение функции Шпрага-Гранди нашей позиции. Если мы хотим сделать выигрышный ход, взяв y камней со ступеньки с нечётным номером, в которой сейчас лежит x камней, то должно выполняться (g xor x) xor (x - y) = 0, откуда y = x - (g xor x). Если же мы хотим переложить y камней с чётной ступеньки на нечётную, в которой сейчас x камней, то (g xor x) xor (x + y) = 0, и y = (g xor x) - x. Если столько камней взять возможно, то соответствующий выигрышный ход существует.
Теперь сведём нашу задачу к этой игре. Для этого будем считать, что пешка, справа от которой находится k свободных клеток, соответствует камню, который лежит на ступеньке с номером k. Тогда все соседние пешки соответствуют камням из одной и той же кучки, а ступенька 0 свободна по условию. Если ступенька 1 занята, то все ходы с помощью соответствующих пешек выигрышные, а остальные – проигрышные. Если же и первая свободна, то уменьшим номера всех ступенек на 2 и заметим, что игра теперь в точности соответствует лестничному ниму.
Если кому-то хочется упражнений – вот задача на ту же тему на топкодере.