Олимпиады

М.С. Густокашин,
Москва

От редакции. Мы возобновляем добрую традицию регулярных публикаций олимпиадных материалов. Начиная с этого номера, разбор олимпиадных задач (по одной—две в номере) будет готовить Михаил Сергеевич Густокашин, преподаватель ЦДО “Дистантное обучение”, г. Москва.

Известный маг и чародей Асмодей открыл метод предсказывать будущее. Суть метода заключается в следующем: прохожих на улице просят назвать случайное целое число от 1 до 10 000, процесс прекращается, когда очередной прохожий отказывается назвать число, затем числа суммируются по секретной формуле и от результата берется остаток от деления на магическое число 981 537.

Опишем секретную формулу суммирования. Допустим, всего опросили N человек, тогда сумма равна S = N•A₁ + (N – 1)•A₂ + … + 2•A_N–1 + 1•A_N, где A_i — число, сказанное i-м человеком. Остается только посчитать остаток от деления суммы на магическое число.

Однажды Асмодей решил предсказать свое будущее, посчитал число, которое определяет его будущее, схватился за сердце, посерел, выронил листок с формулами из рук и дематериализовался. Его ученик расшифровал записи, просчитал свою судьбу, впал в депрессию и ни с кем с тех пор не разговаривал. В целях безопасности реализуйте подсчет числа, определяющего будущее, в виде программы.

На вход дается последовательность натуральных чисел A_i (1 A_i 10 000). Максимальное количество чисел в последовательности 300 000. Признаком конца последовательности служит число 0.

Выведите остаток от деления S, посчитанного по секретной формуле, на 981 537.

 Пример

Комментарий к примеру

S = 10•5 + 20•4 + 30•3 + 40•2 + 50•1 = 350. Остаток от деления 350 на 981 537 равен 350.

Решение

Решить эту задачу очень легко, если заранее знать общее количество названных чисел: достаточно записать их в массив, идти по нему с конца и считать сумму всех чисел, умноженных на их порядковый номер с конца. Однако из-за ограничений на размер памяти сохранить их в массив невозможно (на каждое из 300 000 чисел требуется как минимум 2 байта, в итоге созданный массив будет занимать слишком много места и решение не будет удовлетворять ограничениям на максимальный размер используемой памяти).

Другой возможный способ состоит в том, чтобы при первом прочтении просто подсчитать количество чисел, а затем открыть файл заново и последовательно подсчитывать сумму, зная коэффициент для каждого из чисел. Чтобы участники не пользовались таким способом, в данной задаче жюри использовало для ввода-вывода стандартные потоки (ввод с клавиатуры и вывод на экран), что делает возможным только однократное чтение.

Поняв невозможность применения простых методов, начнем искать конструктивное решение. Причем начнем искать его “с конца”, по аналогии с методом математической индукции. В информатике для такого метода используется термин “динамическое программирование”, но способ его применения очень похож на индукцию (и в какой-то мере на рекуррентные соотношения).

Если нам дано всего одно число, то задача решается элементарно: ответом будет просто это число. Теперь необходимо научиться решать задачу для N чисел, если известен ответ для N – 1 числа. Будем считать, что нам известно число

S_N–1 = (N – 1)•A₁ + (N – 2)•A₂ + … + A_N-1.

Исходя из знания S_N-1 и очередного входного числа A_N, необходимо получить S_N. Рассмотрим формулу, по которой вычисляется результат для N чисел:

S_N = N•A₁ + (N – 1)•A₁ + … + A_N-1.

Формулы очень похожи, для наглядности запишем их друг под другом:

S_N = N•A₁ + (N – 1)•A₂ + … + 2•A_N-1 + 1•A_N

S_N-1 = (N – 1)•A₁ + (N – 2)•A₂ + … + 1•A_N-1

Каждый коэффициент при переменных A_i в S_N отличается от соответствующего коэффициента в S_N-1 на 1. То есть

S_N – S_N-1 = A₁ + A₂ + … + A_N и S_N = S_N-1 + A₁ + A₂ + … + A_N, S₀ = 0.

Таким образом, если мы будем на каждом шаге знать сумму всех элементов без коэффициентов, то сможем узнать значение S_N, просто прибавив эту сумму к S_N-1!
А для хранения текущего значения подобной суммы достаточно одной переменной.

Однако в реализации и этого решения есть подводные камни. Если внимательно посмотреть на количество и максимальный размер каждого элемента последовательности, то можно заметить, что искомая сумма может быть очень большой (больше, чем 2³¹ — максимальное число, представимое типом longint в Паскале или соответствующим 32-битным целым типом в другом языке программирования). Такая же проблема возникает и для суммы без коэффициентов — она может превысить максимально допустимое значение типа данных, достаточного для хранения исходных переменных.

Здесь поможет знание следующей формулы для суммы остатков: (A + B) mod C =
= (A mod C + B mod C) mod C. Из этой формулы следует, что мы можем брать остаток от деления на каждом шаге без ущерба для ответа. С учетом всех этих моментов, решение данной задачи на языке Паскаль будет выглядеть следующим образом:

var

s, d, i: longint;

begin

s := 0;{сумма на предыдущем шаге с коэффициентами}

d := 0;{сумма без коэффициентов}

repeat

read(i); {считываем очередное число}

if i <> 0 then begin

d := (d + i) mod 981537;

{добавляем новое число к сумме без коэффициентов}

s := (s + d) mod 981537;

{добавляем сумму без коэффициентов

(уже с учетом очередного числа) к результату}

end;

until i = 0;{дошли до конца последовательности}

writeln(s) {выводим ответ}

end.

При реализации важно не забыть, что последнее число 0 не входит в последовательность (в приведенной выше реализации для этого делается сравнение с нулем и пересчет происходит только в случае ненулевого очередного числа).

В решении данной задачи, помимо алгоритма, продемонстрировано, на что следует обращать внимание при программировании олимпиадных задач, а именно, следует учитывать диапазон значений применяемых типов данных и размер используемой памяти.