14. Рестораны

Регулярно пользователи Яндекс Карт выбирают подходящий для них ресторан по множеству критериев.

Для упрощения будут рассмотрены два фактора, влияющие на их выбор: расстояние до пользователя и рейтинг организации. Имеется несколько тысяч попарных оценок от реальных пользователей, в каждой из которых одна пара (расстояние, рейтинг) сравнивается с другой.

Необходимо построить модель, монотонно зависящую от двух этих факторов, которая согласуется с наибольшей долей оценок.

Обучающий датасет restaurants_train.txt находится в архиве, доступном по адресу.

Каждая его строка содержит 5 чисел, разделённых табуляцией: $winner$, $r_1$, $r_2$, $d_1$, $d_2$. При этом $winner$ равен $0$, если победил первый ресторан, $1$, если второй и $0.5$, если случилась ничья. Пары $r_i, d_i$ соответствуют рейтингам и расстояниям для первого и второго ресторанов. Рейтинги $r_i$ равны либо $-1$, что означает, что рейтинг отсутствует, либо принимают действительные значения от $0$ до $10$.

Расстояния $d_i$ равны $1$, если настоящее расстояние не меньше $500$ километров и отношению $\frac{distance\_in\_kilometers}{500}$ в противном случае.

Во время тестирования на вход вашей программе будет дан файл restaurants.in, в котором в первой строке указано число $n \le 20000$ — количество ресторанов, для которых вам нужно указать, насколько они хороши. В следующих $n$ строках задано по два числа, разделённых табом — в $i$-ой строке $r_i$ и $d_i$.

Необходимо вывести $n$ строк, в каждой из которых содержится по одному действительному числу — в $i$-ой строке число $score_i$, означающее насколько хорош соответствующий ресторан.

Решение считается корректным, если не существует двух ресторанов ($r_i$, $d_i$), ($r_j$, $d_j$), таких, что рейтинги $r_i$ и $r_j$ определены, $r_i \ge r_j$, $d_i \le d_j$ и при этом первый ресторан оценён хуже, чем второй ($score_i \lt score_j$). Если решение некорректно, то оно получает $0$ баллов.

Для корректного решения будет подсчитана его согласованность с $N$ парами вида ($winner_k$, $looser_k$), про которые известно, что пользователь оценил ресторан $winner_k$ выше, чем $looser_k$. Чем больше разница между победителем и проигравшим, тем выше итоговый балл. А именно, будет подсчитано

Решение будет принято, если $m \le 0.65$.