IZhO 2014 - Bank

Author: Kevin Sheng

Edit This Page

Table of Contents

ExplanationImplementation

Explanation

We do dynamic programming on all subsets of the notes.

Let covered[S]\texttt{covered}[S] be the maximum prefix of people we can pay off using the notes defined in the subset, and leftover[S]\texttt{leftover}[S] be the leftover amount of money we have after we pay off the prefix of the people.

When transitioning, iterate over all possible "ending" banknotes and see how each of them would fit in when you put them onto the leftovers of the previous subset.

Implementation

Time Complexity: O(M2M)\mathcal{O}(M2^M)

C++

#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	int people_num;
	int note_num;

Java

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));

Python

The following code runs in time only if you submit with 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

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