A. Будем идти сверху вниз и восстанавливать ответ. Нижнюю грань 1й кости восстановить легко. Далее по двум граням 2й кости можно установить какая пара чисел должна быть на верхней и нижней грани. Если одно из чисел совпадает с числов на нижней грани 1й кости, то 2я кость восстанавливается однозначно, и так далее. Если мы смогли восстановить все кости — выводим YES. Если где то возникла неоднозначность, то можно показать, что эта однозначность будет сохраняться и для всех последующих костей. То есть получится хотя бы 2 разничных ответа, поэтому нужно выводить NO.
Автор — Ripatti .
B. Сначала сгенерируем все числа k-боначчи, не превышающие n. Для k ≤ 32 это можно сделать в лоб, а для больших k можно заметить, что числа k-боначчи до 109 являются только степени двойки (и еще 0). Итого получим не более 100 чисел.
Далее предлагается действовать жадно — отнимать от n самое большое число k-боначчи, не превышающее n до тех пор, пока не разложим полностью.
Почему все полученные числа будут различны? Вот одно из возможных доказательств:
F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)
F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)
Вычтеми из 1го равенства 2е и получим F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), то есть 2F(k, n - 1) ≥ F(k, n). Это неравенство так же справедливо и для n ≤ k.
теперь предположим, что жадный алгоритм даст 2 одинаковых числа F(k, x) в разложении. Но тогда, в силу неравенства, мы должны были взять число F(k, x + 1). Противоречие.
Впрочем, доказывать это не требовалось, можно было просто поверить что жадность пройдет:)
Авторы — Gerald , Ripatti .
C. Сначала посчитаем число белых и черных пикселов в каждом столбике. После этого посчитаем сумму черных и белых пикселов на каждом префиксе в последовательности столбиков. Это позволит нам за O(1) вычислять количество черных и белых пикселов на любом отрезке столбиков.
Далее воспользуемся динамическим программированием. dp[i][j] будет хранить наименьшее число перекрашиваемых пикселов на префиксе от 1го столбика до j-го, причем цвет последней полосы будет белым для i = 0 и черным для i = 1.
Далее dp пересчитывается следующим образом: dp[0][0] = dp[1][0] = 0
Ответом будет min(dp[0][m], dp[1][m]).
Итого решение за O(nm + m * (y - x)).
Автор — Ripatti .
D. Обычный поиск в ширину. Состояние — положение головы + маска, которая задает положение хвоста, а именно: двумя битами кодируется относительное положение каждого сегмента (кроме головы) относительно предыдущего. Итого в маске максимум 16 бит, оценка на общее число состояний — 48 × 15 × 15 (на самом деле можно даже показать оценку порядка 38 × 15 × 15).
Далее нужно просто все очень аккуратно реализовать.
Автор — Ripatti .
E. Дано: z = [x / 2] + y + xy. Это равносильно
z = [2k / 2] + y + 2ky, где x = 2k, k > 0
или
z = [(2k + 1) / 2] + y + (2k + 1)y, где x = 2k + 1, k ≥ 0.
Преобразуем:
z = k + y + 2ky, k > 0
или
z = k + y + (2k + 1)y, k ≥ 0.
Еще пару шагов:
2z + 1 = 2k + 2y + 4ky + 1, k > 0
или
z + 1 = k + 2y + 2ky + 1, k ≥ 0.
2z + 1 = (2k + 1)(2y + 1), k > 0
или
z + 1 = (2y + 1)(k + 1), k ≥ 0.
Из второго уравнения видно, что z должно быть вида 2t - 1, иначе z + 1 имеет нечетный делитель и мы можем подобрать решение. Из первого же уравнения получаем, что 2t + 1 - 1 должно быть простым, иначе опять можно подобрать решение. Если же z = 2t - 1, а 2t + 1 - 1 — простое, то очевидно, что уравнение неразрешимо.
Простые числа вида 2a - 1 являются простыми числами Мерсенна, на данный момент найдено всего 46 чисел такого вида. Показатели степени для первых 40 из них можно найти, например, здесь.
Автор — Ripatti .