/* FiveActiveMachines.java
 *
 * Lower bounds for online makespan minimization on
 * a small number of related machines
 * Joint work with Lukasz Jez, Jiri Sgall, Jozsef Bekesi
 *
 * k = number of active machines, r = depth of search
 * Prints number of nodes left at each tree depth r
 * Reports bound if and only if it is found
 * 7-8-12
 *
 * Command: java FiveActiveMachines k r alpha R
 * Example: java FiveActiveMachines 3 100 1.450217 2.3473
 */

import java.util.ArrayList;
public class KActiveMachines 
{

	/* The Mach data structure stores the state at a particular 
	 * node in the search tree
	 * v stores the relative load on all of the machines
	 */  
	private static class Mach
	{
		private double[] v;
		
		public Mach(double[] v)
		{
			this.v = v;
		}
	}
	
	// Arguments in order: k, r, alpha, R
	public static void main(String[] args)
	{
		// Number of active machines
		int k = Integer.parseInt(args[0]);
	
		// Max Depth of Search
		int r = Integer.parseInt(args[1]);
		
		// alpha we are testing
		double alpha = Double.parseDouble(args[2]);
		
		// Ratio R we are testing at current alpha
		double R = Double.parseDouble(args[3]);
		
		// at step j, mach stores the j^th level of the search tree
		ArrayList<Mach> mach = new ArrayList<Mach>();
		
		// initialization
		double[] v = new double[k];
		for (int i = 0; i < k; i++)
			v[i] = 0;
		mach.add(new Mach(v));
		
		// Continue assigning jobs until we reach maximum depth
		for (int j = 0; j < r; j++)
		{
			ArrayList<Mach> next = new ArrayList<Mach>();
			boolean first = true;
			for (Mach ma : mach)
			{
				double[] v0 = ma.v;
				double[] v1 = new double[k];
				double[] v2 = new double[k];
				
				// new relative for machine i is in v1[i] unless
				// it takes the next job, meaning it is in v2[i]
				for (int i = 0; i < k; i++)
				{
					v1[i] = v0[i]/alpha;
					v2[i] = v1[i] + 1;
				}
				
				
				for (int i = 0; i < k; i++)
				{
					// If relative load is under that prescribed by R
					// then, add this vector to the tree
					if (v2[i] <= R/(Math.pow(alpha, k - i - 1)))
					{
						double[] v3 = new double[k];
						for (int p = 0; p < k; p++)
						{
							if (p != i)
								v3[p] = v1[p];
							else
								v3[p] = v2[p];
						}
						next.add(new Mach(v3));
					}
					
				}				
			}
			
			// Report that R is a lower bound if there are no nodes at depth j
			if (next.size() == 0)
			{
				System.out.println("Alpha: " + alpha + "Bound: " + R);
				break;
			}
			
			// Print the number of nodes at current depth
			System.out.println((j+1) + " " + next.size());
			mach = next;
		}	
	}
}