301911: CF362B. Petya and Staircases

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Petya and Staircases

题意翻译

题目描述: 有很多级台阶,皮特想走过他们,有的台阶很脏,所以他不想踏上去。他一次可以跨过 **1 或 2 级** 台阶,也可以只走到上一级,而不跨过台阶。现在他在第一级台阶,他要到第 $n$ 级台阶上,问是否能在不踏上脏台阶的情况下做到。 注意:皮特一定会踏上第一个和最后一个台阶,所以如果第一个或最后一个台阶是脏的,那么皮特一定会踏上脏台阶。 输入格式: 第一行两个整数 $n$ 和 $m$ ,表示有 $n$ 级台阶,和 $m$ 级脏的台阶,接下来是 $m$ 级脏台阶的编号。 输出格式: 如果皮特在不踏上脏台阶的情况下也能到第 $n$ 级台阶上,输出 ``YES``. 否则输出``NO``. $( 1<=n<=10^{9},0<=m<=3000 ) $

题目描述

Little boy Petya loves stairs very much. But he is bored from simple going up and down them — he loves jumping over several stairs at a time. As he stands on some stair, he can either jump to the next one or jump over one or two stairs at a time. But some stairs are too dirty and Petya doesn't want to step on them. Now Petya is on the first stair of the staircase, consisting of $ n $ stairs. He also knows the numbers of the dirty stairs of this staircase. Help Petya find out if he can jump through the entire staircase and reach the last stair number $ n $ without touching a dirty stair once. One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=10^{9} $ , $ 0<=m<=3000 $ ) — the number of stairs in the staircase and the number of dirty stairs, correspondingly. The second line contains $ m $ different space-separated integers $ d_{1},d_{2},...,d_{m} $ ( $ 1<=d_{i}<=n $ ) — the numbers of the dirty stairs (in an arbitrary order).

输出格式


Print "YES" if Petya can reach stair number $ n $ , stepping only on the clean stairs. Otherwise print "NO".

输入输出样例

输入样例 #1

10 5
2 4 8 3 6

输出样例 #1

NO

输入样例 #2

10 5
2 4 5 7 9

输出样例 #2

YES

Input

题意翻译

题目描述: 有很多级台阶,皮特想走过他们,有的台阶很脏,所以他不想踏上去。他一次可以跨过 **1 或 2 级** 台阶,也可以只走到上一级,而不跨过台阶。现在他在第一级台阶,他要到第 $n$ 级台阶上,问是否能在不踏上脏台阶的情况下做到。 注意:皮特一定会踏上第一个和最后一个台阶,所以如果第一个或最后一个台阶是脏的,那么皮特一定会踏上脏台阶。 输入格式: 第一行两个整数 $n$ 和 $m$ ,表示有 $n$ 级台阶,和 $m$ 级脏的台阶,接下来是 $m$ 级脏台阶的编号。 输出格式: 如果皮特在不踏上脏台阶的情况下也能到第 $n$ 级台阶上,输出 ``YES``. 否则输出``NO``. $( 1<=n<=10^{9},0<=m<=3000 ) $

加入题单

上一题 下一题 算法标签: