OI....

[mr262560 0]

hehe okresy są fajne narazie sie jeszcze gubie w danych powyżej 60znaków, i to musze na kartce liczyc i sprawdzac, ale reszta to juz pikus klika zależności trzeba znaleźć i masz n

 

a jak juz tak pomagamy, to sprawdz czy Ci sie średnice krążków zmieszczą w tablicy (longint chyba nie wytrzyma ) no i czy działa dla przypadków:

5 2

6 4 8 1 2

2 6

 

i

 

5 1

6 4 8 1 2

1

 

wyniki sobie policz na kartce

[letus 0]

a jak juz tak pomagamy, to sprawdz czy Ci sie średnice krążków zmieszczą w tablicy (longint chyba nie wytrzyma )

int spokojnie to wytrzyma bo ma zakres do ponad 2mld a w zadaniu jest mowa tylko o 1mld a jeśli byłaby już potrzeba użycia 64 bitowych zmiennych to zadaniu znalazłaby się odpowiednia adnotacja na ten temat, tak przynajmniej było na ostatnich MWPZ.

 

cholera nie mam dziś głowy do myślenia, od dobrych kilku godzin staram się i nie potrafie napisać O(n) do krążków

[januzi 24]

a ja jestem zbyt trzezwy, zeby zrozumiec zadanie z zabami

 

za to tetris 3d wydaje sie byc calkiem przyjemnym zadankiem, pierwsza mysl jest taka, zeby zrobic tablice nxm w ktorej bedzie podawana wysokosc na jaka w danym miejscu ustawily sie klocki

[letus 0]

a ja jestem zbyt trzezwy, zeby zrozumiec zadanie z zabami

 

za to tetris 3d wydaje sie byc calkiem przyjemnym zadankiem, pierwsza mysl jest taka, zeby zrobic tablice nxm w ktorej bedzie podawana wysokosc na jaka w danym miejscu ustawily sie klocki

też myślałem o takim sposobie tylko druga cześć jak doszukać się najwyższego punktu, może zliczać gdzieś po drodze, ale z tym to później najpierw krążki chce zrobić, próbowałem robić wyszukiwanie binarnm jak pisałem ale coś dużo "if'ów" mi się zrobiło i się pogubiłem

 

W szkole ostatnio dużo pisze w Aśmie dla '51 i AWL dla Siemens PLC i teraz mam spore trudności z C++

[januzi 24]

to rob o(n):

wyobraz sobie to cos jako tablice, pierwszy (czyli 0) indeks w tablicy to gora, potem ida kolejne segmenty, na koncu masz dno

co robimy ? ustawiamy indeks dna (ID) i od niego sprawdzamy w gore kiedy krazek sie zatrzyma, ustawiamy indeks tego miejsca (ID), bierzemy kolejny klocek i znowu jedziemy w gore (w tym przypadku nalezy pamietac ze kolejny klocek moze byc mniejszy), znowu zmieniamy indeks (ID) itd ... wychodzi o(n) porownan (wczesniej trzeba zauwazyc pewna rzecz zwiazana z rura, bez niej to rozwiazanie moze dawac nieprawidlowe wyniki)

[Stnkk 0]

To pierwsze zadanie nawet nie jest takie trudne, juz mam zrobione Dawniej jak chodzilem do liceum to te zadania byly trudniejsze ;/

[mr262560 0]

tylko to pierwsze takie banalne ;]

a co do tetrisa, to Januzi, Twoj algorytm bedzie miał złożność:

n*d*s

 

1<= n <=20000

1<= d <=1000

1<= s <=1000

 

~20 000 000 000

 

i to chyba troszke za duzo... na forum czytałem, ze n*n też jeszcze jest za duzo

 

~400 000 000

 

w sumie to tam jeszcze powinna być dwójka, bo najpierw trzeba znaleźć maksa na danym "terenie" a potem do całego terenu dodać wysokość; w sumie to wiem jak mocno przyspieszyć szukanie maksa, tylko nie wiem jak zrobić dodawanie...

 

 

int spokojnie to wytrzyma bo ma zakres do ponad 2mld a w zadaniu jest mowa tylko o 1mld a jeśli byłaby już potrzeba użycia 64 bitowych zmiennych to zadaniu znalazłaby się odpowiednia adnotacja na ten temat, tak przynajmniej było na ostatnich MWPZ.

sorry, faktycznie, moj błąd ;]

[kostek13_88 0]

hehe okresy są fajne narazie sie jeszcze gubie w danych powyżej 60znaków, i to musze na kartce liczyc i sprawdzac, ale reszta to juz pikus klika zależności trzeba znaleźć i masz n

 

a jak juz tak pomagamy, to sprawdz czy Ci sie średnice krążków zmieszczą w tablicy (longint chyba nie wytrzyma ) no i czy działa dla przypadków:

5 2

6 4 8 1 2

2 6

 

i

 

5 1

6 4 8 1 2

1

 

wyniki sobie policz na kartce

 

