Решение задачи заключается в том, что бы просуммировать все числа которые записанны на карточках, и пытатся эту сумму свести к нулю за минимальное количество операций, используя операции +х и -х.
Решение А
Поскольку ограничения в этой задаче не очень большие, то можно написать простой жадный алгоритм. Вначале обозначить в массиве номера контестов которые запомнил Сережа, как занятые. Для нахождения максимального количества контестов, нужно посмотреть сколько ячеек, номера которых меньше за х, еще не заняты. Это и будет максимальный ответ. Для нахождения минимального количества, нужно пройтись по массиву и пытаться как можно больше вставлять контести типа "Div1+Div2" — это можно будет сделать, если будут свободны две подряд ячейки нашего массива. Если же нельзя вставить контест типа "Div1+Div2", тогда в свободный номер забиваем контест типа "Div2". Проделав такие операции, мы узнаем минимальное количество контестов.
Решение Б
Эту задачу можно было делать несколькими способами, я расскажу Вам об одном из них. Обозначим количество карточек на которых записано 0 — n, а количество карточек на которых записано 1 — m. Тогда можно сделать нужную последовательность когда (n - 1 <= m && m <= 2 * (n + 1))
.
Если же все таки можно сделать нужную последовательность, рассмотрим 3 случая:
(m == n - 1)
. Тогда выводим единички и нули через один, но обязательно начинаем с 0.
(m == n)
. Тогда выводим единички и нули через один, но тут мы можем начинать и с 0, и с 1
(m >= n + 1 && m <= 2 * (n + 1))
. В этом случае нам обязательно нужно начинать с 1 и выводит единички и нули через один. В конце тоже должна быть обязательно единичка. Если мы доходим до конца но единички еще остались, то пытаемся прилепить по одной единичке к тем что у нас есть. Например у нас было 10101, у нас осталось две единички, делаем сначала 110101, а потом 1101101. После таких операций мы получим правильный ответ.
Решение С
На счет того что некоторые решения не проходили 11 тест на FPC, но проходили на Delphi, то в этой ситуации участник должен был понимать, что на Паскале вывод займет достаточно много времени, и он должен был или как-то оптимизировать решение, или же написать в другой среде.
Эту задачу можно отнести к теме динамическое программирование. Используя маски для запоминания взятых уже цифр мы можем с помощью динамики очень легко решить эту задачу. Пускай у нас будет динамика — dp[i][x]
, где i — маска перестановки, а х — это остаток от деления данной перестановки на m. Будем перебирать сами маски и остаток. При добавлении цифры a[j] будем использовать такой переход:
dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] := dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] + dp[i,x];
Обязательно в конце нужно ответ поделить на факториал количества вхождений каждой цифры, поскольку у нас может получиться несколько одинаковых перестановок, а это недопустимо.
for i:=0 to 9 do
for j:=2 to b[i] do
ans:=ans div int64(j);
Для улучшения времени работы программы, можно приписывать одинаковые цифры в порядке их следования в числе.
Решение Д
Для начала в этой задаче нужно было понять, что пару учеников мы могли задавать в виде прямоугольника. Тогда расстояние между учениками это диагональ прямоугольника. Пускай первый ученик находится в точке (x1,y1), а второй в точке (x2,y2). В этом случае нам нужно что бы выполнялись два условия:
Так как поле может быть 100000*100000, то понятно что перебор значений abs(x1-x2)
и abs(y1-y2)
займет достаточно много времени. Поэтому будем перебирать только одно значение, а количество вхождений второго вычислять из нашего неравенства:
Количество вариантов разместить наш квадрат на поле n*m будет (n-abs(x1-x2)+1)*(m-abs(y1-y2)+1)
. Вычисление суммы (n-abs(x1-x2)+1)
не очень сложное, но вот что бы вычислить сумму (m-abs(y1-y2)+1)
, где (L*L<=abs(x1-x2)*abs(x1-x2)<=abs(y1-y2)*abs(y1-y2)<=R*R-abs(x1-x2)*abs(x1-x2))
, будет немного тяжелее. Нужно использовать метод включения-исключения и найти сумму чисел на отрезке, которые делятся хотя бы на один из простых множителей нашего числа abs(x1-x2)
.
К сожалению, по моей вине, в раунд попала задача которая ранее была использована на другом соревновании. Так как это не соответствует правилам Codeforces, задача E будет удалена.
Решение Е
Хочу сказать спасибо Сергею Орышичу (Oryshych) за помощь в написании разбора.