#509. 欢乐的跳

欢乐的跳

题目背景

在一个遥远的整数王国里,住着一位热爱跳跃的国王。他每天都要在数组的石阶上蹦跶,并且坚持认为:只有每一步的跳跃距离恰好覆盖了所有可能的步伐长度,才算真正的欢乐。

题目描述

给定一个包含 nn 个整数的数组 a1,a2,…,ana_1, a_2, \dots, a_n。

定义相邻两元素之间的跳跃距离为:

di=∣ai−ai+1∣(1≤i<n)d_i = |a_i - a_{i+1}| \quad (1 \le i < n)

如果这 n−1n-1 个跳跃距离恰好包含了从 11 到 n−1n-1 的所有整数(每个至少出现一次),则称该数组符合“欢乐的跳”。

例如数组 {1,4,2,3}\{1, 4, 2, 3\} 符合“欢乐的跳”,因为相邻差的绝对值为:

∣1−4∣=3,∣4−2∣=2,∣2−3∣=1|1-4|=3,\quad |4-2|=2,\quad |2-3|=1

恰好覆盖了 [1,3][1, 3] 中的所有整数。

输入格式

每组测试数据第一行以一个整数 nn(1≤n≤10001 \le n \le 1000)开始。

接下来一行包含 nn 个空格隔开的整数,每个整数在 [−108,108][-10^8, 10^8] 之间。

注意:本题可能包含多组测试数据,直到文件结束(EOF)。

输出格式

对于每组测试数据,输出一行:

  • 若该数组符合“欢乐的跳”,输出 Jolly
  • 否则输出 Not jolly

输入输出样例 #1

输入 #1

4 1 4 2 3

输出 #1

Jolly

输入输出样例 #2

输入 #2

5 1 4 2 -1 6

输出 #2

Not jolly

样例解释

样例 1

数组为 {1,4,2,3}\{1,4,2,3\},相邻差的绝对值为:

3, 2, 13,\ 2,\ 1

恰好包含 1,2,31,2,3,所以输出 Jolly。

样例 2

数组为 {1,4,2,−1,6}\{1,4,2,-1,6\},相邻差的绝对值为:

3, 2, 3, 73,\ 2,\ 3,\ 7
  • 缺少 11(n−1=4n-1=4,需要覆盖 1,2,3,41,2,3,4)
  • 出现 77,超出范围

所以输出 Not jolly。

数据范围与提示

  • 1≤n≤10001 \le n \le 1000
  • ∣ai∣≤108|a_i| \le 10^8
  • 输入可能有多组,读到文件结束为止
  • 建议使用布尔数组或集合记录出现过的跳跃距离

小提示

当 n=1n = 1 时,不存在相邻元素对,跳跃距离集合为空。此时从 11 到 00 的范围也是空的,因此默认符合“欢乐的跳”,应输出 Jolly。