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 

Zadanie L - Smok
Idź do strony 1, 2  Następny
 
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ść
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Czw 8:31, 09 Lis 2006    Temat postu: Zadanie L - Smok

[link widoczny dla zalogowanych]

Heh, zadanie z ubiegłorocznego AMPPZeta ;) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kafex
zielony żul



Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów

Skąd: Zawiercie

PostWysłany: Czw 9:59, 09 Lis 2006    Temat postu:

Jak dla mnie treść ownz :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Azhag
pijak



Dołączył: 16 Paź 2006
Posty: 33
Przeczytał: 0 tematów


PostWysłany: Czw 13:34, 09 Lis 2006    Temat postu:

Cytat:
Dla danych wejściowych:
1
5 1 10 3 10 1
Poprawną odpowiedzią jest:
20


dlaczego tylko 20 ?

1: 5 1 10 3 10 1 - zjadamy 10 od prawej
2: 4 0 9 2 - zjadamy 4 od lwej
3: 8 1 - zjadamy 8

zjedlismy 22 owce.

1: 5 1 10 3 10 1 - zjadamy 5 od lewj.
2: 0 9 2 9 0 - zjadamy 9
3: 8 1 - zjadamy 8

zjedlismy 22 owce.
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: Czw 13:48, 09 Lis 2006    Temat postu:

5 to liczba pastwisk, czyli mamy: 1 10 3 10 1
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: Czw 18:44, 09 Lis 2006    Temat postu:

Czytamy opis inputa ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



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

Skąd: Gościeradów

PostWysłany: Czw 20:41, 09 Lis 2006    Temat postu:

Obciągamy opis inputa... :lol:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Czw 21:12, 09 Lis 2006    Temat postu:

Z własnego doświadczenia mogę powiedzieć, że WARTO czytać treść zadania przynajmniej 2 razy :wink:

edited: A specyfikację wejścia i wyjścia to i z 5 razy się czasami przyda :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Czw 22:51, 09 Lis 2006    Temat postu:

czy mi sie wydaje, czy wynik moze przekroczyc wartosc longa? :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Czw 22:53, 09 Lis 2006    Temat postu:

Może nie zmieścić się w 4 bajtach.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
cct
pijak



Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów


PostWysłany: Pią 5:05, 10 Lis 2006    Temat postu:

I kolejna [link widoczny dla zalogowanych] :D

Przechodzi n*log(n).

Wynik trzymać w long longu, wypisywać najlepiej przez strumien z <iostream>.

BTW śliczny, króciutki algos - liczy... 1 (słownie: jedną) linijkę :D
(No, przygotowanie danych liczy trochę więcej, ale można je w całości przekopiować z paru innych zadań z ASD1/2).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Roxel
pijak



Dołączył: 06 Kwi 2006
Posty: 249
Przeczytał: 0 tematów

Skąd: Pszczyna

PostWysłany: Pią 7:30, 10 Lis 2006    Temat postu:

cct napisał:
wypisywać najlepiej przez strumien z <iostream>

ja napisalem
Kod:
printf("%lld\n", answer);
i tez dziala :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pią 8:01, 10 Lis 2006    Temat postu:

Widać nie postarali się z ograniczeniami czasowymi, skoro przechodzi nie dość, że nlogn (pół biedy, często się zdarza), to jeszcze na strumieniach (raczej się nie zdarza :P ). Ja tam mam liniówkę i printfa ;) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
cct
pijak



Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów


PostWysłany: Pią 8:57, 10 Lis 2006    Temat postu:

Spectro napisał:
Widać nie postarali się z ograniczeniami czasowymi, skoro przechodzi nie dość, że nlogn (pół biedy, często się zdarza), to jeszcze na strumieniach (raczej się nie zdarza :P ). Ja tam mam liniówkę i printfa ;) .


Fuck, chyba wreszcie dotarło do mnie jak zrobić tę liniówkę, i to faktycznie w 4MB pamięci... Ale to potestuje dopiero jak wrócę z Instytutu dzisiaj.

A na strumieniach jednoliczbowe wyniki nie widzę czemu miałyby nie przejść, zwł. na tyle duże, że do lla wchodzące. Znam dużo wolniejszych rzeczy które można zrobić a w innych zadaniach przechodzą.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pią 9:59, 10 Lis 2006    Temat postu:

ufff... już myślałem, że mam zły algorytm... a tu się okazało, że zamiast printf("%ld", result) wystarczyło napisać printf("%lld", result)...

dzięki za info o tym problemie! :)
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: Pią 14:48, 10 Lis 2006    Temat postu:

lol.... :d pamietajcie zerowac wynik pomiedzy zestawami ;p ;p ;p
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pią 15:28, 10 Lis 2006    Temat postu:

