Задача
Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…
Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.
Входные данные
Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.
Выходные данные
Номер команды, выигравшей соревнования. Если несколько команд имеют одинаковые результаты, то побеждает та, у которой больше номер.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 3 20 10 30 15 20 20 30 30 20 |
3 |
| 2 | 3 3 20 -10 -30 15 25 20 30 -30 20 |
1 |
| 1 | 3 3 0 -10 -30 15 25 20 30 -30 20 |
2 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <cmath> #include <climits> using namespace std; double INF = 1e18; int sgn(long long a){ if(a < 0) return -1; else if(a == 0) return 0; else return 1; } struct logNumber{ long long sign; double value; logNumber(int sign = 1, double value = 0){ this->sign = sign; this->value = value; } void operator *= (long long a){ sign *= sgn(a); if(sign == 0) value = 0; else value += log(abs(a)); } bool operator >(logNumber a){ return (sign > a.sign) or (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value); } bool operator ==(logNumber a){ return sign == a.sign and value == a.value; } }; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n,k; cin>>n>>k; logNumber mult[n]; for(int i =0; i < k; i++){ for(int j=0; j < n; j++){ long long temp; cin>>temp; mult[j] *= temp; } } logNumber maxMult = mult[0]; int maxTeam = 0; for(int i = 0; i < n; i++){ if (mult[i] > maxMult){ maxMult = mult[i]; maxTeam = i; } else if(mult[i]==maxMult){ maxTeam = max(i, maxTeam); } } cout << maxTeam + 1; return 0; } |
Решение задачи
Произведение результатов крыс может быть очень большим числом. Поэтому можно сравнивать их по знаку, если же по знаку они равны, то можно сравнивать не сами числа, а логарифмы от чисел. Создаем структуру, которая реализует эту идею.
Ссылки
Ссылка на e-olymp
Ссылка на ideone