10038 - Jolly Jumpers

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.

Output

For each line of input, generate a line of output saying "Jolly" or "Not jolly".

Sample Input

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

Sample Output

Jolly
Not jolly

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=979

---

這題的題意是說若有一n項的數列，相鄰兩個數的差的絕對值，包含了所有1~n-1的數字就是jolly，反之就是not jolly。我的作法是將相鄰兩數相減取絕對值後記在table裡，看有哪些數字有出現過，最後在從1跑到n-1檢查table看是不是每個數字都出現了，只要有任何一個數字沒有出現，這就不是jolly，若都出現了，就是jolly。

c++程式碼:

#include <iostream>
#include <map>
#include <vector>
#include <cstdlib>
using namespace std;

int main() {
    int n;

    while (cin >> n) {
        map<int, bool> rem;
        vector<int> seq;
        bool isJolly = true;

        for (int i=0; i<n; i++) {
            int num;

            cin >> num;
            seq.push_back(num);
        }
        for (int i=1; i<seq.size(); i++)
            rem[abs(seq[i]-seq[i-1])] = true;
        for (int i=1; i<n; i++) {
            if (!rem[i]) {
                isJolly = false;
                break;
            }
        }
        if (isJolly)
            cout << "Jolly\n";
        else
            cout << "Not jolly\n";
    }
    return 0;
}