WEB форумы на jedi
[Форум] [Помощь] [Поиск] [Выйти]
Добро пожаловать, [info]User

WEB форумы на jedi [ПОИСК] [Архив до 03.2006]

Тема По просьбе мл.ком. решены "Дрова"! К предыдущему сообщению На следующее сообщение Программирование

Отправил Crypto в 21:40 23.10.2002[Ответить]
Dear Crypto:

Your PASCAL program has solved Ok the problem 10003 (Cutting Sticks)
in 0.000 seconds with low memory spent.
Congratulations!

--

PS: Check the board at http://acm.uva.es/board/

The Online Judge (Linux acm.uva.es 2.4.18-17.7.x i686)
Judge software version 2.8 [http://acm.uva.es/problemset/]
Wed Oct 23 16:50:55 UTC 2002
------------------------------------------------------------------
Решение:

program p10003;
var i,j:integer;
   n,m:integer;
   l:integer;
   t:array [0..51] of integer;
   ct:integer;
   min:integer;
procedure Go;
var mi,ind:integer;
begin
   min:=0;
   for i:=m downto 2 do
   begin
     mi:=t[1]+t[2];
     ind:=1;
     for j:=2 to i-1 do
     if t[j]+t[j+1]<mi then
     begin
       mi:=t[j]+t[j+1];
       ind:=j;
     end;
     t[ind]:=t[ind]+t[ind+1];
     min:=min+t[ind];
     for j:=ind+1 to i-1 do t[j]:=t[j+1];
   end;
end;
begin
   repeat
     readln(l);
     if l=0 then break;
     readln(n);
     t[0]:=0;
     for i:=1 to n do
     begin
       read(ct);
       t[i]:=ct-t[0];
       t[0]:=ct;
     end;
     t[n+1]:=l-ct;
     readln;
     m:=n+1;
{-------------------}
     Go;
     writeln('The minimum cutting is ',min,'.');
   until false;
end.
------------------------------------------------------------------
Алгоритм - тот, который я предлагал в автобусе и который типа неправильный ;) Объяснять второй раз не буду...


Отправил lord_Alex в 22:18 23.10.2002[Ответить]
Ну... на сколько я понял это просто склеивание двух наименьших бревень, обрадую тебя, это решение не проходит на некоторых тестах. А то что испанский сервер его заакцептил, значит у них тесты не правильные. Иначе мы бы тебе эту задачку не предложили.


Отправил Crypto в 23:21 23.10.2002[Ответить]
Пожалуйста, приведи пример теста, а то я так и не подобрал...
Вообще я доказал, что алгоритм верный, но буду рад опровергнуться :)


Отправил lord_Alex в 00:25 26.10.2002[Ответить]
84
9
25 35 39 41 42 43 45 49 59

отрезки:
25 10 4 2 1 1 2 4 10 25
если склеивать
25 10 4 3 1 2 4 10 25
25 10 4 3 3 4 10 25
25 10 7 3 4 10 25
25 10 7 7 10 25
25 17 7 10 25
25 17 17 25
42 42
Итого: 222