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

public class TestsGen {

	static final Random rnd = new Random(556668949239L);

	static String str =  "../tests/";

	static TestWriter testWriter = new TestWriter(true);

	static class RevolutionTest {
		int n;
		int k;
		String s;

		public RevolutionTest(int n, int k, int[] a) {
			this.n = n;
			this.k = k;
			StringBuilder sb = new StringBuilder("");
			for (int i = 0; i < n; i++) {
				sb.append("" + a[i]);
			}
			s = sb.toString();
		}

		public RevolutionTest(int n, int k, String s) {
			this.n = n;
			this.k = k;
			this.s = s;
		}

		public String toString() {
			return n + " " + k + "\r\n" + s;
		}

	}

	static void genSample() throws IOException {
		testWriter.init(2);
		testWriter.printTest(new RevolutionTest(3, 1, "110"));
		testWriter.printTest(new RevolutionTest(3, 1, "011"));
		testWriter.close();
	}

	private static void generateAllPossible(int l, int r) throws IOException {
		int cnt = 0;
		int agents = 0;
		for (int i = l; i <= r; i++) {
			cnt += i / 2 * (1 << i);
			agents += i / 2 * (1 << i) * i;
		}
		System.err.println(cnt + " " + agents);
		if (agents >= 100000) {
			throw new AssertionError();
		}
		testWriter.init(cnt);
		for (int n = l; n <= r; n++) {
			for (int k = 1; k * 2 <= n; k++) {
				for (int mask = 0; mask < (1 << n); mask++) {
					String str = Integer.toBinaryString(mask);
					while (str.length() < n) {
						str = "0" + str;
					}
					testWriter.printTest(new RevolutionTest(n, k, str));
				}
			}
		}
		testWriter.close();
	}

	private static void generatePossible(int l, int r) throws IOException {
		int cnt = 0;
		int agents = 0;
		for (int i = l; i <= r; i++) {
			cnt += (1 << i);
			agents += (1 << i) * i;
		}
		System.err.println(cnt + " " + agents);
		if (agents >= 100000) {
			throw new AssertionError();
		}
		testWriter.init(cnt);
		for (int n = l; n <= r; n++) {
			for (int mask = 0; mask < (1 << n); mask++) {
				String str = Integer.toBinaryString(mask);
				while (str.length() < n) {
					str = "0" + str;
				}
				testWriter.printTest(new RevolutionTest(n,
						rnd.nextInt(n / 2) + 1, str));
			}
		}
		testWriter.close();
	}

