main.js

/*
 * Execute with node.js, and pass the input via stdin, like so:
 *     node main.js < input.txt
 */

/**
 * The entry point, reads a number n then n datasets from stdin
 * and passes them into run()
 */
function main() {
	process.stdin.resume();
	process.stdin.setEncoding('utf8');
	
	process.stdin.on('data', function (chunk) {
	  var input = chunk.split('\n');
	  for(var i = 1; i <= input[0]; i++) {
	  	var line = input[i].split(' ');
	  	run(line, i);
	  }
	});
}

/**
 * Called when a line is read in by main
 */
function run(data, iteration) {
	var width = data[0],
		height = data[1],
		words = data.slice(2);
	
	for(var size = 1000; size > 0; size--) {
		var line = 0,
			lines = [];
		var valid = true;
		
		for(var i = 0; i < words.length; i++) {
			do {
				var space = 0;
				var placed = false;
				
				if(typeof lines[line] == 'undefined') lines[line] = '';
				else space = 1;
				
				if((line+1) * size > height) {
					valid = false;
					break;
				} else if((words[i].length + space + lines[line].length) * size > width) {
					line++;
				} else   {
					if(space == 1) lines[line] += ' ';	
					lines[line] += words[i];
					placed = true;
				}
			} while(!placed);
			
			if(!valid) break;
		}
		
		if(valid) {
			console.log('Case #' + iteration + ': ' + size);
			return;
		}
	}
}

main();