Hiring

SRM 93 · 2002-05-30 · by Perlaze

Class Name: Hiring

Return Type: int

Method Name: recruit

Arg Types: (int, vector<string>)

Problem Statement

Grover, Inc. is looking to hire three new employees. After giving all of the potential employees interviews, they have narrowed it down to a list of a few qualified and impressive candidates. Unfortunately, the company recruiter has been given a strict budget for his new hires. He decides that he would like to hire the three new employees such that they have the highest possible average score on the technical exam, but the sum of their expected salaries is in adherence (less than or equal) to the budget.

Given the budget for new hires (in thousands) and a list of the possible employees, including their percentage score on the technical exam and their expected salaries (in thousands), determine the combination of employees that the company would hire. Return their average technical exam score, rounding up to the nearest integer if the decimal portion is .5 or higher, and rounding down otherwise. If there is no such set of three possible employees that can be hired, return -1.

Each element of applicants will be formatted as: "<employeeName>,<examScore>,<expectedSalary>", where <employeeName> is a sequence of between 1 and 20, inclusive, lowercase letters ('a'-'z'), <examScore> is an integer between 1 and 100, inclusive, and <expectedSalary> is an integer between 20 and 250, inclusive.

Constraints

budget will be an integer between 1 and 1000, inclusive.
applicants will contain between 3 and 50 elements, inclusive.
each item in applicants will be of the form ",,". Note that these values are only comma separated, and will never have leading or trailing whitespace.
will be between 1 and 20 characters, inclusive, and will only contain the characters 'a'-'z'.
No two employees will have the same .
will be an integer between 1 and 100, inclusive, with no leading zeroes.
will be an integer between 20 and 250, inclusive with be no leading zeroes.

Examples

270
{"ndbronson,99,99", "malpt,97,90", "ambrose,97,70", "dmwright,94,100", "jonmac,98,94"}
Returns: 98

The recruiter would choose ndbronson, ambrose, and jonmac.

299
{"reid,100,100", "dgarthur,100,100", "zorbathut,100,100"}
Returns: -1

The recruiter could not hire three employees with this budget.

240
{"derkuci,85,70", 
 "doeth,87,69",
 "snapdragon,82,75",
 "obfuscator,89,70",
 "evd,89,100",
 "milhouse,77,77",
 "stevevai,79,91",
 "po,83,76",
 "joe,90,73"}
Returns: 89

The recruiter would choose doeth, obfuscator, and joe.

200
{"a,70,70", "b,60,80", "c,100,100", "d,99,99", "e,98,98", "f,55,62", "g,66,66", "h,55,55", "i,100,100", "j,79,74", "k,98,98", "l,44,44", "m,33,33", "n,22,22", "o,69,69", "p,42,42", "q,11,80", "r,100,25", "s,50,50", "t,78,72", "u,82,69", "v,36,64", "w,99,24", "x,34,36", "y,92,92", "aa,70,70", "bb,60,80", "cc,100,100", "dd,99,99", "ee,98,98", "ff,55,62", "gg,66,66", "hh,55,55", "ii,100,100", "jj,79,74", "kk,98,98", "ll,44,44", "mm,33,33", "nn,22,22", "oo,69,69", "pp,42,42", "qq,11,80", "rr,50,25", "ss,50,50", "tt,78,72", "uu,82,69", "vv,36,64", "ww,99,24", "xx,34,36", "yy,50,50"}
Returns: 100

150
{"a,50,50", "b,51,50", "c,51,50"}
Returns: 51

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

Coding Area

Language: C++17 · define a public class Hiring with a public method int recruit(int budget, vector<string> applicants) · 58 test cases · 2 s / 256 MB per case