Page **1** of **1**

### 11429 - Randomness

Posted: **Mon Mar 24, 2008 2:11 am**

by **sclo**

For this problem, how would one find the optimal solution?

Let g = lcm(b1,b2,...,bn).

If R>=g, then the problem is pretty trivial.

I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.

### Re: 11429 - Randomness

Posted: **Mon Mar 24, 2008 9:34 am**

by **Robert Gerbicz**

sclo wrote:For this problem, how would one find the optimal solution?

Let g = lcm(b1,b2,...,bn).

If R>=g, then the problem is pretty trivial.

I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.

My greedy method is independent on the the value of g.

[I haven't proved that my greedy solution is correct, but it works.]

### Re: 11429 - Randomness

Posted: **Mon Mar 24, 2008 10:29 pm**

by **sclo**

Robert Gerbicz wrote:sclo wrote:For this problem, how would one find the optimal solution?

Let g = lcm(b1,b2,...,bn).

If R>=g, then the problem is pretty trivial.

I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.

My greedy method is independent on the the value of g.

[I haven't proved that my greedy solution is correct, but it works.]

I haven't tried it but it seems to work. Sort the ai/bi in non-increasing order, then we consider a1/b1 and try to decide it as soon as possible, with the fewest number of calls to RNG. If it can't be exactly decided, then replace a1/b1 with the difference with the decided fraction.

Edit: This is probably a good case to consider:

Code: Select all

```
Input:
2 5
1 5 1 5 1 5 1 5 1 5
Output:
3.600000
```

### Re: 11429 - Randomness

Posted: **Tue Mar 25, 2008 12:34 am**

by **Robert Gerbicz**

sclo wrote:
Is the solution correct?

My AC code returns by 3.600000

[don't forget, that :"Input will be terminated by a line containing two zeros."]

Ps. I've proved that the greedy solution is correct in all cases.

### Re: 11429 - Randomness

Posted: **Tue Mar 25, 2008 1:45 am**

by **sclo**

Robert Gerbicz wrote:sclo wrote:
Is the solution correct?

Code: Select all

```
Input:
2 5
1 5 1 5 1 5 1 5 1 5
Output:
4.400000
```

My AC code returns by 3.600000

[don't forget, that :"Input will be terminated by a line containing two zeros."]

Ps. I've proved that the greedy solution is correct in all cases.

Thanks, I found a bug in my reasoning. I think it's correct now. Anyway, it's based on R-ary expansion of the fractions.