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

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni »

thanks, but my code prints "Jolly" for n == 1;
when n == 1 on main(), last becames zero on jolly(), hence the test if( last ) fails, so 1 is returned;
can you see another wrong???
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

progman
New poster
Posts: 4
Joined: Fri Jun 23, 2006 4:39 am

10038 Evil WA

Post by progman »

I've tried a number of test cases, many from the forum and my program matches all the outputs, but I still get wrong answer. Can anyone help? Thanks.


#ifdef ONLINE_JUDGE
#define NDEBUG
#endif

#include<iostream>
#include <cassert>
#include <cstdio>
#include<cmath>
#include <algorithm>

using namespace std;


int array[3000];
int n;
int a[3000];
bool jolly;
int diff;

inline static bool read () {

if (scanf("%d", &n) == EOF)
return false;
for(int i = 0; i < abs(n); i++)

scanf("%d", &a);

return true;}

inline static void eval () {

for(int z = 0; z < abs(n); z++)
array[z] = 0;

for(int g = 0; g<(abs(n)-1); g++){
diff = abs(a[g] - a[g+1]);
array[diff] = 1;
}

for(int r = 0; r < abs(n); r++)
if(array[r] == 0)
jolly = false;
else jolly = true;



for(int x = 0; x<(abs(n)-1); x++) {
if(abs(a[x] - a[x+1]) == 0 || abs(a[x] - a[x+1]) >= abs(n))
jolly = false;
}
if(abs(n) == 1)
jolly = true;
if(n == 0)
jolly = false;

}





inline static void print () {



if(jolly) cout<<"Jolly\n";
else cout<<"Not jolly\n";

}

int main () {
#ifndef ONLINE_JUDGE
freopen("jolly jumpers.in", "r", stdin);
#endif
while (read()) {
eval();
print();

}
return 0;}

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

Sort your number first. Then do your job.

progman
New poster
Posts: 4
Joined: Fri Jun 23, 2006 4:39 am

Post by progman »

Thank you for your reply, but I don't quite understand it. I don't know what you mean by sorting my number. I also don't understand the need of sorting anything. The part of my code that deals with arrays basically checks if any differences in the sequence repeats and if so, it's not jolly. Thanks again.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni »

at least some input test ???
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

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

Post by chunyi81 »

Try the search function. There are some test cases lying around in older threads.

progman
New poster
Posts: 4
Joined: Fri Jun 23, 2006 4:39 am

10038 Program Crashes

Post by progman »

I keep getting WA even though I've checked multiple inputs/outputs that match mine. However, for some reason my program crashes for this particular input that I got from an older thread. I'm wondering if this is my problem and if anyone can help me with it. My code is pasted below. (I also wasn't sure how to deal with n < 0, but I've tried automatically returning "Not jolly" if that is the case or taking the absolute value of n then performing the calculations...either way I still get WA.)

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

#ifdef ONLINE_JUDGE
#define NDEBUG
#endif

#include<iostream>
#include <cassert>
#include <cstdio>
#include<cmath>
#include <algorithm>

using namespace std;


int array[3000];
int n;
int a[3000];
bool jolly;
int diff;

inline static bool read () {

if (scanf("%d", &n) == EOF)
return false;
for(int i = 0; i < abs(n); i++)

scanf("%d", &a);

return true;}

inline static void eval () {
if(n < 0) {
jolly = false;}
else{

for(int z = 0; z < abs(n); z++)
array[z] = 0;

for(int g = 0; g<(abs(n)-1); g++){
diff = abs(a[g] - a[g+1]);
array[diff] = 1;
}

for(int r = 0; r < abs(n); r++)
if(array[r] == 0)
jolly = false;
else jolly = true;



for(int x = 0; x<(abs(n)-1); x++) {
if(abs(a[x] - a[x+1]) == 0 || abs(a[x] - a[x+1]) >= abs(n))
jolly = false;
}
if(n == 1)
jolly = true;
if(n == 0)
jolly = false;

}
}




inline static void print () {



if(jolly) cout<<"Jolly\n";
else cout<<"Not jolly\n";

}

int main () {
#ifndef ONLINE_JUDGE
freopen("jolly jumpers.in", "r", stdin);
#endif
while (read()) {
eval();
print();

}
return 0;}

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

Your program should crash for Array index out of bounds.... Consider these line in your code
for(int g = 0; g<(abs(n)-1); g++){
diff = abs(a[g] - a[g+1]);
array[diff] = 1;
}
If the input is like
2 1 50000
Your program will try to index array[49999] which is not clearly good. so you have check cases where abs(diff) >= n ... and don't mark it in array.
Also there's shouldn't be cases like n < 0 .... but i'm not 100% sure.
Istiaque Ahmed [the LA-Z-BOy]

progman
New poster
Posts: 4
Joined: Fri Jun 23, 2006 4:39 am

Post by progman »

Thank you so much. I was able to fix my program with the crashing with that input, and in doing so, I figured out why I kept getting WA. Thanks again!!!!

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni »

hello,
what if I do the two last lines of your algorithm in one step, that is, after I calcule each difference, I can verify if the term is inside [1,n-1].
What you tell me about that? thats right?
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

spicy_hair
New poster
Posts: 7
Joined: Wed Jul 19, 2006 12:26 am
Location: Calgary, Canada

Post by spicy_hair »

to sohel:

your suggestion to habibiamin also helped me (ya...after 2 yearz :) ) thanx

bongssi
New poster
Posts: 14
Joined: Mon Jul 31, 2006 10:35 am

10038 WA!

Post by bongssi »

I got WA for 10038(Jolly Jumper). At first, I thought I misunderstood the problem, but I didn't. I don't know why my program isn't correct. Would you mind giving me an answer?

Here is my source code. :)

-----------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
int diff_break_out[3000];
int main(void){

int seq_num, is_jolly, old_num, new_num, i, diff;
while(scanf("%d", &seq_num) == 1){

for(i=0; i<3000; i++)
diff_break_out = 0;

is_jolly = 1;

if(seq_num!=0)
scanf("%d", &old_num);
else is_jolly = 0;

for(i=1; i<seq_num; i++){
scanf("%d", &new_num);
diff = abs(old_num - new_num);
/*printf("%d ", diff);*/

if(diff < 1 || diff > seq_num-1){
is_jolly = 0;
break;
}

else diff_break_out[diff-1]++;
old_num = new_num;
}

if(is_jolly){
for(i=0; i<seq_num-1; i++)
if(diff_break_out == 0){
is_jolly = 0;
break;
}
}

if(is_jolly) printf("Jolly\n");
else printf("Not jolly\n");

fflush(stdin);
}

return 0;
}
Last edited by bongssi on Fri Aug 11, 2006 8:18 pm, edited 1 time in total.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

I think n cound be 0, in which case you should output "Not jolly".

bongssi
New poster
Posts: 14
Joined: Mon Jul 31, 2006 10:35 am

Thanks. ^^; But I got WA again...

Post by bongssi »

the modified part of code..
-------------------------------------

for(i=0; i<2999; i++)
diff_break_out = 0;

is_jolly = 1;

if(seq_num!=0)
scanf("%d", &old_num);
else is_jolly = 0;

for(i=1; i<seq_num; i++){
scanf("%d", &new_num);
diff = abs(old_num - new_num);
printf("%d ", diff);

When seq_num is 0, it prints "Not jolly". But still wrong answer...
If when seq_num is 1, it should print "Not jolly", too??

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

1 is Jolly. It also seems that your array is not large enough. Try changing 2999 to 3000.

Post Reply

Return to “Volume 100 (10000-10099)”