Алгоритмы сортировки

314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Сортировка по возрастанию#92143

Пользователь вводит несколько целых чисел в одной строке через пробел. Выведите их в порядке возрастания.

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

Одна строка — те же числа, отсортированные по возрастанию, через пробел.

Использование сортировки
—Войти и решать
Словарь длин слов#92138

Пользователь вводит несколько слов через пробел. Постройте словарь, где ключ — слово, значение — его длина. Выведите пары в формате слово: длина, отсортированные по длине в порядке возрастания. Если длины одинаковые, сортируйте по алфавиту.

Формат входных данных

Одна строка — слова через пробел (от 2 до 15 слов). Все слова различны.

Формат выходных данных

Строки в формате слово: длина, отсортированные по длине (по возрастанию), при равенстве — по алфавиту.

Использование сортировкиСловариСтроки
✓ 7✗ 15500лёгкаяВойти и решать
Сортировка словаря по значениям#92137

Пользователь вводит количество учеников, а затем для каждого — имя и оценку. Сохраните данные в словарь. Выведите пары в формате Имя — оценка, отсортированные по оценке в порядке убывания. Если оценки одинаковые, сохраните порядок ввода.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 10\)).

Следующие \(N\) строк — имя и оценка (целое число) через пробел. Имена уникальны.

Формат выходных данных

\(N\) строк в формате Имя — оценка, отсортированные по убыванию оценки.

Использование сортировки
—Войти и решать
Сортировка словаря по ключам#92136

Пользователь вводит количество учеников, а затем для каждого — имя и оценку. Сохраните данные в словарь. Выведите пары в формате Имя — оценка, отсортированные по имени в алфавитном порядке.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 10\)).

Следующие \(N\) строк — имя и оценка через пробел. Имена уникальны, состоят из русских букв, начинаются с заглавной.

Формат выходных данных

\(N\) строк в формате Имя — оценка, отсортированные по имени (алфавитный порядок).

Алгоритмы обработкиИспользование сортировкиСловари
—Войти и решать
Миссия Пиксель. 9. Отчёт командира#91327
🎯
Шаг 9: Отчёт командира
Средне
Финальная задача перед решающей атакой! Нужно составить рейтинг серверных зон по суммарному урону. Данные разбросаны — одна зона может встречаться несколько раз. Сгруппируй и отсортируй!
Условие задачи
 

Дано N строк. В каждой — название зоны и число (урон), через пробел. Одна зона может встречаться несколько раз.

Для каждой зоны посчитай суммарный урон, затем выведи зоны в порядке убывания суммарного урона. При равном уроне — в алфавитном порядке.

Входные данные

В первой строке — число N. В каждой из следующих N строк — название зоны и целое число через пробел.

Выходные данные

На каждой строке: название и суммарный урон через пробел (по убыванию урона).

Использование сортировки
✓ 1✗ 01 000средняяВойти и решать
Миссия Пиксель. 6. Рейтинг Героев#91323
🏆
Шаг 6: Рейтинг героев
Средне
Вирус перемешал рейтинги героев. Чтобы восстановить турнирную таблицу, нужно отсортировать баллы и показать лидеров. Применяй навыки сортировки!
Условие задачи
 

Дана строка из N целых чисел — рейтинги героев. Выведи три строки:

  • все числа, отсортированные по возрастанию, через пробел;
  • три наибольших числа через пробел (от меньшего к большему);
  • среднее арифметическое, округлённое вниз (целочисленное деление).
Входные данные

Одна строка: N целых чисел через пробел (3 ≤ N ≤ 100, значения от 0 до 10000).

Выходные данные

Три строки.

Алгоритмы обработкиИспользование сортировки
✓ 6✗ 6600лёгкаяВойти и решать
Глючные робоанты#91274

Недавно директору Ресторана Отеля пришла в голову следующая мысль: <<Все какое-то обычное. Надо что-то модернизировать!>> Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.

Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО <<В Гараже у Петровича>>. И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили \(n\) столов и приготовили \(n\) блюд. Все блюда попарно различны и имеют номера от \(1\) до \(n\). Изначально, блюда по мере готовности как-то расставили по \(n\) столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, \(i\)-е блюдо должно оказаться на \(i\)-м столе.

Рядом с каждым столом изначально стоит робоант. Далее каждый робоант независимо от других может выполнять следующую операцию неограниченное число раз: пусть сейчас робоант стоит у \(i\)-го стола. Тогда, если у него с собой нет ни одного блюда, он может взять (а может и не брать) блюдо в данный момент, находящееся на \(i\)-м столе и перейти к любому \(j\)-му столу при условии, что \(i\) и \(j\) имеют общий делитель больший \(1\). Далее, если у робоанта есть с собой блюдо, он может положить его на \(j\)-й стол (а может и не класть).

