//-----------------------------------------------------------------------
//	File:		prob.cpp
//	Description:	Calculate distance between 2 family names
//	Author:		Chau-Wen Tseng (tseng@cs.umd.edu)
//-----------------------------------------------------------------------

#include <stdlib.h>
#include <iostream.h>
#include <assert.h>

// Uncomment the following lines if using APCS classes
// #include "apvector.h"
// #include "apmatrix.h"
// #include "apstack.h"
// #include "apqueue.h"
// #include "apstring.cpp"

#include "apstring.cpp"

//-----------------------------------------------------------------------
//  calcDist() - calculates distance between 2 hobbit names
//-----------------------------------------------------------------------

double calcDist(apstring x, apstring y)
{
	int i, xlen, ylen, mlen, diff;
	double d, weight;
	const int MISMATCH_PENALTY = 50;	// penalty for mismatch
	const int TRUNCATE_PENALTY = 4;		// penalty for missing letter
	const double SCALE_FACTOR = 0.90;	// scaling factor for later positions

	xlen = x.length();
	ylen = y.length();
	mlen = xlen > ylen ? xlen : ylen;

	d = 0.0;
	weight = 1.0;

	for (i = 0; i < mlen; i++) {
		if ((i < xlen) && (i < ylen)) {
			diff = (int) x[i] - (int) y[i];
			if (diff < 0) 
				diff = -diff;
			if (diff > 0)
				diff += MISMATCH_PENALTY;
		}
		else {
			diff = TRUNCATE_PENALTY;
		}
		d += weight * (double) diff;
		weight *= SCALE_FACTOR;
	}
	return d;
}

//-----------------------------------------------------------------------
//  main
//-----------------------------------------------------------------------

int main()
{
	const int MAXLEN = 50;
	apstring names[MAXLEN];
	double dist[MAXLEN][MAXLEN];
	int families;
	int i,j;

	// read in family names, should be in alphabetical order

	cin >> families;
	for (i = 0; i < families; i++) {
		cin >> names[i];

		if ((i > 0) && (names[i] < names[i-1])) {
			cout << "ERROR: name " << names[i] << " not in alphabetical order!" << endl;		;
		}
	}

	// calculate distance for every pair of family names

	for (i = 0; i < families; i++) {
		for (j = i+1; j < families; j++) {
			dist[i][j] = calcDist(names[i], names[j]);
		}
	}

	// output distance between pairs of family names in alphabetical order

	cout.setf(ios::showpoint); // show trailing decimal places

	cout << families << endl;

	for (i = 0; i < families; i++) {
		for (j = i+1; j < families; j++) {
			cout << dist[i][j] << " " << names[i] << " " << names[j] << endl;
		}
	}

	return 0;
}