10139 - Factovisors
Moderator: Board moderators
10139 - Factovisors
I already got 10+ WA on this question.....
can anyone give me some tricky input?
and if the following I/O is correct?
input:
0 0
1 0
0 1
output:
0 does not divide 0!
0 does not divide 1!
1 divides 0!
can anyone give me some tricky input?
and if the following I/O is correct?
input:
0 0
1 0
0 1
output:
0 does not divide 0!
0 does not divide 1!
1 divides 0!
10139
I think my algorithm seems OK. But it always gets WA. Is there something wrong with my code??
[c]
#include<stdio.h>
#define MAX 23171
#define KEPT 1
#define DELETED 0
#define YES 1
#define NO 0
void main(void)
{
int count,check_m,check_n;
char *sieve,error;
long *prime,x,i,j,m,n,temp1,temp2;
sieve=(char *)malloc(sizeof(char)*MAX);
prime=(long *)malloc(sizeof(long)*4792);
prime[0]=2,count=1;
for(x=0;x<MAX;x++)
sieve[x]=KEPT;
for(x=0;x<MAX;x++)
if(sieve[x]==KEPT)
{
i=2*x+3;
prime[count++]=i;
for(j=i+x;j<MAX;j+=i)
sieve[j]=DELETED;
}
free(sieve);
while(scanf("%ld %ld",&n,&m)!=EOF)
{
if(m==0)
{
printf("0 does not divide %ld!\n",n);
continue;
}
if(n==0 || n==1)
{
if(m==1)
printf("%ld divides %ld!\n",m,n);
else
printf("%ld does not divide %ld!\n",m,n);
continue;
}
if(m<=n)
{
printf("%ld divides %ld!\n",m,n);
continue;
}
for(x=0,temp1=m,error=NO;x<count && prime[x]*prime[x]<=m;x++)
{
check_m=check_n=0;
while(temp1%prime[x]==0)
{
temp1/=prime[x];
check_m++;
}
for(temp2=n;temp2/prime[x]!=0;)
{
check_n+=temp2/prime[x];
temp2/=prime[x];
}
if(check_m>check_n)
{
error=YES;
break;
}
}
if(error)
printf("%ld does not divide %ld!\n",m,n);
else
{
if(temp1>1)
{
if(temp1<=n)
printf("%ld divides %ld\n",m,n);
else
printf("%ld does not divide %ld!\n",m,n);
}
else
printf("%ld divides %ld!\n",m,n);
}
}
free(prime);
}
[/c]
[c]
#include<stdio.h>
#define MAX 23171
#define KEPT 1
#define DELETED 0
#define YES 1
#define NO 0
void main(void)
{
int count,check_m,check_n;
char *sieve,error;
long *prime,x,i,j,m,n,temp1,temp2;
sieve=(char *)malloc(sizeof(char)*MAX);
prime=(long *)malloc(sizeof(long)*4792);
prime[0]=2,count=1;
for(x=0;x<MAX;x++)
sieve[x]=KEPT;
for(x=0;x<MAX;x++)
if(sieve[x]==KEPT)
{
i=2*x+3;
prime[count++]=i;
for(j=i+x;j<MAX;j+=i)
sieve[j]=DELETED;
}
free(sieve);
while(scanf("%ld %ld",&n,&m)!=EOF)
{
if(m==0)
{
printf("0 does not divide %ld!\n",n);
continue;
}
if(n==0 || n==1)
{
if(m==1)
printf("%ld divides %ld!\n",m,n);
else
printf("%ld does not divide %ld!\n",m,n);
continue;
}
if(m<=n)
{
printf("%ld divides %ld!\n",m,n);
continue;
}
for(x=0,temp1=m,error=NO;x<count && prime[x]*prime[x]<=m;x++)
{
check_m=check_n=0;
while(temp1%prime[x]==0)
{
temp1/=prime[x];
check_m++;
}
for(temp2=n;temp2/prime[x]!=0;)
{
check_n+=temp2/prime[x];
temp2/=prime[x];
}
if(check_m>check_n)
{
error=YES;
break;
}
}
if(error)
printf("%ld does not divide %ld!\n",m,n);
else
{
if(temp1>1)
{
if(temp1<=n)
printf("%ld divides %ld\n",m,n);
else
printf("%ld does not divide %ld!\n",m,n);
}
else
printf("%ld divides %ld!\n",m,n);
}
}
free(prime);
}
[/c]
-
- New poster
- Posts: 3
- Joined: Tue Jun 03, 2003 5:02 pm
- Contact:
10139 WA
DreamersBee wrote: I keep getting wrong answer.
what is the wrong of this problem?
I can't find the wrong.
Anybody can help me to give a counter-example where my problem fails??
Thank's a million to everyone who can help my poblem.
[c]
#include<stdio.h>
float penyebut;
int check(unsigned long a,unsigned long b);
int see(unsigned long a,unsigned long b);
int prime(unsigned long a);
int main()
{
unsigned long bil,fak,i,k;
while(scanf("%lu %lu",&fak,&bil)==2) {
penyebut=bil;
if(prime(bil)) {
if(fak>bil) { penyebut=1; goto lanjut; }
else { penyebut=0; goto lanjut; }
}
for(i=2;i<=fak;i++)
{
if(prime(penyebut)) {
if(i<penyebut && fak>penyebut) penyebut=1; goto lanjut; }
else if(penyebut>fak) { goto lanjut; }
}
for(k=2;k<=i;k++) {
if(prime(k)) see(i,k);
if( penyebut<k) break;
}
if(penyebut<=1) break;
}
lanjut:
if(penyebut==1) printf("%lu divides %lu!\n",bil,fak);
else printf("%lu does not divide %lu!\n",bil,fak);
}
return 1;
}
int check(unsigned long a,unsigned long b) {
unsigned long hasil;
hasil=a%b;
if(hasil==0) return 1;
else return 0;
}
int see(unsigned long a,unsigned long b) {
if((int)a<=1||a<b) return 0;
if(check(a,b)) {
if(check(penyebut,b)) penyebut/=b;
see(a/b,b);
}
return 1;
}
int prime(unsigned long a)
{
int i,j,ctr=0;
for(i=2;i<a;i++) { if(a%i==0) {ctr++;break; }}
if(ctr==0) return 1;
else return 0;
}
[/c]
Last edited by dreeamersbee on Thu Jun 05, 2003 9:35 am, edited 1 time in total.
-
- Experienced poster
- Posts: 193
- Joined: Thu Sep 19, 2002 6:39 am
- Location: Indonesia
- Contact:
Hello, ... I think you need to be more careful on spelling ... It should say "divides" instead of "devides".
Moreover, you have a very huge potential of getting Time-Limit-Exceeded ... You need to implement better algorithm on the prime() function ... If you know a prime-number that is close to 2^31 ... use it on "bil", I'm sure your solution will be running for a long time ....
Not to mention there's a for loop -> for (i=2; i<=fak;i++) ....
-turuthok-
Moreover, you have a very huge potential of getting Time-Limit-Exceeded ... You need to implement better algorithm on the prime() function ... If you know a prime-number that is close to 2^31 ... use it on "bil", I'm sure your solution will be running for a long time ....
Not to mention there's a for loop -> for (i=2; i<=fak;i++) ....
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
-
- New poster
- Posts: 3
- Joined: Tue Jun 03, 2003 5:02 pm
- Contact:
I have just changed it
[/quote]dreamersbee wrote:hello, I have just changed my prime function,
and it becomes faster, but i still get Wrong Answer,
any other suggestion????
Thank's .
[c]
#include<stdio.h>
#include<math.h>
float penyebut;
int check(unsigned long a,unsigned long b);
int see(unsigned long a,unsigned long b);
int prime(unsigned long a);
int main()
{
unsigned long bil,fak,i,k;
while(scanf("%lu %lu",&fak,&bil)==2) {
penyebut=bil;
if(prime(bil)) {
if(fak>bil) { penyebut=1; goto lanjut; }
else { penyebut=0; goto lanjut; }
}
for(i=2;i<=fak;i++)
{
if(prime(penyebut)) {
if(i<penyebut && fak>penyebut) penyebut=1; goto lanjut; }
else if(penyebut>fak) { goto lanjut; }
}
for(k=2;k<=i;k++) {
if(prime(k)) see(i,k);
if( penyebut<k) break;
}
if(penyebut<=1) break;
}
lanjut:
if(penyebut==1) printf("%lu divides %lu!\n",bil,fak);
else printf("%lu does not divide %lu!\n",bil,fak);
}
return 1;
}
int check(unsigned long a,unsigned long b) {
unsigned long hasil;
hasil=a%b;
if(hasil==0) return 1;
else return 0;
}
int see(unsigned long a,unsigned long b) {
if((int)a<=1||a<b) return 0;
if(check(a,b)) {
if(check(penyebut,b)) penyebut/=b;
see(a/b,b);
}
return 1;
}
int prime(unsigned long a)
{
unsigned long limit,i;
if(a==2) return 1;
limit=(ceil)(sqrt(a));
for(i=2;i<=limit;i++) { if(a%i==0) return 0;}
return 1;
}
[/c]
-
- Experienced poster
- Posts: 193
- Joined: Thu Sep 19, 2002 6:39 am
- Location: Indonesia
- Contact:
Hello, ... try the following input:
-turuthok-
Code: Select all
1 0
0 1
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
-
- New poster
- Posts: 3
- Joined: Tue Jun 03, 2003 5:02 pm
- Contact:
dreamersbee wrote: hai....
I have added the validation for 1 and 0, have any other suggestion or input ????
Thank's
[c]
#include<stdio.h>
#include<math.h>
float penyebut;
int check(unsigned long a,unsigned long b);
int see(unsigned long a,unsigned long b);
int prime(unsigned long a);
int main()
{
unsigned long bil,fak,i,k;
while(scanf("%lu %lu",&fak,&bil)==2){
penyebut=bil;
if(fak==1 || fak==0) {
if(bil==1) penyebut=1;
else penyebut=0;
goto lanjut;
}
if(bil==0) { penyebut=0; goto lanjut; }
if(prime(bil)){
if(fak>bil) {penyebut=1; goto lanjut;}
else {penyebut=0; goto lanjut;}
}
for(i=2;i<=fak;i++)
{
if(prime(penyebut)){
if(i<penyebut && fak>penyebut) {penyebut=1; goto lanjut;}
else if(penyebut>fak){ goto lanjut;}
}
for(k=2;k<=i;k++){
if(prime(k)) see(i,k);
if(penyebut<k) break;
}
if(penyebut<=1) break;
}
lanjut:
if(penyebut==1) printf("%lu divides %lu!\n",bil,fak);
else printf("%lu does not divide %lu!\n",bil,fak);
}
return 1;
}
int check(unsigned long a,unsigned long b){
unsigned long hasil1;
hasil1=a%b;
if(hasil1==0) return 1;
else return 0;
}
int see(unsigned long a,unsigned long b){
if((int)a<=1 || a<b) return 0;
if(check(a,b)) {
if(check(penyebut,b)) penyebut/=b;
see(a/b,b);
}
return 1;
}
int prime(unsigned long a){
unsigned long limit,i;
if(a==2) return 1;
limit=(ceil)(sqrt(a));
for(i=2;i<=limit;i++){ if(a%i==0) return 0;}
return 1;
}
[/c]
10139
why am I getting an output limit exceeded error?
[c]#include<stdio.h>
#include<math.h>
#define UPPER_BOUND 66000
#define MAX_PRIME_FACTORS 20
int init(int *primes) {
unsigned long a[UPPER_BOUND];
unsigned long i = 0, j = 0;
for(i = 0; i < UPPER_BOUND; i++) a = 1;
for(i = 2; i < UPPER_BOUND; i++)
if(a)
for(j = i; j*i < UPPER_BOUND; j++)
a[j*i] = 0;
j = 0;
primes[++j] = 2;
for(i = 1; 2*i+1 < UPPER_BOUND; i++) {
if(a[2*i + 1])
primes[++j] = 2*i + 1;
}
primes[0] = j;
}
int get_prime_factors(unsigned long divisor, unsigned int *prime_factor, unsigned int *primes) {
int i = 1, j = 0;
unsigned long upper_bound = (unsigned long)sqrt((double)divisor) + 2;
while(divisor > 1) {
while(divisor % primes == 0 && divisor > 1) {
prime_factor[j++] = primes;
divisor /= primes;
}
if(primes > upper_bound && divisor > 1) {
prime_factor[j++] = divisor;
divisor = 0;
}
i++;
}
return j;
}
int check_divides(unsigned long factorial, unsigned long divisor, unsigned int *primes) {
unsigned int prime_factor[MAX_PRIME_FACTORS];
int number_of_factors = get_prime_factors(divisor, prime_factor, primes);
int i = 0, k = 0;
prime_factor[number_of_factors] = 0; /*SENTENIAL VALUE*/
for(i = 0; i < number_of_factors; i++) {
if(prime_factor == prime_factor[i+1])
k++;
else {
if(factorial/prime_factor < k+1)
return 0;
k = 0;
}
}
return 1;
}
int main() {
unsigned long factorial;
unsigned long divisor;
unsigned int primes[UPPER_BOUND];
int i = 0;
init(primes);
while(1) {
scanf("%i", &factorial);
if(factorial == EOF)
break;
scanf("%i", &divisor);
if(check_divides(factorial, divisor, primes))
printf("%i divides %i!\n", divisor, factorial);
else
printf("%i does not divide %i!\n",divisor, factorial);
}
return 0;
}[/c]
[c]#include<stdio.h>
#include<math.h>
#define UPPER_BOUND 66000
#define MAX_PRIME_FACTORS 20
int init(int *primes) {
unsigned long a[UPPER_BOUND];
unsigned long i = 0, j = 0;
for(i = 0; i < UPPER_BOUND; i++) a = 1;
for(i = 2; i < UPPER_BOUND; i++)
if(a)
for(j = i; j*i < UPPER_BOUND; j++)
a[j*i] = 0;
j = 0;
primes[++j] = 2;
for(i = 1; 2*i+1 < UPPER_BOUND; i++) {
if(a[2*i + 1])
primes[++j] = 2*i + 1;
}
primes[0] = j;
}
int get_prime_factors(unsigned long divisor, unsigned int *prime_factor, unsigned int *primes) {
int i = 1, j = 0;
unsigned long upper_bound = (unsigned long)sqrt((double)divisor) + 2;
while(divisor > 1) {
while(divisor % primes == 0 && divisor > 1) {
prime_factor[j++] = primes;
divisor /= primes;
}
if(primes > upper_bound && divisor > 1) {
prime_factor[j++] = divisor;
divisor = 0;
}
i++;
}
return j;
}
int check_divides(unsigned long factorial, unsigned long divisor, unsigned int *primes) {
unsigned int prime_factor[MAX_PRIME_FACTORS];
int number_of_factors = get_prime_factors(divisor, prime_factor, primes);
int i = 0, k = 0;
prime_factor[number_of_factors] = 0; /*SENTENIAL VALUE*/
for(i = 0; i < number_of_factors; i++) {
if(prime_factor == prime_factor[i+1])
k++;
else {
if(factorial/prime_factor < k+1)
return 0;
k = 0;
}
}
return 1;
}
int main() {
unsigned long factorial;
unsigned long divisor;
unsigned int primes[UPPER_BOUND];
int i = 0;
init(primes);
while(1) {
scanf("%i", &factorial);
if(factorial == EOF)
break;
scanf("%i", &divisor);
if(check_divides(factorial, divisor, primes))
printf("%i divides %i!\n", divisor, factorial);
else
printf("%i does not divide %i!\n",divisor, factorial);
}
return 0;
}[/c]
-
- New poster
- Posts: 12
- Joined: Sun Jun 01, 2003 12:21 pm
- Location: Pune, India
(factorial == EOF) ??????????
[cpp] if(factorial == EOF)
break;[/cpp]
Are you sure that works ?
I usually use : [cpp]if(feof(stdin)) break;[/cpp]
People often use the number of fields successfully scanned, returned by scanf(), to terminate their loop.... [cpp]while(scanf("%d",&variable)==1)
{
Dostuffwithvariable();
}[/cpp]
break;[/cpp]
Are you sure that works ?
I usually use : [cpp]if(feof(stdin)) break;[/cpp]
People often use the number of fields successfully scanned, returned by scanf(), to terminate their loop.... [cpp]while(scanf("%d",&variable)==1)
{
Dostuffwithvariable();
}[/cpp]
I wanted to change the world, but they didn't give me the source code.