10038 - Jolly Jumpers

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Contact:

i think u couldn't understand the problem yet

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
Jolly
Not Jolly
Not Jolly
Jolly
Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
Not Jolly
this time WA
what next...............?

youareaverage
New poster
Posts: 1
Joined: Wed Jan 14, 2004 1:38 am

10038

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;
//Execution.
while ( cin >> arraySize )
{
for ( counter = 0; counter < arraySize; counter++ )
{
cin >> array[ counter ];
}
jolly( array, arraySize );
}
return 0;
}
[/cpp]

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Contact:

INPUT && OUTPUT

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
this time WA
what next...............?

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

10038 why WA(Jolly Jumpers using Java)

[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)
{
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]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
Hm... You have very big code and I can't understand it. Please write steps of algo that you program do.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
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)
{
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]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
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/

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
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/

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
Hey.Thanks so much:)i'll check it
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

epidemyk
New poster
Posts: 3
Joined: Tue Feb 03, 2004 7:01 am

10038 Jolly Jumpers - Time Limit Exceeded

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
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
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,s=0,temp;

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
New poster
Posts: 2
Joined: Fri Feb 27, 2004 5:52 pm
Location: Estonia

10038 WA

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={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
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
You spelled the output wrong?
"Jolly", "Not jolly"

In your code I see:
"Jolly", "Not yolly"
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
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.
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

dominus
New poster
Posts: 2
Joined: Fri Feb 27, 2004 5:52 pm
Location: Estonia
Yeah, you are totally right. What a stupid I am... . Thanks for notifying me