Zadanie c0

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 =< 2²⁰
• 1 =< z =< 2³¹
• 0 =< s[x],s[y] =< 2⁶³

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:

7 1 2 2

Analiza przykładu: