10110  Light, more light
Moderator: Board moderators

 New poster
 Posts: 14
 Joined: Fri Jul 05, 2002 7:04 pm
 Location: Bangladesh
 Contact:
10110
I can't understand why time limit exceed.... Can anybody help about the problem????
#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<=n1;i++)
{
if((n%i)==0) k++;
}
if(k%2==0) cout<<"yes";
else cout<<"no";
}
cout<<endl;
}
return 0;
}
#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<=n1;i++)
{
if((n%i)==0) k++;
}
if(k%2==0) cout<<"yes";
else cout<<"no";
}
cout<<endl;
}
return 0;
}

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Helping Hand
Here goes a hint  Square root the number , it has some special property, think of it.
bye
bye
little mistake
well 2^321 means unsigned long
that should correct problem
that should correct problem
10110
See my code :
I try it with the bigest number 2^321 and it's very fast, why does it take too much time ??
Please help me !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! i am driven to
despair !!
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;
}
Please help me !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! i am driven to
despair !!
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.
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.

 Learning poster
 Posts: 93
 Joined: Sun Jan 12, 2003 3:30 pm
yes, that's right
but why I still got WA for this code :
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
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 ;
}
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
yes the algorithm is right
int and long int is just the same here,
before I know that I also post something
like
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.
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
has 64 bit.
If I'm not mistaken int and long int
which are used here has 32 bit.

 Learning poster
 Posts: 93
 Joined: Sun Jan 12, 2003 3:30 pm
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 :
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 ) ) ;
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.
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);
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
[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
10110  WA, help...
Code: Select all
result=(long)sqrt(n);
if(result*result==n)
printf("yes\n");
else printf("no\n");
Please correct me if i'm wrong
Thanx..