Начало
Соревнования
Разбор задачи A. Потерянная страница
Тема: вывод формулы или сортировкаСложность: простая
Ответ можно найти по формуле
`sum_{i=1}^n\ i\ -\ sum_{i=1}^{n-1}\ p_i`,
где `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` велико.
