SPOJ Problem Set (main)

4243. Filatelista

Problem code: ASD0809B

Jaś jest zapalonym filatelistą. Ponieważ jego kolekcja przekroczyła masę krytyczną i nie jest już w
stanie jej ogarnąć, prosi Cię o pomoc. Twoim zadaniem jest napisanie programu do zarządzania
kolekcją znaczków Jasia. Każdy rodzaj znaczka jest identyfikowany jednoznacznie przez jego numer
serii (ciąg dużych liter i cyfr). Jaś może mieć więcej niż jeden znaczek z danej serii (np. na wymianę).
Kolekcja nieustannie rozwija się. Jaś kupuje, sprzedaje i wymienia znaczki - program powinien zatem
umożliwiać te operacje. Od czasu do czasu chce też nacieszyć się stanem swojego posiadania, więc
program powinien umożliwiać wypisanie zawartości całej, lub części, kolekcji.

Wejście i wyjście

Na wejściu programu zostanie podany ciąg poleceń (każde w osobnej linii) o jednej z następujących
postaci:

KUP nrserii ile - oznacza zakup ile znaczków o numerze serii nrserii (należy je dodać do
kolekcji)
ILE nrserii - zapytanie o ilość znaczków o numerze serii nrserii w kolekcji; program powinien
wypisać jedną liczbę nieujemną (zero gdy nie ma ich w kolekcji) oraz znak nowej linii
SPRZEDAJ nrserii ile - oznacza sprzedaż ile znaczków o numerze serii nrserii (należy je usunąć
z kolekcji); gdy ile jest większe od liczby posiadanych przez Jasia znaczków danej serii należy
wypisać BLAD<nowa-linia>, nie usuwać niczego i kontynuować przetwarzanie poleceń
WYMIEN nrserii1 nrserii2 - oznacza zamianę jednego znaczka o numerze serii nrserii1 (ten
Jasio oddaje) na znaczek o numerze serii nrserii2 (ten Jasio dostaje); gdy Jasio nie posiada
znaczka o numerze serii nrserii1, należy wypisać BLAD<nowa-linia>, nie modyfikować
zawartości kolekcji i kontynuować przetwarzanie poleceń
WYPISZ - wypisanie kolekcji w formacie:
nrserii-1

ilość-1

nrserii-2

ilość-2

...
nrserii-n

ilość-n

gdzie nrserii-i to uporządkowane alfabetycznie numery serii znaczków zaś ilość-i to liczba
posiadanych przez Jasia znaczków o numerze serii nrserii-i (należy wypisać tylko te, które Jasio
posiada, więc nie może pojawić się linia zawierająca ilość <= 0
WYPISZTYLKO prefiks - wypisanie tej części kolekcji, która zawiera znaczki o numerach serii
zaczynających się od napisu prefiks w formacie:
nrserii-1

ilość-1

nrserii-2

ilość-2

...
nrserii-n

ilość-n

gdzie nrserii-i to uporządkowane alfabetycznie numery serii znaczków zaś ilość-i to liczba
posiadanych przez Jasia znaczków o numerze serii nrserii-i (należy wypisać tylko te, które Jasio
posiada, więc nie może pojawić się linia zawierająca ilość <= 0
DRZEWO - wypisanie drzewa czerwono-czarnego zawierającego kolekcję w formacie:

1

( spacja lewy-syn spacja kolor spacja nrserii spacja ilość spacja prawy-syn spacja ) gdzie nrserii
i ilość to zawartość węzła, kolor to kolor węzła (R gdy czerwone, B gdy czarne) zaś lewy-syn i
prawy-syn

to opis lewego lub prawego poddrzewa w takim samym formacie lub () (nawias

otwierający

nawias zamykający) gdy odpowiednie poddrzewo jest puste. Np:

( () B BOND007 1 ( () R BOREWICZ07 2 () ) )

(należy zwrócić szczególną uwagę na umieszczenie w odpowiednich miejscach białych znaków).

Testy

Za implementację wszystkich komend, poza DRZEWO (testy nr. 1-7) można uzyskać 5 pkt
(dopuszczalna jest implementacja przy użyciu innej struktury, o ile zmieści się w czasie). Za
implementację wszystkich komend otrzymuje się 9 pkt. Kolejne testy sprawdzają następujące rzeczy:

Test 1 (0.5 pkt.) - małe dane, polecenia KUP, i WYPISZ
Test 2 (0.5 pkt.) - małe dane, polecenia KUP, ILE i WYPISZ
Test 3 (0.5 pkt.) - małe dane, polecenia KUP, ILE, SPRZEDAJ i WYPISZ
Test 4 (0.5 pkt.) - małe dane, polecenia KUP, ILE, SPRZEDAJ, WYMIEN i WYPISZ
Test 5 (1 pkt.) - małe dane, polecenia KUP, ILE, SPRZEDAJ, WYMIEN, WYPISZTYLKO i
WYPISZ
Test 6 (1 pkt.) - duże dane, polecenia KUP, ILE, SPRZEDAJ, WYMIEN, WYPISZTYLKO i
WYPISZ
Test 7 (1 pkt.) - duże dane, polecenia KUP, ILE, SPRZEDAJ, WYMIEN, WYPISZTYLKO i
WYPISZ
Test 8 (4 pkt.) - wszystko (duże dane, polecenia KUP, ILE, SPRZEDAJ, WYMIEN, WYPISZ,
WYPISZTYLKO i DRZEWO)

Język

Zadanie należy zaimplementować w języku C.

Przykład

Wejście

KUP BOND007 1

KUP BOREWICZ07 2

KUP SUPERMAN 3

WYMIEN BOREWICZ07 AGENTAS

ILE BOREWICZ07

ILE KAJMANY

WYPISZ

DRZEWO

WYPISZTYLKO B

Wyjście

2

1

0

AGENTAS 1

BOND007 1

BOREWICZ07 1

SUPERMAN 3

( ( ( () R AGENTAS 1 () ) B BOND007 1 () ) B BOREWICZ07 1 ( () B SUPERMAN 3 () ) )

BOND007 1

BOREWICZ07 1

Dodatkowe testy
6,7,8 - wszystkie możliwe sposoby tworzenia i usuwania (po jednym węźle) drzew o n=6,7,8
rand - ciąg losowych operacji

Added by:

Krzysztof M. Ocetkiewicz

Date:

2009-04-21

Time limit: 1s
Source limit:50000B
Languages: C C99 strict DOC PDF PS

3