시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 35 | 24 | 20 | 68.966% |
경근이는 요즘 여러 능력을 가지고 몬스터들과 싸우는 웹게임을 열심히 하고 있다. 경근이는 지금 N개의 공격 능력을 가지고 있다. 경근이는 능력들을 편하게 관리하고자 각 능력에 1 이상 N 이하의 자연수 번호를 붙였다.
i번 능력에는 그 능력이 발동될 확률 pi와 상대에게 입히는 피해량 di가 책정되어 있다. 따라서 경근이가 i번 능력에 발동 명령을 내리면, pi의 확률로 능력이 발동되어 상대에게 di만큼의 피해를 입히고, (1 - pi)의 확률로 능력이 발동되지 않아 아무 일도 일어나지 않는다.
열심히 게임을 한 결과, 경근이는 드디어 게임 내에서 모든 능력을 자유롭게 장착하고 해제할 수 있게 되었다! 이제 경근이는 상대가 입을 피해량의 기댓값이 최대가 되도록 하기 위해 어떤 능력들을 장착해야 할지를 알고 싶다. 경근이가 어떤 능력(들)을 장착한 채로 상대방을 공격할 기회를 얻었다면, 아래 과정이 일어난다:
현재 경근이가 가지고 있는 N개의 능력이 발동될 확률과 상대에게 입히는 피해량이 주어질 때, 한 번의 공격 기회에서 피해량의 기댓값이 최대가 되도록 하기 위해 장착해야 할 능력의 집합을 구하는 프로그램을 작성하라.
첫 번째 줄에 자연수 N (1 ≤ N ≤ 20)이 주어진다. 다음 N개의 줄에는 능력들의 정보가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄에는 i번 능력이 발동될 확률과 상대에게 입히는 피해량을 의미하는 두 정수 pi, di (1 ≤ pi , di ≤ 100)이 공백을 사이로 두고 주어진다. 이는 i번 능력은 pi% ( = pi / 100)의 확률로 발동하는 능력이며 상대에게 di만큼의 피해를 입힌다는 의미이다.
가지고 있는 능력들을 적절히 장착하여 얻을 수 있는 피해량의 기댓값의 최댓값을 출력한다. 정답과의 절대/상대 오차가 10-8 이하이면 올바른 답안으로 처리된다.
2 100 1 10 20
2.000000000000
3 12 10 11 11 10 12
3.227420000000
첫 번째 예제의 경우 1번 능력은 100% 발동하지만 피해량이 너무 낮아 이를 사용하지 않고 2번 능력만 사용하는 것이 피해량의 기댓값이 더 높다.
Contest > kriiicon > 제3회 kriiicon ㅊ번