cct napisał:
A na strumieniach jednoliczbowe wyniki nie widzę czemu miałyby nie przejść, zwł. na tyle duże, że do lla wchodzące.

XI Olimpiada Informatyczna, I etap, zadanie Szpiedzy. Ludzie zamiast 100 punktów początkowo dostawali 30, bo robili operacje wejścia/wyjścia na strumieniach - na szczęście ostatecznie porobiono przekierowania do cstdio, więc te setki ostatecznie zostały przyznane osobom, które na nie zasługiwały :P . Na podstawie Twojej wypowiedzi wnioskuję, że jedynie wypisywałeś wyniki strumieniami, ale dla dużej ilości zestawów danych i dla małych testów w zestawach taki program raczej powinien normalnie dawać TLE. Jest to co prawda tylko moje przypuszczenie (wymagające testów, na które aktualnie czasu nie mam), ale poparte spostrzeżeniem, jakie uczyniłem przy limitach czasowych dla zadania J i F oraz po analizie niektórych rozwiązań, które spokojnie mogłyby przekroczyć czas przeznaczony na wykonanie algorytmu.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
r4ku
żul



Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów

Skąd: klikash? :D

PostWysłany: Pią 16:22, 10 Lis 2006    Temat postu:

@spectro: ale rozwiazanie liniowe dla malych zestawow z duzymi danymi wejsciowymi ma kosmiczna stala :) ja wybralem wersje z qwiksortem a nie ze zliczaniem (tez ze wzgledu na technike copy&paste w/wym algorytmie:P ) a odnosnie strumieni to od wersji g++ 3.4 istnieje taki myk ze po wylaczeniu synchronizacji:
Kod:
ios_base::sync_with_stdio(0);

strumienie przestaja byc problemem
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pią 17:51, 10 Lis 2006    Temat postu:

@r4ku:
Też prawda, zapomniałem o możliwości włączenia synchronizacji poprzez wymienioną linijkę ;) . Co do sortowania, to zakresy wielkości danych sugerowały countingsorta :) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
cct
pijak



Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów


PostWysłany: Sob 0:27, 11 Lis 2006    Temat postu:

Spectro napisał:
@r4ku:
Też prawda, zapomniałem o możliwości włączenia synchronizacji poprzez wymienioną linijkę ;) . Co do sortowania, to zakresy wielkości danych sugerowały countingsorta :) .


W sumie można samego countinga zrobić, ale dalej - to będzie Th( 1000000 ), czyli liniówka, ale zawsze od górnego ograniczenia. Od ~200000 wzwyż opłacalna, ale jednak fajnie byłoby coś liniowego od rozmiaru danych.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Crow
alkoholik



Dołączył: 14 Mar 2006
Posty: 497
Przeczytał: 0 tematów

Skąd: KRK-NH

PostWysłany: Sob 10:58, 11 Lis 2006    Temat postu:

Ja mysle ze to zadanie mozna zrobic w czasie stalym... np. O(10^32) :]
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: Sob 15:31, 11 Lis 2006    Temat postu:

[link widoczny dla zalogowanych] - zestawy, na których było testowane to zadanie rok temu. BTW wzorcówkę mieli wtedy kwadratową ;].
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
cct
pijak



Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów


PostWysłany: Sob 21:20, 11 Lis 2006    Temat postu:

Crow napisał:
Ja mysle ze to zadanie mozna zrobic w czasie stalym... np. O(10^32) :]


Bez przesady Crow - w złożoności asymptotycznej ważne jest wybranie argumentu dla niej. A maksymalny zakres wartości i liczba elementow to dwie różne bajki.
(Na przykład tutaj zakres wartości jest nie większy niż maksymalna liczba elementów, ale w praktyce zawsze większy lub równy liczbie elementów, czyli jest liniowy od zakresu).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kafex
zielony żul



Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów

Skąd: Zawiercie

PostWysłany: Sob 21:54, 11 Lis 2006    Temat postu:

Z tego co mi się wydaje to był dżołk ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
cct
pijak



Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów


PostWysłany: Sob 21:58, 11 Lis 2006    Temat postu:

kafex napisał:
Z tego co mi się wydaje to był dżołk ;]


Słusznie Ci się wydaje.

To był dżołk którym Crow chciał nam dać do zrozumienia, że można sobie wpisać co się chce jak się uprze w notacje, a z czym się do końca zgadzam w tym przypadku :)

EDIT@Madras: spadaj, spadaj ;)


Ostatnio zmieniony przez cct dnia Sob 22:44, 11 Lis 2006, w całości zmieniany 1 raz
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: Sob 22:29, 11 Lis 2006    Temat postu:

Ja także się zgadzam zgadzam.
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)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
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