10038 - Jolly Jumpers

[osan]

CHECK THIS INPUT

INPUT

4 1 4 2 3
5 1 4 2 -1 6
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

REAL OUTPUT

Jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Jolly
Jolly

YOUR OUTPUT

Jolly
Not Jolly
Not Jolly
Jolly
Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly

[youareaverage]

I've tried just about every sample input from the boards and they all seem to work properly in my program. Maybe someone can help?
Here's my code:
[cpp]
#include <iostream>
#include <algorithm>

using namespace std;

template < class T > T absoluteValue( T input )
{
if ( input < 0 )
{
input *= -1;
}
return input;
}

void jolly( int input[], int arraySize )
{
bool broken = 0;
int counter = 0;
int nArray[ arraySize ];
for ( counter = 1; counter < arraySize; counter++ )
{
nArray[counter-1]=absoluteValue(absoluteValue(input[counter])
-absoluteValue(input[counter-1]));
}
sort( nArray, nArray + ( arraySize - 1 ) );
for ( counter = 0; counter < arraySize - 1 && !broken; counter++ )
{
if ( nArray[ counter ] != counter + 1 )
{
broken = true;
}
}
if ( !broken )
{
cout << "Jolly" << endl;
}
else
{
cout << "Not jolly" << endl;
}
}

int main()
{
//Variables.
int counter = 0;
int arraySize = 3000;
int array[3000];
//Execution.
while ( cin >> arraySize )
{
for ( counter = 0; counter < arraySize; counter++ )
{
cin >> array[ counter ];
}
jolly( array, arraySize );
}
return 0;
}
[/cpp]

Thanks in advance!

[osan]

INPUT

4 1 4 2 3
5 1 4 2 -1 6
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

OUTPUT

Jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Jolly
Jolly

[Morning]

[java]
import java.io.*;
import java.util.*;

class Main
{
static int abs(int number)
{
if (number < 0)
{
return -1 * number;
}
else return number;
}
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
}

void Begin()
{
int array[];
String input;
StringTokenizer idata;
int n,a,b,flag;
while ((input = Main.ReadLn (255)) != null)
{
flag = 0;
idata = new StringTokenizer (input);
n = Integer.parseInt (idata.nextToken());
if (n == 1)
{
System.out.println("Jolly");
continue;
}
array = new int[n - 1];
for(int loop = 0;loop < n - 1;loop++)
{
array[loop] = loop + 1;
}
a = Integer.parseInt (idata.nextToken());
b = Integer.parseInt (idata.nextToken());
if (abs(a - b) >= n)
{
System.out.println("Not jolly");
}
else
{
for(int loop2 = 0;loop2 < n - 1;loop2++)
if (array[loop2] == abs(a - b))
{
array[loop2] = 0;
break;
}
for(int loop=1;loop < n - 1;loop++)
{
a = b;
b = Integer.parseInt (idata.nextToken());
if (abs(a - b) >= n)
{
System.out.println("Not jolly");
flag = 1;
break;
}
else
{
for(int loop2 = 0;loop2 < n - 1;loop2++)
if (array[loop2] == abs(a - b))
{
array[loop2] = 0;
break;
}
}
}
if (flag == 0)
{
for(int loop = 0;loop < n - 1;loop++)
if(array[loop] != 0)
{
System.out.println("Not jolly");
flag = 1;
break;
}
if (flag == 0) System.out.println("Jolly");
}
}
}
}
}[/java]

[pavelph]

Hm... You have very big code and I can't understand it. Please write steps of algo that you program do.

[Morning]

I'm sorry my english is poor.I just make a array that contains the numbers from 1 to n so that i can compare with the absolutes differences
[java]
import java.io.*;
import java.util.*;

class Main
{
static int abs(int number)
{
if (number < 0)
{
return -1 * number;
}
else return number;
}
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
}

void Begin()
{
int array[];
String input;
StringTokenizer idata;
int n,a,b,flag;
while ((input = Main.ReadLn (255)) != null)
{
flag = 0;
idata = new StringTokenizer (input);
n = Integer.parseInt (idata.nextToken());

if (n == 1)
{
//a single integer is always Jolly
System.out.println("Jolly");
continue;
}
array = new int[n - 1];
//i put the numbers from 1 to n in array so that i can compare with the absolutes differences
for(int loop = 0;loop < n - 1;loop++)
{
array[loop] = loop + 1;
}

a = Integer.parseInt (idata.nextToken());
b = Integer.parseInt (idata.nextToken());
//a and b are two absolutes differences one by one in input
if (abs(a - b) >= n)
{
System.out.println("Not jolly");
}
else
{
for(int loop2 = 0;loop2 < n - 1;loop2++)
if (array[loop2] == abs(a - b))
{
array[loop2] = 0;
break;
//give 0 to array[loop2] to mark this value has appeared in absolutes differences
}
for(int loop=1;loop < n - 1;loop++)
{
a = b;
b = Integer.parseInt (idata.nextToken());
//a and b are next two absolutes differences
if (abs(a - b) >= n)
{
System.out.println("Not jolly");
flag = 1;
//flag mark that it is definitely "Not jolly"
break;
}
else
{
for(int loop2 = 0;loop2 < n - 1;loop2++)
if (array[loop2] == abs(a - b))
{
array[loop2] = 0;
break;
//just like what i did above
}
}
}
if (flag == 0)//if whether it is "Not jolly" is not sure
{
for(int loop = 0;loop < n - 1;loop++)
if(array[loop] != 0)
{
//if any element in array not equals to 0,then it must be "Not jolly"
System.out.println("Not jolly");
flag = 1;
break;
}
if (flag == 0) System.out.println("Jolly");
}
}
}
}
}[/java][/java]

