## 10038 - Jolly Jumpers

Moderator: Board moderators

### Re: 10038 - Jolly Jumpers

Hi

im getting toruble with this problem and i wanna know if the following input is "JOLLY"

9 10 5 1 4 6 12 19 27 26

because according to the uva toolkit its JOLLY, and I still cannot understand why?

can anyone help me? plis

thelostknight
New poster

Posts: 1
Joined: Wed Nov 18, 2009 4:59 am

### Re: 10038 - Jolly Jumpers

Words of general advice from correcting my WA into an AC:
In my original algorithm, I just read in numbers, took differences as I read them in, and trashed the rest of the line if I found something bad before the end of the sequence. I switched over to reading them *all* into an ADT, and then taking differences, and magically, my algorithm started working. Also at this time, rather than relying on my general formula (which should have been closed for a sequence of one number), I added an additional clause for a sequence only one number in length.

General tips:
Why sort when you can use something much more like hashing? O(n) vs. O(n lg(n)) Not to mention it's cleaner...
All operations stay within the bounds of 32-bit integers.

thelostknight:

The test case of...
9 10 5 1 4 6 12 19 27 26

This sequence is jolly because there are 9 numbers in the sequence, so the absolute differences between consecutive numbers in the sequence must make up the set {1,2,3,4,5,6,7,8}, but in no particular order.

|10 - 5| = 5
|5 - 1| = 4
|1 - 4| = 3
|4 - 6| = 2
|6 - 12| = 6
|12 - 19| = 7
|19 - 27| = 8
|27 - 26| = 1

Since the set {1,2,3,4,5,6,7,8} has been constructed from these differences, you would call this sequence of nine integers "Jolly"
jenovaforum
New poster

Posts: 2
Joined: Sun Feb 14, 2010 12:05 am

### Re: 10038 - Jolly Jumpers

Hi everybody! Iḿ trying to solve jolly jumpers but UVa keeps on "Runtime error". I really don't know what is going on, someone could please look my code I give a sugestion?

Code: Select all
`import java.io.*;class jolly_jumpers{    public static void main(String[] args) throws IOException{            boolean[] validar;        int n,indice;        int passou;        BufferedReader   inReader;        inReader = new BufferedReader(new InputStreamReader(System.in));        String line;            while((line = inReader.readLine())!= null) {                String [] numeros = line.split("\\s");                n = Integer.parseInt(numeros[0]);                                validar = new boolean[n];               passou = 1;                for(int i=0;i<n;i++){                    validar[i]=false;                }                for(int i=0; i<n-1; i++){                    indice = Math.abs(Integer.parseInt(numeros[i+1]) - Integer.parseInt(numeros[i+2]));                    //conferir se indice se encaixa na faixa permitida                     if(indice==0 || indice>=n){                       passou = 0;                       break;                    }                    validar[indice] = true;                }                if(passou == 1){              for(int i=1;i<n;i++){                 if(validar[i]==false){ passou = 0;}              }                }                if(passou==1){System.out.println("Jolly");}                else{System.out.println("Not jolly");}              }        }}`

I'm using this input:

4 1 4 2 3
5 1 4 2 -1 6
6 3 2 4 3 2 1
4 1 3 0 -1
4 1 3 2 -2
1 2000
2 1999 1998
3 1 2 4
3 4 2 1
3 104 102 101
3 -5 -7 -6
3 4 1 3
200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
10 1 2 3 4 5 6 7 8 9 10
10 1 2 4 7 11 16 22 29 37 46
10 -1 -2 -4 -7 -11 -16 -22 -29 -37 -46
10 -1 -1 -4 -7 -11 -16 -22 -29 -37 -46
1 1
2 1 2
2 2 1
4 0 4 2 3
4 1 3 2 4
1 2
6 1 4 3 7 5 10
5 3 4 2 3 5
9 5 6 4 1 -3 2 8 15 7
9 10 5 1 4 6 12 19 27 36
9 10 5 1 4 6 12 19 27 26

Ginving me:

Jolly
Not jolly
Not jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Not jolly
Jolly
tristanx9
New poster

Posts: 4
Joined: Mon Mar 08, 2010 11:35 pm

### Re: 10038 - Jolly Jumpers

Hi tristranx9,

I've tested in my program the case you posted and I get exactly the same output
I cannot find any error in both your code and mine's. Here is my code:

