/*
 * 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.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;

public class Recycled {

	/**
	 * @param args
	 */
	private boolean[] b;
	private int[] factorial = { 1, 1, 2, 6, 24, 120, 720, 5040 };

	private String in, temp;
	private int count = 0;
	private int total = 0;
	private char[] c;

	public int getMaxRecycle(int min, int max) {
		b = new boolean[max + 1 - min];
		count = 0;
		total = 0;
		for (int i = min; i <= max; i++) {
			if (!b[i - min]) {
				b[i - min] = true;
				total++;
				in = "" + i;
				c = in.toCharArray();
				StringBuilder sb = new StringBuilder(in);
				total = c.length;
				for (int j = 0; j < c.length - 1; j++) {
					sb.append(c[j]);
					if (c[j + 1] != '0') {
						temp = sb.substring(j + 1);
						if (!temp.equals(in)) {
							int pos = Integer.parseInt(temp);
							if (pos <= max && pos >= min && !b[pos - min]) {
								b[pos - min] = true;
							} else {
								total--;
							}
						} else {
							total--;
						}
					} else {
						total--;
					}
				}

				if (total >= 2) {
					count += (factorial[total] / (2 * factorial[total - 2]));
				}
			}
		}
		return count;
	}

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

	public static void main(String[] args) {
		Recycled r = new Recycled();
		long start = System.currentTimeMillis();

		try {
			FileInputStream fstream = new FileInputStream("C-large.in");
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));

			FileWriter fwriter = new FileWriter("C-large.out");
			BufferedWriter out = new BufferedWriter(fwriter);

			String strLine;
			strLine = br.readLine();
			int testCases = Integer.parseInt(strLine);

			int currentCase = 0;
			String[] input;
			int min, max, temp;
			while ((strLine = br.readLine()) != null && currentCase < testCases) {
				input = strLine.split(" ");
				min = Integer.parseInt(input[0]);
				max = Integer.parseInt(input[1]);
				if (min > max) {
					temp = min;
					min = max;
					max = temp;
				}
				out.write("Case #" + ++currentCase + ": "
						+ r.getMaxRecycle(min, max));
				out.newLine();
			}
			System.out.println("Time is: "
					+ (System.currentTimeMillis() - start) * 10E-3 + " Sec.");
			in.close();
			out.close();
		} catch (Exception e) {
			System.err.println("I/O Error while reading file.");
		}
	}
}
