Я пишу вопрос на онлайн-судье для практики. Вопрос касается оптимизации Bogosort и подразумевает не перетасовку всего диапазона номеров каждый раз. Если после последнего перемешивания несколько первых элементов окажутся в нужных местах, мы исправим их и больше не будем перемешивать эти элементы. Мы сделаем то же самое для последних элементов, если они находятся в нужных местах. Например, если начальная последовательность (3, 5, 1, 6, 4, 2) и после одной случайной последовательности Джонни получает (1, 2, 5, 4, 3, 6), он исправит 1, 2 и 6 и продолжит с сортировкой (5, 4, 3) по тому же алгоритму.
Для каждого тестового примера выведите ожидаемое количество перемешиваний, необходимое для улучшенного алгоритма для сортировки последовательности первых n натуральных чисел в виде неприводимых дробей.
Пример ввода / вывода говорит, что для n = 6 ответ 1826 / 189.
Я не совсем понимаю, как был получен ответ.