Zadanie KLASTER - kto rozwiąże?

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.

0

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

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

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)

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

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