## 10976 - Fractions Again?!

Moderator: Board moderators

### 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.
rahurprem
New poster

Posts: 10
Joined: Mon Mar 28, 2005 5:59 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...

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

### 10976 - Fractions Again?!

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
lyc
New poster

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

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

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

### 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!
Kaul
New poster

Posts: 4
Joined: Tue May 02, 2006 10:56 am
Location: Seoul, Korea

### 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.
tan_Yui
Experienced poster

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

### 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.
DD
Experienced poster

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

### Re: 10976 - Fractions Again?!

Some Previous Input Output clarification:

Input:
Code: Select all
`314159265358979323846264338327950288`

Output:

Code: Select all
`21/3 = 1/12 + 1/41/3 = 1/6 + 1/611/1 = 1/2 + 1/231/4 = 1/20 + 1/51/4 = 1/12 + 1/61/4 = 1/8 + 1/851/15 = 1/240 + 1/161/15 = 1/90 + 1/181/15 = 1/60 + 1/201/15 = 1/40 + 1/241/15 = 1/30 + 1/3081/92 = 1/8556 + 1/931/92 = 1/4324 + 1/941/92 = 1/2208 + 1/961/92 = 1/1150 + 1/1001/92 = 1/621 + 1/1081/92 = 1/460 + 1/1151/92 = 1/276 + 1/1381/92 = 1/184 + 1/18421/653 = 1/427062 + 1/6541/653 = 1/1306 + 1/130651/589 = 1/347510 + 1/5901/589 = 1/18848 + 1/6081/589 = 1/11780 + 1/6201/589 = 1/1550 + 1/9501/589 = 1/1178 + 1/117851/793 = 1/629642 + 1/7941/793 = 1/49166 + 1/8061/793 = 1/11102 + 1/8541/793 = 1/4514 + 1/9621/793 = 1/1586 + 1/1586141/2384 = 1/5685840 + 1/23851/2384 = 1/2844112 + 1/23861/2384 = 1/1423248 + 1/23881/2384 = 1/712816 + 1/23921/2384 = 1/357600 + 1/24001/2384 = 1/179992 + 1/24161/2384 = 1/91188 + 1/24481/2384 = 1/46786 + 1/25121/2384 = 1/40528 + 1/25331/2384 = 1/24585 + 1/26401/2384 = 1/21456 + 1/26821/2384 = 1/11920 + 1/29801/2384 = 1/7152 + 1/35761/2384 = 1/4768 + 1/476851/626 = 1/392502 + 1/6271/626 = 1/196564 + 1/6281/626 = 1/98595 + 1/6301/626 = 1/1878 + 1/9391/626 = 1/1252 + 1/1252231/4338 = 1/18822582 + 1/43391/4338 = 1/9413460 + 1/43401/4338 = 1/6277086 + 1/43411/4338 = 1/4708899 + 1/43421/4338 = 1/3140712 + 1/43441/4338 = 1/2095254 + 1/43471/4338 = 1/1572525 + 1/43501/4338 = 1/1049796 + 1/43561/4338 = 1/701310 + 1/43651/4338 = 1/527067 + 1/43741/4338 = 1/352824 + 1/43921/4338 = 1/236662 + 1/44191/4338 = 1/178581 + 1/44461/4338 = 1/120500 + 1/45001/4338 = 1/82422 + 1/45791/4338 = 1/62419 + 1/46621/4338 = 1/43380 + 1/48201/4338 = 1/30366 + 1/50611/4338 = 1/23859 + 1/53021/4338 = 1/17352 + 1/57841/4338 = 1/13014 + 1/65071/4338 = 1/10845 + 1/72301/4338 = 1/8676 + 1/867651/3279 = 1/10755120 + 1/32801/3279 = 1/3587226 + 1/32821/3279 = 1/1197928 + 1/32881/3279 = 1/13116 + 1/43721/3279 = 1/6558 + 1/655851/502 = 1/252506 + 1/5031/502 = 1/126504 + 1/5041/502 = 1/63503 + 1/5061/502 = 1/1506 + 1/7531/502 = 1/1004 + 1/1004111/88 = 1/7832 + 1/891/88 = 1/3960 + 1/901/88 = 1/2024 + 1/921/88 = 1/1056 + 1/961/88 = 1/792 + 1/991/88 = 1/572 + 1/1041/88 = 1/440 + 1/1101/88 = 1/330 + 1/1201/88 = 1/264 + 1/1321/88 = 1/209 + 1/1521/88 = 1/176 + 1/176`
magurmach
New poster

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