Fruit Feast

Explicación

Ejecutamos una DP de mochila (knapsack) con los pesos de las frutas y una capacidad de $T$ . Para manejar el hecho de beber agua, tomamos la mitad del peso de cada estado válido y marcamos esos estados como válidos también. Finalmente, podemos ejecutar otra DP de mochila a partir de los pesos a la mitad.

Implementación

Complejidad temporal: $\mathcal{O}(T)$ , donde $T$ es la saciedad máxima.

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	ifstream fin("feast.in");
	ofstream fout("feast.out");
 
	int max_fullness, orange, lemon;
	fin >> max_fullness >> orange >> lemon;
 
	// dp[i].first es sin agua; dp[i].second es con agua usada
	vector<pair<bool, bool>> dp(max_fullness + 1);
	dp[0].first = true;
 
	// Primera mochila: estados sin agua y estados iniciales a la mitad
	for (int i = 0; i <= max_fullness; i++) {
		if (dp[i].first) {
			if (i + orange <= max_fullness) { dp[i + orange].first = true; }
			if (i + lemon <= max_fullness) { dp[i + lemon].first = true; }
			dp[i / 2].second = true;
		}
	}
 
	// Segunda mochila: estados con agua usada
	for (int i = 0; i <= max_fullness; i++) {
		if (dp[i].second) {
			if (i + orange <= max_fullness) { dp[i + orange].second = true; }
			if (i + lemon <= max_fullness) { dp[i + lemon].second = true; }
		}
	}
 
	for (int i = max_fullness; i >= 0; i--) {
		if (dp[i].first || dp[i].second) {
			fout << i << endl;
			break;
		}
	}
}


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());
 
		int maxFullness = Integer.parseInt(st.nextToken());
		int orange = Integer.parseInt(st.nextToken());
		int lemon = Integer.parseInt(st.nextToken());
 
		// dp[i][0] es sin agua; dp[i][1] es con agua usada
		boolean[][] dp = new boolean[maxFullness + 1][2];
		dp[0][0] = true;
 
		// Primera mochila: estados sin agua y estados iniciales a la mitad
		for (int i = 0; i <= maxFullness; i++) {
			if (dp[i][0]) {
				if (i + orange <= maxFullness) dp[i + orange][0] = true;
				if (i + lemon <= maxFullness) dp[i + lemon][0] = true;
				dp[i / 2][1] = true;
			}
		}
 
		// Segunda mochila: estados con agua usada
		for (int i = 0; i <= maxFullness; i++) {
			if (dp[i][1]) {
				if (i + orange <= maxFullness) dp[i + orange][1] = true;
				if (i + lemon <= maxFullness) dp[i + lemon][1] = true;
			}
		}
 
		for (int i = maxFullness; i >= 0; i--) {
			if (dp[i][0] || dp[i][1]) {
				pw.println(i);
				break;
			}
		}
 
		br.close();
		pw.close();
	}
}


with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())
 
# dp[i][0] es sin agua; dp[i][1] es con agua usada
dp = [[False, False] for _ in range(max_fullness + 1)]
dp[0][0] = True
 
# Primera mochila: estados sin agua y estados iniciales a la mitad
for i in range(max_fullness + 1):
	if dp[i][0]:
		if i + orange <= max_fullness:
			dp[i + orange][0] = True
		if i + lemon <= max_fullness:
			dp[i + lemon][0] = True
		dp[i // 2][1] = True
 
# Segunda mochila: estados con agua usada
for i in range(max_fullness + 1):
	if dp[i][1]:
		if i + orange <= max_fullness:
			dp[i + orange][1] = True
		if i + lemon <= max_fullness:
			dp[i + lemon][1] = True
 
with open("feast.out", "w") as fout:
	for i in range(max_fullness, -1, -1):
		if dp[i][0] or dp[i][1]:
			fout.write(f"{i}\n")
			break

Explicación alternativa

En lugar de una solución de mochila, se puede hacer un BFS/DFS para iterar sobre todos los estados alcanzables y determinar el de máxima saciedad. La escena se puede pensar como un grafo definiendo cada arista como la transición de saciedad $i$ a $j$ . Cada estado se define por la saciedad y si Bessie ya bebió agua. Hay así $2T$ estados, y cada estado se visita a lo sumo una vez.

Implementación - BFS

Complejidad temporal: $\mathcal{O}(T)$ , donde $T$ es la saciedad máxima.

C++JavaPython


#include <fstream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
	ifstream fin("feast.in");
	ofstream fout("feast.out");
 
	int max_fullness, orange, lemon;
	fin >> max_fullness >> orange >> lemon;
 
	// visited.first es agua no usada; visited.second es agua usada
	vector<pair<bool, bool>> visited(max_fullness + 1);
	visited[0].first = true;
 
	//{saciedad, agua_usada}
	queue<pair<int, bool>> q;
	q.push({0, false});
 
	while (!q.empty()) {
		int fullness = q.front().first;
		bool water = q.front().second;
		q.pop();
		if (water) {
			if (fullness + orange <= max_fullness &&
			    !visited[fullness + orange].second) {
				visited[fullness + orange].second = true;
				q.push({fullness + orange, water});
			}
			if (fullness + lemon <= max_fullness && !visited[fullness + lemon].second) {
				visited[fullness + lemon].second = true;
				q.push({fullness + lemon, water});
			}
		} else {
			if (fullness + orange <= max_fullness &&
			    !visited[fullness + orange].first) {
				visited[fullness + orange].first = true;
				q.push({fullness + orange, water});
			}
			if (fullness + lemon <= max_fullness && !visited[fullness + lemon].first) {
				visited[fullness + lemon].first = true;
				q.push({fullness + lemon, water});
			}
			if (!visited[fullness / 2].second) {
				visited[fullness / 2].second = true;
				q.push({fullness / 2, true});
			}
		}
	}
 
	for (int i = max_fullness; i >= 0; i--) {
		if (visited[i].first || visited[i].second) {
			fout << i << endl;
			break;
		}
	}
	return 0;
}


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());
 
		int maxFullness = Integer.parseInt(st.nextToken());
		int orange = Integer.parseInt(st.nextToken());
		int lemon = Integer.parseInt(st.nextToken());
 
		// visited[i][0] es agua no usada; visited[i][1] es agua usada
		boolean[][] visited = new boolean[maxFullness + 1][2];
		visited[0][0] = true;
 
		// {saciedad, aguaUsada}
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {0, 0});
 
		while (!queue.isEmpty()) {
			int[] curr = queue.poll();
			int fullness = curr[0];
			int water = curr[1];
			if (water == 1) {
				if (fullness + orange <= maxFullness &&
				    !visited[fullness + orange][1]) {
					visited[fullness + orange][1] = true;
					queue.add(new int[] {fullness + orange, 1});
				}
				if (fullness + lemon <= maxFullness && !visited[fullness + lemon][1]) {
					visited[fullness + lemon][1] = true;
					queue.add(new int[] {fullness + lemon, 1});
				}
			} else {
				if (fullness + orange <= maxFullness &&
				    !visited[fullness + orange][0]) {
					visited[fullness + orange][0] = true;
					queue.add(new int[] {fullness + orange, 0});
				}
				if (fullness + lemon <= maxFullness && !visited[fullness + lemon][0]) {
					visited[fullness + lemon][0] = true;
					queue.add(new int[] {fullness + lemon, 0});
				}
				if (!visited[fullness / 2][1]) {
					visited[fullness / 2][1] = true;
					queue.add(new int[] {fullness / 2, 1});
				}
			}
		}
 
		for (int i = maxFullness; i >= 0; i--) {
			if (visited[i][0] || visited[i][1]) {
				pw.println(i);
				break;
			}
		}
 
		br.close();
		pw.close();
	}
}


from collections import deque
 
with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())
 
# visited[i][0] es agua no usada; visited[i][1] es agua usada
visited = [[False, False] for _ in range(max_fullness + 1)]
visited[0][0] = True
 
