레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Hiring
English 1.1
고용 (HIRING)
여러분은 건설 프로젝트를 위해 노동자를 고용해야 한다. 1부터 N까지 번호가 매겨진 N명의 지원자가 있다. 각 지원자 k는 고용된다면 최소 Sk 달러를 받아야 한다고 요구한다. 또한 각 지원자 k에게는 자격 수준 Qk가 있다. 건설 업계 규정에 따르면 노동자들에게는 서로의 자격 수준에 비례하여 임금을 지급해야 한다. 예를 들어 두 노동자 A와 B를 고용했고 QA = 3 * QB라면, 노동자 A에게 노동자 B의 정확히 세 배를 지급해야 한다. 임금은 정수가 아닌 금액으로 지급해도 된다. 여기에는 3분의 1달러나 6분의 1달러처럼 십진법으로 유한한 자리로 표현할 수 없는 양도 포함된다.
여러분에게는 W 달러가 있고 가능한 한 많은 노동자를 고용하고 싶다. 누구를 고용하고 얼마를 지급할지는 여러분이 정하지만, 고용하기로 한 사람들의 최소 임금 요구를 충족해야 하고 업계 규정을 지켜야 한다. 또한 예산 W 달러를 초과하면 안 된다.
프로젝트의 특성상 자격 수준은 전혀 중요하지 않으므로, 자격 수준과 무관하게 노동자 수를 최대화하는 데만 관심이 있다. 다만 이를 달성하는 방법이 여러 가지라면, 노동자들에게 지급해야 하는 총액이 가장 작은 방법을 원한다. 그런 방법도 여러 가지라면 그중 어느 것이든 상관없다.
TASK
지원자들의 서로 다른 임금 요구와 자격 수준, 그리고 가진 돈이 주어졌을 때, 어느 지원자들을 고용해야 하는지 결정하는 프로그램을 작성하시오. 위에 명시된 업계 규정을 지키면서, 가능한 한 많이 고용하고 가능한 한 적은 돈으로 고용해야 한다.
EXAMPLES
Sample Input
Sample Output
4 100
5 1000
10 100
8 10
20 1
2
2
3
두 명의 노동자를 고용하면서 모든 제약을 지킬 수 있는 유일한 조합은 노동자 2와 3을 선택하는 것이다. 각각 80달러와 8달러를 지급하면 예산 100달러 안에 들어간다.
Sample Input
Sample Output
3 4
1 2
1 3
1 3
3
1
2
3
여기서는 세 노동자를 모두 고용할 수 있다. 노동자 1에게 1달러, 노동자 2와 3에게 각각 1.50달러를 지급하면, 가진 4달러로 전원을 고용할 수 있다.
Sample Input
Sample Output
3 40
10 1
10 2
10 3
2
2
3
여기서는 세 노동자를 모두 고용하면 60달러가 들어 불가능하지만, 어느 두 명이든 고용할 수는 있다. 다른 두 명 조합에 비해 지급할 돈의 합이 가장 작으므로 노동자 2와 3을 고용한다. 노동자 2에게 10달러, 노동자 3에게 15달러, 총 25달러를 지급하면 된다. 노동자 1과 2를 고용한다면 각각 최소 10달러와 20달러를 지급해야 한다. 노동자 1과 3을 고용한다면 각각 최소 10달러와 30달러를 지급해야 한다.
\(1 \le N \le 500,000\)
지원자의 수
\(1 \le Sk \le 20,000\)
지원자 k의 최소 임금 요구
\(1 \le Qk \le 20,000\)
지원자 k의 자격 수준
\(1 \le W \le 10,000,000,000\)
여러분이 가진 돈
IMPORTANT NOTE
W의 최댓값은 32비트에 들어가지 않는다. W의 값을 하나의 변수에 저장하려면 C/C++의 long long이나 Pascal의 int64 같은 64비트 자료형을 사용해야 한다. 자세한 내용은 기술 안내문을 참조하시오.
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N과 W가 공백으로 구분되어 주어진다.
• 다음 N개의 줄에는 지원자들이 한 줄에 한 명씩 설명된다. 이 중 k번째 줄은 지원자 k를 설명하며, 정수 Sk와 Qk가 공백으로 구분되어 주어진다.
August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Hiring
English 1.1
프로그램은 표준 출력에 다음 데이터를 출력해야 한다:
• 첫 줄에는 고용하는 노동자의 수인 정수 H 하나를 출력해야 한다.
• 다음 H개의 줄에는 고용하기로 한 지원자들의 번호(각각 1 이상 N 이하의 서로 다른 수)를 임의의 순서로 한 줄에 하나씩 나열해야 한다.
GRADING
어떤 테스트 케이스든, 선택한 지원자들이 모든 제약을 만족하면서 모든 목표를 달성하면 만점을 받는다. 첫 줄(즉, H의 값)은 올바르지만 위 설명을 충족하지 못하는 출력을 내면 해당 테스트 케이스 점수의 50%를 받는다. 첫 줄만 올바르다면 출력 파일의 형식이 올바르지 않아도 마찬가지이다.
총 50점에 해당하는 여러 테스트에서 N은 5,000을 넘지 않는다.