w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005
|
|
IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005 |
Zadanie C - Gra w liczby |
Opis
Anty-Patentowcy razem z Anty-Anty-Patentowcami w wolnych chwilach (pomiędzy kolejnymi wiecami) lubią dla relaksu pograć sobie w prostą grę towarzyską. Jej reguły, jak przystało na prostą grę, są proste. Gracze po kolej mówią pewne dodatnie liczby całkowite które wszyscy zapamiętują. Co jakiś czas jeden z graczy zadaje pytanie: "Po posortowaniu niemalejąco wszystkich dotychczas wymienionych liczb, która z nich znalazłaby się na j-tej pozycji?". Pierwszy z pozostałych graczy który prawidłowo odpowie na to pytanie w nagrodę dostaje od wszystkich pozostałych uczestników zabawy po cukierku.
Łasuch - jeden z graczy który bardzo lubił słodkości (a cukierki w szczególności), poprosił Cię o napisanie programu który pomógłby mu w zdobyciu smakołyków.
Zadanie
Napisz program który na podstawie wymienianych przez graczy liczb oraz zadawanych pytań podpowiadałby Łasuchowi prawidłowe odpowiedzi.
Wejście
W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę następujących zestawów danych.
Każdy zestaw składa się z dwóch linii. W pierwszej z nich zapisana jest liczba N oznaczająca liczbę ruchów w grze. W drugiej linii zapisanych jest N liczb całkowitych ki opisujących kolejne ruchy. Jeżeli ki>0 to oznacza, że w i-tym ruchu powiedziano liczbę ki. Jeżeli natomiast ki<0 to oznacza to, że w i-tym ruchu zadano pytanie o liczbę leżącą na (-ki)-tej pozycji w posortowanym ciągu wypowiedzianych wcześniej liczb. Wiadomo, że: 1≤N≤1000000, ki≤1000000 oraz, że liczba pytań w grze (czyli takich i, że ki<0) jest nie większa niż 100000. Oczywiście w podanym ciągu nigdy nie padnie pytanie o nieistniejącą pozycję, czyli w szczególności wiadomo, że k1>0.
Wyjście
Dla każdego zestawu danych należy w pojedynczej linii wypisać odpowiedzi na wszystkie zadane w danej grze pytania. Jeżeli nie padło żadne pytanie to należy wypisać pustą linię.
2 6 1 2 -2 3 4 -3 6 7 6 -2 5 4 -3
2 3 7 6