471. Funny Game
Time limit per test: 0.25
Memory limit: 262144
Goryinyich and vot decided to play the following funny game.
Initially some natural number is written on the board. Players move in turns, Goryinyich starts the game. In each turn, player wipes the board out and writes new number equal to the difference between erased number and number chosen by the player. Player may choose any number between one and sum of squares of digits of number that is written on the board. If minimal number is written on the board, the player who got the number in his turn is considered to win. Minimal number is the smallest possible number with a given length and given sum of squares of its digits.
Consider the example. Suppose that number 20 is written on the board. Goryinyich may subtract any number from 1 to 22
=4 from it. Any of these possibilities makes the number minimal in the abovementioned sense, so Goryinyich wins the game. But after the game was proposed by Goryinyich, vot claimed that Goryinyich went crazy, oversolved problems from Ural championships and vot will never play a game with such cumbersome and tedious rules. Instead, he proposed another game which, in his opinion, is much simpler and more cheerful.
Goryinyich and vot agree on some natural number N
. Then vot writes some integer number a
from 1 to N
on a piece of paper and Goryinyich, unaware of the number written by vot, writes number b
(also from 1 to N
). If |a-b
|=1, then vot pays 1 dollar to Goryinyich, otherwise Goryinyich pays the same to vot.
Your task is to find expected gain of Goryinyich. Of course, you should realize that the players are not stupid (actually, they even also participate in computer programming contests from time to time), so everybody will do his best to maximize expected gain from the game.
Input file contains up to 10 lines, each containing number N
from the problem statement (1 ≤ N
For every N
in the input file write to the output file on a separate line the required number as an irreducible fraction. Minus sign, if necessary, should be in the numerator. Follow the format shown in the example below.
Case #1: -1/1
Case #2: 0/1