Official Analysis (Java)

Explanation

We run a knapsack DP with the weights of the fruits and a capacity of TT. To handle the drinking of water, we take half the weight of each valid state and mark those states as valid as well. Finally, we can run another knapsack DP based on the halved weights.

Implementation

Time Complexity: O(T)\mathcal{O}(T), where TT is the maximum fullness.

C++

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;


int main() {
	ifstream fin("feast.in");
	ofstream fout("feast.out");


	int max_fullness, orange, lemon;

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("feast.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("feast.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());

Python

with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())


# dp[i][0] is no water; dp[i][1] is water used
dp = [[False, False] for _ in range(max_fullness + 1)]
dp[0][0] = True


# First knapsack: no water states and initial halved states
for i in range(max_fullness + 1):
	if dp[i][0]:

Alternative Explanation

Instead of a knapsack solution, a BFS/DFS can be done to iterate though all attainable states and determine the one with maximum fullness. The scene can be thought of as a graph by defining each edge to be the transition from fullness ii to jj. Each state is defined by fullness and whether Bessie has drank water. There are thus 2T2T states, and each state is visited at most once.

Implementation - BFS

Time Complexity: O(T)\mathcal{O}(T), where TT is the maximum fullness.

C++

#include <fstream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;


int main() {
	ifstream fin("feast.in");
	ofstream fout("feast.out");

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("feast.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("feast.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());

Python

from collections import deque


with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())


# visited[i][0] is water unused; visited[i][1] is water used
visited = [[False, False] for _ in range(max_fullness + 1)]
visited[0][0] = True


# (fullness, water)

Implementation - DFS

Time Complexity: O(T)\mathcal{O}(T), where TT is the maximum fullness.

C++

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;


int max_fullness, orange, lemon;
vector<pair<bool, bool>>
    visited;  // visited[i][0] is water unused; visited[i][1] is water used


void dfs(int fullness, bool water) {

Java

import java.io.*;
import java.util.*;


public class Main {
	static int maxFullness, orange, lemon;
	static boolean[][] visited;


	static void dfs(int fullness, int water) {
		if (visited[fullness][water]) return;
		visited[fullness][water] = true;

Python

from sys import setrecursionlimit


setrecursionlimit(1 << 25)


with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())


# visited[i][0] is water unused; visited[i][1] is water used
visited = [[False, False] for _ in range(max_fullness + 1)]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum