OI....

[kostek13_88 0]

jeszcze przejdziesz do drugiego etapu i co będzie

[Stnkk 0]

jeszcze przejdziesz do drugiego etapu i co będzie

Hehe, moze do finalu Wtedy mialbym wstep na uczelnie za friko A tak na serio to skasuje moje zadania ;]

[kostek13_88 0]

hmmm..... zrobiłem tetrisa ale na ostatnim teście łapie czasówkę... a po za tym zorientowałem się że w profesorze szu nie przejdzie tabica miliard na miliard

[mr262560 0]

hmmm..... zrobiłem tetrisa ale na ostatnim teście łapie czasówkę... a po za tym zorientowałem się że w profesorze szu nie przejdzie tabica miliard na miliard

mi ostatni test przechodzi w 0,17s, ale wygenerowałem sobie kompletnie 2 losowe i jeden leci 10s a drugi 18, na moim kompie (pIII800, 256ram@150mhz)... na kompie brata (1,5Ghx, celeron M, 256MB jakiegoś DDR) robi 3x szybciej...

no a w szu trzeba wszystko chyba dynamicznie trzymac, bo inaczej braknie pamieci

[kostek13_88 0]

hmmmm....to może ktoś mi da jakiegoś hinta do tetrisa.....bo nie mam pomysłu...

[bRave 0]

Tak sobie z ciekawości zajrzałem na tego tetrisa 3d i całkiem fajne zadanie, do jego rozwiązania wystarczy jedna tablica o rozmiarach NxM

 

Złożoność algorytmu jest liniowa N*(Nd*Ns) porównań

 

Zapomniałbym, hint:

W tablicy zapisujecie obecną wysokość na jakiej znajduje się wierzchni klocek dla danych koordynatów

[kostek13_88 0]

do tego też doszedłem....tylko moja złożoność aktualnie wygląda 2n^3+n^2 jakiś inny hint

[januzi 24]

bierzesz klocek, masz x, y, w, d, s

for a := x to x + s do

for b := y to y + d do

tablica[a,b] := nowe_w ;

 

ale mysle, ze daloby sie zrobic to troche szybciej

 

jednak da sie zrobic szybciej, i to uniezalezniajac sie od D, tyle ze ta metoda dobra bedzie od okreslonych wymiarow studni

[bRave 0]

bierzesz klocek, masz x, y, w, d, s

for a := x to x + s do

for b := y to y + d do

tablica[a,b] := tablica[a,b] + w ;

 

ale mysle, ze daloby sie zrobic to troche szybciej

 

nie do końca, z tych pól które wskazałeś trzeba wybrać aktualnie najwyższe, następnie zwiększyć jego wartość o wysokość klocka i tą nową wartość wpisać do wszystkich pozostałych pól z tego zakresu jaki podałeś.

[kostek13_88 0]

i to ma taki czas jak podałem więc czekam na jakiegoś normalnego hinta

[bRave 0]

i to ma taki czas jak podałem więc czekam na jakiegoś normalnego hinta

 

No to podaj dokładnie jak to liczysz i opisz algorytm to skonsultujemy Jak wolisz może być przez PM.

 

P.S. Ja złożoność liczę tylko i wyłącznie ze względu na ilość porównań, bo nic innego nie ma tu IMHO większego sensu...może w tym Tkwi problem różnicy między Twoim a moim oszacowaniem.

[mr262560 0]

