Amdrek

07.09.2021 20:38

Информатика

Есть ответ 👍

C. Кольцо ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Дано n передатчиков, которые стоят в кольце, т.е. за i-м стоит i+1-й, а за n-м стоит 1-й. Каждое из устройств может передавать сообщение на расстояние mi (0≤mi≤n), т.е. может передать сообщение всем передатчикам справа от i+1 до i+mi, а также передатчикам слева от i−mi до i−1. Если mi=0, значит, устройство включено только на чтение.

Задача состоит в том, чтобы понять, можно ли «закольцевать» сообщение в этой сети - сообщение отправляется от 1-го передатчика, проходит через все передатчики (возможно, не один раз) и снова возвращается 1-му передатчику.

Входные данные
В первой строке содержится целое число t - количество тестов. Далее идут t тестов, вида: в первой строке теста содержится целое число n (1≤n≤105) - количество устройств, в следующих n строках содержатся радиусы mi работы устройств 0≤mi≤n. Сумма всех n по всем t тестам не превосходит 105.

Выходные данные
Вывести t ответов «YES» или «NO» на каждый тест (каждый ответ на отдельной строке).

Примеры
входные данные
1
5
1 2 3 4 5
выходные данные
YES
входные данные
2
3
1 1 1
4
1 0 0 0
выходные данные
YES
NO