Блог

Главная - Вопросы по программированию - Решите для двух неизвестных переменных и двух функций

Решите для двух неизвестных переменных и двух функций

#java #algorithm #dynamic-programming

Вопрос:

Две функции с разным определением.

 funcA:  a = a - 2;  b = b - 1;   funcB:   a = a - 1;  b = b - 2;

Наша цель-получить количество операций, когда и a = 0 b = 0 ;

Ввод образца: a = 4, b = 2 

 call funcA:  a become 2, b become 1;  again call funcA  a become 0, b become 0;

всего не выполнено ни одной операции 2 0 = 2 , поэтому возвращено 2;

Ввод образца 2: a = 3, b = 3 

 call funcA:  a become 1, b become 2;  call funcB  a become 0, b become 0;

всего не выполнено ни одной операции 1 1 = 2 , поэтому возвращено 2;

Ответ №1:

Давайте начнем с особых случаев:

  • если a lt; 0 или b lt; 0 у нас нет решения
  • если a = 0 и b lt;gt; 0 или a lt;gt; 0 и b = 0 у нас нет решения
  • если a gt; 2 * b или b gt; 2 * a у нас нет решения

Если мы используем funcA x время и funcB y время и получаем 0 от обоих a , и b мы можем написать

 a - 2 * x - y = 0 b - 2 * y - x = 0

Давайте решим эту систему линейных уравнений для x и y :

 2 * x   y = a 2 * y   x = b

Решение заключается в следующем

 x = (2 * a - b) / 3 y = (2 * b - a) / 3

Итак, если у нас есть целочисленное решение для x и y мы должны выполнять funcA x раз, funcB y раз

Код (Java):

 public static int Solve(int a, int b) {  // beware integer overflow! we use long in case a = 2_000_000_000 provided   long x = (2L * a - b) / 3;  long y = (2L * b - a) / 3;   return ((x gt;= 0 amp;amp; y gt;= 0 amp;amp; (2L * b - a) % 3 == 0 amp;amp; (2L * a - b) % 3 == 0))  ? (int)(x   y)  : -1; // impossible }

Как можно видеть, у нас есть прямое решение со O(1) сложностью во времени и пространстве; нет необходимости в динамическом программировании

Комментарии:

1. @Alex Руденко: спасибо вам! Вы совершенно правы, мой плохой — проблема симметрична, ее легко было ошибочно поменять x местами и y

2. Спасибо @Дмитрий Быченко . Решение прошло все тестовые случаи.

Метки: