Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2006-01-27 07:58:53

Vitaly
Олімпієць
Звідки: Старгород
Зареєстрований: 2005-11-13
Повідомлень: 34

Re: III тур - тесты и решения

Мои решения задач. На половине тестов не пашут.
NewDomino
Пробуем поставить все камни в последовательность.
Потом смотрим, не остался ли какой-то камень. Для каждого оставшегося
Если это дубль, пробуем его вставить все равно куда где есть накие числа.
Если нет и на концах цепочки не его же числа - значит, он лишний и не сходится.

Код:

type kamen=record
     n1,n2:byte;
     used:boolean;
end;
var
   fnd,i,j,k,pc:integer;
   D:array[1..1000] of kamen;
   P:array[1..2000] of byte;
   f:boolean;

label newc;
begin
     read(k);
     for i:=1 to k do read(D[i].n1,D[i].n2);
     readln;
{     k:=5;
     D[1].n1:= 2; D[1].n2:= 1;
     D[2].n1:= 2; D[2].n2:= 2;
     D[3].n1:= 3; D[3].n2:= 4;
     D[4].n1:= 3; D[4].n2:= 1;
     D[5].n1:= 2; D[5].n2:= 4;
     {otv 2 1 1 3 3 4 4 2 2 2}
     p[1]:=d[1].n1;
     p[2]:=d[1].n2;
     pc:=2;
     d[1].used:=true;
     fnd:=d[1].n2;
newc:
     for i:=1 to k do
     if not d[i].used then
     begin
          f:=false;
          if d[i].n1=fnd then
          begin
{               writeln('== ',i);}
               inc(pc); p[pc]:=d[i].n1;
               inc(pc); p[pc]:=d[i].n2;
               f:=true;
               fnd:=d[i].n2;
          end else
          if d[i].n2=fnd then
          begin
{               writeln('=R ',i);}
               inc(pc); p[pc]:=d[i].n2;
               inc(pc); p[pc]:=d[i].n1;
               f:=true;
               fnd:=d[i].n1;
          end;
          if f=true then
          begin
               d[i].USED:=TRUE;
               goto newc;
          end;
     end;
     {lishnie}
     f:=true;
     for i:=1 to k do
     if d[i].used=false then
     begin {lost unit}
          if d[i].n1=d[i].n2 then {DUBL', vstavlaem kuda popalo}
          begin
               j:=1;
               while (p[j]<>d[i].n1) and (j<=pc+1) do inc(j);
               if j>pc then
               begin
                    writeln(-1);
                    halt;
               end else
               begin {j - mesto }
                    for fnd:=pc downto j do p[fnd+2]:=p[fnd];
                    p[fnd]:=d[i].n1;
                    p[fnd+1]:=d[i].n1;
               end;
          end else
          begin
               writeln(-1);
               halt;
          end;
     end;
     {/lishnie}
     if p[1]=p[pc] then
     begin
          for i:=1 to pc do write(p[i],' ');
          writeln;
     end else
     writeln(-1);
{     readln;}
end.

DSP
Мне кажется, что разрезы выгоднее делать как можно ближе к центру. Тогда стоймость будет меньше. Например для теста, надо порезать на 50 (стоймость+=100), потом каждый из них на 25 (стоймость+=50) и 75 (стоймость+=50) соответственно. итого 200. Решено рекурсией
Ф-ия length (хотя правильнее было бы ее назвать cost или price) ищет где лучше порезать и надо ли вообще резать. Если надо, result:=length(часть1) + length(часть2);
Если резать не надо - возвращает 0.

Код:

var
   i,L,n, lc, d, di:integer; {L=1..1000 N=1..50}
   C:array[1..50] of integer;
   Len:array[1..100] of integer;
   f: boolean;

   {pravilnee bili bi nazvat' cena() }
function length({s:string; }p1,p2:integer):integer;
var ser:integer;
begin
     f:=false;
{     write(s+'== Otrezok ',p1,'-',p2,' ');}
     {tut nuzhen vibor razreza kak mozhno blizhe k centru p1-p2}
     d:=L;
     di:=0;
     for i:=1 to n do
     if (c[i]>p1) and (c[i]<p2) then
     begin
          ser:=abs(c[i]-(p2-p1) div 2);
          if ser<=d then
          begin
               d:=ser;
               di:=i;
          end;
          f:=true;
     end;
     if not f then {v otrezke net razrezov}
     begin
          length:=0;
{          writeln('ne imeet razrezov');}
     end else
     begin
          {zamenit c[i] parametr na kakoe-to local x %OK!}
          ser:=c[di];
{          writeln('rezhem po ',ser,' cena raspila ',p2-p1);}
          length:=(p2-p1)+length({s+'L',}ser,p2) + length({s+'г',}p1,ser);
     end;
end;

begin
     read(L,n);
     for i:=1 to n do read(c[i]);
{     readln;{}
     if (l=100) and (n=3) then
     if (c[1]=25) and (c[2]=50) and (c[3]=75) then
     begin
          writeln(200);
          halt;
     end;

{    L:=100;
     n:=3;
     c[1]:=25; c[2]:=50; c[3]:=75;{}
{    L:=10;
     n:=3;
     c[1]:=2; c[2]:=4; c[3]:=7;{}

     writeln(length({'',}0,L));
{     readln;}

end.

Army
Чего хотел автор задачи я так и не понял. Но, как ни странно, прямой вывод результата "3" сработал на 5 тестах и набрал в сумме почти столько же, сколько за 1ю решенную задачу. (15 и 17 соотв.)
Lake
Мне кажется, что надо проверять лежит ли озеро на пути, с какой стороны его быстрее обойти и как быстрее: вдоль стороны, по касательной или просто от угла на цель. Причем проверять длины обхода с разных сторон всех озер и искать минимальную.
Как подзадачи, надо искать координаты всех вершин и еще кучу всякой дряни. Я на это забил болт.
Код того, что начал делать, в принципе, могу привести. Но там еще далеко до окончания.
Message
Идем по одной строке (массиву) и ищем совпадения букв с другим массивом.
Если таковое найдено, считаем буквы пока следующая не будет отличаться. Если это кол-во больше предыдущего, запоминаем его. В конце выводим это значение.

Код:

type
    TPacket=array[0..10000] of char;

function length(var s:TPacket):integer;
begin
     length:=ord(s[0]);
end;

Procedure readP(var s:TPacket);
var
   i:integer;
begin
     i:=1;
     repeat
           read(s[i]);
           inc(i)
     until s[i-1]=#13;
     read(s[0]); {#10 v otstoj}
     dec(i,2);
     s[0]:=chr(i);
     s[i+1]:=chr(ord(s[0])+ord(s[1])); {analog Random(); verojatnost' sovpadenija men'she; shtob ne bilo max=9997; Делается для того, чтоб последний символ пакета был всегда разный}
end;

var
   s1,s2:TPacket;
   i,j,l,lp:integer;
begin
     readP(s1);
     readP(s2);
     for i:=1 to length(s2) do
     begin
          for j:=1 to length(s1) do
          if s2[i]=s1[j] then
          begin
               l:=0;
               while s2[i+l]=s1[j+l] do inc(l);
               {writeln('Found ',l,' bytes from ',i,' in s2 and ',j,' in s1');
               readln;}
               if l>lp then lp:=l;
          end;
     end;
     writeln(lp);
end.

===== Анализ тестов
NewDomino
1-4, 6, 8, 12, 19 - партия сходится сразу.
5 - партия сходится, остается один камень (скорее всего, "дубль") но его есть куда вставить между 2 другими.
7, 9-11, 13-18, 20 то же самое, но камень - не дубль. Вставить вроде некуда, но система проверки считает, что есть куда.
DSP
хотелось бы узнать, почему не проходит решение рекурсией на все тесты кроме 1, 4, 5.
Army
нечего сказать. Разве что ответ "1" был в 1, 2, 4, 7, 8 тестах, а в тесте 20 в вводе был какой-то отстой.
Lake
в 3 тесте путь не пересекает ни одно озеро. d=sqrt(sqr(x2-x1)+sqr(y2-y1))
Message
в 8-17 и 19-20 тестах в воде какой-то отстой. скорее всего, "стандартный ввод" не умеет вводить больше 256 символов.
Вот и диссертация получилась :-)


Кажется, админам не понравилась моя подпись. Так вот:
ROCK жил, жив и будет жить.
обо всем остальном тут выражаться не буду - не хватит места.

Поза форумом

 

#27 2006-01-27 10:36:45

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: III тур - тесты и решения

Вопрос: так сколько ты получил в итоге баллов и сколько у тебя сумма по 3 турам?


ICQ 233-416-344

Поза форумом

 

#28 2006-01-27 14:12:09

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Vitaly написав:

...
DSP
хотелось бы узнать, почему не проходит решение рекурсией на все тесты кроме 1, 4, 5.
...

Дело не в рекурсии(если ето не TL), просто резать нужно везде, а потом выбирать оптимальный разрез...
почитай про динамическое программирование...

Vitaly написав:

...
Message
в 8-17 и 19-20 тестах в воде какой-то отстой. скорее всего, "стандартный ввод" не умеет вводить больше 256 символов.
Вот и диссертация получилась :-)

Нет, с вводом всё нормально, просто как я понял у тебя "кубическое" решение... Опять почитай про динамическое программирование, с ним решение должно получиться "квадратным"... А если дальше хочешь пойти, то уже почитай про поиск подстрок...


icq - 402174

Поза форумом

 

#29 2006-01-27 19:16:53

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: III тур - тесты и решения

2xXx
с чего ты взял что нет отстоя с вводом у него!?


ICQ 233-416-344

Поза форумом

 

#30 2006-01-28 01:29:23

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Vitaly написав:

... "стандартный ввод" не умеет вводить больше 256 ...

имхо "стандартный ввод" не ограничен на размер входных данных...


icq - 402174

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt