TypingJob

SRM 123 · 2002-12-10 · by axchma

Class Name: TypingJob

Return Type: int

Method Name: bestTime

Arg Types: (vector<int>)

Problem Statement

You have three assistants working for you. They all type with the same speed of one page per minute. You came to your office today with a bunch of papers you need to have typed as soon as possible. You have to distribute the papers among your assistants in such a way that they finish all the papers at the earliest possible time.

Your task is, given an int[] with the number of pages for each paper, return the minimum number of minutes needed for your assistants to type all these papers. Assume that they can't divide a paper into parts, that is, each paper is typed by one person.

Constraints

pages has between 1 and 10 elements inclusive
each element of pages is between 1 and 100 inclusive

Examples

{38}
Returns: 38

{15,10,5,7,8}
Returns: 15

The first secretary can type the 15-page paper. The second secretary can type the 10-page and 5-page papers. The third secretary can type the 7-page and 8-page papers.

{100,100,100,100,100,100,100,100,100,100}
Returns: 400

{1,2,3,4,5}
Returns: 5

{1,2,3,4,5,6,7}
Returns: 10

16)

{1,1,2,3,5,8,13,21,34,55}
Returns: 55

Fibonnaci numbers

17)

{4,76,41,49,57,85,41,29,3,11}
Returns: 133

Ten random test cases

Submissions are judged against all 49 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TypingJob with a public method int bestTime(vector<int> pages) · 49 test cases · 2 s / 256 MB per case