[pascal] Zadanie

[Max1414]

Witam!

 

Robie sobie pewne zadanie na OPSS i mam problem... otóż potrzebuję zapamiętywać gdzieś współrzędne (x,y) i tak:

 

- zapisując je do tablicy i potem przeszukując tablicę przekraczam limit czasu

- zapisując współrzędne do tablicy(boolean) jako tab[x, y]:=true;(jesli dana wspolrzedna wystepu) co jest znacznie szybsze niż przeszukiwanie tablicy przekraczam minimalnie limit pamięci

- zapisujac współrzędne do stringa i potem operując na nim funkcje pos lub delete przekraczają limit czasu

 

Ma ktoś jakiś pomysł w jaki sposób mogę przechowywać te współrzędne?

[Toster]

stworz sobie kolejke posortowana, bedziesz szybciej wyszukiwal, ale dluzej dodawal

[Max1414]

hmm coś nie bardzo mi sie widzi bo takto będzie mi się sortować co chwila, a potem jeszcze będę musiał wyszukiwać(tyle ze juz szybciej troche)

[Force]

Czemu co chwila? logarytmicznie szuka miejsca gdzie włożyć i wsadza.

Wszystko zależy czy współrzędne x,y się powtarzają często.

Edit: no i boolean nie zajmuje jednego bita, tylko minimum bajt, to powinieneś zapisywać np. do integera, przesuwając bitowo

[Toster]

true pozatym rozwiazn jest sporo mozna zrobic np drzewo, albo kolejke albo tablice. pytanie tylko ile bedzie danych i na czym ci najbardziej zalezy (czas zapisu czy odczytu)

[KKKas]

Jak nie chcesz przekombinować to daj jakieś BST (Binary Search Tree) czy coś... Ale jak chcesz mieć dobry wynik to przekombinuj lepiej ;-)

[Max1414]

dzisiaj juz nie mam do tego siły jutro pokombinuje, a teraz tylko skomentuje to "wsadzanie" w odpowiednie miejsce nowych wartosci... otóż, żeby gdzieś wsadzić jakiś element do tablicy to trzeba mu zrobić miejsce a to się wiąże z przesuwaniem elementów i to chyba chwile zajmuje podobnie jak przeszukiwanie pokolei elementów

 

EDIT: i zależy mi na ogólnym czasie, odczyt+zapis , żeby się wyrobić w 1 sekundzie xD

 

 

Edit: no i boolean nie zajmuje jednego bita, tylko minimum bajt, to powinieneś zapisywać np. do integera, przesuwając bitowo

Przybliżysz mi bardziej jak to ma działać? bo nie bardzo czaj

[Toster]

1 sek ?

zerknij na http://forum.unit1.pl/index.php?s=&showtop...indpost&p=13678

pi*drzwi jest tam 10000*20000 operacji co zajmuje okolo 1,7 s na moim kompie

 

wiec o jakich tablicach my mowimy ? kikadziesiat milionow punktow ? bo zwatpilem

[Max1414]

max 10^9 elementow

[Force]

Każdy integer ma 32 bity więc możesz w nie upchać 32 boolean-y. No i sprawdzasz bity. Np jak chcesz 3 bit ro robisz liczba and 4 i jeśli jest różnie od 0, to znaczy że jest true.

Oczywiście mówię o integerach takich 4 bajtowych z freepascal

 

Albo możesz zrobić tablice haszującą dla punktów, to dostaniesz czas stały

[Toster]

10^9 ?

chcialbym zauwazyc ze jesli trzymasz x,y na shortach to masz 4bajty na te wspolrzedne co przy tej wielkosci tablicy daje ci

4x 10^9 = 4GB danych czyli cala przestrzen adresowa dla aplikacji w systemie 32bitowym

jak uzyjesz intow to masz 8GB

 

ale zalozmy ze masz shorty wiec

przy ilosci 5*10^9 konczy ci sie pamiec bo nie dodasz nowego elementu, jak bedziesz chcial zrobic resiza tablicy przez kopiowanie

