Обсуждение @ 1200. Рога и копыта @ Timus Online Judge

Vlad Veselov My solution is O(K). Does exist better solution? [6] // Задача 1200. Рога и копыта 8 май 2004 15:50

Sandro Re: My solution is O(K). Does exist better solution? [1] // Задача 1200. Рога и копыта 27 май 2004 00:08

I have O(K) solution too, but I suspect that there is a simple solution O(1).

anus (USU) Re: My solution is O(K). Does exist better solution? // Задача 1200. Рога и копыта 8 июл 2006 20:07

I have O(1) solution. Simply draw conditions in Cartesian coordinates with axis horns and hoofs.

wangyin Re: My solution is O(K). Does exist better solution? [3] // Задача 1200. Рога и копыта 14 авг 2006 15:01

Mine is O(min(a,b) div 2)
0.015s

Piratek-(akaDK) Re: My solution is O(K). Does exist better solution? [2] // Задача 1200. Рога и копыта 19 янв 2008 02:52

We must solve some equipments
{Ax + By - x * x - y * y = Max , x + y <= k} where A , B , K we know. We simplify first equipment of that system

x * (A - x) + y * (B - y) = Max {1}

Our First Problem is to find x + y? Let's do it!
If we decrease x(or y) x = x - 1.We will get

(x - 1) * (A - x + 1) + y * (B - Y) =
Ax - x^2 + x - A + x - 1 + By - y^2. Let's compare it with {1}
<---> Ax - x^2 + By - Y^2
The same part is consist of all Ax - x^2 + By - Y^2.
so if we subtract it we'll get
2 *x - 1 - A. So it x > (A + 1) / 2 we can decrease x to increase our profit. It's equal to y if y > (B + 1) / 2 we can decrease y.

Vedernikoff Sergey Re: My solution is O(K). Does exist better solution? [1] // Задача 1200. Рога и копыта 5 июн 2008 01:07

From trivial economic theory (micro 0) we should equate marginal benefits - that's all!

Denis Koshman Re: My solution is O(K). Does exist better solution? // Задача 1200. Рога и копыта 28 июл 2008 03:49

I just test 5x5 vicinities of 0;0, 0;k, k;0, a/2;b/2, a/2;0, 0;b/2, a/4-b/4+k/2;b/4-a/4+k/2.

Обсуждение задачи 1200. Рога и копыта