Код Крушера#6963
Уеслі Крушер працює асистентом і веде курс "Вступ до алгоритмів". Під час першого заняття студентів попросили придумати власні алгоритми сортування. Монті запропонував наступний код:
Натхненний Карлос представив наступний код:
Уеслі хоче визначити, чий алгоритм є кращим.
Для заданого вхідного масиву, що містить до значень, обчисліть і виведіть очікувану кількість ітерацій для кожного алгоритму. Тобто, скільки ітерацій у середньому має виконати кожен алгоритм для даного вводу?
Перша строка містить кількість тестів (2 \le t \le 100). Кожен тест задається в окремому рядку. Першим у рядку йде кількість елементів у масиві (2 \le n \le 8). Далі у рядку задані цілих чисел. Числа знаходяться в діапазоні від до включно. Елементи масиву не обов'язково різні.
Для кожного тесту виведіть очікувану кількість ітерацій для алгоритму Монті та для алгоритму Карлоса, як показано у прикладі виходу. Між словами має бути рівно один пробіл, і не повинно бути пробілів на початку або в кінці кожного рядка. Має бути рівно шість цифр після десяткової крапки. Округлення повинно бути до найближчого значення, яке можна представити.
Приклад 1