algoprog.kz

Ограничения в этой задаче $N \le 10^{2000}$.

Пусть длина $N$ равна n.

Для длины $k$, количество палиндромов будет $10^[k/2]$, где $[x]$ = округленное значение $x$.

Надо сложить все значения для $k = 1..n-1$.

Теперь рассмотрим палиндромы длины n. Будем считать количество палиндромов так:

если $N = abc...xyz$, то прибавляем к ответу:

$(a-1)$99 ... 9 (до середины, так как это палиндром)

$a$$(b - 1)$99 ... *9 (так же до середины)

... И так далее.

Cложность будет примерно $O(n^2)$.

Надо найти количество построений дорог между $N$ центрами, где $N \le 100$.

Можно представить сеть центров, как ориентированный граф с $N$ вершинами.

Максимум дорог(неориентированных) между вершинами такого графа может быть $C_N^2 = \frac{N(N-1)}{2}$.

И у каждой дороги($u - v$) будет три состояния:

$u \to v$.

$v \to u$.

дорог между $u$ и $v$ вообще нет.

То есть ответ: $3^{\frac{N(N-1)}{2}}$. Так как ответ может быть большим, надо использовать

длинную арифметику.

Сперва надо отсортировать все окружности по углу(угловая сортировка). Можно было сортировать по

тангенсу угла. Дальше надо было придумать формулу для нахождения длины части веревки соединяющей

две последовательные окружности. Точную формулу можете вывести сами, для этого нужно знать, как

вычислять расстояние между двумя точками в декартовой системе координат, и знать теорему

косинусов.

Сложность будет $O(NlogN)$.

Надо найти количество таких заполнений бланков ответа из $N$ вопросов по $K$ ответов, чтобы ни в

одном варианте заполнения не было ни одного правильного ответа.

Нам дано какое-то множество правильных ответов к каждому вопросу, и мы можем выбрать любой

вариант ответа, кроме правильного. Т.е., если есть $K$ ответов, то один из них правильный, а

остальные $K-1$ неправильные. Всего вопросов $N$ и мы можем выбрать любые $K-1$ неправильных

ответов. Значит ответ: $(K-1)^{N}$. Здесь также нужно воспользоваться длинной арифметикой.

В данной задаче надо быстро проверять, находиться ли в таблице Менделеева

элемент $s_i + s_{i+1}$(конкатенация двух символов строки $s$).

Для этого в C++, можно воспользоваться map'ом. Сложность будет $O(NlogM)$

Так же можно завести буленовый массив 26x26(в паскале можно сделать array['a'..'z', 'a'..'z'] of

boolean). И для каждого элемента хранить true, если он есть в таблице Менделеева, иначе false.

Или можно просто хранить элементы в хэш-таблице. Тут ограничения не большие и методов много. То

есть сложность при таких методах будет $O(N)$

Сперва решетом находим все простые числа от $1$ до $N$. Понятно, что все эти числа и есть

делители $N!$,

потому что $N! = 1 * 2 * ... * N$.

И записываем простые числа в массив $p[]$.

То есть он будет выглядеть так: $p[1] = 2, p[2] = 3, p[3] = 5, \dots$

Требуется посчитать, с какой степенью простой делитель $p$ входит в число $N!$,

т.е. найти наибольшее $x$ такое, что $N!$ делится на $p^x$.

Теперь как надо искать $x$ для $p$?

$x = [{\frac{N}{p}}] + [{\frac{N}{p^2}}] + [{\frac{N}{p^3}}] +\dots$

Конечно, не до бесконечности, потому что берем только целую часть.

Сложность нахождения степени делителя факториала $ O(log_{p}N) $

Итоговая сложность $\approx O(NlogN)$, если считать грубо.

Будем решать задачу с помощью сведения ее к аналогичной с меньшими числами. Пусть на i-ом шаге требуется вычислить цепную дробь для $\frac{p}{q}$. Тогда $a_i=\lfloor\frac{p}{q}\rfloor, \frac{p}{q} = a_i + \frac{1}{x}, x = \frac{q}{p \mod q}$. Таким образом мы свели задачу к решению задачи для дроби $\frac{q}{p \mod q}$. Заметим, что сумма числителя и знаменателя уменьшилась. Так как она будет все время уменьшаться, то рано или поздно получим дробь $\frac{1}{1}$.

Источник разбора neerc.ifmo.ru