co wiecej nie sadze aby mgr pamieci byl zdolny zadeklarowac ci jeden ciagly obszar o wielkosci 2GB

 

co wiecej, zazwyczaj masz 1-2GB w systemie, jak zrobisz taka alokacje po pojdzie w ruch virtualka i rzezbienie na dysku

jak uzyskasz predkosc rzedu 1 punkt na 10s to bedzie znaczacy sukces.

po co ci tak gigantyczna ilosc danych ?

[Max1414]

jak juz wspominalem robie zadanie z OPSS wiem ze da sie to zrobić bez tablicy, ale na poziomie mojej matmy nie wymyśle innego sposobu... wiec kombinuje tak

[Toster]

zapomij o tablicy przy takich gigantycznych ilosciach danych, wydaje mi sie ze drzwo byloby chyba najlepszym wyjsciem. Wez na poczatek drzewo binarne dosyc proste i powinno chyba dac rade.

[Force]

A mógłbyś podać treść do zadania lub ją tu wkleić? To ułatwi nam bardzo

[Max1414]

http://opss.safo.biz/?menu=comp&sub=prob&comp=0&prob=1006

[Force]

Acha, to nie do końca jeszcze to przemyślałem, bo jest północ, ale wg mnie nie ma sensu trzymać informacji o wszystkich polach, ale tylko o polach z krawędzie, a mianowicie - ile razy w którą stronę się odbiło, a są tylko 2 możliwości, może podąż tym tropem

 

Edit:

Kilka przydatnych faktów

1) pola na krawędziach zawsze mają nieparzystą ilość ruchów, chyba, że piłka odbije od kąta, wtedy ilość pól z nieparzystą ilością ruchów jest zawsze równa 1

2) piłka nie przechodzi przez pola, które mają za sąsiadów w poziomi lub w pionie, pola przez które już przeszła, inaczej mówić, co drugie pole w każdej linii poziomej będzie puste (z przesunięciem o 1 modulo 2)

3) piłka przechodzi przez jedno pole tylko 0,1 lub 2 razy, chyba, że odbije się od kąta, ale w tedy jest trywialnie, bo punkt 1 zachodzi

4) zaznaczać tylko krawędzie od których piłka się odbiła, kierunek odbicia nie jest ważny, jeśli wejdzie w kąt to zakończyć i zwrócić 1

 

Z tych wskazówek pewnie nie da się zrobić takiej złożoności pamięciowej i czasowej jak jest wymagana, ale może coś z tego się urodzi ja sam nawet nie wiem

 

Edi2: Można to zrobić nie zaznaczają pól nie będących na krawędziach, dla nich pamięci nie trzymać, ale dalej pamięciowo nie przejdzie

[DarkAndrew]

Mozna to zrobic tak ze jak pilka sie odbija zapisujesz rownanie prostej po ktorej leci (tu jest łatwo bo kąt 45 stopni możesz zapisać tylko zkąd się odbija i do czego doleci)i tak do końca aż się będą powtarzać, a potem tylko zliczasz punkty przecięcia a dokladniej to gdzie ich nie ma

[Max1414]

Narazie bawiłem się z tym drzewem... i tak: na opss przekracza czas 1s...

 

program Pileczka;

uses SysUtils;

type
 TPunkt = record
   X, Y: Integer;
 end;
 TDana = TPunkt;
 Drzewo = ^TDrzewo;
 TDrzewo = record
   etykieta: TDana;
   lewy, prawy: Drzewo;
 end;

var
 Wyniki: array[0..20] of Integer;
 N, x, y, x2, y2, I, J, StartX, StartY: Integer;
 IncX, IncY, Znaleziono: Boolean;
 Dana: TDana;
 Drzewko : Drzewo;


