10038 - Jolly Jumpers

[Sedefcho]

No problem, you haven't troubled me at all. I hope
I've helped you at least a little bit.

[chunyi81]

Why does the following C++ code give WA for problem 10038?

Code: Select all

Cut. AC.

I have tried with all sample inputs in this forum and all output ok.
This code compiles and runs fine in dev-C++.
Can anyone give me IOs which could make my code give WA?

Algorithm:
If number of integers len is 1, output "Jolly", read in the single integer also.
Else read in the first two integers, check if the absolute value of the difference is < len, set flags accordingly, even if the difference is 0.
Because if difference is 0, then answer will be not jolly, and this is eventually detected. If difference is >= len, then not jolly, read in remaining integers and output not jolly. Else set flags[temp] to true, temp is the difference between successive pairs. Process the remaining integers.
Then I check the flags array from 1 to n (not 0 to n), and if one of the positions from 1 to n is false, then not jolly, else all positions from 1 to n are true, then jolly. I cannot figure out where this algorithm can go wrong.

Note that I free memory every test case for the flags array and allocate again using the new keyword.

Also I used math.h instead of cmath to avoid compile error from the OJ.
Anyone can help please?

[chunyi81]

Found my mistake. I should have initialised all the elements of the bool flags array for every new test case.

[agolsme]

Code: Select all

#include<stdio.h>

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

int main()
{
    int i=1,n=0,j,flag;
    int current,count,last;
    int stuffs[5000] = {0};
    while(scanf("%d", &n) != EOF)
    {
        scanf("%d", &last);
        while(i < n)
        {
            scanf("%d", &current);
            if(stuffs[abs(current - last)] == 0)
                stuffs[abs(current - last)] = 1;
            last = current;
            i++;
        }
        j =1;
        flag = 0;
        for(; j < n; j++)
        {
            if(flag != 1)
            {
                if(stuffs[j] != 1)
                {
                    printf("Not Jolly\n");
                    flag = 1;
                }
            }
            stuffs[j]=0;
        }
        if(n == 1)
        {
            if(last != 1 && last != 2 && last != 0)
            {
                printf("Not Jolly\n");
                flag = 1;
            }
        }
        if(flag != 1)
            printf("Jolly\n");
        i = 1;
    }
}

I've tried the various inputs that I found through search for those problem. It works fine for those. Yet I still get a WA.

How is it suppose to respond to a line with

Code: Select all

1 x

I had assumed that that would only be Jolly with 1 1?

[chunyi81]

For 1 x, the output is Jolly. Hope this helps.

Even if you have catered your code to that, you will still get WA. You are making the same mistake I did for this problem. Did you initialise the stuffs array for every new test case?

[Jemerson]

wow, in fact it would help too much if you used the Code tag...
I couldnt understand your code very well but i'm gonna divide my observation in two points, ok? the first thing i noticed is that the buffer length in the method readLine() is toooo small (255) Once the input may contain 3000 number in a line
Actually i'm using this method, that guarantees me enough memory to hold the line and suggest you to use it too!

Code: Select all

    static String readln() {
        String newLine = System.getProperty("line.separator");
        StringBuffer buffer = new StringBuffer();
        int car = -1;
        try {
            car = System.in.read();
            while ((car > 0) && (car != newLine.charAt(0))) {
                buffer.append((char) car);
                car = System.in.read();
            }
            if (car == newLine.charAt(0))
                System.in.skip(newLine.length() - 1);
        } catch (java.io.IOException e) { return (null); }
        if ((car < 0) && (buffer.length() == 0))
            return (null); /* eof */
        return (buffer.toString()).trim();
    }

Second, i'd like to give you an approach for solve this problem, use it if you wish to.

If n = 1 Jolly
Else
Build a 3000 length array
Keep all the differences in this array
Verify if all terms between 1 and n-1 are in the array (I did it by quicksorting first)


I used this and got Acceptance in in 0.082, which is a regular time.

Good Luck

[Moussa]

i've submited it many time and it either give me a WA or Time Limit Exceed
im feeling that i don't understand what the problem wants specially these lines

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the
differences between successive elements take on all possible values 1 through n−1.

and here is my code i hope i understand the problem

Code: Select all

code deleted

[chunyi81]

What does your code output for the following test case?

Input
1 1

Correct output is "Jolly", but I think your code will crash for this test case.

And instead of cin.eof(), which can cause problems if you have blank lines at the end of the input, your code will print extra lines of "Not jolly", or possibly TLE, try this:

