객관식 시험은 채점하기가 쉽기 때문에 일부 교사들 사이에서 매우 인기가 있습니다. 일부 학생들은 이를 좋아하고("답을 전혀 모르더라도 맞출 기회가 있다"), 일부 학생들은 싫어합니다("어딘가에 함정이 있을 것이다"). 객관식 문제의 궁극적인 형태는 참/거짓 문제입니다.
이제 여러분이 참/거짓 시험을 보고 있다고 가정해봅시다. 각 문제에 대해, 두 답안 중 각각이 정답일 확률에 대한 사전 추정치가 있습니다. i번째 문제에 대해, "예"가 정답일 확률이 yi이고, "아니오"가 정답일 확률이 1 - yi입니다. 당연히 yi와 1 - yi 중 더 큰 쪽을 선택해야 합니다(yi = 1/2인 경우 어느 쪽이든 선택할 수 있습니다).
함정이 있다면? 모든 문제에 대해 "예"의 추정치가 "아니오"보다 높다면, 뭔가 이상하다고 의심할 수 있습니다. 대부분의 교사들은 답안지에 명확한 패턴이 있는 것을 좋아하지 않고 답을 섞으려고 합니다. 이 특정 교사가 항상 "예" 답변의 수를 ℓ과 r 사이(포함)로 유지한다고 가정해봅시다(ℓ ≤ r). 그렇다면, 예상되는 총 정답 수를 최대화하기 위해 "예"로 답할 문제를 선택하는 것은 더 이상 쉽지 않습니다. 그러므로 프로그램을 작성하는 것이 좋겠습니다. 구체적으로, 예상되는 정답 수를 최대화하면서 "예" 답변을 최소 ℓ번, 최대 r번 사용하는 모든 문제에 대한 답을 찾고 싶습니다.
입력
첫 줄에는 파일의 입력 데이터 세트 수를 나타내는 숫자 K ≥ 1이 주어집니다. 이어서 다음과 같은 형식의 K개의 데이터 세트가 이어집니다:
각 데이터 세트의 첫 줄에는 세 개의 정수 ℓ ≤ r ≤ n이 주어지며, n ≤ 200은 시험의 총 문제 수, ℓ은 답이 "예"인 문제의 최소 개수, r은 최대 개수입니다.
이어서 n개의 줄에 각각 해당하는 문제 i에 대한 분수 yi ∈ [0, 1]이 주어집니다.
출력
각 데이터 세트에 대해, 먼저 "Data Set x:"를 한 줄에 출력하십시오(x는 데이터 세트의 번호입니다). 그런 다음, 모든 제약 조건을 만족하면서 맞출 수 있는 최대 문제 수를 소수점 둘째 자리까지 반올림하여 출력하십시오.
hanzch 1년 전
예 또는 아니오
문제
객관식 시험은 채점하기가 쉽기 때문에 일부 교사들 사이에서 매우 인기가 있습니다. 일부 학생들은 이를 좋아하고("답을 전혀 모르더라도 맞출 기회가 있다"), 일부 학생들은 싫어합니다("어딘가에 함정이 있을 것이다"). 객관식 문제의 궁극적인 형태는 참/거짓 문제입니다. 이제 여러분이 참/거짓 시험을 보고 있다고 가정해봅시다. 각 문제에 대해, 두 답안 중 각각이 정답일 확률에 대한 사전 추정치가 있습니다. i번째 문제에 대해, "예"가 정답일 확률이 yi이고, "아니오"가 정답일 확률이 1 - yi입니다. 당연히 yi와 1 - yi 중 더 큰 쪽을 선택해야 합니다(yi = 1/2인 경우 어느 쪽이든 선택할 수 있습니다). 함정이 있다면? 모든 문제에 대해 "예"의 추정치가 "아니오"보다 높다면, 뭔가 이상하다고 의심할 수 있습니다. 대부분의 교사들은 답안지에 명확한 패턴이 있는 것을 좋아하지 않고 답을 섞으려고 합니다. 이 특정 교사가 항상 "예" 답변의 수를 ℓ과 r 사이(포함)로 유지한다고 가정해봅시다(ℓ ≤ r). 그렇다면, 예상되는 총 정답 수를 최대화하기 위해 "예"로 답할 문제를 선택하는 것은 더 이상 쉽지 않습니다. 그러므로 프로그램을 작성하는 것이 좋겠습니다. 구체적으로, 예상되는 정답 수를 최대화하면서 "예" 답변을 최소 ℓ번, 최대 r번 사용하는 모든 문제에 대한 답을 찾고 싶습니다.
입력
첫 줄에는 파일의 입력 데이터 세트 수를 나타내는 숫자 K ≥ 1이 주어집니다. 이어서 다음과 같은 형식의 K개의 데이터 세트가 이어집니다: 각 데이터 세트의 첫 줄에는 세 개의 정수 ℓ ≤ r ≤ n이 주어지며, n ≤ 200은 시험의 총 문제 수, ℓ은 답이 "예"인 문제의 최소 개수, r은 최대 개수입니다. 이어서 n개의 줄에 각각 해당하는 문제 i에 대한 분수 yi ∈ [0, 1]이 주어집니다.
출력
각 데이터 세트에 대해, 먼저 "Data Set x:"를 한 줄에 출력하십시오(x는 데이터 세트의 번호입니다). 그런 다음, 모든 제약 조건을 만족하면서 맞출 수 있는 최대 문제 수를 소수점 둘째 자리까지 반올림하여 출력하십시오.
예제 입력 1
예제 출력 1