import java.io.*;
import java.util.*;

public class TestGen {

	PrintWriter out;
	Random rnd;
	int tNumber;

	class Country {
		ArrayList<String> cities;
		String code;

		public Country(String s, Collection<String> hs) {
			code = s;
			cities = new ArrayList<>(hs);
		}

		@Override
		public String toString() {
			StringWriter res = new StringWriter();
			PrintWriter out = new PrintWriter(res);
			out.println(code + " " + cities.size());
			Collections.shuffle(cities, rnd);
			for (String c : cities) {
				out.println(c);
			}
			return res.toString();
		}
	}

	class Test {

		ArrayList<Country> countries;
		ArrayList<String> numbers;

		void printTest(int screwedCount, int maxScrewSize) throws IOException {
			if (tNumber < 10)
				out = new PrintWriter("../tests/0" + tNumber);
			else
				out = new PrintWriter("../tests/" + tNumber);
			System.err.println("Test " + tNumber + " OK");
			tNumber++;
			Collections.shuffle(countries, rnd);
			Collections.shuffle(numbers, rnd);
			out.println(countries.size());
			for (Country c : countries) {
				out.print(c);
			}
			out.println(numbers.size());
			for (int i = 0; i < screwedCount; i++) {
				int id = rnd.nextInt(numbers.size());
				numbers.set(id, screwUp(numbers.get(id), maxScrewSize));
			}
			for (String n : numbers) {
				out.println(n);
			}
			out.close();
		}

		private String screwUp(String string, int maxScrewSize) {
			char[] res = string.toCharArray();
			int cnt = rnd.nextInt(maxScrewSize + 1);
			for (int i = 0; i < cnt; i++) {
				int ind = rnd.nextInt(res.length);
				if (ind > 0)
					res[ind] = (char) ('0' + rnd.nextInt(10));
				else
					res[ind] = (char) ('1' + rnd.nextInt(9));
			}
			return new String(res);
		}

		public void generateSomethingInteresting(int numberCount,
				int maxErrCount, int screwedCount, int maxScrewSize)
				throws IOException {
			String thatWeWillChange = randString(11);
			numbers = new ArrayList<String>();
			for (int i = 0; i < numberCount; i++) {
				char[] addon = thatWeWillChange.toCharArray();
				int errCount = rnd.nextInt(maxErrCount) + 1;
				for (int j = 0; j < errCount; j++) {
					int ind = rnd.nextInt(11);
					if (ind == 0)
						addon[ind] = (char) ('1' + rnd.nextInt(9));
					else
						addon[ind] = (char) ('0' + rnd.nextInt(10));
					numbers.add(new String(addon));
				}
			}
			genPossibleCodes();
			printTest(screwedCount, maxScrewSize);
		}

		private void genPossibleCodes() {
			HashMap<String, HashSet<String>> hm = new HashMap<>();
			HashSet<String> alreadyBad = new HashSet<String>();
			ArrayList<String> newNumbers = new ArrayList<String>();
			for (String n : numbers) {
				if (!contains(hm, n)) {
					int l1 = 1 + rnd.nextInt(3);
					int it = 0;
					while (n.charAt(l1) == '0') {
						l1 = 1 + rnd.nextInt(3);
						it++;
						if (it > 100)
							break;
					}
					if (it > 100)
						continue;
					if (hm.size() == 100)
						continue;
					int l2 = 3 + rnd.nextInt(3);

					it = 0;
					while (alreadyBad.contains(n.substring(0, l2))) {
						l1 = 1 + rnd.nextInt(3);
						while (n.charAt(l1) == '0')
							l1 = 1 + rnd.nextInt(3);
						l2 = 3 + rnd.nextInt(3);
						it++;
						if (it > 100)
							break;
					}
					// it2++;
					// System.err.println(it2 + " " + numbers.size());
					if (it > 100)
						continue;
					if (!hm.containsKey(n.substring(0, l1))) {
						hm.put(n.substring(0, l1), new HashSet<String>());
					}
					if (hm.get(n.substring(0, l1)).size() == 100) {
						continue;
					}
					hm.get(n.substring(0, l1)).add(n.substring(l1, l1 + l2));
					addAll(alreadyBad, n.substring(0, l1 + l2));
					newNumbers.add(n);
				}
			}
			numbers = newNumbers;

			convert(hm);
		}

		private void convert(HashMap<String, HashSet<String>> hm) {
			countries = new ArrayList<TestGen.Country>();
			for (String s : hm.keySet()) {
				countries.add(new Country(s, hm.get(s)));
			}
		}

		private boolean contains(HashMap<String, HashSet<String>> hm, String n) {
			for (int l1 = 1; l1 < 4; l1++) {
				for (int l2 = 3; l2 < 6; l2++) {
					if (hm.containsKey(n.substring(0, l1))
							&& hm.get(n.substring(0, l1)).contains(
									n.substring(l1, l1 + l2)))
						return true;
				}
			}
			return false;
		}

