10139 - Factovisors

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10139 - Factovisors

Post by .. » Sat Jan 26, 2002 2:44 pm

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Jan 27, 2002 4:28 pm

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Jan 27, 2002 4:31 pm

btw, your output is correct

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Jan 27, 2002 9:49 pm

Thanks for your reply~~
I got accepted now~

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10139

Post by htl » Sun May 11, 2003 4:30 pm

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
New poster
Posts: 3
Joined: Tue Jun 03, 2003 5:02 pm
Contact:

10139 WA

Post by dreeamersbee » Wed Jun 04, 2003 5:05 am

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.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Jun 04, 2003 7:07 am

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

dreeamersbee
New poster
Posts: 3
Joined: Tue Jun 03, 2003 5:02 pm
Contact:

I have just changed it

Post by dreeamersbee » Thu Jun 05, 2003 9:45 am

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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Jun 05, 2003 11:06 am

Hello, ... try the following input:

Code: Select all

1 0
0 1
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

dreeamersbee
New poster
Posts: 3
Joined: Tue Jun 03, 2003 5:02 pm
Contact:

Post by dreeamersbee » Fri Jun 06, 2003 7:44 am

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]

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

...

Post by Even » Tue Jun 10, 2003 3:07 pm

Maybe you can try this

Input

5 5

Output

5 divides 5!

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

10139

Post by czar » Mon Jun 23, 2003 10:04 pm

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
New poster
Posts: 12
Joined: Sun Jun 01, 2003 12:21 pm
Location: Pune, India

(factorial == EOF) ??????????

Post by technogeek » Tue Jun 24, 2003 2:51 am

[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]
I wanted to change the world, but they didn't give me the source code.

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

Post by czar » Tue Jun 24, 2003 4:46 am

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
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

Post by czar » Tue Jun 24, 2003 6:59 pm

Nevermind, I found the problem

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: Bing [Bot] and 1 guest