Question

В некоторой олимпиаде участвовало 360 человек. Все работы пронумеровали натуральными числами от 1 до 360, номер каждой работы записали на титульном листе. После проверки оказалось, что порядок работ в стопке (снизу вверх) имеет очень необычный вид: 241, 242, 243, …, 359, 360, 121, 122, 123, …, 239, 240, 1, 2, 3, …, 119, 120. Внутри каждой сотни работы упорядочены по возрастанию номеров, но вот сотни переставлены местами. Антону (одному из студентов, помогавшему на олимпиаде) поручили упорядочить работы так, чтобы они лежали (снизу вверх) в порядке возрастания номеров: 1, 2, 3, …, 360. Ему совершенно не хочется перекладывать все 360 работ, поэтому он решил, что будет делать только такие действия: возьмет непрерывный кусок из нескольких работ, перевернет, и вставит как целое на то же место. Например, если бы в стопке лежало 5 работ в таком порядке: 1, 4, 3, 2, 5, то взяв и перевернув три средние работы, Антон получит стопку 1, 2, 3, 4, 5. За какое наименьшее количество таких операций (одна операция это переворачивание куска работ) Антон сможет сложить все работы в нужном порядке?

Answer 1

Ответ:

4

Объяснение:

Наиболее эффективное решение обеспечивается разбиением массива работ на 3 равные части, переворота каждой из них и затем переворота всего массива.

Answer 2

Для решения этой задачи можно использовать следующий алгоритм:

1. Найдите первую работу с номером 1. Она должна находиться где-то в стопке.

2. Если работа с номером 1 не находится внизу стопки, выполните операцию переворота, чтобы она оказалась внизу.

3. После выполнения первых двух шагов у вас будет правильно расположенная работа с номером 1 внизу стопки. Теперь повторите следующий шаг для работы с номером 2.

4. Найдите работу с номером 2 в оставшейся части стопки (сверху от работы с номером 1) и выполните операцию переворота, чтобы она оказалась ниже работы с номером 1.

5. Повторяйте шаги 3 и 4 для оставшихся работ с номерами 3, 4, ..., 360. Каждый раз находите нужную работу и переворачивайте её, чтобы она оказалась ниже предыдущей работы.

После выполнения всех этих шагов работы должны быть упорядочены по возрастанию номеров.

Таким образом, Антону потребуется выполнить операцию переворота для каждой работы, кроме работы с номером 1, поэтому наименьшее количество операций будет равно 360 - 1 = 359.