🚀 [Duathlon] 문제 😊😊😊😊😊
달리기와 자전거로 총 t 킬로미터를 달리는 철인 2종 경기를 개최한다. 0 ~ (n-1)번까지 모두 n명의 참가자가 등록했으며, 각 참가자의 달리기 속도와 자전거 속도가 주어졌다. 그런데 (n-1)번 참가자가 주최측에 뇌물을 건네며 자신이 승리할 수 있도록 달리기와 자전거 경주의 길이를 조정해달라고 요청했다. 이 참가자가 2등과 가장 큰 차이로 우승하려면 달리기 경주의 길이 r과 자전거 경주의 길이 t-r을 어떻게 정해야 할까요?
🔑 [풀이]
미분 할 수 없는 (이분 탐색을 할 수 없는) 문제를 삼분 검색을 이용하여 해결하였다(물론 책 참고).\
총 주어진 시간을 계산하는 time() 함수를 구현한다. (참가자와, cheater를 다른 컨테이너에 구현하여 time함수 또한 오버로딩을하였다.)
달리기 거리가 주어졌을때 cheater를 제외한 참가자들중 가장 빠른 참가자를 찾고 빠른참가자와 cheater와의 시간차이를 리턴하는 Diff(runDistance) 를 구현한다.
solve() 함수에서 달리기 거리를 삼분 검색을 통해 100번 반복하여 최적값을 찾아낸다. 찾아낸 runDistance를 앞에 사용된 함수와 출력 포맷을 맞추어 출력한다.\
ps. 정답을 찾지 못한다면 c++ 5.3 버전 컴파일러로 제출하여야 해라(runDistance 가 0이거나 100일경우 출력값이 다르다). 결론 -? 외국사이트 못쓰겠다.
⌨️ 입력
각 세트의 첫 번째 줄에는 총 경주 거리(km)인 정수 t가 포함됩니다. 즉, r + k = t입니다. 다음 줄은 경쟁자의 수인 정수 n을 포함합니다. 각 참가자에 대해 해당 참가자의 달리기 및 사이클링 속도를 나타내는 두 개의 실수가 줄을 따릅니다. 입력의 마지막 줄은 주최자에게 뇌물을 준 참가자의 달리기 및 사이클링 속도를 제공한다. (t < 100), (n < 20) 연속된 세트는 빈 줄로 구분되거나 구분되지 않을 수 있습니다.
🖥 출력
각 테스트 케이스에 대해서 레이스를 조작할 수 있는 경우 r 및 k를 소수점 이하 두 자리까지 정확하게 알려주는 메시지와 cheaterc 레이스에서 승리하는 데 걸리는 시간(초)을 출력합니다.
아래 출력 예제에서와 같이 가능하지 않은 경우 ‘The cheater cannot win.’이라고 출력합니다.
🖱 입력 예제
100
3
10.0 40.0
20.0 30.0
15.0 35.0
100
3
10.0 40.0
20.0 30.0
15.0 25.0
💻 출력 예제
The cheater can win by 612 seconds with r = 14.29km and k = 85.71km.
The cheater cannot win.
💎 전체 코드는 다음과 같습니다.
//
// DUATHLON.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/10.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("DUATHLON2.txt");
int track; // 트랙 길이
int n; // 경쟁자 수
// <run time, cycle time> = <달리기 속도, 자전거 속도>
vector<pair<double, double> > people;
pair<double, double> fool;
// 달리기 구간이 run 일때 i 번 선수가 걸리는 시간
double time(int i, double run){
double cycle = track - run;
return (run / people[i].first) + (cycle / people[i].second);
}
// cheater 가 걸리는 시간
double time(double run){
double cycle = track - run;
return (run / fool.first + cycle / fool.second);
}
// 달리기 거리가 주어질 때 가장 빠른 사람과 cheater 의 시간 차이.
double diff(double run){
double others = time(0, run);
double cheater = time(run);
for(int i=1; i<people.size(); i++){
others = min(others, time(i,run));
}
return others - cheater;
}
// 차이나는 최대치 run distance 를 출력.
double solve(){
double lo = 0, hi = track;
for(int it= 0; it<100; it++){
// 삼분 탐색 1/3 지점
double oneThird = (2*lo+hi)/3;
// 2/3 지점
double twoThird = (lo+2*hi)/3;
if(diff(oneThird) > diff(twoThird)){
hi = twoThird;
}
else{
lo = oneThird;
}
}
return (lo+hi)/2;
}
int main(){
while(fin>> track){
fin >> n;
double run, cycle;
for(int i=0; i<n-1; i++){
fin >> run >> cycle;
people.push_back(make_pair(run,cycle));
}
fin >> run >> cycle;
fool = make_pair(run, cycle);
double runDistance = solve();
double cycleDistance = track - runDistance;
double timeDiff = diff(runDistance);
if(timeDiff >= 0.0){
const char *result = "The cheater can win by %.0f seconds with r = %0.2fkm and k = %0.2fkm.\n";
// * 3600 -> 시간을 초로 나타낸다.
printf(result, timeDiff*3600,runDistance, cycleDistance);
//The cheater can win by 612 seconds with r = 14.29km and k = 85.71km.
//The cheater cannot win.
}
else{
cout << "The cheater cannot win." << endl;
}
people.clear();
}
return 0;
}
Comments