ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Cellular Characters

Time limit: 1.0 second
Memory limit: 64 MB
A famous gangster Vito Maretti has got a present from the sheriff — the latest model of a cellular phone Gnusmas. This telephone has a lot of cool functions. Most of them are useless for the ordinary gangster, but there are several useful features. One of them is an opportunity to insert additional characters into SMS.
The feature works in the following way. If Vito wants to insert a character that is absent at the keyboard, he has to push the "*" key first. Then N additional characters appear. They are arranged in the form of a table with M columns. All rows of this table, except the last one, contain exactly M characters, the last row may contain from 1 to M characters. Initially the cursor is at the upper left character.
[.] , ! ? _
+ - " = *
( ) /    
Here N = 13, M = 5. The cursor is denoted by the square brackets.
One can move the cursor left, right, up and down respectively with the keys LEFT, RIGHT, UP, DOWN. Also the LEFT key moves the cursor from the first character in a row to the last character in the previous one and the RIGHT key – from the last character in a row to the first character in the next one. If the cursor is in the first character of the first row then the LEFT key moves it to the last character of the last row. Respectively, if the cursor is in the last character of the last row then the RIGHT key moves it to the first character of the first row. Thus one can choose any character by pushing the arrow keys just several times.
In the given above example one can reach the cells ",", "+", "/" from the cell "."and the cells "=", "_", "(" from the cell "*", pushing an arrow key only once.
Even a gangster understands that the first location of the cursor is not optimal: the average number of the keys pushes needed to choose a character is not minimal. Vito has been exasperated by that fact. If he wants to send an SMS to the sheriff he has to push the keys some extra times. But Vito realized that he has a perfect way to solve this problem: he blackmailed you to make you reprogram his cellular phone.


The numbers N and M (1 ≤ N ≤ 256; 1 ≤ M ≤ min(N, 20)).


In the first line "Mean = X", where X is the average number of the keys pushes assuming that initially cursor is positioned at the best possible initially position. Number X should be printed with a precision of two digits after the decimal point. Then print N integers, M of them in each line – the minimal number of the keys pushes that is necessary to choose each character with the found best initial position of the cursor. If the are several cases with the least average value output any of them.


5 3
Mean = 1.00
1 0 1
2 1
Problem Author: Vladimir Yakovlev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)
To submit the solution for this problem go to the Problem set: 1400. Cellular Characters