Задача C. Самый точный прогноз погоды.
Задачу добавил: alef
Успешно сдано решений: 15
Маша Петрова обратила внимание, что разные метеослужбы в интернете дают различные прогнозы погоды. В какие-то периоды ей казалось, что самые точные прогнозы дает служба погоды сайта Хаос-Инь, в какие-то — сайта Drop... «Наверное, они используют разные математические модели, — рассуждала Маша. — Было бы хорошо выяснить, в каких условиях модель какой службы работает лучше...». Впрочем, это довольно сложное дело, и пока она решила попробовать составлять свой прогноз по температуре воздуха на следующий день, основываясь на данных N служб погоды, которые она выбрала. Обозначим через T1, T2, …, TN прогнозы температуры воздуха, которые выдают эти службы, а через R — температуру воздуха, которая в действительности была зафиксирована.
Маша собирается составлять свой прогноз по формуле (k1 * T1 + k2 * T2 + … + kN * TN) / (k1 + k2 + … + kN), где kj — коэффициент доверия Маши к прогнозу службы #j.
В первый день Маша одинаково доверяет всем службам погоды и составляет свой прогноз как среднее арифметическое прогнозов всех N служб: (T1 + T2 + … + TN)/N (k1 = k2 = … = kN = 1). Однако при составлении прогноза на второй и последующие дни она хочет сделать более весомыми прогнозы тех служб, которые были более точными в предшествующие периоды.
Маша собирается действовать следующим образом. Она считает прогноз службы #j достаточно точным, если температура Tj отличалась от R не более чем на величину d. Если прогноз службы #j оказался достаточно точен, то Маша увеличивает коэффициент своего доверия к прогнозу этой службы на единицу (kj + 1). Если же прогноз оказывается точным недостаточно, то Маша уменьшает коэффициент своего доверия, деля его нацело на два.
Входной файл содержит прогнозы N служб на Q дней, а также реальную температуру в каждый из этих Q дней
Ваша задача — определить, сколь точным будет прогноз Маши в день Q. Гарантируется, что в каждый день наблюдений хотя бы один из прогнозов был достаточно точен.
Формат входного файла input.txt
Первая строка — два целых числа N (1 <= N <= 10000)и Q (2 <= Q <= 1000) через пробел: количество погодных служб и количество дней, в течение которых Маша делает свой прогноз
Вторая строка — два целых числа dn и dd через пробел, определяющие точность прогноза d = dn / dd (0 <= dn <= 10^14, 1 <= dd <= 10^14).
В каждой из следующих Q строк содержится N + 1 число (не меньшее 5.00 и не большее 50.00) с ровно двумя знаками после запятой через пробел. Первые N чисел являются прогнозами погодных служб (с соответствующими номерами) на соответствующий день. Последнее число — реальная температура, которая была зафиксирована в этот день.
Гарантируется, что размер входного файла не превышает 4 Мб.
Формат выходного файла output.txt
Первая строка — символ «+» или «–», пробел, затем два целых числа через пробел, числитель и знаменатель дроби, определяющие знак и значение разности между прогнозом Маши и реальной температурой в последний день наблюдений.
Дробь должна быть несократимой. Если разница составляет 0, следует вывести +, 0 и 1.
Пример входного файла — 1
7 5
10 20
36.39 36.32 32.99 31.42 36.55 37.54 30.82 36.45
36.27 35.67 36.68 32.57 34.15 30.17 32.92 32.51
37.93 36.75 32.93 32.27 37.60 35.81 37.19 37.66
33.78 34.75 31.91 34.45 34.19 37.59 35.10 34.51
30.68 35.44 31.69 37.53 34.11 31.61 32.50 31.63
Пример выходного файла — 1
+ 1707 700
Пример входного файла — 2
4 10
8 10
35.49 33.42 35.72 33.26 33.34
36.91 33.37 33.19 32.50 36.99
33.30 33.45 33.19 35.84 33.53
33.89 32.11 32.61 35.30 34.43
32.60 32.29 36.00 32.13 32.21
33.73 35.66 36.67 35.48 35.40
35.90 32.14 33.10 31.98 32.60
34.90 36.72 32.29 36.72 36.64
32.10 33.80 36.79 33.80 33.72
33.15 34.48 32.81 32.60 32.73
Пример выходного файла — 2
+ 197 220