Informatyka UJ forum

Spectro

[link widoczny dla zalogowanych]

Heh, zadanie z ubiegłorocznego AMPPZeta ;) .

kafex

Jak dla mnie treść ownz :D

Azhag

jagm

5 to liczba pastwisk, czyli mamy: 1 10 3 10 1

Skrobocik

Czytamy opis inputa ;)

Yoter

Obciągamy opis inputa... :lol:

Rogal

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

kg86

czy mi sie wydaje, czy wynik moze przekroczyc wartosc longa? :)

Rogal

Może nie zmieścić się w 4 bajtach.

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

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).

Roxel

Spectro

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 ;) .

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

Fen

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! :)

Makros

lol.... :d pamietajcie zerowac wynik pomiedzy zestawami ;p ;p ;p

Spectro

r4ku

@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:

Spectro

@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 :) .

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

Crow

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

Madras

[link widoczny dla zalogowanych] - zestawy, na których było testowane to zadanie rok temu. BTW wzorcówkę mieli wtedy kwadratową ;].

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

kafex

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

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

Madras

Ja także się zgadzam zgadzam.