meditationatae

Just another WordPress.com site

Unit distance graph searcher for 14 vertices in C

I wrote a modified searcher for 14-vertex, non 3-colorable, unit distance graphs, embeddable in the plane R^2 with edges of length 1 between vertices, at least numerically.

The searcher has a randomozing seed constant for the PRNG (pseudo-random number generator): it is the unisgned long long constant:

14502779422240352273ULL

present in the array initiaizer code:

for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]&14502779422240352273ULL;

// seed above = 14502779422240352273ULL
}

Any value from 0 to 2^64 – 1 will work, if as with my system a 64-bit compilation is done by default. For 32-bits by default, something must be told to the compiler, or maybe the source code modified.

The stages of the search will probably be described in another post.

So far, the new searcher has found some (probable) 14-vertex UDGs, with at least 25 edges, and which are not 3-colorable:

 

$ cat udgraph14_solver019a.txt | grep count_4_colorings | sort
count_4_colorings = 2143 num_4_colorings_mod_24 = 0
count_4_colorings = 2496 num_4_colorings_mod_24 = 0
count_4_colorings = 3130 num_4_colorings_mod_24 = 0
count_4_colorings = 3644 num_4_colorings_mod_24 = 0
count_4_colorings = 3908 num_4_colorings_mod_24 = 0
count_4_colorings = 4419 num_4_colorings_mod_24 = 0
count_4_colorings = 4446 num_4_colorings_mod_24 = 0
count_4_colorings = 896 num_4_colorings_mod_24 = 0

The smallest number of four-colorings found for one of these is 896 (where colour permutations count as the same 4-colouring). This compares to 811 (a prime) distinct 4-colourings in the 24-hour run of the searcher with another seed value.

[david@localhost golomb19]$ cat udgraph14_solver019a.c

(C cource code follows).
#include <stdio.h>
#include <math.h>
#define NUMSTEPS 2500
#define MAXDIFFAT100 ((long double) 18)/((long double) 1)
#define MAXDIFFAT50 ((long double) 18)/((long double) 1)
#define MAXDIFFAT25 ((long double) 40)/((long double) 1)
#define MAXDIFFAT1 ((long double) 40)/((long double) 1)
#define MAXDIFFAT200 ((long double) 96)/((long double) 10)
#define MAXDIFFAT400 ((long double) 67)/((long double) 1000)
#define MAXDIFFAT800 ((long double) 79)/((long double) 100000000)
#define MAXDIFFAT1200 ((long double) 84)/((long double)1000000000000)
#define VERBOSE
#define VERTEX 14

/**********************************************
rec_diff1 = 28.852841 40.0
rec_diff25 = 39.668785 40.0
rec_diff50 = 17.967935 18.0
rec_diff100 = 17.856958 18.0
rec_diff200 = 9.573263 9.6
rec_diff400 = 0.066982 6.7e-2
rec_diff800 = 0.0000007832212564 7.9e-7
rec_diff1200 = 0.0000000000839841 8.4e-11
************************************************/

static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )
/********************* README SECTION *********************

10-point non-singular solutions to the unit
graph problem are found numerically at a rate of
57.9 solutions per second on a dual core Athlon
5000+ processor.

The solutions are expected to be isometric as a
10-point metric space to the soltion depicted in
the graph in my blog post :

Sketch of 10-vertex unit distance graph, 2013
at URL =

meditationatae.wordpress.com/2017/02/06/sketch-of-10-vertex-unit-distance-graph-2013
The sci dot math posts:

mathforum.org/kb/message.jspa?messageID=10081388

and earlier:

mathforum.org/kb/message.jspa?messageID=10074716

This solver for a particular graph has been optimized
to run in as little time as possible for the given graph,
decribed by the 10×10 adjacency matrix.

To compile, I type:

$ gcc -lm -O3 -o udgraph_solver201a.out udgraph_solver201a.c

at the shell command line in Linux.

The executable is then udgraph_solver201a.out .
In C pre-processor terms, if VERBOSE is defined by
a pre-processor directive,
Number-Sign define VERBOSE
say on line 7 above after the other
Number-sign defines,
then the solution count and the 10×10 matrix of vertex to vertex
distances for a solution will be printed.

As above VERBOSE is not defined, the program will run with
minimal output until it finishes after about 9 minutes
with my system.

This README is based on file
Slash home slash david slash graphs slash golomb6
slash udgraph_solver201a dot c,

will serve to write the local file:

Slash home slash david slash graphs slash golomb6
slash udgraph_solver301a dot c ,

and will go by the Moniker or alias
“unit distance graph solver draft 101”

a hexadecimal dump will be posted to my blog

meditationatae.wordpress.com
David Bernier

********************* README END *************************/

int main(void)
{
unsigned long long i,cng=123456789987654321LL, xs=362436069362436069LL;
unsigned long long randx;
unsigned long long mask = 2147483647LL;
int B;
int j;
int k;
int quit;
int is_singular;
int graph_found;
int total_edges;
int degree_test_passed;
int l, m;
int n, p;
int has_k4;
int is_3colorable;
int count;
int total_finds;
int probable_unit_lengths;
int solution_found;
int coloring_found;
char alphabet[VERTEX];
unsigned long long maxi_ull;
long double xcoord[VERTEX];
long double diff;
long double diff25;
long double diff50;
long double diff100;
long double diff200;
long double diff400;
long double diff800;
long double diff1200;
long double diff1;
long double rec_diff25;
long double rec_diff50;
long double rec_diff100;
long double rec_diff200;
long double rec_diff400;
long double rec_diff800;
long double rec_diff1200;
long double rec_diff1;
int ru1;
int ru2;
long double epsilon;
int co1;
int co2;
int colors[VERTEX];
int num_4_colorings;
int num_4_colorings_mod_24;
int count_4_colorings;
int n_colors;
int degrees[VERTEX];
int v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13;
int has_failed;
int numedges;
long double diff_record;
long double maxdiffat400;
long double one;
long double ycoord[VERTEX];
long double forces[VERTEX][2];
long double C;
long double vector[2];
long double xgood[VERTEX];
long double ygood[VERTEX];
int four_colouring_failed;
int has_converged_flag;
int has_converged_step;
int max_has_converged_step;
long double scaling;
long double dmatrix[VERTEX][VERTEX];
int adjmat[VERTEX][VERTEX];
int post_adjmat[VERTEX][VERTEX];
/************************************************************************

udgraph_solver3401a.c : user 22m50.198s w/
MAXDIFFAT100 ((long double) 38)/((long double) 1)

newtestz746a.out 345 : 8m 34.631s for 30k solns. , using -O3
newtestz745a.out 340 : 8m 35s for 30000 solutions, with -O3
newtestz585a.c: 8m 51s for 30000 solutions, using -O3 optimization
newtest83a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest81a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest73a.c: 8m 49s for 30000 solutions, using -O3 optimization option
newtest66a.c: 10m 25s for 30000 solutions, using -O3 optimization option
newtest65a.c: 11m 30s for 30000 solutions
newtest64a.c: 11m 30s for 30000 solutions
newtest63a.c: 11m 33s for 30000 solutions
newtest62a.c: 11m 33s for 30000 solutions
newtest61a.c: 3m 51s for 10000 solutions
newtest57a.c: 6m 27s for 10000 solutions
newtest56a.c: 6m 37s for 10000 solutions
newtest55a.c: 6m 43s for 10000 solutions
newtest54a.c: 6m 48s for 10000 solutions
newtest53a.c: 6m 46s for 10000 solutions
newtest48a.c: 62 seconds for 1600 solutions
newtest47a.c: 14 seconds for 400 solutions
newtest46a.c: 66 seconds for 400 solutions
newtest39a.c: 67 seconds for 400 solutions
newtest37a.c: 70 seconds for 400 solutions
newtest35a.c: 79 seconds for 400 solutions
newtest34a.c: 72 seconds for 400 solutions
newtest33a.c: 91 seconds for 400 solutions
newtest30a.c: 16 seconds for 100 solutions
newtest29a.c: 18 seconds for 100 solutions
newtest28a.c: 25 seconds for 100 solutions
newtest27a.c: 50 seconds for 100 solutions
newtest26a.c: 99 seconds for 100 solutions
newtest25a.c: 3000 solutions per hour
for 100 solutions, 2 minutes …
808 solutions per minute for 4-point diamond shape.
gtest230a.c :
2600 solutions per minute for 7-point 4-colour
graph
gtest980a.c :
98000 solutions per minute for 7-point 4-colour
graph, Mosers’ spindle.
en.wikipedia.org slash wiki slash Moser_spindle
*************************************************/
B = 340;
total_edges = 25 ;

total_finds = 0;

maxi_ull = ((unsigned long long)6700417)*((unsigned long
long)2753074036095);
scaling = ((long double) 37)/((long double) 10);
one = (long double) 1;
diff_record = ((long double) 4100)/((long double) 100);

diff_record = MAXDIFFAT1;
maxdiffat400 = ((long double)1)/((long double)100000);
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;

epsilon = ((long double)1)/((long double)10000000);

rec_diff25 = (long double) 0;
rec_diff50 = (long double) 0;
rec_diff100 = (long double) 0;
rec_diff1 = (long double) 0;
rec_diff200 = (long double) 0;
rec_diff400 = (long double) 0;
rec_diff800 = (long double) 0;
rec_diff1200 = (long double) 0;
alphabet[0] = ‘A’;
alphabet[1] = ‘B’;
alphabet[2] = ‘C’;
alphabet[3] = ‘D’;
alphabet[4] = ‘E’;
alphabet[5] = ‘F’;
alphabet[6] = ‘G’;
alphabet[7] = ‘H’;
alphabet[8] = ‘I’;
alphabet[9] = ‘J’;
alphabet[10] = ‘K’;
alphabet[11] = ‘L’;
alphabet[12] = ‘M’;
alphabet[13] = ‘N’;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]&14502779422240352273ULL;
}

for(l=0; l< VERTEX ; l++)
{
dmatrix[l][l] = (long double) 0;
}

while( total_finds < 5000000000 )
{

graph_found = 0;

while( graph_found == 0)
{

numedges = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
adjmat[l][m] = 0;
}
}

while(numedges < total_edges )
{
ru1 = (int) (KISS&mask);
co1 = ru1/153391690;
ru2 = (int) (KISS&mask);
co2 = ru2/153391690;
if( (co1 != co2) && (adjmat[co1][co2] == 0) )
{
adjmat[co1][co2] = 1;
adjmat[co2][co1] = 1;
numedges++;
}
}

/*** compute degrees[] ***/
/*** each 3 or more ***/

degree_test_passed = 1;

for(l=0; l< VERTEX ; l++)
{
degrees[l] = 0;

for(m=0; m < VERTEX; m++)
{
degrees[l] = degrees[l] + adjmat[l][m];
}

if( degrees[l] < 3 )
{
degree_test_passed = 0;
break;
}
}

if(degree_test_passed == 1)
{
graph_found = 1;
}

}
count = 0;
max_has_converged_step = 0;
while( count < 20 )
{
solution_found = 0;

while( 0 == solution_found )
{
for( j=0; j< VERTEX ; j++)
{
randx = KISS;
xcoord[j] = ((long double) randx)/((long double) maxi_ull);
xcoord[j] = scaling*xcoord[j];
randx = KISS;
ycoord[j] = ((long double) randx)/((long double) maxi_ull);
ycoord[j] = scaling*ycoord[j];
}
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xcoord[l]-xcoord[m])*(xcoord[l]-xcoord[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ycoord[l]-ycoord[m])*(ycoord[l]-ycoord[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1 = diff;

if(diff < diff_record)
{
solution_found = 1;

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xcoord[j];
ygood[j] = ycoord[j];
}
}
}

/*****************************************************************

have solution …

*****************************************************************/
has_converged_flag = 0;
quit = 0;
count = count + 1;
/*************** BEGIN ITERATIONS TO CONVERGE **************/
for( k = 0; k < NUMSTEPS ; k++)
{
if( quit == 1)
{
break;
}

if( (k+1) < 100)
{
C = ((long double) 345)/((long double) 1000);
}
else
{
C = ((long double) B )/((long double) 1000);
}

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xgood[l]-xgood[m])*(xgood[l]-xgood[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ygood[l]-ygood[m])*(ygood[l]-ygood[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
if( (k+1) == 25 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff25 = diff;

if( diff > MAXDIFFAT25 )
{
quit = 1;
}
}
if( (k+1) == 50 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff50 = diff;

if( diff > MAXDIFFAT50 )
{
quit = 1;
}
}
if( (k+1) == 100 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff100 = diff;

if( diff > MAXDIFFAT100 )
{
quit = 1;
}
}

if( (k+1) == 200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff200 = diff;

if( diff > MAXDIFFAT200 )
{
quit = 1;
}
}
if( (k+1) == 400 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff400 = diff;

if( diff > MAXDIFFAT400 )
{
quit = 1;
}
}
if( (k+1) == 800 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff800 = diff;

if( diff > MAXDIFFAT800 )
{
quit = 1;
}

}
if( (k+1) == 1200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1200 = diff;

if( diff > MAXDIFFAT1200 )
{
quit = 1;
}

}
diff = (long double) 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

if( (diff < maxdiffat400) && (has_converged_flag == 0) )
{
has_converged_flag = 1;
has_converged_step = k+1;

if( has_converged_step > max_has_converged_step )
{
max_has_converged_step = has_converged_step;
}

quit = 1;

/***********************

int is_singular;

**********************/
is_singular = 0;

for(l=0; l < VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( dmatrix[l][m] < epsilon )
{
is_singular = 1;
}
}
}
if( is_singular == 0)
{

total_finds = total_finds + 1;

if( (diff25 > rec_diff25) && (has_converged_step > 25))
{
rec_diff25 = diff25;
}

if( (diff50 > rec_diff50) && (has_converged_step > 50))
{
rec_diff50 = diff50;
}
if( (diff100 > rec_diff100) && (has_converged_step > 100))
{
rec_diff100 = diff100;
}

if( diff1 > rec_diff1)
{
rec_diff1 = diff1;
}

if( (diff200 > rec_diff200) && (has_converged_step > 200) )
{
rec_diff200 = diff200;
}

if( (diff400 > rec_diff400 ) && (has_converged_step > 400))
{
rec_diff400 = diff400;
}
if( (diff800 > rec_diff800) && (has_converged_step > 800))
{
rec_diff800 = diff800;
}
if( (diff1200 > rec_diff1200) && (has_converged_step > 1200))
{
rec_diff1200 = diff1200;
}
#ifdef VERBOSE
for(l = 0; l< VERTEX; l++)
{
for(m=0; m< VERTEX; m++)
{
post_adjmat[l][m] = 0;
}
}
probable_unit_lengths = 0;

for(l = 0; l<VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( fabsl(dmatrix[l][m]-one) < epsilon )
{
probable_unit_lengths++ ;
post_adjmat[l][m] = 1;
post_adjmat[m][l] = 1;
}
}
}
/**** TEST post_adjmat[][] for 3-coloring BEGIN ****/

n_colors = 3;
coloring_found = 0;
for(v0 = 0; v0< 1 ; v0++)
{
for(v1 = 0; v1< 2 ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{
for(v13 = 0; v13< n_colors ; v13++)
{
colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
colors[13] = v13;
has_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
}
}
}

if( has_failed == 0 )
{
coloring_found = 1;
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
is_3colorable = 1;
}
else
{
is_3colorable = 0;
}

/**** TEST post_adjmat[][] for 3-coloring END ****/

printf(“adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, adjmat[l][m]) ;
}
printf(“\n”);
}

printf(“\n”);
printf(“post adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, post_adjmat[l][m]) ;
}
printf(“\n”);
}

if( is_3colorable == 0)
{

n_colors = 4;
coloring_found = 0;
num_4_colorings = 0;

for(v0 = 0; v0< n_colors ; v0++)
{
for(v1 = 0; v1< n_colors ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{
for(v13 = 0; v13< n_colors ; v13++)
{
colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
colors[13] = v13;
has_failed = 0;
four_colouring_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
four_colouring_failed = 1;
}
if( four_colouring_failed == 1)
{
break;
}
}

if( four_colouring_failed == 1)
{
break;
}
}

if( has_failed == 0 )
{
coloring_found = 1;
num_4_colorings++ ;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

num_4_colorings_mod_24 = num_4_colorings%24 ;

count_4_colorings = num_4_colorings/24;

}
printf(“total_finds = %d\n”, total_finds);
printf(“Tests count = %d “, count);
printf(“has_converged_step = %d “, has_converged_step);
printf(“max_has_converged_step = %d\n”, max_has_converged_step);
printf(“rec_diff1 = %.6Lf\n”, rec_diff1);
printf(“rec_diff25 = %.6Lf\n”, rec_diff25);
printf(“rec_diff50 = %.6Lf\n”, rec_diff50);
printf(“rec_diff100 = %.6Lf\n”, rec_diff100);
printf(“rec_diff200 = %.6Lf\n”, rec_diff200);
printf(“rec_diff400 = %.6Lf\n”, rec_diff400);
printf(“rec_diff800 = %.16Lf\n”, rec_diff800);
printf(“rec_diff1200 = %.16Lf\n”, rec_diff1200);
printf(“probable_unit_lengths = %d\n”, probable_unit_lengths);

printf(“graph is 3-colorable:”);
if(is_3colorable == 1)
{
printf(“yes. \n”);
}
else
{
printf(“no. \n”);
}
if( is_3colorable == 0 )
{
printf(“count_4_colorings = %d “, count_4_colorings);
printf(“num_4_colorings_mod_24 = %d\n”, num_4_colorings_mod_24);
}

printf(“Matrix of distances vertex to vertex:\n”);
printf(” “);
for(m=0; m<VERTEX; m++)
{
printf(” %c “, alphabet[m]);
}
printf(“\n”);
for(l=0; l< VERTEX ; l++)
{
printf(“%c “, alphabet[l]);
for(m=0; m< VERTEX ; m++)
{
printf(“%.3Lf “, dmatrix[l][m]);
}
printf(“\n”);
}

printf(“\n”);
fflush(stdout);
#endif

}
}
for(l=0; l< VERTEX ; l++)
{
forces[l][0] = (long double) 0;
forces[l][1] = (long double) 0;

for(m=0; m< VERTEX ; m++)
{
if( 1 == adjmat[l][m] )
{
vector[0] = xgood[m]-xgood[l];
vector[1] = ygood[m]-ygood[l];
vector[0] = vector[0]/dmatrix[l][m];
vector[1] = vector[1]/dmatrix[l][m];
vector[0] = vector[0]*C;
vector[1] = vector[1]*C;
vector[0] = vector[0]*(dmatrix[l][m]-one);
vector[1] = vector[1]*(dmatrix[l][m]-one);

forces[l][0] = forces[l][0] + vector[0];
forces[l][1] = forces[l][1] + vector[1];
}
}
}

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xgood[j] + forces[j][0];
ygood[j] = ygood[j] + forces[j][1];
}
}
/******************************************************
Below, post-convergence algorithm or heuristic:
******************************************************/
}
/*****************************************
while( count < 1 ) end Block
*****************************************/
}
/********************************************
end of while( 1 == 1 ) Block
********************************************/
return 0;
}

Written by meditationatae

February 21, 2017 at 1:38 pm

Posted in History

“Best candidate” graph, 14 vertices, udg

I modified my searcher of unit distance graphs for 13 vertices, so that it works on searching and solving 14-vertex unit distance graphs. I look for 14-vertex unit distance graphs that:

(a) are not 3-colorable and

(b) have the least possible 4-colorings, up to permutation of the 4 colors, which can be done be 4! = 24 ways.

My best candidate in that sense is decribed from file below:

$ cat nano
adjacency matrix:
0 0 1 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0
1 0 0 1 1 0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 1 0
1 0 0 0 0 1 0 0 0 0 0 1 1 0
0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 1 0 1 0 0 1
0 1 0 0 1 1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0

post adjacency matrix:
0 1 1 0 0 0 1 1 1 0 0 1 0 0
1 0 0 0 0 0 0 0 0 1 1 1 0 0
1 0 0 1 1 0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 1 0
1 0 0 0 0 1 0 0 0 0 0 1 1 0
1 0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 1 0 1 0 0 1
0 1 0 0 1 1 0 0 0 1 0 0 1 0
1 1 0 1 0 0 1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0
total_finds = 629
Tests count = 4 has_converged_step = 1788 max_has_converged_step = 1788
rec_diff1 = 39.680992
rec_diff25 = 39.884218
rec_diff50 = 17.695808
rec_diff100 = 15.382953
rec_diff200 = 9.138731
rec_diff400 = 0.066954
rec_diff800 = 0.0000007847509167
rec_diff1200 = 0.0000000000828210
probable_unit_lengths = 29
graph is 3-colorable:no.
count_4_colorings = 1114 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N
A 0.000 1.000 1.000 0.457 1.732 0.457 1.000 1.000 1.000 0.292 0.737 1.000 0.577 1.242
B 1.000 0.000 1.457 0.577 1.568 0.737 1.732 0.577 1.979 1.000 1.000 1.000 1.568 1.859
C 1.000 1.457 0.000 1.000 1.000 1.370 1.915 1.000 1.568 1.291 0.457 1.947 1.000 2.189
D 0.457 0.577 1.000 0.000 1.457 0.457 1.370 0.577 1.457 0.577 0.577 1.000 1.000 1.568
E 1.732 1.568 1.000 1.457 0.000 1.915 2.731 1.000 2.524 1.979 1.000 2.432 1.947 2.971
F 0.457 0.737 1.370 0.457 1.915 0.000 1.000 1.000 1.291 0.292 1.000 0.577 1.000 1.155
G 1.000 1.732 1.915 1.370 2.731 1.000 0.000 1.947 0.737 0.792 1.732 1.000 1.000 0.292
H 1.000 0.577 1.000 0.577 1.000 1.000 1.947 0.000 1.979 1.155 0.577 1.457 1.457 2.140
I 1.000 1.979 1.568 1.457 2.524 1.291 0.737 1.979 0.000 1.000 1.568 1.568 0.577 1.000
J 0.292 1.000 1.291 0.577 1.979 0.292 0.792 1.155 1.000 0.000 1.000 0.737 0.737 1.000
K 0.737 1.000 0.457 0.577 1.000 1.000 1.732 0.577 1.568 1.000 0.000 1.568 1.000 1.979
L 1.000 1.000 1.947 1.000 2.432 0.577 1.000 1.457 1.568 0.737 1.568 0.000 1.457 1.000
M 0.577 1.568 1.000 1.000 1.947 1.000 1.000 1.457 0.577 0.737 1.000 1.457 0.000 1.291
N 1.242 1.859 2.189 1.568 2.971 1.155 0.292 2.140 1.000 1.000 1.979 1.000 1.291 0.000

=====

Added :   Mon Feb 20 19:13:27 EST 2017

Re: post adjacency matrix for graph in file nano

The “post adjacency matrix” is obtained by filling in the

adjacency matrix with 1s for “new unit length edges” that are “probably of length 1” , such as the represented by the vertices A and L above, which are  1.000 after convergence of the system with springs of length 1 joining edges we want to be 1 apart.

In the adjacency matrix at the top, A is required to be at unit distance from vertices C, G, and I. As it turns out, A is also at practically unit distance from vertices B, H, and L also, in one solution to the unit distance graph equations.

Proving this rigorously would be difficult, so I’m content to call it “probably true”, provisionally.

Another program I wrote finds 9 triangles, also known as complete graphs on 3 vertices, or type K3:

Complete graph at Wikipedia:

https://en.wikipedia.org/wiki/Complete_graph

The output:

adjacency matrix:

A B C D E F G H I J K L M N
A 0 1 1 0 0 0 1 1 1 0 0 1 0 0
B 1 0 0 0 0 0 0 0 0 1 1 1 0 0
C 1 0 0 1 1 0 0 1 0 0 0 0 1 0
D 0 0 1 0 0 0 0 0 0 0 0 1 1 0
E 0 0 1 0 0 0 0 1 0 0 1 0 0 0
F 0 0 0 0 0 0 1 1 0 0 1 0 1 0
G 1 0 0 0 0 1 0 0 0 0 0 1 1 0
H 1 0 1 0 1 1 0 0 0 0 0 0 0 0
I 1 0 0 0 0 0 0 0 0 1 0 0 0 1
J 0 1 0 0 0 0 0 0 1 0 1 0 0 1
K 0 1 0 0 1 1 0 0 0 1 0 0 1 0
L 1 1 0 1 0 0 1 0 0 0 0 0 0 1
M 0 0 1 1 0 1 1 0 0 0 1 0 0 0
N 0 0 0 0 0 0 0 0 1 1 0 1 0 0

( 29 edges )

Triangles found:

triangle ACH
triangle CEH
triangle BJK
triangle ABL
triangle AGL
triangle CDM
triangle FGM
triangle FKM
triangle IJN

