정사각형 복권

시간 제한1초메모리 제한128 MB

요약
N x N 격자에 1부터 N^2까지를 배열한 모든 순열에 대해, 정사각형의 네 꼭짓점을 이루는 네 수가 뽑힐 때 당첨 티켓 수의 기댓값을 구하고 상금을 나눈다.
난이도

어려움10점 중 8점

유형
조합론, 수학, 기하, 확률
정답자
아직 제출이 없습니다

문제

작은탑 공화국은 올림픽 주경기장 건설 자금을 모으기 위해 매주 열리는 새 복권을 시작한다.

복권은 매주 정사각형 카드 형태로 판매된다. 복권 한 장은 N×NN \times N 격자이며, 각 칸에는 11부터 N2N^2까지의 정수가 임의의 순서로 정확히 한 번씩 적혀 있다(그림 1 참고). 서로 같은 복권은 존재하지 않고 시민들이 가능한 모든 배열을 사기 때문에, 매주 서로 다른 (N2)!(N^2)! 종류의 복권이 각각 한 장씩 모두 판매되며, 한 장의 가격은 T$1.00(작은탑의 화폐 단위인 토레알 1)이다.

그림 1: N=3N = 3일 때의 복권 예시.

당첨자를 뽑기 위해 11부터 N2N^2 사이의 서로 다른 네 수를 무작위로 고른다. 어떤 복권에서 이 네 수가 적힌 칸들이 정사각형의 네 꼭짓점을 이루면 그 복권이 당첨된다(정사각형은 축에 평행할 수도, 기울어져 있을 수도 있다). 예를 들어 그림 1의 복권은 (6,3,2,9)(6, 3, 2, 9), (1,4,2,5)(1, 4, 2, 5), (7,8,9,6)(7, 8, 9, 6)을 고르면 당첨이지만, (1,7,2,9)(1, 7, 2, 9)를 고르면 당첨이 아니다. 당첨 복권이 여러 장이면 그 주의 상금을 똑같이 나눠 갖는다.

NN과, 전체 판매 금액 중 상금으로 지급할 비율 PP(퍼센트)가 주어질 때, 당첨 복권 한 장에 지급되는 상금을 구하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 NN과 PP가 적힌 한 줄이며, 각각 복권의 행(그리고 열)의 수와, 걷힌 금액 중 상금으로 지급하는 비율(퍼센트)을 나타낸다(2≤N≤1002 \le N \le 100, 0≤P≤1000 \le P \le 100). 입력의 끝은 N=P=0N = P = 0인 줄로 표시되며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 당첨 복권 한 장에 지급되는 상금을 한 줄에 출력한다. 값은 소수점 아래 정확히 두 자리로, 마지막 자리를 반올림하여 출력한다. 반올림 방향에 따라 결과가 달라지는 경계값은 입력에 포함되지 않는다.

예제2

  1. 예제 1

    입력
    2 100
    2 80
    3 50
    0 0
    
    예상 출력
    1.00
    0.80
    10.50
    
  2. 예제 2

    입력
    4 100
    4 50
    5 100
    10 100
    0 0
    
    예상 출력
    91.00
    45.50
    253.00
    4753.00