화학 실험

시간 제한2초메모리 제한128 MB

요약
농도와 양이 주어진 여러 병에서 원하는 만큼씩 덜어내어 정확히 목표 농도의 용액을 최대 몇 리터까지 만들 수 있는지 구하는 문제입니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 수학
정답자
아직 제출이 없습니다

문제

화학에서 말하는 용액은 컴퓨터 프로그래밍에서 말하는 솔루션과는 다른 뜻이다.

어떤 물질 x리터를 물 (100 - x)리터에 섞으면 그 물질의 농도가 x%인 용액 100리터를 얻는다.

다솜이는 같은 물질이 녹아 있는 용액을 담은 병 N개를 가지고 있다. 각 병에는 현재 들어 있는 용액의 양과 농도가 적힌 이름표가 붙어 있다.

다솜이는 이 병들에서 원하는 만큼의 용액을 골라 한 병에 모아 농도가 정확히 M%인 용액을 만들려고 한다. 병 하나를 전부 사용하지 않아도 되며, 필요한 만큼만 덜어 섞을 수 있다.

만들 수 있는 M% 용액의 최대 양을 리터 단위로 구하시오.

입력

첫째 줄에 병의 개수 N과 만들고자 하는 농도 M이 주어진다.

N은 50 이하의 자연수이고, M은 100 이하의 음이 아닌 정수이다.

둘째 줄부터 N개의 줄에 각 병의 정보가 하나씩 주어진다. 각 줄에는 이름표에 적힌 농도와 그 병에 들어 있는 용액의 양이 공백으로 구분되어 주어진다. 농도는 100 이하의 음이 아닌 정수이고, 용액의 양은 1000 이하의 자연수이다.

출력

첫째 줄에 만들 수 있는 M% 용액의 최대 양을 리터 단위로 출력한다.

절대 오차 또는 상대 오차가 10^-2 이하이면 정답으로 인정된다.

힌트

목표 농도보다 낮은 용액은 물이 많은 쪽으로, 목표 농도보다 높은 용액은 물질이 많은 쪽으로 기여한다. 두 쪽의 부족분과 초과분이 같아지도록 섞어야 목표 농도를 만들 수 있다.

예제5

  1. 예제 1

    입력
    2 50
0 20
100 30
    예상 출력
    40.00

  2. 예제 2

    입력
    2 60
0 20
100 30
    예상 출력
    50.0

  3. 예제 3

    입력
    3 50
90 10
70 10
80 10
    예상 출력
    0.0

  4. 예제 4

    입력
    3 57
30 40
80 10
60 15
    예상 출력
    35.18518518518519

  5. 예제 5

    입력
    3 50
50 395
50 971
50 964
    예상 출력
    2330.0