PAST1M

https://gyazo.com/6e7b0970c5ef90359fec6baba959c845

Thoughts.

The problem of finding a selection method that maximizes the ratio

I wonder if there is anything to be said regarding the ratio's small and large.

3/1 and 200/100, the former is larger, but the latter is larger when 0/100 is added

DP issues on ratios

Not this time, because the range of values is 10^5.

Official Explanation

Instead of maximizing the ratio directly, make it a question of determining whether the ratio exceeds X

This can be determined by O(NlogN)

We can bisect the search for the possible range of ratios.

A thought I've had time to think about.

N is 1000, so a full 2^N search is not possible.

Can't we just greedily "add what makes it big"?

OK if "X1 < X1 + X2 then X1 + X3 < X1 + X2 + X3

code:python

from random import randint

for i in range(1000):

if a / b < (a + c) / (b + d) and (a + e) / (b + f) > (a + c + e) / (b + d + f):

print(a, b, c, d, e, f)

break

Easily found counterexamples: 5 8 5 7 8 7

[Maximize the sum ratio

Make it a question of determining whether X is exceeded or not.

Choose one of the largest from M

If all are negative, the maximum is 0 for "don't choose".

Sort and if the largest one is positive, OK.

3WA

code:python

def solve(N, M, AS, BS, CS, DS):

left = 0.0

right = 1000000.0

while left < right - 10 ** -7:

x = (left + right) / 2

if y > 0:

else:

if y >= 0:

left = x

else:

right = x

return left

RIGHT should be 10001, I set it to 1000000 more, but no change.

left < right - 10 ** -7 is smaller than the required 10 ** -6

→AC

When the best help has a negative score, the decision is "no gain, so don't use it", but due to the "must choose 5 animals" constraint, zs4 will be chosen if the help is not chosen, which could be an even bigger negative here.

---