Zadanie KLASTER - kto rozwiąże?

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

Rejestracja: 17 lat temu

Ostatnio: 14 lat temu

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

Rejestracja: 16 lat temu

Ostatnio: 2 lata temu

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

Rejestracja: 17 lat temu

Ostatnio: 14 lat temu

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

mystthg
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

Rejestracja: 17 lat temu

Ostatnio: 14 lat temu

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

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