Здравствуйте!
Вот такая задачка:
Дана упорядоченная последовательность N чисел. (2<=N<=200). Каждое число больше 0, но меньше 30000. Нужно из этого ряда найти два набора чисел, величины которых должны быть равны и минимальны. Гарантируется, что эта величина будет меньше 100000. Эту величину нужно выписать.
Примеры:
Дано: 1 2 3 4 5. Группы чисел: 1 2 и 3. Ответ: 3.
Дано: 1 2 5 5 8 10 102. Группы чисел: 5 и 5. Ответ: 5.
Дано: 2 3 4 5. Группы чисел: 2 3 и 5. Ответ: 5.
Дано: 1 3 5 7 13 21. Группы чисел: 1 7 и 3 5. Ответ: 8.
Дано: 1 2 5 8 14. Группы чисел: 1 2 5 и 8. Ответ: 8.
Вот я придумал вот такое решение:
http://img401.imageshack.us/img401/500/20308125la9.png
const
MaxCount=200;
MaxSum=100000;
type
pair=record
l,r:longint;
end;
var
a:array [1..MaxCount] of integer;
b:array [0..50000] of pair; //чтоб хватило
f:text;
n,i,j,k,d:integer;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do readln(f,a[i]);
close(f);
d:=0;
repeat
inc(d);
b[0].l:=a[d];
b[0].r:=0;
i:=1;
k:=d;
repeat
inc(k);
for j:= 0 to (i-1) do begin
b[j+i].l:=b[j].l;
b[j+i].r:=b[j].r+a[k];
inc(b[j].l , a[k]);
end;
j:=1;
inc(i,i);
while (j<=i) and (b[j-1].l<>b[j-1].r) do inc(j);
until(j<=i) or (b[0].l>MaxSum)
until j<=i;
writeln(b[j-1].l);
end.
Любые решения этой задачи будут эвристическими, поскольку она NP-полная.
Непонятно условие:
- что такое набор чисел?
- почему сначала о величинах говорится во множественном числе, а потом фигурирует "эта величина", которая, кстати, может достигать 100000, тогда как числа ограничены 30000?
- чем группа числе отличается он "не группы"? Как определить границы группы?
andriano, ок. постараюсь по подробней.
В файле "file.in" в первой строке написано число N (2<=N<=200).
Затем идет N строк, в каждой из которых написано число, величина которого больше одного, но меньше 30000.
Понятно.
Просто уже неоднократно сталкивался с тем, что название темы никак не связано с ее содержанием, а слова "сумма" в теле темы нет.
Честно говоря не имею опыта в подобных оценках, но у меня складывается впечатление, что эта задача скорее олимпиадная, чем учебная. Поэтому, извини, вопрос: откуда она появилась?
andriano, нет это ты меня извини, что задачу описал не информативно.
Задача взята с латвийского портала по олимпиадным http://www.lio.lv/olimps/uzdevumi.php?show=3.
Если она очень мешает в ветке задач, то я могу поместить в тему "олимпиадные задачи".
Сорри, если что не так.
Задача переборная. Поэтому основная идея в решении - сократить перебираемое количество вариантов.
Для начала я бы написал функцию, которая осуществляет перебор всех возможных групп в массиве длины N, где N - входной параметр (массив может быть и глобальный).
Затем отсортировал массив чисел по возрастанию и стал последовательно вызывать функцию перебора, для возрастающих значений N, начиная с 2.
Если за некоторое количество шагов (думаю, не больше 10) искомое решение не найдено, попытался бы применить эвристику (какую - пока не знаю).
В твоем решении не разбирался, но мне непонятно две вещи:
1. Почему именно пары? Ведь в условии, если я правильно его понял, возможны группы из произвольного количества элементов.
2. Зачем хранить пары? Это явно нерациональное использование памяти. У нас ведь переборная задача. Увеличение объема вычислений в 2-3 раза совершенно некритично. Поэтому не грех вычислять суммы прямо внутри цикла, нигде их не храня. Сохранять имеет смысл только наилучший из найденных ваиантов.
Через некоторое время.
Пожалуй, эвристики или, по крайней мере, некоторые из них лучше использовать ДО перебора. В частности, они могут помочь найти решение, не являющееся минимальным, но существенно сокращающее объем дальнейшего поиска.
И так же по поводу эвристик:
Какой именно из двух ваиантов тебе нужен?
1. Программа ВСЕГДА находит нужное решение. Сама программа при этом наиболее проста, но работать может до конца существования Вселенной (ну или, по крайней мере, до физического износа компа).
2. Программа, время работы которой ограничено. При этом она может выдать не то решение, которое нужно (т.е. не минимальное) или же совсем ничего не найти.
Да, и еще:
Перебор рано заканчивать, если найдено решение, при котором в обеих группах более одного элемента, - необходимо продолжить его до тех пор, пока в рассмотрении не будет участвовать максимальное число, не превосходящее эту сумму.
в общем вот грубый перебор Все приведенные тобой тесты программа прошла, на 200 чисел конечно такое решение врятли потянет, не пробовал, но думаю задумается прога надолго
{$R-}
uses crt;
type
PTArray = ^TArray;
TArray = array [1..1] of Integer;
PTFlags = ^TFlags;
TFlags = array [1..1] of 0..1;
TIdxSet = Set of Byte;
const
MIN_SUM: Integer = 10001;
group1: TIdxSet = [];
group2: TIdxSet = [];
var
arr: PTArray;
size: Byte;
flags1, flags2: PTFlags;
procedure shift_flags(var flags: PTFlags);
var
i: Byte;
begin
i := size + 1;
repeat
dec(i);
inc(flags^[i]);
if flags^[i] = 2 then
flags^[i] := 0;
until flags^[i] = 1;
end;
procedure print_flags(const flags: PTFlags);
var
i: Byte;
begin
writeln;
for i := 1 to size do write(flags^[i]);
writeln;
end;
function group_sum(const flags: PTFlags): Integer;
var
i: Byte;
_result: Integer;
begin
_result := 0;
for i := 1 to size do
if flags^[i] = 1 then
_result := _result + arr^[i];
group_sum := _result;
end;
procedure copy_flags(const _from: PTFlags; var _to: PTFlags);
begin
move(_from^, _to^, size);
end;
function unique_flags(const a, b: PTFlags): Boolean;
var
i: Byte;
begin
i := size;
while (i > 0) and not (a^[i] * b^[i] = 1) do
dec(i);
unique_flags := (i = 0);
end;
procedure flags2set(const flags: PTFlags; var idx_set: TIdxSet);
var
i: Byte;
begin
idx_set := [];
for i := 1 to size do
if flags^[i] = 1 then
include(idx_set, i);
end;
function final_query(const flags: PTFlags): Boolean;
var
i: Byte;
begin
i := 1;
while (i <= size) and (flags^[i] = 1) do
inc(i);
final_query := (i > size);
end;
procedure get_solve;
var
s1, s2: Integer;
find: Boolean;
begin
repeat
shift_flags(flags1);
s1 := group_sum(flags1);
if (s1 < MIN_SUM) then begin
copy_flags(flags1, flags2);
find := false;
repeat
shift_flags(flags2);
if unique_flags(flags1, flags2) then begin
s2 := group_sum(flags2);
if s1 = s2 then begin
MIN_SUM := s1;
flags2set(flags1, group1);
flags2set(flags2, group2);
find := true;
end;
end;
until find or final_query(flags2);
end;
until final_query(flags1);
end;
var
f: Text;
i: Byte;
begin
clrscr;
assign(f, 'C:\input.txt');
reset(f);
readln(f, size);
getmem(arr, size * sizeof(TArray));
for i := 1 to size do begin
readln(f, arr^[i]);
write(arr^[i]:4);
end;
writeln;
close(f);
getmem(flags1, size * sizeof(TFlags));
getmem(flags2, size * sizeof(TFlags));
fillchar(flags1^, size * sizeof(TFlags), 0);
copy_flags(flags1, flags2);
get_solve;
freemem(flags1, size * sizeof(TFlags));
freemem(flags2, size * sizeof(TFlags));
writeln;
write('group1: ');
for i := 1 to size do
if i in group1 then write(arr^[i]:3, ',');
writeln;
write('group2: ');
for i := 1 to size do
if i in group2 then write(arr^[i]:3, ',');
writeln;
writeln;
writeln('S = ', MIN_SUM);
freemem(arr, size * sizeof(TArray));
readln;
end.
Спасибо всем большое за ответы!
klem4, спасибо за код.
Я "вроде бы" нашел решение.
Чтобы было более понятнее вот текст задачки:
const
MaxCount=200;
MaxSum=100000;
var
a:array [1..MaxCount] of integer;
u,d:array [1..(MaxSum div 2)*3+1] of longint; //"*3+1" для крайности, т.к. мы сначала заполняем, а потом отсеиваем ненужное
udn:longint;
b:array [0..(MaxSum div 2)] of longint; //если будет болше 50000, то общая сумма будет больше 100000
f:text;
n:byte;
i,j,k:longint;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);
for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=1;
i:=1;
u[1]:=0;
d[1]:=a[1];
b[a[1]]:=a[1];
repeat
inc(i);
inc(udn);
u[udn]:=0;
d[udn]:=a[i];
for j:= 1 to udn-1 do begin
inc(udn);
u[udn]:=u[j];
d[udn]:=d[j]+a[i];
inc(udn);
if u[j]+a[i]<d[j] then begin
u[udn]:=u[j]+a[i];
d[udn]:=d[j];
end else begin
u[udn]:=d[j];
d[udn]:=u[j]+a[i];
end;
end;
inc(j);
repeat
k:=d[j]-u[j];
if (d[j]>(MaxSum div 2)) or (u[j]>(MaxSum div 2)) then begin
u[j]:=u[udn];
d[j]:=d[udn];
dec(udn);
end else if b[k]>0 then begin
if u[j]<u[b[k]] then begin
u[b[k]]:=u[j];
d[b[k]]:=d[j];
end;
u[j]:=u[udn];
d[j]:=d[udn];
dec(udn);
end else begin
b[k]:=j;
inc(j);
end;
until j>udn;
until b[0]>0;
writeln(u[b[0]]); //ответ
end.
Не мог бы ты объяснить, почему надо перебирать именно эти числа? Во входном файле может не оказаться ни одного из них.
Именно эти - чтоб получилась цепочка максимальной длины.
Можно, конечно, выбрать и этот ряд 1 3 5 10 20 40 80 160 320 640 1280 2560 5120 10240 20480 и еще одно до 30000. Можно и другой, но с учетом, чтобы числа были как можно меньше. Будут числа более большие - меньше шансов что следующее число будет меньше 30000 и, как следствие, длиннее цепь.
Не понял.
Прочитав эту фразу:
Я имел ввиду нахождение наибольшего количества чисел из входной цепочке, которые следует перебирать.
Может, и я тебя неправильно понял.
Так и не получил ответа на вопрос:
andriano, мне не нужен ни один из предложенных вариантов. Мне нужно, что программа всегда давала правильный ответ за ограниченное время работы (не дольше 1 секунды). Именно такой программой и является мой последний выложенный код.
Ко всем: если кто может, помогите найти такие входные файлы, чтобы эта программа давала неправильный ответ, т.к. все тесты, которые я пробовал, она проходила на "ура".
Вот небольшое разъяснение работы моего кода, которое поможет вам в ней разобраться и, возможно, найти такую цепь, при которой прога давала бы неправильный ответ.
1) Массивы "u" и "d" содержат все возможные минимальные наборы чисел от 1 до i элемента в цепи. Причем для удобства u[num]<=d[num].
2) Под минимальными имеется ввиду следующее: например сдери массивов уже имеются такие пары: u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7. Первая пара нам не нужна, т.к. если следующая i будет 7, то в качестве ответа подойдет и 7 (0+7=7) и 8 (1+7=8). Поэтому после всех добавления в массивы u и d всех новых пар с участием i, идет отсеивание ненужных пар.
3) Чтобы каждый раз не сортировать массивы u и d, используется массив b, каждый элемент которого указывает на пару в массива u и d с соответствующей разностью. Например, в случае с u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7, b[8-1]=num1, а b[7-0]=num2. Понятно, что b[7] может хранить только одно значение. В нашем случае - b[7]=num2, т.к. u[num2]=0 d[num2]=7 - минимальны.
Разберем пример цепи из 4-ех чисел: 1 3 5 7.
1) сначало копируем первый элемент(1):
u d
0 1
b= ( 0,1,0,0,0,0,0,0...). Именно так потому, что d[1]-u[1]=1, а массив b начинается с 0-ого элемента.
2) второй элемент(3):
u d
0 1 - этот был.
0 3 - этот добавляем с учетом, что ответ будет включать в себя 2-ой эл-т, но не будет то, что было.
0 4 - один набор включает то, что было в d + 3, а второй - то, что было в u.
1 3 - наобарот. один набор включает то, что было в u + 3, а второй - то, что было в d. Переверачиваем,т.к. u[4]>d[4].
b= ( 0,1,4,2,3,0,0,0...).
3) третий элемен(5):
u d
0 1 - был.
0 3 - был.
0 4 - был.
1 3 - был.
0 5 - этот добавляем с учетом, что ответ будет включать в себя 3-ий эл-т, но не будет то, что было.
0 6 - один набор включает то, что было в d[1] + 5, а второй - то, что было в u[1].
1 5 - наобарот. один набор включает то, что было в u[1] + 5, а второй - то, что было в d[1]. Переверачиваем,т.к. u[8]>d[8].
0 8 - u[2]/d[2]+5.
3 5 - u[2]+5/d[2]. Переворачиваем.
0 9 - u[3]/d[3]+5.
4 5 - u[3]+5/d[3]. Переворачиваем.
1 8 - u[4]/d[4]+5.
3 6 - u[4]+5/d[4]. Переворачиваем.
Теперь отсеиваем ненужные: 1/5 (т.к. есть 0/4), 3/5 (есть 1/3), 4/5 (0/1), 3/6 (0/3).
Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
b= (0,1,4,2,3,5,6,7,8,9)
4) четвертый элемен(7):
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 8
1 7
0 10
3 7
0 11
4 7
1 10
3 8
0 12
5 7
0 13
6 7
0 15
7 8
0 16
7 9
1 15
8 8
Отсеиваем ненужные. Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 10
0 11
0 12
0 13
0 15
0 16
1 15
8 8
b= (18,1,4,2,3,5,6,9,7...)
Ура! b[0]>0. ответ: u[b[0]]. т.е. - 8
Во-первых, посыпая голову пеплом, вынужден признать, что задача ни разу не NP-полная.
Ты двигаешься в правильном направлении.
Проблема в массиве b. Дело в том, что он хранит "указатели" на первый попавшийся результат для данной разницы. А тебе нужен не любой, а наименьший (т.е. с наименьшей суммой).
Вот тебе тест:
Его решение оптимально, поэтому твое в лучшем случае имело бы лучшую константу, и такую же асимптотику.
// схематически
fillchar(can_achieve_difference_next_step, false);
can_achieve_difference_next_step[X] := true; // только эта гирька на правой чаше
can_achieve_difference_next_step[-X] := true; // только эта гирька на левой
for i := -100000 to 100000 do
can_achieve_difference_next_step :=
can_achieve_difference[i-x] // на левую чашу?
or can_achieve_difference[i + x] // на правую?
or can_achieve_difference[x]; // не используем вообще?
move(can_achieve_difference, can_achieve_difference_next_step);
// на самом деле, второй массив не нужен, так как старые значения true остаются на месте. но так - понятнее
Спасибо, идею алгоритма понял.
выбрать не получилось.
видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.
но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум. мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.
Michael_Rybak, спасибо за пример.
Вот исправленный код:
const
MaxCount=200;
MaxSum=100000;
type
posanddif=record
c,d:longint;
end;
var
a:array [1..MaxCount] of integer;
n:byte;
u,d:array [1..(MaxSum div 2)] of longint;
udn:longint;
b:array [0..(MaxSum div 2)] of longint;
pad:array [1..(MaxSum div 2)] of posanddif;
pn:longint;
f:text;
i,j:longint;
procedure ProcessUD(uu,dd:longint);
var
ii:longint;
begin
if dd<=(MaxSum div 2) then begin
if b[dd-uu]>0 then begin
if u[b[dd-uu]]>uu then begin
ii:=1;
while (ii<=pn) and (pad[ii].c<>b[dd-uu]) do inc(ii);
if ii>pn then begin
inc(pn);
pad[pn].c:=b[dd-uu];
pad[pn].d:=u[b[dd-uu]]-uu;
end else if pad[ii].d>u[b[dd-uu]]-uu then
pad[ii].d:=u[b[dd-uu]]-uu;
end;
end else begin
inc(udn);
u[udn]:=uu;
d[udn]:=dd;
b[dd-uu]:=udn;
end;
end;
end;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);
for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=1;
i:=1;
u[1]:=0;
d[1]:=a[1];
b[a[1]]:=a[1];
for i:= 2 to n do begin
pn:=0;
j:=udn;
ProcessUD(0,a[i]);
for j:= 1 to j do begin
ProcessUD(u[j],d[j]+a[i]);
if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
else ProcessUD(d[j],u[j]+a[i]);
end;
for j:= 1 to pn do begin
dec(u[pad[j].c],pad[j].d);
dec(d[pad[j].c],pad[j].d);
end;
end;
writeln(u[b[0]]); //ответ
end.
на самом деле 15.
1 15000 15002 15004 ... 29998 29999- если ты имел ввиду все четные, начиная с 15000, то сразу же получится 15000+15006 = 15002+15004.
ночью посмотрю, где ошибка.
15000+15006 = 15002+15004 = 30006
1+29998 = 29999
А, теперь я понял, к чему этот пример был.
Отличная мысль.
andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.
Спасибо большое всем, кто потратил свое время читая это все и пытался помочь...
Я нашел решение:
const
MaxCount=200;
MaxSum=100000;
type
posanddif=record
c,u:longint;
end;
var
a:array [1..MaxCount] of integer;
n:byte;
u,d,b:array [0..(MaxSum div 2)] of longint;
udn:longint;
pad:array [1..(MaxSum div 2)] of posanddif;
pn:longint;
f:text;
i,j:longint;
procedure ProcessUD(uu,dd:longint);
begin
if dd<=(MaxSum div 2) then begin
if b[dd-uu]>0 then begin
if u[b[dd-uu]]>uu then begin
inc(pn);
pad[pn].c:=b[dd-uu];
pad[pn].u:=uu;
end;
end else begin
inc(udn);
u[udn]:=uu;
d[udn]:=dd;
b[dd-uu]:=udn;
end;
end;
end;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);
for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=0;
i:=1;
u[0]:=0;
d[0]:=a[1];
b[a[1]]:=a[1];
for i:= 2 to n do begin
pn:=0;
j:=udn;
ProcessUD(0,a[i]);
for j:= 0 to j do begin
ProcessUD(u[j],d[j]+a[i]);
if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
else ProcessUD(d[j],u[j]+a[i]);
end;
for j:= 1 to pn do begin
if pad[j].u<u[pad[j].c] then begin
dec(d[pad[j].c],u[pad[j].c]-pad[j].u);
u[pad[j].c]:=pad[j].u;
end;
end;
end;
writeln(u[b[0]]);
end.
Отлично, поздравляю.
Приходи еще