10976 - Fractions Again?!

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

Moderator: Board moderators

Post Reply
rahurprem
New poster
Posts: 10
Joined: Mon Mar 28, 2005 5:59 pm
Location: Dhaka, Bangladesh
Contact:

10976 - Fractions Again?!

Post by rahurprem » Sun Feb 26, 2006 10:12 pm

This is my code -

Code: Select all

#include<stdio.h>

int k,x,y,i;

void list()
{
	for(y=k+1; y<=200000 ; y++)
	{		
		if( k*y %(y-k))continue;
		
		x= k*y / (y-k);

		if(x<y)break;
	
		if(k*y%(x+y)==0 && ((x*y /(x+y))==k))
			printf("1/%d = 1/%d + 1/%d\n",k,x,y);
	}
}

int main()
{
	//freopen("10976.in","r",stdin);
	//freopen("10976.out","w",stdout);

	while(scanf("%d",&k)==1)
	{
		printf("%d\n",k);
		list();
	}
	return 0;
}
Please help me in getting the errors I did here.

Ashis
Programmer? No, no, i am a speedy typist.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Feb 26, 2006 11:08 pm

I think that k * y can overflow.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

lyc
New poster
Posts: 2
Joined: Fri Jun 17, 2005 8:30 am

10976 - Fractions Again?!

Post by lyc » Thu Mar 09, 2006 5:40 pm

here's my code

Code: Select all

#include<stdio.h>
int main(void){
    int n,count,x,y,i;
    int temp[10000][2];
    while(scanf("%d",&n)!=EOF){
        memset(temp,0,sizeof(temp));
        count=0;
        y=n;
        while(y++){
            if((n*y)%(y-n)!=0)continue;
            x=(n*y)/(y-n);
            if(x*y%(x+y)!=0)continue;
            if(x*y/(x+y)!=n)continue;
            temp[count][0]=x;
            temp[count++][1]=y;
            if(x==y)break;
        }
        printf("%d\n",count);
        for(i=0;i<count;i++)
            printf("1/%d = 1/%d + 1/%d\n",n,temp[i][0],temp[i][1]);
    }
}            
but..just WA
maximum of n*y = 200000000
not overflow

something wrong?

thanks

ThanhNhan
New poster
Posts: 15
Joined: Sun Aug 08, 2004 12:24 am

Post by ThanhNhan » Tue Mar 28, 2006 3:01 am

The output k is not the same as the input k.
You should diff your output with the sample output.

Kaul
New poster
Posts: 4
Joined: Tue May 02, 2006 10:56 am
Location: Seoul, Korea
Contact:

10976 - Fractions Again?!

Post by Kaul » Sat May 06, 2006 10:10 am

My program got WA, and I'm testing many I/O.

Do you have some critical I/O?

Thx in advance!
______Have a Nice Day :)______
Dokdo is the Korean territory!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10976 Many I/O Please!

Post by tan_Yui » Mon May 08, 2006 3:32 am

I solved this problem with single loop (nearly...brute force).
I think it is important to take care about the range of iteration for keeping the time limit.

