А. Буквы и Весы
Делается напрямую. Пусть весов меньше, чем букв в результирующем слове, тогда ответ 'Impossible', иначе пройдем по строке и сложим стоимости букв.
B. Геном-палиндром
1) Заметим, что лексикографический порядок палиндромов зависит только от их первой половины( m=(n+1)/2 ), вторая по ней восстанавливается однозначно
2) Забудем про буквы и заменим их на числа 0-3.
Тогда для k=1 мы должны вывести 0000000, k=2 - 0000001 и т.д. то есть представить k-1 в четверичной позиционной системе счисления. Будем постепенно заполнять строку с конца остатком текущего k по модулю 4 и делить его на 4. Пусть после m делений у нас k не занулилось, значит, k больше, чем 4^m и ответ Impossible, иначе разворачиваем полученную строку и добавляем ее в конец(не забыв про четность/нечетность n)
С. Елка
Сохраним l[i]
Заметим, что нам важны только расстояния между ветками, а не их реальные высоты, поэтому можем считать h[1]=0.
Далее вводить данные h: h[i]=h[i-1]-введенное число.
Таким образом мы получим все высоты, на которых располагаются ветки. Осталось отсортировать их в порядке неубывания, чтобы сопоставить их номерам веток.
Теперь уже несложно отвечать на запросы гномов:
abs(h[i]-h[j])+l[i]+l[j]
Не забываем, что h[i] может быть до 1014, поэтому юзаем long long и подобнные
D. Большая сумма.
1) gcd(d,i)=gcd(d,kd+i), поэтому внутренняя сумма равна n/d * сумму от 1 до d gcd(d,i)
2) Осталось научиться быстро считать эту сумму.
Обозначим ее за f(d). легко понять что f(p)=2p-1
Далее, f(pn)=(p-1)p(n-1)+pf(p(n-1)), отсюда явная формула: f(p^n)=(n+1)pn-np(n-1) . Далее, замечаем, что функция мультипликативна. Это несложно доказать для произведения двух простых. Для непростых доказать у меня не получилось, буду рад, если кто-то расскажет, это просто проверил для маленьких и поверил.
3) Замечаем, что каждое d можно не факторизовать как обычно, а сделать это чуть побыстрее имея факторизацию n. (Не знаю, нужно ли это)
UPD: решение от i7cix:
Заметим, что внутренняя сумма это w*fi(d/w) для всех w-делителей d. таким образом нужно посчитать для всех делителей w числа n для всех чисел таких что n кратно d,d кратно n сумму d/w(fi(w)). Найдем все делители за sqrt(n), отсортируем, а потом за квадрат от кол-ва делителей легко посчитаем требуемое
Комментарии (8)
0
