Решение задачи #71 на acmp.ru

[Poma][a]

Добрый вечер.

Я упорно пытаюсь сдать задачку #71 на acmp.ru. А acmp упорно говорит, что у меня ошибка в 1-ом тесте.. Проверив свою писанину на многих тестах (начиная с "примера" и своих тестах, и заканчивая тестами в "Обсуждениях"). Однако любимый acmp продолжает меня мучить.

Поэтому я прошу Вас оказать мне неоценимую услугу - найти мой "косяк".

Я решил не мучиться с комбинаторикой. Я навскидку применил самый обычный лом - рекурсию )). Но я не уверен, пролезет ли рекурсивное решение по времени при больших n. (c) TinMan

type
	SetOfStones = array [1..18] of Integer;
	Differences = array [1..262144] of Integer; // 2^18
	
var
	diff : Differences;
	count : Int64;
	
procedure AddNewStone (const a : SetOfStones; FirstSet, SecondSet :
								 SetOfStones; 
								 n : Integer;
								 const MaxSize : Integer);
function SumOf (const a : SetOfStones; const n : Integer) : Integer;

var
	i, r : Integer;
	
begin
	r := 0;
	
	for i := 1 to n do
		r := r  + a[i];
	
	SumOf := r
end;
								 
								 
begin
	if n > MaxSize then begin
		diff[count] := Abs (SumOf(FirstSet, MaxSize) - SumOf(SecondSet, MaxSize));
		Inc (count);
		Exit
	end;
	
	FirstSet[n] := a[n];
	
	AddNewStone (a, FirstSet, SecondSet, n+1, MaxSize);
	
	FirstSet[n] := 0;
	SecondSet[n] := a[n];
	AddNewStone (a, FirstSet, SecondSet, n+1, MaxSize)
end;

		
var
	n, i, min : Integer;
	a, f, s : SetOfStones;
	
begin
	Assign (input, 'input.txt');
    Reset (input);
    
    Assign (output, 'output.txt');
    Rewrite (output);

	ReadLn (n);
	
	for i := 1 to n do
		Read (a[i]);
	
	count := 1;
	
	for i := 1 to n do begin
		f[i] := 0;
		s[i] := 0
	end;
		
		
	AddNewStone (a, f, s, 1, n);
	
	min := diff[1];
	for i := 2 to count-1 do
		if diff[i] < min then
			min := diff[i];
			
	WriteLn (min)
end.

Заранее спасибо!

[Stilet]

Э-э-эммм..

var a:array[1..5] of integer=(5, 8, 13, 27, 14);
 h1,h2,i:integer;
begin
 h1:=a[1];h2:=a[2];
 for i:=3 to 5 do begin
   if (h1<h2) then h1:=h1+a[i] else h2:=h2+a[i];
 end;
Caption:=IntToStr(h1)+' - '+IntToStr(h2); 
end;

Или 2плю?

[Poma][a]

7
21 1 16 11 5 18 21

Правильный ответ - 1
21+21+5=47 и 18+16+11+1=46 => 47-46=1

Ваш ответ - 5
1+16+11+21=49 и 21+5+18=44 => 49-44=5

[Аватар]

А косяк не в том, что diff слишком много памяти кушает? Зачем он вообще нужен, без него спокойно можно обойтись, каждую полученную сумму сравнивая с min еще в AddNewStone

[Poma][a]

А косяк не в том, что diff слишком много памяти кушает? Зачем он вообще нужен, без него спокойно можно обойтись, каждую полученную сумму сравнивая с min еще в AddNewStone

Ага. Есть такой грешок. Понял это (не про ошибку, а про возможность сравнения без массива) когда уже дописывал и было уж очень лень исправлять..

type
	SetOfStones = array [1..18] of Integer;
	Differences = array [1..262144] of Integer; // 2^18
	
var
	min : Integer;
		
procedure AddNewStone (const a : SetOfStones; FirstSet, SecondSet :
								 SetOfStones; 
								 n : Integer;
								 const MaxSize : Integer);
function SumOf (const a : SetOfStones; const n : Integer) : Integer;

var
	i, r : Integer;
	
begin
	r := 0;
	
	for i := 1 to n do
		r := r  + a[i];
	
	SumOf := r
end;
								 
var
	t : Integer;
	
begin
	if n > MaxSize then begin
		t := Abs (SumOf(FirstSet, MaxSize) - SumOf(SecondSet, MaxSize));
		if t < min then
			min := t;
		Exit
	end;
	
	FirstSet[n] := a[n];
	
	AddNewStone (a, FirstSet, SecondSet, n+1, MaxSize);
	
	FirstSet[n] := 0;
	SecondSet[n] := a[n];
	AddNewStone (a, FirstSet, SecondSet, n+1, MaxSize)
end;

		
var
	n, i : Integer;
	a, f, s : SetOfStones;
	
begin
	Assign (input, 'input.txt');
    Reset (input);
    
    Assign (output, 'output.txt');
    Rewrite (output);

	ReadLn (n);
	
	for i := 1 to n do
		Read (a[i]);
	
	for i := 1 to n do begin
		f[i] := 0;
		s[i] := 0
	end;
		
	min := MaxInt;	
	AddNewStone (a, f, s, 1, n);
	
	WriteLn (min)
end.

Поправил..

Результат такой же - Wrong Answer на 1-м тесте

[Stilet]

Ладно, продолжу выдумывать

var a:array[1..7] of integer=(21, 1, 16, 11, 5, 18, 21);
 j,i,k:integer;c:byte;
 h:array[0..1] of integer;
begin
 h[0]:=a[1];
 h[1]:=a[2];
 for i:=3 to high(a) do begin
   k:=a[i];
   for j:=i+1 to high(a) do if k<a[j] then k:=a[j];
   c:=byte(h[0]>h[1]);
   h[c]:=h[c]+k
 end;
 Caption:=IntToStr(h[1])+' - '+IntToStr(h[0]);
end;

Все равно нечем заняться, пока в Сплинтер Целл бегаю.

[Аватар]

А почему a[1] и a[2] изначально в разных кучах и варианта, что они в одной нет? Может когда они в одной и будет оптимальным вариантом

[Poma][a]

Проблема была решена..
Ваш верный слуга банально отправлял не тот файлик...

[Stilet]

Может когда они в одной и будет оптимальным вариантом

Ну хорошо, можно внести их в цикл.

Проблема была решена..

Ну и ладно

[Stilet]

Может когда они в одной и будет оптимальным вариантом

Ну хорошо, можно внести их в цикл.

Проблема была решена..

Ну и ладно