9 triangles in all

=====

Added:

Mon Feb 20 16:19:25 EST 2017

The “Best candidate” has been improved: the latest is not 3-colorable, and has 811 4-colorings, up to permutations of the 4 colors:

adjacency matrix:
0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 1 0 0 0 1 1 0 0
0 1 0 0 0 0 0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1
1 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 0 0 1 1
0 0 1 0 1 1 1 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0

post adjacency matrix:
0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 1 0 0 0 1 1 0 0
0 1 0 0 1 0 0 0 0 1 0 1 0 0
0 0 1 1 0 1 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1
1 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 1 1 1 1
0 0 1 0 1 1 1 0 0 1 0 0 0 0
1 0 1 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 1 0 1 0 1 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0
total_finds = 854
Tests count = 15 has_converged_step = 1399 max_has_converged_step = 1568
rec_diff1 = 39.680992
rec_diff25 = 39.884218
rec_diff50 = 17.695808
rec_diff100 = 17.881124
rec_diff200 = 9.138731
rec_diff400 = 0.066954
rec_diff800 = 0.0000007847509167
rec_diff1200 = 0.0000000000828210
probable_unit_lengths = 29
graph is 3-colorable:no.
count_4_colorings = 811 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N
A 0.000 1.732 0.737 0.737 0.457 1.000 1.291 2.524 1.000 1.568 0.577 1.000 1.979 2.432
B 1.732 0.000 2.354 1.000 1.915 1.000 2.180 1.732 1.000 1.000 1.370 1.732 2.000 1.000
C 0.737 2.354 0.000 1.370 1.000 1.732 1.000 2.731 1.444 1.915 1.000 1.000 1.947 2.887
D 0.737 1.000 1.370 0.000 1.000 0.577 1.444 2.000 0.457 1.000 0.457 1.000 1.732 1.732
E 0.457 1.915 1.000 1.000 0.000 1.000 1.732 2.929 1.370 1.947 1.000 1.457 2.432 2.731
F 1.000 1.000 1.732 0.577 1.000 0.000 2.000 2.432 1.000 1.457 1.000 1.568 2.291 1.947
G 1.291 2.180 1.000 1.444 1.732 2.000 0.000 1.915 1.191 1.370 1.000 0.457 1.000 2.354
H 2.524 1.732 2.731 2.000 2.929 2.432 1.915 0.000 1.568 1.000 1.947 1.732 1.000 1.000
I 1.000 1.000 1.444 0.457 1.370 1.000 1.191 1.568 0.000 0.577 0.457 0.737 1.291 1.457
J 1.568 1.000 1.915 1.000 1.947 1.457 1.370 1.000 0.577 0.000 1.000 1.000 1.000 1.000
K 0.577 1.370 1.000 0.457 1.000 1.000 1.000 1.947 0.457 1.000 0.000 0.577 1.457 1.915
L 1.000 1.732 1.000 1.000 1.457 1.568 0.457 1.732 0.737 1.000 0.577 0.000 1.000 2.000
M 1.979 2.000 1.947 1.732 2.432 2.291 1.000 1.000 1.291 1.000 1.457 1.000 0.000 1.732
N 2.432 1.000 2.887 1.732 2.731 1.947 2.354 1.000 1.457 1.000 1.915 2.000 1.732 0.000

=====

Added:  Mon Feb 20 20:14:02 EST 2017

Re: K3’s , or triangles, found in “post adjacency matrix” with graph having 811 4-colorings

I ran my triangle counter program on the 14-vertex, 29-edge graph whose adjacency matrix is the one labelled “post-(convergence) adjacency matrix” above.

It finds 11 complete graphs on three vertices, or K3’s:

adjacency matrix:

XXA B C D E F G H I J K L M N
A 0 0 0 0 0 1 0 0 1 0 0 1 0 0
B 0 0 0 1 0 1 0 0 1 1 0 0 0 1
C 0 0 0 0 1 0 1 0 0 0 1 1 0 0
D 0 1 0 0 1 0 0 0 0 1 0 1 0 0
E 0 0 1 1 0 1 0 0 0 0 1 0 0 0
F 1 1 0 0 1 0 0 0 1 0 1 0 0 0
G 0 0 1 0 0 0 0 0 0 0 1 0 1 0
H 0 0 0 0 0 0 0 0 0 1 0 0 1 1
I 1 1 0 0 0 1 0 0 0 0 0 0 0 0
J 0 1 0 1 0 0 0 1 0 0 1 1 1 1
K 0 0 1 0 1 1 1 0 0 1 0 0 0 0
L 1 0 1 1 0 0 0 0 0 1 0 0 1 0
M 0 0 0 0 0 0 1 1 0 1 0 1 0 0
N 0 1 0 0 0 0 0 1 0 1 0 0 0 0

(29 edges)

Triangles found:

triangle AFI
triangle BFI
triangle BDJ
triangle CEK
triangle EFK
triangle CGK
triangle DJL
triangle HJM
triangle JLM
triangle BJN
triangle HJN

11 triangles in all

 

=====

Added: Tue Feb 21 23:20:03 EST 2017
Re: possible unit distance graphs with 14 vertices

Below, the adjacency matrix for a graph with vertices labeled A to N,
and a matrix of distances vertex to vertex to 3 decimals with 33 edges
listed as of length 1.000 ; the program checks that the l_1 norm
of the vector (1, 1, 1, … 1) – (d_1, d_2, … d_33) is
less than about 1E-15, where d_1, d_2, … d_33 are the 33 edge lengths.

About graph and its embedding in R^2:

– 14-vertex, 33-edge graph.
– Not 3-colorable.
– Has 324 4-colorings, up to permutation of colors.
– Possibly a unit distance graph, according to numerical evidence.
– “count_4_colorings” below is the total number of 4-colorings, divided by 24; so this counts permuted colors as giving equivalent colorings.
adjacency matrix after “convergence” of the discrete dynamical system:

xxAxBxCxDxExFxGxHxIxJxKxLxMxN
A 0 0 0 0 0 1 1 1 0 0 0 0 1 0
B 0 0 1 0 1 1 0 0 0 0 0 0 0 1
C 0 1 0 0 0 0 0 1 0 0 1 0 0 0
D 0 0 0 0 0 1 0 1 0 1 1 1 0 0
E 0 1 0 0 0 0 1 1 0 1 0 0 0 1
F 1 1 0 1 0 0 0 0 0 0 0 1 1 0
G 1 0 0 0 1 0 0 1 1 0 0 1 0 0
H 1 0 1 1 1 0 1 0 0 0 1 0 0 0
I 0 0 0 0 0 0 1 0 0 0 1 1 1 1
J 0 0 0 1 1 0 0 0 0 0 0 1 0 1
K 0 0 1 1 0 0 0 1 1 0 0 0 1 1
L 0 0 0 1 0 1 1 0 1 1 0 0 0 0
M 1 0 0 0 0 1 0 0 1 0 1 0 0 0
N 0 1 0 0 1 0 0 0 1 1 1 0 0 0

total_finds = 263
Tests count = 20 has_converged_step = 1155 max_has_converged_step = 1334
rec_diff1 = 38.851687
rec_diff25 = 38.971383
rec_diff50 = 16.526850
rec_diff100 = 15.400758
rec_diff200 = 4.882370
rec_diff400 = 0.051505
rec_diff800 = 0.0000007203509511
rec_diff1200 = 0.0000000000803201

probable_unit_lengths = 33
graph is 3-colorable:no.
count_4_colorings = 324 num_4_colorings_mod_24 = 0

Matrix of distances vertex to vertex:

xxxxxAxxxxxBxxxxxCxxxxxDxxxxxExxxxxFxxxxxGxxxxxHxxxxxIxxxxxJxxxxxKxxxxxLxxxxxMxxxxxNx
A 0.000 0.737 0.457 1.915 1.732 1.000 1.000 1.000 0.457 2.354 1.370 1.370 1.000 1.444
B 0.737 0.000 1.000 1.568 1.000 1.000 0.457 0.577 0.577 1.732 1.457 0.737 1.568 1.000
C 0.457 1.000 0.000 1.732 1.915 0.737 1.370 1.000 0.457 2.354 1.000 1.444 0.577 1.370
D 1.915 1.568 1.732 0.000 1.457 1.000 1.947 1.000 1.457 1.000 1.000 1.000 1.947 0.577
E 1.732 1.000 1.915 1.457 0.000 1.568 1.000 1.000 1.457 1.000 1.947 0.577 2.432 1.000
F 1.000 1.000 0.737 1.000 1.568 0.000 1.457 0.577 0.577 1.732 0.457 1.000 1.000 0.737
G 1.000 0.457 1.370 1.947 1.000 1.457 0.000 1.000 1.000 1.915 1.915 1.000 1.947 1.370
H 1.000 0.577 1.000 1.000 1.000 0.577 1.000 0.000 0.577 1.370 1.000 0.457 1.457 0.457
I 0.457 0.577 0.457 1.457 1.457 0.577 1.000 0.577 0.000 1.947 1.000 1.000 1.000 1.000
J 2.354 1.732 2.354 1.000 1.000 1.732 1.915 1.370 1.947 0.000 1.915 1.000 2.731 1.000
K 1.370 1.457 1.000 1.000 1.947 0.457 1.915 1.000 1.000 1.915 0.000 1.370 1.000 1.000
L 1.370 0.737 1.444 1.000 0.577 1.000 1.000 0.457 1.000 1.000 1.370 0.000 1.915 0.457
M 1.000 1.568 0.577 1.947 2.432 1.000 1.947 1.457 1.000 2.731 1.000 1.915 0.000 1.732
N 1.444 1.000 1.370 0.577 1.000 0.737 1.370 0.457 1.000 1.000 1.000 0.457 1.732 0.000

Written by meditationatae

February 20, 2017 at 6:29 pm

Posted in History

Simple C test programs that open and read a file

To open a file for reading in the C programming language, one can pass to fopen a string containing the absolute path to the file. It looks like this:

fopen(“/home/david/fname”, “r”)

string = “/home/david/fname” = path to file, and

“r” for open in read-only mode.