		public void genNonContradictoryRandom(int countryCount,
				int minCountrySize, int maxCountrySize, int numberCount,
				int minCountryLength, int maxCountryLength, int minCityLength,
				int maxCityLength, int screwedCount, int maxScrewSize)
				throws IOException {
			HashSet<String> alreadyBad = new HashSet<String>();
			HashSet<String> alreadyVeryBad = new HashSet<String>();
			countries = new ArrayList<TestGen.Country>();
			HashSet<String> existingCountries = new HashSet<String>();
			for (int i = 0; i < countryCount; i++) {
				int len = randNumber(minCountryLength, maxCountryLength);
				String code = randString(len);
				int it = 0;
				while (existingCountries.contains(code)) {
					len = randNumber(minCountryLength, maxCountryLength);
					code = randString(len);
					it++;
					if (it > 100)
						break;
				}
				if (it > 100)
					continue;
				int size = randNumber(minCountrySize, maxCountrySize);
				ArrayList<String> cities = new ArrayList<String>();
				for (int j = 0; j < size; j++) {
					String city = randString(randNumber(minCityLength,
							maxCityLength));
					while (alreadyBad.contains(code + city)
							|| contains(alreadyVeryBad, code + city)) {
						city = randString(randNumber(minCityLength,
								maxCityLength));
					}
					cities.add(city);
					addAll(alreadyBad, code + city);
					alreadyVeryBad.add(code + city);
					existingCountries.add(code);
				}
				countries.add(new Country(code, cities));
			}
			countryCount = countries.size();
			numbers = new ArrayList<String>();
			for (int i = 0; i < numberCount; i++) {
				int countryId = rnd.nextInt(countryCount);
				String countryName = countries.get(countryId).code;
				int cityId = rnd
						.nextInt(countries.get(countryId).cities.size());
				String cityName = countries.get(countryId).cities.get(cityId);
				String number = countryName
						+ cityName
						+ randString(11 - countryName.length()
								- cityName.length());
				numbers.add(number);
			}

			printTest(screwedCount, maxScrewSize);
		}

		private boolean contains(HashSet<String> hs, String s) {
			for (int i = 1; i <= s.length(); i++) {
				if (hs.contains(s.substring(0, i))) {
					return true;
				}
			}
			return false;
		}

		private void addAll(HashSet<String> alreadyBad, String string) {
			for (int i = 1; i <= string.length(); i++) {
				alreadyBad.add(string.substring(0, i));
			}
		}

		private String randString(int len) {
			String res = "";
			for (int i = 0; i < len; i++) {
				if (i == 0)
					res = res + (char) ('1' + rnd.nextInt(9));
				else
					res = res + (char) ('0' + rnd.nextInt(10));
			}
			return res;
		}

		private int randNumber(int min, int max) {
			return min + rnd.nextInt(max - min + 1);
		}

		public void genBinaryVectors(int screwedCount, int maxScrewSize)
				throws IOException {
			numbers = new ArrayList<String>();
			for (int i = 1 << 10; i < (1 << 11); i++) {
				String s = Integer.toBinaryString(i);
				if (isValid(s)) {
					numbers.add(Integer.toBinaryString(i));
				}
			}
			Collections.shuffle(numbers, rnd);
			genPossibleCodes();
			printTest(screwedCount, maxScrewSize);
		}

		private boolean isValid(String s) {
			int t = 1;
			while (t < s.length() && s.charAt(t) == '0')
				t++;
			return t <= 3;
		}
	}

	public void solve() throws IOException {
		printSample();
		tNumber = 2;
		rnd = new Random(31);
		Test t = new Test();

		// tests 02 - 04
		t.genNonContradictoryRandom(1, 1, 1, 1, 1, 1, 3, 3, 0, 1);
		t.genNonContradictoryRandom(1, 1, 1, 1, 1, 1, 3, 3, 1, 1);
		t.genNonContradictoryRandom(1, 1, 1, 1, 1, 1, 3, 3, 1, 2);

		// tests 05 - 10
		for (int screwedCount : new int[] { 0, 10, 100 }) {
			for (int maxScrewSize : new int[] { 1, 3 }) {
				t.genBinaryVectors(screwedCount, maxScrewSize);
			}
		}

		// tests 11 - 15
		t.genNonContradictoryRandom(100, 1, 100, 10000, 1, 3, 3, 5, 10, 1);
		t.genNonContradictoryRandom(10, 1, 10, 10000, 1, 1, 3, 4, 10, 2);
		t.genNonContradictoryRandom(100, 1, 100, 10000, 3, 3, 5, 5, 0, 1);
		t.genNonContradictoryRandom(10, 1, 100, 10000, 1, 1, 5, 5, 0, 1);
		t.genNonContradictoryRandom(10, 1, 10, 10000, 3, 3, 3, 3, 10, 5);

		// tests 16 - 19
		t.generateSomethingInteresting(10000, 1, 0, 1);
		t.generateSomethingInteresting(10000, 3, 0, 1);
		t.generateSomethingInteresting(10000, 3, 10, 10);
		t.generateSomethingInteresting(10000, 3, 10000, 3);

		// test 20
		t.genNonContradictoryRandom(100, 100, 100, 10000, 1, 3, 3, 5, 0, 1);

        printSpecial();
	}

	private void printSpecial() throws FileNotFoundException {
		out = new PrintWriter("../tests/21");
		String[] test = new String[] {"1", "100 2", "100", "1000", "3", "10010001234", "10010012345", "10010000123"};
		for (String s : test) {
			out.println(s);                                                                 
		}
		out.close();	
	}

	private void printSample() throws FileNotFoundException {
		out = new PrintWriter("../tests/01");
		String[] sample = new String[] { "2", "7 3", "981", "3517", "812",
				"351 3", "34712", "1234", "963", "8", "79818266456",
				"35196328463", "78122472557", "01234567890", "73517960326",
				"35134712239", "35112342013", "78120102030" };
		for (String s : sample) {
			out.println(s);
		}
		out.close();
	}

	public void run() {
		try {

			solve();

		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		new TestGen().run();
	}
}
