Problem A - Bankowość
Problem B - Wiadomości sieciowe
Problem C - Łamanie szyfru
Problem D - Dekarze
Problem E - Części wspólne figur
Problem F - Szewc Olo
Problem G - Mikrokomputerowy sterownik wyłączników

 

 

 

1982

Problem B - Wiadomości sieciowe


Opis

Zbudowano pewną sieć komputerową, która łączy duże komputery w różych miastach. Nie wszystkie komputery są ze sobą połączone bezpośrednio, lecz każdy z nich może wysyłać wiadomość do każdego innego, przesyłając ją przez kilka komputerów pośrednich. Sieć jest trzewem, co oznacza, że istnieje dokładnie jedna ścieżka pomiędzy dwoma dowolnymi komputerami. Przykład takiej sieci jest pokazany poniżej:

 

 

Pożądane jest określenie sposobu przesyłu wiadomości od określonego komputera do wszystkich pozostałych w najmniejszym czasie. Przesłanie wiadomości z jednego komputera do drugiego zajmuje jedną jednostkę czasu, a danym czasie komputer może przesyłać wiadomość tylko do jednego z pozostałych. Podczas pierwszej jednostki czasu komputer źródłowy wiadomości może przesłać ją do jednego z sąsiednich komputerów. Podczas drugiej jednostki czasu zarówno nadawca wiadomości jak i ten sąsiad mogą przesłać tą wiadomość do kolejnych sąsiadów. W tym punkcie wiadomość została przeglądnięta przez przez co najwyżej cztery komputery. Podczas trzeciej jednostki czasu, każdy z nich może przesłać wiadomość do kolejnych sąsiadów, itd.

Ponieważ każdy komputer może posiadać kilku sąsiadów, wybór jednego z nich na odbiorcę wiadomości potrafi znacząco wpłynąć na całkowity czas przesłania wiadomości. Na przykład, na poniższych rysunkach numery na krawędziach oznaczają jednostkę czasu, w której ta gałąź przenosi wiadomość. Nadawcą wiadomości jest w każdym przypadku węzeł C, lecz na lewym rysunku wymagane jest 6 jednostek czasu, natomiast na prawym rysunku potrzebne są jedynie trzy jednostki.

 

 

Twój program powinien wykonać następujące operacje:

  1. Wczytać opis sieci wg reguł podanych poniżej.
  2. Wczytać węzeł wysyłający wiadomość.
  3. Określić optymalną kolejność wysyłania tej wiadomości. Wypisać tę kolejność, pokazując nadawcę i odbiorcę każdej transmisji w obrębie każdej jednostki czasu.

 

Specyfikacja wejścia

Sieć będzie reprezentowana przez następującą strukturę danych wejściowych:

 

W pierwszym wierszu będzie podana liczba n określająca ilość węzłów w sieci, 2 ≤ n ≤ 9.

W każdym z n kolejnych wierszy będą podane następujące elementy rozdzielone spacjami:

  • numer węzła - pojedyncza cyfra 2,3,...,9;
  • nazwa miasta, pojedynczy wyraz o długości do 13 znaków;
  • lista wierzchołków sąsiednich - pojedyncze cyfry rozdzielone spacjami. Na końcu listy jest cyfra 0.

 

Specyfikacja wyjścia

Dla każdej jednostki czasu należy wypisać słowo TIME, numer jednostki oraz pod spodem nazwy miast skojarzonych z węzłami wysyłającymi i odbierającymi wiadomość. Miasto wysyłające powinno być umieszczone najpierw, następnie słowo TO (ang. do) i miasto odbierające wiadomość:

 

Przykładowe dane wejściowe

7
1 A 3 0
2 B 3 0
3 C 1 2 4 0
4 D 3 5 6 0
5 E 4 0
6 F 4 7 0
7 G 6 0
3

 

Przykładowe dane wyjściowe

TIME 1
C             TO D

TIME 2
C             TO B
D             TO F

TIME 3
C             TO A
D             TO E
F             TO G

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.