Code: Select all
`import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main implements Runnable{    public static void main(String args[]) {        Main myWork = new Main();        myWork.run();    }    public void run() {        new JollyJumpers().run();    }    }class JollyJumpers implements Runnable {      static boolean[] DIFFERENCES = new boolean[3000];       public void run() {              String line;       boolean jolly;       int ant;       int sig;       int absdif;       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       try {          while ( (line = br.readLine()) != null && line.length() > 0 ) {             jolly = true;             String[] tokens = line.split(" ");             int n = Integer.parseInt(tokens[0]);             // The definition implies that any sequence of a single integer              // is a jolly jumper.             if (n > 1) {                initDifferences(DIFFERENCES, n);                   for (int i = 1; i < n; i++) {                   // n-1 differences                   ant = Integer.parseInt(tokens[i]);                   sig = Integer.parseInt(tokens[i+1]);                   absdif = Math.abs(sig-ant);                   if (absdif > n-1 || absdif < 1) {                      jolly = false;                      break;                   } else {                      if (DIFFERENCES[absdif]) {                         jolly = false;                         break;                      } else                         DIFFERENCES[absdif] = true;                   }                }             }             if (jolly)                System.out.println("Jolly");             else                System.out.println("Not jolly");          }       } catch (IOException ioe) {          ioe.printStackTrace();       }           }        void initDifferences(boolean[] differences, int n) {       for (int i = 1; i < n; i++)          differences[i] = false;    }        // You can insert more classes here if you want.}`

Some help would be very grateful, I've tried many test cases in the forum and the judge in programming-challenges always replies me Wrong Answer.
fj.iglesias
New poster

Posts: 1
Joined: Fri Jun 18, 2010 1:00 pm

### Re: 10038 - Jolly Jumpers

jenovaforum wrote:This is the point where every 1 becomes fool....
Tnx for ur post i got AC without posting anything....

Sometime's other's mistakes can be ur Idea
It's not who i m inside me... But what i do, that defines me...:)
shaon_cse_cu08
New poster

Posts: 46
Joined: Tue May 25, 2010 9:10 am

### Re: 10038 - Jolly Jumpers

can anybody help me to sort out the problem.I m getting runtime error again and again...
Code: Select all
`#include<stdio.h>#include<iostream.h>int main(){long long i=0,temp1,temp2,dif,flag;int n,check=1;struct node{long long data;node *next;}*list,*tmp,*last;list=NULL;while(scanf("%d",&n)==1){   flag=0;   dif=1;   check=1;   if(n==1)   {      scanf("%lld",&temp2);      printf("Not jolly\n");         }   else {   for(i=0;i<n;i++)   {     scanf("%lld",&temp2);     if(flag==1)      continue;     if(i==0)      temp1=temp2;     else dif=temp2-temp1;     temp1=temp2;     if(dif<0) dif=-dif;     if(dif>(n-1)) flag=1;     if(i>0&&list==NULL)     {      if(dif<0)      {         list=new node;         list->data=-dif;      }      else      {         list=new node;         list->data=dif;      }      list->next=NULL;     }     else if(i>1)     {      tmp=list;      last=tmp;      while(tmp->data<=dif&&tmp!=NULL)      {         last=tmp;         tmp=tmp->next;      }      if(last->data==dif)         flag=1;      else      {         node *tmp1;         tmp1=new node;         if(last==list)         {            tmp1->data=dif;            tmp1->next=list;            list=tmp1;         }         else         {            tmp1->next=tmp;            tmp1->data=dif;            last->next=tmp1;         }      }//end of flag1 else     }//end of else   }//end of for   if(flag==1)      printf("Not jolly\n");   else   {      //printf("dif=%d\n",(tmp->data)-(last->data));      last=list;      tmp=list;      while(tmp!=NULL)      {         if(tmp->data!=check)         {            printf("Not jolly\n");            break;         }         tmp=tmp->next;         check++;      }//end of nested while      if(tmp==NULL)         printf("Jolly\n");      else printf("Not jolly\n");   }   }//end of n=1 condition}//end of whileexit(0);return 0;}`
6662666
New poster

Posts: 1
Joined: Sat Jul 03, 2010 8:02 am

### Re: 10038 - Jolly Jumpers

Why i get WA, every time ??

#include<stdio.h>
#include<stdlib.h>

int main(){
long n, a[3000], b[3000], i, j ;

while(scanf("%ld",&n)==1){

for(i=0; i<n; i++)
scanf("%ld",&a[i]);

if(n == 0 || n == 1){
printf("Jolly\n");
continue;
}

j=0;
for(i=1; i<n; i++)
b[j++] = abs(a[i] - a[i-1]);

i=0;
if(b[i] == 1){
i++;
while(i<j){
if(b[i-1]+1==b[i])
i++;
else
goto outer;
}
printf("Jolly\n");
continue;
}
else if(b[i] == n-1){
i++;
while(i<j){
if(b[i-1]-1 == b[i])
i++;
else
goto outer;
}
printf("Jolly\n");
continue;
}
else{
printf("Not jolly\n") ;
continue;
}
outer:
printf("Not jolly\n") ;
}
return 0;
}

Plz, help me to find the error.
kawsar
New poster

Posts: 12
Joined: Thu Aug 05, 2010 7:40 pm

### Re: 10038 - Jolly Jumpers

I got accepted....just a few change of my code.
Thanks.
kawsar
New poster

Posts: 12
Joined: Thu Aug 05, 2010 7:40 pm

### Re: 10038 - Jolly Jumpers

