더블릿은 이번에 횡성에서 개최되는 세계최대 자동차 경주대회에 참가 신청을하였다. 더블릿이 소유하고 있는 레이싱카는 현재 무게가 M(1 <= M <= 1,000)이고, 힘이F(1 <= F <= 1,000,000)이다. 더블릿은 이번 대회에 대한 기대가 남달라 지금 가지고 레이싱카를 튜닝하고자 서울에 있는 레이싱카 튜닝전문 매장을 찾아 갔다. 튜닝 매장에는 N (1 <= N <= 20)개의 튜닝 부품을 판매하며, 각각의 부품은 1개의 재고만 있어 동일 부품을 여러개 구입할 수는 없다.
i번째부품 P_i를 레이싱카에 추가하면 힘F_i(1 <= F_i <= 1,000,000)를 증가시킬수 있으나 부품의무게 M_i(1 <= M_i <= 1,000)또한 추가 되게 된다.
레이싱카의 생명은 가속도(Acceleration)이다. 더블릿은 이번대회 우수한 성적을 위해 레이싱카의 가속도를 최대화 하기위해 튜닝 매장에 있는 부품중 어느것을 구입하여 장착하여야 하는지 여러분에게 도움을 요청하였다.
여러분은 더블릿의 레이싱카의 가속도를 최대화 시킬 수 있는 추가부품리스트를 작성하는 프로그램을 만들어 주어야 한다.
물론 공부잘하는 여러분이 이미 알고있겠지만, 뉴톤의제2법칙 F=MA를 따르면 힘이 일정할 경우 무게와 가속도는 반비례가 된다. 따라서 부품을 추가하면 힘과 무게가 동시에 증가하기 때문제 고려하여 선택하여야 한다.
초기 힘F=1500, 무게 M=100이고 4가지 종류의 부품이 추가가능한 아래 경우를 살펴보자.
| I | F_i | M_i |
|---|---|---|
| 1 | 250 | 25 |
| 2 | 150 | 9 |
| 3 | 120 | 5 |
| 4 | 200 | 8 |
2번 부품만 추가할 경우 가속도는 (1500+150)/(100+9) = 1650/109 = 15.13761. 가 된다.
아래 표에서 가능한 모든경우의 가속도를 살펴볼 수 있다.(1=포함, 0=제외):
Parts Aggregate Aggregate 1234 F M F/M 0000 1500 100 15.0000 0001 1700 108 15.7407 0010 1620 105 15.4286 0011 1820 113 16.1062 0100 1650 109 15.1376 0101 1850 117 15.8120 0110 1770 114 15.5263 0111 1970 122 16.1475 <-- highest F/M 1000 1750 125 14.0000 1001 1950 133 14.6617 1010 1870 130 14.3846 1011 2070 138 15.0000 1100 1900 134 14.1791 1101 2100 142 14.7887 1110 2020 139 14.5324 1111 2220 147 15.1020위 표로부터 최적의 부품리스트는 2,3,4번 임을 확인할 수 있다.
입력 1500 100 4 250 25 150 9 120 5 200 8 출력 2 3 4
출처:usaco 2010 March blonze 번역:sunghyen