Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP5_2D - Stosy |
Jakże wielkie było nasze zaskoczenie kiedy zajrzeliśmy dzisiaj rano do magazynu WWSI. Otóż kartony, w których znajdowały się nagrody dla zwycięzców MWWSIP zniknęły! Jeszcze wczoraj po południu leżały wszystkie na stosie o numerze p a teraz po prostu ich nie ma! Wyniki śledztwa jakie natychmiastowo rozpoczęliśmy trochę nas uspokoiły, wciąż jednak sytuacja nie jest w stu procentach jasna...
Nasze śledztwo wykazało, że wczoraj tuż po naszym opuszczeniu budynku jeden z pracowników szukał czegoś w magazynie i poprzestawiał w nim większość kartonów. Na naszą prośbę odtworzył z pamięci wygląd magazynu sprzed szukania oraz ruchy jakie wykonywał. W ten sposób uzyskaliśmy informację, że "początkowo na stosie o numerze jeden znajdowały się 3 kartony, na stosie o numerze dwa było 5 kartonów, a na n-tym stosie 38 kartonów. Wasze kartony były na p-tym stosie - najpierw wziąłem dwa kartony ze stosu drugiego i przełożyłem je na stos czwarty, potem wziąłem trzy kartony ze stosu n-tego i przełożyłem je na stos pierwszy... itd."
Wszystko to rzetelnie spisaliśmy i teraz potrzebujemy programu, który na podstawie informacji o liczbie kartonów znajdujących się na danym stosie, numerze stosu który zawierał nasze kartony (stos ten zwierał wyłącznie nasze kartony), a także wykonywanych przez sprzątającego ruchach określi ile obecnie należących do nas kartonów znajduje się na danym stosie. Należy brać pod uwagę, że w takich sytuacjach pamięć bywa zawodna tak więc czasem opis może okazać się nieprecyzyjny - tzn. czasami według relacji, sprzątający wziął ze stosu pięć kartonów podczas kiedy w rzeczywistości znajdowały się na nim jedynie trzy innym razem z kolei twierdził, że brał kartony ze stosu który w rzeczywistości był pusty... Zakładamy wtedy że w pierwszym przypadku sprzątający wziął w rzeczywistości jedynie trzy kartony, a liczba pięć była po prostu pomyłką a w drugim przypadku nie wziął ich wcale (są to jedyne rodzaje nieścisłości jakie mogą wystąpić).
Wejście
W pierwszej linii wejścia znajdują się dwie liczby n (1 ≤ n ≤ 1000) oraz p (1 ≤ p ≤ n) określające odpowiednio liczbę stosów znajdujących się w magazynie oraz numer stosu na którym początkowo znajdowały się interesujące nas kartony. W drugiej linii znajduje się n liczb z przedziału od 1 do 106, każda z nich określa początkowy rozmiar danego stosu (i-ta liczba określa i-ty stos). W trzeciej linii wejścia znajduje się liczba m (1 ≤ m ≤ 10000) opisująca ile ruchów wykonała osoba sprzątająca magazyn, a po niej w każdej z następnych m linii znajduje się opis kolejnego wykonanego przestawienia. Opis ten składa się z trzech liczb a, b oraz c (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ c ≤ 10) oznaczających odpowiednio numer stosu, z którego wzięte zostały kartony, numer stosu na jaki kartony zostały przełożone i liczbę przełożonych kartonów. Należy założyć, że kartony zawsze przekładane są pojedynczo (w końcu nie ma co przeciążać kręgosłupa dźwigając dwa kartony za jednym razem!).
Wyjście
Na wyjściu należy wypisać n liczb oddzielonych od siebie pojedynczymi spacjami. Liczby te powinny określać ile interesujących nas kartonów znajduje się na danym stosie (i-ta liczba opisuje i-ty stos).
Przykład
Wejście:
5 3 4 5 3 4 2 5 1 2 2 4 3 2 3 5 4 5 1 3 3 5 3
Wyjście:
2 0 0 0 1
Dodane przez: | Maciej Boniecki |
Data dodania: | 2013-03-15 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |
Pochodzenie: | V Mistrzostwa WWSI w Programowaniu |