Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3843
Unlucky Right Triangle

Time Limit: 5 Seconds      Memory Limit: 65536 KB

William thinks 89 is an unlucky number for him. But he still wants to know more about 89. He knows 89 is the 24th prime number, and also a Fibonacci number after searching on the internet.

Recently, William starts to study some problems about right triangles. He call a right triangle is unlucky if lengths of its both legs are integers and the length of the hypotenuse is a multiple of √89. For example, a right triangle with three edges (5,8,√89) is unlucky, (4,47,5√89), (17,44,5√89), and (10,16,2√89) are also unlucky. He thinks each unlucky triangle has an energy which is defined by its hypotenuse. The energy of an unlucky triangle is its hypotenuse divided by √89. For example, the energy of (5,8,√89) is 1, and the energy of (71,100,13√89) is 13. William is very curious about the average circumference of all the unlucky triangles whose energy is less than or equal to n. The circumference of a triangle is the sum of its three sides. Can you help him? William is expecting a precise answer.

Input

There are multiple cases. Each case is an integer number n in a line. (1≤ n≤ 108, the sum of n in the whole input is less than 2*108)

Output

Each output for one case has 5 lines. Each output should be in the following format:

***************************************************
*          Numerator1             Numerator2    __*
*Integer1------------ + Integer2------------ x V89*
*        Denominator1           Denominator2      *
***************************************************
Each mixed fraction should be irreducible. When numerator is 0, the proper fraction part should be omitted. If Numerator2 is 0 and Integer2 is 1, then "1 x " part should be omitted too. The numerator and the denominator need to be right-aligned. The "---" part should be as same long as the corresponding denominator.

Note the characters other than digits used in the output: '*'(Asterisk, ascii code 42), ' '(Space, ascii code 32), '_'(Underscore, ascii code 95), '-'(Hyphen or minus sign, ascii code 45), 'x'(letter x, ascii code 120), and 'V'(letter V, ascii code 86).

Print a blank line after each case. Please refer to the sample output.

Sample Input

1
8
9
89
99999999

Sample Output

**********
*      __*
*13 + V89*
*        *
**********

***************
*      3    __*
*58 + 4- x V89*
*      5      *
***************

****************
*   4        __*
*63-- + 5 x V89*
*  11          *
****************

********************
*   37     13    __*
*598-- + 48-- x V89*
*   90     18      *
********************

**********************************************
*          93224754            97600661    __*
*620114538--------- + 51235071--------- x V89*
*         106191655           318574965      *
**********************************************

Hint

If n is 108, there are 637149947 kinds of right triangles in different shapes and sizes.

Explanation for n=8, we can find 10 unlucky right triangles whose energy is no more than 8. They are (5,8,√89), (10,16,2√89), (15,24,3√89), (20,32,4√89), (4,47,5√89), (17,44,5√89), (25,40,5√89), (30,48,6√89), (35,56,7√89), and (40,64,8√89). The sum of circumferences is 580+46√89, so the average circumference is (580+46√89)/10.


Author: ZHOU, Yuchen
Source: ZOJ Monthly, January 2015
Submit    Status