시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 38 | 20 | 16 | 48.485% |
Młodsza siostra Hektora, Kornelia (którą poznaliśmy w zadaniu Zgadywanka) z dystansem podchodzi do zajęć prowadzonych w przedszkolu, do którego uczęszcza. Przykładowo - wychowawcy w przedszkolu oczekują od niej, że będzie ćwiczyć sprawność posługiwania się piórem rysując w specjalnym zeszycie tak zwane "szlaczki" - powtarzające się wzory. Kornelia uważa to zajęcie za mało ambitne, postanowiła więc je urozmaicić, i rysować wymyślone przez siebie "szlaczki rekurencyjne".
Szlaczki Kornelii zamiast z graficznych wzorów, składają się z liczb naturalnych. Kornelia rozpoczyna je od zapisania dowolnego ciągu liczb naturalnych, przykładowo:
1 2 1 1 1
A następnie do woli dopisuje do już zapisanego fragmentu "szlaczka" ten sam fragment od końca (każdorazowo podwajając długość szlaczka). Dla przykładowego szlaczka, w następnym kroku wyglądałby on tak:
1 2 1 1 1 1 1 1 2 1
Natomiast w kolejnym kroku Kornelia uzyskałaby wzór:
1 2 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1
Proces konstrukcji szlaczka można kontynuuować bez końca.
Znając ciąg, od którego Kornelia rozpoczęła tworzenie szlaczka, oblicz jaka liczba znajdzie się na zadanej pozycji wzoru.
W pierwszej linii wejścia znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
Pierwsza linia opisu zestawu testowego zawiera parę liczb naturalnych N i M ( 1 <= N <= 1000000, 0 <= M <= 1000000000), oznaczających kolejno: długość początkowego ciągu oraz pozycję w wynikowym wzorze.
W drugiej linii opisu zestawu znajduje się N oddzielonych spacjami liczb naturalnych ci ( 1 <= ci <= 1000000) oznaczających kolejne liczby w początkowym ciągu.
Dla każdego testu należy w osobnej linii wypisać liczbę, która znajdzie się na M-tej pozycji szlaczka Kornelii, przy czym pozycje w ciągu numerujemy począwszy od zera.
3 5 0 1 2 1 1 1 5 1 1 2 1 1 1 5 8 1 2 1 1 1
1 2 2
Contest > Spot > HotSpot 2011 1-3번