제안 요청서 (RFP)

정부, 군, 또는 기업 기관이 대규모 구매를 하려고 할 때, 먼저 성공적인 제안이 충족해야 하는 여러 요구사항을 나열한 제안 요청서(RFP, Request for Proposal)를 발행한다. 경쟁하는 공급업체들은 각자 어떤 요구사항을 충족하는지와, 기관이 제안을 수락할 경우 청구할 가격을 표시한 제안서(Proposal)를 제출한다.

이 기관들은 관료들로 구성되어 있고 또 다른 관료 기관에 책임을 지므로, 선정 과정에서 모든 인간의 주관적 판단을 배제해야 한다. 이를 위해 각 평가자는 평가표를 받는다. 평가표에는 요구사항마다 한 개의 열, 가격을 위한 추가 열 한 개, 그리고 제안서마다 한 개의 행이 있다. 평가자는 각 제안서를 읽고, 충족된 요구사항마다 해당 칸에 체크 표시를 한다. 모든 제안서를 평가한 뒤, 각 행의 체크 표시 개수를 합산한다. 체크 표시의 개수가 요구사항의 개수와 같은 제안서를 완전 충족(compliant)이라 하고, 그렇지 않으면 부분 충족(partially compliant)이라 한다.

많은 기관은 완전 충족 제안서 중 가격이 가장 낮은 것에 계약을 준다. 완전 충족 제안서가 하나도 없으면, 많은 기관은 다음 식으로 부분 충족도를 계산한다.

$$\text{충족도} = \frac{\text{충족한 요구사항 수}}{\text{요구사항 수}}$$

여러분의 임무는 충족도가 가장 높은 제안서를 선택하는 것이다. 충족도가 가장 높은 제안서가 여럿이면 그중 가격이 가장 낮은 것을 선택한다. 충족도와 가격이 모두 같은 제안서가 여럿이면 입력에서 가장 먼저 나오는 것을 선택한다.

입력은 여러 개의 RFP와 그에 딸린 제안서들의 정보로 이루어진다. 각 RFP의 정보는 다음과 같다.

• 두 정수가 담긴 한 줄: 요구사항의 수 $n$ ($0 < n \le 1000$)과 제안서의 수 $p$. 0 0인 줄은 더 이상 RFP가 없음을 뜻한다.
• 요구사항의 이름이 담긴 $n$개의 줄. 각 요구사항은 최대 80자의 문자열이며 줄 끝으로 끝난다. 모든 문자열은 대소문자를 구분한다.
• $p$개의 제안서 각각에 대해:
  • 제안서의 이름이 담긴 한 줄(최대 80자, 줄 끝으로 끝남).
  • 실수 $d$와 정수 $r$ ($0 \le r \le n$)이 담긴 한 줄. $d$는 가격이고, $r$은 뒤에 이어질 충족 요구사항 줄의 개수이다.
  • 충족한 요구사항마다 그 이름이 각각 한 줄씩. 모든 요구사항은 이 RFP의 요구사항 목록에 있으며, 중복되지 않는다.

각 RFP에 대해, RFP의 번호(예시 참고)를 출력한 뒤 위 기준에 따라 가장 좋은 제안서의 이름을 출력한다. 연속한 두 RFP의 출력 사이에는 빈 줄을 하나 넣는다.