Following is the my input.
I hope this helps you.
3
1
4
15
92
653
589
793
2384
626
4338
3279
502
88
Output :
2
1/3 = 1/12 + 1/4
1/3 = 1/6 + 1/6
1
1/1 = 1/2 + 1/2
3
1/4 = 1/20 + 1/5
1/4 = 1/12 + 1/6
1/4 = 1/8 + 1/8
5
1/15 = 1/240 + 1/16
1/15 = 1/90 + 1/18
1/15 = 1/60 + 1/20
1/15 = 1/40 + 1/24
1/15 = 1/30 + 1/30
8
1/92 = 1/8556 + 1/93
1/92 = 1/4324 + 1/94
1/92 = 1/2208 + 1/96
1/92 = 1/1150 + 1/100
1/92 = 1/621 + 1/108
1/92 = 1/460 + 1/115
1/92 = 1/276 + 1/138
1/92 = 1/184 + 1/184
2
1/653 = 1/427062 + 1/654
1/653 = 1/1306 + 1/1306
5
1/589 = 1/347510 + 1/590
1/589 = 1/18848 + 1/608
1/589 = 1/11780 + 1/620
1/589 = 1/1550 + 1/950
1/589 = 1/1178 + 1/1178
5
1/793 = 1/629642 + 1/794
1/793 = 1/49166 + 1/806
1/793 = 1/11102 + 1/854
1/793 = 1/4514 + 1/962
1/793 = 1/1586 + 1/1586
14
1/2384 = 1/5685840 + 1/2385
1/2384 = 1/2844112 + 1/2386
1/2384 = 1/1423248 + 1/2388
1/2384 = 1/712816 + 1/2392
1/2384 = 1/357600 + 1/2400
1/2384 = 1/179992 + 1/2416
1/2384 = 1/91188 + 1/2448
1/2384 = 1/46786 + 1/2512
1/2384 = 1/40528 + 1/2533
1/2384 = 1/24585 + 1/2640
1/2384 = 1/21456 + 1/2682
1/2384 = 1/11920 + 1/2980
1/2384 = 1/7152 + 1/3576
1/2384 = 1/4768 + 1/4768
5
1/626 = 1/392502 + 1/627
1/626 = 1/196564 + 1/628
1/626 = 1/98595 + 1/630
1/626 = 1/1878 + 1/939
1/626 = 1/1252 + 1/1252
23
1/4338 = 1/18822582 + 1/4339
1/4338 = 1/9413460 + 1/4340
1/4338 = 1/6277086 + 1/4341
1/4338 = 1/4708899 + 1/4342
1/4338 = 1/3140712 + 1/4344
1/4338 = 1/2095254 + 1/4347
1/4338 = 1/1572525 + 1/4350
1/4338 = 1/1049796 + 1/4356
1/4338 = 1/701310 + 1/4365
1/4338 = 1/527067 + 1/4374
1/4338 = 1/352824 + 1/4392
1/4338 = 1/236662 + 1/4419
1/4338 = 1/178581 + 1/4446
1/4338 = 1/120500 + 1/4500
1/4338 = 1/82422 + 1/4579
1/4338 = 1/62419 + 1/4662
1/4338 = 1/43380 + 1/4820
1/4338 = 1/30366 + 1/5061
1/4338 = 1/23859 + 1/5302
1/4338 = 1/17352 + 1/5784
1/4338 = 1/13014 + 1/6507
1/4338 = 1/10845 + 1/7230
1/4338 = 1/8676 + 1/8676
5
1/3279 = 1/10755120 + 1/3280
1/3279 = 1/3587226 + 1/3282
1/3279 = 1/1197928 + 1/3288
1/3279 = 1/13116 + 1/4372
1/3279 = 1/6558 + 1/6558
5
1/502 = 1/252506 + 1/503
1/502 = 1/126504 + 1/504
1/502 = 1/63503 + 1/506
1/502 = 1/1506 + 1/753
1/502 = 1/1004 + 1/1004
11
1/88 = 1/7832 + 1/89
1/88 = 1/3960 + 1/90
1/88 = 1/2024 + 1/92
1/88 = 1/1056 + 1/96
1/88 = 1/792 + 1/99
1/88 = 1/572 + 1/104
1/88 = 1/440 + 1/110
1/88 = 1/330 + 1/120
1/88 = 1/264 + 1/132
1/88 = 1/209 + 1/152
1/88 = 1/176 + 1/176
Best regards.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10976 - Fractions Again?!

Post by DD » Tue Mar 15, 2011 10:46 pm

Kaul wrote:My program got WA, and I'm testing many I/O.

Do you have some critical I/O?

Thx in advance!
Maybe you should try to show your output for some random k, and we can check that for you.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

magurmach
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 10976 - Fractions Again?!

Post by magurmach » Tue Jun 26, 2012 9:46 am

Some Previous Input Output clarification:

Input:

Code: Select all

3
1
4
15
92
653
589
793
2384
626
4338
3279
502
88
Output:

Code: Select all

