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

Moecdx
New poster
Posts: 2
Joined: Sat Oct 22, 2005 8:28 am

10038 Time Limit Exceeded...beleive or not!!

Post by Moecdx » Fri Mar 31, 2006 7:21 am

I donno y am i getting Time Limit Exceeded for such a problem..my code is very straight forward,

Code: Select all

#include <iostream>

using namespace std;

const int MAX = 3000;

int main()
{
	int numElements;
	int elements[MAX];
	int diffs[MAX];
	int diff;
	int i;
	bool jolly;

	while(true)
	{
		jolly = true;
		cin>>numElements;
		if(numElements == 1)
		{
			cin>>numElements;
			cout<<"Jolly\n";
		}
		else if(numElements > 1)
		{
			for(i = 0; i < numElements; i++)
				cin>>elements[i];

			for(i = 1; i < numElements; i++)
			{
				diffs[i] = 0;
				if( elements[i-1] > elements[i] )
					diff =  elements[i-1] - elements[i];
				else
					diff =  elements[i] - elements[i-1];
				diffs[diff] = 1;
			}

			for(i = 1; i < numElements; i++)
				if(!diffs[i])
				{
					jolly = false;
					i = numElements;
				}

			if(jolly)
				cout<<"Jolly\n";
			else
				cout<<"Not jolly\n";
		}
	}
	return 0;
}
any clues??
Moe

Moecdx
New poster
Posts: 2
Joined: Sat Oct 22, 2005 8:28 am

comment added

Post by Moecdx » Fri Mar 31, 2006 7:24 am

Code: Select all

if(numElements == 1)
		{
			//This next line is to get the number, which i don care about, just put it in any variable
			cin>>numElements;
			cout<<"Jolly\n";
		}
Moe

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

Post by chunyi81 » Fri Mar 31, 2006 11:16 am

How does your code terminate when there is no more input?

You have a while(true) loop there but that is precisely causing time limit exceed. You can simply do this:

Code: Select all

while (cin >> numElements)

computer_sc_girl
New poster
Posts: 1
Joined: Fri Apr 07, 2006 12:48 pm

Post by computer_sc_girl » Fri Apr 07, 2006 12:51 pm

hey i have a wrong answer to the same problem

may code is as follows :

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

int main()
{
int x,arr[3000]={0},i=0,z[3000]={0},j=0,c=0;

while(cin>>x)
{
c=0;


for(i=0;i<x;i++)
{
cin>>arr;

}
for(j=0;j<x-1;j++)
{
z[j]=abs(arr[j]-arr[j+1]);

} j=0;
for(i=(x-1);i>=1;i--)
{
if(z[j]==i)c++;
j++;
}
if(c==(x-1))cout<<"Jolly"<<endl;
else cout<<"Not jolly"<<endl;

}



return 0;
}


does anyone know the reason ?![/b]

SiLwS
New poster
Posts: 6
Joined: Wed May 03, 2006 8:12 pm

RUntime error

Post by SiLwS » Thu May 04, 2006 10:18 am

Code: Select all

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int c[3000],a[3000],b,n,j,i,d,f[10000];
    i=1;
    while(scanf("%d",&n)!=EOF)
    {
           for(j=1;j<=n;j++)
           {scanf("%d",&a[j]);c[j]=0;}
           for(j=1;j<=n-1;j++)
           {
                 if(a[j]>a[j+1])
                 { 
                       b=a[j]-a[j+1];
                 }
                 else
                 {
                       b=a[j+1]-a[j];
                 }
                 c[b]=1;
           }
           d=0;
           for(j=1;j<=n-1;j++)
           {
                 if(c[j]==1)
                 {
                            d++;
                 }
           }
           if(d==(n-1))
           {
                     f[i]=1;
           }
           else
           {
                     f[i]=0;
           }
           i++;
    }
    i--;
    for(j=1;j<=i;j++)
    {
            if(f[j]==1)
            {printf("Jolly\n");}
            else
            {printf("Not jolly\n");}
    }
    return 0;
}
I've submited the code in programming-challenges and was accepted... here it wasn't.... Runtime error.... why is it?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu May 04, 2006 10:52 am

According to your implementation your array size should be 3000+.

Michfi
New poster
Posts: 1
Joined: Mon May 15, 2006 3:35 am

10038 Jolly Jumper WA Java

Post by Michfi » Tue May 16, 2006 2:08 am

Hi!


Who can help me with this code?

Code: Select all

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

