IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V < 1 2  
 Ответить  Открыть новую тему 
> Нахождение двух минимальных сумм чисел
сообщение
Сообщение #21


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Michael_Rybak @ 30.12.2007 20:07) *

В приведенном мной объяснении многое описано не совсем так, как я бы делал на практике, да.
Логично.
Цитата

А как быть с тестом, в ответе которого участвует большее количество элементов? Почти уверен, что можно составить тест, для которого понадобится и около 40.
Всегда рад smile.gif
А я думаю, что невозможно больше 16. Об этом, кстати, S_lip писал.
Т.е. при заданных ограничениях первые 16 упорядоченного массива ВСЕГДА будут содержать минимум одну искомую группу.
Впрочем, возможно, я и ошибаюся. Просто я не могу придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #22


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.


сейчас попробуем.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #23


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум. мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #24


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Michael_Rybak @ 30.12.2007 20:49) *

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.
Жду с интересом.
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук
Цитата

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум.
Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.
Цитата
мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.
Ну, можно начать с нескольких эвристик. Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #25


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук


Ну 15. Какая разница.

Цитата
Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.


Это не обязательно правильно.

Цитата
Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.


Можешь написать и попросить ОП проверить на сайте.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #26


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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.


Главное отличие - обходим все элементы, а также убрана медленная проверка в конце главного цикла и добавлен массив pad, который содержит позицию "с" и разницу "d" тех элементов, для которых мы нашли замену.
Этот пример также навел на мысль, что максимальное количество перебираемых чисел будет не 15 и не 16, а... 7502 (1 15000 15002 15004 ... 29998 29999). Поэтому нужно перебирать все n. Однако прога не справилась с примером из 200 чисел (1 200 202 204 ... 594 595). udn выходит за пределы 50000. Ошибка 201. Я потратил достаточно много времени, чтобы найти, где промах, но безуспешно.
Этот пример в 200 чисел прикреплен.

Сообщение отредактировано: S_lip -


Прикрепленные файлы
Прикрепленный файл  file.in.txt ( 1003 байт ) Кол-во скачиваний: 144
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #27


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


на самом деле 15.

1 15000 15002 15004 ... 29998 29999- если ты имел ввиду все четные, начиная с 15000, то сразу же получится 15000+15006 = 15002+15004.

ночью посмотрю, где ошибка.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #28


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


15000+15006 = 15002+15004 = 30006
1+29998 = 29999
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #29


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


А, теперь я понял, к чему этот пример был.

Отличная мысль.

andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #30


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


Спасибо большое всем, кто потратил свое время читая это все и пытался помочь...
Я нашел решение:
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.

Ошибка 201 была из-за того, что элементы массивов u и d могу принимать значения от 0 до 50000. Т.е. всего 50001 значение. Изменение начала массивов на 0-ой элемент решило проблему. Также убрана ошибка в ProcessUD, долгий цикл "for ii:= 1 to pn" перенесен в конец главного цикла в виде проверки "if pad[j].u<u[pad[j].c]".
В тестере все примеры решены.

P.S.: С новым годом =)

Сообщение отредактировано: S_lip -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #31


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Отлично, поздравляю.

Приходи еще smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #32


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Michael_Rybak @ 31.12.2007 22:35) *
andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.
Спасибо, я заметил. smile.gif
Кстати, к вопросу об эвристиках:
Решения вида a[n]=a[m] находятся (после сортировки) за O(N), вида a[n]=a[m]+a[k] за O(N*log(N)), a[n]+a[m]=a[k]+a[l] и a[n]=a[m]+a[k]+a[l] - за O(N^2*log(N)).
Правда:
1, 2, 4, 8, 16, 32, 64, 15000, 15128, 15256, ... 29848, 29975 содержит 125 чисел и находится только степенной эвристикой аналогичной тем, что приведены выше, O(N^7*log(N)).

В этой связи возникает еще одна интересная задача: подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения. Заодно интересно было бы оценить минимально необходимое количество тестов в этом наборе.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #33


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения

Такая задача возникает всегда. Именно поэтому уровень тех, кто предлагает задачи на олимпиаду, должен как минимум не уступать уровню участников, а в идеале - быть на порядок выше. Как, кстати, и бывает на всероссийской олимпиаде школьников, где каждая задача проходит через семь кругов ада, прежде чем попасть на тур.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V < 1 2
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.09.2020 3:25
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name