Code: Select all

while (cin >> j) {

...

}

And shift all the declarations in the while loop to before the while loop.

[Moussa]

hay it's accepted thx
the problem was in the case u told me
thx

[thirddawn]

Code: Select all

#include <stdio.h>

int main(){
	int line[3000],number,i,ans,last,counter=1;
	while (scanf("%d",&number)==1){
		for (i=0;i<number;i++)
			scanf("%d",&line[i]);
		for (i=0;i<number-1;i++){
			if (line[i]>line[i+1]){
				ans = line[i] - line[i+1];
				counter = counter + 1;
			}
			if (line[i]<line[i+1]){
				ans = line[i+1] - line[i];
				counter = counter + 1;
			}
			if (counter == number - 1){
				printf("Jolly");
				return 0;
			}
			if (i==0){
				last = ans;
				continue;
			}
			if (i>0){
				if (ans - last == 1){
					last = ans;
					continue;
				}
				else{
					printf("Not jolly");
					return 0;
				}
			}
		}
	}
}

the sample is ok, but when I send it just tell me wrong answer

thanks for helping

[tan_Yui]

Hi, thirddawn.

the sample is ok, but when I send it just tell me wrong answer

Really?
Your code couldn't output even for sample input.
Try to check again....

By the way, please use the following i/o for your debugging, if you want.
Input :

Code: Select all

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

Output should be :

Code: Select all

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

Best regards.

[vice]

Why my code give wa? I have tried lots of sample input but it's still wa

Code: Select all

/* ACM uva 10038 - JollyJumper */

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

void Jolly(int size)
{
	int i = 0;
	int val = 0;
	int val2 = 0;
	int counter = 0;
	int isJolly = 1;
	int diff[size];
	scanf(" %d",&val);
	while ((counter++)<(size-1))
	{	
		scanf(" %d",&val2);
		if (abs(val-val2)>(size-1))
		{
			isJolly = 0;
		}
		else
			diff[abs(val-val2)] = 1;
		val = val2;
	}

	for (i = 1; i<size; i++)
	{
		if (diff[i] != 1)
		{
			isJolly = 0;
			break;
		}
	}
	if (isJolly)
		printf("%s\n","Jolly");
	else
		printf("%s\n","Not jolly");
}

int main(int argc, char *argv[])
{
	int size = 0;
	while (scanf("%d",&size)!=EOF)
	{
		Jolly(size);
		size = 0;
	}
	return 0;
}

[vice]

/*
ACM uva 10038 - JollyJumper
Note: !!!!Don't forget to initialize array to 0
*/

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

void Jolly(int size)
{
int i = 0;
int val = 0;
int val2 = 0;
int counter = 0;
int isJolly = 1;
int diff[size];
scanf(" %d",&val);
for (i = 0;i<size ;i++ )
diff = 0;

while ((counter++)<(size-1))
{
scanf(" %d",&val2);
//printf("val:%d, val2:%d",val,val2);
if (abs(val-val2)<=(size-1))
diff[abs(val-val2)] = 1;

val = val2;
}

for (i = 1; i<size; i++)
{
if (diff != 1)
{
isJolly = 0;
break;
}
}
if (isJolly)
printf("%s\n","Jolly");
else
printf("%s\n","Not jolly");
}

int main(int argc, char *argv[])
{
int size = 0;
//freopen("input.txt", "r", stdin);
while (scanf("%d",&size)!=EOF)
{
Jolly(size);
size = 0;
}
return 0;
}

[10599]

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

int main()
{ long int n,a[3000],b[3000],c[3000],d[3000],e,i,k,t;
scanf("%ld",&n);
for(i=0;i<n;i++)
{scanf("%ld",&a);}
for(k=0,t=1;k<(n-1);k++,t++)
{b[k]=t;d[k]=0;}
for(i=0;i<(n-1);i++)
{c=a[i+1]-a;
if(c<0)
c=-c;

for(k=0;k<(n-1);k++)
{for(e=0;e<(n-1);e++)
{if(c[k]==b[e])
d[e]++;}
}
}
for(k=0;k<(n-1);k++)
{if(d[k]==0)
{printf("Not jolly\n");
goto ending;}
}
printf("Jolly\n");
ending:
return 0;
}

Please tell me why I got "WA".
>"<

[tan_Yui]

Your code only outputs for a input of first line.
Because there are many input lines in the input file,
your code should read until reach the EOF.

Best regards.