10110 - Light, more light

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Rajib Mazumder
New poster
Posts: 14
Joined: Fri Jul 05, 2002 7:04 pm
Location: Bangladesh
Contact:

10110

Post by Rajib Mazumder » Mon Dec 09, 2002 5:52 pm

I can't understand why time limit exceed.... Can anybody help about the problem????
:cry: :( :cry: :(

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


long primes[10000];

long pc;
long p1,p2;


int isprime(long num)
{
???????????????
}


void genprime(long lim)
{
???????????????????
}


int main()
{

long i,k,n;
genprime(32767);
while(cin>>n)
{
if(isprime(n)) cout<<"no";
else
{
for(i=2;i<=n-1;i++)
{
if((n%i)==0) k++;
}
if(k%2==0) cout<<"yes";
else cout<<"no";
}
cout<<endl;
}
return 0;
}

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Dec 14, 2002 8:07 am

You needn't get all the divisors of the number - you just have to know whether it has even or odd number of divisors. There is a simple class of numbers that has odd number of divisors. Think of it. The problem can be solved in O(1) and you are trying to get AC in O(n). That won't work.

Good luck!

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

Helping Hand

Post by laboni » Tue Dec 17, 2002 9:51 pm

Here goes a hint - Square root the number , it has some special property, think of it.
bye :D

fzrone
New poster
Posts: 4
Joined: Mon Jan 06, 2003 2:26 pm
Location: Indonesia, Jakarta

little mistake

Post by fzrone » Mon Jan 06, 2003 3:32 pm

well 2^32-1 means unsigned long
that should correct problem

Calvin
New poster
Posts: 5
Joined: Sat Mar 08, 2003 12:50 pm

10110

Post by Calvin » Sat Mar 08, 2003 2:59 pm

See my code :

Code: Select all

#include <stdio.h>

int main()

{
	unsigned int num,i,j;
	char step;

	scanf("%d",&num);

	while (num!=0)
	{
		step=0;
		i=4;
		j=5;

		while (num>i && i>0)
		{
			i+=j;
			j+=2;
		}

		if (num==i) printf("yes\n");
		else printf("no\n");
		scanf("%d",&num);
	}

	return 0;
}
I try it with the bigest number 2^32-1 and it's very fast, why does it take too much time ??

Please help me !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! i am driven to
despair !!

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sat Mar 08, 2003 8:21 pm

for this problem you unnecessary to solve by brute force, you can solve this with math. this is the logic:
1. the question only check the last lamp (ON/OFF).
2. you can know it with the factor from the number of last lamp.
3. if sum of factor is odd, the last lamp condition is ON, and when sum of
factor is even, the last lamp condition is OFF.
(I'm sorry for my bad english)
this is a example for you:
1. n=6.
the factor is 1 2 3 6.
the n factor is 4, and the result is OFF.
2. n=16.
the factor is 1 2 4 8 16.
the n factor is 5, and the result is ON.
from this you can solve it by math. :)

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Apr 26, 2003 9:24 am

yes, that's right

but why I still got WA for this code :

Code: Select all

#include <math.h>
#include <stdio.h>

int main ( )
{
  unsigned long input , limit ;

/*  freopen ( "10110.in" , "r" , stdin ) ;
  freopen ( "10110.out" , "w" , stdout ) ;*/

  while ( 1 )
  {
	 scanf ( "%li" , &input ) ;

	 if ( input == 0 ) break ;

	 limit = sqrt ( input ) ;

	 if ( limit * limit == input )
		printf ( "yes\n" ) ;
	 else
		printf ( "no\n" ) ;
  }

  return 0 ;
}
Explanation :
I use the square root of input to determine if the divisor of the input is odd or even. Am I right to use this algorythm ?

For Calvin :
try to use unsigned long instead of unsigned int

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat Apr 26, 2003 1:53 pm

yes the algorithm is right

int and long int is just the same here,
before I know that I also post something
like

Code: Select all

use long instead of int
what different here is long long int which
has 64 bit.

If I'm not mistaken int and long int
which are used here has 32 bit.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sat Apr 26, 2003 3:24 pm

hello, almost human.......

for sqrt() your data type must use double, not integer. :wink:

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat Apr 26, 2003 5:12 pm

Hi Hisoka,

My Ac-ed program not using double,
I used long long int and get Acc

I don't know maybe just some
rounding precission.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sun Apr 27, 2003 6:41 am

I changed my code and use float instead of long and I 've got AC for this.

but I still wonder why I should changed it into float ?? Any suggestion ... ?

What I've changed :

Code: Select all

float input , limit ;

Code: Select all

scanf ( "%lf" , &input ) ;

Code: Select all

limit = ceil ( sqrt ( input ) ) ;

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sun Apr 27, 2003 7:26 am

hello......

Deddy one can use long long for this problem. but I don't know about that, because as far as I know sqrt only work in float or another float. you can get more explanation from help in your bc 3.1.

Code: Select all

double sqrt(double);

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo » Wed Sep 03, 2003 6:12 am

I've got AC by using

[c]
double n, factor;

factor = floor( sqrt(n) );

if(n - factor*factor < 0.00000001)
printf("yes\n");
else
printf("no\n");[/c]

also got AC by using
[c]
long long n, factor;

factor = (long long) sqrt(n);

if(n == factor*factor)
printf("yes\n");
esle
printf("no\n");[/c]

But I think that the second method is more dangerous than the first one.
Because I force double turning into long long, possibly losing data.

For this prob, it's all ok :wink:

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

10110 - WA, help...

Post by Bug! » Wed Nov 19, 2003 6:51 am

Code: Select all

result=(long)sqrt(n);
  if(result*result==n)
     printf("yes\n");
  else printf("no\n");
is my algorithm correct??? I've tried with the sample input and it's work..
Please correct me if i'm wrong
Thanx..

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Nov 19, 2003 8:34 am

Yes it is correct. :wink:

Post Reply

Return to “Volume 101 (10100-10199)”