А. Ярмарка оружия [реализация, математика]

Необходимо последовательно сравнить силы наборов, если текущая сила строго больше максимальной предыдущей, то обновляем максимальную и индекс лучшего набора. Вычислить силу набора можно было в нецелых числах как (сумма s_i, j / w_i), или сохранить числитель и знаменатель дроби (sum_smax и w_max) и сравнивая с текущим набором домножить обе части на (w_max·w_i). Не стоит забывать, что суммирование 10⁵ чисел до 10⁹ приведёт к переполнению типа integer.

Асимптотика: O(n·max(w_i))

Код в нецелых числах

Код в целых числах

B. Имённо-фамильный никнейм [перебор, строки]

Любое решение сводится к тому, чтобы максимизировать подстроку в n (ведь чем больше символов мы возьмём из n, тем меньше потребуется из f).

Обозначим длину такой подстроки за k.

1) Наивное решение может проверять все подстроки строки n для поиска максимального k, после чего искать недостающий конец строки в f. Это будет работать за O(q·|n|² + q·|f|) в теории, однако лишь в худшем частном случае, когда множество раз наблюдается значительное совпадение подстроки с первой часть строки s_i (пример: n = " ", f = " ", и все s_i = " ").

Код

2) Подсчитать все возможные подстроки для n за |n|², сложить в set[string] или бор, или подсчитать хеши (это будет работать аналогично set[string]). Теперь для каждого s_i можно последовательно искать k, после чего можно пройтись последовательно по f, узнав, есть ли там оставшиеся |s_i| - k символов. При использовании set[string] или хешей можно также искать k бинарным поиском, укорачивая или удлиняя текущую строку до длины M на каждой итерации и ища ей соответствие в подстроках n.

Асимптотики такого решения:

• Для хешей или set:
  • если искать k последовательно: O(q·k·log₂(|n|²) + q·|f|)
  • бинарным поиском: O(q·log₂(k)·log₂(|n|²) + q·|f|)
• Для бора: O(q·k + q·|f|)

Код с set[string], последовательная проверка k

Код с set[string], бинарный поиск по k

Код с бором

3) Развернём n, f, и s_i задом наперёд. Тогда нам нужно максимизировать не подстроку, а подпоследовательность в f, в этом единственное отличие от предыдущего варианта. Искать k для подпоследовательности можно только последовательно, после чего нам нужно найти в n подстроку длины |n| - k, для чего опять же следует предподсчитать все возможные подстроки для n за |n|² и сложить их в какую-нибудь структуру.

Асимптотика решения:

• Для хешей или set[string]: O(q·k + q·log₂(|n|²))
• Для бора: O(q·k + q·|n|)

C. Два великана [игры, математика]

Очевидно, что размер кучи от 1 до x является выигрышным для Тора, т.к. он может сломать её одним ударом.

А теперь давайте подумаем насчет n = x + 1. Если Тор сломает 1 кирпич, останется x кирпичей, и Арен победит, если Тор сломает x кирпичей, Арену останется 1 кирпич и он тоже выиграет.

Значит, куча размера x + 1 всегда является проигрышной для Тора. А это в свою очередь значит, что все кучи от x + 2 до 2x + 1 являются выигрышными — Тор может всегда сломать столько кирпичей, что Арену достанется куча размера x + 1 и тот проиграет.

Подобным образом рассуждаем дальше, применяя важное правило теории игр — если из состояния текущего игрока нет способа привести состояние в проигрышное (чтобы в нём оказался другой игрок, а текущий выиграл), значит для текущего игрока состояние проигрышное, и при оптимальной игре обеих сторон он всегда будет в проигрышном состоянии, а другой игрок наоборот, в выигрышном.

И получаем, что проигрышными для Тора являются только кучи кратные x + 1 (x + 1, 2x + 2, 3x + 3, ..). Тогда ответ на отрезке [1;n] можно найти как , обозначим это функцией f(n), тогда ответ на отрезке [L;R] равняется f(R) - f(L - 1).

Асимптотика: O(q)

Код