2
1/3 = 1/12 + 1/4
1/3 = 1/6 + 1/6
1
1/1 = 1/2 + 1/2
3
1/4 = 1/20 + 1/5
1/4 = 1/12 + 1/6
1/4 = 1/8 + 1/8
5
1/15 = 1/240 + 1/16
1/15 = 1/90 + 1/18
1/15 = 1/60 + 1/20
1/15 = 1/40 + 1/24
1/15 = 1/30 + 1/30
8
1/92 = 1/8556 + 1/93
1/92 = 1/4324 + 1/94
1/92 = 1/2208 + 1/96
1/92 = 1/1150 + 1/100
1/92 = 1/621 + 1/108
1/92 = 1/460 + 1/115
1/92 = 1/276 + 1/138
1/92 = 1/184 + 1/184
2
1/653 = 1/427062 + 1/654
1/653 = 1/1306 + 1/1306
5
1/589 = 1/347510 + 1/590
1/589 = 1/18848 + 1/608
1/589 = 1/11780 + 1/620
1/589 = 1/1550 + 1/950
1/589 = 1/1178 + 1/1178
5
1/793 = 1/629642 + 1/794
1/793 = 1/49166 + 1/806
1/793 = 1/11102 + 1/854
1/793 = 1/4514 + 1/962
1/793 = 1/1586 + 1/1586
14
1/2384 = 1/5685840 + 1/2385
1/2384 = 1/2844112 + 1/2386
1/2384 = 1/1423248 + 1/2388
1/2384 = 1/712816 + 1/2392
1/2384 = 1/357600 + 1/2400
1/2384 = 1/179992 + 1/2416
1/2384 = 1/91188 + 1/2448
1/2384 = 1/46786 + 1/2512
1/2384 = 1/40528 + 1/2533
1/2384 = 1/24585 + 1/2640
1/2384 = 1/21456 + 1/2682
1/2384 = 1/11920 + 1/2980
1/2384 = 1/7152 + 1/3576
1/2384 = 1/4768 + 1/4768
5
1/626 = 1/392502 + 1/627
1/626 = 1/196564 + 1/628
1/626 = 1/98595 + 1/630
1/626 = 1/1878 + 1/939
1/626 = 1/1252 + 1/1252
23
1/4338 = 1/18822582 + 1/4339
1/4338 = 1/9413460 + 1/4340
1/4338 = 1/6277086 + 1/4341
1/4338 = 1/4708899 + 1/4342
1/4338 = 1/3140712 + 1/4344
1/4338 = 1/2095254 + 1/4347
1/4338 = 1/1572525 + 1/4350
1/4338 = 1/1049796 + 1/4356
1/4338 = 1/701310 + 1/4365
1/4338 = 1/527067 + 1/4374
1/4338 = 1/352824 + 1/4392
1/4338 = 1/236662 + 1/4419
1/4338 = 1/178581 + 1/4446
1/4338 = 1/120500 + 1/4500
1/4338 = 1/82422 + 1/4579
1/4338 = 1/62419 + 1/4662
1/4338 = 1/43380 + 1/4820
1/4338 = 1/30366 + 1/5061
1/4338 = 1/23859 + 1/5302
1/4338 = 1/17352 + 1/5784
1/4338 = 1/13014 + 1/6507
1/4338 = 1/10845 + 1/7230
1/4338 = 1/8676 + 1/8676
5
1/3279 = 1/10755120 + 1/3280
1/3279 = 1/3587226 + 1/3282
1/3279 = 1/1197928 + 1/3288
1/3279 = 1/13116 + 1/4372
1/3279 = 1/6558 + 1/6558
5
1/502 = 1/252506 + 1/503
1/502 = 1/126504 + 1/504
1/502 = 1/63503 + 1/506
1/502 = 1/1506 + 1/753
1/502 = 1/1004 + 1/1004
11
1/88 = 1/7832 + 1/89
1/88 = 1/3960 + 1/90
1/88 = 1/2024 + 1/92
1/88 = 1/1056 + 1/96
1/88 = 1/792 + 1/99
1/88 = 1/572 + 1/104
1/88 = 1/440 + 1/110
1/88 = 1/330 + 1/120
1/88 = 1/264 + 1/132
1/88 = 1/209 + 1/152
1/88 = 1/176 + 1/176

sidsi
New poster
Posts: 7
Joined: Sun Mar 23, 2014 5:28 pm

Re: 10976 - Fractions Again?!

Post by sidsi » Sun Mar 23, 2014 5:38 pm

where is the problem in this code?? getting wrong answer
#include<stdio.h>
int main()
{int d[1000],e[1000],i,k;
float a,b,y;
int c;
double x;
while(scanf("%d",&k)==1)
{

a=k*2;
for( i=k+1,c=0;i<=a;i++)
{y=i;
x=(k*y)/(y-k);
if(x==(int)x)
{d[c]=(int)x,e[c]=(int)y;
c++;}
}
printf("%d\n",c);
for(i=0;i<c;i++)
printf("1/%d = 1/%d + 1/%d\n",k,d,e);
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10976 - Fractions Again?!

Post by brianfry713 » Mon Mar 24, 2014 7:11 am

sidsi, try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

sidsi
New poster
Posts: 7
Joined: Sun Mar 23, 2014 5:28 pm

Re: 10976 - Fractions Again?!

Post by sidsi » Mon Mar 24, 2014 12:57 pm

thnx, brainfry... :) accepted. but i dont understand the difference of using double or float in this code. :(
thnx again

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10976 - Fractions Again?!

Post by brianfry713 » Tue Mar 25, 2014 12:11 am

I meant try solving it using only integers.
http://floating-point-gui.de/
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 109 (10900-10999)”