	private static int[] randomVector(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = rnd.nextInt(2);
		}
		return a;
	}

	private static int[] same(int n, int val) {
		int[] a = new int[n];
		Arrays.fill(a, val);
		return a;
	}

	private static int[] mirrored(int n, int val, int coef) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			if (i / coef % 2 == 0) {
				a[i] = val;
			} else {
				a[i] = 1 - val;
			}
		}
		return a;
	}

	private static int[] changed(int n, int val) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			if (i % 2 == 0) {
				a[i] = val;
			} else {
				a[i] = 1 - val;
			}
		}
		return a;
	}

	private static int[] sparsed(int n, int step) {
		int[] a = new int[n];
		for (int i = step; i < n; i += step) {
			a[i] = a[i - 1] = 1;
		}
		return a;
	}

	private static int[] someFill(int[] a, int k) {
		int n = a.length;
		for (int i = 0; i < n / 1.5 / k; i++) {
			int l = rnd.nextInt(n);
			int len = rnd.nextInt(k / 2) + k / 2;
			int val = rnd.nextInt(2);
			for (int j = 0; j + l < n && j < len; j++) {
				a[j + l] = val;
			}
		}
		return a;
	}

	private static void genCorrectness() throws IOException {
		generateAllPossible(2, 10);
		generatePossible(11, 12);
		testWriter.init(115);
		for (int i = 0; i < 10; i++) {
			int n = 100;
			testWriter.printTest(new RevolutionTest(n, rnd.nextInt(n / 8 - n
					/ 10)
					+ n / 10, someFill(randomVector(n), n / 5)));
		}
		for (int n : new int[] { 99, 100 }) {
			for (int val : new int[] { n / 4, 1, n / 2, 10 }) {
				testWriter.printTest(new RevolutionTest(n, val, changed(n, 0)));
				testWriter.printTest(new RevolutionTest(n, val, changed(n, 1)));
				testWriter.printTest(new RevolutionTest(n, val, same(n, 0)));
				testWriter.printTest(new RevolutionTest(n, val, same(n, 1)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 0,
						n / 2)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 1,
						n / 2)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 0,
						n / 4)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 1,
						n / 4)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 0,
						n / 6)));
				testWriter.printTest(new RevolutionTest(n, val, mirrored(n, 1,
						n / 6)));
			}
		}
		for (int i = 0; i < 10; i++) {
			testWriter.printTest(new RevolutionTest(100, rnd.nextInt(33) + 1,
					randomVector(100)));
		}
		for (int i = 0; i < 10; i++) {
			if (10 * (i + 1) * 2 <= 100) {
				testWriter.printTest(new RevolutionTest(100, 10 * (i + 1),
						randomVector(100)));
			}
			testWriter.printTest(new RevolutionTest(100, i + 1,
					randomVector(100)));

		}

		testWriter.close();
		testWriter.init(1);
		testWriter.printTest(new RevolutionTest(1000, 5, sparsed(1000, 20)));
		testWriter.close();

	}

	static void genPerfomance() throws IOException {
		int n = 100000;
		for (int i = 0; i < 5; i++) {
			testWriter.printSimpleTest(new RevolutionTest(n, rnd.nextInt(n / 12 - n
					/ 15)
					+ n / 15, someFill(randomVector(n), n / 7)));
		}
		testWriter.printSimpleTest(new RevolutionTest(n, rnd.nextInt(n / 12 - n
				/ 15)
				+ n / 15, randomVector(n)));
		testWriter.printSimpleTest(new RevolutionTest(n,1,same(n, 0)));
		for (int k : new int[]{n/2,1,n/4}) {
			testWriter.printSimpleTest(new RevolutionTest(n,k,mirrored(n,0,n/2)));
			testWriter.printSimpleTest(new RevolutionTest(n,k,mirrored(n,0,n/4)));
			testWriter.printSimpleTest(new RevolutionTest(n, k, changed(n, 0)));			
		}
		testWriter.printSimpleTest(new RevolutionTest(n, 5, sparsed(n, 200)));
	}

	public static void main(String[] args) throws IOException {
		new File("../tests").mkdir();
		genSample();
		genCorrectness();
		genPerfomance();
		return;
	}

	public static class TestWriter {
		private boolean isMultiTest;
		private int done;

		private boolean isOpened;
		private PrintWriter out;
		private int printedTests;
		private int countTests = 0;

		public TestWriter(boolean isMultiTest) {
			this.isMultiTest = isMultiTest;
			this.done = 0;
		}

		public void init(int n) throws FileNotFoundException {
			printedTests = 0;
			if (isOpened) {
				throw new AssertionError("Please close prevoius multitest");
			}
			isOpened = true;
			countTests = n;
			done++;
			out = new PrintWriter(str + ((done < 10) ? "0" : "")
					+ String.valueOf(done));
			if (isMultiTest) {
				out.println(countTests);
			}
		}

		public void close() {
			if (!isOpened) {
				System.err.println("Before closing test was not created");
			}
			isOpened = false;
			if (printedTests != countTests) {
				throw new AssertionError("Wrong number of tests: all: "
						+ countTests + " printed: " + printedTests);
			}
			out.close();
		}

		public void printTest(Object test) throws IOException {
			if (!isMultiTest) {
				throw new AssertionError("Multi test doesn't allowed");
			}
			if (!isOpened) {
				throw new AssertionError("Please create test");
			}
			printedTests++;
			out.println(test.toString());
		}

		public void printSimpleTest(Object test) throws IOException {
			init(1);
			printedTests++;
			out.println(test.toString());
			close();
		}
	}

}
