GoodNumbers

import java.io.*;
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import java.math.BigInteger;
/*
Question : Find Smallest Possible Good Numbers.A number is termed as a “GOOD NUMBER” if meets the 2 criteria’s mentioned below;
a. All the digits in the number must be only 1 or 2 or 3
b. No two adjacent substrings of the number is same
Example for good numbers: 1, 121, 1213, 1213121
Example for bad numbers: 11, 1212, 1221, 1231231
11 is a bad number because 1 follows 1.Similarly, 1212 is bad because the substring “12” is present adjacent to the substring “12” 1221 is a bad number because the substring “2” follows “2”
1231231 is a bad number because the substring “123” is adjacent to substring “123”
Design an algorithm to accept an input value N (which is a positive non-zero number). The algorithm must then find out the smallest good number which can be formed and has only N digits in it. The number must be displayed as output.
For Example – If the value on N entered by the user is 4
The smallest possible good number which can be formed having 4 digits is 1213
*/
class GoodNumbers
{
    String res = "";
    void run() {
        dfs("",new int[]{1,2,3},ni());
        out.println(res);
        out.close();
    }
    boolean dfs(String s,int a[],int n) {
        if(s.length()==n) return true;
        boolean b=false;
        for(int i:a) if(isValid(s,i) && dfs(s+i,a,n)) { res=i+res; b=true; break; }
        return b;
    }
    boolean isValid(String s, int i) {
        if(s.length()==0) return true;
        int l=1,n=s.length();
        boolean b=true;
        while(l<=(n+1)>>1 && b) {
            if(s.substring(n-l+1-l,n-l+1).compareTo(s.substring(n-l+1)+i)==0) b=false;
            l++;
        }
        return b;
    }
    public static void main(String[] args)throws Exception {
        try {
            // new Thread(null, new GoodNumbers()::run, "1", 1 << 26).start();
            new Thread(null, new GoodNumbers("ONLINE_JUDGE")::run, "1", 1 << 26).start();
        } catch(Exception e) {}
    }
    FastReader sc=null;PrintWriter out = null;
    public GoodNumbers()throws Exception {
        sc = new FastReader(new FileInputStream("D:\\CP\\input.txt"));
        out = new PrintWriter(new BufferedWriter(new FileWriter("D:\\CP\\output.txt")));
    }
    public GoodNumbers(String JUDGE) {
        sc = new FastReader(System.in);
        out = new PrintWriter(System.out);
    }

    String ns() { return sc.next(); }
    int ni() { return sc.nextInt(); }
    long nl() { return sc.nextLong(); }
    int[] ni(int n) {
        int a[]=new int[n];
        for(int i=0;i<n;a[i++]=ni());
        return a;
    }
    long[] nl(int n) {
        long a[]=new long[n];
        for(int i=0;i<n;a[i++]=nl());
        return a;
    }

    int[][] ni(int n,int m) {
        int a[][]=new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                a[i][j]=ni();
        return a;
    }
    long[][] nl(int n,int m) {
        long a[][]=new long[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                a[i][j]=nl();
        return a;
    }
    int gcd(int a, int b) {
        return b==0?a:gcd(b,a%b);
    }
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;
        public FastReader(InputStream stream) {
            this.stream = stream;
        }
        public int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res = res*1L*10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res *1L* sgn;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c) {
            if (filter != null) return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}