Square Lottery

Time limit1sMemory limit128 MB

Summary
Count, over all permutations of 1 to N^2 on an N by N grid, the expected number of winning tickets for a random set of four corners forming a square, then divide the prize pool.
Level

Hard8 of 10

Topics
Combinatorics, Math, Geometry, Probability
Solved
No attempts yet

Problem

The Republic of Little Tower is launching a new weekly lottery to raise money for its Olympic stadium.

Each week, tickets are sold as square cards. A single ticket is an N×NN \times N grid whose cells contain every integer from 11 to N2N^2 exactly once, placed in some order (see Figure 1). No two tickets are identical, and because the citizens buy every possible arrangement, all (N2)!(N^2)! distinct tickets are sold each week, one copy of each, at a price of T$1.00 (one Torreal, Little Tower's monetary unit).

Fig. 1: A sample lottery ticket, for N=3N = 3.

To draw the winners, four distinct numbers between 11 and N2N^2 are picked at random. A ticket wins if, on that ticket, the four picked numbers lie in cells that form the four corners of a square (squares may be axis-aligned or tilted). For example, the ticket in Figure 1 wins for the picks (6,3,2,9)(6, 3, 2, 9), (1,4,2,5)(1, 4, 2, 5), or (7,8,9,6)(7, 8, 9, 6), but not for (1,7,2,9)(1, 7, 2, 9). When several tickets win, they share that week's prize pool equally.

Given NN and a percentage PP of the total ticket revenue that the government pays out as prizes, determine the prize paid to each winning ticket.

Input

The input contains several test cases. Each test case is a line with two integers NN and PP: the number of rows (and columns) of a ticket, and the percentage of the collected money paid out as prizes (2≤N≤1002 \le N \le 100, 0≤P≤1000 \le P \le 100). The input ends with a line containing N=P=0N = P = 0, which must not be processed.

Output

For each test case, print one line with the prize paid to each winning ticket. Print the value with exactly two decimal places, rounding the last digit. No test case lies on a rounding boundary where the choice of rounding would matter.

Examples2

  1. Example 1

    Input
    2 100
    2 80
    3 50
    0 0
    
    Expected output
    1.00
    0.80
    10.50
    
  2. Example 2

    Input
    4 100
    4 50
    5 100
    10 100
    0 0
    
    Expected output
    91.00
    45.50
    253.00
    4753.00