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

public class TestGen {
    private static int nTests = 0;
    private static Random random = new Random(442);
    private static void write(String word, List<Integer> numbers, boolean greedySolvable) {
        try {
            PrintWriter out = new PrintWriter(String.format("%02d", 1 + nTests));
            out.println(word);
            out.println(numbers.size());
            for (int i = 0; i < numbers.size(); ++i) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(numbers.get(i));
            }
            out.println();
            out.close();
            if (out.checkError()) {
                throw new IOException("Error from PrintWriter");
            }
            ++nTests;

            PrintWriter ruDesc = new PrintWriter(new OutputStreamWriter(
                    new FileOutputStream("tests-ru.desc", nTests > 1), "cp1251"));
            ruDesc.printf("%02d: Случайный тест, слово длиной %d, %d чисел, %s жадным алгоритмом.%n",
                    nTests, word.length(), numbers.size(), greedySolvable ? "решается" : "не решается");
            ruDesc.close();

            PrintWriter enDesc = new PrintWriter(new OutputStreamWriter(
                    new FileOutputStream("tests-en.desc", nTests > 1), "cp1251"));
            enDesc.printf("%02d: Random test with a word of length %d, %d numbers, %s by greedy algorithm.%n",
                    nTests, word.length(), numbers.size(), greedySolvable ? "solvable" : "unsolvable");
            enDesc.close();
            System.out.println("Test " + nTests + " generated");
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    private static boolean greedySolvable(String word, List<Integer> numbers) {
        String[] ns = new String[numbers.size()];
        for (int i = 0; i < ns.length; ++i) {
            ns[i] = String.valueOf(numbers.get(i));
        }
        while (word.length() > 0) {
            int best = -1;
            for (int i = 0; i < ns.length; ++i) {
                if (ns[i] != null && word.startsWith(ns[i])) {
                    if (best == -1 || ns[i].length() > ns[best].length()) {
                        best = i;
                    }
                }
            }
            if (best == -1) {
                return false;
            }
            String t = ns[best];
            ns[best] = null;
            word = word.substring(t.length());
        }
        return true;
    }

    private static void generateRandom(int wordLength, int numberCount, boolean greedyMaySolve) {
        String word;
        List<Integer> numbers = new ArrayList<Integer>();
        Set<Integer> numberSet = new HashSet<Integer>();
        do {
            boolean bad;
            do {
                StringBuilder wordSrc = new StringBuilder();
                for (int i = 0; i < wordLength; ++i) {
                    if (i == 0) {
                        wordSrc.append((char) ('1' + random.nextInt(9)));
                    } else {
                        wordSrc.append((char) ('0' + random.nextInt(10)));
                    }
                }
                word = wordSrc.toString();
                bad = false;
                System.out.print(">");
                numbers.clear();
                numberSet.clear();
                int prev = 0;
                loop:
                while (prev < word.length()) {
                    int length;
                    int value;
                    System.out.print("-");
                    int count = 0;
                    do {
                        ++count;
                        if (count == 1000) {
                            bad = true;
                            break loop;
                        }
                        if (numberCount > numbers.size()) {
                            int minimalLength = (word.length() - prev) / (numberCount - numbers.size());
                            int maximalLength = 3;
                            minimalLength = Math.max(1, minimalLength);
                            if (maximalLength - minimalLength + 1 <= 0) {
                                bad = true;
                                break loop;
                            }
                            length = minimalLength + random.nextInt(maximalLength - minimalLength + 1);
                        } else {
                            length = 1 + random.nextInt(3);
                        }
                        if (prev + length > word.length()) {
                            length = word.length() - prev;
                        }
                        if (word.charAt(prev) == '0') {
                            length = 1;
                        }
                        value = Integer.parseInt(word.substring(prev, prev + length));
                    } while (numberSet.contains(value));
                    System.out.print("|");
                    numbers.add(value);
                    numberSet.add(value);
                    prev += length;
                }
            } while (numbers.size() > numberCount || bad);
            while (numbers.size() < numberCount) {
                int value;
                do {
                    value = random.nextInt(1000);
                } while (numberSet.contains(value));
                numbers.add(value);
                numberSet.add(value);
            }
            Collections.shuffle(numbers, random);
        } while (!greedyMaySolve && greedySolvable(word, numbers));
        write(word, numbers, greedyMaySolve);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; ++i) {
            generateRandom(i + 5, 8, i < 9 || i == 19);
        }
        for (int i = 0; i < 15; ++i) {
            generateRandom(30, 900, false);
        }
        for (int i = 0; i < 15; ++i) {
            generateRandom(45, 990, false);
        }
    }
}
