Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.08.2013, 20:26   #1
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию Решение задачи #71 на acmp.ru

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

Я упорно пытаюсь сдать задачку #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.
Заранее спасибо!
Poma][a вне форума Ответить с цитированием
Старый 28.08.2013, 20:46   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Э-э-эммм..
Код:
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плю?
I'm learning to live...

Последний раз редактировалось Stilet; 28.08.2013 в 20:49.
Stilet вне форума Ответить с цитированием
Старый 28.08.2013, 21:02   #3
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Код:
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
Poma][a вне форума Ответить с цитированием
Старый 28.08.2013, 21:24   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

А косяк не в том, что diff слишком много памяти кушает? Зачем он вообще нужен, без него спокойно можно обойтись, каждую полученную сумму сравнивая с min еще в AddNewStone
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 28.08.2013, 21:29   #5
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
А косяк не в том, что 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-м тесте
Poma][a вне форума Ответить с цитированием
Старый 28.08.2013, 21:30   #6
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Ладно, продолжу выдумывать
Код:
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;
Все равно нечем заняться, пока в Сплинтер Целл бегаю.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 28.08.2013, 21:37   #7
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

А почему a[1] и a[2] изначально в разных кучах и варианта, что они в одной нет? Может когда они в одной и будет оптимальным вариантом
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 28.08.2013, 21:41   #8
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Проблема была решена..
Ваш верный слуга банально отправлял не тот файлик...
Poma][a вне форума Ответить с цитированием
Старый 28.08.2013, 22:09   #9
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Цитата:
Может когда они в одной и будет оптимальным вариантом
Ну хорошо, можно внести их в цикл.
Цитата:
Проблема была решена..
Ну и ладно
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 28.08.2013, 22:09   #10
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Цитата:
Может когда они в одной и будет оптимальным вариантом
Ну хорошо, можно внести их в цикл.
Цитата:
Проблема была решена..
Ну и ладно
I'm learning to live...
Stilet вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация (сокращение) кода решения задачи #2 c acmp.ru - нахождение суммы целых чисел от 1 до N Serge_Bliznykov Помощь студентам 31 23.08.2014 22:35
Оптимизация (сокращение) кода решения задачи #46 c acmp.ru - вывод числа E с заданной точностью Poma][a Паскаль, Turbo Pascal, PascalABC.NET 47 05.07.2013 23:50
Олимпиадные Задачи (с acmp.ru) Poma][a Паскаль, Turbo Pascal, PascalABC.NET 7 20.12.2012 07:44
Решение задачи в с++. Gray007 Помощь студентам 2 27.01.2011 15:19
решение задачи kuzmich Помощь студентам 1 14.09.2010 19:57