Hello everyone,↵
↵
I’m working on the USACO 2015 December Gold problem Fruit Feast. The goal is to find the maximum fullness Bessie can achieve by eating two types of fruits, with an option to drink water once which halves her fullness.↵
↵
**Problem Summary**↵
↵
Maximum fullness T (1 ≤ T ≤ 5,000,000)↵
↵
Eating an orange adds A fullness, a lemon adds B fullness (1 ≤ A,B ≤ T)↵
↵
Bessie can eat fruits any number of times without exceeding fullness T↵
↵
Bessie can drink water once, which halves fullness (floor division)↵
↵
Find the maximum achievable fullness↵
↵
**My Approach and Code**↵
↵
I used a DP array `dp` to track achievable fullness states.↵
Also, I use a boolean `track` array to record if water has been used or not at each state.↵
↵
`dp[i] == true` means fullness `i` is achievable.↵
↵
`track[i] == true` means water has not been used at fullness `i`.↵
↵
`track[i] == false` means water has already been used at fullness `i`.↵
↵
Whenever I move from fullness `i` to `i + v[j]` by eating a fruit, if water is still available (`track[i] == true`), I mark `(i + v[j]) / 2` as reachable (drinking water now), and mark water as used there.↵
↵
Here’s my code (without file I/O for simplicity):- ↵
↵
`↵
~~~~~↵
#include <bits/stdc++.h>`↵
`using namespace std;`↵
`↵
#define ll long long`↵
`↵
void solve()`↵
`{`{↵
` ll t;`↵
` vector<ll> v(3, 0);`↵
` cin >> t >> v[1] >> v[2];`↵
``↵
` vector<bool> dp(t + 1, false), track(t + 1, true);`↵
` dp[0] = true;`↵
``↵
` for (ll i = 0; i <= t; i++)`↵
` {`↵
` for (ll j = 1; j <= 2; j++)`↵
` {`↵
` if (dp[i] && i + v[j] <= t)`↵
` {`↵
` dp[i + v[j]] = true;`↵
` if (track[i])`↵
` {`↵
` dp[(i + v[j]) / 2] = true;`↵
` track[(i + v[j]) / 2] = false;`↵
` }`↵
` }`↵
` }`↵
` }`↵
``↵
` for (ll i = t; i >= 0; i--)`↵
` {`↵
` if (dp[i])`↵
` {`↵
` cout << i << endl;`↵
` return;`↵
` }`↵
` }`↵
`}`}↵
↵
`int main()`↵
`{`{↵
` ios::sync_with_stdio(false);`↵
` cin.tie(nullptr);`↵
` solve();`↵
` return 0;`↵
`}`}↵
↵
~~~~~↵
↵
↵
↵
**My Question**↵
↵
My code passes almost all test cases, but fails test case #11 on the USACO judge.↵
↵
I suspect it has to do with how I update `dp` and use the `track` array.↵
↵
Is there a flaw in the way I handle transitions or water usage?↵
↵
Can this failure be fixed without completely changing my code structure?↵
↵
Any hints or explanations about why test case 11 fails would be really appreciated! Thanks in advance.
↵
I’m working on the USACO 2015 December Gold problem Fruit Feast. The goal is to find the maximum fullness Bessie can achieve by eating two types of fruits, with an option to drink water once which halves her fullness.↵
↵
**Problem Summary**↵
↵
Maximum fullness T (1 ≤ T ≤ 5,000,000)↵
↵
Eating an orange adds A fullness, a lemon adds B fullness (1 ≤ A,B ≤ T)↵
↵
Bessie can eat fruits any number of times without exceeding fullness T↵
↵
Bessie can drink water once, which halves fullness (floor division)↵
↵
Find the maximum achievable fullness↵
↵
**My Approach and Code**↵
↵
I used a DP array `dp` to track achievable fullness states.↵
Also, I use a boolean `track` array to record if water has been used or not at each state.↵
↵
`dp[i] == true` means fullness `i` is achievable.↵
↵
`track[i] == true` means water has not been used at fullness `i`.↵
↵
`track[i] == false` means water has already been used at fullness `i`.↵
↵
Whenever I move from fullness `i` to `i + v[j]` by eating a fruit, if water is still available (`track[i] == true`), I mark `(i + v[j]) / 2` as reachable (drinking water now), and mark water as used there.↵
↵
Here’s my code (without file I/O for simplicity):- ↵
↵
~~~~~↵
#include <bits/stdc++.h>
#define ll long long
void solve()
↵
↵
~~~~~↵
↵
↵
↵
**My Question**↵
↵
My code passes almost all test cases, but fails test case #11 on the USACO judge.↵
↵
I suspect it has to do with how I update `dp` and use the `track` array.↵
↵
Is there a flaw in the way I handle transitions or water usage?↵
↵
Can this failure be fixed without completely changing my code structure?↵
↵
Any hints or explanations about why test case 11 fails would be really appreciated! Thanks in advance.
