Informatyka UJ forum

Spectro

[link widoczny dla zalogowanych]

Ech, zbiory rozłączne...

dzendras

Kiedyś my będziemy Sprite...

Spectro

Ok, przepchnąłem to wreszcie. Moja intuicja okazała się błędna - chodziło w tym zadaniu tylko o Floyda-Warshalla ;) . Uwaga na stałą: poprawny algorytm ma złożoność p*p*(p+s), ale trzeba trochę pooptymalizować (przez co zarobiłem gwiazdkę ;]). Trzymałem zestaw bitowy reprezentujący wiersz macierzy sąsiedztwa w longintach (32 informacje w jednym). To bardzo pomogło przy redukowaniu stałej (da się zredukować właśnie o wielkość longinta).

Kurczę, dobrze że z Żenczykiem dzisiaj omówiliśmy na ćwiczeniach operacje bitowe przy wczytywaniu i wypisywaniu... jeden problem był z głowy ;) .

kg86

nie wszyscy maja z Zenczykiem, takze na pewnu wielu by sie ucieszylo, gdybys je opisal ;)
a tak btw. jesli startujac z przekaznika np. nr 1, dotre do przekaznika nr 1, to tez powinienem go wliczac w ilosc przekaznikow do jakich dotarlem? :)

Makros

jak dla mnie tak... należy go liczyć... :)

Madras

Tak wynika z przykładu.

kg86

pospieszylem sie troche z postem... nie zauwazylem tego w przykladzie... na szczescie mam to za soba, strasznie nieprzyjemne to zadanie... szczegolnie operacje na bitach... ale zamiast na longIncie operowalem na longWordzie :)

Robson

O zesz ich w morde kopaną znowu dali takie poronione limity czasów! Chciałem ładnie napisać i wszystko sobie sproceduralizowałem ładnie i pieknie, puszczam, queued chyba z 5 minut, no i TLE :evil:
Mozna sie wkurzyc nieziemsko. Teraz troszke zoptymalizowałem... zobaczymy co powie ta krowa Athina...

edited:
Nie wie ktoś jak zrobic te operacje na bitach w taki sposob zeby to cholerstwo przeszło?

edited:
to był zdecydowanie zły pomysł zabierać sie za to zadanie o 1.30 w nocy :/ . 2 godziny zajęło mi zauważenie ze mozna aktualizować pola paczkami po 32 bity :/ ... chyba sie starzeję..

r4ku

przeszedlem samego siebie, stracilem 6 h i 8 bomb na tym gownianym zadaniu bo zle policzylem rozmiar macierzy:/ zamiast liczby kolumn 8000/32 policzylem sobie 6000/32. a co ciekawe athina wypluwala ans zamiast s11 wiec myslalem ze mam blad w algorytmie:/

Spectro

Fen

przeczytałem uwagi zamieszczone powyżej postarałem się starannie zaimplementować ten algorytm... niestety jedna gwiazdka i tak mnie dopadła ;/
Dostałem ANS... już sobie myślę, że coś źle napisałem, że może algorytm coś jest nie tak... ale patrzę do kodu i okazało się, że na przykład nie usunąłem sobie wywołań funkcji pomocnych do debugu :)
Ale za głupotę trzeba płacić :)

co do samego algorytmu to najpierw napisałem sobie "zwyczajną" wersję, w której była tablica 2D booleanów a później dodałem operacje bitowe i tablicę zmieniłem na DWord'y i jak widać poszło :)

Madras

Do debugu polecam dyrektywy kompilatora {$DEFINE DEBUG}, {$IFDEF DEBUG}, {$ENDIF}. Wystarczy wykomentować tą pierwszą, a funkcje degugujące wstawiać między tą drugą a trzecią dyrektywą. Ewentualnie można zadeklarować stałą boolowską i pisać if debug then ..., ale to dla tych, którym fakt wykonywania zbędnych porównań nie przeszkadza ;].

Rogal

Wciąż nie mogę w to uwierzyć, ale jest to moje pierwsze zadanie bez bombki (nie licząć kilku rozgrzewkowych). Jestem z siebie dumny 8)

Makros

Hmmm...?!?!? a co z D :P

Fen

chlebek

Czy mogłby ktoś napisać jak za pomoca W-F znalezc ta liczbe przkaznikow i odbiornikow dla danego x, bo jakos nie mam pomyslu, czy trzeba stosowac rekurencje, czy da sie jakos prosciej, dzieki wielkie za pomoc i opisanie dzialania, to juz OSTATNIE marudzenie w tym semestrze :)

Source

Ja mam takie pytanie: Czy my mamy w tym zadaniu wczytaj wszystkie pytania a nastepnie dopiero q linii odpowiedzi, czy to ma wygladac w trybie: pytanie i odpowiedz od razu ?
Btw moze ktos dobry umiescilby do tego testy jakies ? :wink:

EDIT: No i jeszcze jedno male pytanko ... Jak wyglada sprawa jesli informacja dojdzie do goscia z jego wlasnego urzadzenia i tylko z niego (czyli w i-tym wierszu na i-tym miejscu jest 1). Mam go wtedy liczyć czy nie ?

Madras

Source

Madras: nie powiedziałbym że tak wynika z przykładu, bo żaden z tych gości nie wysyła informacji bezpośrednio do siebie(a mi właśnie o to chodziło).
Np jaka powinna być odpowiedz na dane:
1
3 3
100000
000000
000000
1
1
?

Spectro

@chlebek:
Niech bit o wartości 1 oznacza, że na przecięciu i-tego wiersza oraz j-tej kolumny istnieje połączenie z i-tego przekaźnika do j-tego przekaźnika/odbiornika. 0 w przeciwnym wypadku. Używamy W-F, aby ustalić dla których j istnieje połączenie z i-tego przekaźnika. Mamy dane wstępnie tylko połączenia bezpośrednie. Stosujemy odpowiednie operatory logiczne np. dodawanie zastępujemy orem. Potem już wystarczy tylko sumować jedynki w wierszach, aby dostać to, o co chodzi w zadaniu ;) .

@Source:
Radzę uważniej przeczytać treść zadania. Oczywiście wynikiem jest 1 0.

chlebek

ok rozumiem, dzieki Spectro.

Source

Hehe jak zwykle macie racje :wink:
Dzięki za pomoc, sory za głupie pytania. Całe szczęście mam to zadanie za sobą. Ale miałem całą plejadę błędów: ANS, TLE, S11, RD8. W zasadzie wszystkie z czego innego :D

gochapod · [świeżak] Dołączył: 02 Mar 2006 Posty: 13 Przeczytał: 0 tematów

hej ma ktos do tego jakies testy??

Krisowski

Kurde, już trzecie TLE dostałem :x . Ma ktoś pomysł co z tym zrobić?? Wszystkie mody i divy zamieniłem na shr i and, program mi się raczej nie pętli (choć pewności nie mogę mieć), buffering też załączyłem :/ . Czy to, że wczytywanie, getbit i floyda-warshalla mam w osobnych procedurach może mieć znaczenie??

Robson

A we W-F-ie ( ;) ) łączysz paczkami, czy po bicie?