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!

[wyvmak]

i should thank you. coz i got WA. and i think the input you set are already the most tricky.

what about:
2 0
1 1
2 1

and have you tried big numbers?check the spelling, "divide" and divides".
check the output.

[wyvmak]

btw, your output is correct

[..]

Thanks for your reply~~
I got accepted now~

[htl]

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]

[dreeamersbee]

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]

[turuthok]

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-

[dreeamersbee]

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]

[/quote]

[turuthok]

Hello, ... try the following input:

Code: Select all

1 0
0 1

-turuthok-

[dreeamersbee]

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]

[Even]

Maybe you can try this

Input

5 5

Output

5 divides 5!

[czar]

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]

[technogeek]

[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]

[czar]

yes that works. I originally had

[c]while(scanf("%i", &factorial) == 1) {
//Do stuff
}[/c]

but still got the same output limit exceeded error. I still have no clue as to why I am getting an output limited exceeded error.

[czar]

Nevermind, I found the problem