/*
 * Problem C. Recycled Numbers
 * 
 * Do you ever become frustrated with television because you keep seeing the
 * same things, recycled over and over again? Well I personally don't care about
 * television, but I do sometimes feel that way about numbers.
 * 
 * Let's say a pair of distinct positive integers (n, m) is recycled if you can
 * obtain m by moving some digits from the back of n to the front without
 * changing their order. For example, (12345, 34512) is a recycled pair since
 * you can obtain 34512 by moving 345 from the end of 12345 to the front. Note
 * that n and m must have the same number of digits in order to be a recycled
 * pair. Neither n nor m can have leading zeros.
 * 
 * Given integers A and B with the same number of digits and no leading zeros,
 * how many distinct recycled pairs (n, m) are there with A â¤ n < m â¤ B?
 * 
 * Input
 * 
 * The first line of the input gives the number of test cases, T. T test cases
 * follow. Each test case consists of a single line containing the integers A
 * and B.
 * 
 * Output
 * 
 * For each test case, output one line containing "Case #x: y", where x is the
 * case number (starting from 1), and y is the number of recycled pairs (n, m)
 * with A â¤ n < m â¤ B.
 * 
 * Limits
 * 
 * 1 â¤ T â¤ 50.
 * 
 * A and B have the same number of digits.

Small dataset

1 â¤ A â¤ B â¤ 1000.

Large dataset

1 â¤ A â¤ B â¤ 2000000.

Sample


Input 
 	
Output 
 
4
1 9
10 40
100 500
1111 2222
Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287
 */

package google.codejam.y2012.qualifications;

import google.codejam.commons.Utils;

import java.io.IOException;
import java.util.StringTokenizer;

/**
 * @author Marco Lackovic <marco.lackovic@gmail.com>
 * @version 1.0, Apr 14, 2012
 */
public class RecycledNumbers {

	private static final String INPUT_FILE_NAME = "C-large.in";
	private static final String OUTPUT_FILE_NAME = "C-large.out";

	public static void main(String[] args) throws IOException {
		String[] input = Utils.readFromFile(INPUT_FILE_NAME);
		String[] output = new String[input.length];
		int x = 0;
		for (String line : input) {
			StringTokenizer st = new StringTokenizer(line);
			int a = Integer.valueOf(st.nextToken());
			int b = Integer.valueOf(st.nextToken());
			System.out.println("Computing case #" + (x + 1));
			output[x++] = "Case #" + x + ": " + recycledNumbers(a, b);
		}
		Utils.writeToFile(output, OUTPUT_FILE_NAME);
	}

	private static int recycledNumbers(int a, int b) {
		int count = 0;
		for (int n = a; n < b; n++) {
			count += getNumGreaterRotations(n, b);
		}
		return count;
	}

	private static int getNumGreaterRotations(int n, int b) {
		int count = 0;
		char[] chars = Integer.toString(n).toCharArray();
		for (int i = 0; i < chars.length; i++) {
			chars = rotateRight(chars);
			if (chars[0] != '0') {
				int m = Integer.valueOf(new String(chars));
				if (n == m) {
					break;
				} else if (n < m && m <= b) {
					count++;
				}
			}
		}
		return count;
	}

	private static char[] rotateRight(char[] chars) {
		char last = chars[chars.length - 1];
		for (int i = chars.length - 2; i >= 0; i--) {
			chars[i + 1] = chars[i];
		}
		chars[0] = last;
		return chars;
	}

}

package codejam;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;


public abstract class CodeJam {
	
	protected BufferedReader reader;
	protected FileWriter writer;
	
	//used in multithread mode
	protected String[] inputLines;
	protected String[] outputLines;
	protected int linesPerCase;
	long start;
	
	protected String caseLabel = "Case #";
	
	protected boolean runningMultiThread = false;
	
	public CodeJam(String file) throws Exception {
		this(file, -1);
	}
	
	public CodeJam(String file, int linesPerCase) throws Exception {
		start = System.currentTimeMillis();
		
		this.linesPerCase = linesPerCase;
		FileReader fileReader = new FileReader(new File(file));
		reader = new BufferedReader(fileReader);
		File outFile = new File(file.replaceAll("\\.\\w+$", ".out"));
		outFile.delete();
		writer = new FileWriter(outFile);
		
	}