class Main {
	public static void main(String args[]){
		
	StringTokenizer st;
	String zeile;
  
  		zeile = readLn(25500);
  		while(!zeile.equals(" ")){
		st=new StringTokenizer(zeile);
		int n = Integer.parseInt(st.nextToken());
		int[] a = new int[n];
		for(int i=1;i<=n;i++){
		a[i-1]= Integer.parseInt(st.nextToken());
		}
		boolean g = jolly(a);
		if(g) {System.out.println("Jolly");}
		else {System.out.println("Not jolly");}
		zeile=readLn(25500);
	}//while
	
	
	}
	
	static String readLn(int maxLg)
	{
	byte lin[] = new byte [maxLg];
	int lg=0,car=-1;
	
	try{
		while (lg<maxLg)
	{
		car=System.in.read();
		if((car<0)||(car=='\n')) break;
		lin[lg++]+=car;
	}
	}	
	catch(IOException e)
	{return(null);
	}
	
	if((car<0)&&(lg==0)) return(null);
	return (new String (lin,0,lg));
	
}	
	
	static boolean jolly(int[] a){
		boolean jolly=true;
		int z = a[0]-1;
		int[] c = new int[a.length-1];
		
		for(int i=1;i<a.length;i++) {
		c[i-1] = a[i];
		
		}
		
		boolean[] b = new boolean[c.length-1];
		for(int i=1;i<c.length;i++){
			if(java.lang.Math.abs(c[i]-c[i-1])>z||java.lang.Math.abs(c[i]-c[i-1])==0) {jolly=false;}
			else {b[java.lang.Math.abs(c[i]-c[i-1])-1]=true;}
	
		}
		
		
		for(int j=0;j<b.length;j++) {
			if(b[j]==false){jolly=false;}
			}
						
		
		return jolly;
		
	}
}

naga
New poster
Posts: 3
Joined: Fri Jun 02, 2006 11:02 pm
Contact:

10038

Post by naga » Fri Jun 02, 2006 11:05 pm

hi this is my program.It's saying WA.Can somebody look at my code.



/*@BEGIN_OF_SOURCE_CODE*/
#include <stdio.h>
#include<stdlib.h>


