크림 통 헹구기

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

요약
물을 부어 섞은 뒤 정해진 양만 남기고 버리는 헹굼을 최대 k번 하면서, 물 Vb 이하를 사용해 남는 위스키의 양을 최소로 줄이는 문제다.
난이도

보통10점 중 7점

유형
수학, 그리디, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

할머니는 크림 통 안에 밀주 위스키를 보관하고 있는데, 곧 엘리엇 네스의 불시 단속이 닥칠 예정입니다. 그가 오기 전에 할머니는 통에서 위스키를 최대한 많이 없애고 싶어 합니다.

통을 뒤집어 내용물을 땅에 쏟을 수 있지만, 표면 장력과 통의 모양 때문에 항상 일정한 부피 VrV_r 만큼의 액체가 통 안쪽에 달라붙어 쏟아지지 않고 남습니다. 더 많은 위스키를 씻어내기 위해 할머니에게는 빗물이 담긴 통이 있으며, 크림 통을 최대 kk 번까지 헹굴 수 있습니다.

처음에 통에는 순수한 위스키가 VwV_w 단위만큼 들어 있습니다. 한 번의 헹굼은 다음과 같이 진행됩니다.

  1. 물 w≥0w \ge 0 단위(전혀 넣지 않을 수도 있음)를 통에 붓습니다. 이때 통 안의 전체 액체는 통의 최대 용량 VcV_c 를 절대 초과할 수 없습니다.
  2. 충분히 섞어 위스키가 액체 전체에 고르게 퍼지도록 합니다.
  3. 통을 뒤집어, 정확히 VrV_r 단위의 액체만 남깁니다. 남는 액체는 붓기 직전과 같은 비율의 위스키와 물의 혼합물입니다.

위스키와 물은 완벽하게 섞이며 부피는 서로 더해집니다. 할머니는 최대 kk 번 헹굴 시간과 빗물 총 VbV_b 단위를 가지고 있습니다. 각 헹굼에 물을 얼마씩 사용할지 정하여, 마지막 헹굼이 끝난 뒤 통에 남는 위스키의 부피를 최소화하려고 합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 다섯 개의 수가 적힌 한 줄입니다.

  • kk — 정수이며 0<k≤1000 < k \le 100, 허용되는 최대 헹굼 횟수입니다.
  • VbV_b — 실수이며 Vb>0V_b > 0, 통에 담긴 사용 가능한 빗물의 부피입니다.
  • VwV_w — 실수이며 Vw>0V_w > 0, 통에 처음 들어 있는 위스키의 부피입니다.
  • VrV_r — 실수이며 Vr>0V_r > 0, 통을 뒤집은 뒤 항상 남는 액체의 부피입니다.
  • VcV_c — 실수이며 Vc>VwV_c > V_w 이고 Vc>VrV_c > V_r, 통의 최대 용량입니다.

마지막 테스트 케이스 다음에는 00 하나만 있는 줄이 오며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다, 최대 kk 번의 헹굼을 최적으로 수행했을 때 통에 남는 위스키 부피의 최솟값을 소수점 아래 정확히 여섯 자리로 반올림하여 한 줄에 출력합니다.

참고

모든 헹굼에 사용한 물의 총량은 VbV_b 를 넘을 수 없고, 통 안의 전체 액체는 어느 순간에도 VcV_c 를 넘을 수 없습니다. 위스키와 물은 완벽하게 섞이며 부피가 그대로 더해진다고 가정합니다. 즉 위스키 xx 단위와 물 yy 단위를 합치면 정확히 x+yx + y 단위의 액체가 됩니다.

예제3

  1. 예제 1

    입력
    2 15.0 25.0 1.0 50.0
    0
    
    예상 출력
    0.062500
    
  2. 예제 2

    입력
    1 10.0 20.0 2.0 50.0
    0
    
    예상 출력
    1.333333
    
  3. 예제 3

    입력
    4 15.0 30.0 1.0 100.0
    0
    
    예상 출력
    0.004630