Проклятие победителя (НТО 21/22 :: ИЭС)
Легенда
Подзадача 1. На аукционе с N участниками выставляется M лотов (положим N=20,M=100). Все участники являются покупателями. У каждого лота есть истинная ценность, а у каждого участника — представления о ней, находящиеся в коридоре ±10% от истинной. Каждый лот выставляется на аукцион первой цены. Какой участник получит наибольшую выгоду от участия в аукционе?
Входной формат: N+1 строка, в каждой из которых приведено M вещественных чисел через пробел. В первой строке приведены истинные ценности соответствующих лотов, в следующих строках – оценки участников (вторая строка – участник под номером 0, третья – 1 и т.д.). Пример формата для 5 лотов и 4 участников:
1 2 3 4 5
1.1 1.9 3.15 3.8 4.5
1.2 1.8 3.18 3.3 4.6
1.3 1.7 3.13 3.2 4.3
1.4 1.6 3.11 3.5 4.2
Выходной формат: единственное целое число, номер участника с наибольшей выгодой (нумерация идёт с 0). Решение принимается, если выгода выбранного вами участника больше выбранного авторским решением, либо отличается меньше, чем на 10^(-6).
Подзадача 2.
Напишите программу, решающую аналогичную задачу для произвольных N (до 30) и М (до 500). Входной и выходной форматы аналогичны прошлой подзадаче, но теперь на входе первой строкой через пробел идут N и M, дальше данные аналогичны. Например,
4 5
1 2 3 4 5
1.1 1.9 3.15 3.8 4.5
1.2 1.8 3.18 3.3 4.6
1.3 1.7 3.13 3.2 4.3
1.4 1.6 3.11 3.5 4.2
Time Limit: 1 секунда
Memory Limit: 256 MB