eolymp
bolt
Try our new interface for solving problems
Məsələlər

Головоломка с велосипедом

Головоломка с велосипедом

\includegraphics{https://static.e-olymp.com/content/02/0201d1f57adabf81998a6719775c4f9555868eab.jpg} Пьер и Гунар нашли в сети превосходный пазл с картинкой велосипеда. И они решили узнать кто из них лучший решатель головоломки. Задача игры - собрать картинку велосипеда. В начале каждой игры велосипед разбит на \textbf{W} умноженное на \textbf{H }одинаковых прямоугольников произвольным образом. Неоднократно игрок выбирает два произвольных прямоугольника и меняет их местами. Процесс обмена прямоугольников продолжается до тех пор, пока вся картинка не будет собрана. Счет прохождения игры равен количеству указанных обменов. После того как Гунар сыграл в игру, он отправляет свой счет (вместе с \textbf{W} и \textbf{H}) Пьеру, и предлагает ему улучшить его счет. Пьер вскоре понимает, что если ему не повезет с перестановками прямоугольников, то он не сможет улучшить счет Гунара. Пьер быстренько написал программу, вычисляющую вероятность того что он сможет улучшить счет Гунара (считаем, что расположение всех картинок равновероятно) при условии оптимальной игры. Но он не уверен в ее корректности и поэтому просит написать Вас такую же программу. \InputFile Первая строка содержит количество тестов \textbf{T} (\textbf{0} < \textbf{T} ≤ \textbf{150}). Первая строка каждого теста содержит три числа \textbf{W }(\textbf{0} < \textbf{W} ≤ \textbf{5}), \textbf{H} (\textbf{0} < \textbf{H} ≤ \textbf{4}) и \textbf{S} (\textbf{0} ≤ \textbf{S} ≤ \textbf{W}·\textbf{H}), где\textbf{ S} - последний счет Гунара. При сравнении двух счетов лучшим считается меньший. \OutputFile Для каждого теста в отдельной строке вывести вероятность того что Пьер сможет улучшить счет Гунара. Вероятность следует выводить в формате несократимой дроби, числитель которой отделяется от знаменателя символом \textbf{/}. Если результат является целым, то выводить следует только числитель.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
3
1 1 1
1 2 1
3 1 2
Çıxış verilənləri #1
1
1/2
2/3