Теперь директор просит помочь ему у написать программу, которая определит, смогут ли его робоанты расставить все блюда по местам.

Формат входных данных
В первой строке записано одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество столиков в Ресторане.

Во-второй строке записано \(n\) различных целых чисел \(a_1, a_2, \dots a_n\) (\(1 \le a_i \le n\)) — номера блюд изначально расставленных на соответственно \(1\)-й, \(2\)-й, …\(n\)-й столиках.

Формат выходных данных
Выведите <<YES>>, если робоанты смогут расставить все блюда по местам, и <<NO>> в противном случае случае.

 

Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:

  1. Берёт со \(2\)-го стола \(8\)-е блюдо, перемещается к \(8\)-му столу, кладет блюдо.

  2. Берёт с \(8\)-го стола \(2\)-е блюдо, перемещается ко \(2\)-му столу, кладет блюдо.

  3. Перемещается к \(4\)-му столу.

  4. Берёт с \(4\)-го стола \(6\)-е блюдо, перемещается к \(6\)-му столу, кладет блюдо.

  5. Берёт с \(6\)-го стола \(4\)-е блюдо, перемещается к \(4\)-му столу, кладет блюдо.

Можно доказать, что во втором примере невозможно расставить все блюда по местам.

Алгоритмы сортировкиматематикатеория чисел
✓ 1✗ 01 200средняяВойти и решать
Why Did the Cow Cross the Road III#90425
Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

Соседние коровы ещё имеют возможность войти, но только через одни ворота и с большой очередью, потому что каждой нужно ответить на длинный список вопросов, прежде чем войти.

Для каждой из \(N\) коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

Определите минимально возможное время, за которое все коровы войдут на ферму.

ФОРМАТ ВВОДА (файл cowqueue.in):

Первая строка ввода содержит \(N\), положительное целое число, не более 100. Каждая из последующих \(N\) строк описывает одну корову, задавая время прибытия и время, которое требуется ей для ответов на вопросы. Каждое из этих чисел - положительное целое число не более 1,000,000.

ФОРМАТ ВЫВОДА (файл cowqueue.out):

Определите минимально возможное время, в которое все коровы завершат обработку.

