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 REDS = 1000, BLACKS = 1000, NODES = REDS + BLACKS;
	static final int DEGREE = 10, JOINS = 5, COLUMNS = 20, WALK_STEPS = 6;
	static final int ROUNDS = 10000, SWAPS_PER_ROUND = 1000 * 1000;
	static final int SWAP_LIMIT = SWAPS_PER_ROUND * WALK_STEPS / NODES;
	
	ArrayList<Node> reds, blacks, nodes;
	int[] loc = new int[COLUMNS];
	int round;
	
	Simulation()
	{
		// Create two separate networks each covering the whole keyspace
		reds = new ArrayList<Node> (REDS);
		for (int i = 0; i < REDS; i++) reds.add (new Node());
		makeKleinbergNetwork (reds);
		blacks = new ArrayList<Node> (BLACKS);
		for (int i = 0; i < BLACKS; i++) blacks.add (new Node());
		makeKleinbergNetwork (blacks);
		
		// Join the networks at a few randomly chosen points
		for (int i = 0; i < JOINS; i++) {
			Node a = reds.get ((int) (Math.random() * REDS));
			Node b = blacks.get ((int) (Math.random() * BLACKS));
			a.neighbours.add (b);
			b.neighbours.add (a);
		}
		
		// Allow the networks to swap with each other
		nodes = new ArrayList<Node> (NODES);
		nodes.addAll (reds);
		nodes.addAll (blacks);
		
		// See whether the locations become segregated
		for (round = 1; round <= ROUNDS; round++) {
			printLocations();
			swapLocations();
		}
	}
	
	void printLocations()
	{
		// Print the location distribution of the reds
		for (Node r : reds) loc[(int) (r.location * COLUMNS)]++;
		for (int i = 0; i < COLUMNS; i++) {
			System.out.print (loc[i] + " ");
			loc[i] = 0;
		}
	}
	
	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);
	}
	
	static 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;
	}
}