The Battle for Wesnoth

The Battle for Wesnoth는 엘프, 오크, 언데드, 드워프, 드레이크가 나오는 판타지 턴제 전략 게임이다. 이 문제에 필요한 사실은 두 가지다. 모든 유닛에는 체력이 있고, 전투를 치르면 체력이 줄어든다. 여기서는 가장 단순한 전투, 즉 방어하지 못하는 유닛을 평범하게 공격하는 경우만 다룬다.

공격은 정수 세 개로 정해진다.

• $d$: 공격이 적중했을 때 주는 피해량
• $b$: 공격 횟수
• $p$: 한 번의 공격이 적중할 확률(백분율)

$b$번의 공격은 각각 독립으로 $p/100$의 확률로 적중하고, 적중할 때마다 체력이 $d$만큼 줄어든다. 게임에서 $d$와 $b$는 공격자의 속성이고 $p$는 보통 방어자가 서 있는 지형으로 정해지지만, 이 문제에서는 마법 공격처럼 $p$도 공격자의 속성으로 본다.

$d=6$, $b=2$, $p=60$인 공격을 예로 들면 결과는 세 가지다.

• $16\%$의 확률로 두 번 모두 빗나가 피해를 전혀 주지 못한다.
• $48\%$의 확률로 한 번만 적중해 체력을 $6$만큼 줄인다.
• $36\%$의 확률로 두 번 모두 적중해 체력을 $12$만큼 줄인다.

방어하는 유닛은 체력이 $0$ 이하가 되면 죽는다.

David가 즐기는 확장판에는 엘프 공주라는 특별한 유닛이 있다. 엘프 공주는 $d$와 $b$ 대신 정수 $m$ 하나로 정해지며, 공격할 때 플레이어는 $d \times b \le m$을 만족하는 양의 정수 $d$와 $b$를 마음대로 고를 수 있다.

David는 엘프 공주로 흉측한 해골이나 악취 나는 오크 전사를 자주 처치해야 해서, $d$와 $b$를 어떻게 골라야 적을 죽일 확률이 가장 높은지 알고 싶다. 죽여야 하는 유닛마다 가장 좋은 선택을 구하라.

첫째 줄에 공격자의 정보인 정수 $m$ ($1 \le m \le 10^6$)과 $p$ ($1 \le p \le 99$)가 주어진다. 둘째 줄에 죽여야 하는 유닛의 수 $n$ ($1 \le n \le 10^5$)이 주어진다. 셋째 줄에 정수 $n$개 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^6$)이 주어지며, $h_i$는 죽여야 하는 $i$번째 유닛의 체력이다.

유닛마다 한 줄에 정수 두 개 $d$와 $b$를 출력한다. 그 유닛을 죽일 확률이 가장 높아지는 선택이어야 한다.

최대 확률이 같은 선택이 여럿이면 $d$가 가장 작은 것을 출력하고, 그중에서도 $b$가 가장 작은 것을 출력한다. 어떻게 골라도 죽일 확률이 $0$이어서 유닛을 죽일 수 없다면 1 1을 출력한다.

$m=10$, $p=60$일 때 체력이 $5$인 유닛은 $84\%$, 체력이 $6$인 유닛은 $68.256\%$, 체력이 $7$인 유닛은 $60\%$의 확률로 죽일 수 있다.

계산은 배정밀도 실수로 충분하지만 오버플로와 언더플로를 조심해야 하고, 크기가 크게 차이 나는 수를 더하는 것처럼 위험한 연산은 피해야 한다. $a=0.5$이고 $b=10^{-100}$이면 $a+b$는 $a$와 같은 값으로 계산된다.