Жадный алгоритмЗадачи на моделированиеИспользование сортировки
—Войти и решать
Load Balancing#90419
Коровы Фермера Джона стоят в различных точках \((x_1, y_1) \ldots (x_n, y_n)\) его поля (\(1 \leq N \leq 100,000\), все \(x_i\) и \(y_i\) - положительные нечётные целые числа, не превышающие \(1,000,000\). ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением \(x=a\) (\(a\) - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением \(y=b\), где \(b\) - чётное целое. Эти две изгороди пересекаются в точке \((a,b)\), и вместе делят поле на четыре региона.

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

ФОРМАТ ВВОДА (файл balancing.in):

Первая строка ввода содержит одно целое число, \(N\). Каждая из следующих \(n\) строк содержит местоположение одной коровы, указанное её координатами \(x\) и \(y\).

ФОРМАТ ВЫВОДА (файл balancing.out):

Выведите минимально возможное значение \(M\), которое может достичь ФД оптимальным расположением изгородей.

Сортировка событий
—Войти и решать
Stampede#90377

Problem 1: Stampede [Brian Dean]

N коров (1 <= N <= 50,000) Фермера Джона стоят вдоль дороги перед
фермой – предстоит забег, чтобы узнать какая корова самая быстрая.

Каждая корова представлена горизонтальным отрезком одиночной длины,
с началом в левой угловой точке в момент времени t=0. Например,
(-3,6) обозначает корову, которая в момент времени 0 представлена отрезком
из (-3,6) в (-2,6). Каждая корова движется вправо (в направлении + по оси x),
на некоторой скорости указанной количеством времени, требуемым для того,
чтобы переместиться на единицу расстояния вправо.

ФД для того, чтобы определить, какие из его коров участвуют в гонке,
расположился в точке (0,0) и смотрит в направлении +y.
ФД видит только ближайшую к себе корову. То есть корова может быть
не видима, если другая корова находится «перед ней» всё время пока
пересекает «линию взгляда» ФД.

Пожалуйста, определите количество коров, которые ФД увидит во время
гонок.

Формат входных данных

Первая строка ввода содержит N. Каждая из последующих N строк
описывает одну корову тремя целыми числами x y r, определяющими
левую точку коровы (x,y) в момент времени t=0 и постоянную скорость
её движения право – r, то есть что эта корова перемещается на 1
единицу расстояния за r единиц времени. X находится в диапазоне -1000..1,
а y находится в диапазоне 1..1,000,000 (и различается для каждой коровы,
чтобы предотвратить коллизии), и значение r находится в диапазоне 1..1,000,000.

Формат выходных данных

Одно целое число, указывающее количество коров, которых ФД
сможет увидеть за время гонки от момента времени 0 и далее.

Примечание
ФД сможет увидеть коров 1 и 2 и не сможет увидеть корову 3.

Сортировка событий
—Войти и решать
Counting Haybales#90366
Фермер Джон разместил свои \(N\) (\(1 \leq N \leq 100,000\)) стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на \(Q\) (\(1 \leq Q \leq 100,000\)) запросов, о том сколько стогов сена находится внутри указанного участка дороги.

ФОРМАТ ВВОДА (файл haybales.in):

Первая строка содержит \(N\) и \(Q\).

Следующая строка содержит \(N\) различных целых чисел, каждое в интервале \(0 \ldots 1,000,000,000\), указывающих местоположения стогов сена.

Каждая из последующих \(Q\) строк содержит два целых числа \(A\) и \(B\) (\(0 \leq A \leq B \leq 1,000,000,000\)) задающих запрос на количество стогов сена между \(A\) и \(B\), включительно.

ФОРМАТ ВЫВОДА (файл haybales.out):

Вы должны вывести \(Q\) строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

Бинарный поиск в массивеИспользование сортировки
—Войти и решать
High Card Wins#90354
Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

Беси может предсказать порядок, в котором будет выкладывать карты Эльза. Определите максимальное количество очков, которое может выиграть Беси.

ФОРМАТ ВВОДА (файл highcard.in):

Первая строка ввода содержит значение N (\(1 \leq N \leq 50,000\)).

Следующие N строк содержат карты, которыми будет играть в каждом из последующих раундов игры. Заметим, что из этой информации легко определить карты, которые на руках у Беси.

ФОРМАТ ВЫВОДА (файл highcard.out):

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритмИспользование сортировки
—Войти и решать
High Card Wins#90349
Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

Беси может предсказать порядок, в котором будет выкладывать карты Эльза. Определите максимальное количество очков, которое может выиграть Беси.

ФОРМАТ ВВОДА (файл highcard.in):

Первая строка ввода содержит значение N (\(1 \leq N \leq 50,000\)).

Следующие N строк содержат карты, которыми будет играть в каждом из последующих раундов игры. Заметим, что из этой информации легко определить карты, которые на руках у Беси.

ФОРМАТ ВЫВОДА (файл highcard.out):

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритмЗадачи на моделированиеИспользование сортировки
—Войти и решать
High Card Low Card (Platinum)#90348
Беси и Эльза играютв простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делится на две части по \(N\) карт для Беси и \(N\) карт для Эльзы. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. Изначально, одно очко за каждый раунд выигрывает игрок, у которого карта больше. Однако однажды за всю игру Беси может переключить правила игры так, что до конца игры выигрывать одно очко за раунд будет игрок, карта которого меньше. Беси может также выбрать не использовать эту опцию, оставляя на всю игру правило "выигрывает бОльшая карта" или она может включить это правило перед первыми раундом, и тогда вся игра ведётся по правилу "выигрывает меньшая карта".

Зная порядок, в котором будет выкладывать свои карты Эльза, помогите Беси определить максимальное количество очков, которое она сможет заработать.

ФОРМАТ ВВОДА (файл cardgame.in):

Первая строка ввода содержит значение N (\(2 \leq N \leq 50,000\)).

Следующие N строк содержат карты которым играет Эльзав том порядке как она их будет выкладывать в последовательных раундах игры. Заметим, что по этой информации легко определить, какие карты на руках у Беси.

ФОРМАТ ВЫВОДА (файл cardgame.out):

Выведите одну строку, содержащую максимальное количество очков, которое может заработать Беси.

Жадный алгоритмИспользование сортировки
—Войти и решать
Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит число \(N\).

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Ответы для всех сортов на отдельных строках.

SCORING:

  • Тесты 4-5: \(N \leq 5000\)
  • Тесты 6-11: \(k\) одинаковое для всех интервалов
  • Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

ОтрезкиПрефиксные суммы(минимумы, ...)Сортировка событий
—Войти и решать
Maximizing Productivity#90248

У Фермера Джона есть \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) ферм, пронумерованных от \(1\) до \(N\). Известно, что ФД закрывает ферму \(i\) в момент времени \(c_i\). Беси просыпается в момент времени \(S\) и хочет максимизировать производительность своего дня посетив как можно больше ферм, прежде чем они закроются. Она планирует посетить ферму \(i\) в момент времени \(t_i + S\). Беси должна прибыть на ферму строго раньше чем ФД закроет её, чтобы действительно посетить эту ферму.

У Беси есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. Для каждого запроса она даёт Вам два целых числа \(S\) и \(V\). Для каждого запроса выведите сможет ли Беси посетить не менее \(V\) ферм, если она проснётся в момент времени \(S\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка состоит из \(N\) и \(Q\).

Вторая строка состоит из \(c_1, c_2, c_3 \dots c_N\) (\(1 \leq c_i \leq 10^6\)).

Третья строка состоит из \(t_1, t_2, t_3 \dots t_N\) (\(1 \leq t_i \leq 10^6\)).

Каждая из последующих \(Q\) строк содержит два целых числа \(V\) (\(1 \leq V \leq N\)) and \(S\) (\(1 \leq S \leq 10^6\)).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого из \(Q\) запросов, выведите YES или NO на новой строке.

Использование сортировки
—Войти и решать
Milk Sum#90233

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка содержит \(N\).

Вторая строка содержит \(a_1\dots a_N\).

Третья строка содержит \(Q\).

Следующие \(Q\) строк содержат по два целых числа \(i\) и \(j\), разделенных пробелом.

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Пожалуйста, выведите значение \(T\) для каждого из запросов \(Q\) в отдельных строках.

Использование сортировкиПрефиксные суммы(минимумы, ...)реализация
—Войти и решать
Minimizing Haybales#90169
У Фермера Джона есть \(N\) (\(1\leq N \leq 10^5\)) стогов из тюков сена. Для каждого \(i\in [1,N]\), \(i\)-ый стог имеет \(h_i\) (\(1\le h_i\le 10^9\)) тюков. Бесси может выполнять следующие операции:

  • Если высоты двух соседних стогов сена различаются не более чем на \(K\) (\(1\le K\le 10^9\)), она может поменять местами два стога

Какую лексикографически минимальную последовательность высот Беси может получить после некоторой последовательности таких операций?

**Примечание: ограничения на время и память для этой задачи 4сек и 512 Мбт, что в 2 раза больше значений по умолчанию.**

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка ввода содержит \(N\) и \(K\). \(i+1\)-ая строка содержит высоту \(i\)-того стога.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(N\) строк, \(i\)-ая строка содержит высоту \(i\)-го стога в решении.

Использование сортировки
—Войти и решать
Cow College#90138
Фермер Джон планирует открыть новый университет для коров!

Имеется \(N\) (\(1 \le N \le 10^5\)) коров, которые потенциально могут посещать университет. Каждая корова готова платить за обучение максимум \(c_i\) (\(1 \le c_i \le 10^6\)). Фермер Джон может установить плату за обучение, которую все коровы должны оплатить. Если эта плата больше, чем корова готова платить, она не платит и не учится в университете. Фермер Джон хочет установить такую оплату, чтобы получить максимальную сумм оплат. Определите эту максимальную сумму и установленную плату за обучение.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\). Вторая строка содержит \(N\) целых чисел \(c_1, c_2, \dots, c_N\), где \(c_i\) - это максимальная плата, которую готова платить корова \(i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите максимальное количество денег, которое может получить ФД и оптимальную оплату за обучение, которую он должен установить. Если имеется несколько вариантов, выберите тот в котором минимальная оплата за обучение.

Заметим, что надо использовать 64-битный целый тип, например "long" в Java, или "long long" в C/C++).

Использование сортировки
—Войти и решать
Sleepy Cow Sorting#90065
Фермер Джон пытается отсортировать свои \(N\) коров (\(1 \leq N \leq 100\)), последовательно пронумерованных \(1 \dots N\).

В настоящий момент коровы выстроились в линию в порядке \(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\). Он хочет переупорядочить коров так, чтобы они стали в порядке \(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.

Фермера Джона слышит только корова, которая стоит перед ним. В этот момент ФД может сказать ей перейти на \(k\) позиций назад (\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит, двигаются вперёд, освобождая место для неё, в которое она и становится.

Например, пусть \(N=4\) и коровы стоят в таком порядке 

 ФД: 4, 3, 2, 1

Единственная корова, которая слышит ФД, это корова \(4\). Если он скажет ей сдвинуться на 2 позиции, порядок станет таким: 

 ФД: 3, 2, 4, 1

Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.

Определите последовательность инструкций (с минимальным их количеством), которые должен дать ФД, чтобы отсортировать всех коров.

ФОРМАТ ВВОДА (файл sleepy.in):

Первая строка содержит \(N\). Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами : \(p_1, p_2, p_3, \dots, p_N\), указывающих стартовый порядок коров.

ФОРМАТ ВЫВОДА (файл sleepy.out):

Первая строка должна содержать одно целое число \(K\), задающее минимальное количество инструкций, которое требуется, чтобы отсортировать всех коров.

Вторая строка должна содержать \(K\) разделённых одиночными пробелами целых чисел \(c_1, c_2, \dots, c_K\), каждое в интервале \(1 \ldots N-1\), задающих последовательность инструкций, которая отсортирует исходную последовательность коров.

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

Жадный алгоритмИспользование сортировкиреализация
—Войти и решать
Поделиться
Класснуть