Festa della frutta (Editoriale)

C'è uno zaino di capacità $t$. Sono disponibili due oggetti con valori $a$ e $b$. Ciascuno di essi può essere messo nello zaino un numero arbitrario di volte. Risolviamo il problema dello zaino per due oggetti.

Sia dp[i] = 1 se Bessie può ottenere una sazietà pari a $i$. Ora Bessie beve dell'acqua. Precisamente, per ogni valore $i$ per cui dp[i] = 1, impostiamo dp[i / 2] = 1.

Ora risolviamo di nuovo il problema dello zaino per due oggetti. Troviamo le sazietà che Bessie potrà raggiungere dopo aver bevuto l'acqua.

Esempio

Consideriamo l'esempio fornito. Risolviamo il problema dello zaino per arance e limoni.

Bessie beve dell'acqua.

Risolviamo di nuovo il problema dello zaino per arance e limoni.

La sazietà massima di Bessie è pari a $8$.

Implementazione dell'algoritmo

Dichiariamo un array $dp$, in cui dp[i] = 1 se Bessie può ottenere una sazietà pari a $i$.

#define MAX 5000001
int dp[MAX];

Leggiamo i dati di input.

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

Inizializziamo lo zaino: la sazietà $0$ può essere raggiunta se non si mangia nulla.

dp[0] = 1;

Mettiamo le arance nello zaino.

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

Mettiamo i limoni nello zaino.

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

Bessie beve dell'acqua. Se la sazietà $i$ è raggiungibile, allora anche la sazietà $i/2$ è raggiungibile.

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

Risolviamo di nuovo il problema dello zaino per arance e limoni.

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;

Troviamo e stampiamo la sazietà massima che Bessie può raggiungere.

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

Implementazione in Python

Leggiamo i dati di input.

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

Dichiariamo un array $dp$, in cui dp[i] = 1 se Bessie può ottenere una sazietà pari a $i$.

dp = [0] * (t + 1)

Inizializziamo lo zaino: la sazietà $0$ può essere raggiunta se non si mangia nulla.

dp[0] = 1

Mettiamo le arance nello zaino.

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

Mettiamo i limoni nello zaino.

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

Bessie beve dell'acqua. Se la sazietà $i$ è raggiungibile, allora anche la sazietà $i/2$ è raggiungibile.

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

Risolviamo di nuovo il problema dello zaino per arance e limoni.

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

Troviamo e stampiamo la sazietà massima che Bessie può raggiungere.

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