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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

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

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

10038 why WA

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

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

agolsme
New poster
Posts: 6
Joined: Tue Mar 08, 2005 5:22 am

10038

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by 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 :o
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
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Moussa
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

10038 jolly jumper

Post by 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 :cry:

Code: Select all

code deleted
Last edited by Moussa on Sun Nov 26, 2006 1:08 am, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

Post by Moussa »

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

thirddawn
New poster
Posts: 9
Joined: Sat Oct 15, 2005 4:41 am

10038 WA,Need assist

Post by 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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10038 WA,Need assist

Post by 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
New poster
Posts: 3
Joined: Thu May 12, 2005 6:09 pm
Contact:

10038 why WA?

Post by 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
New poster
Posts: 3
Joined: Thu May 12, 2005 6:09 pm
Contact:

Finally i found my mistake and got AC

Post by 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
New poster
Posts: 3
Joined: Sat Nov 19, 2005 11:24 am

10038wa.....>O<....C

Post by 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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10038wa.....>O<....C

Post by 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.

Post Reply

Return to “Volume 100 (10000-10099)”