procedure Wstaw(var W : Drzewo; Co : TDana);
begin
 if W = nil then
 begin
   new(W);
   if W = nil then
     exit;
   W^.lewy:=nil;
   W^.prawy:=nil;
   W^.etykieta:=Co;
 end
 else
 if W^.etykieta.X > Co.X then
   Wstaw(W^.lewy,Co)
 else
   Wstaw(W^.prawy,Co);
end;

procedure Usun(var W : Drzewo; Co : TDana);
var
 T,X,Y,Z: Drzewo;
begin
 X:=nil;
 Y:=W;
 while Y<>nil do
 begin
 if (Y^.etykieta.X = Co.X) and (Y^.etykieta.Y = Co.Y) then
   break
 else
 begin
   X:=Y;
   if Y^.etykieta.X > Co.X then
     Y:=Y^.lewy
   else
     Y:=Y^.prawy;
 end;
 end;
 if Y<>nil then
   if (Y^.lewy= nil) or (Y^.prawy=nil) then
   begin
     if (Y^.lewy = nil) and (Y^.prawy = nil) then
       Z:=nil
     else
       if (Y^.lewy =nil) then
         Z:=Y^.prawy
       else
         Z:=Y^.lewy;
     if X=nil then
       W:=Z
     else
       if Y=X^.lewy then
         X^.lewy:=Z
       else
         X^.prawy:=Z;
     dispose(Y);
   end
   else
   begin
     Z:=Y^.prawy;
     if Z^.lewy=nil then
       Y^.prawy:= Z^.prawy
     else
     begin
       repeat
         T:=Z;
         Z:=Z^.lewy;
       until
         Z^.lewy=NIL;
       T^.lewy:=Z^.prawy;
     end;
     Y^.etykieta:= Z^.etykieta;
     dispose(Z);
   end;
end;

procedure szukaj(W : Drzewo; Co: tdana);
begin
 if W <> nil then
 begin
   szukaj(W^.Lewy, Co);
   if (W^.etykieta.X = Co.X) and (W^.etykieta.Y = Co.Y) then
   begin
     Znaleziono:=true;
     Exit;
   end;

   szukaj(W^.Prawy, Co);
 end;
end;

procedure drukuj(W : Drzewo);
begin
 if W <> nil then
 begin
   drukuj(W^.Lewy);
   inc(Wyniki[j-1]);
   drukuj(W^.Prawy);
 end;
end;


begin
 ReadLn(N);

 for J:=1 to N do
 begin
   if drzewko <> nil then dispose(drzewko);
   ReadLn(X2, Y2, StartX, StartY);
   X:= StartX;
   Y:= StartY;

   if x = X2 then IncX:=false else IncX:=true;
   if y = Y2 then IncY:= false else IncY:=true;

   repeat
     Dana.X:= x;
     Dana.Y:= y;

     Znaleziono:=false;
     Szukaj(Drzewko, Dana);

     if Znaleziono = false then
       Wstaw(Drzewko, Dana)
     else
       Usun(drzewko, Dana);

     if x = X2 then IncX:=false;
     if x = 1 then IncX:=true;
     if y = Y2 then IncY:= false;
     if y = 1 then IncY:=true;

     if IncX then inc(x) else dec(x);
     if IncY then inc(y) else dec(y);
   until (x=StartX) and (y=StartY);

   drukuj(drzewko);
 end;

 for i:=0 to N-1 do WriteLn(Wyniki[i]);
 ReadLn;
end.

 

EDIT: zły kod wcześniej podałem

[Force]

DarkAndrew: nie trzeba dla ścian pamiętać dokąd leci, tylko czy się odbiła, a ilośc przecięć można zrobić w locie. Gdyby nie to że można tylko 1 mega pamięci uzyć to by było łatwe. Można też pamiętać tylko odbicia dla ściany np górnej i prawej, i zamiast mieć taką pętle jak ma Max1414, to te x,y zmniejszać/zwiększać póki nie dotknie krawędzi, a wtedy tylko zaznaczyć pole z krawędzie jeśli jest górne lub prawe, że od tego się odbiło, i potem iść po górnej i prawej krawędzi i zliczać ile jest pól na przekątnych, które się nie przecinają czy cuś. No i Max1414 powinieneś mieć warunek czy piłka nie weszła w kąt, bo wtedy jest łatwo, bo wraca po tej samej ścieżce i wszystkie pola, oprócz tego kąta, mają parzystą ilość przecięć

