Here's the problem link: UVa 10976 - Fractions Again

**Caution: This is a spoiler with complete solution. Do not read further if you haven't tried it yet.**

Abbreviated problem definition: Given a fraction 1/z, it can be represented as 1/x + 1/y where x >=y. Find all combinations for a given 0 < z <= 10000.

Sample Inputs:

2

12

Sample Outputs:

2 --# of solutions

1/2 = 1/6 + 1/3

1/2 = 1/4 + 1/4

8 --# of solutions

1/12 = 1/156 + 1/13

1/12 = 1/84 + 1/14

1/12 = 1/60 + 1/15

1/12 = 1/48 + 1/16

1/12 = 1/36 + 1/18

1/12 = 1/30 + 1/20

1/12 = 1/28 + 1/21

1/12 = 1/24 + 1/24

Expression:

1/z = 1/x + 1/y

1/z = (y + x)/ (x * y)

z = (x * y)/(x + y) --(1)

z * (x + y) = (x * y)

z * x + z * y = y * x

z * y = (y - z) * x

x = (z * y) / (y - z) --(2)

Looking at the pattern for the samples, we decrease y and find the x,

if possible.

Start with y = 2 * z = 2 * 2 = 4:

1/2 = 1/4 + 1/4

2 = (4 * 4)/(4 + 4) --using (1) above.

Try y = 3;

2 = (x * 3)/ (x + 3)

2 * (x + 3) = x * 3

2*x + 6 = 3*x

3*x - 2*x = 6

x = 6

So, one more solution found:

1/2 = 1/6 + 1/3

We cannot go further as y becomes equal to 2.

Full answers:

1/2 = 1/4 + 1/4

1/2 = 1/6 + 1/3

Let us look at the second sample:

Start with y = 12 * z = 12 * 2 = 14:

1/12 = 1/24 + 1/24 --Obvious :-)

Reduce y to 23:

Using (1) above we get:

12 = (x * 23)/(x + 23)

12 * (x + 23) = 23 * x

12*x + 276 = 23*x

276 = 11*x

x = 276/11 = 25.0909 => NOT a solution as we need 11 to exactly divide 276

Reduce y to 22:

Using (1) above we get:

12 = (x * 22)/(x + 22)

12*x + 12 * 22 = 22 * x

12 * 22 = 10 * x => NOT a solution

Reduce y to 21:

Using (1) above we get:

12 = (x * 21)/(x + 21)

12 * (x + 21) = 21 * x

12*x + 12 * 21 = 21*x

12 * 21 = 9*x

x = 28 => We have a solution :-)

1/12 = 1/28 + 1/21

Reduce y to 20:

Using (1) above we get:

12 = (x * 20)/(x + 20)

12*x + 12*20 = 20*x

12*20 = 8*x

x = 30 => we have a solution :-)

1/12 = 1/30 + 1/20

Reduce y to 19:

Using (1) above we get:

12 = (x * 19)/(x + 19)

12*x + 12*19 = 19*x

12*19 = 7*x

x = 32.57 => NOT a solution

Reduce y to 18:

Using (1) above we get:

12 = (x * 18)/(x + 18)

12*x + 12*18 = 18*x

12*18 = 6*x

x = 36 => we have a solution :-)

1/12 = 1/36 + 1/18

Reduce y to 17:

Using (1) above we get:

12 = (x * 17)/(x + 17)

12*x + 12*17 = 17*x

12*17 = 5*x

x = 40.8 => NOT a solution

Reduce y to 16:

Using (1) above we get:

12 = (x * 16)/(x + 16)

12*x + 12*16 = 16*x

12*16 = 4*x

x = 48 => we have a solution :-)

1/12 = 1/48 + 1/16

Reduce y to 15:

Using (1) above we get:

12 = (x * 15)/(x + 15)

12*x + 12*15 = 15*x

12*15 = 3*x

x = 60 => we have a solution :-)

1/12 = 1/60 + 1/15

Reduce y to 14:

Using (1) above we get:

12 = (x * 14)/(x + 14)

12*x + 12*14 = 14*x

12*14 = 2*x

x = 84 => we have a solution :-)

1/12 = 1/84 + 1/14

Reduce y to 13:

Using (1) above we get:

12 = (x * 13)/(x + 13)

12*x + 12*13 = 13*x

12*13 = 1*x

x = 156 => we have a solution :-)

1/12 = 1/156 + 1/13

END when y = 12

There you go :-)

There could be some optimization that can be performed for quickly

discarding some values of y. Will update.

why you fixed y=2*z is it there any proper reason ??

ReplyDelete