[pavelph]

Sorry, I know java very and very bad. All that I can help you is my algo:
1) read input to array a[1..n] of integer
2) create other array b[1..n] of boolean

Code: Select all

for i=1 to n-1 do
  if |a[i] - a[i+1]|>=n then /Not jolly/
  else b[|a[i] - a[i+1]|]:=true

for i=1 to n-1 if not b[i] then /Not jolly/
else {if b[i]=true for all i=1..n-1} /Jolly/

Maybe it's help you.[/code][/pascal]

[pavelph]

Sorry, I know java very and very bad. All that I can help you is my algo:
1) read input to array a[1..n] of integer
2) create other array b[1..n] of boolean

Code: Select all

for i=1 to n-1 do
  if |a[i] - a[i+1]|>=n then /Not jolly/
  else b[|a[i] - a[i+1]|]:=true

for i=1 to n-1 if not b[i] then /Not jolly/
else {if b[i]=true for all i=1..n-1} /Jolly/

Maybe it's help you.

[Morning]

Hey.Thanks so much:)i'll check it

[epidemyk]

Time limit exceeded, not sure why...

[c]
#include <stdio.h>
#include <math.h>

int main(void)
{
int num;
int i;
int n1, n2;

while(scanf("%d", &num) != EOF)
{
int stat[num];
int jolly = 1;
int val = 0;
char temp;

for(i=0; i<num; i++)
{
stat = 0;
}


if (num == 1)
{
printf("Jolly\n");
scanf("%d", &num); /* Consume extra number */
goto end; /* Break loop */
} else {

scanf("%d", &n2); /* First number into n2 */
for(i=1; i<num; i++)
{
n1 = n2; /* First number into n1 */
scanf("%d", &n2); /* Next number into n2 */
val = abs(n1-n2);

if (val < num) /* If val is in the bounds */
stat[abs(n1-n2)] = 1; /* Then set flag in array */
else /* Else print Not Jolly */
{ /* and consume rest of line */
printf("Not jolly\n");
scanf("%c", &temp);
while (temp != '\n')
scanf("%c", &temp);
goto end;
}
}

for(i=1; i<num; i++)
jolly = jolly && stat; /* Boolean with all values */

if (jolly == 1)
printf("Jolly\n");
else
printf("Not jolly\n");

} /* End If */
end:
} /* End While */

return 0;
}
[/c]

[midra]

Why the output for: 6 1 4 3 7 5 10 is Jolly???
the sequence is 3 1 4 2 5 and to be Jolly, it must change in values of 1

Here is my code, it works with many inputs, but not with this because I think that :6 1 4 3 7 5 10 is NOT JOLLY


[c]#include <stdio.h>
#include <math.h>

int main()
{
int n,i,x[3001],s=0,temp[3001];

scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &x);
if (n==1)
{
printf("Jolly");
return 0;
}

for (i=1; i<=n-2; i++)
{
if (abs(abs(x)-abs(x[i+1]))==abs(abs(x[i+1])-abs(x[i+2])-1))
{
s++;
if(n>=3) /*1 3 2 4 */
{
if(abs(abs(x)-abs(x[i+1]))==abs(abs(x[i+2])-abs(x[i+3])))
{
printf("Not Jolly");
return 0;
}
}
}
else if (abs(abs(x)-abs(x[i+1]))==abs(abs(x[i+1])-abs(x[i+2])+1))
{
s++;
if(n>=3) /*1 3 2 4 */
{ if(abs(abs(x)-abs(x[i+1]))==abs(abs(x[i+2])-abs(x[i+3])))
{
printf("Not Jolly");
return 0;
}
}
}
}
if (s>=n-2)
printf("Jolly");
else
printf("Not Jolly");

return 0;
}[/c]


thanks for reading!

[dominus]

Can anybody tell me why this code returns WA?

Code: Select all

#include <iostream.h>

int abs(int i)
{
    if (i>0){ return i;}
    else { return -i;}
}

int main()
{
    int inp1=0, inp2=0, jolly=1, n=0, i=0, a[3005]={0};
    
    while( (cin >> n) && n )
    {
        jolly=1;
        cin >> inp1;        //first number
        for(i=1;i<n;i++)    //other numbers
        {
            cin >> inp2;
            a[abs(inp1-inp2)] = 1;
            inp1=inp2;
        }
        for(i=1;i<n;i++)    //cycle from 1 to N-1
        {
            if(!a[i])       //every cell must be >0
            {
                jolly=0;
            }
            a[i]=0;
        }
        a[n]=0;
        n=0;
        
        cout << (jolly ? "Jolly" : "Not yolly") << endl;
    }
    return 0;
}

[Kentaro]

You spelled the output wrong?
"Jolly", "Not jolly"

In your code I see:
"Jolly", "Not yolly"

[Kentaro]

1 4 3 7 5 10 is a jolly jumper of 6 integers.
(equivalent to input: "6 1 4 3 7 5 10")

|1 - 4| = 3
|4 - 3| = 1
|3 - 7| = 4
|7 - 5| = 2
|5 - 10| = 5

All the numbers from 1 to 5 are seen at least once in the above list so the sequence is a jolly jumper. They don't have to be seen in any particular order.
EDIT: Read the problem statement carefully.
EDIT 2: Edited to make a clearer explanation.

[dominus]

Yeah, you are totally right. What a stupid I am... . Thanks for notifying me