Skip to Content
CTRL K

Bank

Explicación

Hacemos programación dinámica sobre todos los subconjuntos de los billetes.

Sea covered[S]\texttt{covered}[S] el prefijo máximo de personas que podemos pagar usando los billetes definidos en el subconjunto, y leftover[S]\texttt{leftover}[S] la cantidad de dinero sobrante que tenemos después de pagar el prefijo de las personas.

Al transicionar, iteramos sobre todos los posibles billetes “finales” y vemos cómo encajaría cada uno al colocarlo sobre los sobrantes del subconjunto previo.

Implementación

Complejidad temporal: O(M2M)\mathcal{O}(M2^M)

#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int people_num;
	int note_num;
	std::cin >> people_num >> note_num;
	vector<int> people(people_num);
	vector<int> banknotes(note_num);
	for (int &p : people) { std::cin >> p; }
	for (int &b : banknotes) { std::cin >> b; }
 
	vector<int> leftover(1 << note_num, -1);
	vector<int> people_covered(1 << note_num, -1);
	leftover[0] = 0;
	people_covered[0] = 0;
	for (int s = 0; s < (1 << note_num); s++) {
		for (int last = 0; last < note_num; last++) {
			if ((s & (1 << last)) == 0) { continue; }
			int prev = s & ~(1 << last);
			if (people_covered[prev] == -1) { continue; }
 
			int new_amt = leftover[prev] + banknotes[last];
			// el salario de la persona actual a la que vamos a intentar pagar
			int curr_target = people[people_covered[prev]];
			// si aún no alcanza, solo incrementamos el montón de sobrantes
			if (new_amt < curr_target) {
				people_covered[s] = people_covered[prev];
				leftover[s] = new_amt;
			}
			/*
			 * o es exactamente el monto, en cuyo caso reiniciamos el conteo de sobrantes
			 * e incrementamos la cantidad cubierta
			 */
			else if (new_amt == curr_target) {
				people_covered[s] = people_covered[prev] + 1;
				leftover[s] = 0;
			}
		}
		// ¡hemos cubierto a todas las personas!
		if (people_covered[s] == people_num) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Bank {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int peopleNum = Integer.parseInt(initial.nextToken());
		int noteNum = Integer.parseInt(initial.nextToken());
		int[] people = Arrays.stream(read.readLine().split(" "))
		                   .mapToInt(Integer::parseInt)
		                   .toArray();
		int[] banknotes = Arrays.stream(read.readLine().split(" "))
		                      .mapToInt(Integer::parseInt)
		                      .toArray();
 
		int[] leftover = new int[1 << noteNum];
		int[] peopleCovered = new int[1 << noteNum];
		Arrays.fill(leftover, -1);
		Arrays.fill(peopleCovered, -1);
		leftover[0] = 0;
		peopleCovered[0] = 0;
		for (int s = 0; s < (1 << noteNum); s++) {
			for (int last = 0; last < noteNum; last++) {
				if ((s & (1 << last)) == 0) { continue; }
				int prev = s & ~(1 << last);
				if (peopleCovered[prev] == -1) { continue; }
 
				int new_amt = leftover[prev] + banknotes[last];
				// el salario de la persona actual a la que vamos a intentar pagar
				int curr_target = people[peopleCovered[prev]];
				// si aún no alcanza, solo incrementamos el montón de sobrantes
				if (new_amt < curr_target) {
					peopleCovered[s] = peopleCovered[prev];
					leftover[s] = new_amt;
				}
				/*
				 * o es exactamente el monto, en cuyo caso reiniciamos el conteo de sobrantes
				 * e incrementamos la cantidad cubierta
				 */
				else if (new_amt == curr_target) {
					peopleCovered[s] = peopleCovered[prev] + 1;
					leftover[s] = 0;
				}
			}
			// ¡hemos cubierto a todas las personas!
			if (peopleCovered[s] == peopleNum) {
				System.out.println("YES");
				return;
			}
		}
		System.out.println("NO");
	}
}

El siguiente código corre a tiempo solo si se envía con PyPy.

from sys import exit
 
people_num, note_num = [int(i) for i in input().split()]
people = [int(i) for i in input().split()]
banknotes = [int(i) for i in input().split()]
 
leftover = [-1 for _ in range(1 << note_num)]
people_covered = [-1 for _ in range(1 << note_num)]
leftover[0] = 0
people_covered[0] = 0
for s in range(1, 1 << note_num):
	for last in range(note_num):
		if (s & (1 << last)) == 0:
			continue
		prev = s & ~(1 << last)
		if people_covered[prev] == -1:
			continue
 
		new_amt = leftover[prev] + banknotes[last]
		# el salario de la persona actual a la que vamos a intentar pagar
		curr_target = people[people_covered[prev]]
		# si aún no alcanza, solo incrementamos el montón de sobrantes
		if new_amt < curr_target:
			people_covered[s] = people_covered[prev]
			leftover[s] = new_amt
			"""
			o es exactamente el monto, en cuyo caso reiniciamos el conteo de sobrantes
			e incrementamos la cantidad cubierta
			"""
		elif new_amt == curr_target:
			people_covered[s] = people_covered[prev] + 1
			leftover[s] = 0
 
	# ¡hemos cubierto a todas las personas!
	if people_covered[s] == people_num:
		print("YES")
		exit()
print("NO")
Fundamentos