Informatyka UJ forum

Skrobocik

Jak coś, to kolejna binarka do testowania: [link widoczny dla zalogowanych] plik N.exe

Kurczę, implementacja tego jest prościutka jak już się załapie, ale i tak złapałem jedno RTE :?

Jeszcze mam pytanko do Rogalika: jak to zrobiłeś, że Twoja binarka zajmuje tylko 17,5k moja aż 465,3k. Czy to jakieś opcje kompilacji, czy inne kosmosy :?:

hansu

Rogal

paladin

Skrobocik

kg86

dzieki rogal :) dzieki Twojej binarce znalazlem blad - troche nie poprawnie zerowalem jedna tablice ;) jednak moj algorytm byl poprawny :D :D :D

Spectro

Heh, też dzięki za binarkę - myliłem numery indeksów z wartościami tablicy dla B. Oczywiście ani test próbny, ani moje własne nie wykryły nieprawidłowości w działaniu programu ;] .

Używajcie build_heapa, zamiast inserta - mi pomogło z TLE (pierwszy u mnie komunikat inny niż OK czy ANS z ASD2).

Fidel

Skrobocik

Spectro

build_heap jest liniowy, a n insertów to nlogn :P . Przesiewanie w górę? Ja miałem cały czas przesiewanie w dół ;] .

No, miałem jeszcze błąd z za małą tablicą, ale to by raczej ANS wyskoczył, a nie TLE ;) .

Fidel

Spectro

Fidel

Skrobocik

Fidel

ale w drugim przypadku masz mniejsza zlozonosc bo downHeapow robisz nie n tylko chyba n/2 albo jakos tak :}

Spectro

Tak, n/2 downheapów, do tego jeszcze amortyzuje się ;) . Biorąc pod uwagę limity czasowe w tym zadaniu, każde udoskonalenie na redukcję stałej może okazać się kluczowe.

hansu

Zgodze sie ze Spectrem - dostalem TLE mimo ze moje rozwiazanie bylo zlozonosciowo dobre, po czym zmienilem konstrukcje kopca, odarlem go z calej obiektowosci, wywalilem operatory inline i przeszlo. Jednym slowem w tym zadaniu trzeba uwazac na stala...

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

hansu

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

Prezioso

Przybliżyłby ktoś ideę algorytmu?? Tak trochę przynajmniej :)

Fidel

mowisz masz.

tak w skrocie to zadanie polega na napisaniu kopca min ;) a nie w skrocie:

pierwsze ulatwienie, to zauwazenie ze mozna najpierw policzyc czasy przetwarzania dla maszyn A a dopiero potem dla maszyn B tylko obliczanie dla A odbywa sie od 1..n a dla B n..1

idea przetwarzania polega na tym aby kolejne elementy wkladac do maszyn ktore najwczesniej skoncza prace. czyli na przyklad mamy maszyny o szybkosciach 2 3 6 wtedy dla kolejnych elementow uzyjemy maszyn 1 2 1 1 2 3

dlaczego? bo przetwarzajac pierwszy element pierwsza maszyna dostaniemy gotowy po czasie 2 wtedy drugi mozemy przetworzyc druga maszyna i dostaniemy go po czasie 3 ale nastepny najlepiej przetworzyc znowu pierwsza maszyna bo dostaniemy go po czasie 4 (2 na pierwszy drugie 2 na trzeci element) itd itd

a jak to zrobic algorytmicznie? tworzymy sobie kopiec dla maszyn w ktorym wartosciami beda czasy skonczenia pracy
dla maszyn ktore podalem wczesniej to bedzie 2 3 6

teraz przetwarzajac element oprocz wyliczenia czasu przetworzenia danego elementu w tablicy wynikow uaktualniamy kopiec czyli szczyt kopca zwiekszamy o szybkosc dzialania maszyny ktora jest na szczycie i przesiewamy kopiec w dol zeby zachowac warunek kopca min

czyli w tamtym przykladzie uzywamy kopca pierwszego i uaktualniamy kopiec, co daje 3 4 6 po drugim 4 6 6 po trzecim 6 6 6 itd

gdy obliczymy cala tablice wynikow przetworzenia dla maszyn A liczymy juz na tej tablicy tylko od tylu kopcem B i uaktualniamy wyniki, jak nie trudno sie domyslic wynikiem dla zestawu jest element maksymalny naszej tablicy wynikow

nie czytalem tego co napisalem, mam nadzieje ze da sie to zrozumiec ;)

Fen

dzienki Fidel

na pewno pomoc się przyda

Prezioso

dzendras

to znaczy, że gdy przy maszynach typu A, rozważałeś elementy(półprodukty) od 1 do n, to dla kopca B bierzesz kolejne elementy od n do 1.