CF500A.New Year Transportation
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
New Year is coming in Line World! In this world, there are n cells numbered by integers from 1 to n, as a 1 × n board. People live in cells. However, it was hard to move between distinct cells, because of the difficulty of escaping the cell. People wanted to meet people who live in other cells.
So, user tncks0121 has made a transportation system to move between these cells, to celebrate the New Year. First, he thought of n - 1 positive integers _a_1, _a_2, ..., a__n - 1. For every integer i where 1 ≤ i ≤ n - 1 the condition 1 ≤ a__i ≤ n - i holds. Next, he made n - 1 portals, numbered by integers from 1 to n - 1. The i-th (1 ≤ i ≤ n - 1) portal connects cell i and cell (i + a__i), and one can travel from cell i to cell (i + a__i) using the i-th portal. Unfortunately, one cannot use the portal backwards, which means one cannot move from cell (i + a__i) to cell i using the i-th portal. It is easy to see that because of condition 1 ≤ a__i ≤ n - i one can't leave the Line World using portals.
Currently, I am standing at cell 1, and I want to go to cell t. However, I don't know whether it is possible to go there. Please determine whether I can go to cell t by only using the construted transportation system.
新年即将来到线性世界(Line World)!在这个世界中,有 n 个单元格,编号为 1 到 n,排成一个 1×n 的方格阵列。人们居住在这些单元格中。然而,由于难以离开当前单元格,人们很难在不同单元格之间移动。大家都希望能与居住在其他单元格中的人见面。
因此,用户 tncks0121 构建了一套运输系统,以便在这些单元格之间通行,以此庆祝新年。首先,他构思了 n−1 个正整数 a1,a2,…,an−1。对每个满足 1≤i≤n−1 的整数 i,均满足条件 1≤ai≤n−i。接着,他建造了 n−1 个传送门,编号为 1 到 n−1。第 i 个传送门(其中 1≤i≤n−1)连接单元格 i 和单元格 (i+ai),且可通过第 i 个传送门从单元格 i 单向前往单元格 (i+ai)。不幸的是,该传送门不可逆向使用,即无法通过第 i 个传送门从单元格 (i+ai) 返回单元格 i。显然,由条件 1≤ai≤n−i 可知,使用传送门不会使人离开线性世界。
目前,我正位于单元格 1,希望前往单元格 t。但我尚不清楚能否到达那里。请判断:仅利用上述构建的运输系统,我是否能够抵达单元格 t?
输入格式
The first line contains two space-separated integers n (3 ≤ n ≤ 3 × 104) and t (2 ≤ t ≤ n) — the number of cells, and the index of the cell which I want to go to.
The second line contains n - 1 space-separated integers _a_1, _a_2, ..., a__n - 1 (1 ≤ a__i ≤ n - i). It is guaranteed, that using the given transportation system, one cannot leave the Line World.
第一行包含两个以空格分隔的整数 n(3 ≤ n ≤ 3 × 104)和 t(2 ≤ t ≤ n)——分别为单元格总数,以及我想要到达的单元格的编号。
第二行包含 n − 1 个以空格分隔的整数 a1,a2,...,an−1(1 ≤ ai ≤ n − i)。题目保证:利用给定的交通系统,无法离开“线性世界”(Line World)。
输出格式
If I can go to cell t using the transportation system, print "YES". Otherwise, print "NO".
如果我能通过交通系统到达单元格 t,则输出“YES”;否则输出“NO”。
输入输出样例
输入#1
8 4 1 2 1 2 1 2 1
输出#1
YES
输入#2
8 5 1 2 1 2 1 1 1
输出#2
NO
说明/提示
In the first sample, the visited cells are: 1, 2, 4; so we can successfully visit the cell 4.
In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8; so we can't visit the cell 5, which we want to visit.
在第一个样例中,访问过的格子为:1、2、4;因此我们可以成功访问格子 4。
在第二个样例中,可能访问的格子为:1、2、4、6、7、8;因此我们无法访问目标格子 5。
输入解题思路,AI测评打分。不知道怎么写?