프로그램 명: ioi_hiring(special judge)
제한시간: 2 초
[문제 요약]
회사에서 사람들을 고용하고자 하는데 N명의 사람들이 지원했고 1에서 N까지 번호가 붙어있습니다.
어떤 사람 k가 원하는 최소임금 Sk와 일에대한 숙련도 Qk가 주어져 있습니다.
임금규정에 의해 고용한 사람들에게 숙련도에 비례하는 임금을 주어야 합니다.
예를 들어 두 지원자 A,B에 대해 QA = 3QB라면 A의 임금이 B의 임금의 3배여야 한다는 뜻입니다. 그리고 임금은 실수범위에 속하는 값을 줄수도 있습니다.
예산 W가 주어질때 이 금액 내에서 최대한 많은 사람을 고용하는 문제입니다.
당연히 고용한 사람들은 자기가 원하는 최소임금 이상의 임금을 받아야 하고, 회사의 임금규정을 만족하는 방법을 선택해야 합니다. 이런방법이 많다면 지불하는 총 임금이 가장 작게 만들면 됩니다.
You have to hire workers for a construction project. There are N candidates applying for the job,
numbered from 1 to N inclusive. Each candidate k requires that if he is hired, he must be paid at
least Sk dollars. Also, each candidate k has a qualification level Qk. The regulations of the
construction industry require that you pay your workers in proportion to their qualification level,
relative to each other. For example, if you hire two workers A and B, and QA = 3 * QB, then you
have to pay worker A exactly three times as much as you pay worker B. You are allowed to pay
your workers non-integer amounts of money. This even includes quantities that cannot be written
with a finite number of digits in decimal form, such as a third or a sixth of a dollar.
You have W dollars at hand and you want to hire as many workers as possible. You decide
whom to hire and how much to pay them, but you have to meet the minimum salary
requirements of those you choose to hire, and you have to obey the industry regulations. You
also have to fit within your budget of W dollars.
The nature of your project is such that the qualification level is completely irrelevant, so you are
only interested in maximizing the number of workers without regard to their qualification level.
However, if there is more than one way to achieve this, then you want to select the one where
the total amount of money you have to pay your workers is as small as possible. In case there is
more than one way to achieve this, then you are indifferent among these ways and you would be
satisfied with any one of them.
TASK
Write a program that, given the different salary requirements and qualification levels of the
candidates, as well as the amount of money you have, determines which candidates you should
hire. You must hire as many of them as possible and you must do so with as little money as
possible, while complying with the industry regulations specified above.
CONSTRAINTS
1 ￡ N ￡ 500,000 The number of candidates
1 ￡ Sk ￡ 20,000 The minimum salary requirement of candidate k
1 ￡ Qk ￡ 20,000 The qualification level of candidate k
1 ￡ W ￡ 10,000,000,000 The amount of money available to you
IMPORTANT NOTE
The maximum value of W does not fit in 32 bits. You have to use a 64-bit data type, such as
long long in C/C++ or int64 in Pascal, in order to store the value of W in a single variable.
Please see the technical info sheet for details.
INPUT
OUTPUT
GRADING
For any given test case, you will receive full points if your choice of candidates enables you to
achieve all of your goals, while satisfying all constraints. If you produce an output file with a
correct first line (i.e., a correct value of H), but which does not meet the above description, you
will receive 50% of the points for that test case. The latter will be the case even if the output file
is not properly formatted, as long as the first line is correct.
For a number of tests, worth a total of 50 points, N will not exceed 5,000.
EXAMPLES
Sample Input Sample Output
4 100
5 1000
10 100
8 10
20 1
2
2
3
The only combination for which you can afford to hire two workers and still meet all the
constraints is if you select workers 2 and 3. You can pay them 80 and 8 dollars respectively and
thus fit in your budget of 100.
Here you can afford to hire all three workers. You pay 1 dollar to worker 1 and 1.50 dollars each
to workers 2 and 3, and you manage to hire everyone with the 4 dollars that you have.
Sample Input Sample Output
Here you cannot afford to hire all three workers, as it would cost you 60 dollars, but you can
afford to hire any two of them. You choose to hire workers 2 and 3 because they would cost you
the smallest sum of money, compared to the other two-worker combinations. You can pay 10
dollars to worker 2 and 15 dollars to worker 3 for a total of 25 dollars. If you were to hire workers
1 and 2 you would have to pay them at least 10 and 20 dollars respectively. If you were to hire 1
and 3, then you would have to pay them at least 10 and 30 dollars respectively.
입력
Your program must read from standard input the following data:
· The first line contains the integers N and W, separated by a space.
· The next N lines describe the candidates, one candidate per line. The kth of these lines
describes candidate number k and it contains the integers Sk and Qk, separated by a space.
출력
Your program must write to standard output the following data:
· The first line must contain a single integer H, the number of workers that you hire.
· The next H lines must list the identifying numbers of the candidates you choose to hire (each
of them a different number between 1 and N), one per line, in any order.
입출력 예
입력
3 4
1 2
1 3
1 3
출력
3
1
2
3
입력
3 40
10 1
10 2
10 3
출력
2
2
3
출처: International Olympiad In Informatics 2009
요약+special judge: august14
[질/답]
[제출 현황]
[푼 후(0)]