Zadania należy wysyłać za pomocą panelu,
zgodnie z zamieszczonymi tam wytycznymi.
Grzegorz Wierzowiecki 2011
C0 - BZP - Bank Z
Priorytetami
Dostępna
pamięć: 100MiB
Historia
Bank Z Priorytetami (BZP) ma motto: Nasze dobre
interesy, to dobre interesy naszych klientów.
Im lepsze Bank osiąga wyniki, tym większy procent od zysków dostają klienci.
Tak, więc i oni doskonale rozumieją tę zasadę.
Jak najszybsza obsługa klientów obracających największym kapitałem, leży w
interesie wszystkich.
Jeżeli zniecierpliwieni, odeszliby do innego banku, wtedy Bank, a co za tym
idzie, klienci - straciliby procenty płynące z obrotów gotówką tegoż klienta.
Z tego płynie następująca zasada BZP: Bądź pewien, iż zostaniesz
obsłużony w pierwszej kolejności, przed klientami mającymi mniej na koncie.
Zarząd po latach sukcesywnego stosowania owej zasady zapragnął posiąść
symulator działania oddziału banku by móc dokonać symulacji różnych
scenariuszy zleceń.
Problem
Zbuduj symulator oddziału banku BZP.
Oddział banku ma k punktów obsługi klienta (pok), numerowanych
0,1,...,k-1.
Każdy punkt obsługi klienta ma oddzielną kolejkę (,gdyż mieści się na
oddzielnym piętrze).
Klient, wchodząc skanuje kartę z numerem konta x.
Dostaje wydruk z numerem p punktu obsługi klienta (pok), do którego
ma się udać:
p = x
mod k
(reszta z dzielenia numeru konta przez ilość punktów obsługi klienta).
W danym punkcie obsługi klienta (pok) klienci są obsługiwani zgodnie z
ilością środków na koncie - w pierwszej kolejności, klienci z większym
kapitałem (ku radości tych z mniejszym, bo bank
więcej dzięki nim zarobi, więc i oni otrzymają większy procent).
W przypadku, kiedy dwie osoby mają tę samą ilość środków na koncie,
pierwszeństwo mają klienci o mniejszym numerze konta - jako, iż są klientami
o dłuższym stażu.
Klient o numerze konta x składa jedno zlecenie przelewu składające
się z
- numeru konta
docelowego y
- kwoty do przelania z.
Jeżeli
dany klient posiada odpowiednią ilość środków na koncie s[x] , czyli
z=<s[x], to przelew zostaje zrealizowany; w przeciwnym
przypadku, zostaje odrzucony (stan kont się nie zmienia, klient idzie do
domu).
Jeżeli przelew został zrealizowany, zmienia to odpowiednio stan kont:
- s[x] = s[x] - z
- s[y] = s[y] + z
Co
wpływa na kolejność obsługi klientów. Tak, więc może się okazać, że klient o
koncie y stał na końcu kolejki, a po wykonaniu owego przelewu, nagle
znajdzie się na początku.
Co więcej, ktoś mający z początku 0 środków na koncie, może - w momencie,
kiedy będzie obsługiwany - mieć, ich odpowiednią ilość. (To
kolejny plus obsługi, klientów o większej ilości środków w pierwszej
kolejności.)
Obecnie oprogramowanie BZP wykonuje jedną transakcję w danym
momencie, cyklicznie dla danych punktów obsługi klienta (pok).
Przykładowo:
Dla oddziału o k=3, pok-ach : p0,p1,p2.
Kolejkach p0={a,b,c}, p1={}, p2={d}
Stanach konta:
s[a]=100
s[b]=10
s[c]=1
s[d]=1
Zostaną obsłużeni :
* p0: a (gdyż ma najwięcej środków w p0)
* p1: ∅ (nikt, bo kolejka jest pusta)
* p2: d (gdyż ma najwięcej środków w p2)
* p0: b lub c (w zależności od zleceń a,d - tzn. czy stan kont b,c jest nadal s[b]>s[c], czy zmienił się na s[c]>s[b])
* p1: ∅ (nikt, bo kolejka jest pusta)
* p2: ∅ (nikt, bo kolejka jest pusta)
* p0: ostatni w kolejce (b lub c)
- 0 =< n
=< 1'000'000 (ilość osób do obsłużenia w danej symulacji)
- 0 =< x,y
=< n
- 1 =< k
=< 220
- 1 =< z
=< 231
- 0 =< s[x],s[y]
=< 263
Struktura danych
Zalecenia:
- użycie kopca
binarnego do każdego (pok) (albo innej kolejki
priorytetowej o odpowiedniej złożoności obliczeniowej)
- w implementacji
tablicowej (dane trzymane w ciągłej tablicy o rozmiarze nie
wymagającym realokacji w trakcie działania programu)
- wzbogaconego o
operację: Update(numer_konta, kwota_wpływająca_na_konto)
- Do efektywnej
implementacji Update trzymać w oddzielnej tablicy (dla każdego
kopca) informację, gdzie dany numer_kopca w danym momencie się
znajduje (a ją aktualizować przy każdej operacji swap)
- trzymanie w kopcach
numerów kont, a informacje o środkach w oddzielnej tablicy
- budowanie struktury
danych stopniowo. Wpierw same operacje down-heap, up-heap. Jak działają
to build-heap, update (a.k.a decrease-key). I dopiero jak mamy
działający kopiec, próbować go użyć do rozwiązania zadania.
(W obserwowaniu zachowania kopca i wyrobieniu intuicji,
zawsze zalecam ćwiczenia na stole, z wyciętymi kartkami z numerami z
ewentualnym porównywaniem z narzędziami wizualizacji algorytm-ów, takimi jak
np. TRAKLA2 (hasło "heap") - jednak obserwacja
wizualizacji bez własnych ćwiczeń to za mało)
Wejście (format
wejścia)
W pierwszym wierszu dwie liczby:
- n - ilość osób w
oddziale banku na początku symulacji
- k - ilość pok (punktów
obsługi klienta) w symulowanym oddziale
W
kolejnych n wierszach, mamy opisy dotyczące, kolejno wchodzących
osób.
W i-tym wierszu, mamy opis dotyczący osoby o numerze konta x=i-2
(kolejno
dla x=0,1,2,...,n-1):
- s[x] - ilość środków na
koncie
- y - numer konta
docelowego
- z - kwotę przelewu na
konto y
(Liczby - standardowo - są całkowite, oddzielone
pojedynczą spacją; ostatni wiersz zakończony znakiem nowej linii)
Wyjście (format
wyjścia)
Jeden wiersz z podsumowaniem danej symulacji, w postaci czterech liczb
całkowitych oddzielonych pojedynczymi spacjami (a
wiersz zakończony znakiem nowej linii):
- α - ilość
zrealizowanych przelewów
- β - ilość przelewów
odrzuconych
- γ - ilość klientów,
których miejsce w kolejce (w pewnym momencie) uległo zmianie na
lepsze
- δ - sumaryczna ilość
zmian miejsc na lepsze w kolejkach
Zwróćmy uwagę, iż nie każdy zrealizowany
przelew wpływa na wartość γ, nawet jeżeli dotyczy osoby jeszcze stojącej w
kolejce.
Przykład:
Wejście:
8 2
10 5 4
10 7 1
10 7 1
10 6 10
8 7 14
8 4 2
10 7 20
8 4 25
Wyjście:
Analiza przykładu:
Operacja
z
x do y, kwota z
|
Stan przed wykonaniem
danej operacji
|
p
|
x
|
y
|
z
|
p0
|
p1
|
s[0]
|
s[1]
|
s[2]
|
s[3]
|
s[4]
|
s[5]
|
s[6]
|
s[7]
|
α
|
β
|
γ
|
δ
|
p0
|
0
|
5
|
4
|
0,2,6,4
|
1,3,5,7
|
10
|
10
|
10
|
10
|
8
|
8
|
10
|
8
|
0
|
0
|
0
|
0
|
p1
|
5
|
4
|
2
|
2,6,4
|
5,1,3,7
|
|
10
|
10
|
10
|
8
|
12
|
10
|
8
|
1
|
0
|
1
|
1
|
p0
|
2
|
7
|
1
|
2,4,6
|
1,3,7
|
|
10
|
10
|
10
|
10
|
|
10
|
8
|
2
|
0
|
2
|
2
|
p1
|
1
|
7
|
1
|
4,6
|
1,3,7
|
|
10
|
|
10
|
10
|
|
10
|
9
|
3
|
0
|
2
|
2
|
p0
|
4
|
7
|
14
|
4,6
|
3,7
|
|
|
|
10
|
10
|
|
10
|
10
|
4
|
0
|
2
|
2
|
p1
|
3
|
6
|
10
|
6
|
3,7
|
|
|
|
10
|
|
|
10
|
10
|
4
|
1
|
2
|
2
|
p0
|
6
|
7
|
20
|
6
|
7
|
|
|
|
|
|
|
20
|
10
|
5
|
1
|
2
|
2
|
p1
|
7
|
4
|
25
|
|
7
|
|
|
|
|
|
|
|
30
|
6
|
1
|
2
|
2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7
|
1
|
2
|
2
|