Всем здравствуйте.
Есть вот такая задача : http://www.e-olimp.com/problems/875
Кратко : есть уравнение вида a * x + b * y = c. Нужно максимизировать (x + y).
Для решения использую следующую схему:
1. Находим такие корни (xg, yg), что a * xg + b * yg = gcd(a, b)
2. Далее находим, так сказать, первоначальные корни :
x0 = xg + (c / gcd(a, b))
y0 = yg + (c / gcd(a, b))
3. И теперь мы можем найти все решения данного уравнения по :
x = x0 + k * (b / gcd(a, b))
y = y0 - k * (a / gcd(a, b))
Проблема именно в том, что для того чтобы максимизировать (x + y) нужно брать какой то коэффициент k. А как его найти при таких ограничениях?Как-то линейно или, возможно, бинпоиском к примеру?
Зачем диофантовы уравнения? Вы за 2 секунды можете даже перебрать миллион вариантов комбинаций гамбургеров/чизбургеров. Хотя я полагаю что функция общего числа съеденых единиц (гамбургеров и чизбургеров) в зависимости от количества только гамбургеров (или чизбургеров) обладает определёнными симпатичными свойствами, которые позволят провести меньше вычислений.
UPD: Кроме того обратите внимание на 2-й пример к задаче. Судя по нему тут на первом месте по важности не максимизация суммы съеденого а минимизация упущенного времени...
UPD2: Даже на Java прямой перебор прокатил... Неинтересно :-(
Просто преобразованиями.
1/x+1/y=1/n => nx+ny=xy => x(n-y)+ny=0 => x(n-y)-n(n-y)+n^2=0
=> n^2=(x-n)*(y-n). То есть, ставится вопрос о количестве упорядоченных пар (a,b) таких, что n^2=a*b. А это округленная вверх целая часть от tau(n^2) - количества делителей n^2. Функцию tau можно найти, например, по решету.
Тогда Вам нужно подобрать максимальное такое k, при котором y будет не меньше нуля. Кажется должно прокатить что-то вроде k=floor(y0 / (a / gcd(a, b)))