아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

피트 스톱 전략

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

요약
랩마다 연료량에 따라 시간과 소모가 달라지고 피트 정지 비용도 주어질 때, 연료가 바닥나지 않으면서 L랩을 완주하는 최소 시간을 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

다른 조건이 모두 같다면 경주용 자동차는 연료를 적게 실을수록 빨라진다. 연료의 무게는 차를 느리게 만들 뿐 아니라 연료 소모도 늘리기 때문이다. 따라서 연료는 적게 싣는 편이 유리하지만, 경주 도중에 연료가 바닥나서는 안 된다.

경주가 시작되기 전에는 원하는 만큼 연료를 실을 수 있으며(이 최초 주유에는 시간이 들지 않는다), 경주 도중에는 피트 스톱에서 연료를 보충할 수 있다. 피트 스톱에 드는 시간은 주유량이 많을수록 늘어난다.

총 LL바퀴를 도는 경주를 생각하자. 어떤 바퀴를 시작할 때 차가 연료 ff리터를 싣고 있다면,

  • 그 바퀴를 도는 데 t+a⋅ft + a \cdot f초가 걸리고,
  • 그 바퀴에서 연료를 c+b⋅fc + b \cdot f리터 소모한다.

여기서 tt는 빈 탱크에서의 한 바퀴 시간, aa는 실은 연료 1리터당 늘어나는 바퀴 시간, cc는 빈 탱크에서 한 바퀴당 연료 소모량, bb는 실은 연료 1리터당 늘어나는 소모량이다(단 b<1b < 1).

피트 스톱은 바퀴와 바퀴 사이에서만 할 수 있다. 피트 스톱에서 연료 xx리터를 주유하면 p+q⋅xp + q \cdot x초가 걸리며, 여기서 pp는 피트 스톱의 고정 소요 시간, qq는 주유 1리터당 추가로 드는 시간이다. 경주 전에 싣는 연료에는 시간이 들지 않는다.

총 경주 시간은 모든 바퀴 시간과 모든 피트 스톱 시간의 합이다. 연료가 바닥나지 않으면서 LL바퀴를 모두 도는, 최소 총 경주 시간을 구하여라.

입력

입력은 여러 줄로 이루어지며, 각 줄은 자동차 한 대를 나타내고 서로 독립적으로 처리한다. 입력의 끝까지 각 줄을 읽는다.

각 줄에는 공백 하나로 구분된 일곱 개의 수가 주어진다.

  • LL — 경주의 바퀴 수 (정수, L≤100L \le 100)
  • tt — 빈 탱크일 때 한 바퀴에 걸리는 시간(초) (실수)
  • aa — 바퀴 시작 시 실은 연료 1리터당 늘어나는 바퀴 시간(초) (실수)
  • cc — 빈 탱크일 때 한 바퀴당 연료 소모량(리터) (실수)
  • bb — 바퀴 시작 시 실은 연료 1리터당 늘어나는 연료 소모량 (실수, 11보다 엄격히 작음)
  • pp — 연료를 넣지 않는 피트 스톱에 걸리는 시간(초) (실수)
  • qq — 주유 1리터당 추가로 드는 피트 스톱 시간(초) (실수)

출력

각 자동차(각 입력 줄)마다, 가능한 최소 총 경주 시간을 소수점 아래 셋째 자리까지 반올림하여 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3 100 0 10 0 20 0
    3 100 0 10 .1 20 0
    3 100 2 10 0 20 1
    3 100 4 10 0 20 1
    3 100 2 10 .1 20 1
    
    예상 출력
    300.000
    300.000
    410.000
    480.000
    422.469