인덱스국 선발고사 I (Team Selection I)

문제

인덱스국 선발고사 : Day 1

인덱스국의 선발고사는 1차 4문제, 2차 4문제로 총 8문제의 인덱스 트리 문제가 출제됩니다.

인덱스국의 왕 (검열됨)은 세그먼트 트리를 사용하는 반란군의 첩자가 선발고사에 응시했다는 첩보를 받았습니다. 하지만 이미 선발고사는 모두 끝난 후였고, 모두가 자신의 점수를 알고 있기 때문에 조작은 불가능합니다. 그러나 아직 정해지지 않은 값이 하나 있는데, 바로 1차 선발고사와 2차 선발고사의 반영 비율입니다. 반영 비율은 a : b로 표현되며 a, b는 서로소인 한 자리 자연수여야 합니다. 1차 선발고사의 점수를 x, 2차 선발고사의 점수를 y라고 할 때, ax + by가 총 점수가 됩니다. 총 점수가 높은 K명이 최종 선발되며, 총 점수가 같다면 이름이 사전순으로 빠른 사람이 선발됩니다. 인덱스국의 왕은 아직 누가 첩자인지 모르기 때문에, 모든 응시자들에 대해 응시자를 떨어트릴 수 있는 가장 그럴듯한 반영 비율을 구해 두어야 합니다. 국민들은 반영 비율 a : b에 대해 |a − b|가 작은 비율을 그럴듯하다고 느끼며, |a − b|가 같다면 a + b가 작은 비율을 그럴듯하다고 느끼며, a + b도 같다면 a가 더 작은 비율을 그럴듯하다고 느낍니다. 모든 응시자들에 대해 응시자를 떨어트릴 수 있는 가장 그럴듯한 반영 비율을 구해주는 프로그램을 작성해주세요.

구현 세부 사항

다음 함수를 구현하세요.

void getFailRatio(int K, string S[], int X[], int Y[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• K는 최종 선발 인원입니다.
• S, X, Y 는 크기 N 의 배열입니다. 모든 0 ≤ i ≤ N − 1에 대해 i + 1번 응시자 S[i]의 1차 선발고사 점수가 X[i], 2차 선발고사 점수가 Y[i]입니다.

getFailRatio는 다음 함수를 호출할 수 있습니다.

void answer(int x, int a, int b)

• getFailRatio는 이 함수를 사용해서 답을 출력합니다.
• x번 응시자를 떨어트리기 위한 가장 그럴듯한 반영 비율이 a : b일 경우 answer(x, a, b)를 호출해야 합니다. 단, x번 응시자를 떨어트리는 것이 불가능할 경우, answer(x, −1, −1)을 호출해야 합니다.
• 1 ≤ x ≤ N 을 만족하지 않거나, 같은 x에 대해서 answer를 여러번 호출해서는 안됩니다.

제한 조건

• 0 ≤ K < N ≤ 100
• 응시자들의 이름은 알파벳 소문자 10글자 이하로, 모두 다릅니다.
• 5 ≤ X[i], Y[i] ≤ 369 (0 ≤ i ≤ N − 1)

서브태스크

서브태스크	점수	제한 조건
1	1	예제 입력
2	2	X[i] = Y[i] (0 ≤ i ≤ N − 1)
3	2	추가 제한 조건 없음

예제 입출력

K = 2, S = ["messi", "diuven", "tamref"], X = [200, 300, 100], Y = [100, 300, 200]

그레이더는 다음 함수를 호출합니다.

getFailRatio(2, ["messi", "diuven", "tamref"], [200, 300, 100], [100, 300, 200])

getFailRatio는 다음 함수를 호출하여 답을 출력합니다.

answer(2, -1, -1)

answer(1, 1, 2)

answer(3, 1, 1)

샘플 그레이더

Sample Grader는 다음과 같은 형식으로 입력을 받습니다.

• line 1 : N K
• line 2 + i (0 ≤ i ≤ N − 1) : S[i] X[i] Y[i]