0026. HyperCube

Имя входного файла:	hypercub.in
Имя выходного файла:	hypercub.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

There lives an n-dimensional Kitten on the surface of n-dimensional cube. His n-dimensional house is situated in the vertex of this cube.

Once they have built an n-dimensional subway near his house. This subway is a straight line in n-dimensional space connecting two vertices (one of them is Kitten's home).

Also they have built another straight subway. This subway is also connecting two vertices (may be the same or another).

The Kitten now often uses these lines because the other subway passes near his n-dimensional girlfriend's home. And now he thinks about the following problem: which is the fastest way between two subways? The subways are very fast, but the Kitten's velocity is very small relatively to velocity of subway train, so he wants to minimize the time of travelling by feet between two subways. Also there are many streets under the surface of cube and near it (as you know, the n-dimensional Kittens always build true n-dimensional towns with many n-dimensional passes) so the distance is approximately equal to the distance between the selected two straight lines in n-dimensional space (infinite straight lines, of course, because the subways are very very long).

So your task is to find this distance.

For this task you may assume that all edges of cube have the length of 1. One of the vertices of the cube is (0, 0, …, 0), and all edges are parallel to coordinate axes. So any vertex of the cube may be coded by a sequence of n 0's and 1's.

Input file

The first line of the input file contains one integer number n (2≤ n≤ 100). Then four input lines follow with n symbols each. All of these symbols are 0's and 1's. The i-th symbol of j-th line represents the i-th coordinate of j-th vertex. The first subway passes through first and second vertices, the second subway – through the other two ones. The vertices describing each subway are different (but subways may intersect in one or both of the vertices, for example, first and third vertices may be identical).

Output file

Write to the output file distance between given two lines in n-dimensional space rounded to 6 digits after decimal point.

Examples:

hypercub.in	hypercub.out
2 00 01 10 11	1.000000

Источник: Petrozavodsk training camp, Summer 2002. Startup contest
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати