## 10976 - Fractions Again?!

Moderator: Board moderators

rahurprem
New poster
Posts: 10
Joined: Mon Mar 28, 2005 5:59 pm
Contact:

### 10976 - Fractions Again?!

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;
}
``````

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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?!

here's my code

Code: Select all

``````#include<stdio.h>
int main(void){
int n,count,x,y,i;
int temp;
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]=x;
temp[count++]=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],temp[i]);
}
}
``````
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
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?!

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

Do you have some critical I/O?

______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!

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?!

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

Do you have some critical I/O?

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?!

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?!

where is the problem in this code?? getting wrong answer
#include<stdio.h>
int main()
{int d,e,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?!

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?!

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?!

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