## 10038 - Jolly Jumpers

**Moderator:** Board moderators

### 10038 why WA

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

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?

Code: Select all

```
Cut. AC.
```

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?

### 10038

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", ¤t);
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;
}
}
```

How is it suppose to respond to a line with

Code: Select all

`1 x`

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!

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

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

UFCG Brazil - Computer Science graduate student

http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

### 10038 jolly jumper

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

im feeling that i don't understand what the problem wants specially these lines

and here is my code i hope i understand the problemA 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.

Code: Select all

```
code deleted
```

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

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) {
...
}
```

### 10038 WA,Need assist

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;
}
}
}
}
}
```

thanks for helping

### Re: 10038 WA,Need assist

Hi, thirddawn.

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.

Best regards.

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

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

### 10038 why WA?

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;
}
```

### Finally i found my mistake and got AC

/*

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

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 (diffwhile ((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;

}{

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;

}

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

#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

#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++)

{cfor(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(cif(c

*<0)*

cc

*=-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".

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

>"<

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

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.

Because there are many input lines in the input file,

your code should read until reach the EOF.

Best regards.