zwraca dla pierwszego 1 a dla drugiego 5.... co do longintów itp. najfajniejsze jest to że borlandc(w którym działam) 3.1 nie obsługuje nawet tablicy na 100 000...natomiast gcc na serwerze bez problemu kompiluje 1000 000

[mr262560 0]

heh, ja tam działam w FPC

[kostek13_88 0]

hmmm....może ktoś mi poleci jakiś kompilator pod windę bo próbowałem lcc-win32 i złe odpowiedzi zwraca po kompilacji, dev c++ zawiesza się po odpaleniu i minGW studio również zawiesza się po odpaleniu

[januzi 24]

jak sie zawiesza ? po odpaleniu Twojego programu ? jak tak, to wniosek od razu sie nasuwa oczywisty

[letus 0]

zwraca dla pierwszego 1 a dla drugiego 5.... co do longintów itp. najfajniejsze jest to że borlandc(w którym działam) 3.1 nie obsługuje nawet tablicy na 100 000...natomiast gcc na serwerze bez problemu kompiluje 1000 000

Dla mnie jesteś rzeźnik ja lubię tworzyć na Dev-C++ a na linux'ach wystarczy mi mcedit i gcc

[januzi 24]

druga przymiarka do tetrisa:

tab[x][y] += w ; ( o(n) )

potem przejrzec tab i pododawac w rzedach i kolumnach co trzeba ( o(D*S) )

 

Edit: hmmm ... jednak niebardzo, kolejnosc wrzucania jeszcze bedzie miala decydujace znaczenie, dwa klocki obok siebie a potem jeden na wierzch posrodku (piramidka) to cos innego niz: klocek, klocek posrodku, klocek z boku (schodki)

 

jak bede na bani to wymysle jeszcze lepsze

[kostek13_88 0]

odnośnie moich krążków... działa na serwerze więc mój wniosek różni się od Twojego Januzi

[mr262560 0]

kostek, a jakbym Ci podał algorytm na profesora, to mi przepiszesz na C++?? bo tak dzisiaj zacząłem, i mi wychodzi ze jakies 200 linijek bedzie, i mi sie nie chce pisać

[letus 0]

Żaby jak liczycie? Ja sprawdzam długości wektorów i porównuje je, tylko nie bardzo wiem jeszcze jak sprawdzić czy żaba może przejść z p do k (odstraszacze są tak rozłożone że żabsko nie przejdzie czyli jeden obok drugiego) ale chyba dojdę do tego bo już mi coś świta tylko przeliczyć czy wynik będzie poprawny.

 

@rojmarek skoro wcześniej zadanie napisałeś w pascalu to teraz dlaczego chcesz w c++?

[kostek13_88 0]

ja mam już sposób na profesora może jeszcze dzisiaj go przeleję na komputer.... ps. ja nie piszę w c++!!1 ja piszę w najzwyczjniejszym C tylko borland dopisał mi rozszerzenie cpp

[mr262560 0]

zaczalem pisac, tzn nie skonczylem ;]

a w zabach problemem (jak dla mnie) jest naniesienie miliona zabek na tablice, i dla kazdego pola obliczenie gdzie jest najblizsza zabka...

[letus 0]

Mój program do żabek dla testów dostępnych na stronie SOI w 3 zadaniach daje poprawne wyniki nie potrafie rozwiązać problemów zawartych w 3 pozostałych testach jeszcze, ale wciąż nad nimi wyśle.

[mr262560 0]

cholera, chcialem sobie dzis zabki napisac... i tak prawie ze napisałem, ale nie wziałem pod uwage tego ze zabka moze poruszac sie we wszystkich kierunkach... juz mam w tablicy wpisane odległości do najbliższego odstraszacza, ale nie mam pojecia jak zrobic tą ściezke, w jakims akceptowalnym czasie...

[Stnkk 0]

Heh powodzenia wam zycze ;]

[jackm 0]

.. juz mam w tablicy wpisane odległości do najbliższego odstraszacza

i masz to w czasie mniejszym niz o(wz*wy*liczba_odstraszaczy) ??

[mr262560 0]

i masz to w czasie mniejszym niz o(wz*wy*liczba_odstraszaczy) ??

dokładny czas pesymistyczny to 2*n*s+2*s*w=2s(n+w), gdzie n to ilosc odstraszaczy, w wysokość, s szerokość; moim zdaniem powinien sie wyrobić... ale w sumie to taka złożność osiągnie dla miliona-2 odstraszaczy i jeszcze ich kolejność musi być taka ze sie nie podoba algorytmowi... wiesz jak zrobic reszte?? jak tak to w jakim czasie?

[Stnkk 0]

zwraca dla pierwszego 1 a dla drugiego 5....

Zle masz

5 2
6 4 8 1 2
2 6

Racja dobrze

[Stnkk 0]

Jak sie tam zarejestrowac, wiem ze to nielegalne, ale chcialbym sprawdzic swoje rozwiazania Dobra juz mam ;]