Could anyone please tell me why this is not working??????
Code: Select all
`Removed after AC`
Last edited by dewsworld on Fri Aug 27, 2010 1:16 pm, edited 1 time in total.
dewsworld
New poster

Posts: 12
Joined: Fri Aug 13, 2010 11:52 am

### Re: 10038 - Jolly Jumpers

"Not Jolly" should be "Not jolly"
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10038 - Jolly Jumpers

"Not Jolly" should be "Not jolly"

Thanks Helloneo
dewsworld
New poster

Posts: 12
Joined: Fri Aug 13, 2010 11:52 am

### Re: 10038 - Jolly Jumpers

Will you please explain me what is "Jolly jumper" & what is it's conditions.
Thank you.
Deb20
New poster

Posts: 2
Joined: Mon Sep 13, 2010 4:26 pm

### Re: 10038 - Jolly Jumpers

Hi I keep getting runtime error.
However when i test it with input from the forums it is giving correct answers

Code: Select all
`#include <iostream>#include <sstream>#include <string>using namespace std;int inp;bool list [3000];int jumpers [3005];string input;int total_numbers;void clear_first_number(){    int initial = 0;    int final = 0;    char buffer;    for (int counter = 0; counter == counter ;++counter)    {        buffer = input[counter];        if (buffer == ' ')        {            final = counter;            ++ final;            break;        }    }    input.erase(0, final);}int subtract (int one, int two){    int difference = one - two;    if (difference < 0)    {        difference = -1*difference;    }    return difference;}int main(){    for (;;)// main loop till no input    {        int is_jolly = 1;        input.clear();        getline (cin, input);        if (input.length() == 0)        {            return 0;        }        stringstream(input) >> total_numbers;        clear_first_number();        for (int i = 0 ; i < total_numbers; ++i)//process input string        {            stringstream(input) >> inp;            jumpers[i] = inp;            clear_first_number();        }                //create subtractions        for (int j = 0; j < total_numbers ; ++j)        {            int difference = subtract(jumpers[j], jumpers[j+1]);            jumpers[j] = difference;        }                //set bool array all to false        for (int e = 0; e < total_numbers; ++e)        {            list [e] = false;        }                        //make those indexes true which are present        for (int t = 0; t < total_numbers ; ++t)        {            list[jumpers[t]-1] = true;        }        //check if jolly        for (int d = 0; d < total_numbers-1; ++d)        {            if (list[d] == false)            {                is_jolly = 0;            }        }        //print statements        if (is_jolly == 1)        {            cout << "Jolly\n";        }        else        {            cout << "Not jolly\n";        }    }}`
tejas.deshpande
New poster

Posts: 1
Joined: Mon Sep 20, 2010 9:47 am

### Re: 10038 - Jolly Jumpers

Hi,

Could anyone tell me what is wrong with the code below, please? It works with the test input, but on the programming challenges website http://www.programming-challenges.com it is marked as being the wrong answer.

Code: Select all
`#include <iostream>#include <map>#include <vector>using namespace std;int abs(int n);map<int,int> sequence(int n);void readInput();int main(){    while(cin)    {        readInput();    }    return 0;}int abs(int n){    int absoluteValue = n > 0 ? n : -n;    return absoluteValue;}/* Takes a number n and returns a map with a sequence ofintegers from n to n - 1 as the key, and a value of 0. */map<int,int> sequence(int n){    map<int,int> seq;    while(n > 1){       n--;       seq.insert(make_pair(n,0));    }    return seq;}void readInput(){    bool jolly = true;    vector<int> absolutes;    int n;    int next;    int prev;    int count = 0;    cin>>n;    map<int,int>seq = sequence(n);    while(count < n)    {        if(count == 0)        {            prev = 0;        }        cin >> next;        absolutes.push_back(abs(prev - next));        prev = next;        count++;    }    for(int i = 0;i < absolutes.size();i++){       seq[absolutes[i]]++;    }    for(map<int,int>::const_iterator it = seq.begin();        it != seq.end();it++){       if(it->second == 0)       {           jolly = false;       }    }    if(jolly || n == 1)    {        cout << "Jolly"<<endl;    }    else    {        cout << "Not jolly"<<endl;    }}`
sbrown
New poster

Posts: 1
Joined: Mon Mar 28, 2011 1:21 pm

### Re: 10038 - Jolly Jumpers

need help. don't know whats wrong with my code. its always WA

here is the code:
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;

string jolly(int count)
{
bool test[2998] = {0};
int temp, array[2999];
if(count > 0 && count < 3000)
{
for(int x =0;x < count;x++)
cin >> array[x];
if(count == 1)
return "Jolly\n";
for(int i=0;i < count-1;i++)
{
temp = abs(array[i] - array[i+1]);
test[temp] = 1;
}

for(int x = 1;x < count; x++)
{
if(test[x] == 0)
return "Not jolly\n";
}
return "Jolly\n";
}
else
return "";
}

int main()
{
int input;
while(cin >> input)
{
cout << jolly(input);
}
return 0;
}