Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

[ERROR] Unexpected error has been found: Unexpected verdict CRASHED, comment=Can't find input for test. Are you sure generator produces it?
Input:

В чем может быть проблема?
Могу дать доступ для того, тобы посмотреть ибо задача - не задача там

Заранее спасибо

А. Буквы и Весы

Делается напрямую. Пусть весов меньше, чем букв в результирующем слове, тогда ответ '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] может быть до 10¹⁴, поэтому юзаем 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(pⁿ)=(p-1)p^(n-1)+pf(p^(n-1)), отсюда явная формула: f(p^n)=(n+1)pⁿ-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), отсортируем, а потом за квадрат от кол-ва делителей легко посчитаем требуемое

Полный текст и комментарии »

Блог пользователя riadwaw

А. Буквы и Весы

B. Геном-палиндром

С. Елка

D. Большая сумма.