In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
You have to hire workers for a construction project. There are candidates applying for the job,
numbered from
to
inclusive. Each candidate
requires that if he is hired, he must be paid at
least
dollars. Also, each candidate
has a qualification level
. 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
and
, and
, then you
have to pay worker
exactly three times as much as you pay worker
. 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 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
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.
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.
- the number of candidates
- the minimum salary requirement of candidate
- the qualification level of candidate
- the amount of money available to you
The maximum value of 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
in a single variable.
Your program must read from standard input the following data:
Your program must write to standard output the following data:
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 ), 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, will not exceed
.
For the input data:
4 100 5 1000 10 100 8 10 20 1
the correct result is:
2 2 3
Explanation of the example: 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.
For the input data:
3 4 1 2 1 3 1 3
the correct result is:
3 1 2 3
Explanation of the example: 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.
For the input data:
3 40 10 1 10 2 10 3
the correct result is:
2 2 3
Explanation of the example: 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.