Delayed Work: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "This problem asks us to optimize the number of painters that need to be hired to most cheaply paint a house. One notices that even if X is 1 and P and K are 10k, we will stil..." |
imported>Kmk21 No edit summary |
||
| Line 18: | Line 18: | ||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
[[Category:pacnw2017]] | |||
[[Category:Algorithm Trivial]] | [[Category:Algorithm Trivial]] | ||
[[Category:Implementation Trivial]] | [[Category:Implementation Trivial]] | ||
Latest revision as of 00:03, 25 December 2017
This problem asks us to optimize the number of painters that need to be hired to most cheaply paint a house.
One notices that even if X is 1 and P and K are 10k, we will still only <10k painters (since the next one still costs a dollar, but saves us 10000/100001 dollars, so it's already diminishing returns). Given that result, we can iterate over all counts and find the min.
We could also ternary search or binary search.
We can also compute an exact result
Cost = XM + P*K/M
dCost/dM = X - PK/M^2
X = PK/M^2
M = sqrt(PK/X)
And evaluate cost(floor/ceil(M))