Іноді трапляється так, що умова задачі сформульована неточно. Буває, що в ній багато зайвих деталей, які відволікають. А іноді автори навмисно заплутують умову. Пропоную розглянути задачу «Сортуюча машина", в умові якої є приклад-пояснення. Проте алгоритм, описаний у прикладі, зовсім неоптимальний. Якщо зробити по-своєму, задача виявляється нескладною.
Умова:
Сортуюча машина
(https://www.eolymp.com/uk/problems/1144)
Є машина для сортування набору різних чисел. Вона має лише одну команду MOVE з одним аргументом. Ця команда переміщує число, вказане в аргументі, в кінець послідовності. Наприклад, щоб відсортувати масив чисел 19,7,8,25 у зростаючому порядку, потрібно виконати дві команди:
- MOVE 19, отримаємо 7,8,25,19.
- MOVE 25, отримаємо 7,8,19,25.
Для заданого набору чисел необхідно знайти мінімальну кількість команд MOVE, після виконання яких його елементи будуть упорядковані у зростаючому порядку.
Вхідні дані
Перший рядок містить кількість чисел n (n≤50). Другий рядок містить n цілих чисел у діапазоні від −1000 до 1000.
Вихідні дані
Виведіть мінімальну кількість команд MOVE, після виконання яких усі числа будуть упорядковані у зростаючому порядку.
Давайте розберемо приклад, представлений в умові.
У нас є послідовність: 19,7,8,25. І нам потрібно відсортувати її за зростанням.
Як це пропонується в умові ми робити не будемо. Робити це за алгоритмом, запропонованим в умові, складно. Спочатку нам потрібно перемістити число 19, але воно не є ані найбільшим, ані найменшим, чому варто починати саме з нього, з усім тим потрібно возитися. Пропоную інший підхід — метод стіни. Давайте після списку намалюємо червону стіну:
19,7,8,25|
Наступним кроком ми проаналізуємо список ліворуч від стіни. Може він вже відсортований. Тоді жодних переміщень робити не потрібно, можна виводити нуль і йти спати. Якщо список не сортований, то виконуємо таку дію:
Знаходимо найбільше число, перекидуємо його за стіну і загинаємо палець кількості виконаних команд MOVE. Що у нас вийде в нашому прикладі?
19,7,8|25
Ми зробили одне переміщення і у нас тепер один загнутий палець.
Знову аналізуємо список ліворуч від стіни, він не сортований (19,7,8). Знову відшукуємо максимальний елемент, перекидуємо його за стіну і загинаємо ще один палець:
7,8|19, 25
Продовжуємо. Список ліворуч від стіни відсортований? Так. Чудово. Виводим кількість загнутих пальців і завершуємо роботу програми.
Уважний читач помітить, що числа справа від стіни при такому алгоритмі завжди будуть відсортовані. Тому ми можемо їх не переносити за стіну, а видаляти з несортованого списка, загинаючи палець.
Вхідні дані:
19,7,8,25
Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо палець. Що залишилось:
19,7,8
Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо ще один палець. Що залишилось:
7,8
Не відсортований список? Відсортований. Виводимо кількість загнутих пальців і завершуємо роботу програми.
Погодьтесь, цей спосіб значно простіший, ніж наведений в умові.
Який з цього всього можна зробити висновок? Якщо ви досюди дочитали, то ви розумні. Сформулюйте самі )
Хто зрозумів моє пояснення – можете написати код і здати задачу. У кого не виходить, натисність «детальніше» - побачите один з варіантів коду.
Успіхів!
input()
num = [int(x) for x in input().split()]
count = 0
while num != sorted(num):
num.remove(max(num))
count += 1
print(count)