	public void start() throws IOException,
			InterruptedException {
		String readLine = reader.readLine();
		//total number of cases
		int t = Integer.parseInt(readLine);
		
		int threads = 1;
		if (linesPerCase > 0) {
			runningMultiThread = true;
			loadInputLines(t*linesPerCase);
			outputLines = new String[t];
			threads = 4;
		}
		ExecutorService newCachedThreadPool = Executors.newCachedThreadPool();
		
		for (int i = 0; i < threads; i++) {
			newCachedThreadPool.execute(new CaseProcessor(i*t/threads+1, (i+1)*t/threads));
		}
		newCachedThreadPool.shutdown();
		newCachedThreadPool.awaitTermination(8*60*1000, TimeUnit.MILLISECONDS);

		if (runningMultiThread) {
			for (int i = 0; i < outputLines.length; i++) {
				writer.write(outputLines[i]);
			}
		}
		writer.flush();
		
		long delay = System.currentTimeMillis() - start;
		
		if (delay < 5000) {
			System.out.println("Total time "+delay+ " millis");
		} else {
			System.out.println("Total time "+(delay/1000)+ " secs");
		}
		
		System.exit(0);
	}
	
	class CaseProcessor implements Runnable {
		
		int firstCase;
		int lastCase;
		
		public CaseProcessor(int firstCase, int lastCase) {
			this.firstCase = firstCase;
			this.lastCase = lastCase;
		}

		public void run() {
			for (int i = firstCase; i <= lastCase; i++) {
				Object result;
				try {
					result = processCase(i);
					writeCaseResult(i, result);
				} catch (Exception e) {
					e.printStackTrace();
				}
				
				if (i%10 == 0) {
					long timeRemaing = (System.currentTimeMillis() - start)/i * (lastCase-i);
					if (timeRemaing < 5000) {
						System.out.println(i*100f/lastCase+" % Complete (Time remaing: "+timeRemaing+" millis)");
					} else {
						System.out.println(i*100f/lastCase+" % Complete (Time remaing: "+timeRemaing/1000+" secs)");
					}
				}
			}
			System.out.println("Finish"+firstCase);
		}
		
	}
	
	private void loadInputLines(int lines) throws IOException {
		inputLines = new String[lines];
		for (int i = 0; i < lines; i++) {
			inputLines[i] = reader.readLine();
		}
		reader.close();
		reader = null;
	}

	public final String readLine() throws IOException {
		return reader.readLine();
	}
	
	public final int readLineInt() throws IOException {
		return Integer.parseInt(reader.readLine());
	}
	
	public final String readLine(int caseNumber, int i) {
		return inputLines[(caseNumber-1)*linesPerCase+i];		
	}
	
	public final int[] readIntArray(int caseNumber, int line) {
		String[] numbers = readLine(caseNumber, line).split(" ");
		int[] n = new int[numbers.length];
		
		for (int i = 0; i < numbers.length; i++) {
			n[i] = Integer.parseInt(numbers[i]);
		}
		return n;
	}
	
	public final Integer[] readIntegerArray(int caseNumber, int line) {
		String[] numbers = readLine(caseNumber, line).split(" ");
		Integer[] n = new Integer[numbers.length];
		
		for (int i = 0; i < numbers.length; i++) {
			n[i] = Integer.parseInt(numbers[i]);
		}
		return n;
	}
	
	@SuppressWarnings("unchecked")
	public static <T> T[] reverse(T[] arr) {
		List<T> list = Arrays.asList(arr);
		Collections.reverse(list);
		return (T[]) list.toArray(new Object[arr.length]);
	}
	
	public static void reverse(char[] data) {
	    int left = 0;
	    int right = data.length - 1;

	    while( left < right ) {
	        // swap the values at the left and right indices
	        char temp = data[left];
	        data[left] = data[right];
	        data[right] = temp;

	        // move the left and right index pointers in toward the center
	        left++;
	        right--;
	    }
	}

	protected void writeCaseResult(int caseNumber, Object result) throws IOException {
		StringBuilder out = new StringBuilder(caseLabel);//"Case #"
		out.append(caseNumber);
		out.append(": ");
		out.append(result);
		out.append('\n');
		System.out.println(out);
		if (runningMultiThread) {
			outputLines[caseNumber-1] = out.toString();
		} else {
			writer.write(out.toString());
		}
	}
	
	public long convetNumber(int number, int currentBase, int destBase) {
		long result = 0;
		
		int count = 0;
		
		while (number > 0) {
			int remainder = number % destBase;
			
			number /= destBase;
			
			int current = remainder*(int)Math.pow(currentBase,count);
			result += current;
			count++;
		}
		
		return result;
	}
	
	public abstract Object processCase(int caseNumber) throws Exception;
	
}
