usl, stud, I semsetr, WSTEP DO PROGRAMOWANIA, Liceum, zadania z programowania

[ Pobierz całość w formacie PDF ]
Zadanie: USL
Us“ugi kurierskie
Fina“, plik „r
ó
d“owy usl.*, dostƒpna pamiƒ¢ 32 MB
19 marca 2005
Firma SuperKurier oferuje dostarczanie przesy“ek w dowolny zak¡tek –wiata. Firma ma sie¢
n
plac
ó
wek ponumerowanych od 1 do
n
. W plac
ó
wkach nastƒpuje zbieranie przesy“ek z okre–lonego
obszaru, ich sortowanie, prze“adunek oraz dostarczanie odbiorcom. Pomiƒdzy plac
ó
wkami utrzymy-
wane s¡ sta“e po“¡czenia umo»liwiaj¡ce transport przesy“ek. Plac
ó
wki podzielone s¡ na klasy A,
B i C. W sieci znajduje siƒ
n
A
plac
ó
wek klasy A,
n
B
plac
ó
wek klasy B oraz
n
C
plac
ó
wek klasy C,
przy czym
n
A
+
n
B
+
n
C
=
n
,
n
A
>
0,
n
C
>
0. W plac
ó
wkach klasy A odbywa siƒ sortowanie
zasadnicze oraz prze“adunek przesy“ek. Ka»da przesy“ka na swej drodze od nadawcy do odbiorcy
musi przej–¢ przez co najmniej jedn¡ plac
ó
wkƒ klasy A. Plac
ó
wki klasy A maj¡ po“¡czenia ze wszys-
tkimi pozosta“ymi plac
ó
wkami klasy A oraz z pewn¡ liczb¡ plac
ó
wek klasy B i C. W plac
ó
wkach
klasy B odbywa siƒ sortowanie wt
ó
rne oraz prze“adunek przesy“ek. Ka»da plac
ó
wka klasy B ma
po“¡czenia z co najmniej jedn¡ plac
ó
wk¡ klasy A oraz z pewn¡ liczb¡ plac
ó
wek klasy C, nie ma nato-
miast po“¡cze« z innymi plac
ó
wkami klasy B. Zadaniem plac
ó
wek klasy C jest jedynie odbieranie
przesy“ek z okre–lonego obszaru i dostarczanie przesy“ek do odbiorc
ó
w na tym obszarze. Ka»da
plac
ó
wka klasy C ma tylko jedno po“¡czenie z plac
ó
wk¡ klasy A lub B. Poni»szy rysunek przedstawia
przyk“adow¡ sie¢ plac
ó
wek. Plac
ó
wkom oraz po“¡czeniom s¡ przyporz¡dkowane pary atrybut
ó
w
C
9
(3, 2)
B
7
(10, 15)
C
8
(1, 3)
(2, 2)
(3, 3)
(4, 4)
A
6
(23, 27)
C
5
(1, 1)
C
2
(2, 1)
(4, 3)
(1, 2)
(5, 1)
(2, 7)
B
(12, 13)
4
(3, 2)
(1, 1)
A
3
(20, 30)
C
1
(1, 2)
Rysunek 1: Przyk“adowa sie¢ plac
ó
wek.
(koszt, czas). Dla plac
ó
wek para ta wyznacza koszt oraz czas odebrania lub dorƒczenia przesy“ki na
obszarze obs“ugiwanym przez plac
ó
wkƒ, a tak»e sortowania i prze“adunku przesy“ek, w zale»no–ci od
klasy plac
ó
wki. Para atrybut
ó
w przypisana po“¡czeniu oznacza koszt i czas przewiezienia przesy“ki
pomiƒdzy plac
ó
wkami.
1
Zadanie polega na wyznaczeniu dla danej sieci najlepszych tras transportu przesy“ek z danej
plac
ó
wki pocz¡tkowej
s
, do danej plac
ó
wki docelowej
t
(plac
ó
wki
s
i
t
s¡ klasy C). Ka»da trasa
charakteryzuje siƒ par¡ atrybut
ó
w, kosztem oraz czasem transportu: s¡ to sumy koszt
ó
w i czas
ó
w,
plac
ó
wek i po“¡cze« znajduj¡cych siƒ na trasie (“¡cznie z
s
i
t
). Im mniejszy koszt i kr
ó
tszy czas
transportu, tym lepiej. Powiemy, »e jedna trasa jest lepsza od drugiej, je–li charakteryzuje siƒ:
²
mniejszym kosztem i nie d“u»szym czasem, lub
²
kr
ó
tszym czasem i nie wiƒkszym kosztem.
Interesuj¡ nas takie trasy, od kt
ó
rych nie ma lepszych.
Na przyk“ad, niech
s
=
C
1
oraz
t
=
C
2
(por. rysunek). Chc¡c wybra¢ najlepsze trasy transportu
przesy“ek pomiƒdzy tymi plac
ó
wkami rozwa»amy nastƒpuj¡ce trasy:
C
1
!B
4
!A
3
!B
4
!C
2
,
C
1
!B
4
!A
6
!B
4
!C
2
,
C
1
!B
4
!A
3
!A
6
!B
4
!C
2
oraz
C
1
!B
4
!A
6
!A
3
!
B
4
!C
2
o parach (koszt, czas) odpowiednio:(55
;
66),(60
;
65),(84
;
95)i(84
;
95). Pierwsze dwie
trasy s¡ lepsze ni» trzecia i czwarta. Tak wiƒc, mamy dwie trasy transportu przesy“ek, od kt
ó
rych
nie ma lepszych:
C
1
!B
4
!A
3
!B
4
!C
2
i
C
1
!B
4
!A
6
!B
4
!C
2
.
Zadanie
Napisz program, kt
ó
ry:
²
wczyta opis sieci plac
ó
wek oraz plac
ó
wkƒ pocz¡tkow¡
s
i docelow¡
t
,
²
wyznaczy wszystkie pary (koszt, czas) charakteryzuj¡ce te trasy transportu przesy“ek z
s
do
t
, od kt
ó
rych nie ma lepszych, przy czym je»eli co najmniej2r
ó
»ne trasy daj¡ tƒ sam¡ parƒ
(koszt, czas), to nale»y j¡ wypisa¢1raz,
²
wypisze wyznaczone pary.
Wej–cie
W pierwszym wierszu zapisane s¡ dwie dodatnie liczby ca“kowite oddzielone pojedynczym odstƒpem:
liczba plac
ó
wek
n
oraz liczba po“¡cze«
m
,2
·n·
1000,1
·m·
5000. Plac
ó
wki s¡ ponumerowane
od 1 do
n
. W kolejnych
n
wierszach opisane s¡ kolejne plac
ó
wki, po jednej w wierszu. Opis ka»dej
plac
ó
wki sk“ada siƒ z litery A, B lub C, oraz dw
ó
ch dodatnich liczb ca“kowitych
k
i
c
, pooddzielanych
pojedynczymi odstƒpami. Liczba
k
oznacza koszt, a
c
czas sortowania przesy“ek w plac
ó
wce,1
·
k·
20,1
·c·
20.
W kolejnych
m
wierszach opisane s¡ po“¡czenia miƒdzy plac
ó
wkami, po jednym w wierszu. Opis
ka»dego z po“¡cze« sk“ada siƒ z czterech liczb ca“kowitych
a
,
b
,
k
i
c
, pooddzielanych pojedynczymi
odstƒpami. Liczby
a
i
b
, to numery po“¡czonych plac
ó
wek,1
·a;b·n
. Liczba
k
to koszt, a
c
to
czas transportu przesy“ki danym po“¡czeniem,1
·k·
100,1
·c·
100. Wszystkie po“¡czenia
s¡ dwukierunkowe. Miƒdzy ka»dymi dwiema plac
ó
wkami mamy co najwy»ej jedno (bezpo–rednie)
po“¡czenie.
W ostatnim wierszu zapisane s¡ dwie dodatnie liczby ca“kowite
s
i
t
, oddzielone pojedynczym
odstƒpem,1
·s;t·n
. S¡ to numery plac
ó
wek pocz¡tkowej i docelowej.
2
Wyj–cie
W pierwszym wierszu powinna zosta¢ wypisana jedna dodatnia liczba ca“kowita
r
liczba r
ó
»nych
par (koszt, czas) charakteryzuj¡cych wszystkie trasy transportu przesy“ek z plac
ó
wki
s
do
t
, od
kt
ó
rych nie ma lepszych. W kolejnych
r
wierszach powinny by¢ wypisane te pary, w kolejno–ci
rosn¡cych koszt
ó
w. Ka»da para powinna by¢ wypisana w osobnym wierszu, a koszt i czas powinny
by¢ oddzielone pojedynczym odstƒpem.
Przyk“ad
Dla danych wej–ciowych:
9 9
C 1 2
C 2 1
A 20 30
B 12 13
C 1 1
A 23 27
B 10 15
C 1 3
C 3 2
1 4 1 1
2 4 1 2
3 4 3 2
5 3 2 7
3 6 5 1
6 4 4 3
6 7 4 4
7 8 3 3
7 9 2 2
1 2
poprawnym wynikiem jest:
2
55 66
60 65
3
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •