Начало
Соревнования
Разбор задачи A. Потерянная страница
Тема: вывод формулы или сортировкаСложность: простая
Ответ можно найти по формуле
n∑i=1 ,
где p_i – номера собранных страниц. Эту формулу можно еще упростить, вспомнив следующую историю о детстве математика Гаусса.
Школьный учитель математики, чтобы занять первокласников на время, пока он будет занимать с другими учениками, предложил им сосчитать сумму чисел от 1 до 100. Юный Гаусс заметил, что попарные суммы с противоположных концов одинаковы: 1+100=101, 2+99=101 и т.д., и мгновенно получил результат 5050.
Используя эту идею, можно легко найти сумму элементов любой арифметической прогрессии. Если выписать под последовательностью a_1\ …\ a_n те же элементы в обратном порядке, то суммы в каждом столбце будут одинаковы и равны a_1\ +\ a_n. В сумме этих n слагаемых каждый элемент исходной последовательности будет учтен дважды, поэтому результат сложения (a_1\ +\ a_n)*n нужно поделить на 2.
sum_{i=1}^n\ a_i\ =\ {(a_1\ +\ a_n)*n}/2
После применения формулы для суммы арифметической прогрессии получаем
{(1\ +\ n)*n}/2\ \ -\ sum_{i=1}^{n-1}\ p_i
Также для решения этой задачи можно применить сортировку расстановкой, работающую за время O(n), или быструю сортировку, работающую за время O(n\ log\ n). Использование сортировки пузырьком, работающей за время O(n^2), приводит к превышению предела времени в тестах, где n велико.
