예상 항공 지연

옛날 뉴욕 주 뉴욕 시에 살던 그레이스라는 여성 사업가가 있었다. 그녀는 일 때문에 아이오와 주 디모인으로 매일 있는 정기 항공편을 자주 이용했다. 그런데 큰 문제가 하나 있었다. 뉴욕에서 디모인으로 가는 항공편은 특히 주말에 결항이 잦기로 악명이 높았다. 날씨, 정비 문제, 그 밖에 예측하기 어려운 요인들이 늘 방해가 되는 듯했다.

그레이스는 지난 경험으로 볼 때, 다가오는 회의의 요일, 제시간에 도착하는 것의 중요도(늦어도 전날까지 출발에 성공하면 제시간에 도착한 것으로 본다), 평일(월요일부터 금요일)과 주말(토요일, 일요일)에 항공편이 무사히 출발할 확률을 입력할 수 있는 앱이 있으면 아주 편하겠다고 생각했다. 그러면 제시간에 디모인에 도착할 수 있다는 확신을 갖고 항공편 출발일을 정하는 데 도움이 된다. 그녀는 프로그래밍과 확률 지식이 다소 부족해서, 이 앱을 만들어 달라고 부탁하고 있다.

예를 들어 회의 날짜가 월요일이라고 하자. 평일 성공 확률 $p_{\mathrm{wday}}=80\%$, 주말 성공 확률 $p_{\mathrm{wend}}=60\%$라고 하자. 제시간 도착의 중요도는 $90\%$ 확신이라고 하자. 그레이스가 일요일에 출발하려 하면 제시간에 도착할 확률은 $60\%$에 불과하다. 그녀가 원하는 $90\%$의 보장에는 한참 못 미친다. 토요일에 출발하면 어떨까? 토요일 항공편이 취소되어도 일요일에 다시 시도할 수 있다.

이 경우 일요일까지 출발에 성공할 확률은 토요일 항공편이 성공할 확률 $60\%$와, 토요일 항공편이 실패할 확률 $40\%$에 일요일 항공편이 성공할 확률 $60\%$를 곱한 값을 더한 $84\%$이다. 그래도 충분하지 않다.

금요일도 선택지에 넣고, 평일 성공 확률 $80\%$를 적용해 일요일까지 출발에 성공할 확률을 계산하면 $0.8 + 0.2 \cdot 0.6 + 0.2 \cdot 0.4 \cdot 0.6 = 96.8\%$가 된다. 그레이스에게는 이 정도면 충분하다.

입력은 한 줄이며, 공백으로 구분된 정수 네 개로 이루어진다. 첫 번째 정수는 회의 요일로, 범위는 $[1,7]$이다. 1은 일요일, 2는 월요일이며, 이후 요일도 같은 순서로 이어진다. 다음 두 정수는 평일과 주말에 항공편이 성공할 확률(백분율) $p_{\mathrm{wday}}$와 $p_{\mathrm{wend}}$이다($0 \leq p_{\mathrm{wday}}, p_{\mathrm{wend}} \leq 100$). 두 값 중 적어도 하나는 0이 아니다. 네 번째 정수는 제시간에 회의에 도착하는 것의 중요도 $p_{\mathrm{imp}}$(백분율)이다($1 \leq p_{\mathrm{imp}} \leq 99$).

$p(i)$는 회의 $i$일 전부터 출발을 시도했을 때 그레이스가 제시간에 회의에 도착할 확률(백분율)이다. 모든 $i \geq 1$에 대해 $\min_{i \geq 1} |p(i) - p_{\mathrm{imp}}| > 10^{-6}$이 보장된다.

Try to leave on DEPDAY, N days before the MEETDAY meeting. 형식으로 출력한다. DEPDAY는 회의 날짜에 가장 가까우면서, 그레이스가 회의에 도착할 확률이 $p_{\mathrm{imp}}$퍼센트 이상이 되도록 하는 출발 요일이다. 요일은 Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday 중 하나로 쓴다. N은 회의 날보다 며칠 전에 출발해야 하는지를 나타낸다. 중요도 조건을 맞추려면 7일보다 더 일찍 출발해야 할 수도 있다. MEETDAY는 회의의 요일이다. N이 1이면 days 대신 day를 출력한다.