2015 Dec Gold Problem 2 Fruit Feast

Problem

In the "Fruit Feast" problem, Bessie the cow is preparing for a fruit feast. There are two types of fruits, apples and oranges, with certain amounts of tastiness. However, after consuming fruits, Bessie can take a nap, during which she can digest up to half of the fruit consumed so far. Bessie can only nap once.

More specifically:

• Each apple has a tastiness of A (1 ≤ A ≤ 1,000,000,000).
• Each orange has a tastiness of B (1 ≤ B ≤ 1,000,000,000).
• Bessie can consume up to T units of tastiness (1 ≤ T ≤ 1,000,000,000).
• The tastiness of the fruits Bessie consumes cannot exceed T. However, if Bessie decides to take a nap, she will digest up to half of the tastiness of the fruits she has consumed (rounded down).

The goal is to determine the maximum tastiness Bessie can achieve after possibly taking a nap.

Solution

We use dynamic programming to solve this problem. Let dp[i][j] be the maximum tastiness that Bessie can achieve after consuming fruits with a total tastiness of i and taking j naps (0 if no nap is taken, 1 if a nap is taken). We have:

dp[i][0] = max(dp[i-A][0], dp[i-B][0]) if i-A >= 0 or i-B >= 0 dp[i][1] = max(dp[i][1], dp[i//2][0] if i//2 >= 0)

The first equation represents consuming an apple or an orange without taking a nap, while the second equation represents taking a nap after consuming some fruits.

Finally, the maximum tastiness that Bessie can achieve is max(dp[i][1] for i in range(T+1)).

Note that to save memory, we can use a rolling array and compute dp[i] in non-decreasing order of i. The time complexity is O(T), and the space complexity is O(T) without optimizations, or O(1) with a rolling array.

Code

C++

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("feast.in");
    int maxTastiness, appleTastiness, orangeTastiness;
    fin >> maxTastiness >> appleTastiness >> orangeTastiness;

    vector<vector<bool>> seen(2, vector<bool>(maxTastiness + 1));
    seen[0][0] = true;

    for(int nap = 0; nap < seen.size(); nap++) {
        for(int i = 0; i < seen[nap].size(); i++) {
            if (!seen[nap][i]) continue;
            if (i + appleTastiness <= maxTastiness) {
                seen[nap][i + appleTastiness] = true;
            }
            if (i + orangeTastiness <= maxTastiness) {
                seen[nap][i + orangeTastiness] = true;
            }
            if (nap + 1 < seen.size()) {
                seen[nap + 1][i / 2] = true;
            }
        }
    }

    int result = maxTastiness;
    while (!seen[1][result]) {
        result--;
    }

    ofstream fout("feast.out");
    fout << result << endl;

    return 0;
}

Java

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

public class FruitFeast {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("feast.in"));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int maxTastiness = Integer.parseInt(tokenizer.nextToken());
        int appleTastiness = Integer.parseInt(tokenizer.nextToken());
        int orangeTastiness = Integer.parseInt(tokenizer.nextToken());

        boolean[][] seen = new boolean[2][maxTastiness+1];
        seen[0][0] = true;

        for (int nap = 0; nap < seen.length; nap++) {
            for (int i = 0; i < seen[nap].length; i++) {
                if (!seen[nap][i]) continue;
                if (i + appleTastiness <= maxTastiness) {
                    seen[nap][i + appleTastiness] = true;
                }
                if (i + orangeTastiness <= maxTastiness) {
                    seen[nap][i + orangeTastiness] = true;
                }
                if (nap + 1 < seen.length) {
                    seen[nap + 1][i / 2] = true;
                }
            }
        }

        int result = maxTastiness;
        while (!seen[1][result]) {
            result--;
        }

        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("feast.out")));
        writer.println(result);
        writer.close();
    }
}

Python

def main():
    with open("feast.in") as fin:
        maxTastiness, appleTastiness, orangeTastiness = map(int, fin.readline().split())

    seen = [[False] * (maxTastiness + 1) for _ in range(2)]
    seen[0][0] = True

    for nap in range(len(seen)):
        for i in range(len(seen[nap])):
            if not seen[nap][i]: 
                continue
            if i + appleTastiness <= maxTastiness:
                seen[nap][i + appleTastiness] = True
            if i + orangeTastiness <= maxTastiness:
                seen[nap][i + orangeTastiness] = True
            if nap + 1 < len(seen):
                seen[nap + 1][i // 2] = True

    result = maxTastiness
    while not seen[1][result]:
        result -= 1

    with open("feast.out", 'w') as fout:
        fout.write(str(result))

if __name__ == "__main__":
    main()