Because it’s a statement, it must end with a `;’ like this:

fopen(“/home/david/fname”, “r”);

I guess the fopen function returns a file pointer …

In any case, the complete line of code is this:

in = fopen(“/home/david/fname”, “r”);

where in the inital declarations one has:

FILE *in;

My question was: what happens if instead we write:

in = fopen(“/home/david/fname “, “r”);

with fname followed by a space?

More on that later.

In my home directory /home/david/,

I redirected the output of “cal 2017” to fname like this:

$ cal 2017 > fname  [ENTER]

Then, fname has 1998 characters in Linux CentOS 6.8, including the digits for the year 2017.

 

My test program was to count each kind of digit, and show the total by digit, as well as the grand total of digits.

Executing the compiled program and the output went like this:

$ ./testprogram01.out
The file has in total:
36 0s
164 1s
156 2s
54 3s
36 4s
36 5s
36 6s
37 7s
36 8s
35 9s

The file has in total: 626 digits.

 

So according to this program, using the bash shell, typing

“cal 2017” produces a calendar for 2017, with 626 digits in all.

 

The source code is copied now:

#include <stdio.h>
int main(void)
{
int j;
unsigned char car;
int num0 = 0;
int num1 = 0;
int num2 = 0;
int num3 = 0;
int num4 = 0;
int num5 = 0;
int num6 = 0;
int num7 = 0;
int num8 = 0;
int num9 = 0;
int digits = 0;
FILE *in;

in = fopen(“/home/david/fname”, “r”);

for(j = 0; j < 1998; j++)
{
fscanf(in, “%c”, &car);

if(car == ‘0’)
{
num0++;
}

if(car == ‘1’)
{
num1++;
}

if(car == ‘2’)
{
num2++;
}

if(car == ‘3’)
{
num3++;
}

if(car == ‘4’)
{
num4++;
}

if(car == ‘5’)
{
num5++;
}

if(car == ‘6’)
{
num6++;
}

if(car == ‘7’)
{
num7++;
}

if(car == ‘8’)
{
num8++;
}

if(car == ‘9’)
{
num9++;
}
}

fclose(in);

printf(“The file has in total:\n”);
printf(“%d 0s\n”, num0);
printf(“%d 1s\n”, num1);
printf(“%d 2s\n”, num2);
printf(“%d 3s\n”, num3);
printf(“%d 4s\n”, num4);
printf(“%d 5s\n”, num5);
printf(“%d 6s\n”, num6);
printf(“%d 7s\n”, num7);
printf(“%d 8s\n”, num8);
printf(“%d 9s\n”, num9);

digits = num0 + num1 + num2 + num3 + num4 + num5;
digits = digits + num6 + num7 + num8 + num9;

printf(“\n”);
printf(“The file has in total: %d digits.\n”, digits);

return 0;
}

=======

Next, we edit testprogram01.c and add a space after fname in the string: “/home/david/fname” , saving the result to testprogram02.c :

The  relevant part of the 2nd program is this:

#include <stdio.h>
int main(void)
{
int j;
unsigned char car;
int num0 = 0;
int num1 = 0;
int num2 = 0;
int num3 = 0;
int num4 = 0;
int num5 = 0;
int num6 = 0;
int num7 = 0;
int num8 = 0;
int num9 = 0;
int digits = 0;
FILE *in;

in = fopen(“/home/david/fname “, “r”);

 

(The SPACE after “fname is apparent…).

Next, compile testprogram02.c:

gcc -o testprogram02.out testprogram02.c

Compilation successful, executable is named: testprogram02.out.

Now, we try to run testprogram02.out :

$ ./testprogram02.out [ENTER]
Segmentation fault (core dumped)

It seems therefore that

“/home/david/fname ” (with a space after the ‘e’ in fname)

does not work as a substitute for the proper string:

“/home/david/fname”  .

 

Written by meditationatae

February 19, 2017 at 2:50 pm

Posted in History

Hexadecimal dump of C source code …

C source code file =

/home/david/graphs/golomb18/udgraph13_solverff9789nu97b.c

or:

udgraph13_solverff9789nu97b.c

in directory:

/home/david/graphs/golomb18/

 

23 69 6e 63 6c 75 64 65 20 3c 73 74 64 69 6f 2e
68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 74
68 2e 68 3e 0a 23 64 65 66 69 6e 65 20 4e 55 4d
53 54 45 50 53 20 32 35 30 30 0a 23 64 65 66 69
6e 65 20 4d 41 58 44 49 46 46 41 54 31 30 30 20
20 28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20
31 38 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62 6c
65 29 20 31 29 0a 23 64 65 66 69 6e 65 20 4d 41
58 44 49 46 46 41 54 35 30 20 20 20 28 28 6c 6f
6e 67 20 64 6f 75 62 6c 65 29 20 31 38 29 2f 28
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 31 29
0a 23 64 65 66 69 6e 65 20 4d 41 58 44 49 46 46
41 54 32 35 20 20 20 28 28 6c 6f 6e 67 20 64 6f
75 62 6c 65 29 20 34 30 29 2f 28 28 6c 6f 6e 67
20 64 6f 75 62 6c 65 29 20 31 29 0a 23 64 65 66
69 6e 65 20 4d 41 58 44 49 46 46 41 54 31 20 20
20 28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20
34 30 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62 6c
65 29 20 31 29 0a 23 64 65 66 69 6e 65 20 4d 41
58 44 49 46 46 41 54 32 30 30 20 20 28 28 6c 6f
6e 67 20 64 6f 75 62 6c 65 29 20 39 36 29 2f 28
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 31 30
29 0a 23 64 65 66 69 6e 65 20 4d 41 58 44 49 46
46 41 54 34 30 30 20 20 28 28 6c 6f 6e 67 20 64
6f 75 62 6c 65 29 20 36 37 29 2f 28 28 6c 6f 6e
67 20 64 6f 75 62 6c 65 29 20 31 30 30 30 29 20
20 0a 23 64 65 66 69 6e 65 20 4d 41 58 44 49 46
46 41 54 38 30 30 20 20 28 28 6c 6f 6e 67 20 64
6f 75 62 6c 65 29 20 37 39 29 2f 28 28 6c 6f 6e
67 20 64 6f 75 62 6c 65 29 20 31 30 30 30 30 30
30 30 30 29 0a 23 64 65 66 69 6e 65 20 4d 41 58
44 49 46 46 41 54 31 32 30 30 20 20 28 28 6c 6f
6e 67 20 64 6f 75 62 6c 65 29 20 38 34 29 2f 28
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 31 30 30
30 30 30 30 30 30 30 30 30 30 29 0a 23 64 65 66
69 6e 65 20 56 45 52 42 4f 53 45 0a 23 64 65 66
69 6e 65 20 56 45 52 54 45 58 20 31 33 0a 0a 2f
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 72
65 63 5f 64 69 66 66 31 20 3d 20 20 20 20 32 38
2e 38 35 32 38 34 31 20 20 20 34 30 2e 30 0a 72
65 63 5f 64 69 66 66 32 35 20 3d 20 20 20 33 39
2e 36 36 38 37 38 35 20 20 20 34 30 2e 30 0a 72
65 63 5f 64 69 66 66 35 30 20 3d 20 20 20 31 37
2e 39 36 37 39 33 35 20 20 20 31 38 2e 30 0a 72
65 63 5f 64 69 66 66 31 30 30 20 3d 20 20 31 37
2e 38 35 36 39 35 38 20 20 20 31 38 2e 30 0a 72
65 63 5f 64 69 66 66 32 30 30 20 3d 20 20 39 2e
35 37 33 32 36 33 20 20 20 20 20 39 2e 36 0a 72
65 63 5f 64 69 66 66 34 30 30 20 3d 20 20 30 2e
30 36 36 39 38 32 20 20 20 20 20 36 2e 37 65 2d
32 0a 72 65 63 5f 64 69 66 66 38 30 30 20 3d 20
20 30 2e 30 30 30 30 30 30 37 38 33 32 32 31 32
35 36 34 20 20 37 2e 39 65 2d 37 0a 72 65 63 5f
64 69 66 66 31 32 30 30 20 3d 20 30 2e 30 30 30
30 30 30 30 30 30 30 38 33 39 38 34 31 20 20 38
2e 34 65 2d 31 31 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 0a 0a 0a 0a 20 20
73 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64 20
6c 6f 6e 67 20 6c 6f 6e 67 20 51 5b 32 30 39 37
31 35 32 5d 2c 63 61 72 72 79 3d 30 3b 0a 0a 20
20 75 6e 73 69 67 6e 65 64 20 6c 6f 6e 67 20 6c
6f 6e 67 20 42 36 34 4d 57 43 28 76 6f 69 64 29
0a 20 20 7b 20 20 75 6e 73 69 67 6e 65 64 20 6c
6f 6e 67 20 6c 6f 6e 67 20 74 2c 78 3b 20 73 74
61 74 69 63 20 69 6e 74 20 6a 3d 32 30 39 37 31
35 31 3b 0a 20 20 20 20 20 6a 3d 28 6a 2b 31 29
26 32 30 39 37 31 35 31 3b 0a 20 20 20 20 20 78
3d 51 5b 6a 5d 3b 20 74 3d 28 78 3c 3c 32 38 29
2b 63 61 72 72 79 3b 0a 20 20 20 20 20 63 61 72
72 79 3d 28 78 3e 3e 33 36 29 2d 28 74 3c 78 29
3b 0a 20 20 20 20 20 72 65 74 75 72 6e 20 28 51
5b 6a 5d 3d 74 2d 78 29 3b 0a 20 20 7d 0a 0a 23
64 65 66 69 6e 65 20 43 4e 47 20 20 28 20 63 6e
67 3d 36 39 30 36 39 36 39 30 36 39 4c 4c 2a 63
6e 67 2b 31 33 35 37 39 20 29 0a 23 64 65 66 69
6e 65 20 58 53 20 28 20 78 73 5e 3d 28 78 73 3c
3c 31 33 29 2c 20 78 73 5e 3d 28 78 73 3e 3e 31
37 29 2c 20 78 73 5e 3d 28 78 73 3c 3c 34 33 29
20 29 0a 23 64 65 66 69 6e 65 20 4b 49 53 53 20
28 20 42 36 34 4d 57 43 28 29 2b 43 4e 47 2b 58
53 20 29 0a 0a 0a 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 20 20 52 45
41 44 4d 45 20 53 45 43 54 49 4f 4e 20 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 0a 0a 31 30 2d 70 6f 69 6e 74 20 6e 6f 6e
2d 73 69 6e 67 75 6c 61 72 20 73 6f 6c 75 74 69
6f 6e 73 20 74 6f 20 74 68 65 20 75 6e 69 74 0a
67 72 61 70 68 20 70 72 6f 62 6c 65 6d 20 61 72
65 20 66 6f 75 6e 64 20 6e 75 6d 65 72 69 63 61
6c 6c 79 20 61 74 20 61 20 72 61 74 65 20 6f 66
0a 35 37 2e 39 20 73 6f 6c 75 74 69 6f 6e 73 20
70 65 72 20 73 65 63 6f 6e 64 20 6f 6e 20 61 20
64 75 61 6c 20 63 6f 72 65 20 41 74 68 6c 6f 6e
20 0a 35 30 30 30 2b 20 70 72 6f 63 65 73 73 6f
72 2e 0a 0a 54 68 65 20 73 6f 6c 75 74 69 6f 6e
73 20 61 72 65 20 65 78 70 65 63 74 65 64 20 74
6f 20 62 65 20 69 73 6f 6d 65 74 72 69 63 20 61
73 20 61 0a 31 30 2d 70 6f 69 6e 74 20 6d 65 74
72 69 63 20 73 70 61 63 65 20 74 6f 20 74 68 65
20 73 6f 6c 74 69 6f 6e 20 64 65 70 69 63 74 65
64 20 69 6e 0a 74 68 65 20 67 72 61 70 68 20 69
6e 20 6d 79 20 62 6c 6f 67 20 70 6f 73 74 20 3a
0a 0a 53 6b 65 74 63 68 20 6f 66 20 31 30 2d 76
65 72 74 65 78 20 75 6e 69 74 20 64 69 73 74 61
6e 63 65 20 67 72 61 70 68 2c 20 32 30 31 33 0a
61 74 20 55 52 4c 20 3d 0a 0a 6d 65 64 69 74 61
74 69 6f 6e 61 74 61 65 2e 77 6f 72 64 70 72 65
73 73 2e 63 6f 6d 2f 32 30 31 37 2f 30 32 2f 30
36 2f 73 6b 65 74 63 68 2d 6f 66 2d 31 30 2d 76
65 72 74 65 78 2d 75 6e 69 74 2d 64 69 73 74 61
6e 63 65 2d 67 72 61 70 68 2d 32 30 31 33 0a 0a
0a 54 68 65 20 73 63 69 20 64 6f 74 20 6d 61 74
68 20 70 6f 73 74 73 3a 0a 0a 6d 61 74 68 66 6f
72 75 6d 2e 6f 72 67 2f 6b 62 2f 6d 65 73 73 61
67 65 2e 6a 73 70 61 3f 6d 65 73 73 61 67 65 49
44 3d 31 30 30 38 31 33 38 38 0a 0a 61 6e 64 20
65 61 72 6c 69 65 72 3a 0a 0a 6d 61 74 68 66 6f
72 75 6d 2e 6f 72 67 2f 6b 62 2f 6d 65 73 73 61
67 65 2e 6a 73 70 61 3f 6d 65 73 73 61 67 65 49
44 3d 31 30 30 37 34 37 31 36 0a 0a 54 68 69 73
20 73 6f 6c 76 65 72 20 66 6f 72 20 61 20 70 61
72 74 69 63 75 6c 61 72 20 67 72 61 70 68 20 68
61 73 20 62 65 65 6e 20 6f 70 74 69 6d 69 7a 65
64 20 0a 74 6f 20 72 75 6e 20 69 6e 20 61 73 20
6c 69 74 74 6c 65 20 74 69 6d 65 20 61 73 20 70
6f 73 73 69 62 6c 65 20 66 6f 72 20 74 68 65 20
67 69 76 65 6e 20 67 72 61 70 68 2c 0a 64 65 63
72 69 62 65 64 20 62 79 20 74 68 65 20 31 30 78
31 30 20 61 64 6a 61 63 65 6e 63 79 20 6d 61 74
72 69 78 2e 0a 0a 54 6f 20 63 6f 6d 70 69 6c 65
2c 20 49 20 74 79 70 65 3a 0a 0a 24 20 67 63 63
20 2d 6c 6d 20 2d 4f 33 20 2d 6f 20 20 75 64 67
72 61 70 68 5f 73 6f 6c 76 65 72 32 30 31 61 2e
6f 75 74 20 75 64 67 72 61 70 68 5f 73 6f 6c 76
65 72 32 30 31 61 2e 63 0a 0a 61 74 20 74 68 65
20 73 68 65 6c 6c 20 63 6f 6d 6d 61 6e 64 20 6c
69 6e 65 20 69 6e 20 4c 69 6e 75 78 2e 20 0a 0a
54 68 65 20 65 78 65 63 75 74 61 62 6c 65 20 69
73 20 74 68 65 6e 20 20 75 64 67 72 61 70 68 5f
73 6f 6c 76 65 72 32 30 31 61 2e 6f 75 74 20 2e
0a 0a 0a 49 6e 20 43 20 70 72 65 2d 70 72 6f 63
65 73 73 6f 72 20 74 65 72 6d 73 2c 20 69 66 20
56 45 52 42 4f 53 45 20 69 73 20 64 65 66 69 6e
65 64 20 62 79 0a 61 20 70 72 65 2d 70 72 6f 63
65 73 73 6f 72 20 64 69 72 65 63 74 69 76 65 2c
0a 4e 75 6d 62 65 72 2d 53 69 67 6e 20 64 65 66
69 6e 65 20 56 45 52 42 4f 53 45 0a 73 61 79 20
6f 6e 20 6c 69 6e 65 20 37 20 61 62 6f 76 65 20
61 66 74 65 72 20 74 68 65 20 6f 74 68 65 72 20
0a 4e 75 6d 62 65 72 2d 73 69 67 6e 20 64 65 66
69 6e 65 73 2c 20 0a 74 68 65 6e 20 74 68 65 20
73 6f 6c 75 74 69 6f 6e 20 63 6f 75 6e 74 20 61
6e 64 20 74 68 65 20 31 30 78 31 30 20 6d 61 74
72 69 78 20 6f 66 20 76 65 72 74 65 78 20 74 6f
20 76 65 72 74 65 78 0a 64 69 73 74 61 6e 63 65
73 20 66 6f 72 20 61 20 73 6f 6c 75 74 69 6f 6e
20 77 69 6c 6c 20 62 65 20 70 72 69 6e 74 65 64
2e 0a 0a 41 73 20 61 62 6f 76 65 20 56 45 52 42
4f 53 45 20 69 73 20 6e 6f 74 20 64 65 66 69 6e
65 64 2c 20 74 68 65 20 70 72 6f 67 72 61 6d 20
77 69 6c 6c 20 72 75 6e 20 77 69 74 68 20 0a 6d
69 6e 69 6d 61 6c 20 6f 75 74 70 75 74 20 75 6e
74 69 6c 20 69 74 20 66 69 6e 69 73 68 65 73 20
61 66 74 65 72 20 61 62 6f 75 74 20 39 20 6d 69
6e 75 74 65 73 0a 77 69 74 68 20 6d 79 20 73 79
73 74 65 6d 2e 0a 0a 54 68 69 73 20 52 45 41 44
4d 45 20 69 73 20 62 61 73 65 64 20 6f 6e 20 66
69 6c 65 0a 53 6c 61 73 68 20 68 6f 6d 65 20 73
6c 61 73 68 20 64 61 76 69 64 20 73 6c 61 73 68
20 67 72 61 70 68 73 20 73 6c 61 73 68 20 67 6f
6c 6f 6d 62 36 0a 73 6c 61 73 68 20 75 64 67 72
61 70 68 5f 73 6f 6c 76 65 72 32 30 31 61 20 64
6f 74 20 63 2c 0a 0a 77 69 6c 6c 20 73 65 72 76
65 20 74 6f 20 77 72 69 74 65 20 74 68 65 20 6c
6f 63 61 6c 20 66 69 6c 65 3a 0a 0a 53 6c 61 73
68 20 68 6f 6d 65 20 73 6c 61 73 68 20 64 61 76
69 64 20 73 6c 61 73 68 20 67 72 61 70 68 73 20
73 6c 61 73 68 20 67 6f 6c 6f 6d 62 36 0a 73 6c
61 73 68 20 75 64 67 72 61 70 68 5f 73 6f 6c 76
65 72 33 30 31 61 20 64 6f 74 20 63 20 2c 0a 0a
61 6e 64 20 77 69 6c 6c 20 67 6f 20 62 79 20 74
68 65 20 4d 6f 6e 69 6b 65 72 20 6f 72 20 61 6c
69 61 73 0a 22 75 6e 69 74 20 64 69 73 74 61 6e
63 65 20 67 72 61 70 68 20 73 6f 6c 76 65 72 20
64 72 61 66 74 20 31 30 31 22 20 0a 0a 61 20 68
65 78 61 64 65 63 69 6d 61 6c 20 64 75 6d 70 20
77 69 6c 6c 20 62 65 20 70 6f 73 74 65 64 20 74
6f 20 6d 79 20 62 6c 6f 67 0a 0a 6d 65 64 69 74
61 74 69 6f 6e 61 74 61 65 2e 77 6f 72 64 70 72
65 73 73 2e 63 6f 6d 0a 0a 0a 44 61 76 69 64 20
42 65 72 6e 69 65 72 0a 0a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 20 20
20 52 45 41 44 4d 45 20 45 4e 44 20 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2f 0a 0a 69 6e 74 20 6d 61 69 6e
28 76 6f 69 64 29 0a 7b 0a 20 20 75 6e 73 69 67
6e 65 64 20 6c 6f 6e 67 20 6c 6f 6e 67 20 69 2c
63 6e 67 3d 31 32 33 34 35 36 37 38 39 39 38 37
36 35 34 33 32 31 4c 4c 2c 20 78 73 3d 33 36 32
34 33 36 30 36 39 33 36 32 34 33 36 30 36 39 4c
4c 3b 0a 20 20 75 6e 73 69 67 6e 65 64 20 6c 6f
6e 67 20 6c 6f 6e 67 20 72 61 6e 64 78 3b 0a 20
20 69 6e 74 20 42 3b 0a 20 20 69 6e 74 20 6a 3b
0a 20 20 69 6e 74 20 6b 3b 0a 20 20 69 6e 74 20
71 75 69 74 3b 0a 20 20 69 6e 74 20 69 73 5f 73
69 6e 67 75 6c 61 72 3b 0a 20 20 69 6e 74 20 67
72 61 70 68 5f 66 6f 75 6e 64 3b 0a 20 20 69 6e
74 20 74 6f 74 61 6c 5f 65 64 67 65 73 3b 0a 20
20 69 6e 74 20 64 65 67 72 65 65 5f 74 65 73 74
5f 70 61 73 73 65 64 3b 0a 20 20 69 6e 74 20 6c
2c 20 6d 3b 0a 20 20 69 6e 74 20 6e 2c 20 70 3b
0a 20 20 69 6e 74 20 68 61 73 5f 6b 34 3b 0a 20
20 69 6e 74 20 69 73 5f 33 63 6f 6c 6f 72 61 62
6c 65 3b 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b
0a 20 20 69 6e 74 20 74 6f 74 61 6c 5f 66 69 6e
64 73 3b 0a 20 20 69 6e 74 20 70 72 6f 62 61 62
6c 65 5f 75 6e 69 74 5f 6c 65 6e 67 74 68 73 3b
0a 20 20 69 6e 74 20 73 6f 6c 75 74 69 6f 6e 5f
66 6f 75 6e 64 3b 0a 20 20 69 6e 74 20 63 6f 6c
6f 72 69 6e 67 5f 66 6f 75 6e 64 3b 0a 20 20 63
68 61 72 20 61 6c 70 68 61 62 65 74 5b 56 45 52
54 45 58 5d 3b 0a 20 20 75 6e 73 69 67 6e 65 64
20 6c 6f 6e 67 20 6c 6f 6e 67 20 6d 61 78 69 5f
75 6c 6c 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75 62
6c 65 20 78 63 6f 6f 72 64 5b 56 45 52 54 45 58
5d 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65
20 64 69 66 66 3b 0a 20 20 6c 6f 6e 67 20 64 6f
75 62 6c 65 20 64 69 66 66 32 35 3b 0a 20 20 6c
6f 6e 67 20 64 6f 75 62 6c 65 20 64 69 66 66 35
30 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65
20 64 69 66 66 31 30 30 3b 0a 20 20 6c 6f 6e 67
20 64 6f 75 62 6c 65 20 64 69 66 66 32 30 30 3b
0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 64
69 66 66 34 30 30 3b 0a 20 20 6c 6f 6e 67 20 64
6f 75 62 6c 65 20 64 69 66 66 38 30 30 3b 0a 20
20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 64 69 66
66 31 32 30 30 3b 0a 20 20 6c 6f 6e 67 20 64 6f
75 62 6c 65 20 64 69 66 66 31 3b 0a 20 20 6c 6f
6e 67 20 64 6f 75 62 6c 65 20 72 65 63 5f 64 69
66 66 32 35 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75
62 6c 65 20 72 65 63 5f 64 69 66 66 35 30 3b 0a
20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 72 65
63 5f 64 69 66 66 31 30 30 3b 0a 20 20 6c 6f 6e
67 20 64 6f 75 62 6c 65 20 72 65 63 5f 64 69 66
66 32 30 30 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75
62 6c 65 20 72 65 63 5f 64 69 66 66 34 30 30 3b
0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 72
65 63 5f 64 69 66 66 38 30 30 3b 0a 20 20 6c 6f
6e 67 20 64 6f 75 62 6c 65 20 72 65 63 5f 64 69
66 66 31 32 30 30 3b 0a 20 20 6c 6f 6e 67 20 64
6f 75 62 6c 65 20 72 65 63 5f 64 69 66 66 31 3b
0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 72
75 31 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c
65 20 72 75 32 3b 0a 20 20 6c 6f 6e 67 20 64 6f
75 62 6c 65 20 65 70 73 69 6c 6f 6e 3b 0a 20 20
69 6e 74 20 63 6f 31 3b 0a 20 20 69 6e 74 20 63
6f 32 3b 0a 20 20 69 6e 74 20 63 6f 6c 6f 72 73
5b 56 45 52 54 45 58 5d 3b 0a 20 20 69 6e 74 20
6e 75 6d 5f 34 5f 63 6f 6c 6f 72 69 6e 67 73 3b
0a 20 20 69 6e 74 20 6e 75 6d 5f 34 5f 63 6f 6c
6f 72 69 6e 67 73 5f 6d 6f 64 5f 32 34 3b 0a 20
20 69 6e 74 20 63 6f 75 6e 74 5f 34 5f 63 6f 6c
6f 72 69 6e 67 73 3b 0a 20 20 69 6e 74 20 6e 5f
63 6f 6c 6f 72 73 3b 0a 20 20 69 6e 74 20 64 65
67 72 65 65 73 5b 56 45 52 54 45 58 5d 3b 0a 20
20 69 6e 74 20 76 30 2c 20 76 31 2c 20 76 32 2c
20 76 33 2c 20 76 34 2c 20 76 35 2c 20 76 36 2c
20 76 37 2c 20 76 38 2c 20 76 39 2c 20 76 31 30
2c 20 76 31 31 2c 20 76 31 32 3b 0a 20 20 69 6e
74 20 68 61 73 5f 66 61 69 6c 65 64 3b 0a 20 20
69 6e 74 20 6e 75 6d 65 64 67 65 73 3b 0a 20 20
6c 6f 6e 67 20 64 6f 75 62 6c 65 20 64 69 66 66
5f 72 65 63 6f 72 64 3b 0a 20 20 6c 6f 6e 67 20
64 6f 75 62 6c 65 20 6d 61 78 64 69 66 66 61 74
34 30 30 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75 62
6c 65 20 6f 6e 65 3b 0a 20 20 6c 6f 6e 67 20 64
6f 75 62 6c 65 20 79 63 6f 6f 72 64 5b 56 45 52
54 45 58 5d 3b 0a 20 20 6c 6f 6e 67 20 64 6f 75
62 6c 65 20 66 6f 72 63 65 73 5b 56 45 52 54 45
58 5d 5b 32 5d 3b 0a 20 20 6c 6f 6e 67 20 64 6f
75 62 6c 65 20 43 3b 0a 20 20 6c 6f 6e 67 20 64
6f 75 62 6c 65 20 76 65 63 74 6f 72 5b 32 5d 3b
0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 78
67 6f 6f 64 5b 56 45 52 54 45 58 5d 3b 0a 20 20
6c 6f 6e 67 20 64 6f 75 62 6c 65 20 79 67 6f 6f
64 5b 56 45 52 54 45 58 5d 3b 0a 20 20 69 6e 74
20 66 6f 75 72 5f 63 6f 6c 6f 75 72 69 6e 67 5f
66 61 69 6c 65 64 3b 0a 20 20 69 6e 74 20 68 61
73 5f 63 6f 6e 76 65 72 67 65 64 5f 66 6c 61 67
3b 0a 20 20 69 6e 74 20 68 61 73 5f 63 6f 6e 76
65 72 67 65 64 5f 73 74 65 70 3b 0a 20 20 69 6e
74 20 6d 61 78 5f 68 61 73 5f 63 6f 6e 76 65 72
67 65 64 5f 73 74 65 70 3b 0a 20 20 6c 6f 6e 67
20 64 6f 75 62 6c 65 20 73 63 61 6c 69 6e 67 3b
0a 20 20 6c 6f 6e 67 20 64 6f 75 62 6c 65 20 64
6d 61 74 72 69 78 5b 56 45 52 54 45 58 5d 5b 56
45 52 54 45 58 5d 3b 0a 20 20 69 6e 74 20 61 64
6a 6d 61 74 5b 56 45 52 54 45 58 5d 5b 56 45 52
54 45 58 5d 3b 0a 20 20 69 6e 74 20 70 6f 73 74
5f 61 64 6a 6d 61 74 5b 56 45 52 54 45 58 5d 5b
56 45 52 54 45 58 5d 3b 0a 0a 0a 2f 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 0a 0a 75 64 67 72 61 70 68 5f 73 6f
6c 76 65 72 33 34 30 31 61 2e 63 20 3a 20 20 75
73 65 72 09 32 32 6d 35 30 2e 31 39 38 73 20 77
2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 4d
41 58 44 49 46 46 41 54 31 30 30 20 20 28 28 6c
6f 6e 67 20 64 6f 75 62 6c 65 29 20 33 38 29 2f
28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 31
29 0a 0a 0a 0a 6e 65 77 74 65 73 74 7a 37 34 36
61 2e 6f 75 74 20 20 33 34 35 20 3a 20 38 6d 20
33 34 2e 36 33 31 73 20 66 6f 72 20 33 30 6b 20
73 6f 6c 6e 73 2e 20 2c 20 75 73 69 6e 67 20 2d
4f 33 20 0a 6e 65 77 74 65 73 74 7a 37 34 35 61
2e 6f 75 74 20 20 33 34 30 20 3a 20 38 6d 20 33
35 73 20 66 6f 72 20 33 30 30 30 30 20 73 6f 6c
75 74 69 6f 6e 73 2c 20 77 69 74 68 20 20 2d 4f
33 0a 6e 65 77 74 65 73 74 7a 35 38 35 61 2e 63
3a 20 38 6d 20 35 31 73 20 66 6f 72 20 33 30 30
30 30 20 73 6f 6c 75 74 69 6f 6e 73 2c 20 75 73
69 6e 67 20 2d 4f 33 20 6f 70 74 69 6d 69 7a 61
74 69 6f 6e 20 0a 6e 65 77 74 65 73 74 38 33 61
2e 63 3a 20 20 39 6d 20 35 37 73 20 66 6f 72 20
33 30 30 30 30 20 73 6f 6c 75 74 69 6f 6e 73 2c
20 75 73 69 6e 67 20 2d 4f 33 20 6f 70 74 69 6d
69 7a 61 74 69 6f 6e 20 6f 70 74 69 6f 6e 0a 6e
65 77 74 65 73 74 38 31 61 2e 63 3a 20 20 39 6d
20 35 37 73 20 66 6f 72 20 33 30 30 30 30 20 73
6f 6c 75 74 69 6f 6e 73 2c 20 75 73 69 6e 67 20
2d 4f 33 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e
20 6f 70 74 69 6f 6e 0a 6e 65 77 74 65 73 74 37
33 61 2e 63 3a 20 20 38 6d 20 34 39 73 20 66 6f
72 20 33 30 30 30 30 20 73 6f 6c 75 74 69 6f 6e
73 2c 20 75 73 69 6e 67 20 2d 4f 33 20 6f 70 74
69 6d 69 7a 61 74 69 6f 6e 20 6f 70 74 69 6f 6e
0a 6e 65 77 74 65 73 74 36 36 61 2e 63 3a 20 20
31 30 6d 20 32 35 73 20 66 6f 72 20 33 30 30 30
30 20 73 6f 6c 75 74 69 6f 6e 73 2c 20 75 73 69
6e 67 20 2d 4f 33 20 6f 70 74 69 6d 69 7a 61 74
69 6f 6e 20 6f 70 74 69 6f 6e 0a 6e 65 77 74 65
73 74 36 35 61 2e 63 3a 20 20 31 31 6d 20 33 30
73 20 66 6f 72 20 33 30 30 30 30 20 73 6f 6c 75
74 69 6f 6e 73 20 0a 6e 65 77 74 65 73 74 36 34
61 2e 63 3a 20 20 31 31 6d 20 33 30 73 20 66 6f
72 20 33 30 30 30 30 20 73 6f 6c 75 74 69 6f 6e
73 20 0a 6e 65 77 74 65 73 74 36 33 61 2e 63 3a
20 20 31 31 6d 20 33 33 73 20 66 6f 72 20 33 30
30 30 30 20 73 6f 6c 75 74 69 6f 6e 73 20 0a 6e
65 77 74 65 73 74 36 32 61 2e 63 3a 20 20 31 31
6d 20 33 33 73 20 66 6f 72 20 33 30 30 30 30 20
73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65 77 74 65
73 74 36 31 61 2e 63 3a 20 20 33 6d 20 35 31 73
20 66 6f 72 20 31 30 30 30 30 20 73 6f 6c 75 74
69 6f 6e 73 20 0a 6e 65 77 74 65 73 74 35 37 61
2e 63 3a 20 20 36 6d 20 32 37 73 20 66 6f 72 20
31 30 30 30 30 20 73 6f 6c 75 74 69 6f 6e 73 20
0a 6e 65 77 74 65 73 74 35 36 61 2e 63 3a 20 20
36 6d 20 33 37 73 20 66 6f 72 20 31 30 30 30 30
20 73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65 77 74
65 73 74 35 35 61 2e 63 3a 20 20 36 6d 20 34 33
73 20 66 6f 72 20 31 30 30 30 30 20 73 6f 6c 75
74 69 6f 6e 73 20 0a 6e 65 77 74 65 73 74 35 34
61 2e 63 3a 20 20 36 6d 20 34 38 73 20 66 6f 72
20 31 30 30 30 30 20 73 6f 6c 75 74 69 6f 6e 73
20 0a 6e 65 77 74 65 73 74 35 33 61 2e 63 3a 20
20 36 6d 20 34 36 73 20 66 6f 72 20 31 30 30 30
30 20 73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65 77
74 65 73 74 34 38 61 2e 63 3a 20 20 36 32 20 73
65 63 6f 6e 64 73 20 66 6f 72 20 31 36 30 30 20
73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65 77 74 65
73 74 34 37 61 2e 63 3a 20 20 31 34 20 73 65 63
6f 6e 64 73 20 66 6f 72 20 34 30 30 20 73 6f 6c
75 74 69 6f 6e 73 20 0a 6e 65 77 74 65 73 74 34
36 61 2e 63 3a 20 20 36 36 20 73 65 63 6f 6e 64
73 20 66 6f 72 20 34 30 30 20 73 6f 6c 75 74 69
6f 6e 73 0a 6e 65 77 74 65 73 74 33 39 61 2e 63
3a 20 20 36 37 20 73 65 63 6f 6e 64 73 20 66 6f
72 20 34 30 30 20 73 6f 6c 75 74 69 6f 6e 73 20
0a 6e 65 77 74 65 73 74 33 37 61 2e 63 3a 20 20
37 30 20 73 65 63 6f 6e 64 73 20 66 6f 72 20 34
30 30 20 73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65
77 74 65 73 74 33 35 61 2e 63 3a 20 20 37 39 20
73 65 63 6f 6e 64 73 20 66 6f 72 20 34 30 30 20
73 6f 6c 75 74 69 6f 6e 73 0a 6e 65 77 74 65 73
74 33 34 61 2e 63 3a 20 20 37 32 20 73 65 63 6f
6e 64 73 20 66 6f 72 20 34 30 30 20 73 6f 6c 75
74 69 6f 6e 73 20 0a 6e 65 77 74 65 73 74 33 33
61 2e 63 3a 20 20 39 31 20 73 65 63 6f 6e 64 73
20 66 6f 72 20 34 30 30 20 73 6f 6c 75 74 69 6f
6e 73 20 0a 6e 65 77 74 65 73 74 33 30 61 2e 63
3a 20 20 31 36 20 73 65 63 6f 6e 64 73 20 66 6f
72 20 31 30 30 20 73 6f 6c 75 74 69 6f 6e 73 0a
6e 65 77 74 65 73 74 32 39 61 2e 63 3a 20 20 31
38 20 73 65 63 6f 6e 64 73 20 66 6f 72 20 31 30
30 20 73 6f 6c 75 74 69 6f 6e 73 20 0a 6e 65 77
74 65 73 74 32 38 61 2e 63 3a 20 20 32 35 20 73
65 63 6f 6e 64 73 20 66 6f 72 20 31 30 30 20 73
6f 6c 75 74 69 6f 6e 73 0a 6e 65 77 74 65 73 74
32 37 61 2e 63 3a 20 20 35 30 20 73 65 63 6f 6e
64 73 20 66 6f 72 20 31 30 30 20 73 6f 6c 75 74
69 6f 6e 73 0a 6e 65 77 74 65 73 74 32 36 61 2e
63 3a 20 20 39 39 20 73 65 63 6f 6e 64 73 20 66
6f 72 20 31 30 30 20 73 6f 6c 75 74 69 6f 6e 73
20 0a 6e 65 77 74 65 73 74 32 35 61 2e 63 3a 20
20 20 33 30 30 30 20 73 6f 6c 75 74 69 6f 6e 73
20 70 65 72 20 68 6f 75 72 0a 20 20 20 20 20 20
20 20 20 20 20 20 20 20 20 20 66 6f 72 20 31 30
30 20 73 6f 6c 75 74 69 6f 6e 73 2c 20 32 20 6d
69 6e 75 74 65 73 20 2e 2e 2e 0a 38 30 38 20 73
6f 6c 75 74 69 6f 6e 73 20 70 65 72 20 6d 69 6e
75 74 65 20 66 6f 72 20 34 2d 70 6f 69 6e 74 20
64 69 61 6d 6f 6e 64 20 73 68 61 70 65 2e 0a 67
74 65 73 74 32 33 30 61 2e 63 20 3a 0a 32 36 30
30 20 73 6f 6c 75 74 69 6f 6e 73 20 70 65 72 20
6d 69 6e 75 74 65 20 66 6f 72 20 37 2d 70 6f 69
6e 74 20 34 2d 63 6f 6c 6f 75 72 0a 67 72 61 70
68 0a 67 74 65 73 74 39 38 30 61 2e 63 20 3a 0a
39 38 30 30 30 20 73 6f 6c 75 74 69 6f 6e 73 20
70 65 72 20 6d 69 6e 75 74 65 20 66 6f 72 20 37
2d 70 6f 69 6e 74 20 34 2d 63 6f 6c 6f 75 72 0a
67 72 61 70 68 2c 20 20 4d 6f 73 65 72 73 27 20
73 70 69 6e 64 6c 65 2e 0a 65 6e 2e 77 69 6b 69
70 65 64 69 61 2e 6f 72 67 20 73 6c 61 73 68 20
77 69 6b 69 20 73 6c 61 73 68 20 4d 6f 73 65 72
5f 73 70 69 6e 64 6c 65 0a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 0a 20 20
42 20 3d 20 33 34 30 3b 0a 20 20 74 6f 74 61 6c
5f 65 64 67 65 73 20 3d 20 32 34 20 3b 0a 0a 20
20 74 6f 74 61 6c 5f 66 69 6e 64 73 20 3d 20 30
3b 0a 0a 20 20 6d 61 78 69 5f 75 6c 6c 20 3d 20
28 28 75 6e 73 69 67 6e 65 64 20 6c 6f 6e 67 20
6c 6f 6e 67 29 36 37 30 30 34 31 37 29 2a 28 28
75 6e 73 69 67 6e 65 64 20 6c 6f 6e 67 20 0a 6c
6f 6e 67 29 32 37 35 33 30 37 34 30 33 36 30 39
35 29 3b 0a 20 20 73 63 61 6c 69 6e 67 20 3d 20
28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 33
37 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65
29 20 31 30 29 3b 0a 20 20 6f 6e 65 20 3d 20 28
6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 31 3b 0a
20 20 64 69 66 66 5f 72 65 63 6f 72 64 20 3d 20
28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 34
31 30 30 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62
6c 65 29 20 31 30 30 29 3b 0a 0a 20 20 64 69 66
66 5f 72 65 63 6f 72 64 20 3d 20 4d 41 58 44 49
46 46 41 54 31 3b 0a 0a 0a 20 20 6d 61 78 64 69
66 66 61 74 34 30 30 20 3d 20 28 28 6c 6f 6e 67
20 64 6f 75 62 6c 65 29 31 29 2f 28 28 6c 6f 6e
67 20 64 6f 75 62 6c 65 29 31 30 30 30 30 30 29
3b 0a 20 20 6d 61 78 64 69 66 66 61 74 34 30 30
20 3d 20 28 28 28 6c 6f 6e 67 20 64 6f 75 62 6c
65 29 31 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62
6c 65 29 31 30 30 30 30 30 29 29 2a 6d 61 78 64
69 66 66 61 74 34 30 30 3b 0a 20 20 6d 61 78 64
69 66 66 61 74 34 30 30 20 3d 20 28 28 28 6c 6f
6e 67 20 64 6f 75 62 6c 65 29 31 29 2f 28 28 6c
6f 6e 67 20 64 6f 75 62 6c 65 29 31 30 30 30 30
30 29 29 2a 6d 61 78 64 69 66 66 61 74 34 30 30
3b 0a 0a 20 20 65 70 73 69 6c 6f 6e 20 3d 20 28
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 31 29 2f
28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 31 30
30 30 30 30 30 30 29 3b 0a 0a 20 20 72 65 63 5f
64 69 66 66 32 35 20 3d 20 28 6c 6f 6e 67 20 64
6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65 63 5f
64 69 66 66 35 30 20 3d 20 28 6c 6f 6e 67 20 64
6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65 63 5f
64 69 66 66 31 30 30 20 3d 20 28 6c 6f 6e 67 20
64 6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65 63
5f 64 69 66 66 31 20 3d 20 28 6c 6f 6e 67 20 64
6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65 63 5f
64 69 66 66 32 30 30 20 3d 20 28 6c 6f 6e 67 20
64 6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65 63
5f 64 69 66 66 34 30 30 20 3d 20 28 6c 6f 6e 67
20 64 6f 75 62 6c 65 29 20 30 3b 0a 20 20 72 65
63 5f 64 69 66 66 38 30 30 20 3d 20 28 6c 6f 6e
67 20 64 6f 75 62 6c 65 29 20 30 3b 0a 20 20 72
65 63 5f 64 69 66 66 31 32 30 30 20 3d 20 28 6c
6f 6e 67 20 64 6f 75 62 6c 65 29 20 30 3b 0a 0a
0a 0a 0a 0a 0a 20 20 61 6c 70 68 61 62 65 74 5b
30 5d 20 3d 20 27 41 27 3b 0a 20 20 61 6c 70 68
61 62 65 74 5b 31 5d 20 3d 20 27 42 27 3b 0a 20
20 61 6c 70 68 61 62 65 74 5b 32 5d 20 3d 20 27
43 27 3b 0a 20 20 61 6c 70 68 61 62 65 74 5b 33
5d 20 3d 20 27 44 27 3b 0a 20 20 61 6c 70 68 61
62 65 74 5b 34 5d 20 3d 20 27 45 27 3b 0a 20 20
61 6c 70 68 61 62 65 74 5b 35 5d 20 3d 20 27 46
27 3b 0a 20 20 61 6c 70 68 61 62 65 74 5b 36 5d
20 3d 20 27 47 27 3b 0a 20 20 61 6c 70 68 61 62
65 74 5b 37 5d 20 3d 20 27 48 27 3b 0a 20 20 61
6c 70 68 61 62 65 74 5b 38 5d 20 3d 20 27 49 27
3b 0a 20 20 61 6c 70 68 61 62 65 74 5b 39 5d 20
3d 20 27 4a 27 3b 0a 20 20 61 6c 70 68 61 62 65
74 5b 31 30 5d 20 3d 20 27 4b 27 3b 0a 20 20 61
6c 70 68 61 62 65 74 5b 31 31 5d 20 3d 20 27 4c
27 3b 0a 20 20 61 6c 70 68 61 62 65 74 5b 31 32
5d 20 3d 20 27 4d 27 3b 0a 0a 0a 0a 0a 0a 20 20
2f 2a 20 46 69 72 73 74 20 73 65 65 64 20 51 5b
5d 20 77 69 74 68 20 43 4e 47 2b 58 53 3a 20 20
20 20 2a 2f 0a 20 20 20 20 20 66 6f 72 28 69 3d
30 3b 69 3c 32 30 39 37 31 35 32 3b 69 2b 2b 29
20 51 5b 69 5d 3d 43 4e 47 2b 58 53 3b 0a 0a 20
20 66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52
54 45 58 20 3b 20 6c 2b 2b 29 0a 20 20 7b 0a 20
20 20 20 64 6d 61 74 72 69 78 5b 6c 5d 5b 6c 5d
20 3d 20 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29
20 30 3b 0a 20 20 7d 0a 0a 0a 0a 77 68 69 6c 65
28 20 74 6f 74 61 6c 5f 66 69 6e 64 73 20 3c 20
35 30 30 30 30 30 30 30 30 30 20 20 29 0a 7b 0a
0a 20 20 67 72 61 70 68 5f 66 6f 75 6e 64 20 3d
20 30 3b 0a 0a 20 77 68 69 6c 65 28 20 67 72 61
70 68 5f 66 6f 75 6e 64 20 3d 3d 20 30 29 0a 20
7b 0a 0a 20 20 6e 75 6d 65 64 67 65 73 20 3d 20
30 3b 0a 0a 20 20 66 6f 72 28 6c 3d 30 3b 20 6c
3c 20 56 45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a
20 20 7b 0a 20 20 20 20 66 6f 72 28 6d 3d 30 3b
20 6d 20 3c 20 56 45 52 54 45 58 3b 20 6d 2b 2b
29 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 61 64
6a 6d 61 74 5b 6c 5d 5b 6d 5d 20 3d 20 30 3b 0a
20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 77 68 69
6c 65 28 6e 75 6d 65 64 67 65 73 20 3c 20 74 6f
74 61 6c 5f 65 64 67 65 73 20 29 0a 20 20 7b 0a
20 20 20 20 72 75 31 20 3d 20 28 28 6c 6f 6e 67
20 64 6f 75 62 6c 65 29 20 4b 49 53 53 29 2f 28
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 6d 61
78 69 5f 75 6c 6c 29 3b 0a 20 20 20 20 63 6f 31
20 3d 20 66 6c 6f 6f 72 6c 28 72 75 31 2a 28 28
6c 6f 6e 67 20 64 6f 75 62 6c 65 29 56 45 52 54
45 58 29 29 3b 0a 20 20 20 20 72 75 32 20 3d 20
28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 4b
49 53 53 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62
6c 65 29 20 6d 61 78 69 5f 75 6c 6c 29 3b 0a 20
20 20 20 63 6f 32 20 3d 20 66 6c 6f 6f 72 6c 28
72 75 32 2a 28 28 6c 6f 6e 67 20 64 6f 75 62 6c
65 29 56 45 52 54 45 58 29 29 3b 0a 20 20 20 20
69 66 28 20 28 63 6f 31 3c 56 45 52 54 45 58 29
20 26 26 20 28 63 6f 32 3c 56 45 52 54 45 58 29
29 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 69 66
28 63 6f 31 20 21 3d 20 63 6f 32 29 0a 20 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 20 69 66 28
61 64 6a 6d 61 74 5b 63 6f 31 5d 5b 63 6f 32 5d
20 3d 3d 20 30 29 0a 20 20 20 20 20 20 20 20 7b
0a 20 20 20 20 20 20 20 20 20 20 61 64 6a 6d 61
74 5b 63 6f 31 5d 5b 63 6f 32 5d 20 3d 20 31 3b
0a 20 20 20 20 20 20 20 20 20 20 61 64 6a 6d 61
74 5b 63 6f 32 5d 5b 63 6f 31 5d 20 3d 20 31 3b
0a 20 20 20 20 20 20 20 20 20 20 6e 75 6d 65 64
67 65 73 20 3d 20 6e 75 6d 65 64 67 65 73 20 2b
20 31 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20
20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a
0a 2f 2a 2a 2a 20 63 6f 6d 70 75 74 65 20 64 65
67 72 65 65 73 5b 5d 20 2a 2a 2a 2f 0a 2f 2a 2a
2a 20 65 61 63 68 20 33 20 6f 72 20 6d 6f 72 65
20 2a 2a 2a 2f 0a 0a 20 20 64 65 67 72 65 65 5f
74 65 73 74 5f 70 61 73 73 65 64 20 3d 20 31 3b
0a 0a 20 20 66 6f 72 28 6c 3d 30 3b 20 6c 3c 20
56 45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a 20 20
7b 0a 20 20 20 20 64 65 67 72 65 65 73 5b 6c 5d
20 3d 20 30 3b 0a 0a 20 20 20 20 66 6f 72 28 6d
3d 30 3b 20 6d 20 3c 20 56 45 52 54 45 58 3b 20
6d 2b 2b 29 0a 20 20 20 20 7b 0a 20 20 20 20 20
20 20 64 65 67 72 65 65 73 5b 6c 5d 20 3d 20 64
65 67 72 65 65 73 5b 6c 5d 20 2b 20 61 64 6a 6d
61 74 5b 6c 5d 5b 6d 5d 3b 0a 20 20 20 20 7d 0a
0a 20 20 20 20 69 66 28 20 64 65 67 72 65 65 73
5b 6c 5d 20 3c 20 33 20 29 0a 20 20 20 20 7b 0a
20 20 20 20 20 20 64 65 67 72 65 65 5f 74 65 73
74 5f 70 61 73 73 65 64 20 3d 20 30 3b 0a 20 20
20 20 7d 0a 20 20 7d 0a 0a 20 20 69 66 28 64 65
67 72 65 65 5f 74 65 73 74 5f 70 61 73 73 65 64
20 3d 3d 20 31 29 0a 20 20 7b 0a 20 20 20 20 67
72 61 70 68 5f 66 6f 75 6e 64 20 3d 20 31 3b 20
0a 20 20 7d 0a 0a 20 7d 0a 0a 0a 0a 0a 0a 0a 20
20 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 6d 61
78 5f 68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f
73 74 65 70 20 3d 20 30 3b 20 20 0a 0a 0a 0a 0a
77 68 69 6c 65 28 20 63 6f 75 6e 74 20 3c 20 31
20 29 0a 7b 0a 20 20 73 6f 6c 75 74 69 6f 6e 5f
66 6f 75 6e 64 20 3d 20 30 3b 0a 0a 77 68 69 6c
65 28 20 30 20 3d 3d 20 73 6f 6c 75 74 69 6f 6e
5f 66 6f 75 6e 64 20 29 0a 7b 0a 20 20 66 6f 72
28 20 6a 3d 30 3b 20 6a 3c 20 56 45 52 54 45 58
20 3b 20 6a 2b 2b 29 0a 20 20 7b 0a 20 20 20 20
72 61 6e 64 78 20 3d 20 4b 49 53 53 3b 0a 20 20
20 20 78 63 6f 6f 72 64 5b 6a 5d 20 3d 20 28 28
6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 72 61 6e
64 78 29 2f 28 28 6c 6f 6e 67 20 64 6f 75 62 6c
65 29 20 6d 61 78 69 5f 75 6c 6c 29 3b 0a 20 20
20 20 78 63 6f 6f 72 64 5b 6a 5d 20 3d 20 73 63
61 6c 69 6e 67 2a 78 63 6f 6f 72 64 5b 6a 5d 3b
0a 20 20 20 20 72 61 6e 64 78 20 3d 20 4b 49 53
53 3b 0a 20 20 20 20 79 63 6f 6f 72 64 5b 6a 5d
20 3d 20 28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65
29 20 72 61 6e 64 78 29 2f 28 28 6c 6f 6e 67 20
64 6f 75 62 6c 65 29 20 6d 61 78 69 5f 75 6c 6c
29 3b 0a 20 20 20 20 79 63 6f 6f 72 64 5b 6a 5d
20 3d 20 73 63 61 6c 69 6e 67 2a 79 63 6f 6f 72
64 5b 6a 5d 3b 0a 20 20 7d 0a 20 20 66 6f 72 28
6c 3d 30 3b 20 6c 3c 20 56 45 52 54 45 58 20 3b
20 6c 2b 2b 29 0a 20 20 7b 0a 20 20 20 20 20 66
6f 72 28 6d 3d 30 3b 20 6d 3c 20 6c 20 3b 20 6d
2b 2b 29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20
20 20 20 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d
20 3d 20 28 78 63 6f 6f 72 64 5b 6c 5d 2d 78 63
6f 6f 72 64 5b 6d 5d 29 2a 28 78 63 6f 6f 72 64
5b 6c 5d 2d 78 63 6f 6f 72 64 5b 6d 5d 29 3b 0a
20 20 20 20 20 20 20 20 64 6d 61 74 72 69 78 5b
6c 5d 5b 6d 5d 20 3d 20 64 6d 61 74 72 69 78 5b
6c 5d 5b 6d 5d 20 2b 20 0a 28 79 63 6f 6f 72 64
5b 6c 5d 2d 79 63 6f 6f 72 64 5b 6d 5d 29 2a 28
79 63 6f 6f 72 64 5b 6c 5d 2d 79 63 6f 6f 72 64
5b 6d 5d 29 3b 0a 20 20 20 20 20 20 20 20 64 6d
61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d 20 73 71
72 74 6c 28 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d
5d 29 3b 0a 20 20 20 20 20 7d 0a 20 20 20 20 20
66 6f 72 28 6d 3d 20 6c 2b 31 20 3b 20 6d 3c 20
56 45 52 54 45 58 20 3b 20 6d 2b 2b 29 0a 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 20 64 6d 61
74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d 20 64 6d 61
74 72 69 78 5b 6d 5d 5b 6c 5d 3b 0a 20 20 20 20
20 7d 0a 20 20 7d 0a 20 20 64 69 66 66 20 3d 20
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 30 3b
0a 20 20 66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56
45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a 20 20 7b
0a 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d 3c
20 6c 3b 20 6d 2b 2b 29 0a 20 20 20 20 7b 0a 20
20 20 20 20 20 69 66 28 20 31 20 3d 3d 20 61 64
6a 6d 61 74 5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 20 64 69 66
66 20 3d 20 64 69 66 66 20 2b 20 66 61 62 73 6c
28 6f 6e 65 2d 64 6d 61 74 72 69 78 5b 6c 5d 5b
6d 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20
20 7d 0a 20 20 7d 0a 0a 20 20 64 69 66 66 31 20
3d 20 64 69 66 66 3b 0a 0a 0a 0a 20 20 69 66 28
64 69 66 66 20 3c 20 64 69 66 66 5f 72 65 63 6f
72 64 29 0a 20 20 7b 0a 20 20 20 20 73 6f 6c 75
74 69 6f 6e 5f 66 6f 75 6e 64 20 3d 20 31 3b 0a
0a 20 20 20 20 66 6f 72 28 20 6a 20 3d 30 3b 20
6a 3c 20 56 45 52 54 45 58 20 3b 20 6a 2b 2b 29
0a 20 20 20 20 7b 0a 20 20 20 20 20 20 78 67 6f
6f 64 5b 6a 5d 20 3d 20 78 63 6f 6f 72 64 5b 6a
5d 3b 0a 20 20 20 20 20 20 79 67 6f 6f 64 5b 6a
5d 20 3d 20 79 63 6f 6f 72 64 5b 6a 5d 3b 0a 20
20 20 20 7d 0a 20 20 7d 0a 7d 0a 0a 2f 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 0a
20 20 20 20 20 20 20 20 20 20 68 61 76 65 20 73
6f 6c 75 74 69 6f 6e 20 2e 2e 2e 0a 0a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a
20 20 68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f
66 6c 61 67 20 3d 20 30 3b 0a 20 20 71 75 69 74
20 3d 20 30 3b 0a 20 20 63 6f 75 6e 74 20 3d 20
63 6f 75 6e 74 20 2b 20 31 3b 0a 0a 0a 0a 0a 2f
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 20
42 45 47 49 4e 20 49 54 45 52 41 54 49 4f 4e 53
20 54 4f 20 43 4f 4e 56 45 52 47 45 20 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 0a 66
6f 72 28 20 6b 20 3d 20 30 3b 20 6b 20 3c 20 4e
55 4d 53 54 45 50 53 20 3b 20 6b 2b 2b 29 0a 7b
0a 0a 20 20 0a 0a 0a 20 20 20 69 66 28 20 71 75
69 74 20 3d 3d 20 31 29 0a 20 20 20 7b 0a 20 20
20 20 20 62 72 65 61 6b 3b 0a 20 20 20 7d 0a 0a
20 20 20 69 66 28 20 28 6b 2b 31 29 20 3c 20 31
30 30 29 0a 20 20 20 7b 0a 20 20 20 20 20 43 20
3d 20 28 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29
20 33 34 35 29 2f 28 28 6c 6f 6e 67 20 64 6f 75
62 6c 65 29 20 31 30 30 30 29 3b 0a 20 20 20 7d
0a 20 20 20 65 6c 73 65 0a 20 20 20 7b 0a 20 20
20 20 20 43 20 3d 20 28 28 6c 6f 6e 67 20 64 6f
75 62 6c 65 29 20 42 20 29 2f 28 28 6c 6f 6e 67
20 64 6f 75 62 6c 65 29 20 31 30 30 30 29 3b 0a
20 20 20 7d 0a 0a 20 20 20 66 6f 72 28 6c 3d 30
3b 20 6c 3c 20 56 45 52 54 45 58 20 3b 20 6c 2b
2b 29 0a 20 20 20 7b 0a 20 20 20 20 20 66 6f 72
28 6d 3d 30 3b 20 6d 3c 20 6c 20 3b 20 6d 2b 2b
29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d 20
28 78 67 6f 6f 64 5b 6c 5d 2d 78 67 6f 6f 64 5b
6d 5d 29 2a 28 78 67 6f 6f 64 5b 6c 5d 2d 78 67
6f 6f 64 5b 6d 5d 29 3b 0a 20 20 20 20 20 20 20
64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d 20
64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 2b 20
0a 28 79 67 6f 6f 64 5b 6c 5d 2d 79 67 6f 6f 64
5b 6d 5d 29 2a 28 79 67 6f 6f 64 5b 6c 5d 2d 79
67 6f 6f 64 5b 6d 5d 29 3b 0a 20 20 20 20 20 20
20 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d
20 73 71 72 74 6c 28 64 6d 61 74 72 69 78 5b 6c
5d 5b 6d 5d 29 3b 0a 20 20 20 20 20 7d 0a 20 20
20 20 20 66 6f 72 28 6d 3d 20 6c 2b 31 20 3b 20
6d 3c 20 56 45 52 54 45 58 20 3b 20 6d 2b 2b 29
0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 64
6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 20 3d 20 64
6d 61 74 72 69 78 5b 6d 5d 5b 6c 5d 3b 0a 20 20
20 20 20 7d 0a 20 20 20 7d 0a 0a 0a 20 20 20 69
66 28 20 28 6b 2b 31 29 20 3d 3d 20 32 35 20 29
0a 20 20 20 7b 0a 20 20 20 20 20 64 69 66 66 20
3d 20 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20
30 3b 0a 20 20 20 20 20 66 6f 72 28 6c 3d 30 3b
20 6c 3c 20 56 45 52 54 45 58 20 3b 20 6c 2b 2b
29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
66 6f 72 28 6d 3d 30 3b 20 6d 3c 20 6c 3b 20 6d
2b 2b 29 0a 20 20 20 20 20 20 20 7b 0a 20 20 20
20 20 20 20 20 20 69 66 28 20 31 20 3d 3d 20 61
64 6a 6d 61 74 5b 6c 5d 5b 6d 5d 20 29 0a 20 20
20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
20 20 20 20 64 69 66 66 20 3d 20 64 69 66 66 20
2b 20 66 61 62 73 6c 28 6f 6e 65 2d 64 6d 61 74
72 69 78 5b 6c 5d 5b 6d 5d 29 3b 0a 20 20 20 20
20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 7d 0a
20 20 20 20 20 7d 0a 0a 20 20 20 20 20 64 69 66
66 32 35 20 3d 20 64 69 66 66 3b 20 0a 0a 20 20
20 20 20 69 66 28 20 64 69 66 66 20 3e 20 4d 41
58 44 49 46 46 41 54 32 35 20 29 0a 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 71 75 69 74 20 3d
20 31 3b 0a 20 20 20 20 20 7d 0a 20 20 20 7d 0a
0a 0a 20 20 20 69 66 28 20 28 6b 2b 31 29 20 3d
3d 20 35 30 20 29 0a 20 20 20 7b 0a 20 20 20 20
20 64 69 66 66 20 3d 20 28 6c 6f 6e 67 20 64 6f
75 62 6c 65 29 20 30 3b 0a 20 20 20 20 20 66 6f
72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52 54 45 58
20 3b 20 6c 2b 2b 29 0a 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d
3c 20 6c 3b 20 6d 2b 2b 29 0a 20 20 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 20 20 69 66 28 20
31 20 3d 3d 20 61 64 6a 6d 61 74 5b 6c 5d 5b 6d
5d 20 29 0a 20 20 20 20 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 20 20 20 20 64 69 66 66 20 3d
20 64 69 66 66 20 2b 20 66 61 62 73 6c 28 6f 6e
65 2d 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 29
3b 0a 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20
20 20 20 20 7d 0a 20 20 20 20 20 7d 0a 0a 20 20
20 20 20 64 69 66 66 35 30 20 3d 20 64 69 66 66
3b 20 0a 0a 20 20 20 20 20 69 66 28 20 64 69 66
66 20 3e 20 4d 41 58 44 49 46 46 41 54 35 30 20
29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
71 75 69 74 20 3d 20 31 3b 0a 20 20 20 20 20 7d
0a 20 20 20 7d 0a 0a 0a 20 20 20 69 66 28 20 28
6b 2b 31 29 20 3d 3d 20 31 30 30 20 29 0a 20 20
20 7b 0a 20 20 20 20 20 64 69 66 66 20 3d 20 28
6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 30 3b 0a
20 20 20 20 20 66 6f 72 28 6c 3d 30 3b 20 6c 3c
20 56 45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a 20
20 20 20 20 7b 0a 20 20 20 20 20 20 20 66 6f 72
28 6d 3d 30 3b 20 6d 3c 20 6c 3b 20 6d 2b 2b 29
0a 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 20 20 69 66 28 20 31 20 3d 3d 20 61 64 6a 6d
61 74 5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20 20 20
20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 20 20
20 64 69 66 66 20 3d 20 64 69 66 66 20 2b 20 66
61 62 73 6c 28 6f 6e 65 2d 64 6d 61 74 72 69 78
5b 6c 5d 5b 6d 5d 29 3b 0a 20 20 20 20 20 20 20
20 20 7d 0a 20 20 20 20 20 20 20 7d 0a 20 20 20
20 20 7d 0a 0a 20 20 20 20 20 64 69 66 66 31 30
30 20 3d 20 64 69 66 66 3b 0a 0a 0a 0a 20 20 20
20 20 69 66 28 20 64 69 66 66 20 3e 20 4d 41 58
44 49 46 46 41 54 31 30 30 20 29 0a 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 71 75 69 74 20 3d
20 31 3b 0a 20 20 20 20 20 7d 0a 20 20 20 7d 0a
0a 0a 0a 0a 0a 0a 0a 0a 0a 20 20 20 69 66 28 20
28 6b 2b 31 29 20 3d 3d 20 32 30 30 20 29 0a 20
20 20 7b 0a 20 20 20 20 20 64 69 66 66 20 3d 20
28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20 30 3b
0a 20 20 20 20 20 66 6f 72 28 6c 3d 30 3b 20 6c
3c 20 56 45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a
20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 66 6f
72 28 6d 3d 30 3b 20 6d 3c 20 6c 3b 20 6d 2b 2b
29 0a 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20
20 20 20 20 69 66 28 20 31 20 3d 3d 20 61 64 6a
6d 61 74 5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20 20
20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 20
20 20 64 69 66 66 20 3d 20 64 69 66 66 20 2b 20
66 61 62 73 6c 28 6f 6e 65 2d 64 6d 61 74 72 69
78 5b 6c 5d 5b 6d 5d 29 3b 0a 20 20 20 20 20 20
20 20 20 7d 0a 20 20 20 20 20 20 20 7d 0a 20 20
20 20 20 7d 0a 0a 20 20 20 20 20 64 69 66 66 32
30 30 20 3d 20 64 69 66 66 3b 0a 0a 0a 0a 20 20
20 20 20 69 66 28 20 64 69 66 66 20 3e 20 4d 41
58 44 49 46 46 41 54 32 30 30 20 29 0a 20 20 20
20 20 7b 0a 20 20 20 20 20 20 20 71 75 69 74 20
3d 20 31 3b 0a 20 20 20 20 20 7d 0a 20 20 20 7d
0a 0a 0a 0a 0a 0a 0a 20 20 20 69 66 28 20 28 6b
2b 31 29 20 3d 3d 20 34 30 30 20 29 0a 20 20 20
7b 0a 20 20 20 20 20 64 69 66 66 20 3d 20 28 6c
6f 6e 67 20 64 6f 75 62 6c 65 29 20 30 3b 0a 20
20 20 20 20 66 6f 72 28 6c 3d 30 3b 20 6c 3c 20
56 45 52 54 45 58 20 3b 20 6c 2b 2b 29 0a 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 66 6f 72 28
6d 3d 30 3b 20 6d 3c 20 6c 3b 20 6d 2b 2b 29 0a
20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
20 20 69 66 28 20 31 20 3d 3d 20 61 64 6a 6d 61
74 5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20 20 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20
64 69 66 66 20 3d 20 64 69 66 66 20 2b 20 66 61
62 73 6c 28 6f 6e 65 2d 64 6d 61 74 72 69 78 5b
6c 5d 5b 6d 5d 29 3b 0a 20 20 20 20 20 20 20 20
20 7d 0a 20 20 20 20 20 20 20 7d 0a 20 20 20 20
20 7d 0a 0a 20 20 20 20 20 64 69 66 66 34 30 30
20 3d 20 64 69 66 66 3b 0a 0a 0a 0a 20 20 20 20
20 69 66 28 20 64 69 66 66 20 3e 20 4d 41 58 44
49 46 46 41 54 34 30 30 20 29 0a 20 20 20 20 20
7b 0a 20 20 20 20 20 20 20 71 75 69 74 20 3d 20
31 3b 0a 20 20 20 20 20 7d 0a 20 20 20 7d 0a 0a
0a 0a 0a 20 20 20 69 66 28 20 28 6b 2b 31 29 20
3d 3d 20 38 30 30 20 29 0a 20 20 20 7b 0a 20 20
20 20 20 64 69 66 66 20 3d 20 28 6c 6f 6e 67 20
64 6f 75 62 6c 65 29 20 30 3b 0a 20 20 20 20 20
66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52 54
45 58 20 3b 20 6c 2b 2b 29 0a 20 20 20 20 20 7b
0a 20 20 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b
20 6d 3c 20 6c 3b 20 6d 2b 2b 29 0a 20 20 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 20 20 69 66
28 20 31 20 3d 3d 20 61 64 6a 6d 61 74 5b 6c 5d
5b 6d 5d 20 29 0a 20 20 20 20 20 20 20 20 20 7b
0a 20 20 20 20 20 20 20 20 20 20 20 64 69 66 66
20 3d 20 64 69 66 66 20 2b 20 66 61 62 73 6c 28
6f 6e 65 2d 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d
5d 29 3b 0a 20 20 20 20 20 20 20 20 20 7d 0a 20
20 20 20 20 20 20 7d 0a 20 20 20 20 20 7d 0a 0a
20 20 20 20 20 64 69 66 66 38 30 30 20 3d 20 64
69 66 66 3b 0a 0a 0a 0a 20 20 20 20 20 69 66 28
20 64 69 66 66 20 3e 20 4d 41 58 44 49 46 46 41
54 38 30 30 20 29 0a 20 20 20 20 20 7b 0a 20 20
20 20 20 20 20 71 75 69 74 20 3d 20 31 3b 0a 20
20 20 20 20 7d 0a 0a 20 20 20 7d 0a 0a 0a 0a 0a
20 20 20 69 66 28 20 28 6b 2b 31 29 20 3d 3d 20
31 32 30 30 20 29 0a 20 20 20 7b 0a 20 20 20 20
20 64 69 66 66 20 3d 20 28 6c 6f 6e 67 20 64 6f
75 62 6c 65 29 20 30 3b 0a 20 20 20 20 20 66 6f
72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52 54 45 58
20 3b 20 6c 2b 2b 29 0a 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d
3c 20 6c 3b 20 6d 2b 2b 29 0a 20 20 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 20 20 69 66 28 20
31 20 3d 3d 20 61 64 6a 6d 61 74 5b 6c 5d 5b 6d
5d 20 29 0a 20 20 20 20 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 20 20 20 20 64 69 66 66 20 3d
20 64 69 66 66 20 2b 20 66 61 62 73 6c 28 6f 6e
65 2d 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 29
3b 0a 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20
20 20 20 20 7d 0a 20 20 20 20 20 7d 0a 0a 20 20
20 20 20 64 69 66 66 31 32 30 30 20 3d 20 64 69
66 66 3b 0a 0a 0a 0a 20 20 20 20 20 69 66 28 20
64 69 66 66 20 3e 20 4d 41 58 44 49 46 46 41 54
31 32 30 30 20 29 0a 20 20 20 20 20 7b 0a 20 20
20 20 20 20 20 71 75 69 74 20 3d 20 31 3b 0a 20
20 20 20 20 7d 0a 0a 20 20 20 7d 0a 0a 0a 0a 0a
0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a
0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 20 20 20 64
69 66 66 20 3d 20 28 6c 6f 6e 67 20 64 6f 75 62
6c 65 29 20 30 3b 0a 0a 20 20 20 66 6f 72 28 6c
3d 30 3b 20 6c 3c 20 56 45 52 54 45 58 20 3b 20
6c 2b 2b 29 0a 20 20 20 7b 0a 20 20 20 20 20 66
6f 72 28 6d 3d 30 3b 20 6d 3c 20 6c 3b 20 6d 2b
2b 29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 69 66 28 20 31 20 3d 3d 20 61 64 6a 6d 61 74
5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20 20 20 20 20
7b 0a 20 20 20 20 20 20 20 20 20 64 69 66 66 20
3d 20 64 69 66 66 20 2b 20 66 61 62 73 6c 28 6f
6e 65 2d 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d
29 3b 0a 20 20 20 20 20 20 20 7d 0a 20 20 20 20
20 7d 0a 20 20 20 7d 0a 0a 20 20 20 69 66 28 20
28 64 69 66 66 20 3c 20 6d 61 78 64 69 66 66 61
74 34 30 30 29 20 26 26 20 28 68 61 73 5f 63 6f
6e 76 65 72 67 65 64 5f 66 6c 61 67 20 3d 3d 20
30 29 20 29 0a 20 20 20 7b 0a 20 20 20 20 20 68
61 73 5f 63 6f 6e 76 65 72 67 65 64 5f 66 6c 61
67 20 3d 20 31 3b 0a 20 20 20 20 20 68 61 73 5f
63 6f 6e 76 65 72 67 65 64 5f 73 74 65 70 20 3d
20 6b 2b 31 3b 0a 0a 20 20 20 20 20 69 66 28 20
68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f 73 74
65 70 20 3e 20 6d 61 78 5f 68 61 73 5f 63 6f 6e
76 65 72 67 65 64 5f 73 74 65 70 20 29 0a 20 20
20 20 20 7b 0a 20 20 20 20 20 20 20 6d 61 78 5f
68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f 73 74
65 70 20 3d 20 68 61 73 5f 63 6f 6e 76 65 72 67
65 64 5f 73 74 65 70 3b 0a 20 20 20 20 20 7d 0a
0a 20 20 20 20 20 71 75 69 74 20 3d 20 31 3b 0a
0a 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 0a 20 20 69 6e 74
20 69 73 5f 73 69 6e 67 75 6c 61 72 3b 0a 0a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2f 0a 0a 0a 20 20 20 20 20 69 73
5f 73 69 6e 67 75 6c 61 72 20 3d 20 30 3b 0a 0a
20 20 20 20 20 66 6f 72 28 6c 3d 30 3b 20 6c 20
3c 20 56 45 52 54 45 58 3b 20 6c 2b 2b 29 0a 20
20 20 20 20 7b 0a 20 20 20 20 20 20 20 66 6f 72
28 6d 20 3d 20 30 3b 20 6d 20 3c 20 6c 3b 20 6d
2b 2b 29 0a 20 20 20 20 20 20 20 7b 0a 20 20 20
20 20 20 20 20 20 69 66 28 20 64 6d 61 74 72 69
78 5b 6c 5d 5b 6d 5d 20 3c 20 65 70 73 69 6c 6f
6e 20 29 0a 20 20 20 20 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 20 20 20 20 69 73 5f 73 69 6e
67 75 6c 61 72 20 3d 20 31 3b 0a 20 20 20 20 20
20 20 20 20 7d 0a 20 20 20 20 20 20 20 7d 0a 20
20 20 20 20 7d 0a 0a 0a 20 20 20 20 20 20 20 69
66 28 20 69 73 5f 73 69 6e 67 75 6c 61 72 20 3d
3d 20 30 29 0a 20 20 20 20 20 20 20 7b 0a 0a 20
20 20 20 20 20 20 20 20 74 6f 74 61 6c 5f 66 69
6e 64 73 20 3d 20 74 6f 74 61 6c 5f 66 69 6e 64
73 20 2b 20 31 3b 0a 0a 20 20 20 20 20 20 20 20
20 69 66 28 20 28 64 69 66 66 32 35 20 3e 20 72
65 63 5f 64 69 66 66 32 35 29 20 26 26 20 28 68
61 73 5f 63 6f 6e 76 65 72 67 65 64 5f 73 74 65
70 20 3e 20 32 35 29 29 0a 20 20 20 20 20 20 20
20 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 72
65 63 5f 64 69 66 66 32 35 20 3d 20 64 69 66 66
32 35 3b 0a 20 20 20 20 20 20 20 20 20 7d 0a 0a
20 20 20 20 20 20 20 20 20 69 66 28 20 28 64 69
66 66 35 30 20 3e 20 72 65 63 5f 64 69 66 66 35
30 29 20 26 26 20 28 68 61 73 5f 63 6f 6e 76 65
72 67 65 64 5f 73 74 65 70 20 3e 20 35 30 29 29
0a 20 20 20 20 20 20 20 20 20 7b 0a 20 20 20 20
20 20 20 20 20 20 20 72 65 63 5f 64 69 66 66 35
30 20 3d 20 64 69 66 66 35 30 3b 0a 20 20 20 20
20 20 20 20 20 7d 0a 0a 0a 20 20 20 20 20 20 20
20 20 69 66 28 20 28 64 69 66 66 31 30 30 20 3e
20 72 65 63 5f 64 69 66 66 31 30 30 29 20 20 26
26 20 28 68 61 73 5f 63 6f 6e 76 65 72 67 65 64
5f 73 74 65 70 20 3e 20 31 30 30 29 29 0a 20 20
20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20
20 20 20 20 72 65 63 5f 64 69 66 66 31 30 30 20
3d 20 64 69 66 66 31 30 30 3b 0a 20 20 20 20 20
20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 20
69 66 28 20 64 69 66 66 31 20 3e 20 72 65 63 5f
64 69 66 66 31 29 0a 20 20 20 20 20 20 20 20 20
7b 0a 20 20 20 20 20 20 20 20 20 20 20 72 65 63
5f 64 69 66 66 31 20 3d 20 64 69 66 66 31 3b 0a
20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20
20 20 20 20 20 69 66 28 20 28 64 69 66 66 32 30
30 20 3e 20 72 65 63 5f 64 69 66 66 32 30 30 29
20 26 26 20 28 68 61 73 5f 63 6f 6e 76 65 72 67
65 64 5f 73 74 65 70 20 3e 20 32 30 30 29 20 29
0a 20 20 20 20 20 20 20 20 20 7b 0a 20 20 20 20
20 20 20 20 20 20 20 72 65 63 5f 64 69 66 66 32
30 30 20 3d 20 64 69 66 66 32 30 30 3b 0a 20 20
20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20
20 20 20 69 66 28 20 28 64 69 66 66 34 30 30 20
3e 20 72 65 63 5f 64 69 66 66 34 30 30 20 29 20
26 26 20 28 68 61 73 5f 63 6f 6e 76 65 72 67 65
64 5f 73 74 65 70 20 3e 20 34 30 30 29 29 0a 20
20 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 20 20 20 20 72 65 63 5f 64 69 66 66 34 30 30
20 3d 20 64 69 66 66 34 30 30 3b 0a 20 20 20 20
20 20 20 20 20 7d 0a 0a 0a 20 20 20 20 20 20 20
20 20 69 66 28 20 28 64 69 66 66 38 30 30 20 3e
20 72 65 63 5f 64 69 66 66 38 30 30 29 20 26 26
20 28 68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f
73 74 65 70 20 3e 20 38 30 30 29 29 0a 20 20 20
20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20
20 20 20 72 65 63 5f 64 69 66 66 38 30 30 20 3d
20 64 69 66 66 38 30 30 3b 0a 20 20 20 20 20 20
20 20 20 7d 0a 0a 0a 20 20 20 20 20 20 20 20 20
69 66 28 20 28 64 69 66 66 31 32 30 30 20 3e 20
72 65 63 5f 64 69 66 66 31 32 30 30 29 20 20 26
26 20 28 68 61 73 5f 63 6f 6e 76 65 72 67 65 64
5f 73 74 65 70 20 3e 20 31 32 30 30 29 29 0a 20
20 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 20 20 20 20 72 65 63 5f 64 69 66 66 31 32 30
30 20 3d 20 64 69 66 66 31 32 30 30 3b 0a 20 20
20 20 20 20 20 20 20 7d 0a 0a 0a 0a 0a 0a 0a 23
69 66 64 65 66 20 56 45 52 42 4f 53 45 0a 0a 0a
20 20 66 6f 72 28 6c 20 3d 20 30 3b 20 6c 3c 20
56 45 52 54 45 58 3b 20 6c 2b 2b 29 0a 20 20 7b
0a 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d 3c
20 56 45 52 54 45 58 3b 20 6d 2b 2b 29 0a 20 20
20 20 7b 0a 20 20 20 20 20 20 70 6f 73 74 5f 61
64 6a 6d 61 74 5b 6c 5d 5b 6d 5d 20 3d 20 30 3b
0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 0a 20 20 70
72 6f 62 61 62 6c 65 5f 75 6e 69 74 5f 6c 65 6e
67 74 68 73 20 3d 20 30 3b 0a 0a 20 20 66 6f 72
28 6c 20 3d 20 30 3b 20 6c 3c 56 45 52 54 45 58
3b 20 6c 2b 2b 29 0a 20 20 7b 0a 20 20 20 20 66
6f 72 28 6d 20 3d 20 30 3b 20 6d 20 3c 20 6c 3b
20 6d 2b 2b 29 0a 20 20 20 20 7b 0a 20 20 20 20
20 20 69 66 28 20 66 61 62 73 6c 28 64 6d 61 74
72 69 78 5b 6c 5d 5b 6d 5d 2d 6f 6e 65 29 20 3c
20 65 70 73 69 6c 6f 6e 20 29 0a 20 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 20 70 72 6f 62 61
62 6c 65 5f 75 6e 69 74 5f 6c 65 6e 67 74 68 73
2b 2b 20 3b 0a 20 20 20 20 20 20 20 20 70 6f 73
74 5f 61 64 6a 6d 61 74 5b 6c 5d 5b 6d 5d 20 3d
20 31 3b 0a 20 20 20 20 20 20 20 20 70 6f 73 74
5f 61 64 6a 6d 61 74 5b 6d 5d 5b 6c 5d 20 3d 20
31 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d
0a 20 20 7d 0a 0a 0a 0a 0a 0a 0a 2f 2a 2a 2a 2a
20 20 54 45 53 54 20 70 6f 73 74 5f 61 64 6a 6d
61 74 5b 5d 5b 5d 20 66 6f 72 20 33 2d 63 6f 6c
6f 72 69 6e 67 20 42 45 47 49 4e 20 20 20 20 2a
2a 2a 2a 2f 0a 0a 20 20 6e 5f 63 6f 6c 6f 72 73
20 3d 20 33 3b 0a 20 20 63 6f 6c 6f 72 69 6e 67
5f 66 6f 75 6e 64 20 3d 20 30 3b 0a 0a 0a 20 20
66 6f 72 28 76 30 20 3d 20 30 3b 20 76 30 3c 20
31 20 3b 20 76 30 2b 2b 29 0a 20 20 7b 0a 20 20
66 6f 72 28 76 31 20 3d 20 30 3b 20 76 31 3c 20
32 20 3b 20 76 31 2b 2b 29 0a 20 20 7b 0a 20 20
66 6f 72 28 76 32 20 3d 20 30 3b 20 76 32 3c 20
6e 5f 63 6f 6c 6f 72 73 20 3b 20 76 32 2b 2b 29
0a 20 20 7b 0a 20 20 66 6f 72 28 76 33 20 3d 20
30 3b 20 76 33 3c 20 6e 5f 63 6f 6c 6f 72 73 20
3b 20 76 33 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f
72 28 76 34 20 3d 20 30 3b 20 76 34 3c 20 6e 5f
63 6f 6c 6f 72 73 20 3b 20 76 34 2b 2b 29 0a 20
20 7b 0a 20 20 66 6f 72 28 76 35 20 3d 20 30 3b
20 76 35 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20
76 35 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28
76 36 20 3d 20 30 3b 20 76 36 3c 20 6e 5f 63 6f
6c 6f 72 73 20 3b 20 76 36 2b 2b 29 0a 20 20 7b
0a 20 20 66 6f 72 28 76 37 20 3d 20 30 3b 20 76
37 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76 37
2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28 76 38
20 3d 20 30 3b 20 76 38 3c 20 6e 5f 63 6f 6c 6f
72 73 20 3b 20 76 38 2b 2b 29 0a 20 20 7b 0a 20
20 66 6f 72 28 76 39 20 3d 20 30 3b 20 76 39 3c
20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76 39 2b 2b
29 0a 20 20 7b 0a 20 20 66 6f 72 28 76 31 30 20
3d 20 30 3b 20 76 31 30 3c 20 6e 5f 63 6f 6c 6f
72 73 20 3b 20 76 31 30 2b 2b 29 0a 20 20 7b 0a
20 20 66 6f 72 28 76 31 31 20 3d 20 30 3b 20 76
31 31 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76
31 31 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28
76 31 32 20 3d 20 30 3b 20 76 31 32 3c 20 6e 5f
63 6f 6c 6f 72 73 20 3b 20 76 31 32 2b 2b 29 0a
20 20 7b 0a 0a 0a 0a 0a 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 30 5d 20 3d 20 76 30 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 31 5d 20 3d 20 76 31 3b
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 32 5d 20 3d
20 76 32 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
33 5d 20 3d 20 76 33 3b 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 34 5d 20 3d 20 76 34 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 35 5d 20 3d 20 76 35 3b
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 36 5d 20 3d
20 76 36 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
37 5d 20 3d 20 76 37 3b 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 38 5d 20 3d 20 76 38 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 39 5d 20 3d 20 76 39 3b
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 31 30 5d 20
3d 20 76 31 30 3b 0a 20 20 20 20 63 6f 6c 6f 72
73 5b 31 31 5d 20 3d 20 76 31 31 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 31 32 5d 20 3d 20 76 31
32 3b 0a 0a 0a 0a 0a 20 20 20 20 68 61 73 5f 66
61 69 6c 65 64 20 3d 20 30 3b 0a 0a 20 20 20 20
66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52 54
45 58 20 3b 20 6c 2b 2b 29 0a 20 20 20 20 7b 0a
20 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d
20 3c 20 6c 3b 20 6d 2b 2b 29 0a 20 20 20 20 20
20 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20 28
70 6f 73 74 5f 61 64 6a 6d 61 74 5b 6c 5d 5b 6d
5d 3d 3d 31 29 26 26 20 28 63 6f 6c 6f 72 73 5b
6c 5d 3d 3d 63 6f 6c 6f 72 73 5b 6d 5d 29 20 29
0a 20 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20
20 20 20 20 20 68 61 73 5f 66 61 69 6c 65 64 20
3d 20 31 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20
20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 0a 20 20
20 20 69 66 28 20 68 61 73 5f 66 61 69 6c 65 64
20 3d 3d 20 30 20 29 0a 20 20 20 20 7b 0a 20 20
20 20 20 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f 75
6e 64 20 3d 20 31 3b 0a 20 20 20 20 7d 0a 0a 20
20 20 20 69 66 28 20 63 6f 6c 6f 72 69 6e 67 5f
66 6f 75 6e 64 20 3d 3d 20 31 20 29 0a 20 20 20
20 7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a
20 20 20 20 7d 0a 0a 0a 0a 20 20 7d 0a 0a 20 20
20 20 69 66 28 20 63 6f 6c 6f 72 69 6e 67 5f 66
6f 75 6e 64 20 3d 3d 20 31 20 29 0a 20 20 20 20
7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20
20 20 20 7d 0a 0a 0a 20 20 7d 0a 0a 20 20 20 20
69 66 28 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f 75
6e 64 20 3d 3d 20 31 20 29 0a 20 20 20 20 7b 0a
20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20
20 7d 0a 0a 0a 20 20 7d 0a 20 20 20 20 69 66 28
20 63 6f 6c 6f 72 69 6e 67 5f 66 6f 75 6e 64 20
3d 3d 20 31 20 29 0a 20 20 20 20 7b 0a 20 20 20
20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a
0a 0a 20 20 7d 0a 0a 20 20 20 20 69 66 28 20 63
6f 6c 6f 72 69 6e 67 5f 66 6f 75 6e 64 20 3d 3d
20 31 20 29 0a 20 20 20 20 7b 0a 20 20 20 20 20
20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 0a 0a
20 20 7d 0a 0a 20 20 20 20 69 66 28 20 63 6f 6c
6f 72 69 6e 67 5f 66 6f 75 6e 64 20 3d 3d 20 31
20 29 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 62
72 65 61 6b 3b 0a 20 20 20 20 7d 0a 0a 20 20 7d
0a 0a 20 20 20 20 69 66 28 20 63 6f 6c 6f 72 69
6e 67 5f 66 6f 75 6e 64 20 3d 3d 20 31 20 29 0a
20 20 20 20 7b 0a 20 20 20 20 20 20 62 72 65 61
6b 3b 0a 20 20 20 20 7d 0a 0a 0a 20 20 7d 0a 0a
20 20 20 20 69 66 28 20 63 6f 6c 6f 72 69 6e 67
5f 66 6f 75 6e 64 20 3d 3d 20 31 20 29 0a 20 20
20 20 7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b
0a 20 20 20 20 7d 0a 0a 20 20 7d 0a 0a 20 20 20
20 69 66 28 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f
75 6e 64 20 3d 3d 20 31 20 29 0a 20 20 20 20 7b
0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20
20 20 7d 0a 0a 20 20 7d 0a 0a 20 20 20 20 69 66
28 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f 75 6e 64
20 3d 3d 20 31 20 29 0a 20 20 20 20 7b 0a 20 20
20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d
0a 0a 0a 20 20 7d 0a 0a 20 20 20 20 69 66 28 20
63 6f 6c 6f 72 69 6e 67 5f 66 6f 75 6e 64 20 3d
3d 20 31 20 29 0a 20 20 20 20 7b 0a 20 20 20 20
20 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 0a
20 20 7d 0a 0a 20 20 20 20 69 66 28 20 63 6f 6c
6f 72 69 6e 67 5f 66 6f 75 6e 64 20 3d 3d 20 31
20 29 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 62
72 65 61 6b 3b 0a 20 20 20 20 7d 0a 0a 0a 20 20
7d 0a 0a 20 20 20 20 69 66 28 20 63 6f 6c 6f 72
69 6e 67 5f 66 6f 75 6e 64 20 3d 3d 20 31 20 29
0a 20 20 20 20 7b 0a 20 20 20 20 20 20 62 72 65
61 6b 3b 0a 20 20 20 20 7d 0a 0a 0a 20 20 7d 0a
0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 20 20
69 66 28 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f 75
6e 64 20 3d 3d 20 31 20 29 0a 20 20 7b 0a 20 20
20 20 69 73 5f 33 63 6f 6c 6f 72 61 62 6c 65 20
3d 20 31 3b 0a 20 20 7d 0a 20 20 65 6c 73 65 0a
20 20 7b 0a 20 20 20 20 69 73 5f 33 63 6f 6c 6f
72 61 62 6c 65 20 3d 20 30 3b 0a 20 20 7d 0a 0a
0a 0a 2f 2a 2a 2a 2a 20 20 54 45 53 54 20 70 6f
73 74 5f 61 64 6a 6d 61 74 5b 5d 5b 5d 20 66 6f
72 20 33 2d 63 6f 6c 6f 72 69 6e 67 20 45 4e 44
20 20 20 2a 2a 2a 2a 2f 0a 0a 0a 0a 0a 0a 20 20
70 72 69 6e 74 66 28 22 61 64 6a 61 63 65 6e 63
79 20 6d 61 74 72 69 78 3a 5c 6e 22 29 3b 0a 0a
20 20 66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56 45
52 54 45 58 20 3b 20 6c 2b 2b 29 0a 20 20 7b 0a
20 20 20 20 66 6f 72 28 6d 3d 30 3b 20 6d 20 3c
20 56 45 52 54 45 58 3b 20 6d 2b 2b 29 0a 20 20
20 20 7b 0a 20 20 20 20 20 20 70 72 69 6e 74 66
28 22 25 64 20 22 2c 20 61 64 6a 6d 61 74 5b 6c
5d 5b 6d 5d 29 20 3b 0a 20 20 20 20 7d 0a 20 20
20 20 70 72 69 6e 74 66 28 22 5c 6e 22 29 3b 0a
20 20 7d 0a 0a 20 20 70 72 69 6e 74 66 28 22 5c
6e 22 29 3b 0a 0a 0a 20 20 70 72 69 6e 74 66 28
22 70 6f 73 74 20 61 64 6a 61 63 65 6e 63 79 20
6d 61 74 72 69 78 3a 5c 6e 22 29 3b 0a 0a 20 20
66 6f 72 28 6c 3d 30 3b 20 6c 3c 20 56 45 52 54
45 58 20 3b 20 6c 2b 2b 29 0a 20 20 7b 0a 20 20
20 20 66 6f 72 28 6d 3d 30 3b 20 6d 20 3c 20 56
45 52 54 45 58 3b 20 6d 2b 2b 29 0a 20 20 20 20
7b 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 22
25 64 20 22 2c 20 70 6f 73 74 5f 61 64 6a 6d 61
74 5b 6c 5d 5b 6d 5d 29 20 3b 0a 20 20 20 20 7d
0a 20 20 20 20 70 72 69 6e 74 66 28 22 5c 6e 22
29 3b 0a 20 20 7d 0a 0a 0a 0a 0a 0a 0a 20 20 6e
5f 63 6f 6c 6f 72 73 20 3d 20 34 3b 0a 20 20 63
6f 6c 6f 72 69 6e 67 5f 66 6f 75 6e 64 20 3d 20
30 3b 0a 20 20 6e 75 6d 5f 34 5f 63 6f 6c 6f 72
69 6e 67 73 20 3d 20 30 3b 0a 20 20 66 6f 72 28
76 30 20 3d 20 30 3b 20 76 30 3c 20 6e 5f 63 6f
6c 6f 72 73 20 3b 20 76 30 2b 2b 29 0a 20 20 7b
0a 20 20 66 6f 72 28 76 31 20 3d 20 30 3b 20 76
31 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76 31
2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28 76 32
20 3d 20 30 3b 20 76 32 3c 20 6e 5f 63 6f 6c 6f
72 73 20 3b 20 76 32 2b 2b 29 0a 20 20 7b 0a 20
20 66 6f 72 28 76 33 20 3d 20 30 3b 20 76 33 3c
20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76 33 2b 2b
29 0a 20 20 7b 0a 20 20 66 6f 72 28 76 34 20 3d
20 30 3b 20 76 34 3c 20 6e 5f 63 6f 6c 6f 72 73
20 3b 20 76 34 2b 2b 29 0a 20 20 7b 0a 20 20 66
6f 72 28 76 35 20 3d 20 30 3b 20 76 35 3c 20 6e
5f 63 6f 6c 6f 72 73 20 3b 20 76 35 2b 2b 29 0a
20 20 7b 0a 20 20 66 6f 72 28 76 36 20 3d 20 30
3b 20 76 36 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b
20 76 36 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72
28 76 37 20 3d 20 30 3b 20 76 37 3c 20 6e 5f 63
6f 6c 6f 72 73 20 3b 20 76 37 2b 2b 29 0a 20 20
7b 0a 20 20 66 6f 72 28 76 38 20 3d 20 30 3b 20
76 38 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76
38 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28 76
39 20 3d 20 30 3b 20 76 39 3c 20 6e 5f 63 6f 6c
6f 72 73 20 3b 20 76 39 2b 2b 29 0a 20 20 7b 0a
20 20 66 6f 72 28 76 31 30 20 3d 20 30 3b 20 76
31 30 3c 20 6e 5f 63 6f 6c 6f 72 73 20 3b 20 76
31 30 2b 2b 29 0a 20 20 7b 0a 20 20 66 6f 72 28
76 31 31 20 3d 20 30 3b 20 76 31 31 3c 20 6e 5f
63 6f 6c 6f 72 73 20 3b 20 76 31 31 2b 2b 29 0a
20 20 7b 0a 20 20 66 6f 72 28 76 31 32 20 3d 20
30 3b 20 76 31 32 3c 20 6e 5f 63 6f 6c 6f 72 73
20 3b 20 76 31 32 2b 2b 29 0a 20 20 7b 0a 0a 0a
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 30 5d 20 3d
20 76 30 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
31 5d 20 3d 20 76 31 3b 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 32 5d 20 3d 20 76 32 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 33 5d 20 3d 20 76 33 3b
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 34 5d 20 3d
20 76 34 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
35 5d 20 3d 20 76 35 3b 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 36 5d 20 3d 20 76 36 3b 0a 20 20 20
20 63 6f 6c 6f 72 73 5b 37 5d 20 3d 20 76 37 3b
0a 20 20 20 20 63 6f 6c 6f 72 73 5b 38 5d 20 3d
20 76 38 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
39 5d 20 3d 20 76 39 3b 0a 20 20 20 20 63 6f 6c
6f 72 73 5b 31 30 5d 20 3d 20 76 31 30 3b 0a 20
20 20 20 63 6f 6c 6f 72 73 5b 31 31 5d 20 3d 20
76 31 31 3b 0a 20 20 20 20 63 6f 6c 6f 72 73 5b
31 32 5d 20 3d 20 76 31 32 3b 0a 0a 0a 0a 0a 20
20 20 20 68 61 73 5f 66 61 69 6c 65 64 20 3d 20
30 3b 0a 20 20 20 20 66 6f 75 72 5f 63 6f 6c 6f
75 72 69 6e 67 5f 66 61 69 6c 65 64 20 3d 20 30
3b 0a 0a 20 20 20 20 66 6f 72 28 6c 3d 30 3b 20
6c 3c 20 56 45 52 54 45 58 20 3b 20 6c 2b 2b 29
0a 20 20 20 20 7b 0a 20 20 20 20 20 20 66 6f 72
28 6d 3d 30 3b 20 6d 20 3c 20 6c 3b 20 6d 2b 2b
29 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 20 69 66 28 20 28 70 6f 73 74 5f 61 64 6a 6d
61 74 5b 6c 5d 5b 6d 5d 3d 3d 31 29 26 26 20 28
63 6f 6c 6f 72 73 5b 6c 5d 3d 3d 63 6f 6c 6f 72
73 5b 6d 5d 29 20 29 0a 20 20 20 20 20 20 20 20
7b 0a 20 20 20 20 20 20 20 20 20 20 68 61 73 5f
66 61 69 6c 65 64 20 3d 20 31 3b 0a 20 20 20 20
20 20 20 20 20 20 66 6f 75 72 5f 63 6f 6c 6f 75
72 69 6e 67 5f 66 61 69 6c 65 64 20 3d 20 31 3b
0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20
20 20 20 69 66 28 20 66 6f 75 72 5f 63 6f 6c 6f
75 72 69 6e 67 5f 66 61 69 6c 65 64 20 3d 3d 20
31 29 0a 20 20 20 20 20 20 20 20 7b 0a 20 20 20
20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20
20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a
0a 20 20 20 20 20 20 69 66 28 20 66 6f 75 72 5f
63 6f 6c 6f 75 72 69 6e 67 5f 66 61 69 6c 65 64
20 3d 3d 20 31 29 0a 20 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20
20 20 20 20 7d 0a 20 20 20 20 7d 0a 0a 0a 0a 20
20 20 20 69 66 28 20 68 61 73 5f 66 61 69 6c 65
64 20 3d 3d 20 30 20 29 0a 20 20 20 20 7b 0a 20
20 20 20 20 20 63 6f 6c 6f 72 69 6e 67 5f 66 6f
75 6e 64 20 3d 20 31 3b 0a 20 20 20 20 20 20 6e
75 6d 5f 34 5f 63 6f 6c 6f 72 69 6e 67 73 2b 2b
20 3b 20 20 20 20 20 20 0a 20 20 20 20 7d 0a 20
20 7d 0a 20 20 7d 0a 20 20 7d 0a 20 20 7d 0a 20
20 7d 0a 20 20 7d 0a 20 20 7d 0a 20 20 7d 0a 20
20 7d 0a 20 20 7d 0a 20 20 7d 0a 20 20 7d 0a 20
20 7d 0a 0a 0a 0a 20 20 6e 75 6d 5f 34 5f 63 6f
6c 6f 72 69 6e 67 73 5f 6d 6f 64 5f 32 34 20 3d
20 6e 75 6d 5f 34 5f 63 6f 6c 6f 72 69 6e 67 73
25 32 34 20 3b 0a 0a 20 20 63 6f 75 6e 74 5f 34
5f 63 6f 6c 6f 72 69 6e 67 73 20 3d 20 6e 75 6d
5f 34 5f 63 6f 6c 6f 72 69 6e 67 73 2f 32 34 3b
0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 20 20 20 20 20
70 72 69 6e 74 66 28 22 74 6f 74 61 6c 5f 66 69
6e 64 73 20 3d 20 25 64 5c 6e 22 2c 20 74 6f 74
61 6c 5f 66 69 6e 64 73 29 3b 0a 20 20 20 20 20
70 72 69 6e 74 66 28 22 54 65 73 74 73 20 63 6f
75 6e 74 20 3d 20 25 64 20 20 22 2c 20 63 6f 75
6e 74 29 3b 0a 20 20 20 20 20 70 72 69 6e 74 66
28 22 68 61 73 5f 63 6f 6e 76 65 72 67 65 64 5f
73 74 65 70 20 3d 20 25 64 20 20 22 2c 20 68 61
73 5f 63 6f 6e 76 65 72 67 65 64 5f 73 74 65 70
29 3b 0a 20 20 20 20 20 70 72 69 6e 74 66 28 22
6d 61 78 5f 68 61 73 5f 63 6f 6e 76 65 72 67 65
64 5f 73 74 65 70 20 3d 20 25 64 5c 6e 22 2c 20
6d 61 78 5f 68 61 73 5f 63 6f 6e 76 65 72 67 65
64 5f 73 74 65 70 29 3b 0a 20 20 20 20 20 70 72
69 6e 74 66 28 22 72 65 63 5f 64 69 66 66 31 20
3d 20 25 2e 36 4c 66 5c 6e 22 2c 20 72 65 63 5f
64 69 66 66 31 29 3b 0a 20 20 20 20 20 70 72 69
6e 74 66 28 22 72 65 63 5f 64 69 66 66 32 35 20
3d 20 25 2e 36 4c 66 5c 6e 22 2c 20 72 65 63 5f
64 69 66 66 32 35 29 3b 0a 20 20 20 20 20 70 72
69 6e 74 66 28 22 72 65 63 5f 64 69 66 66 35 30
20 3d 20 25 2e 36 4c 66 5c 6e 22 2c 20 72 65 63
5f 64 69 66 66 35 30 29 3b 0a 20 20 20 20 20 70
72 69 6e 74 66 28 22 72 65 63 5f 64 69 66 66 31
30 30 20 3d 20 25 2e 36 4c 66 5c 6e 22 2c 20 72
65 63 5f 64 69 66 66 31 30 30 29 3b 0a 20 20 20
20 20 70 72 69 6e 74 66 28 22 72 65 63 5f 64 69
66 66 32 30 30 20 3d 20 25 2e 36 4c 66 5c 6e 22
2c 20 72 65 63 5f 64 69 66 66 32 30 30 29 3b 0a
20 20 20 20 20 70 72 69 6e 74 66 28 22 72 65 63
5f 64 69 66 66 34 30 30 20 3d 20 25 2e 36 4c 66
5c 6e 22 2c 20 72 65 63 5f 64 69 66 66 34 30 30
29 3b 0a 20 20 20 20 20 70 72 69 6e 74 66 28 22
72 65 63 5f 64 69 66 66 38 30 30 20 3d 20 25 2e
31 36 4c 66 5c 6e 22 2c 20 72 65 63 5f 64 69 66
66 38 30 30 29 3b 0a 20 20 20 20 20 70 72 69 6e
74 66 28 22 72 65 63 5f 64 69 66 66 31 32 30 30
20 3d 20 25 2e 31 36 4c 66 5c 6e 22 2c 20 72 65
63 5f 64 69 66 66 31 32 30 30 29 3b 0a 20 20 20
20 20 70 72 69 6e 74 66 28 22 70 72 6f 62 61 62
6c 65 5f 75 6e 69 74 5f 6c 65 6e 67 74 68 73 20
3d 20 25 64 5c 6e 22 2c 20 70 72 6f 62 61 62 6c
65 5f 75 6e 69 74 5f 6c 65 6e 67 74 68 73 29 3b
0a 0a 0a 0a 20 20 20 20 20 70 72 69 6e 74 66 28
22 67 72 61 70 68 20 69 73 20 33 2d 63 6f 6c 6f
72 61 62 6c 65 3a 22 29 3b 0a 20 20 20 20 20 69
66 28 69 73 5f 33 63 6f 6c 6f 72 61 62 6c 65 20
3d 3d 20 31 29 0a 20 20 20 20 20 7b 0a 20 20 20
20 20 20 20 70 72 69 6e 74 66 28 22 79 65 73 2e
20 20 20 22 29 3b 0a 20 20 20 20 20 7d 0a 20 20
20 20 20 65 6c 73 65 0a 20 20 20 20 20 7b 0a 20
20 20 20 20 20 20 70 72 69 6e 74 66 28 22 6e 6f
2e 20 20 20 22 29 3b 0a 20 20 20 20 20 7d 0a 0a
0a 0a 20 20 20 20 20 70 72 69 6e 74 66 28 22 63
6f 75 6e 74 5f 34 5f 63 6f 6c 6f 72 69 6e 67 73
20 3d 20 25 64 5c 6e 22 2c 20 63 6f 75 6e 74 5f
34 5f 63 6f 6c 6f 72 69 6e 67 73 29 3b 0a 20 20
20 20 20 70 72 69 6e 74 66 28 22 6e 75 6d 5f 34
5f 63 6f 6c 6f 72 69 6e 67 73 5f 6d 6f 64 5f 32
34 20 3d 20 25 64 5c 6e 22 2c 20 6e 75 6d 5f 34
5f 63 6f 6c 6f 72 69 6e 67 73 5f 6d 6f 64 5f 32
34 29 3b 0a 0a 0a 0a 20 20 20 20 20 70 72 69 6e
74 66 28 22 4d 61 74 72 69 78 20 6f 66 20 64 69
73 74 61 6e 63 65 73 20 76 65 72 74 65 78 20 74
6f 20 76 65 72 74 65 78 3a 5c 6e 22 29 3b 0a 20
20 20 20 20 70 72 69 6e 74 66 28 22 20 20 22 29
3b 0a 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20
6d 3c 56 45 52 54 45 58 3b 20 6d 2b 2b 29 0a 20
20 20 20 20 7b 0a 20 20 20 20 20 20 20 70 72 69
6e 74 66 28 22 20 20 20 25 63 20 20 22 2c 20 61
6c 70 68 61 62 65 74 5b 6d 5d 29 3b 0a 20 20 20
20 20 7d 0a 20 20 20 20 20 70 72 69 6e 74 66 28
22 5c 6e 22 29 3b 0a 20 20 20 20 20 66 6f 72 28
6c 3d 30 3b 20 6c 3c 20 56 45 52 54 45 58 20 3b
20 6c 2b 2b 29 0a 20 20 20 20 20 7b 0a 20 20 20
20 20 20 20 70 72 69 6e 74 66 28 22 25 63 20 22
2c 20 61 6c 70 68 61 62 65 74 5b 6c 5d 29 3b 0a
20 20 20 20 20 20 20 66 6f 72 28 6d 3d 30 3b 20
6d 3c 20 56 45 52 54 45 58 20 3b 20 6d 2b 2b 29
0a 20 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 20 20 70 72 69 6e 74 66 28 22 25 2e 33 4c 66
20 22 2c 20 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d
5d 29 3b 0a 20 20 20 20 20 20 20 7d 0a 20 20 20
20 20 20 20 70 72 69 6e 74 66 28 22 5c 6e 22 29
3b 0a 20 20 20 20 20 7d 0a 20 20 20 20 0a 20 20
20 20 20 70 72 69 6e 74 66 28 22 5c 6e 22 29 3b
0a 20 20 20 20 20 66 66 6c 75 73 68 28 73 74 64
6f 75 74 29 3b 0a 0a 0a 0a 0a 0a 0a 23 65 6e 64
69 66 20 0a 0a 20 20 20 20 20 20 20 7d 0a 0a 0a
20 20 20 7d 0a 0a 0a 20 20 20 66 6f 72 28 6c 3d
30 3b 20 6c 3c 20 56 45 52 54 45 58 20 3b 20 6c
2b 2b 29 0a 20 20 20 7b 0a 20 20 20 20 20 66 6f
72 63 65 73 5b 6c 5d 5b 30 5d 20 3d 20 28 6c 6f
6e 67 20 64 6f 75 62 6c 65 29 20 30 3b 0a 20 20
20 20 20 66 6f 72 63 65 73 5b 6c 5d 5b 31 5d 20
3d 20 28 6c 6f 6e 67 20 64 6f 75 62 6c 65 29 20
30 3b 0a 0a 20 20 20 20 20 66 6f 72 28 6d 3d 30
3b 20 6d 3c 20 56 45 52 54 45 58 20 3b 20 6d 2b
2b 29 0a 20 20 20 20 20 7b 0a 20 20 20 20 20 20
20 69 66 28 20 31 20 3d 3d 20 61 64 6a 6d 61 74
5b 6c 5d 5b 6d 5d 20 29 0a 20 20 20 20 20 20 20
7b 0a 20 20 20 20 20 20 20 20 20 76 65 63 74 6f
72 5b 30 5d 20 3d 20 78 67 6f 6f 64 5b 6d 5d 2d
78 67 6f 6f 64 5b 6c 5d 3b 0a 20 20 20 20 20 20
20 20 20 76 65 63 74 6f 72 5b 31 5d 20 3d 20 79
67 6f 6f 64 5b 6d 5d 2d 79 67 6f 6f 64 5b 6c 5d
3b 0a 20 20 20 20 20 20 20 20 20 76 65 63 74 6f
72 5b 30 5d 20 3d 20 76 65 63 74 6f 72 5b 30 5d
2f 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 3b 0a
20 20 20 20 20 20 20 20 20 76 65 63 74 6f 72 5b
31 5d 20 3d 20 76 65 63 74 6f 72 5b 31 5d 2f 64
6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 3b 0a 20 20
20 20 20 20 20 20 20 76 65 63 74 6f 72 5b 30 5d
20 3d 20 76 65 63 74 6f 72 5b 30 5d 2a 43 3b 0a
20 20 20 20 20 20 20 20 20 76 65 63 74 6f 72 5b
31 5d 20 3d 20 76 65 63 74 6f 72 5b 31 5d 2a 43
3b 0a 20 20 20 20 20 20 20 20 20 76 65 63 74 6f
72 5b 30 5d 20 3d 20 76 65 63 74 6f 72 5b 30 5d
2a 28 64 6d 61 74 72 69 78 5b 6c 5d 5b 6d 5d 2d
6f 6e 65 29 3b 0a 20 20 20 20 20 20 20 20 20 76
65 63 74 6f 72 5b 31 5d 20 3d 20 76 65 63 74 6f
72 5b 31 5d 2a 28 64 6d 61 74 72 69 78 5b 6c 5d
5b 6d 5d 2d 6f 6e 65 29 3b 0a 0a 20 20 20 20 20
20 20 20 20 66 6f 72 63 65 73 5b 6c 5d 5b 30 5d
20 3d 20 66 6f 72 63 65 73 5b 6c 5d 5b 30 5d 20
2b 20 76 65 63 74 6f 72 5b 30 5d 3b 0a 20 20 20
20 20 20 20 20 20 66 6f 72 63 65 73 5b 6c 5d 5b
31 5d 20 3d 20 66 6f 72 63 65 73 5b 6c 5d 5b 31
5d 20 2b 20 76 65 63 74 6f 72 5b 31 5d 3b 0a 20
20 20 20 20 20 20 7d 0a 20 20 20 20 20 7d 0a 20
20 20 7d 0a 0a 20 20 20 66 6f 72 28 20 6a 20 3d
30 3b 20 6a 3c 20 56 45 52 54 45 58 20 3b 20 6a
2b 2b 29 0a 20 20 20 7b 0a 20 20 20 20 20 20 78
67 6f 6f 64 5b 6a 5d 20 3d 20 78 67 6f 6f 64 5b
6a 5d 20 2b 20 66 6f 72 63 65 73 5b 6a 5d 5b 30
5d 3b 0a 20 20 20 20 20 20 79 67 6f 6f 64 5b 6a
5d 20 3d 20 79 67 6f 6f 64 5b 6a 5d 20 2b 20 66
6f 72 63 65 73 5b 6a 5d 5b 31 5d 3b 0a 20 20 20
7d 0a 0a 0a 7d 0a 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 42 65
6c 6f 77 2c 20 20 70 6f 73 74 2d 63 6f 6e 76 65
72 67 65 6e 63 65 20 61 6c 67 6f 72 69 74 68 6d
20 6f 72 20 68 65 75 72 69 73 74 69 63 3a 0a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2f 0a 0a 0a 0a 0a 7d 0a 2f 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 0a 20 20 20 20 20 77 68 69
6c 65 28 20 63 6f 75 6e 74 20 3c 20 31 20 29 20
65 6e 64 20 42 6c 6f 63 6b 0a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2f 0a 0a 0a 7d 0a 2f 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 0a 65 6e 64 20 6f 66 20 77 68
69 6c 65 28 20 31 20 3d 3d 20 31 20 29 20 42 6c
6f 63 6b 20 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a
2a 2f 0a 0a 0a 0a 0a 20 20 72 65 74 75 72 6e 20
30 3b 0a 7d 0a 0a

 

Written by meditationatae

February 19, 2017 at 6:06 am

Posted in History

Possible unit distance graph with 13 vertices and 30 edges

The unit distance graph solver I wrote in the C programming language may have found a unit distance graph with 13 vertices, 30 edges of length one, chromatic number 4, and 212 4-colourings, up to permutation of the 4 colours, where there are 4! = 24 permutations of the colours, say, Red, Green, Blue, and Yellow.

Below, I give the 13×13 adjacency matrix for the vertices labelled A through M. Computations show that in the embedding of the 13-vertex graph into R^2, adjacent vertices are at distance 1.0 to within 1/(10^16). For now, it seems too hard for me to prove that the distances (edges) can be made equal to 1.0 exactly, judging from the rather complex figure I have on graph paper.

Now, for the adjacency matrix:

adjacency matrix, 13×13 :

A B C D E F G H I J K L M
A 0 0 1 0 0 1 1 0 1 0 0 1 0
B 0 0 0 1 1 0 1 0 0 0 0 0 0
C 1 0 0 0 1 0 0 1 0 1 0 1 0
D 0 1 0 0 1 1 0 0 0 0 0 1 1
E 0 1 1 1 0 1 0 0 0 1 0 0 0
F 1 0 0 1 1 0 0 0 1 0 0 0 0
G 1 1 0 0 0 0 0 1 1 0 1 0 0
H 0 0 1 0 0 0 1 0 0 1 1 0 0
I 1 0 0 0 0 1 1 0 0 1 0 0 1
J 0 0 1 0 1 0 0 1 1 0 0 0 1
K 0 0 0 0 0 0 1 1 0 0 0 1 1
L 1 0 1 1 0 0 0 0 0 0 1 0 1
M 0 0 0 1 0 0 0 0 1 1 1 1 0

Next, the list of the 30 edges in the graph :

AC
AF
AG
AI
AL
BD
BE
BG
CE
CH
CJ
CL
DE
DF
DL
DM
EF
EJ
FI
GH
GI
GK
HJ
HK
IJ
IM
JM
KL
KM
LM

When embedded in the plane, these edges have a lentgh between 1 – epsilon and 1 + epsilon, where epsilon = 1E-16 .

For graphing/plotting purposes, I scaled/multiplied by a factor of 8.0 the x and y coordinates of the embedding in the plane for the graph. Thus, in the plotting coordinates below, edges have lengths very close to 8.0 :

PLOT COORDINATES:
x: y:
A 11.19821919 13.25045231
B 5.32174392 12.81261277
C 3.72492760 16.10525751
D 12.79503551 9.95780756
E 11.53072355 17.85727053
F 19.00401514 15.00246532
G 8.81260900 5.61442821
H 1.33931741 8.46923342
I 16.61840495 7.36644123
J 9.14511336 10.22124644
K 2.60362937 0.56977044
L 4.98923956 8.20579454
M 10.40942532 2.32178346

These plotting coordinates are given to 8 decimals. Here they are to 18 decimals:

PLOT COORDINATES:
x: y:
A 11.198219191921061789 13.250452305406670937
B 5.321743918026219025 12.812612769849526509
C 3.724927600140764836 16.105257514913251721
D 12.795035509806516247 9.957807560342945618
E 11.530723548205223334 17.857270533466618027
F 19.004015139985520824 15.002465323960036954
G 8.812608999717104444 5.614428208348530141
H 1.339317407936807158 8.469233417855111156
I 16.618404947781563135 7.366441226901895712
J 9.145113356001265674 10.221246436408476720
K 2.603629369538099817 0.569770444731438857
L 4.989239561742057498 8.205794541789579483
M 10.409425317602558271 2.321783463284804645

Finally, a scan of a plot I did manually on graph paper :

 

feb18scan2

Written by meditationatae

February 19, 2017 at 2:38 am

Posted in History

new solver 13 vertices: minor source code edit…

After convergence to the unit distance graph equations (vertex to vertex distances are 1 to within 1E-15, according to the 13×13 adjacency matrix adjmat[][] ),

the solver checks that no two distinct vertices are “suspiciously close”, which is a good sign they are in fact superposed,what we call a “singular solution”: those are rejected.

After it’s checked that the real-variables solution is not singular, a check is made for distinct vertices that are at a distance “suspiciously close” to 1. When they are, even though the unit distance graph equations did not require it, it’s assumed they are in fact at unit distance, and an extra ‘1’ for “at unit distance” is added to post_adjmat[13][13], that was a ‘0’ in adjmat[13][13], the carrier of the unit distance equations.

 

The minor edit checks for the existence of 3-colorings of the graph with adjacency matrix “post adjacency matrix”, rather than the original adjacency matrix in adjmat[13][13].

 

Here are the first 2 “finds” :

adjacency matrix:
0 0 0 0 1 0 1 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 1 0 1 0 0 0 0 0 1 1
0 1 0 0 0 0 1 0 0 1 1 0 1
0 0 1 0 0 0 0 0 1 0 0 1 0
0 0 0 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0
0 0 1 0 1 0 0 1 1 0 0 0 0

post adjacency matrix:
0 0 0 0 1 0 1 1 0 0 0 0 1
0 0 0 0 1 1 1 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 1 0 1 0 0 0 0 0 1 1
0 1 0 0 0 0 1 0 0 1 1 1 1
0 0 1 0 0 0 0 0 1 0 0 1 0
0 0 0 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 1 1 1 1 0 0 0
1 0 1 0 1 0 0 1 1 0 0 0 0 // extra 1’s : more lengths very nearly ‘1’
total_finds = 1
Tests count = 1 has_converged_step = 1183 max_has_converged_step = 1183
rec_diff1 = 32.435776
rec_diff25 = 2.824074
rec_diff50 = 8.248026
rec_diff100 = 5.834537
rec_diff200 = 0.122107
rec_diff400 = 0.000153
rec_diff800 = 0.0000000002945205
rec_diff1200 = 0.0000000000000000
probable_unit_lengths = 26
graph is 3-colorable:yes. count_4_colorings = 838
num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M
A 0.000 1.731 1.732 2.000 1.000 0.966 1.000 1.000 2.000 2.646 1.693 1.733 1.000
B 1.731 0.000 1.730 2.644 1.000 1.000 1.000 1.998 1.000 2.000 1.712 1.732 0.998
C 1.732 1.730 0.000 1.000 2.000 1.034 0.998 1.000 0.998 1.000 0.039 0.002 1.000
D 2.000 2.644 1.000 0.000 2.646 1.751 1.730 1.000 1.998 1.731 1.000 0.998 1.732
E 1.000 1.000 2.000 2.646 0.000 0.967 1.002 1.732 1.733 2.647 1.967 2.002 1.000
F 0.966 1.000 1.034 1.751 0.967 0.000 0.040 1.000 1.034 1.772 1.000 1.035 0.039
G 1.000 1.000 0.998 1.730 1.002 0.040 0.000 0.998 1.000 1.732 0.965 1.000 0.002
H 1.000 1.998 1.000 1.000 1.732 1.000 0.998 0.000 1.731 2.000 0.966 1.000 1.000
I 2.000 1.000 0.998 1.998 1.733 1.034 1.000 1.731 0.000 1.000 1.000 1.000 1.000
J 2.646 2.000 1.000 1.731 2.647 1.772 1.732 2.000 1.000 0.000 1.034 1.000 1.733
K 1.693 1.712 0.039 1.000 1.967 1.000 0.965 0.966 1.000 1.034 0.000 0.040 0.967
L 1.733 1.732 0.002 0.998 2.002 1.035 1.000 1.000 1.000 1.000 0.040 0.000 1.002
M 1.000 0.998 1.000 1.732 1.000 0.039 0.002 1.000 1.000 1.733 0.967 1.002 0.000

adjacency matrix:
0 0 0 1 1 1 0 0 0 1 0 0 1
0 0 1 1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0 0 1 0
1 0 0 0 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 1
0 1 1 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 1 0 1
1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 1
0 0 0 1 1 0 1 0 0 0 0 0 0
1 0 0 0 1 0 1 0 1 0 1 0 0

post adjacency matrix:
0 1 0 1 1 1 0 0 0 1 0 0 1
1 0 1 1 0 0 0 1 0 1 1 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0 0 1 0
1 0 0 0 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 1 1 1
0 1 1 0 1 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 0 1
1 1 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 1 1 1 0 0 0 1
0 0 0 1 1 0 1 1 0 0 0 0 0
1 0 0 0 1 0 1 0 1 0 1 0 0
total_finds = 2
Tests count = 1 has_converged_step = 1382 max_has_converged_step = 1382
rec_diff1 = 32.435776
rec_diff25 = 10.906118
rec_diff50 = 12.382250
rec_diff100 = 13.752239
rec_diff200 = 0.122107
rec_diff400 = 0.000268
rec_diff800 = 0.0000000050855684
rec_diff1200 = 0.0000000000001208
probable_unit_lengths = 28
graph is 3-colorable:yes. count_4_colorings = 464
num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M
A 0.000 1.000 1.999 1.000 1.000 1.000 0.077 1.692 1.692 1.000 0.932 0.932 1.000
B 1.000 0.000 1.000 1.000 1.066 0.077 1.066 1.000 1.999 1.000 1.000 0.077 1.769
C 1.999 1.000 0.000 1.769 1.769 1.000 2.066 1.000 2.619 1.692 1.732 1.066 2.669
D 1.000 1.000 1.769 0.000 1.769 1.066 1.000 1.999 2.619 1.732 1.692 1.000 1.999
E 1.000 1.066 1.769 1.769 0.000 1.000 1.066 1.000 0.932 0.077 0.077 1.000 1.000
F 1.000 0.077 1.000 1.066 1.000 0.000 1.069 0.932 1.932 0.932 0.935 0.077 1.732
G 0.077 1.066 2.066 1.000 1.066 1.069 0.000 1.769 1.732 1.069 1.000 1.000 1.000
H 1.692 1.000 1.000 1.999 1.000 0.932 1.769 0.000 1.692 0.932 1.000 1.000 1.999
I 1.692 1.999 2.619 2.619 0.932 1.932 1.732 1.692 0.000 1.000 1.000 1.932 1.000
J 1.000 1.000 1.692 1.732 0.077 0.932 1.069 0.932 1.000 0.000 0.077 0.935 1.066
K 0.932 1.000 1.732 1.692 0.077 0.935 1.000 1.000 1.000 0.077 0.000 0.932 1.000
L 0.932 0.077 1.066 1.000 1.000 0.077 1.000 1.000 1.932 0.935 0.932 0.000 1.692
M 1.000 1.769 2.669 1.999 1.000 1.732 1.000 1.999 1.000 1.066 1.000 1.692 0.000

===

This means that the probable unit distance graphs with adjacency matrix  equal to the “post adjacency matrix” are 3-colorable.

Find 8 from previous program says the original adjacency matrix is not 3-colorable; hence by adding edges, neither is it 3-colorable. For the graph where we join  edges with distance extremely close to ‘1’, it finds  that it is 4-colorable in 212 ways, with 30 edges of probable length 1, up to permutation of the 4 colors.

To be declared “probable length 1”, a vertex to vertex distance must differ from 1 by at most 0.0000001 .

 

adjacency matrix:
0 0 1 0 0 1 1 0 1 0 0 0 0
0 0 0 1 1 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 1 0
0 1 0 0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 1 1 0 1 0 0
0 0 0 0 0 0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0 0 1 0 0 1
0 0 0 0 1 0 0 1 1 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 1 1
0 0 1 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 1 1 1 1 0

post adjacency matrix:
0 0 1 0 0 1 1 0 1 0 0 1 0
0 0 0 1 1 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 1 0 1 0
0 1 0 0 1 1 0 0 0 0 0 1 1
0 1 1 1 0 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 1 1 0 1 0 0
0 0 1 0 0 0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0 0 1 0 0 1
0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 1 1
1 0 1 1 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 1 1 1 1 0
total_finds = 8
Tests count = 1 has_converged_step = 1410 max_has_converged_step = 1410
rec_diff1 = 32.435776
rec_diff25 = 10.906118
rec_diff50 = 12.382250
rec_diff100 = 13.752239
rec_diff200 = 0.352660
rec_diff400 = 0.000585
rec_diff800 = 0.0000000246891323
rec_diff1200 = 0.0000000000010421
probable_unit_lengths = 30
graph is 3-colorable:no. count_4_colorings = 212
num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M
A 0.000 0.737 1.000 0.457 0.577 1.000 1.000 1.370 1.000 0.457 1.915 1.000 1.370
B 0.737 0.000 0.457 1.000 1.000 1.732 1.000 0.737 1.568 0.577 1.568 0.577 1.457
C 1.000 0.457 0.000 1.370 1.000 1.915 1.457 1.000 1.947 1.000 1.947 1.000 1.915
D 0.457 1.000 1.370 0.000 1.000 1.000 0.737 1.444 0.577 0.457 1.732 1.000 1.000
E 0.577 1.000 1.000 1.000 0.000 1.000 1.568 1.732 1.457 1.000 2.432 1.457 1.947
F 1.000 1.732 1.915 1.000 1.000 0.000 1.732 2.354 1.000 1.370 2.731 1.947 1.915
G 1.000 1.000 1.457 0.737 1.568 1.732 0.000 1.000 1.000 0.577 1.000 0.577 0.457
H 1.370 0.737 1.000 1.444 1.732 2.354 1.000 0.000 1.915 1.000 1.000 0.457 1.370
I 1.000 1.568 1.947 0.577 1.457 1.000 1.000 1.915 0.000 1.000 1.947 1.457 1.000
J 0.457 0.577 1.000 0.457 1.000 1.370 0.577 1.000 1.000 0.000 1.457 0.577 1.000
K 1.915 1.568 1.947 1.732 2.432 2.731 1.000 1.000 1.947 1.457 0.000 1.000 1.000
L 1.000 0.577 1.000 1.000 1.457 1.947 0.577 0.457 1.457 0.577 1.000 0.000 1.000
M 1.370 1.457 1.915 1.000 1.947 1.915 0.457 1.370 1.000 1.000 1.000 1.000 0.000

 

So, this one is not 3-colorable, and is 4-colorable although not in a huge number of ways (I think).

 

Source code after edit:

udgraph13_solverff9789nu97b.c

in

/home/david/graphs/golomb18

 

#include <stdio.h>
#include <math.h>
#define NUMSTEPS 2500
#define MAXDIFFAT100 ((long double) 18)/((long double) 1)
#define MAXDIFFAT50 ((long double) 18)/((long double) 1)
#define MAXDIFFAT25 ((long double) 40)/((long double) 1)
#define MAXDIFFAT1 ((long double) 40)/((long double) 1)
#define MAXDIFFAT200 ((long double) 96)/((long double) 10)
#define MAXDIFFAT400 ((long double) 67)/((long double) 1000)
#define MAXDIFFAT800 ((long double) 79)/((long double) 100000000)
#define MAXDIFFAT1200 ((long double) 84)/((long double)1000000000000)
#define VERBOSE
#define VERTEX 13

/**********************************************
rec_diff1 = 28.852841 40.0
rec_diff25 = 39.668785 40.0
rec_diff50 = 17.967935 18.0
rec_diff100 = 17.856958 18.0
rec_diff200 = 9.573263 9.6
rec_diff400 = 0.066982 6.7e-2
rec_diff800 = 0.0000007832212564 7.9e-7
rec_diff1200 = 0.0000000000839841 8.4e-11
************************************************/

static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )
/********************* README SECTION *********************

10-point non-singular solutions to the unit
graph problem are found numerically at a rate of
57.9 solutions per second on a dual core Athlon
5000+ processor.

The solutions are expected to be isometric as a
10-point metric space to the soltion depicted in
the graph in my blog post :

Sketch of 10-vertex unit distance graph, 2013
at URL =

meditationatae.wordpress.com/2017/02/06/sketch-of-10-vertex-unit-distance-graph-2013
The sci dot math posts:

mathforum.org/kb/message.jspa?messageID=10081388

and earlier:

mathforum.org/kb/message.jspa?messageID=10074716

This solver for a particular graph has been optimized
to run in as little time as possible for the given graph,
decribed by the 10×10 adjacency matrix.

To compile, I type:

$ gcc -lm -O3 -o udgraph_solver201a.out udgraph_solver201a.c

at the shell command line in Linux.

The executable is then udgraph_solver201a.out .
In C pre-processor terms, if VERBOSE is defined by
a pre-processor directive,
Number-Sign define VERBOSE
say on line 7 above after the other
Number-sign defines,
then the solution count and the 10×10 matrix of vertex to vertex
distances for a solution will be printed.

As above VERBOSE is not defined, the program will run with
minimal output until it finishes after about 9 minutes
with my system.

This README is based on file
Slash home slash david slash graphs slash golomb6
slash udgraph_solver201a dot c,

will serve to write the local file:

Slash home slash david slash graphs slash golomb6
slash udgraph_solver301a dot c ,

and will go by the Moniker or alias
“unit distance graph solver draft 101”

a hexadecimal dump will be posted to my blog

meditationatae.wordpress.com
David Bernier

********************* README END *************************/

int main(void)
{
unsigned long long i,cng=123456789987654321LL, xs=362436069362436069LL;
unsigned long long randx;
int B;
int j;
int k;
int quit;
int is_singular;
int graph_found;
int total_edges;
int degree_test_passed;
int l, m;
int n, p;
int has_k4;
int is_3colorable;
int count;
int total_finds;
int probable_unit_lengths;
int solution_found;
int coloring_found;
char alphabet[VERTEX];
unsigned long long maxi_ull;
long double xcoord[VERTEX];
long double diff;
long double diff25;
long double diff50;
long double diff100;
long double diff200;
long double diff400;
long double diff800;
long double diff1200;
long double diff1;
long double rec_diff25;
long double rec_diff50;
long double rec_diff100;
long double rec_diff200;
long double rec_diff400;
long double rec_diff800;
long double rec_diff1200;
long double rec_diff1;
long double ru1;
long double ru2;
long double epsilon;
int co1;
int co2;
int colors[VERTEX];
int num_4_colorings;
int num_4_colorings_mod_24;
int count_4_colorings;
int n_colors;
int degrees[VERTEX];
int v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12;
int has_failed;
int numedges;
long double diff_record;
long double maxdiffat400;
long double one;
long double ycoord[VERTEX];
long double forces[VERTEX][2];
long double C;
long double vector[2];
long double xgood[VERTEX];
long double ygood[VERTEX];
int four_colouring_failed;
int has_converged_flag;
int has_converged_step;
int max_has_converged_step;
long double scaling;
long double dmatrix[VERTEX][VERTEX];
int adjmat[VERTEX][VERTEX];
int post_adjmat[VERTEX][VERTEX];
/************************************************************************

udgraph_solver3401a.c : user 22m50.198s w/
MAXDIFFAT100 ((long double) 38)/((long double) 1)

newtestz746a.out 345 : 8m 34.631s for 30k solns. , using -O3
newtestz745a.out 340 : 8m 35s for 30000 solutions, with -O3
newtestz585a.c: 8m 51s for 30000 solutions, using -O3 optimization
newtest83a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest81a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest73a.c: 8m 49s for 30000 solutions, using -O3 optimization option
newtest66a.c: 10m 25s for 30000 solutions, using -O3 optimization option
newtest65a.c: 11m 30s for 30000 solutions
newtest64a.c: 11m 30s for 30000 solutions
newtest63a.c: 11m 33s for 30000 solutions
newtest62a.c: 11m 33s for 30000 solutions
newtest61a.c: 3m 51s for 10000 solutions
newtest57a.c: 6m 27s for 10000 solutions
newtest56a.c: 6m 37s for 10000 solutions
newtest55a.c: 6m 43s for 10000 solutions
newtest54a.c: 6m 48s for 10000 solutions
newtest53a.c: 6m 46s for 10000 solutions
newtest48a.c: 62 seconds for 1600 solutions
newtest47a.c: 14 seconds for 400 solutions
newtest46a.c: 66 seconds for 400 solutions
newtest39a.c: 67 seconds for 400 solutions
newtest37a.c: 70 seconds for 400 solutions
newtest35a.c: 79 seconds for 400 solutions
newtest34a.c: 72 seconds for 400 solutions
newtest33a.c: 91 seconds for 400 solutions
newtest30a.c: 16 seconds for 100 solutions
newtest29a.c: 18 seconds for 100 solutions
newtest28a.c: 25 seconds for 100 solutions
newtest27a.c: 50 seconds for 100 solutions
newtest26a.c: 99 seconds for 100 solutions
newtest25a.c: 3000 solutions per hour
for 100 solutions, 2 minutes …
808 solutions per minute for 4-point diamond shape.
gtest230a.c :
2600 solutions per minute for 7-point 4-colour
graph
gtest980a.c :
98000 solutions per minute for 7-point 4-colour
graph, Mosers’ spindle.
en.wikipedia.org slash wiki slash Moser_spindle
*************************************************/
B = 340;
total_edges = 24 ;

total_finds = 0;

maxi_ull = ((unsigned long long)6700417)*((unsigned long
long)2753074036095);
scaling = ((long double) 37)/((long double) 10);
one = (long double) 1;
diff_record = ((long double) 4100)/((long double) 100);

diff_record = MAXDIFFAT1;
maxdiffat400 = ((long double)1)/((long double)100000);
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;

epsilon = ((long double)1)/((long double)10000000);

rec_diff25 = (long double) 0;
rec_diff50 = (long double) 0;
rec_diff100 = (long double) 0;
rec_diff1 = (long double) 0;
rec_diff200 = (long double) 0;
rec_diff400 = (long double) 0;
rec_diff800 = (long double) 0;
rec_diff1200 = (long double) 0;
alphabet[0] = ‘A’;
alphabet[1] = ‘B’;
alphabet[2] = ‘C’;
alphabet[3] = ‘D’;
alphabet[4] = ‘E’;
alphabet[5] = ‘F’;
alphabet[6] = ‘G’;
alphabet[7] = ‘H’;
alphabet[8] = ‘I’;
alphabet[9] = ‘J’;
alphabet[10] = ‘K’;
alphabet[11] = ‘L’;
alphabet[12] = ‘M’;

/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q[i]=CNG+XS;

for(l=0; l< VERTEX ; l++)
{
dmatrix[l][l] = (long double) 0;
}

while( total_finds < 5000000000 )
{

graph_found = 0;

while( graph_found == 0)
{

numedges = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
adjmat[l][m] = 0;
}
}

while(numedges < total_edges )
{
ru1 = ((long double) KISS)/((long double) maxi_ull);
co1 = floorl(ru1*((long double)VERTEX));
ru2 = ((long double) KISS)/((long double) maxi_ull);
co2 = floorl(ru2*((long double)VERTEX));
if( (co1<VERTEX) && (co2<VERTEX))
{
if(co1 != co2)
{
if(adjmat[co1][co2] == 0)
{
adjmat[co1][co2] = 1;
adjmat[co2][co1] = 1;
numedges = numedges + 1;
}
}
}
}

/*** compute degrees[] ***/
/*** each 3 or more ***/

degree_test_passed = 1;

for(l=0; l< VERTEX ; l++)
{
degrees[l] = 0;

for(m=0; m < VERTEX; m++)
{
degrees[l] = degrees[l] + adjmat[l][m];
}

if( degrees[l] < 3 )
{
degree_test_passed = 0;
}
}

if(degree_test_passed == 1)
{
graph_found = 1;
}

}
count = 0;
max_has_converged_step = 0;
while( count < 1 )
{
solution_found = 0;

while( 0 == solution_found )
{
for( j=0; j< VERTEX ; j++)
{
randx = KISS;
xcoord[j] = ((long double) randx)/((long double) maxi_ull);
xcoord[j] = scaling*xcoord[j];
randx = KISS;
ycoord[j] = ((long double) randx)/((long double) maxi_ull);
ycoord[j] = scaling*ycoord[j];
}
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xcoord[l]-xcoord[m])*(xcoord[l]-xcoord[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ycoord[l]-ycoord[m])*(ycoord[l]-ycoord[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1 = diff;

if(diff < diff_record)
{
solution_found = 1;

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xcoord[j];
ygood[j] = ycoord[j];
}
}
}

/*****************************************************************

have solution …

*****************************************************************/
has_converged_flag = 0;
quit = 0;
count = count + 1;
/*************** BEGIN ITERATIONS TO CONVERGE **************/
for( k = 0; k < NUMSTEPS ; k++)
{
if( quit == 1)
{
break;
}

if( (k+1) < 100)
{
C = ((long double) 345)/((long double) 1000);
}
else
{
C = ((long double) B )/((long double) 1000);
}

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xgood[l]-xgood[m])*(xgood[l]-xgood[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ygood[l]-ygood[m])*(ygood[l]-ygood[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
if( (k+1) == 25 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff25 = diff;

if( diff > MAXDIFFAT25 )
{
quit = 1;
}
}
if( (k+1) == 50 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff50 = diff;

if( diff > MAXDIFFAT50 )
{
quit = 1;
}
}
if( (k+1) == 100 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff100 = diff;

if( diff > MAXDIFFAT100 )
{
quit = 1;
}
}

if( (k+1) == 200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff200 = diff;

if( diff > MAXDIFFAT200 )
{
quit = 1;
}
}
if( (k+1) == 400 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff400 = diff;

if( diff > MAXDIFFAT400 )
{
quit = 1;
}
}
if( (k+1) == 800 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff800 = diff;

if( diff > MAXDIFFAT800 )
{
quit = 1;
}

}
if( (k+1) == 1200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1200 = diff;

if( diff > MAXDIFFAT1200 )
{
quit = 1;
}

}
diff = (long double) 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

if( (diff < maxdiffat400) && (has_converged_flag == 0) )
{
has_converged_flag = 1;
has_converged_step = k+1;

if( has_converged_step > max_has_converged_step )
{
max_has_converged_step = has_converged_step;
}

quit = 1;

/***********************

int is_singular;

**********************/
is_singular = 0;

for(l=0; l < VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( dmatrix[l][m] < epsilon )
{
is_singular = 1;
}
}
}
if( is_singular == 0)
{

total_finds = total_finds + 1;

if( (diff25 > rec_diff25) && (has_converged_step > 25))
{
rec_diff25 = diff25;
}

if( (diff50 > rec_diff50) && (has_converged_step > 50))
{
rec_diff50 = diff50;
}
if( (diff100 > rec_diff100) && (has_converged_step > 100))
{
rec_diff100 = diff100;
}

if( diff1 > rec_diff1)
{
rec_diff1 = diff1;
}

if( (diff200 > rec_diff200) && (has_converged_step > 200) )
{
rec_diff200 = diff200;
}

if( (diff400 > rec_diff400 ) && (has_converged_step > 400))
{
rec_diff400 = diff400;
}
if( (diff800 > rec_diff800) && (has_converged_step > 800))
{
rec_diff800 = diff800;
}
if( (diff1200 > rec_diff1200) && (has_converged_step > 1200))
{
rec_diff1200 = diff1200;
}
#ifdef VERBOSE
for(l = 0; l< VERTEX; l++)
{
for(m=0; m< VERTEX; m++)
{
post_adjmat[l][m] = 0;
}
}
probable_unit_lengths = 0;

for(l = 0; l<VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( fabsl(dmatrix[l][m]-one) < epsilon )
{
probable_unit_lengths++ ;
post_adjmat[l][m] = 1;
post_adjmat[m][l] = 1;
}
}
}
/**** TEST post_adjmat[][] for 3-coloring BEGIN ****/

n_colors = 3;
coloring_found = 0;
for(v0 = 0; v0< 1 ; v0++)
{
for(v1 = 0; v1< 2 ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{

colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
has_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
}
}
}

if( has_failed == 0 )
{
coloring_found = 1;
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
is_3colorable = 1;
}
else
{
is_3colorable = 0;
}

/**** TEST post_adjmat[][] for 3-coloring END ****/

printf(“adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, adjmat[l][m]) ;
}
printf(“\n”);
}

printf(“\n”);
printf(“post adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, post_adjmat[l][m]) ;
}
printf(“\n”);
}
n_colors = 4;
coloring_found = 0;
num_4_colorings = 0;
for(v0 = 0; v0< n_colors ; v0++)
{
for(v1 = 0; v1< n_colors ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{

colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
has_failed = 0;
four_colouring_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
four_colouring_failed = 1;
}
if( four_colouring_failed == 1)
{
break;
}
}

if( four_colouring_failed == 1)
{
break;
}
}

if( has_failed == 0 )
{
coloring_found = 1;
num_4_colorings++ ;
}
}
}
}
}
}
}
}
}
}
}
}
}
}

num_4_colorings_mod_24 = num_4_colorings%24 ;

count_4_colorings = num_4_colorings/24;
printf(“total_finds = %d\n”, total_finds);
printf(“Tests count = %d “, count);
printf(“has_converged_step = %d “, has_converged_step);
printf(“max_has_converged_step = %d\n”, max_has_converged_step);
printf(“rec_diff1 = %.6Lf\n”, rec_diff1);
printf(“rec_diff25 = %.6Lf\n”, rec_diff25);
printf(“rec_diff50 = %.6Lf\n”, rec_diff50);
printf(“rec_diff100 = %.6Lf\n”, rec_diff100);
printf(“rec_diff200 = %.6Lf\n”, rec_diff200);
printf(“rec_diff400 = %.6Lf\n”, rec_diff400);
printf(“rec_diff800 = %.16Lf\n”, rec_diff800);
printf(“rec_diff1200 = %.16Lf\n”, rec_diff1200);
printf(“probable_unit_lengths = %d\n”, probable_unit_lengths);

printf(“graph is 3-colorable:”);
if(is_3colorable == 1)
{
printf(“yes. “);
}
else
{
printf(“no. “);
}

printf(“count_4_colorings = %d\n”, count_4_colorings);
printf(“num_4_colorings_mod_24 = %d\n”, num_4_colorings_mod_24);

printf(“Matrix of distances vertex to vertex:\n”);
printf(” “);
for(m=0; m<VERTEX; m++)
{
printf(” %c “, alphabet[m]);
}
printf(“\n”);
for(l=0; l< VERTEX ; l++)
{
printf(“%c “, alphabet[l]);
for(m=0; m< VERTEX ; m++)
{
printf(“%.3Lf “, dmatrix[l][m]);
}
printf(“\n”);
}

printf(“\n”);
fflush(stdout);
#endif

}
}
for(l=0; l< VERTEX ; l++)
{
forces[l][0] = (long double) 0;
forces[l][1] = (long double) 0;

for(m=0; m< VERTEX ; m++)
{
if( 1 == adjmat[l][m] )
{
vector[0] = xgood[m]-xgood[l];
vector[1] = ygood[m]-ygood[l];
vector[0] = vector[0]/dmatrix[l][m];
vector[1] = vector[1]/dmatrix[l][m];
vector[0] = vector[0]*C;
vector[1] = vector[1]*C;
vector[0] = vector[0]*(dmatrix[l][m]-one);
vector[1] = vector[1]*(dmatrix[l][m]-one);

forces[l][0] = forces[l][0] + vector[0];
forces[l][1] = forces[l][1] + vector[1];
}
}
}

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xgood[j] + forces[j][0];
ygood[j] = ygood[j] + forces[j][1];
}
}
/******************************************************
Below, post-convergence algorithm or heuristic:
******************************************************/
}
/*****************************************
while( count < 1 ) end Block
*****************************************/
}
/********************************************
end of while( 1 == 1 ) Block
********************************************/
return 0;
}

Written by meditationatae

February 17, 2017 at 2:33 am

Posted in History

new solver 13 vertices

udgraph13_solverff9789nu95a.c

in

/home/david/graphs/golomb18

#include <stdio.h>
#include <math.h>
#define NUMSTEPS 2500
#define MAXDIFFAT100 ((long double) 18)/((long double) 1)
#define MAXDIFFAT50 ((long double) 18)/((long double) 1)
#define MAXDIFFAT25 ((long double) 40)/((long double) 1)
#define MAXDIFFAT1 ((long double) 40)/((long double) 1)
#define MAXDIFFAT200 ((long double) 96)/((long double) 10)
#define MAXDIFFAT400 ((long double) 67)/((long double) 1000)
#define MAXDIFFAT800 ((long double) 79)/((long double) 100000000)
#define MAXDIFFAT1200 ((long double) 84)/((long double)1000000000000)
#define VERBOSE
#define VERTEX 13

/**********************************************
rec_diff1 = 28.852841 40.0
rec_diff25 = 39.668785 40.0
rec_diff50 = 17.967935 18.0
rec_diff100 = 17.856958 18.0
rec_diff200 = 9.573263 9.6
rec_diff400 = 0.066982 6.7e-2
rec_diff800 = 0.0000007832212564 7.9e-7
rec_diff1200 = 0.0000000000839841 8.4e-11
************************************************/

static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )
/********************* README SECTION *********************

10-point non-singular solutions to the unit
graph problem are found numerically at a rate of
57.9 solutions per second on a dual core Athlon
5000+ processor.

The solutions are expected to be isometric as a
10-point metric space to the soltion depicted in
the graph in my blog post :

Sketch of 10-vertex unit distance graph, 2013
at URL =

meditationatae.wordpress.com/2017/02/06/sketch-of-10-vertex-unit-distance-graph-2013
The sci dot math posts:

mathforum.org/kb/message.jspa?messageID=10081388

and earlier:

mathforum.org/kb/message.jspa?messageID=10074716

This solver for a particular graph has been optimized
to run in as little time as possible for the given graph,
decribed by the 10×10 adjacency matrix.

To compile, I type:

$ gcc -lm -O3 -o udgraph_solver201a.out udgraph_solver201a.c

at the shell command line in Linux.

The executable is then udgraph_solver201a.out .
In C pre-processor terms, if VERBOSE is defined by
a pre-processor directive,
Number-Sign define VERBOSE
say on line 7 above after the other
Number-sign defines,
then the solution count and the 10×10 matrix of vertex to vertex
distances for a solution will be printed.

As above VERBOSE is not defined, the program will run with
minimal output until it finishes after about 9 minutes
with my system.

This README is based on file
Slash home slash david slash graphs slash golomb6
slash udgraph_solver201a dot c,

will serve to write the local file:

Slash home slash david slash graphs slash golomb6
slash udgraph_solver301a dot c ,

and will go by the Moniker or alias
“unit distance graph solver draft 101”

a hexadecimal dump will be posted to my blog

meditationatae.wordpress.com
David Bernier

********************* README END *************************/

int main(void)
{
unsigned long long i,cng=123456789987654321LL, xs=362436069362436069LL;
unsigned long long randx;
int B;
int j;
int k;
int quit;
int is_singular;
int graph_found;
int total_edges;
int degree_test_passed;
int l, m;
int n, p;
int has_k4;
int is_3colorable;
int count;
int total_finds;
int probable_unit_lengths;
int solution_found;
int coloring_found;
char alphabet[VERTEX];
unsigned long long maxi_ull;
long double xcoord[VERTEX];
long double diff;
long double diff25;
long double diff50;
long double diff100;
long double diff200;
long double diff400;
long double diff800;
long double diff1200;
long double diff1;
long double rec_diff25;
long double rec_diff50;
long double rec_diff100;
long double rec_diff200;
long double rec_diff400;
long double rec_diff800;
long double rec_diff1200;
long double rec_diff1;
long double ru1;
long double ru2;
long double epsilon;
int co1;
int co2;
int colors[VERTEX];
int num_4_colorings;
int num_4_colorings_mod_24;
int count_4_colorings;
int n_colors;
int degrees[VERTEX];
int v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12;
int has_failed;
int numedges;
long double diff_record;
long double maxdiffat400;
long double one;
long double ycoord[VERTEX];
long double forces[VERTEX][2];
long double C;
long double vector[2];
long double xgood[VERTEX];
long double ygood[VERTEX];
int four_colouring_failed;
int has_converged_flag;
int has_converged_step;
int max_has_converged_step;
long double scaling;
long double dmatrix[VERTEX][VERTEX];
int adjmat[VERTEX][VERTEX];
int post_adjmat[VERTEX][VERTEX];
/************************************************************************

udgraph_solver3401a.c : user 22m50.198s w/
MAXDIFFAT100 ((long double) 38)/((long double) 1)

newtestz746a.out 345 : 8m 34.631s for 30k solns. , using -O3
newtestz745a.out 340 : 8m 35s for 30000 solutions, with -O3
newtestz585a.c: 8m 51s for 30000 solutions, using -O3 optimization
newtest83a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest81a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest73a.c: 8m 49s for 30000 solutions, using -O3 optimization option
newtest66a.c: 10m 25s for 30000 solutions, using -O3 optimization option
newtest65a.c: 11m 30s for 30000 solutions
newtest64a.c: 11m 30s for 30000 solutions
newtest63a.c: 11m 33s for 30000 solutions
newtest62a.c: 11m 33s for 30000 solutions
newtest61a.c: 3m 51s for 10000 solutions
newtest57a.c: 6m 27s for 10000 solutions
newtest56a.c: 6m 37s for 10000 solutions
newtest55a.c: 6m 43s for 10000 solutions
newtest54a.c: 6m 48s for 10000 solutions
newtest53a.c: 6m 46s for 10000 solutions
newtest48a.c: 62 seconds for 1600 solutions
newtest47a.c: 14 seconds for 400 solutions
newtest46a.c: 66 seconds for 400 solutions
newtest39a.c: 67 seconds for 400 solutions
newtest37a.c: 70 seconds for 400 solutions
newtest35a.c: 79 seconds for 400 solutions
newtest34a.c: 72 seconds for 400 solutions
newtest33a.c: 91 seconds for 400 solutions
newtest30a.c: 16 seconds for 100 solutions
newtest29a.c: 18 seconds for 100 solutions
newtest28a.c: 25 seconds for 100 solutions
newtest27a.c: 50 seconds for 100 solutions
newtest26a.c: 99 seconds for 100 solutions
newtest25a.c: 3000 solutions per hour
for 100 solutions, 2 minutes …
808 solutions per minute for 4-point diamond shape.
gtest230a.c :
2600 solutions per minute for 7-point 4-colour
graph
gtest980a.c :
98000 solutions per minute for 7-point 4-colour
graph, Mosers’ spindle.
en.wikipedia.org slash wiki slash Moser_spindle
*************************************************/
B = 340;
total_edges = 24 ;

total_finds = 0;

maxi_ull = ((unsigned long long)6700417)*((unsigned long
long)2753074036095);
scaling = ((long double) 37)/((long double) 10);
one = (long double) 1;
diff_record = ((long double) 4100)/((long double) 100);

diff_record = MAXDIFFAT1;
maxdiffat400 = ((long double)1)/((long double)100000);
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;

epsilon = ((long double)1)/((long double)10000000);

rec_diff25 = (long double) 0;
rec_diff50 = (long double) 0;
rec_diff100 = (long double) 0;
rec_diff1 = (long double) 0;
rec_diff200 = (long double) 0;
rec_diff400 = (long double) 0;
rec_diff800 = (long double) 0;
rec_diff1200 = (long double) 0;
alphabet[0] = ‘A’;
alphabet[1] = ‘B’;
alphabet[2] = ‘C’;
alphabet[3] = ‘D’;
alphabet[4] = ‘E’;
alphabet[5] = ‘F’;
alphabet[6] = ‘G’;
alphabet[7] = ‘H’;
alphabet[8] = ‘I’;
alphabet[9] = ‘J’;
alphabet[10] = ‘K’;
alphabet[11] = ‘L’;
alphabet[12] = ‘M’;

/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q[i]=CNG+XS;

for(l=0; l< VERTEX ; l++)
{
dmatrix[l][l] = (long double) 0;
}

while( total_finds < 5000000000 )
{

graph_found = 0;

while( graph_found == 0)
{

numedges = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
adjmat[l][m] = 0;
}
}

while(numedges < total_edges )
{
ru1 = ((long double) KISS)/((long double) maxi_ull);
co1 = floorl(ru1*((long double)VERTEX));
ru2 = ((long double) KISS)/((long double) maxi_ull);
co2 = floorl(ru2*((long double)VERTEX));
if( (co1<VERTEX) && (co2<VERTEX))
{
if(co1 != co2)
{
if(adjmat[co1][co2] == 0)
{
adjmat[co1][co2] = 1;
adjmat[co2][co1] = 1;
numedges = numedges + 1;
}
}
}
}

/*** compute degrees[] ***/
/*** each 3 or more ***/

degree_test_passed = 1;

for(l=0; l< VERTEX ; l++)
{
degrees[l] = 0;

for(m=0; m < VERTEX; m++)
{
degrees[l] = degrees[l] + adjmat[l][m];
}

if( degrees[l] < 3 )
{
degree_test_passed = 0;
}
}

if(degree_test_passed == 1)
{
graph_found = 1;
}

}
count = 0;
max_has_converged_step = 0;
while( count < 1 )
{
solution_found = 0;

while( 0 == solution_found )
{
for( j=0; j< VERTEX ; j++)
{
randx = KISS;
xcoord[j] = ((long double) randx)/((long double) maxi_ull);
xcoord[j] = scaling*xcoord[j];
randx = KISS;
ycoord[j] = ((long double) randx)/((long double) maxi_ull);
ycoord[j] = scaling*ycoord[j];
}
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xcoord[l]-xcoord[m])*(xcoord[l]-xcoord[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ycoord[l]-ycoord[m])*(ycoord[l]-ycoord[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1 = diff;

if(diff < diff_record)
{
solution_found = 1;

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xcoord[j];
ygood[j] = ycoord[j];
}
}
}

/*****************************************************************

have solution …

*****************************************************************/
has_converged_flag = 0;
quit = 0;
count = count + 1;
/*************** BEGIN ITERATIONS TO CONVERGE **************/
for( k = 0; k < NUMSTEPS ; k++)
{
if( quit == 1)
{
break;
}

if( (k+1) < 100)
{
C = ((long double) 345)/((long double) 1000);
}
else
{
C = ((long double) B )/((long double) 1000);
}

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xgood[l]-xgood[m])*(xgood[l]-xgood[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ygood[l]-ygood[m])*(ygood[l]-ygood[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
if( (k+1) == 25 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff25 = diff;

if( diff > MAXDIFFAT25 )
{
quit = 1;
}
}
if( (k+1) == 50 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff50 = diff;

if( diff > MAXDIFFAT50 )
{
quit = 1;
}
}
if( (k+1) == 100 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff100 = diff;

if( diff > MAXDIFFAT100 )
{
quit = 1;
}
}

if( (k+1) == 200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff200 = diff;

if( diff > MAXDIFFAT200 )
{
quit = 1;
}
}
if( (k+1) == 400 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff400 = diff;

if( diff > MAXDIFFAT400 )
{
quit = 1;
}
}
if( (k+1) == 800 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff800 = diff;

if( diff > MAXDIFFAT800 )
{
quit = 1;
}

}
if( (k+1) == 1200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1200 = diff;

if( diff > MAXDIFFAT1200 )
{
quit = 1;
}

}
diff = (long double) 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

if( (diff < maxdiffat400) && (has_converged_flag == 0) )
{
has_converged_flag = 1;
has_converged_step = k+1;

if( has_converged_step > max_has_converged_step )
{
max_has_converged_step = has_converged_step;
}

quit = 1;

/***********************

int is_singular;

**********************/
is_singular = 0;

for(l=0; l < VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( dmatrix[l][m] < epsilon )
{
is_singular = 1;
}
}
}
if( is_singular == 0)
{

total_finds = total_finds + 1;

if( (diff25 > rec_diff25) && (has_converged_step > 25))
{
rec_diff25 = diff25;
}

if( (diff50 > rec_diff50) && (has_converged_step > 50))
{
rec_diff50 = diff50;
}
if( (diff100 > rec_diff100) && (has_converged_step > 100))
{
rec_diff100 = diff100;
}

if( diff1 > rec_diff1)
{
rec_diff1 = diff1;
}

if( (diff200 > rec_diff200) && (has_converged_step > 200) )
{
rec_diff200 = diff200;
}

if( (diff400 > rec_diff400 ) && (has_converged_step > 400))
{
rec_diff400 = diff400;
}
if( (diff800 > rec_diff800) && (has_converged_step > 800))
{
rec_diff800 = diff800;
}
if( (diff1200 > rec_diff1200) && (has_converged_step > 1200))
{
rec_diff1200 = diff1200;
}
#ifdef VERBOSE
for(l = 0; l< VERTEX; l++)
{
for(m=0; m< VERTEX; m++)
{
post_adjmat[l][m] = 0;
}
}
probable_unit_lengths = 0;

for(l = 0; l<VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( fabsl(dmatrix[l][m]-one) < epsilon )
{
probable_unit_lengths++ ;
post_adjmat[l][m] = 1;
post_adjmat[m][l] = 1;
}
}
}
/**** TEST for 3-coloring BEGIN ****/

n_colors = 3;
coloring_found = 0;
for(v0 = 0; v0< 1 ; v0++)
{
for(v1 = 0; v1< 2 ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{

colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
has_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
}
}
}

if( has_failed == 0 )
{
coloring_found = 1;
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
is_3colorable = 1;
}
else
{
is_3colorable = 0;
}

/**** TEST for 3-coloring END ****/

printf(“adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, adjmat[l][m]) ;
}
printf(“\n”);
}

printf(“\n”);
printf(“post adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, post_adjmat[l][m]) ;
}
printf(“\n”);
}
n_colors = 4;
coloring_found = 0;
num_4_colorings = 0;
for(v0 = 0; v0< n_colors ; v0++)
{
for(v1 = 0; v1< n_colors ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{

colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
has_failed = 0;
four_colouring_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
four_colouring_failed = 1;
}
if( four_colouring_failed == 1)
{
break;
}
}

if( four_colouring_failed == 1)
{
break;
}
}

if( has_failed == 0 )
{
coloring_found = 1;
num_4_colorings++ ;
}
}
}
}
}
}
}
}
}
}
}
}
}
}

num_4_colorings_mod_24 = num_4_colorings%24 ;

count_4_colorings = num_4_colorings/24;
printf(“total_finds = %d\n”, total_finds);
printf(“Tests count = %d “, count);
printf(“has_converged_step = %d “, has_converged_step);
printf(“max_has_converged_step = %d\n”, max_has_converged_step);
printf(“rec_diff1 = %.6Lf\n”, rec_diff1);
printf(“rec_diff25 = %.6Lf\n”, rec_diff25);
printf(“rec_diff50 = %.6Lf\n”, rec_diff50);
printf(“rec_diff100 = %.6Lf\n”, rec_diff100);
printf(“rec_diff200 = %.6Lf\n”, rec_diff200);
printf(“rec_diff400 = %.6Lf\n”, rec_diff400);
printf(“rec_diff800 = %.16Lf\n”, rec_diff800);
printf(“rec_diff1200 = %.16Lf\n”, rec_diff1200);
printf(“probable_unit_lengths = %d\n”, probable_unit_lengths);

printf(“graph is 3-colorable:”);
if(is_3colorable == 1)
{
printf(“yes. “);
}
else
{
printf(“no. “);
}

printf(“count_4_colorings = %d\n”, count_4_colorings);
printf(“num_4_colorings_mod_24 = %d\n”, num_4_colorings_mod_24);

printf(“Matrix of distances vertex to vertex:\n”);
printf(” “);
for(m=0; m<VERTEX; m++)
{
printf(” %c “, alphabet[m]);
}
printf(“\n”);
for(l=0; l< VERTEX ; l++)
{
printf(“%c “, alphabet[l]);
for(m=0; m< VERTEX ; m++)
{
printf(“%.3Lf “, dmatrix[l][m]);
}
printf(“\n”);
}

printf(“\n”);
fflush(stdout);
#endif

}
}
for(l=0; l< VERTEX ; l++)
{
forces[l][0] = (long double) 0;
forces[l][1] = (long double) 0;

for(m=0; m< VERTEX ; m++)
{
if( 1 == adjmat[l][m] )
{
vector[0] = xgood[m]-xgood[l];
vector[1] = ygood[m]-ygood[l];
vector[0] = vector[0]/dmatrix[l][m];
vector[1] = vector[1]/dmatrix[l][m];
vector[0] = vector[0]*C;
vector[1] = vector[1]*C;
vector[0] = vector[0]*(dmatrix[l][m]-one);
vector[1] = vector[1]*(dmatrix[l][m]-one);

forces[l][0] = forces[l][0] + vector[0];
forces[l][1] = forces[l][1] + vector[1];
}
}
}

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xgood[j] + forces[j][0];
ygood[j] = ygood[j] + forces[j][1];
}
}
/******************************************************
Below, post-convergence algorithm or heuristic:
******************************************************/
}
/*****************************************
while( count < 1 ) end Block
*****************************************/
}
/********************************************
end of while( 1 == 1 ) Block
********************************************/
return 0;
}

 

===

 

It supposedly found a 4-chromatic 13-vertex, 30-edge unit distance graph :

post adjacency matrix:
0 0 1 0 0 1 1 0 1 0 0 1 0
0 0 0 1 1 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 1 0 1 0
0 1 0 0 1 1 0 0 0 0 0 1 1
0 1 1 1 0 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 1 1 0 1 0 0
0 0 1 0 0 0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0 0 1 0 0 1
0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 1 1
1 0 1 1 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 1 1 1 1 0
total_finds = 8
Tests count = 1 has_converged_step = 1410 max_has_converged_step = 1410
rec_diff1 = 32.435776
rec_diff25 = 10.906118
rec_diff50 = 12.382250
rec_diff100 = 13.752239
rec_diff200 = 0.352660
rec_diff400 = 0.000585
rec_diff800 = 0.0000000246891323
rec_diff1200 = 0.0000000000010421
probable_unit_lengths = 30
graph is 3-colorable:no. count_4_colorings = 212
num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M
A 0.000 0.737 1.000 0.457 0.577 1.000 1.000 1.370 1.000 0.457 1.915 1.000 1.370
B 0.737 0.000 0.457 1.000 1.000 1.732 1.000 0.737 1.568 0.577 1.568 0.577 1.457
C 1.000 0.457 0.000 1.370 1.000 1.915 1.457 1.000 1.947 1.000 1.947 1.000 1.915
D 0.457 1.000 1.370 0.000 1.000 1.000 0.737 1.444 0.577 0.457 1.732 1.000 1.000
E 0.577 1.000 1.000 1.000 0.000 1.000 1.568 1.732 1.457 1.000 2.432 1.457 1.947
F 1.000 1.732 1.915 1.000 1.000 0.000 1.732 2.354 1.000 1.370 2.731 1.947 1.915
G 1.000 1.000 1.457 0.737 1.568 1.732 0.000 1.000 1.000 0.577 1.000 0.577 0.457
H 1.370 0.737 1.000 1.444 1.732 2.354 1.000 0.000 1.915 1.000 1.000 0.457 1.370
I 1.000 1.568 1.947 0.577 1.457 1.000 1.000 1.915 0.000 1.000 1.947 1.457 1.000
J 0.457 0.577 1.000 0.457 1.000 1.370 0.577 1.000 1.000 0.000 1.457 0.577 1.000
K 1.915 1.568 1.947 1.732 2.432 2.731 1.000 1.000 1.947 1.457 0.000 1.000 1.000
L 1.000 0.577 1.000 1.000 1.457 1.947 0.577 0.457 1.457 0.577 1.000 0.000 1.000
M 1.370 1.457 1.915 1.000 1.947 1.915 0.457 1.370 1.000 1.000 1.000 1.000 0.000

I find equilateral triangles:

ACL

AFI

AGI

BDE

CEJ

CHJ

DEF

DLM

GHK

IJM

KLM

 

Written by meditationatae

February 17, 2017 at 1:04 am

Posted in History