| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 16 | 11 | 8 | 61.538% |
Бухгалтер Валерий разбирается с нестыковками в бухгалтерских отчетах. Ему осталось проверить ровно $n$ документов, $i$-й из которых доступен в корпоративной сети по шестизначному целочисленному идентификатору $a_i$.
Назовем инверсией в $k$-м разряде пару номеров $i$ и $j$ такую, что $i < j,ドル и $k$-я цифра числа $a_i$ строго больше $k$-й цифры числа $a_j$. Тогда сложностью массива шестизначных чисел $\{a_i\}$ назовем суммарное количество инверсий во всех шести разрядах.
Валерий знает, что чем меньше сложность набора идентификаторов, тем меньше времени он потратит на вбивание их в адресную строку. Поскольку множество документов фиксировано, а радикально менять порядок проверки опасно (можно случайно пропустить некоторые документы), единственный доступный Валерию способ изменить исходный порядок проверки --- сдвинуть его по циклу на несколько позиций. Напомним, что циклическим сдвигом массива $a_1, a_2, \ldots, a_n$ на $t$ позиций влево называется массив $a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$.
Помогите Валерию выбрать циклический сдвиг исходного массива идентификаторов с минимальной сложностью.
В первой строке ввода дано целое число $n$ --- количество документов, которые требуется проверить (1ドル \leqslant n \leqslant 100,000円$).
В $i$-й из следующих $n$ строк даны шесть цифр --- идентификатор $a_i$. Гарантируется, что все $a_i$ различны. Идентификаторы могут начинаться с нуля.
Выведите единственное целое число --- минимальную из сложностей циклических сдвигов массива идентификаторов документов.
3 277659 177013 314836
4
3 250401 185217 296632
3
В первом примере выгодно сделать сдвиг на одну позицию влево, тогда число 177013ドル$ окажется на первом месте. В таком случае в первых четырех разрядах будет по одной инверсии, а в последних двух --- ноль.
Во втором примере порядок чисел уже оптимален с тремя инверсиями: по одной в первом, четвертом и шестом разрядах.