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

public class SeqTestGen {

    static int done = 0;

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

    static PrintWriter out;
    
        
    
    static void printTest(int n,int h, int[] a, String testName) throws FileNotFoundException {
        done++;
        if (done < 10)
            out = new PrintWriter("../tests/0" + String.valueOf(done));
        else
            out = new PrintWriter("../tests/" + String.valueOf(done));
        out.println(n+" "+h);
        for (int i = 0; i < n - 1; i++) {
            out.print(a[i] + " ");
        }
        out.println(a[n - 1]);
        out.close();
        System.err.println();
    }

    
    void genSample() throws IOException {
        printTest(4,3,new int[]{1,1,0,2 },"sample 1");
        printTest(3,3,new int[]{ 1, 3,2 },"sample 2");
    }
    
    void generateSmall() throws FileNotFoundException {
        printTest(1,1,new int[]{1},"small");
        printTest(1,1,new int[]{0},"small");
        printTest(4,2,new int[]{1,2,4,0},"small");
    }
    
    void generateZeros(int n, int cons) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = cons;
        }
        printTest(n,n/2,a,"const = "+cons);
    }
    
    void generateFull(int n) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = i;
        }
        printTest(n,n/2,a,"a[i] = i");
    }
    
    void generateRandom(int n,int h, int k) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = rand.nextInt(k);
        }
        printTest(n,h,a,"Full random a[i] < "+k);
    }
    
    void generateProbRandom(int n, double percent) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 1; i < n; i++) {
            if (rand.nextDouble() < percent) {
                a[i] = a[i-1]+1;
            } else {
                a[i] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] > 2) {
                a[i] -= rand.nextInt(4);
            }
        }
        printTest(n,(int)(percent*n), a,"Probability = "+percent);      
    }
    
    void generateRandomWithPeaks(int n, int peaks, int h) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          if (rand.nextDouble() >0.9) {
              a[i] = 2;
          }else {
              a[i] = rand.nextInt(2);
          }
        }   
        for (int i = 0; i < peaks; i++) {
            a[rand.nextInt(n)] = h;
        }
        printTest(n,h,a,"Peaks = "+peaks);
    }
    
    void generateCrackWa1(int n, int h) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = rand.nextInt(2);
        }
        for (int it = 0; it < h; it++) {
            int pos = rand.nextInt(n-h-4);
            for (int i = 0; i < h; i++) {
                a[pos+i] = i;
            }
            a[pos+h+1+rand.nextInt(2)] = h+5;
        }
        for (int i = 0 ; i < n; i++) {
            if (a[i] > 3 && a[i] < h) {
                a[i] -= rand.nextInt(2); 
            }
        }
        printTest(n,h,a,"Crack1Wa");
    }
    
    public void generateStrange(int n, int h) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i*h < n; i++) {
            a[i*h] = n;         
        }
        printTest(n,h,a,"StrangType1");
    }

    public void generateAnotherStrange(int n, int h) throws FileNotFoundException {
        int[] a = new int[n];
        a[h] = n;
        a[2*h+1]=n;
        for (int i = 3; i*h < n; i++) {
            a[i*h] = n;         
        }
        printTest(n,h,a,"StrangType2");
    }
    
    public void generateSlowAndWrong(int n, int h) throws FileNotFoundException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            if (i / h %2 == 0) {
                if (rand.nextBoolean()) {
                    a[i] = rand.nextInt(h);
                }
            } else {
                a[i] = rand.nextInt(2);
            }
        }
        printTest(n,h,a,"Slow and Wrong");
    }

    
    
    void generate(int n) throws FileNotFoundException {
        generateZeros(n,0);
        generateZeros(n,n/2);
        generateFull(n);
        for (int i = 0; i < 2; i++) {
            generateRandom(n,n/10,10);
        }
        for (int i = 0; i < 2; i++) {
            generateProbRandom(n,0.4);
            generateProbRandom(n,0.5);
            generateProbRandom(n,0.9);  
        }
        generateRandomWithPeaks(n,40,n/40);
        generateRandomWithPeaks(n,40,n/40);
        generateCrackWa1(n, n/38);
        generateCrackWa1(n, n/38);
        generateStrange(n,n/20);
        generateAnotherStrange(n,n/20);
        generateSlowAndWrong(n,n/10);
        generateSlowAndWrong(n,n/10);

    }



    public void run() throws IOException {
        new File("../tests").mkdir();
        genSample();
        generateSmall();
        generate(300);
        generate(200000);
    }

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