import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

class Simulation
{
	// We don't need no steenkin command line arguments, we got constants
	static final int NODES = 2000, DEGREE = 10, WALK_STEPS = 6;
	static final int ROUNDS = 10000, SWAPS_PER_ROUND = 10000;
	static final int SWAP_LIMIT = SWAPS_PER_ROUND * WALK_STEPS / NODES;
	
	ArrayList<Node> nodes;
	int round;
	
	Simulation()
	{
		// Create an ideal Kleinberg network, then shuffle it
		nodes = new ArrayList<Node> (NODES);
		for (int i = 0; i < NODES; i++) nodes.add (new Node());
		makeKleinbergNetwork (nodes);
		for (Node n : nodes) n.location = Math.random();
		
		// See how long it takes to recover
		for (round = 1; round <= ROUNDS; round++) {
			printDistance();
			swapLocations();
		}
	}
	
	void printDistance()
	{
		// Print the mean edge length
		double distance = 0.0;
		int edges = 0;
		for (Node a : nodes) {
			for (Node b : a.neighbours) {
				distance += distance (a, b);
				edges++;
			}
		}
		System.out.print (distance / edges + " ");
	}
	
	void swapLocations()
	{
		int swapsAccepted = 0;
		for (int i = 0; i < SWAPS_PER_ROUND; i++) {
			Node a = nodes.get ((int) (Math.random() * NODES));
			if (a.neighbours.isEmpty()) continue;
			Node b = loopingRandomWalk (a, WALK_STEPS);
			if (b == null) continue; // Too much swap traffic
			swapsAccepted++;
			if (shouldSwap (a, b)) {
				double temp = a.location;
				a.location = b.location;
				b.location = temp;
			}
		}
		System.out.println ((double) swapsAccepted / SWAPS_PER_ROUND);
	}
	
	Node loopingRandomWalk (Node n, int steps)
	{
		if ((double) n.swapTraffic++ / round > SWAP_LIMIT) return null;
		if (steps == 0) return n;
		ArrayList<Node> neighbours = new ArrayList<Node> (n.neighbours);
		int random = (int) (Math.random() * neighbours.size());
		return loopingRandomWalk (neighbours.get (random), steps - 1);
	}
	
	static double distance (Node a, Node b)
	{
		double x = a.location, y = b.location;
		if (x > y) return Math.min (x - y, y - x + 1.0);
		else return Math.min (y - x, x - y + 1.0);
	}
	
	boolean shouldSwap (Node a, Node b)
	{
		double before = 1.0;
		for (Node c : a.neighbours) before *= distance (a, c);
		for (Node d : b.neighbours) before *= distance (b, d);
		
		double after = 1.0;
		for (Node c : a.neighbours) after *= distance (b, c);
		for (Node d : b.neighbours) after *= distance (a, d);
		
		if (after <= before) return true;
		else return Math.random() < before / after;
	}
	
	static void makeKleinbergNetwork (ArrayList<Node> nodes)
	{
		for (Node a : nodes) {
			// Normalise the probabilities
			double norm = 0.0;
			for (Node b : nodes) {
				if (a.location == b.location) continue;
				norm += 1.0 / distance (a, b);
			}
			// Create DEGREE/2 outgoing connections
			for (Node b : nodes) {
				if (a.location == b.location) continue;
				double p = 1.0 / distance (a, b) / norm;
				for (int i = 0; i < DEGREE / 2; i++) {
					if (Math.random() < p) {
						a.neighbours.add (b);
						b.neighbours.add (a);
						break;
					}
				}
			}
		}
	}
	
	public static void main (String[] args)
	{
		new Simulation();
	}
	
	class Node
	{
		HashSet<Node> neighbours = new HashSet<Node>();
		double location = Math.random();
		int swapTraffic = 0;
	}
}