放牧代码和思想
专注自然语言处理、机器学习算法

UVa Q10038: Jolly Jumpers

代数类。作为《挑战编程-程序设计竞赛训练手册》第二章第一题,入门级别。

Q10038: Jolly Jumpers

有n个整数的序列我们称为jolly jumper,如果相邻的2个数其差的绝对值恰好为1到n-1。例如:

1 4 2 3

就是jolly jumper(n=4)。因为相邻2数的差的绝对值为3,2,1,就是1到n-1。但是

1 4 2 -1 6 

不是jolly jumper(n=5)。因为相邻2数的差的绝对值为3,2,3,7,并非1到n-1。

你的任务是写一个程式来判断一个整数序列是否为jolly jumper。

Input

每组测试资料一列,第一个正整数为 n(n < 3000),代表此整数序列的长度。接下来有n个整数,代表此整数序列。请参考Sample Input。

Output

对每一组测试资料,输出此整数序列是否为jolly jumper。请参考Sample Output。

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

我的解法:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
#include <algorithm>
using namespace std;

void print_coll(const vector<int>& coll)
{
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n = 0;
	while (cin >> n)
	{
		vector<int> coll(n);
		vector<bool> digit(n - 1, false);
		for (int i = 0; i < n; ++i)
		{
			cin >> coll[i];
		}

		/*print_coll(coll);*/
		bool is_jolly = true;
		for (int i = 1; i < n; ++i)
		{
			int d = abs(coll[i] - coll[i - 1]) - 1;
			if (d < 0 || d >= n - 1)
			{
				is_jolly = false;
				break;
			}
			digit[d] = true;
		}

		if (is_jolly)
		{
			if (find(digit.begin(), digit.end(), false) != digit.end())
			{
				is_jolly = false;
			}
		}

		if (is_jolly)
		{
			cout << "Jolly" << endl;
		}
		else
		{
			cout << "Not jolly" << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa Q10038: Jolly Jumpers

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机