VMSS '15 #5 - Jeffrey and Frank and a Lack of Roads

View as PDF

Submit solution

Points: 12
Time limit: 2.5s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Frank has made it to a Food Basics! Without causing property damage exceeding $1000! There he meets Jeffrey (since grocery stores don't have roads) and he agrees to help Frank buy some apples. You must also help Frank buy some apples.

The Food Basics that Frank is visiting has N different types of apples, and he can take as much as he can of each type. However, there are some restrictions: Frank has only R dollars to spend on apples, and his car can only hold S volume, excluding Frank's volume (Frank obviously isn't giving Jeffrey a ride, as cars drive on roads).

Frank also likes some types of apples more than others, and he assigns a value V to each type of apple. Frank likes apples with larger values.

Jeffrey and Frank would like to buy apples in such a way so that he can maximise the total sum of all values of apples. Help them calculate it!

Input Specification

The first line of input will contain the integers N (1 \leq N \leq 10), R, and S (1 \leq R, S \leq 1\,000).

The next N lines will each denote a type of apple and be in the form E V A B, where E is the name of the apple type, V (1 \leq V \leq 1\,000) is the value given to the type of apple, A (1 \leq A \leq R) is the cost of one of these apples in dollars, and B (1 \leq B \leq S) is the volume that one of these apples takes up.

It is guaranteed that the apples will be given in alphabetical order by name. Apple names will be strings of latin characters, without spaces. Each apple name will not exceed 32 characters in length. Each type of apple will have a unique name.

Output Specification

First, print out the maximum value sum of apples that Frank can buy. Then, for each type of apple (in alphabetical order) print out a line with the apple type and the number of apples Frank should buy to maximise value.

If there are multiple answers, print any of them.

Sample Input

3 250 250
gala 500 20 4
goldendelicious 450 1 25
green 380 13 4

Sample Output

gala 1
goldendelicious 7
green 17

Sample Explanation

In order to maximise the value of apples purchased, Jeffrey and Frank should buy seven goldendelicious apples, 17 green apples, and 1 gala apple. The sum of the values of the apples they buy will be 10\,110.


  • 1
    andi_g  commented on Aug. 14, 2016, 12:34 p.m.

    If in order to maximize the value of their apples, they shouldn't buy one of the apples, should you include that in your output? For example, if they needed 0 gala apples, 7 golden delicious, and 17 green would the output be:

    gala 0
    goldendelicious 7
    green 17

    • 0
      Pleedoh  commented on Sept. 4, 2017, 7:47 p.m.

      For those who still care

      Then, for each type of apple (in alphabetical order) print out a line with the apple type and the number of apples Frank should buy to maximise value.

      Yes, I believe so.

      • -1
        Evan  commented on April 1, 2020, 3:50 p.m. edited