시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 6 | 5 | 4 | 80.000% |
The country of Fairland has very strict laws governing how companies organize and pay their employees:
The government of Fairland has just passed one additional law:
Marie is the CEO of the Fairland General Stuff Corporation, and she has to ensure that her company complies with the new law. This may require laying off some employees. She has the list of the company's employees, their managers, and their salaries. What is the largest number of employees she can keep, including herself?
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing two space-separated integers N (the number of employees) and D (the maximum allowed salary difference). This is followed by one line with four space-separated integers (S0, As, Cs, Rs) and then another line with four more space-separated integers (M0, Am, Cm and Rm). These last eight integers define the following sequences:
Marie's employee ID is 0, and all other employees have IDs from 1 to N - 1, inclusive. The salary of employee i is Si. For every employee i other than Marie, the manager is Mi mod i. (Note that this means that M0 does not affect Marie's manager -- she has none!)
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the largest number of employees Marie can keep at the company, including herself, such that all of laws 1-7 are obeyed.
3 1 395 18 246 615815 60 73 228 14618 195 6 5 10 1 3 17 5 2 7 19 10 13 28 931 601463 36 231 539 556432 258
Case #1: 1 Case #2: 3 Case #3: 5
In Case #1, the company has only a CEO and no other employees, but it does not violate any of the laws, so no changes need to be made.
Here is the org chart for Case #2:
The optimal strategy is to save employees 0, 1, and 5 (who have salaries of 10, 13, and 8, respectively). It is not possible to save employee 2, for example, because her salary is more than 5 away from employee 0's salary of 10; since employee 0 cannot be laid off, employee 2 must be laid off (along with all employees who report to her).
If you want to check your sequences for employees 1 through 5, they are:
S: 13, 16, 2, 5, 8
M: 17, 3, 13, 14, 16
Manager numbers: 17 % 1 = 0, 3 % 2 = 1, 13 % 3 = 1, 14 % 4 = 2, 16 % 5 = 1
Contest > Google > Code Jam > Google Code Jam 2015 > Round 3 A2번