Sparing w Programowaniu Politechnika Poznańska, 10.03.2007 |
Zadanie F - Czarna skrzynka |
Czarna Skrzynka jest prymitywną bazą danych. Może zapamiętywać liczby oraz posiada specjalną zmienną i. Początkowo Czarna Skrzynka jest pusta, a i wynosi 0. Czarna Skrzynka przetwarza sekwencję komend. Są dwa typy komend:
Rozważmy ciąg 11 komend:
N | Komenda | i | Zawartość Czarnej Skrzynki po danej komendzie (elementy zostały posortowane) |
Odpowiedź |
1 | DODAJ (3) | 0 | 3 | |
2 | POBIERZ | 1 | 3 | 3 |
3 | DODAJ (1) | 1 | 1, 3 | |
4 | POBIERZ | 2 | 1, 3 | 3 |
5 | DODAJ (-4) | 2 | -4, 1, 3 | |
6 | DODAJ (2) | 2 | -4, 1, 2, 3 | |
7 | DODAJ (9) | 2 | -4, 1, 2, 3, 9 | |
9 | DODAJ (-100) | 2 | -100, -4, 1, 2, 3, 9 | |
9 | POBIERZ | 3 | -100, -4, 1, 2, 3, 9 | 1 |
10 | POBIERZ | 4 | -100, -4, 1, 2, 3, 9 | 2 |
11 | DODAJ (2) | 4 | -100, -4, 1, 2, 2, 3, 9 |
Zadanie polega napisaniu programu, który implementuje Czarną Skrzynkę. Maksymalna liczba komend DODAJ i POBIERZ wynosi 30000 każdego rodzaju.
Zapiszmy ciąg komend w postaci dwóch tablic:
1. A(1), A(2), ..., A(M): ciąg elementów, które są dodawane do Czarnej skrzynki komendą DODAJ(x). Wartości tablicy A są liczbami całkowitymi, których bezwzględna wartość nie przekracza 2 000 000 000. M<=30000. Na przykład dla powyższego ciągu, mamy A=(3, 1, -4, 2, 9, -100, 2).
2. u(1), u(2), ..., u(N) : ciąg opisujący momenty wykonania komend POBIERZ. Dla powyższego przykładu wynosi on u=(1, 2, 6, 6), czyli POBIERZ jest po pierwszej, drugiej, szóstej i znów szóstej komendzie DODAJ(x).
Możesz założyć, że ciąg liczb naturalnych u(1), u(2), ..., u(N) jest posortowany niemalejąco, N<=M oraz, że dla każdego p (1<=p<=N) zachodzi p<=u(p)<=M. Wynika to z faktu, iż dla p-tego elementu naszego ciągu u pobieramy p-tą minimalną liczbę z sekwencji A(1), A(2), ..., A(u(p)).
W pierwszej linii wejścia znajduje się liczba D określająca liczbę testów. Każdy zbiór testowy zawiera kolejno: M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). Wszystkie liczby są oddzielone spacjami i/lub znakami końca linii.
Wejście2 1 1 2 1 7 4 3 1 -4 2 9 -100 2 1 2 6 6 |
Wyjście2 3 3 1 2 |