10038 - Jolly Jumpers

[thelostknight]

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

[jenovaforum]

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.

As for recent specific advice...
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"

[tristanx9]

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

[fj.iglesias]

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.

[shaon_cse_cu08]

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

[6662666]

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 while

exit(0);
return 0;
}

[kawsar]

Why i get WA, every time ??
can anyone explain about this problem.

#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]

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

[dewsworld]

Could anyone please tell me why this is not working??????

Code: Select all

Removed after AC


[helloneo]

"Not Jolly" should be "Not jolly"

[dewsworld]

"Not Jolly" should be "Not jolly"

That made me silly
Thanks Helloneo

[Deb20]

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

[tejas.deshpande]

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";
        }

    }
}



[sbrown]

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 of
integers 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;
    }
}





[freshmen87]

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;
}



please help