Фруктове свято (Розбір)

Є рюкзак місткістю $t$. Доступні дві речі з вартостями $a$ і $b$. Кожну з них можна класти в рюкзак довільну кількість разів. Розв'язуємо задачу про рюкзак для двох речей.

Нехай dp[i] = 1, якщо Бессі може отримати ситість, що дорівнює $i$. Тепер Бессі п'є воду. А саме, для кожного значення $i$, для якого dp[i] = 1, встановимо dp[i / 2] = 1.

Тепер знову розв'язуємо задачу про рюкзак для двох речей. Знаходимо ситості, яких зможе досягти Бессі після того, як випила воду.

Приклад

Розглянемо наведений приклад. Розв'язуємо задачу рюкзака для апельсинів і лимонів.

Бессі п'є воду.

Знову розв'язуємо задачу рюкзака для апельсинів і лимонів.

Максимальна ситість Бессі дорівнює $8$.

Реалізація алгоритму

Оголосимо масив $dp$, у якому dp[i] = 1, якщо Бессі може отримати ситість, що дорівнює $i$.

#define MAX 5000001
int dp[MAX];

Читаємо вхідні дані.

scanf("%d %d %d", \&t, \&a, \&b);

Ініціалізуємо рюкзак: ситість $0$ можна досягти, якщо нічого не їсти.

dp[0] = 1;

У рюкзак кладемо апельсини.

for (i = a; i \<= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;

У рюкзак кладемо лимони.

for (i = b; i \<= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Бессі п'є воду. Якщо ситість $i$ досягнута, то ситість $i/2$ також може бути досягнута.

for (i = 1; i \<= t; i++)
  if (dp[i] == 1) dp[i / 2] = 1;

Знову розв'язуємо задачу рюкзака для апельсинів і лимонів.

for (i = a; i \<= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;
for (i = b; i \<= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Знаходимо і виводимо максимальну ситість, якої може досягти Бессі.

for (i = t; i \> 0; i--)
  if (dp[i] == 1) break;
printf("%d\n", i);

Python реалізація

Читаємо вхідні дані.

t, a, b = map(int, input().split())

Оголосимо масив $dp$, у якому dp[i] = 1, якщо Бессі може отримати ситість, що дорівнює $i$.

dp = [0] * (t + 1)

Ініціалізуємо рюкзак: ситість $0$ можна досягти, якщо нічого не їсти.

dp[0] = 1

У рюкзак кладемо апельсини.

for i in range(a, t + 1):
  if dp[i - a] == 1: dp[i] = 1

У рюкзак кладемо лимони.

for i in range(b, t + 1):
  if dp[i - b] == 1:  dp[i] = 1

Бессі п'є воду. Якщо ситість $i$ досягнута, то ситість $i/2$ також може бути досягнута.

for i in range(1, t + 1):
  if dp[i] == 1: dp[i // 2] = 1

Знову розв'язуємо задачу рюкзака для апельсинів і лимонів.

for i in range(a, t + 1):
  if dp[i - a] == 1: dp[i] = 1
for i in range(b, t + 1):
  if dp[i - b] == 1: dp[i] = 1

Знаходимо і виводимо максимальну ситість, якої може досягти Бессі.

for i in range(t, 0, -1):
  if dp[i] == 1: break
print(i)