Решение задачи "Транспорт на Новый год " с Codeforces

Без пояснения   Просмотров: 76


Новый год приходит в Линейный мир! В этом мире есть n ячеек, пронумерованных целыми числами от 1 до n, уложенных в виде доски размером 1 × n. В ячейках живут люди. Однако, передвигаться между различными ячейками сложно, ведь выйти из ячейки — дело непростое. В то же время, люди хотят знакомиться с людьми, живущими в других ячейках.

И вот, tncks0121 придумал систему транспорта для передвижения между ячейками, чтобы люди могли отпраздновать Новый год. Сперва он задумал n - 1 положительных целых чисел a1, a2, ..., an - 1. Для каждого целого числа i, где 1 ≤ i ≤ n - 1, выполняется условие 1 ≤ ai ≤ n - i. Затем он создал n - 1 порталов, пронумерованных целыми числами от 1 до n - 1. Из них i-й (1 ≤ i ≤ n - 1) портал соединяет ячейку номер i и ячейку номер (i + ai), т. е. с его помощью можно путешествовать из ячейки i в ячейку (i + ai). К сожалению, портал не работает в обратную сторону, то есть нельзя пройти из ячейки (i + ai) в ячейку i по i-му порталу. Легко заметить, что из-за условия 1 ≤ ai ≤ n - i нельзя покинуть Линейный мир, пользуясь порталами.

Я нахожусь в ячейке 1 и хочу пройти в ячейку t. Однако я не знаю, могу ли я там оказаться. Пожалуйста, определите, могу ли я пройти в ячейку t, пользуясь только построенной системой транспорта.

Код

#include <iostream>
using namespace std;
 
int main (){
	int n, t, j = 1;
	cin >> n >> t;
	int a[n];
	for (int i=1; i<n; i++)
		cin >> a[i];
	for (j=1; j<t; j=j+a[j])
		;
	cout << (j == t ? "YES" : "NO") << endl;
	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться