РАЗБОР
Задача A. Электронное табло
Если в некоторый момент на табло записано число X, то для того, чтобы отобразить на нем число X + 1, нужно произвести столько операций замен цифр, в каком количестве разрядов числа X и X + 1 отличаются. Например, чтобы перейти от числа 2413 к числу 2414, нужно произвести одну операцию замены, а чтобы перейти от числа 7999 к 8000, нужно заменить все 4 цифры. Ответ на задачу — это суммарное количество операций замен для всех требуемых переходов, то есть для всех значений X от A до B − 1.
С помощью цикла for переберем все возможные значения X от A до B −1. Один из вариантов, что делать дальше — это честно выписать цифры чисел X и X + 1 и проверить все 4 разряда на равенство. В другом варианте можно заметить, что количество различных цифр соответствует количеству нулей в конце записи числа X + 1:
• если оно не делится на 10, то заменить нужно только одну цифру (1234 → 1235),
• если делится на 10, но не на 100, то две (1239 → 1240), • если делится на 100, но не на 1000, то три (1299 → 1300),
• если делится на 1000, то четыре (1999 → 2000).
Первый вариант решения: https://ideone.com/ShhEVT
Второй вариант решения: https://ideone.com/OX05fy
B. Остатки сумм
| Ограничение времени | 2 секунды |
| Ограничение памяти | 256Mb |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Дана последовательность из n целых чисел [a1, a2, … an]. Подотрезком последовательности a называется любая последовательность подряд идущих элементов из a. Например, если a = [10, 3, 7, 8] то подотрезками a являются [10], [3], [7], [8], [10, 3], [3, 7] и [7, 8], [10, 3, 7], [3, 7, 8] и [10, 3, 7, 8].
Рассмотрим все подотрезки последовательности a. Сколько из них таких, что сумма их элементов дает остаток y при делении на x?
Формат ввода
Первая строка ввода содержит три целых числа n, x, y (1 ≤ n ≤ 106), (0 ≤ y < x ≤ 106) — количество элементов последовательности.
Вторая строка содержит n целых чисел a1, a2, …, an (0 ≤ ai ≤ 106) — элементы последовательности a.
Формат вывода
Выведите количество подотрезков последовательности a таких, что сумма их элементов дает остаток y при делении на x?
Пример 1
| Ввод | Вывод |
| 4 7 310 3 7 8 | 3 |
Пример 2
| Ввод | Вывод |
| 4 7 010 3 7 8 | 2 |
Пример 3
| Ввод | Вывод |
| 4 7 510 3 7 8 | 0 |
Пример 4
| Ввод | Вывод |
| 3 4 18 5 3 | 2 |
Примечания
Пояснение к первым трем примерам.
Все подотрезки, суммы их элементов и остатки этих сумм при делении на 7:
· [10], сумма элементов равна 10, остаток при делении на 7 равен 3
· [3], сумма элементов равна 3, остаток при делении на 7 равен 3
· [7], сумма элементов равна 7, остаток при делении на 7 равен 0
· [8], сумма элементов равна 8, остаток при делении на 7 равен 1
· [10, 3], сумма элементов равна 13, остаток при делении на 7 равен 6
· [3, 7], сумма элементов равна 10, остаток при делении на 7 равен 3
· [7, 8], сумма элементов равна 15, остаток при делении на 7 равен 1
· [10, 3, 7], сумма элементов равна 20, остаток при делении на 7 равен 6
· [3, 7, 8], сумма элементов равна 18, остаток при делении на 7 равен 4
· [10, 3, 7, 8], сумма элементов равна 28, остаток при делении на 7 равен 0
Таким образом, количество подотрезков с остатком 3 — три, с остатком 0 — два, с остатком 5 — ни одного.
РАЗБОР
Остатки сумм
Насчитаем вспомогательный массив s [0 ..n ] следующим образом:
• s 0 = 0
• si = a 1 + a 2 + ... + ai = si −1 + ai, i > 1.
Массив s называется массивом префиксных сумм массива a. С помощью этого массива можно эффективно находить сумму элементов любого подотрезка массива a [ l..r ]:
al + al +1 + ... + ar = (a 1 + a 2 + ... + ar) − (a 1 + a 2 + ... + al −1) = sr − sl −1
Таким образом, мы можем перейти к новой задаче: по заданному массиву s найти количество пар индексов l, r таких, что 1 6 l 6 r 6 n и (sr − sl −1) mod x = y, что на самом деле можно упростить и записать как
0 6 l < r 6 n, (sr − sl) mod x = y.
Здесь A mod B означает остаток от деления A на B.
Заметим, что если (sr − sl) mod x = y, то sr mod x = (sl + y) mod x. Здесь можно провести аналогию с обычным вычитанием чисел – если для чисел A, B, C верно, что A − B = C, то верно и A = B + C, только в нашем случае всех операции впоследствии заменяются взятием остатка от деления. Например, раз (17 − 7) mod 6 = 4, то и 17 mod 6 = (7 + 4) mod 6 = 5.
Итак, теперь наша задача выглядит следующим образом. Требуется найти количество пар индексов l, r, что
0 6 l < r 6 n, sr mod x = (y + sl) mod x.
Заведем массив t [0 ..n ], для каждого элемента которого верно ti = (si + y) mod x, а все элементы s заменим остатком от деления на x. А теперь требуется найти количество пар индексов l, r, что
0 6 l < r 6 n, sr = tl.
Эту задачу будем решать следующим образом. Заведем новый массив-счетчик f, где fj будет означать, сколько элементов массива t на текущий момент равны j. Изначально все значения массива f равны нулю. Будем перебирать индекс r слева направо от 1 до n. Для каждого r в массиве f будут находится только те значения элементов tl, для которых l < r.
Пусть имеется некоторое значение r. Сперва нужно добавить в массив f элемент массива t, который раньше нельзя было использовать как tl из условия выше — это элемент tr −1. Количество подходящих значений элементов массива t для текущего значения sr равно fsr; сумма этих значений и есть ответ на задачу.
Реализация: https://ideone.com/flTBPD.
Простое, но медленное решение, получающее 60 баллов: https://ideone.com/cVDKG5. Нужно не
забыть, что ответ на задачу и сумма элементов подотрезка могут превысить 32-битные типы данных (longint для FPC и int для C++), в таком случае это решение набирает на 10 баллов меньше.
C. Числа на листочке
| Ограничение времени | 1 секунда |
| Ограничение памяти | 256Mb |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
У Васи есть два натуральных числа a и b. Вася выписывает числа на листочек следующим образом:
· сначала он записывает на листочек число a
· затем он записывает на листочек число 
· затем он записывает на листочек число 
· затем он записывает на листочек число 
· …
· так он делает до тех пор, пока число, которое он хочет записать на листочек, не становится равным нулю
Запись 
означает целую часть от деления x на y.
Вася выписал все числа и посчитал их сумму — она оказалась равна n. После этого Вася, довольный собой, придумал задачку: даны числа n и b — найдите какое-нибудь такое натуральное a, что если для данного b выписать числа на листочек, как описано выше, то сумма выписанных чисел будет равна n. Эту задачку Вам и предстоит решить.
Формат ввода
Первая и единственная строка ввода состоит из двух натуральных чисел n, b (1 ≤ n ≤ 109, 2 ≤ b ≤ 109).
Формат вывода
Выведите любое подходящее a. Гарантируется, что тестовые данные таковы, что всегда существует хотя бы одно подходящее a.
Пример 1
| Ввод | Вывод |
| 18 2 |
Пример 2
| Ввод | Вывод |
| 54 4 |
РАЗБОР
Задача C. Числа на листочке
Для удобства обозначим через f (a) сумму чисел, которую выпишет Вася на листочек, если начнет с числа a. Например, если 
.
В задаче нужно найти такое минимальное значение a, что f (a) > n.
Нетрудно заметить, что f (0) 6 f (1) 6 f (2) 6 f (3) 6 ..., или, другими словами, для любого a выполняется f (a) 6 f (a +1). То есть, чем больше a, тем больше значение f (a). Это так, потому что для каждого 
, а значит и сумма чисел на листике по всем k тоже больше для a + 1, чем для a.
Это дает возможность воспользоваться так называемой техникой бинарного поиска (в данном случае, бинарным поиском по ответу).
Вкратце, бинарный поиск выглядит следующим образом. Заведем два значения, l и r, которые будут означать, что ответ на задачу находится между l и r. В нашем случае изначально можно положить l = 0, r = n (т.к. f (0) = 0 < n, f (n) > n, а значения f не убывают). Будем сужать область поиска ответа, причем будем поддерживать так называемый инвариант, что всегда выполняется f (l) < n, f (r) > n. Пусть 
. Теперь есть два случая:
• f (m) < n. В таком случае можно сузить поиск, положив l = m (и сохранив инвариант),
• f (m) > n. В таком случае можно сузить поиск, положив r = m (и снова сохранив инвариант)
Таким образом, вычислив один раз значение функции f, можно в два раза уменьшить длину отрезка поиска ответа. Таких уменьшений будет не больше 30, потому что 230 > 109— максимального значения n. Однажды настанет момент, когда r − l = 1, то есть отрезок состоит из двух значений, но мы знаем, что f (l) < n и f (r) > n, следовательно ответ на задачу равен текущему значению r.
Решение: https://ideone.com/FDYS4c.
Решение без бинарного поиска (68 баллов): https://ideone.com/pPH5u7
D. Тройки
| Ограничение времени | 1 секунда |
| Ограничение памяти | 256Mb |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Вам даны два числа L и R. Нужно найти количество различных троек чисел x, y и z таких, что
L ≤ x, y, z ≤ R
и
где | — битовая операция «ИЛИ», 
— битовая операция исключающее «ИЛИ» (xor, сложение по модулю 2).
В современных языках программирования данные операции уже реализованы:
· Битовая операция «ИЛИ» в языках C++ и Python реализована с помощью оператора |, в языке Free Pascal — с помощью оператора or.
· Битовая операция исключающее «ИЛИ» в языках C++ и Python реализована с помощью оператора 
, в языке Free Pascal — с помощью оператора xor.
Результат операции «c = a ИЛИ b » вычисляется следующим образом. Числа a и b переводятся в двоичную систему счисления и, при необходимости, дополняются лидирующими нулями так, чтобы длина записи этих чисел совпадала. После этого каждый бит числа c находится следующим образом:
· если i -й бит числа a и/или числа b равен 1, то и у числа c i -й бит равен 1;
· в противном случае i -й бит числа c равен 0.
После этого число c переводится в десятичную систему счисления. Например, 5 | 3 = 1012 | 0112 = 1112 = 7.
Результат операции «c = a исключающее ИЛИ b » вычисляется следующим образом. Числа a и b переводятся в двоичную систему счисления и, при необходимости, дополняются лидирующими нулями так, чтобы длина записи этих чисел совпадала. После этого каждый бит числа c находится следующим образом:
· если i -й бит числа a не совпадает с i -м битом числа b, то i -й бит числа c равен 1;
· в противном случае i -й бит числа c равен 0.
После этого число c переводится в десятичную систему счисления. Например, 
= 
.
Формат ввода
В единственной строке входного файла заданы два числа L и R (1 ≤ L ≤ R ≤ 5 ⋅ 108).
Формат вывода
В единственной строке выведите количество различных троек чисел, удоволетворяющих заданным условиям.
Пример
| Ввод | Вывод |
| 3 7 |
Примечания
Обратите внимание на то, что тройки, отличающиеся только порядком этих трех чисел, являютя различными.
В примере подходящими тройками являются:
· 3 4 3
· 4 3 4
· 5 3 4
· 6 3 4
· 7 3 4
· 7 4 3
Оценивание:
· не менее чем в 30% тестов, R ≤ 300
· не менее чем в 60% тестов, R ≤ 5000
Язык
РАЗБОР
Немного про битовые операции https://bit.ly/2QMlTFc.
Решение на 38 баллов, перебирающее все возможные тройки чисел: https://ideone.com/m1fF6K
Для решения на 60 баллов нужно воспользоваться фактом, что если c = a ⊕ b, то b = c ⊕ a и a = b ⊕ c, то есть операция «xor» («исключающее или») обратна сама себе (для операции «or» («или»), кстати, это свойство не выполняется). Таким образом, значение z всегда однозначно восстанавливается из x, y: z = (x | y) ⊕ y. https://ideone.com/8CFUr5.
Пусть F (A,B,C) означает количество троек x, y, z, таких, что 0 6 x < A, 0 6 y < B, 0 6 z < C и
((x | y) == (y ⊕ z)). Тогда, пользуясь принципом включений-исключений (https://bit.ly/33dg4Dk),
ответ на задачу можно вычислить как F (R +1 ,R +1 ,R +1) - F (L,R +1 ,R +1) - F (R +1 ,L,R +1) - F (R + 1 ,R + 1 ,L) + F (L,L,R + 1) + F (R + 1 ,L,L) + F (L,R + 1 ,L) - F (L,L,L).
Для вычисления F (A,B,C)нужно хорошо понимать идею динамического программирования. В интернете существует множество статей про динамическое программирование, поэтому в рамках данного разбора мы не будем останавливаться на том, что оно из себя представляет. В данном случае будет использоваться техника динамического программирования «по числу» — по битовому представлению данных чисел.
Пусть dpi,fa,fb,fc означает количество троек префиксов чисел x, y, z длины i (от старших к младшим), для каждого бита j которого выполнялось (xj | yj) == (yj ⊕ zj) и при том:
• fa = 1, если данный префикс числа x полностью совпадает с префиксом длины i бит числа A, и fa = 0 если префиксы не совпадают, но при этом префикс числа x меньше префикса числа A как двоичное число,
• fb = 1, если данный префикс числа y полностью совпадает с префиксом длины i бит числа B, и fb = 0 если префиксы не совпадают, но при этом префикс числа y меньше префикса числа B как двоичное число,
• fc = 1, если данный префикс числа z полностью совпадает с префиксом длины i бит числа C, и fc = 0 если префиксы не совпадают, но при этом префикс числа z меньше префикса числа C как двоичное число.
База: dp 0, 1, 1, 1 = 1 — для длины 0 существует только одна тройка префиксов — пустая, и так как пустые множества что для x, y, z, что для A, B, C, совпадают, fa = fb = fc = 1.
Переход из состояния динамического программирования делается следующим образом. Пусть мы находимся в состоянии dpi,fa,fb,fc. Переберем 8 вариантов значений i +1-го по старшинству бита чисел x, y, z. Тогда переход можно совершить, если (xi +1| yi +1) == (yi +1 ⊕ zi +1) и при том, никакой префикс не стал больше своей соотвествующей границы. Такое могло произойти, если текущие префиксы совпадают, а новый бит числа больше этого же бита в числе-границе, то есть когда fa = 1 и xi +1 = 1, а Ai +1 = 0 и аналогично для y, z. В таком случае можно совершить переход в dpi +1, _ , _ , _ с новыми пересчитанными значениями fa, fb, fc.
Ответ для F (A,B,C) будет лежать в dpn, 0, 0, 0, где n - длина битовой записи чисел (достаточно взять n = 30).
Вариант реализации: https://ideone.com/uzuo57