Розбір

There is a knapsack with a capacity of $t$. Two items are available with values $a$ and $b$. Each item in the knapsack can be placed an arbitrary number of times. We solve the knapsack problem for these two items.

Let $dp[i]=1$, if Bessie can achieve fullness equal to $i$. Now Bessie drinks the water. For each value of $i$ where $dp[i]=1$, we set $dp[i/2]=1$.

Now again solve the knapsack problem for two items. Determine the fullness that Bessie can achieve after drinking the water.

Example

Consider the given example. First we solve the knapsack problem for oranges and lemons.

Bessie drinks water.

Again we solve the knapsack problem for oranges and lemons.

Bessie's maximum fullness is $8$.

Algorithm realization

Declare an array $dp$, where $dp[i]=1$, if Bessie can achieve fullness equal to $i$.

#define MAX 5000001
int dp[MAX];

Read the input data.

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

Initialize the knapsack: fullness $0$ can be achieved if nothing is eaten.

dp[0] = 1;

Put oranges in the knapsack.

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

Put lemons in the knapsack.

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

Bessie drinks water. If fullness $i$ is achieved, then fullness $i/2$ can also be achieved.

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

Solve the knapsack problem again for oranges and lemons.

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;

Find and print the maximum fullness that Bessie can achieve.

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

Python realization

Read the input data.

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

Declare an array $dp$, where $dp[i]=1$, if Bessie can achieve fullness equal to $i$.

dp = [0] * (t + 1)

Initialize the knapsack: fullness $0$ can be achieved if nothing is eaten.

dp[0] = 1

Put oranges in the knapsack.

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

Put lemons in the knapsack.

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

Bessie drinks water. If fullness $i$ is achieved, then fullness $i/2$ can also be achieved.

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

Solve the knapsack problem again for oranges and lemons.

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

Find and print the maximum fullness that Bessie can achieve.

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