아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

카지노

시간 제한2초메모리 제한256 MB

요약
승률이 p퍼센트인 게임에서 m달러로 시작해 n달러에 도달할 확률이 가장 높아지도록 매 회차 베팅액을 정합니다.
난이도

어려움10점 중 9점

유형
확률, 동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

타로는 nn달러의 빚을 지고 있다. 빚을 갚으려고 카지노에 간 타로는 한 판마다 걸 금액을 정한다. 거는 금액은 11달러 이상의 정수이고, 그 시점에 가진 돈을 넘을 수 없다. 한 판에서 이길 확률은 pp퍼센트이며, 이기면 건 금액과 같은 액수를 더 받아 가진 돈이 건 금액만큼 늘어난다. 지면 건 금액을 잃는다.

타로는 지금 mm달러를 가지고 있고, 판을 원하는 만큼 반복할 수 있다. 가진 돈이 nn달러 이상이 되면 빚을 모두 갚는다.

빚을 모두 갚을 확률의 최댓값을 구하고, 최적인 첫 베팅 금액을 모두 구하라. 어떤 금액을 첫 판에 걸고 그다음부터 최선으로 진행했을 때 이 최댓값을 그대로 달성할 수 있으면, 그 금액은 최적인 첫 베팅이다.

입력

첫째 줄에 정수 pp, mm, nn이 공백 하나로 구분되어 주어진다. (0≤p≤1000 \le p \le 100, 0<m<n≤1090 < m < n \le 10^9)

출력

세 줄을 출력한다.

첫째 줄에는 빚을 모두 갚을 확률의 최댓값을 소수점 아래 여섯째 자리까지 반올림해 출력한다.

둘째 줄에는 최적인 첫 베팅의 개수를 출력한다.

셋째 줄에는 그 개수가 200200 이하이면 최적인 첫 베팅을 모두 오름차순으로 공백 하나씩 두고 출력한다. 개수가 200200보다 크면 가장 작은 100100개와 가장 큰 100100개를 오름차순으로 공백 하나씩 두고 출력한다.

예제2

  1. 예제 1

    입력
    60 2 3
    
    예상 출력
    0.789474
    1
    1
    
  2. 예제 2

    입력
    25 3 8
    
    예상 출력
    0.109375
    2
    1 3