| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 2048 MB | 4 | 3 | 3 | 100.000% |
W przedszkolu Bajtosi jest dużo zabawek i czasami ciężko dziewczynce zdecydować, którą z nich będzie się bawić danego dnia. W celu ułatwienia sobie wyboru, Bajtosia postanowiła użyć wyliczanek.
Jeśli danego dnia chce wybrać jedną z $n$ zabawek, to ustawia je wszystkie w rzędzie i numeruje od $1$ do $n$. Zaczyna od wskazania na jedną z zabawek, a potem recytuje wyliczankę i przy każdej sylabie przechodzi do zabawki poprzedniej lub następnej w rzędzie (w przypadku zabawki $1$ oraz $n$ nie ma wyboru i musi przejść odpowiednio do $2$ oraz $n - 1$). Ostatnią wskazaną zabawką bawi się przez resztę dnia.
Bajtosia w trakcie wyliczanki śledzi, ile razy wskazuje na każdą z zabawek: po skończeniu wyliczanki zabawka $i$-ta została wskazana $a_i$ razy. Sprawdź, czy Bajtosia się nie pomyliła, czyli dla danego ciągu $a_1, a_2, \dots , a_n$ zapamiętanego przez Bajtosię stwierdź, czy istnieje wyliczanka do niego pasująca.
Sytuacja ta powtarzała się przez $t$ dni z różnymi podzbiorami zabawek $i$ różnymi wyliczankami.
Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 ≤ t ≤ 100\, 000$), oznaczającą liczbę dni, w których Bajtosia używała wyliczanek do wyboru zabawki. Następnie jest $t$ opisów poszczególnych dni, jeden za drugim.
Pierwszy wiersz opisu dnia zawiera jedną liczbę całkowitą $n$ ($1 ≤ n ≤ 1\, 000\, 000$), oznaczającą liczbę zabawek uczestniczących tego dnia w wyliczance. Drugi wiersz zawiera ciąg $n$ liczb całkowitych $a_1, a_2, \dots , a_n$ ($0 ≤ a_i ≤ 10^9$), oznaczających ile razy kolejne zabawki zostały wskazane w trakcie wyliczanki według Bajtosi. Możesz założyć, że co najmniej jedna z liczb $a_i$ jest niezerowa.
Suma wszystkich wartości $n$ po wszystkich $t$ dniach nie przekracza $1\, 000\, 000$.
Na wyjście należy wypisać $t$ wierszy zawierających jedno ze słów TAK lub NIE. Słowo TAK oznacza, że istnieje wyliczanka pasująca do ciągu zapamiętanego przez Bajtosię, słowo NIE oznacza, że taka wyliczanka nie istnieje.
7 3 1 3 1 2 5 7 3 0 1 0 1 2 6 3 3 2 1 0 0 5 1 3 2 2 3 3 1 0 1
TAK NIE TAK NIE TAK NIE NIE
Pierwszego dnia Bajtosia w trakcie wyliczanki mogła wskazywać kolejno przedmioty $2$, $1$, $2$, $3$, $2$.
Trzeciego dnia użyła krótkiej wyliczanki i zaczęła bawić się pierwszą wskazaną zabawką.
Natomiast piątego mogła wskazać kolejno przedmioty $1$, $2$, $3$, $4$, $3$, $2$, $1$, $2$, $1$.
Dla żadnego z pozostałych dni nie istnieje odpowiednia wyliczanka.
Contest > Algorithmic Engagements > PA 2025 2-2번