A to mi się nie podoba:

 

 
     if x = X2 then IncX:=false;
     if x = 1 then IncX:=true;
     if y = Y2 then IncY:= false;
     if y = 1 then IncY:=true;

     if IncX then inc(x) else dec(x);
     if IncY then inc(y) else dec(y);
'^Ś'ŁiźĆb\"wo,zśŚĘ&j<5ć7Ąi1ik^w)ys\"Wb\"w'Ć-ĘY(ui'
inc(x,IncX);
inc(y,IncY);

Co jest ładne no i szybsze

[Toster]

dobrze prawi dac mu ogorka

[X3o]

Takie małe cytaty z innego tematu o podobnym tematyce

 

CYTAT

Jason:

Na jakimś forum matematycznym (chyba na matematyka.pl) jak się zamieści zadanie z zawodów to dostaje się bana biggrin.gif

 

 

I coś od "moda"

 

Blind:

Jason: a to nawet dobry pomysl jest smile.gif

 

(... )Jesli uczestniczysz w olimpiadzie to znaczy ze umiesz programowac (...)

Jesli ktos uczestniczy w olimiadzie to powinien rozwiazywac zadania samodzielnie!!!!!!

 

No to fajnie na tym forum jest jednym zamkną temat innym nie

To ja dziękuje za takie "forum" :] i się dziwić że mało kto tu zagląda...

 

Pozdrawiam!

 

P.S. Proszę o bana

[TSr]

Już tak nie marudź X3o bo w końcu w tamtym temacie dostałeś podpowiedź, a zadanie było banalne.

Tutaj było ciekawsze zadanie - taki zbieg okoliczności, ze akurat dzisiaj próbowałem je bezskutecznie rozwiązać - czyli było o czym dyskutować.

Ja uważam, że nie powinno się zamykać takich tematów. Jeżeli komuś się będzie chciało o tym coś napisać to będzie OK.

[Nvm]

Tam było "znajdźcie mi błąd w kodzie" a tu jest pytanie bardziej o teorię...

[X3o]

CYTAT(Nvm @ czw, 27 gru 2007 - 10:27) <{POST_SNAPBACK}>

Tam było "znajdźcie mi błąd w kodzie" a tu jest pytanie bardziej o teorię...

 

 

Ty chyba źle zrozumiałeś.. nie chodzi o to czy pytanie było takie czy siakie..

ale temat odwoływał się do "Zawodów Stałych" OPSS i dlatego został zamknięty..

a ten odwołuje się odwołuje..

 

Ale co ja się tu będę żyłował

 

Odpowiedź Moda na pytanie dlaczego mój tak jego nie:

 

temat został załozony nie za mojej kadencji.

 

 

Załóżmy że mnie taka odpowiedź satysfakcjonuje

 

Do nie usłyszenia

[Blind]

Taaa.... tematy z olimpiad na tym forum nigdy nie byly lubiane.

Co to za frajda jesli startujesz w olimpiadzie/konkursie i ktos za ciebie rozwiaze to zadanie, a ty tylko wyslesz? Ten temat tez mi sie nie podoba bo wystepuje w nim pytanie jak to zrobic. To wlasnie chyba o to chodzi zeby uczestnik olimpiady sam na to wpadl.

 

A jesli juz bardzo chcesz zadac pytanie na ten temat to zadaj je tak zeby nie bylo widac ze startujesz w olimpiadze, bo moim zdaniem wszystkie tematy ktore zaczynaja sie w ten sposob "Czesc, startuje w olimpiadzie ale nie wiem jak zrobic zadanie, mozecie mi powiedziec jak to ma byc?" to szczyt chamstwa.