Сложность: 46%
Бухгалтер Валерий разбирается с нестыковками в бухгалтерских отчетах. Ему осталось проверить ровно документов, -й из которых доступен в корпоративной сети по шестизначному целочисленному идентификатору .
Назовем инверсией в -м разряде пару номеров и такую, что , и -я цифра числа строго больше -й цифры числа . Тогда сложностью массива шестизначных чисел назовем суммарное количество инверсий во всех шести разрядах.
Валерий знает, что чем меньше сложность набора идентификаторов, тем меньше времени он потратит на вбивание их в адресную строку. Поскольку множество документов фиксировано, а радикально менять порядок проверки опасно (можно случайно пропустить некоторые документы), единственный доступный Валерию способ изменить исходный порядок проверки – сдвинуть его по циклу на несколько позиций. Напомним, что циклическим сдвигом массива на позиций влево называется массив .
Помогите Валерию выбрать циклический сдвиг исходного массива идентификаторов с минимальной сложностью.
Входные данные
В первой строке ввода дано целое число – количество документов, которые требуется проверить ().
В -й из следующих строк даны шесть цифр – идентификатор . Гарантируется, что все различны. Идентификаторы могут начинаться с нуля.
Выходные данные
Выведите единственное целое число – минимальную из сложностей циклических сдвигов массива идентификаторов документов.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 17 | - | |
2 | 19 | 1 | |
3 | 26 | 1, 2 | |
4 | 38 | 1, 2, 3 | Нет дополнительных ограничений |
STDIN | STDOUT |
3 277659 177013 314836 | 4 |
3 250401 185217 296632 | 3 |
Примечание
В первом примере выгодно сделать сдвиг на одну позицию влево, тогда число окажется на первом месте. В таком случае в первых четырех разрядах будет по одной инверсии, а в последних двух – ноль.
Во втором примере порядок чисел уже оптимален с тремя инверсиями: по одной в первом, четвертом и шестом разрядах.