Zadanie KLASTER - kto rozwiąże?

Odpowiedz Nowy wątek
2005-08-17 21:10
0

Oto treść zadania:
"Wszystkie komputery Bajlandzkiego Centrum Obliczeniowego połączone są szeregowo w sieć i podłączone do tego samego kabla koncentrycznego. W jednej cybernetycznej jednostce czasu komputer i może przesłać pakiet do komputera j (j<>i) pod warunkiem, że żaden z pozostałych komputerów o numerach należących do przedziału (i, j) lub (j, i) nie przesyła pakietów do innych komputerów.
Znając ilość komputerów oraz konieczne do przesłania pakiety, wyznacz minimalną ilość jednostek czasu potrzebnych do wykonania tego zadania.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oddzielone pojedyńczą spacją: liczbę m z zakresu 2..100000000, będącą ilością komputerów w sieci oraz liczbę n z zakresu 0..30000 równą ilości koniecznych do przesłania pakietów. W każdym z kolejnych n wierszy zapisano parę różnych liczb całkowitych z zakresu od 1..m, oddzielonych pojedyńczą spacją i będących numerami komputerów pomiędzy którym należy przesłać pakiet.

Wyjście
W pierwszym i jedynym wierszu powinna znajdować się jedna liczba całkowita, równa obliczonej minimalnej ilości cybernetycznych jednostek czasu, potrzebnych do przesłania wszystkich pakietów.

Przykład
Dla danych wejściowych:
8 4
1 4
4 8
2 3
5 6

poprawną odpowiedzią jest:
2"

Zadanie dostałem na informatyce, rozwiazalem je poprawnie (chyba:) ) ale algorytm troche wolny dla skrajnych danych, wiec licze ze ktos napisze szybszy i krótszy kod od mojego.


Pozostało 580 znaków

2005-08-17 21:31
0

Skoro to zadanie z OI to poszukaj w niebieskich książeczkach na www.oi.edu.pl

Pozostało 580 znaków

2005-08-18 11:40
0

Przeszukałem www.oi.edu.pl. Nic nie znalazlem. Qyon - skąd wiesz ze z OI zadanko?

Chodzi mi głównie o to, żeby ktoś wykazał, że istnieje inna złożoność niż kwadratowa (w przypadku OI to chyba standard).


Pozostało 580 znaków

2005-08-24 17:25
mystthg
0

Jakby złożoność kwadratowa była standardowa w OI to chyba nie mówimy o tej olimpiadzie. Jak sobie wyobrażasz złożoność kwadratową przy 2 miliardach danych (przykładowo)?
Standardowa to góra O(n log n)

Pozostało 580 znaków

2005-08-24 19:58
0
mystthg napisał(a)

Jakby złożoność kwadratowa była standardowa w OI to chyba nie mówimy o tej olimpiadzie. Jak sobie wyobrażasz złożoność kwadratową przy 2 miliardach danych (przykładowo)?
Standardowa to góra O(n log n)

Źle zrozumiałeś. Napisałem, że standardem jest, że zazwyczaj istnieje złożoność inna niż kwadratowa. Poza tym masz rację.


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0