Помогите решить задания. ОЛИМПИАДА ИДЕТ!!!

[maximus007]

Народ, осталось два часа, залазьте в эту тему те, кто может и желает помочь решить олимпиаду. Очень сильно нужно!!!! Вот пока одна задача которую мы не можем решить. Писать можно на паскале, делфи, с, жаве:


Заданы четыре одинаковых по мощности множества целых чисел A, B, C,
D. Элементы этих множеств не превосходят по модулю 109. Различные эле-
менты одного множества могут иметь одинаковые значения. Рассчитайте
количество четверок (a, b, c, d), где a, b, c, d принадлежат соответственно
множествам A, B, C, D, таких, что a + b + c + d = 0.
Входные данные. В первой строке текстового файла SUMZERO.IN запи-
сывается величина M – мощность каждого из множеств (1 ≤ M ≤ 1000).
Каждая из последующих M строк содержит четыре числа – очередные эле-
менты множеств A, B, C, D.
Выходные данные помещаются в текстовый файл SUMZERO.OUT. Един-
ственная строка этого файла должна содержать искомое количество четве-
рок.
Пример входных данных Пример выходных данных
7
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
-45 201 342 -629
6
Пояснение. Сумма, равная нулю, достигается на следующих четверках (при-
ведены их позиции в соответствующих множествах):
(1; 2; 1; 2), (7; 2; 1; 2), (5; 4; 5; 4),

[Paradoksov]

Delphi консольное приложение:

program Main;
{$APPTYPE CONSOLE}
uses
Windows,SysUtils;

type
PMas = ^TMas;
TMas = array [0..0] of integer;

var
F:TextFile;
N:integer; //Мощность множества

function GetSet:PMas;
var
P_var:PMas;
begin
GetMem(P_var,sizeOF(integer)*N);
Result:=P_var;
end;

function Condition(a,b,c,d:integer):bool;
begin
if (a+b+c+d)=0 then Result:=true else Result:=false;
end;

var
A,B,C,D:PMas;
i,j,k,t:integer;
count :integer;

begin
AssignFile(F,'SUMZERO.IN'); //ParamStr(1)
Reset(F);
Readln(F,N); //Сcчитать мощьность

//===Выделили память под множества=======
A:=GetSet;
B:=GetSet;
C:=GetSet;
D:=GetSet;
//=======================================

//===Ссчитали данные из файла============
for i:=0 to N-1 do
begin
Readln(F,A^[i],B^[i],C^[i],D^[i]);
end;
//=======================================

CloseFile(F);


//===Непостредственно работа программы===
count:=0;
for i:=0 to N-1 do
for j:=0 to N-1 do
for k:=0 to N-1 do
for t:=0 to N-1 do
begin
if Condition(A^[i],B^[j],C^[k],D^[t])
then inc(count);
end;
//=======================================


//===Запись в файл=======================
AssignFile(F,'SUMZERO.OUT');
Rewrite(F);

Writeln(F,count);

CloseFile(F);
//=======================================

//===Освободить память====================
FreeMem(D);
FreeMem(C);
FreeMem(B);
FreeMem(A);
//=======================================

end.

Добавлено через 1 минуту
Может я чего не догнал, но по представленным данныи ответ 6

Добавлено через 7 минут
Не все правильно, совпадает с вашими тремя ответами.

[maximus007]

Блин, парень, большое тебе человеческое спасибо. Очень помогло. Твоя прога прошла 18 тестов из 20. Потом тайм-аут превысила, видимо на больших числах залагала. Но это все равно. На олимпиадах редко вааще когда кто решает абсолютно все задачи, да и еще правильно

[novaFrost]

Где такая олимпиада проходит, что для решение "тупо перебор" оказывается верным ?

[Paradoksov]

Предложи красивое решение. Очень интересно.

Я ни когда не участвовал в олимпиадах, поэтому не знал, что нужно, просто хотел ссылку на TMS компонент для Delphi, а для этого нужен был хотя бы одно сообщение. И чтоб не не флудить.

[airyashov]

Цитата: Сообщение от maximus007 Блин, парень, большое тебе человеческое спасибо. Очень помогло. Твоя прога прошла 18 тестов из 20. Потом тайм-аут превысила, видимо на больших числах залагала. Но это все равно. На олимпиадах редко вааще когда кто решает абсолютно все задачи, да и еще правильно

Еще бы не привысило суммировать каждый раз, промежуточные суммы хранить надо, а сравненение не с 0 а с элементом D множества с обратным знаком
A+B+C=-D

[Paradoksov]

Цитата: Сообщение от airyashov Еще бы не привысило суммировать каждый раз, промежуточные суммы хранить надо, а сравненение не с 0 а с элементом D множества с обратным знаком A+B+C=-D

Это-то все конечно очень хорошо, еще циклы развернуть, само собой убрать вызов процедуры Condition, только это всё не очень интересно. Куда интересней избавиться от четырех вложенных циклов. Вот это задача. А то, что ты предлагаешь скучно, совсем не интересно и все равно наверняка тайм-аут превысит.

Добавлено через 21 минуту
Кстати, я думаю, что

A+B+C=-D медленнее, чем A+B+С+D=0

Для A+B+C=-D, это три команды сложения add (или одна команда Lea, но при условии, что все три оператора в регистрах), потом команда neg (что бы получить -D), потом команда сравнения CMP, и переход, ну например, JE (или JNE)

Для A+B+С+D=0, это три команды сложения add (или одна команда Lea, но при условии, что все три оператора в регистрах), еще одна команда add и переход по флагу zf (команда JZ или JNZ)

Да во всех случаях комманда add должна имеет, по крайней мере, в качестве одного из операндов регистр, так было бы логично, если нет, то твой вариант будет быстрее.

Ну, конечно, в общем случае компилятор может все изгадить.

[novaFrost]

Цитата: Сообщение от Paradoksov Предложи красивое решение. Очень интересно. Я ни когда не участвовал в олимпиадах, поэтому не знал, что нужно, просто хотел ссылку на TMS компонент для Delphi, а для этого нужен был хотя бы одно сообщение. И чтоб не не флудить.

Да я тоже 3 поста набирал.

На олимпиадах обычно действует правило: если решение очевидно - оно завалится по времени. А тут вот 18 из 20

[maximus007]

Цитата: Сообщение от novaFrost Где такая олимпиада проходит, что для решение "тупо перебор" оказывается верным ?

Обыкновеннвм перебором прога стала бы на тесте 2-3, какие некоторые другие наши. Дык что нех