void q_sort(int *b, int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = b[left];
while (left < right)
{
while ((b[right] >= pivot) && (left < right))
right--;
if (left != right)
{
b[left] = b[right];
left++;
}
while ((b[left] <= pivot) && (left < right))
left++;
if (left != right)
{
b[right] = b[left];
right--;
}
}
b[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(b, left, pivot-1);
if (right > pivot)
q_sort(b, pivot+1,right);
}

int main()
{
int n,*a,*b,i,temp,count;
printf("Enter N,N integers for the jolly number test\n");
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
b=(int *)malloc(sizeof(int)*n);
/*allocatiing the arrays */
/*if(a==NULL)
printf("could not allocate memory \n");
else
printf("memory allocated\n");*/

for(i=0;i<n;i++)
{
scanf("%d",&temp);
a=temp;
}/*end of for */
/*calculating the absloute values*/
for(i=0;i<n-1;i++)
{
temp=a-a[i+1];
if(temp<0)
{
temp=temp* (-1);
b=temp;

}/*end of if */
else
{
b=temp;
}/*end of else*/
}/*end of for*/
/*for(i=0;i<n-1;i++)
printf("%d",b);*/
q_sort(b, 0, n- 2);
/*for(i=0;i<n-1;i++)
printf("%d",b);*/
for(i=1;i<n;i++)
{
if(b[i-1]==i)
count=1;
else
count=0;
}/* end of for */
if(count)
printf("Jolly\n");
else
printf("Not Jolly\n");
return 0;
}
/*@END_OF_SOURCE_CODE*/

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10038

Post by Martin Macko » Sat Jun 03, 2006 3:07 am

Post your problem to the forum about problems number 10000 to 10099: http://online-judge.uva.es/board/viewforum.php?f=9. There is a bigger chance to find somebody who can help you there.

Also, there are already a lot of topics on this problem. Eg., http://online-judge.uva.es/board/viewtopic.php?t=4137, http://online-judge.uva.es/board/viewtopic.php?t=4589, http://online-judge.uva.es/board/viewtopic.php?t=6666, http://online-judge.uva.es/board/viewtopic.php?t=7918, ... You can find them in the corresponding forum (the link above). First, read them and then if you won't find an answer on your question (eg., a test case for which your code gives a wrong answer), use one of them to post your question.

naga
New poster
Posts: 3
Joined: Fri Jun 02, 2006 11:02 pm
Contact:

10038 wrong answer

Post by naga » Sat Jun 03, 2006 3:26 am

hi this is my program.It's saying WA.Can somebody look at my code.



/*@BEGIN_OF_SOURCE_CODE*/
#include <stdio.h>
#include<stdlib.h>


void q_sort(int *b, int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = b[left];
while (left < right)
{
while ((b[right] >= pivot) && (left < right))
right--;
if (left != right)
{
b[left] = b[right];
left++;
}
while ((b[left] <= pivot) && (left < right))
left++;
if (left != right)
{
b[right] = b[left];
right--;
}
}
b[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(b, left, pivot-1);
if (right > pivot)
q_sort(b, pivot+1,right);
}

int main()
{
int n,*a,*b,i,temp,count;
printf("Enter N,N integers for the jolly number test\n");
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
b=(int *)malloc(sizeof(int)*n);
/*allocatiing the arrays */
/*if(a==NULL)
printf("could not allocate memory \n");
else
printf("memory allocated\n");*/

for(i=0;i<n;i++)
{
scanf("%d",&temp);
a=temp;
}/*end of for */
/*calculating the absloute values*/
for(i=0;i<n-1;i++)
{
temp=a-a[i+1];
if(temp<0)
{
temp=temp* (-1);
b=temp;

}/*end of if */
else
{
b=temp;
}/*end of else*/
}/*end of for*/
/*for(i=0;i<n-1;i++)
printf("%d",b);*/
q_sort(b, 0, n- 2);
/*for(i=0;i<n-1;i++)
printf("%d",b);*/
for(i=1;i<n;i++)
{
if(b[i-1]==i)
count=1;
else
count=0;
}/* end of for */
if(count)
printf("Jolly\n");
else
printf("Not Jolly\n");
return 0;
}
/*@END_OF_SOURCE_CODE*/

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sat Jun 03, 2006 10:02 am

I think you need to read the input/output specifications of the problem more carefully. Your program needs to handle more than one case (more than one line of input). That is, you should not have to restart your program for every new case, it should keep reading input until there is no more input to be read. You could use something like:

Code: Select all

while(scanf("%d",&n)!=-1)
Where -1 is the same as EOF (End of file).

I assume you meant to make the line "Enter N,N..." a comment, since it obviously should not be output.

marcpacios
New poster
Posts: 3
Joined: Tue Jun 13, 2006 4:08 pm

Post by marcpacios » Tue Jun 13, 2006 4:11 pm

I have this program and it says WA and I don't know why. Does anybody know what is wrong??

My program:

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

class Main{

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main(String args[]){
Main myWork = new Main();
myWork.Begin();
}

void Begin(){
String input;
StringTokenizer idata;
boolean[] jolly = new boolean[3000];
int num_linias = 0;
int cant_num;
int num1, num2;
boolean[] secuencia;
while((input = Main.ReadLn(25500))!=null){
idata = new StringTokenizer(input);
cant_num = Integer.parseInt(idata.nextToken());
secuencia = new boolean[cant_num];
for(int i=1;i<cant_num;i++){
secuencia=false;
}
num1 = Integer.parseInt(idata.nextToken());
jolly[num_linias]=true;
for(int i=1;i<cant_num;i++){
num2 = Integer.parseInt(idata.nextToken());
if(modulo(num2-num1)<cant_num && modulo(num2-num1)>0){
secuencia[modulo(num2-num1)] = true;
}else{
break;
}
num1=num2;
}
for(int i=1; i<cant_num;i++){
if(!secuencia){
jolly[num_linias]=false;
break;
}
}
num_linias++;
}
for(int i=0;i<num_linias;i++){
if(jolly){
System.out.println("Jolly");
}else{
System.out.println("Not jolly");
}
}
}

public int modulo(int num){
int modul=(num>0?num:-num);
return modul;
}
}

marcpacios
New poster
Posts: 3
Joined: Tue Jun 13, 2006 4:08 pm

Post by marcpacios » Tue Jun 13, 2006 4:35 pm

Ok, I've seen that the problem is that 25500 is littel for a line. I've used 90000 and now it is accepted :D

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

Post by beloni » Mon Jun 19, 2006 4:27 pm

hello, someone can tell me why my code was WA ???

Code: Select all


#include <stdio.h>
#include <stdlib.h>
#define SIZE 3001


int jolly( int *array, int last )
{
	int w, abs_diff;

	if( last )
		for( w = 0; w < last; w++ )
			{	
				abs_diff = abs(array[w] - array[w+1]);
				if( abs_diff < 1 || abs_diff > last ) 
					return 0;	
			}
	return 1;
}

int main()
{
	int input[SIZE], n, w;

	while( scanf( "%d", &n ) == 1 )
		{
			for( w = 0; w < n; w++ )
				scanf( "%d", &input[w] );
			if( jolly( input, n-1 ) )
				printf( "Jolly\n" );
			else
				printf( "Not jolly\n" );
		}

	return 0;
}
should I print "Not jolly." for n == 1 ???
thanks
"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 » Wed Jun 21, 2006 4:00 pm

You should print "Jolly" for n = 1.

See previous threads on this topic.

Post Reply

Return to “Volume 100 (10000-10099)”