Готовлюсь к олимпиаде ACM и попал вот на такую задачку
acmicpc-live-archive.uva.es/nuevoportal/data/probl...
В двух словах: в прямоугольной таблице n*m (1<=n<=1000, 1<=m<=20) чисел нам нужно найти столбец с максимальным произведением его елементов. Вроде бы простая задача, но в каждой клетке находится 32 битное целое число, их максимум 1000, получаем что максимальное произведение в столбце — 2^31000 что очень много и вынуждает использовать так называемую «длинную арифметику». Но в рейтинге у людей время выполнения 0,018, что для длинной арифметики мало, а значит есть более еффективный метод чем просто умножить и сравнить, да я и сам в это верю.
Вот и вопрос: есть ли еффективный способ сравнить 2 произведения, в каждом до 1000 множителей, каждый множитель по модулю максимум 2^31? Нам нужно сказать какое из них больше, само значение этих произведений нам не нужно.
Спасибо за внимание.
Update. Сайт лежит, вот условие задачи:
Consider the table of 32-bit signed integers with n rows and m columns. The columns are numbered from 1 to m beginning from the left side of the table. Let Ai (1im) is the product of all numbers in the i-th column. Find the maximum of these products and print the column number where this maximum product is achieved. If there are many such columns, print the largest number of the column.
Input
Consists of multiple tests. Each test begins with a line with two integers m and n (1<=m<=20, 1<=n<=1000). Each of the next n lines contains m 32-bit signed integers.
Output
For each test case print on a separate line the column number with the maximum product. If there are several of them — print the largest number of such column.
Sample Input
3 3
20 10 30
15 20 20
30 30 20
3 2
2 -2 2
2 -2 2
Sample Output
3
3
Update 2acm.ro/prob/ACMproblems2010.zip
Задача A
Last Update
Задача сделана! Спасибо хабрачеловеку ! Он напомнил о этом методе с логарифмами, который я почему то сам раньше вычеркнул потому что не получилось + из-за погрешности и т.д. Но видимо задача расчитана именно на такой метод, по этому
Accepted 0.018!!! Наконец то я успокоюсь, меня эта задача мучала)
Исходник:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
struct col {
long double lg;
int sign;
col() {
lg = 1;
sign = 1;
}
};
bool solve(int test) {
col cols[20];
int m,n;
if( scanf("%d %d",&m,&n) != 2) return false;
long long x;
for(int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
scanf("%lld",&x);
if(cols[j].sign == 0) {continue;}
if(x==0) {
cols[j].sign = 0;
continue;
} else if(x<0) {
x=-x;
cols[j].sign *= -1;
}
cols[j].lg += log((long double)x);
}
}
int max = 0;
for(int i=1;i<m;i++) {
if(cols[i].lg*cols[i].sign >= cols[max].lg*cols[max].sign) {
max = i;
}
}
max++;
printf("%d\n",max);
return true;
}
int main() {
int c=1;
while(solve(c++)) {};
}
Простой
Средний