moj ziomus ma ponizej n^2, ale raczej sie i tak nie ryrabia... moj hint: po co robić tablicę, skoro autorzy zadania dają nam dane w bardzo ładnej formie (tak ja robie, ale ciągle nie starcza mi czasu...

[bRave 0]

jednak da sie zrobic szybciej, i to uniezalezniajac sie od D, tyle ze ta metoda dobra bedzie od okreslonych wymiarow studni

 

Zaraz, zaraz piszesz o D (długość studni) czy o d (długość klocka)? Bo od d nie za bardzo jest się jak uniezależnić a D w ogóle nie ma wpływu na złożoność algorytmu (no fakt narzuca nam maksymalne d ale to wszystko)

 

 

moj ziomus ma ponizej n^2, ale raczej sie i tak nie ryrabia... moj hint: po co robić tablicę, skoro autorzy zadania dają nam dane w bardzo ładnej formie (tak ja robie, ale ciągle nie starcza mi czasu...

 

Bo w tablicy przechowujesz dane pomocnicze, których nie ma na wejściu programu

[kostek13_88 0]

mam nadzieję tylko że nie startujesz i nie wyślesz mojego rozwiązania...

[mr262560 0]

Złożoność algorytmu jest liniowa N*(Nd*Ns) porównań

w pesymistycznym przypadku 20000*1000*1000 = 2*10^10, moj ma w najgorszym 2*n^2=8*10*8... w sumie to (n+1)*n= 4*10^8 i sie nie wyrabia dla brzydkich danych

 

Bo w tablicy przechowujesz dane pomocnicze, których nie ma na wejściu programu

w moim programie nie ma zadnej tablicy... musiałem skorzystać z listy, przez co sie poprawiła chyba złożność średnia... chociaz, musiałbym sprawdzic dla tablicy, czy nie leciałoby lepiej ;]

[januzi 24]

zauwaz, ze D moze byc 10, 10k, jak i 10M, i teraz sobie przyjmij, ze wszystkie klocki poleca takie same S,D,jakies_male_w, wyjdzie z tego 40*D*10^6 operacji (najpierw szukanie wartosci maks w zadanym przedziale, potem wspisywanie jej z powrotem do tablicy), jesli D bedzie 10M, to wyjdzie 400*10^12 (o limicie pamieci = 128M juz nie wspominam)

[bRave 0]

zauwaz, ze D moze byc 10, 10k, jak i 10M, i teraz sobie przyjmij, ze wszystkie klocki poleca takie same S,D,jakies_male_w, wyjdzie z tego 40*D*10^6 operacji (najpierw szukanie wartosci maks w zadanym przedziale, potem wspisywanie jej z powrotem do tablicy), jesli D bedzie 10M, to wyjdzie 400*10^12 (o limicie pamieci = 128M juz nie wspominam)

 

na D i S jest limit <=1000

w jest nie istotne, badasz przecież tylko podstawe klocka a nie wszystkie jego warstwy

 

 

mam nadzieję tylko że nie startujesz i nie wyślesz mojego rozwiązania...

 

za stary jestem, ale jak chcesz.

[januzi 24]

a, mozliwe, warunki moglyby byc oddzielane ;

to jak D jest <= 1k, to lacznie bedzie w najgorszym wypadku 40*10^9 operacji

[kostek13_88 0]

hmmm... inne pytanie jak porównać czy literka jest taka sama w tablicy stringów... bo nie działa mi

char tekst[ZAK];
...
if(tekst[0]==tekst[a]) wyn+=a;

 

jak to napisać????

[bRave 0]

w pesymistycznym przypadku 20000*1000*1000 = 2*10^10, moj ma w najgorszym 2*n^2=8*10*8... w sumie to (n+1)*n= 4*10^8 i sie nie wyrabia dla brzydkich danych

w moim programie nie ma zadnej tablicy... musiałem skorzystać z listy, przez co sie poprawiła chyba złożność średnia... chociaz, musiałbym sprawdzic dla tablicy, czy nie leciałoby lepiej ;]

 

W takim wypadku zakładam,że przeglądasz pod kątem kolidujących ze sobą klocków wtedy na wstępie wystarczy badać tylko 4 koordynaty (i już pierwsza może wskazać, że klocek nie opiera się na drugim) tylko przy tej metodzie za każdym razem musisz sprawdzić wszystkie klocki już zrzucone to by było jakieś 4*N! porównań, innej poprawnej metody nie widzę (co nie znaczy, że jej nie ma )

 

tablica,lista od strony algorytmu to żadna różnica.

[jareqq 0]

ja mam takie pytanie - zrobilem krazki i dzialaja, tylko ze na zakresie maksymalnie 3000. jak wy to robicie??? skoro liczba krazkow i wysokosc rurki to max 300 000 to gdzie przechowujecie te dane?? przeciez trzeba stworzyc tablice ktora to przechowa a nie stworze tablicy 300 000 longintow...

[bRave 0]

ja mam takie pytanie - zrobilem krazki i dzialaja, tylko ze na zakresie maksymalnie 3000. jak wy to robicie??? skoro liczba krazkow i wysokosc rurki to max 300 000 to gdzie przechowujecie te dane?? przeciez trzeba stworzyc tablice ktora to przechowa a nie stworze tablicy 300 000 longintow...

 

A musisz to trzymać w tablicy? Nie wystarczy sekwencyjnie odczytywać z pliku? (było by trzeba trochę poskakać między dwoma wierszami)

[jareqq 0]

A musisz to trzymać w tablicy? Nie wystarczy sekwencyjnie odczytywać z pliku? (było by trzeba trochę poskakać między dwoma wierszami)

 

na OI nie wolno tworzyc i uzywac jakichkiolwiek plikow

[bRave 0]

na OI nie wolno tworzyc i uzywac jakichkiolwiek plikow

 

Ale odczytywać plik z danymi wejściowymi przecież możesz, nikt Ci nie każe robić tego za "jednym zamachem"

 

a, mozliwe, warunki moglyby byc oddzielane ;

to jak D jest <= 1k, to lacznie bedzie w najgorszym wypadku 40*10^9 operacji

 

zgadza się, ale nie widzę lepszej metody, chętnie usłyszę co wymyśliłeś (może być pm po zawodach żeby nikt nie zarzucał, że kradnę pomysły )

[kostek13_88 0]

a więc tak.... kompilatorek na oi pociągnie tablicę longintów do 1 000 000