Все мы знаем, что такое сортировка последовательности. для тех, кто подзабыл, напомним: сортировкой последовательности называется такая перестановка ее элементов, когда каждый следующий элемент больше либо равен предыдущему. именно эти знания понадобились гарри поттеру, когда он повстречал сфинкса в лабиринте во время последнего испытания кубка трех волшебников. сфинкс дал гарри такую последовательность: 5, 3, 8, 2, 1, 9, 6, 7, 4 и попросил отсортировать. за один ход гарри может поменять два элемента местами. но сфинкс добавил еще одно условие: если гарри меняет местами числа x и y, то это займет ровно abs(x - y) минут. напомним, что такое abs(a). если a > = 0, то abs(a) = a. иначе abs(a) = -a. гарри сделать сортировку как можно быстрее. в ответе напишите одно число - минимальное число минут, требуемое чтобы отсортировать последовательность (последовательность в итоге должна выглядеть так - 1, 2, 3, 4, 5, 6, 7, 8, 9). и объясните почему оно минимальное.
Имеем конечную арифметическую прогрессию с первым членом -111, разностью арифметической прогрессии 1 (разница между двумя последовательными целыми числами) и суммой 339, нужно найти последний член данной прогрессии
- не подходит, количество членов прогрессии не может быть отрицательным
ответ: 114
второй на смекалку)
(так как слагаемые последовательные целые числа, и меньшее из них отрицательное, а сумма положительна, то последнее из них тоже положительное, иначе они б в сумме дали отрицательное число как сумму отрицательных числе, а не положительное)
далее -111+(-110)+.+0+1+2+...+110+111+112+...+х=
(-111+111)+(-110+110)+(-99+99)+(-1+1)+0+112+113+114+.. + х=
0+0+0+....+0+0+112+113+114+..+х
=112+113+..+х
т.е каждому отрицательному найдется в "противовес" положительное, которое в сумме вместе с ним даст 0,
и фактически наша сумма равна 112+113+...+х (*)
так как наименьшее из слагаемых (*) трицифровое ,и наша сумма трицифровое число, то мы последовательно сравнивая суммы
, найдем его очень быстро
112=112
112+113=225 - меньше
112+113+114=339 -- совпало
значит искомое число х равно 114
ответ: 114