У кого будет желание - напишите разбор тренировки.
В первую очередь интересно D (как нужно было искать максимальный LCM), A, C, G.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | qwexd | 130 |
Условия 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 и заметим, что игра теперь в точности соответствует лестничному ниму.
Если кому-то хочется упражнений – вот задача на ту же тему на топкодере.