Олимпиадный тренинг

Задача . Сравни со стабильной


Задача

Темы:
Стабильная сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка. Нестабильная сортировка - сортировка, которая не гарантирует относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Приведем пример:
Key Value
3 Blue
2 Green
1 Red
2 Yellow
Исходный порядок объектов
Key Value
1 Red
2 Yellow
2 Green
3 Blue
Объекты отсортированы по ключу Key по возрастанию нестабильной сортировкой. Относительный порядок элементов с ключом 2 изменился.
 
Key Value
1 Red
2 Green
2 Yellow
3 Blue
Объекты отсортированы по ключу Key по возрастанию стабильной сортировкой. Относительный порядок элементов с ключом 2 остался прежним.

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

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

Сколько строк не совпало бы, если бы таблицу отсортировали по тем же критериям (сначала по цвету (в алфавитном порядке, по возрастанию), а затем по числу карманов (по убыванию)), но стабильной сортировкой?
В ответ напишите одно число – количество строк таких, что их содержимое различно в приведенном результате нестабильной сортировки и результате стабильной сортировки этой же таблицы.
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя