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

jasonw
New poster
Posts: 1
Joined: Wed Aug 27, 2008 8:21 pm

Re: 10038 - Jolly Jumpers

Post by jasonw »

Hi all, i did this problem before, but my code is too messy, and i was not sure how to nicely parse the input (i used getchar()). After reading through the entire thread, i thought Hikaru78's parsing is the best, so i took a part of his program and implemented my logic, but it still didn't work, can anyone take a look and see what is wrong? (my old program is about 3 times as long):

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0

int main (void) {
   char jj[3002];
   int prev, curr, i, isJolly, total, diff;
   while (scanf("%d",&total) != EOF) {
      scanf("%d",&prev);
      isJolly = 1;
      for (i = 0; i < total; i++) jj[i] = 0;
      for (i = 1; i < total; i++) {
         scanf("%d",&curr);
         diff = abs(curr - prev);
         if (DEBUG) printf("%d ",diff);
         if((diff<= 0) || (diff >= total) || jj[diff]){
            isJolly = 0;
         } else {
            jj[diff] = 1;
         }
         prev = curr;
      }
      printf(isJolly?"Jolly\n":"Not Jolly\n");
   }
}
my test cases:
4 1 3 5 7
15 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106
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
1000 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154 172 191 211 232 254 277 301 326 352 379 407 436 466 497 529 562 596 631 667 704 742 781 821 862 904 947 991 1036 1082 1129 1177 1226 1276 1327 1379 1432 1486 1541 1597 1654 1712 1771 1831 1892 1954 2017 2081 2146 2212 2279 2347 2416 2486 2557 2629 2702 2776 2851 2927 3004 3082 3161 3241 3322 3404 3487 3571 3656 3742 3829 3917 4006 4096 4187 4279 4372 4466 4561 4657 4754 4852 4951 5051 5152 5254 5357 5461 5566 5672 5779 5887 5996 6106 6217 6329 6442 6556 6671 6787 6904 7022 7141 7261 7382 7504 7627 7751 7876 8002 8129 8257 8386 8516 8647 8779 8912 9046 9181 9317 9454 9592 9731 9871 10012 10154 10297 10441 10586 10732 10879 11027 11176 11326 11477 11629 11782 11936 12091 12247 12404 12562 12721 12881 13042 13204 13367 13531 13696 13862 14029 14197 14366 14536 14707 14879 15052 15226 15401 15577 15754 15932 16111 16291 16472 16654 16837 17021 17206 17392 17579 17767 17956 18146 18337 18529 18722 18916 19111 19307 19504 19702 19901 20101 20302 20504 20707 20911 21116 21322 21529 21737 21946 22156 22367 22579 22792 23006 23221 23437 23654 23872 24091 24311 24532 24754 24977 25201 25426 25652 25879 26107 26336 26566 26797 27029 27262 27496 27731 27967 28204 28442 28681 28921 29162 29404 29647 29891 30136 30382 30629 30877 31126 31376 31627 31879 32132 32386 32641 32897 33154 33412 33671 33931 34192 34454 34717 34981 35246 35512 35779 36047 36316 36586 36857 37129 37402 37676 37951 38227 38504 38782 39061 39341 39622 39904 40187 40471 40756 41042 41329 41617 41906 42196 42487 42779 43072 43366 43661 43957 44254 44552 44851 45151 45452 45754 46057 46361 46666 46972 47279 47587 47896 48206 48517 48829 49142 49456 49771 50087 50404 50722 51041 51361 51682 52004 52327 52651 52976 53302 53629 53957 54286 54616 54947 55279 55612 55946 56281 56617 56954 57292 57631 57971 58312 58654 58997 59341 59686 60032 60379 60727 61076 61426 61777 62129 62482 62836 63191 63547 63904 64262 64621 64981 65342 65704 66067 66431 66796 67162 67529 67897 68266 68636 69007 69379 69752 70126 70501 70877 71254 71632 72011 72391 72772 73154 73537 73921 74306 74692 75079 75467 75856 76246 76637 77029 77422 77816 78211 78607 79004 79402 79801 80201 80602 81004 81407 81811 82216 82622 83029 83437 83846 84256 84667 85079 85492 85906 86321 86737 87154 87572 87991 88411 88832 89254 89677 90101 90526 90952 91379 91807 92236 92666 93097 93529 93962 94396 94831 95267 95704 96142 96581 97021 97462 97904 98347 98791 99236 99682 100129 100577 101026 101476 101927 102379 102832 103286 103741 104197 104654 105112 105571 106031 106492 106954 107417 107881 108346 108812 109279 109747 110216 110686 111157 111629 112102 112576 113051 113527 114004 114482 114961 115441 115922 116404 116887 117371 117856 118342 118829 119317 119806 120296 120787 121279 121772 122266 122761 123257 123754 124252 124751 125251 125752 126254 126757 127261 127766 128272 128779 129287 129796 130306 130817 131329 131842 132356 132871 133387 133904 134422 134941 135461 135982 136504 137027 137551 138076 138602 139129 139657 140186 140716 141247 141779 142312 142846 143381 143917 144454 144992 145531 146071 146612 147154 147697 148241 148786 149332 149879 150427 150976 151526 152077 152629 153182 153736 154291 154847 155404 155962 156521 157081 157642 158204 158767 159331 159896 160462 161029 161597 162166 162736 163307 163879 164452 165026 165601 166177 166754 167332 167911 168491 169072 169654 170237 170821 171406 171992 172579 173167 173756 174346 174937 175529 176122 176716 177311 177907 178504 179102 179701 180301 180902 181504 182107 182711 183316 183922 184529 185137 185746 186356 186967 187579 188192 188806 189421 190037 190654 191272 191891 192511 193132 193754 194377 195001 195626 196252 196879 197507 198136 198766 199397 200029 200662 201296 201931 202567 203204 203842 204481 205121 205762 206404 207047 207691 208336 208982 209629 210277 210926 211576 212227 212879 213532 214186 214841 215497 216154 216812 217471 218131 218792 219454 220117 220781 221446 222112 222779 223447 224116 224786 225457 226129 226802 227476 228151 228827 229504 230182 230861 231541 232222 232904 233587 234271 234956 235642 236329 237017 237706 238396 239087 239779 240472 241166 241861 242557 243254 243952 244651 245351 246052 246754 247457 248161 248866 249572 250279 250987 251696 252406 253117 253829 254542 255256 255971 256687 257404 258122 258841 259561 260282 261004 261727 262451 263176 263902 264629 265357 266086 266816 267547 268279 269012 269746 270481 271217 271954 272692 273431 274171 274912 275654 276397 277141 277886 278632 279379 280127 280876 281626 282377 283129 283882 284636 285391 286147 286904 287662 288421 289181 289942 290704 291467 292231 292996 293762 294529 295297 296066 296836 297607 298379 299152 299926 300701 301477 302254 303032 303811 304591 305372 306154 306937 307721 308506 309292 310079 310867 311656 312446 313237 314029 314822 315616 316411 317207 318004 318802 319601 320401 321202 322004 322807 323611 324416 325222 326029 326837 327646 328456 329267 330079 330892 331706 332521 333337 334154 334972 335791 336611 337432 338254 339077 339901 340726 341552 342379 343207 344036 344866 345697 346529 347362 348196 349031 349867 350704 351542 352381 353221 354062 354904 355747 356591 357436 358282 359129 359977 360826 361676 362527 363379 364232 365086 365941 366797 367654 368512 369371 370231 371092 371954 372817 373681 374546 375412 376279 377147 378016 378886 379757 380629 381502 382376 383251 384127 385004 385882 386761 387641 388522 389404 390287 391171 392056 392942 393829 394717 395606 396496 397387 398279 399172 400066 400961 401857 402754 403652 404551 405451 406352 407254 408157 409061 409966 410872 411779 412687 413596 414506 415417 416329 417242 418156 419071 419987 420904 421822 422741 423661 424582 425504 426427 427351 428276 429202 430129 431057 431986 432916 433847 434779 435712 436646 437581 438517 439454 440392 441331 442271 443212 444154 445097 446041 446986 447932 448879 449827 450776 451726 452677 453629 454582 455536 456491 457447 458404 459362 460321 461281 462242 463204 464167 465131 466096 467062 468029 468997 469966 470936 471907 472879 473852 474826 475801 476777 477754 478732 479711 480691 481672 482654 483637 484621 485606 486592 487579 488567 489556 490546 491537 492529 493522 494516 495511 496507 497504 498502 499
5 1 4 1 3 2
result:
Not Jolly
Jolly
Jolly
Not Jolly
Not Jolly
Jolly
Jolly
Not Jolly
Jolly
Jolly
Jolly
Not Jolly
Not Jolly
Jolly
Jolly
Not Jolly
Jolly
Not Jolly
Jolly
Not Jolly
Not Jolly
I believe its all correct, thanks a lot for looking through it!

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

10038 - Jolly Jumpers -> WA

Post by carliros »

where's wrong ?

the answers of this code is correct for jasonw' inputs (try the previous post's test inputs)

[c]

Code: Select all

#include <stdio.h>

int abs(int n);

int main(){
    freopen("P10038.in", "rt", stdin);
    
    int i, tam, bandera2, result, x, y, z, rAntX, rAntY, resto;
    
    while(scanf("%d", &tam) != EOF){
        if(tam > 3){
            scanf("%d %d %d", &x, &y, &z);
            rAntX = abs(x-y);
            rAntY = abs(y-z);
            resto = rAntX - rAntY;
            bandera2 = 1;
            result = 1;
            
        	for(i = 3; i < tam; i++){
        	    scanf("%d", &x);
            	if(bandera2){
                	rAntX = abs(z-x);
                	if((resto != 0)&&(resto == (rAntY-rAntX)) && (rAntX > 0) && (rAntX < tam)){ /*significa que hay una secuencia, then save the datas*/
                	    rAntY = rAntX;
                	    z = x;
                    }else {
                        bandera2 = 0;
                        result = 0;
                    }
                }
             }
         }else {
             for(i = 0; i < tam; i++){
        	    scanf("%d", &x);
             }
             if(tam <= 2) result = 1;
             else result = 0;
         }
         if(result){
             printf("%s\n", "Jolly");
         }else {
             printf("%s\n", "Not jolly");
         }
    }
}

int abs(int n){
    return ((n>=0)?(n):((-1)*n));
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10038 - Jolly Jumpers

Post by sazzadcsedu »

what should be output for a single num???

like: 1 1
1 5
1 10 etc.

and whats wrong with my code???
got WA.

Code: Select all

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

                            int  main()

                         { 
                           int num[3050];
                           int count[3050]; 
                           int  flag;
                           int i,j,n;  
                          
                           while(scanf("%d",&n)==1)

                       {
                           flag=1;
	                  memset(count,0,sizeof(count));
                           
                           for(i=0;i<n;i++)
                          {
                           
                          scanf("%d",&num[i]);   
 
                          }    
                                
                           for(i=0;i<n-1;i++)
                          {
                              j=abs(num[i]-num[i+1]);
		
                             if (j<3000)      
                              count[j]=1; 
                               
                          }

                           for(i=1;i<n;i++)
                         {
                 
                               if(count[i]==0)
			      {  
                               printf("not jolly\n");
                               flag=0;
                               break;  
			      } 
                         }  
                           
			     if(flag==1)
                            printf("jolly\n");

                        }   
                              return 0;

		}

 
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10038 - Jolly Jumpers

Post by newkid »

The output for a single num is Jolly..
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10038 - Jolly Jumpers

Post by newkid »

to sazzadcsedu:

1. Try this case
2 1 4000
the output should be 'Not jolly'

2. Output should be
Jolly & Not jolly
you are prinring jolly & not jolly.. (wrong case)
hmm..

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10038 - Jolly Jumpers

Post by sazzadcsedu »

thanx a lot newkid.
got AC.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10038 - Jolly Jumpers

Post by newkid »

you are welcome..
BTW: Don't mind but your code is horrible to read.. tabs, spaces.. and almost absolutely no indentation.. Please try to fix it first. Your code will be much readable and you can find small bugs easily..
Cheers
hmm..

adibbd
New poster
Posts: 1
Joined: Mon May 04, 2009 7:25 pm

10038- i've WA!pls help me any1..the code is giving output..

Post by adibbd »

#include <iostream>
using namespace std;

int abs(int x)
{
return x<0?(-x):x ;
}

int main ()
{
int i,n,j,num,x;
char jolly[3001],store[3000];

while(cin>>n)
{

for (i=0;i<n;i++)
{
cin>>num;
jolly=num;
}

jolly=NULL;

i=0,j=0;

while(1)
{

x=jolly-jolly[i+1];
x=abs(x);
store[j++]=x;
i++;

if (jolly[i+1]==NULL)
break;
}

store[j]=NULL;

int len=strlen(store),val=1;

for (i=1;i<n;i++)
{
int found=0;
for(j=0;j<len;j++)
{
if (store[j]==i)
{
found=1;
break;
}
}

if (found==0)
{
val=0;
break;
}

}

if (val)
cout<<"Jolly"<<endl;
else
cout<<"Not jolly"<<endl;

}


return (0);


}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10038 - Jolly Jumpers

Post by helloneo »

Try this case

Code: Select all

2 0 257
Output

Code: Select all

Not jolly

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10038 - Jolly Jumpers

Post by asif_khan_ak_07 »

cant find the problem. Got WA

Code: Select all

#include<stdio.h>

int main()
{

	
//freopen("jol.txt","r",stdin);

long double a[30000],n,sum,k,temp;


while((scanf("%Lf",&n)==1))
{

sum=0;
k=0;
	
	for(int i=0;i<n;i++)
	scanf("%Lf",&a[i]);
		
	

	for(int j=1;j<n;j++)
	{
		sum=a[j]-a[j-1];

		if(sum<0)
			sum=-sum;
	
		k=k+sum;
	}

temp=0;

for(int m=1;m<n;m++)
temp=temp+m;


if(k==temp)
printf("Jolly\n");

else 
printf("Not jolly\n");

}

return 0;

}

panda_coder
New poster
Posts: 7
Joined: Mon Jun 08, 2009 4:02 am

Re: 10038 - Jolly Jumpers

Post by panda_coder »

I have NO IDEA why my program gets WA...
Could you please look at my code? I've tried every test cases posted here.

Code: Select all


package Chap2;

import java.io.IOException;
import java.util.*;

public class JollyJumpers implements Runnable{
	

	static String readLine(int maxLength) {
		byte line[] = new byte[maxLength];
		int length = 0;
		int input = -1;
		try {
			while(length < maxLength) {
				input = System.in.read();
				if((input < 0) || (input == '\n')) break;
				line[length++] += input;
			}
			if((input<0) && (length ==0)) return null;
			return new String(line, 0, length);
		}catch(IOException e) {
			return null;
		}
	}
	
	public static void main(String[] args) {
		JollyJumpers jp = new JollyJumpers();
		jp.run();
		
	} 
	
	public void run() { 
		String line;
		boolean ifjoly;
		List<Integer> numbers = new ArrayList<Integer>();
	
		while((line = readLine(750))!=null) {
			ifjoly = true;
			numbers.clear();
			Integer jolyMax = null;
			
			StringTokenizer st = new StringTokenizer(line);
			while(st.hasMoreTokens()) {
				if(jolyMax == null) jolyMax = Integer.parseInt(st.nextToken());
				else numbers.add(Integer.parseInt(st.nextToken()));
			}
			boolean[] jolyCheck = new boolean[jolyMax+1]; 
			
			if(numbers.size() > 0) {
					//	int cur = 0;
			int cur = numbers.get(0);    
			int dif = 0;
			for(int i : numbers) {
				dif = Math.abs(cur-i);
				if(dif <= jolyMax-1 && dif >=1)
					jolyCheck[dif] = true;
				cur = i;
			}
			} 
			for(int i=1; i<=jolyMax-1; i++) {
				if(!jolyCheck[i]) {
					ifjoly = false;
					break;
				}
			}
			
			if(ifjoly) System.out.println("Jolly");		
			else System.out.println("Not jolly");
	}
		

}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10038 - Jolly Jumpers

Post by mf »

asif_khan_ak_07 wrote:cant find the problem. Got WA
And I can't find the reason why you shouldn't get WA. Your program doesn't do what the problem statement asks you.
panda_coder wrote:I have NO IDEA why my program gets WA...
Could you please look at my code? I've tried every test cases posted here.
Why are you using this procedure?

Code: Select all

	static String readLine(int maxLength) {
		byte line[] = new byte[maxLength];
		int length = 0;
		int input = -1;
		try {
			while(length < maxLength) {
				input = System.in.read();
				if((input < 0) || (input == '\n')) break;
				line[length++] += input;
			}
			if((input<0) && (length ==0)) return null;
			return new String(line, 0, length);
		}catch(IOException e) {
			return null;
		}
	}
It was written back in the days when UVa used old and under-featured jdk 1.1 (or maybe it was some old gcj)

Now we have jdk 1.6 in all its glory, you can just use java.io.BufferedReader, and avoid guessing maximum input line size (which you guessed wrong.)

panda_coder
New poster
Posts: 7
Joined: Mon Jun 08, 2009 4:02 am

Re: 10038 - Jolly Jumpers

Post by panda_coder »

It was written back in the days when UVa used old and under-featured jdk 1.1 (or maybe it was some old gcj)

Now we have jdk 1.6 in all its glory, you can just use java.io.BufferedReader, and avoid guessing maximum input line size (which you guessed wrong.)
Thank you for your suggestion. I did not know the reason I was using that procedure, I just adopted it because programming-challenges.com recommended the procedure when submitting it.

Even though I changed my input procedure, I'm still getting WA.

The first one is accepted code in C, and the second one is my modifed Java code. I'm still getting WA in programming challenges.com, and "Run-time error" in Uva website. I'm starting to feel like there is something wrong that I know of because I always get Run-time error in uva. Is there a testcase without any input that makes a null-point exception or something?

Anyway, I don't see the reason why the second Java code is not accepted; while those two codes do seem to work in the same way to me..

Accepted C code

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 3000
#define abs(x) ((x) < 0? (-(x)) : (x))

int main(void) {
int present[MAX_N];
int n,i,prev,curr,diff,jolly;
char line[50000];

	while(scanf("%d", &n) == 1) {
		jolly = 1;
		for(i=1;i<=n;i++) {
			present[i] = 0;
		}
		scanf("%d", &prev);
		for(i=1;i<n;i++) {
			scanf("%d", &curr);
			diff = abs(prev-curr);
			if(diff <= 0 || diff >= n || present[diff]) {
				jolly = 0;
				break;
			}

			present[diff] = 1;
			prev = curr;
		}
		gets(line);
		puts(jolly? "Jolly" : "Not jolly");
	}
}

Run-time error(uva) / Wrong Answer(programming challenges) in Java

Code: Select all

import java.io.*;
import java.util.*;

public class JollyJumpers implements Runnable{
	
	public static void main(String[] args) {
		JollyJumpers jp = new JollyJumpers();
		jp.run();
		
	} 
	
	public void run() { 
		String line;
		boolean ifjoly = true;
		int[] numbers = null;
		boolean[] jolyCheck = null; 
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try { 
		while((line = br.readLine()).length() > 0) {
			ifjoly = true;
			int jolyMax, dif = 0, prev, cur;
			StringTokenizer st = new StringTokenizer(line);
			jolyMax = Integer.parseInt(st.nextToken());
			numbers = new int[jolyMax];
		
			jolyCheck = new boolean[3000];
			Arrays.fill(jolyCheck, false);
			
			for(int i=0;i<jolyMax;i++)		
				numbers[i] = Integer.parseInt(st.nextToken());
			
			prev = numbers[0];    
			
			for(int i=1; i<jolyMax; i++){
				cur = numbers[i];
				dif = abs(cur, prev);
				if(dif >= jolyMax || dif <= 0 || jolyCheck[dif]) {
					ifjoly = false;
					break;
				}
				
				else 
					jolyCheck[dif] = true;
				
				prev = cur;
			}
			
			if(ifjoly) System.out.println("Jolly");		
			else System.out.println("Not jolly");
			}
		}catch(IOException io)
		{
			io.printStackTrace();
		}
	}

		
	
	public int abs(int a, int b) {
		if(a>b) return (a-b);
		else return (b-a);	
	}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10038 - Jolly Jumpers

Post by mf »

This is wrong:
while((line = br.readLine()).length() > 0) {
On end-of-file BufferedReader.readLine() returns null, and an attempt to dereference null throws NullPointerException.

meheraj
New poster
Posts: 1
Joined: Mon Jun 15, 2009 7:05 pm

Re: 10038 - Jolly Jumpers WA...why...please tell me..

Post by meheraj »

:o
#include<iostream>
using namespace std;
int main()
{
int i,j;
long arr[3001],d[3001],n;
while (cin>>n&&n>0)
{
for (i=0;i<n;i++)
cin>>arr;
for (i=0;i<n-1;i++)
{
d=abs(arr[i+1]-arr);
if (d>n-1)break;
}
if (d>n-1)
cout<<"Not jolly"<<endl;
else
//cout<<"Jolly"<<endl;
{
for (i=0;i<n-1;i++)
{
for (j=0;j<n-1;j++)
if (d==d[j])break;
}
if (d==d[j])
cout<<"Not jolly"<<endl;
else
cout<<"Jolly"<<endl;
}

}
return 0;
}

Post Reply

Return to “Volume 100 (10000-10099)”