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

public class TestGen {
    int testCount, subtaskCount;
    PrintWriter testsDesc;

    Random random = new Random(787788);
	int MX = 1_000_000;
    
    int[][][] samples = new int[][][]{{{0, 10}, {5, 15}, {10, 10}}};
	int[][][] hand = new int[][][]{
		{{0, 0}, {1, 0}},
		{{0, 0}, {MX, MX}},
		{{0, 100}, {50, 50}, {100, 1}, {150, 150}},
		{{0, 150}, {50, 1}, {100, 50}, {150, 100}}
	};

    void write(int[][] a, String folder, String subtask, int points, String comment) throws IOException {
        String path = String.format("../%s/%02d", folder, ++testCount);
        PrintWriter out = new PrintWriter(path);
        out.println(a.length);
        for (int i = 0; i < a.length; i++) {
            out.print(a[i][0] + " " + a[i][1]);
            out.println();
        }
        out.close();
        testsDesc.println(String.format("%s, folder=%s, subtask=%s, points=%d, comment=%s", path, folder, subtask, points, comment));
		System.out.println(String.format("Test %d is generated", testCount));
    }


    void genPreliminary() throws IOException {
        for (int i = 0; i < samples.length; i++) {
            write(samples[i], "preliminary", "subtask0", 0, String.format("\"sample %d\"", i + 1));
        }
        testCount = 0;
    }

	void genRandom(int n, boolean dummy) throws IOException {
		TreeSet<Integer> st = new TreeSet<Integer>();
		int y0 = random.nextInt(MX + 1);
		int ans[][] = new int[n][2];
		while (st.size() < n) {
		 	int x = random.nextInt(MX + 1);
			st.add(x);
		}
		Iterator<Integer> it = st.iterator();
		int k = 0;
		while (it.hasNext()) {
		 	ans[k][0] = it.next();
			ans[k][1] = dummy ? y0 : random.nextInt(MX + 1);
			k++;
		}
		
		write(ans, "tests", "subtask" + Integer.toString(subtaskCount), 0, String.format("\"random, n=%d\"", n));
	}

	void genA007814(int n, boolean rev) throws IOException {
		int ans[][] = new int[n][2];
		for (int i = 0; i < n; i++) {
			ans[i][0] = i + 1;
			ans[i][1] = 0;
			int k = i + 1;
			while (k % 2 == 0) {
			 	k /= 2;
				ans[i][1]++;
			}
			if (rev) {
			 	ans[i][1] = 50 - ans[i][1];
			}
		}
		
		write(ans, "tests", "subtask" + Integer.toString(subtaskCount), 0, String.format("\"A007814, n=%d\"", n));
	}

	void genHandTests() throws IOException {
		for (int i = 0; i < hand.length; i++) {
			write(hand[i], "tests", "subtask" + Integer.toString(subtaskCount), 0, String.format("\"hand, %d\"", i + 1));
		}
	}

	int rev(int x, int lg) {
	 	int res = 0;
		for (int i = 0; i < lg; i++) {
		 	if ((x & (1 << i)) != 0) {
		 	 	res |= 1 << (lg - i - 1);
			}
		}
		return res;
	}

	void genFFT(int _n) throws IOException {
	 	int n = 1, lg = 1;
		while (n * 2 <= _n) {
		 	n *= 2;
			lg++;
		}
		int ans[][] = new int[n][2];
		int k = random.nextInt(MX / n) + 1;
		for (int i = 0; i < n; i++) {
		 	ans[i][0] = (i + 1) * k;
			ans[i][1] = rev(i, lg);
		}
		write(ans, "tests", "subtask" + Integer.toString(subtaskCount), 0, String.format("\"fft, n=%d\"", n));
	}

    void genSubtask(int n, int points, boolean dummy) throws IOException {
        ++subtaskCount;

		for (int i = 0; i < 5; i++) {
		 	genRandom(n - n / 10 + random.nextInt(n / 10) + 1, dummy);
		}
		genRandom(n, dummy);
		if (!dummy) {
			genHandTests();
			genA007814(n, false);
			genA007814(n, true);
			genFFT(n);
		}
        
        testsDesc.println(String.format("comment_subtask%d=\"n &lt;= %d\"", subtaskCount, n));
        testsDesc.println(String.format("bonus_subtask%d=%d", subtaskCount, points));       
    }

    void run() throws IOException {
        new File("../preliminary").mkdir();
        new File("../tests").mkdir();
        testsDesc = new PrintWriter("../tests.desc");

        genPreliminary();
        genSubtask(300, 30, true);
        genSubtask(300, 30, false);
        genSubtask(2000, 20, false);
        genSubtask(100000, 20, false);

        testsDesc.close();
    }

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