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
Location: Bangladesh,Dhaka.
Contact:

i think u couldn't understand the problem yet

Post by osan » Fri Dec 12, 2003 7:25 pm

CHECK THIS INPUT :roll:

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

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

10038

Post by youareaverage » Wed Jan 14, 2004 1:41 am

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
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

INPUT && OUTPUT

Post by osan » Sat Jan 17, 2004 12:13 pm

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)

Post by Morning » Sat Jan 31, 2004 2:37 pm

[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]
"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

Post by pavelph » Sat Jan 31, 2004 4:49 pm

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

Post by Morning » Sat Jan 31, 2004 5:06 pm

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

Post by pavelph » Sat Jan 31, 2004 10:56 pm

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

Post by pavelph » Sat Jan 31, 2004 10:57 pm

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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Sat Jan 31, 2004 10:59 pm

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

Post by epidemyk » Tue Feb 03, 2004 7:08 am

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:

Post by midra » Sat Feb 14, 2004 8:28 am

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! :D

dominus
New poster
Posts: 2
Joined: Fri Feb 27, 2004 5:52 pm
Location: Estonia

10038 WA

Post by dominus » Fri Feb 27, 2004 5:57 pm

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
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by Kentaro » Tue Mar 02, 2004 3:03 pm

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
Location: Canada, eh?

Post by Kentaro » Tue Mar 02, 2004 3:10 pm

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

Post by dominus » Tue Mar 02, 2004 7:18 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”