# (saciedad, agua)
q = deque()
q.append((0, 0))
 
while q:
	fullness, water = q.popleft()
	if water:
		if fullness + orange <= max_fullness and not visited[fullness + orange][1]:
			visited[fullness + orange][1] = True
			q.append((fullness + orange, 1))
		if fullness + lemon <= max_fullness and not visited[fullness + lemon][1]:
			visited[fullness + lemon][1] = True
			q.append((fullness + lemon, 1))
	else:
		if fullness + orange <= max_fullness and not visited[fullness + orange][0]:
			visited[fullness + orange][0] = True
			q.append((fullness + orange, 0))
		if fullness + lemon <= max_fullness and not visited[fullness + lemon][0]:
			visited[fullness + lemon][0] = True
			q.append((fullness + lemon, 0))
		if not visited[fullness // 2][1]:
			visited[fullness // 2][1] = True
			q.append((fullness // 2, 1))
 
with open("feast.out", "w") as fout:
	for i in range(max_fullness, -1, -1):
		if visited[i][0] or visited[i][1]:
			fout.write(f"{i}\n")
			break

Implementación - DFS

Complejidad temporal: $\mathcal{O}(T)$ , donde $T$ es la saciedad máxima.

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
 
int max_fullness, orange, lemon;
vector<pair<bool, bool>>
    visited;  // visited[i][0] es agua no usada; visited[i][1] es agua usada
 
void dfs(int fullness, bool water) {
	if (water) {
		if (visited[fullness].second) { return; }
		visited[fullness].second = true;
		if (fullness + orange <= max_fullness) { dfs(fullness + orange, true); }
		if (fullness + lemon <= max_fullness) { dfs(fullness + lemon, true); }
	} else {
		if (visited[fullness].first) { return; }
		visited[fullness].first = true;
		if (fullness + orange <= max_fullness) { dfs(fullness + orange, false); }
		if (fullness + lemon <= max_fullness) { dfs(fullness + lemon, false); }
		dfs(fullness / 2, true);
	}
}
 
int main() {
	ifstream fin("feast.in");
	ofstream fout("feast.out");
 
	fin >> max_fullness >> orange >> lemon;
 
	visited.assign(max_fullness + 1, {false, false});
 
	dfs(0, false);
 
	for (int i = max_fullness; i >= 0; i--) {
		if (visited[i].first || visited[i].second) {
			fout << i << endl;
			break;
		}
	}
}


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;
		if (fullness + orange <= maxFullness) { dfs(fullness + orange, water); }
		if (fullness + lemon <= maxFullness) { dfs(fullness + lemon, water); }
		if (water == 0) { dfs(fullness / 2, 1); }
	}
 
	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());
 
		maxFullness = Integer.parseInt(st.nextToken());
		orange = Integer.parseInt(st.nextToken());
		lemon = Integer.parseInt(st.nextToken());
 
		// visited[i][0] es agua no usada; visited[i][1] es agua usada
		visited = new boolean[maxFullness + 1][2];
 
		dfs(0, 0);
 
		for (int i = maxFullness; i >= 0; i--) {
			if (visited[i][0] || visited[i][1]) {
				pw.println(i);
				break;
			}
		}
 
		br.close();
		pw.close();
	}
}


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] es agua no usada; visited[i][1] es agua usada
visited = [[False, False] for _ in range(max_fullness + 1)]
 
 
def dfs(fullness, water):
	if visited[fullness][water]:
		return
	visited[fullness][water] = True
	if fullness + orange <= max_fullness:
		dfs(fullness + orange, water)
	if fullness + lemon <= max_fullness:
		dfs(fullness + lemon, water)
	if water == 0:
		dfs(fullness // 2, 1)
 
 
dfs(0, 0)
 
with open("feast.out", "w") as fout:
	for i in range(max_fullness, -1, -1):
		if visited[i][0] or visited[i][1]:
			fout.write(f"{i}\n")
			break