Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

R4

 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Gość







PostWysłany: Czw 17:31, 09 Mar 2006    Temat postu: R4

mam banalne pytanie jak wzynaczacie to minimum ?

jak usuwacie elemnet zeby sie zmieniało minimum?
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
oinopion
żul



Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 17:49, 09 Mar 2006    Temat postu:

Zamiast stosu-jednej tablicy, robisz stos dwu-tablicowy: w jednej trzymasz info, czyli liczbę, a w drugiej trzymasz minimum dla tejże liczby.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 18:43, 09 Mar 2006    Temat postu:

a ja zrobiłem dwa stosy jednotablicowe... :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 20:51, 09 Mar 2006    Temat postu:

Najwydajniejszym i najspytniejszym rozwiazaniem jest zrobienie drugiego autonomicznego stosu i dodawanie do nigo INDEKSOW kolejnych najmniejszych elementow... Tzn jak wchodzi nowy element na maina to sprawdzamy czy jest mniejszy niz to na co wskazuje szczyt stosu MIN. Jesli tak to dodajemy ten indeks na MIN. Przy sciaganiu z maina analogicznie...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Czw 22:16, 09 Mar 2006    Temat postu:

Cytat:
dodawanie do nigo INDEKSOW kolejnych najmniejszych elementow

A po co? Tak czy siak musimy wpisywać longint'a, a dostajemy jedno dodatkowe odwołanie się do pamięci przy sprawdzaniu, czy nowy element jest mniejszy.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 22:20, 09 Mar 2006    Temat postu:

No ale wtedy musisz zapisywac na stos MIN kazda liczbe mniejsza lub rowna od aktualnego minimum. Bo jak masz wiecej minimalnych na stosie to jak zdejmujesz jeden taki to nie wiesz czy to jest ostatni czy nie... W pesypistycznym przypadku gdzy ktos Ci kaze zrobic milion razy PUSH 0 to moje jest duzo szybsze...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Pią 0:02, 10 Mar 2006    Temat postu:

Ok przemyślę to jeszcze jutro ;).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Pią 0:14, 10 Mar 2006    Temat postu:

hansu napisał:
W pesypistycznym przypadku gdzy ktos Ci kaze zrobic milion razy PUSH 0 to moje jest duzo szybsze...


Hmm... nie bardzo czaje co masz na mysli mówiąc "przypadek pesymistyczny". Ja na stosie MIN trzymam wartosci a nie indexy i jak na moj gust kazdy przypadek jest dla mnie tak samo pesymistyczny/optymistyczny. Ale za to nie da sie ukryc, ze gdy trzymamy indexy, tak jak ty robisz, to wtedy ten "pesymistyczny" przypadek jest dla ciebie bardzo "optymistyczny" :D.

A co do samego algorytmu to roznica jest jedynie taka ze twoj moze zuzywac lacznie liniowo mniej pamieci w stosunku do algorytmu ktory pamieta wartosci minimow a nie ich indexy.
A ze liczenie czasu dla przypadku optymistycznego, ktorego prawdopodobienstwo jest prawie zadne, mija sie raczej z celem to ogolnie te algorytmy w czasie dzialania nie roznia sie niczym (a tak nawiasem mowiac to nawet w przypadku optymistycznym twoje rozwiazanie jest szybsze jedynie o stala, a wiec nie tak znowu "znacznie"). A jak na moj gust to trzymanie na stosie wartosci tych minimow jest znacznie bardziej intuicyjne.... No ale juz jak kto woli :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
oinopion
żul



Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pią 0:17, 10 Mar 2006    Temat postu:

Najlepiej to zaimplementować na drzewie i minima pamiętać w liściech!
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Pią 1:30, 10 Mar 2006    Temat postu:

macie moze jakies testy do tego zadania? bo mi wywalilo ans :/
a jak sie okaze ze znowu zamiast in64 mialem gdzies longint to sie zezloszcze :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Pią 8:12, 10 Mar 2006    Temat postu:

zrób coś takiego:
1
6
PUSH 2
PUSH 1
PUSH 3
MIN
POP
MIN

Mi się na tym posypało i przy ostatnim MIN zwróciło 2 zamiast 1.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Gość







PostWysłany: Pią 10:36, 10 Mar 2006    Temat postu:

Makros napisał:
a ja zrobiłem dwa stosy jednotablicowe... :)

i gdzie porownywałes te elementy w procedurze push?????
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
szymku
pijak



Dołączył: 20 Lis 2005
Posty: 75
Przeczytał: 0 tematów

Skąd: Jasło

PostWysłany: Pon 23:38, 13 Mar 2006    Temat postu: TLE?!

Zrobiłem na jednym stosie gdzie typ stos to rekord z tablicą wartości tablicą minimalnych i topem i dostałem TLE, ma ktoś jakiś pomysł?? Albo sprytny przykład na zapętlanie ścierwa??
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Wto 0:04, 14 Mar 2006    Temat postu:

Nie musi byc zapetlenia. Czasy na R4 i R5 sa tak ustawione ze wystarczy napisanie nie calkiem optymalnego kodu i juz jest TLE :/ (vide moj przyklad z R5 gdzies w watku o tym walsnie zadaniu). Takze sugerowalbym poczynic daleko idaca optymalizacje (hehe, jak to sophisticated brzmi :P), wlaczajac w to przerobienie calej "mechaniki" na dwa osobne stosy... Chociaz nie wiem, ciezko mi cos powiedziec tak "zdalnie". Wez wrzuc mi kod na maila to oblookne w wolnej chwili.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Wto 1:26, 14 Mar 2006    Temat postu:

Zrobiłem na dwóch równoległych stosach(elementy i min) i zdziwko, bo mi sypnęło ANS. chwila rozkminki i nagle: "O k****, przecież liczby ujemne". Ucieszony submituję i co :?: , znowu ANS. Więc robię analyzing do ujemnych: minimalny Longint pięknie się wpisuje, -256 też, aż tu nagle wpisuję -10, a wczytuje mi -107. Bawię się, kombinuję i w końcu wkurzony zamieniłem
Kod:
while isDigit(tabela[i]) do
begin
   {wczytywanie i przemnażanie liczb}
end;

na takiego myka, że po zczytaniu linii polecenia, dopisuję na końcu 'a', a pętla wygląda:
Kod:
while tabela[i] <> 'a' do
begin
   {wczytywanie i przemnażanie liczb}
end;

No i poszło, chociaż powinno już dawno :?

PS
Jak ktoś mi powie, skąd się bierze ta siódemka to jest master of disaster :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
szymku
pijak



Dołączył: 20 Lis 2005
Posty: 75
Przeczytał: 0 tematów

Skąd: Jasło

PostWysłany: Wto 1:41, 14 Mar 2006    Temat postu: OK

mój problem z pomocą hansa pokonany, nie ładować PUSHów POPów MINów do stringów. Skrobot nie wiem, ale siódemki są magiczne... :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostojek
Gość






PostWysłany: Wto 2:50, 14 Mar 2006    Temat postu:

ostoj ladowal pushy popy miny do stringow, zrobil impelemtacje jednego stosu z rekordami i mu przeszlo
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Wto 4:47, 14 Mar 2006    Temat postu: Re: OK

szymku napisał:
mój problem z pomocą hansa pokonany, nie ładować PUSHów POPów MINów do stringów. Skrobot nie wiem, ale siódemki są magiczne... :wink:

Heh, to chyba jedyne wytłumaczenie, ale dobre :wink: , to jest fatuum niezaliczonego jeszcze zadania A
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 22:27, 14 Mar 2006    Temat postu:

Super cool mam ans :/ Ma ktos pomysl na jakies hardcorowe testy?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Wto 23:08, 14 Mar 2006    Temat postu:

Kod:

2
16
MIN
POP
PUSH 4
MIN
POP
PUSH 4
PUSH 8
PUSH 3
MIN
POP
MIN
POP
MIN
POP
MIN
POP
16
MIN
POP
PUSH 4
MIN
POP
PUSH 4
PUSH 8
PUSH 3
MIN
POP
MIN
POP
MIN
POP
MIN
POP

jest jest on moze jakos strasznie wyszukany ale jesli sie nie myle to sprawdza wszystko co trzeba oprocz wychodzenia poza zakres

u nas jedna osoba miala ANS bo uzywala i jako globala do liczenia ilosci zestawow a potem w funkcjach, przez to i sie zerowalo i robil tylko pierwszy zestaw
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 23:29, 14 Mar 2006    Temat postu:

Fidel, a mozna prosic o poprawne wyniki? Z gory dzieki.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Wto 23:57, 14 Mar 2006    Temat postu:

jasne myslalem ze sobie sprawdzisz :wink: ale w sumie racja - duzo tego

moj program takie cos generuje ( mam juz OK ):
Kod:

ERROR
ERROR
4
4
3
3
4
8
4
4
ERROR
ERROR
ERROR
ERROR
4
4
3
3
4
8
4
4
ERROR
ERROR



Edited: jesli ktos zdazyl sciagnac tamte to byly one zle - myslalem jakos ze to program R5 :P
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Strona 1 z 1

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin