package dataStructures;

class Matrix {

  private static int nDigits(int n) {
    boolean signal = n<0;
    if (n==0) return 1;
    return ((int)Math.ceil(Math.log(Math.abs(n)+1) / Math.log(10))) + (signal?1:0);
  }

  public static void printMatrix( int[][] m) {

    //find maximum length
    int max=0;

    for (int i=0;i<m.length;i++)
      for(int j=0;j<m[0].length;j++)
        if (max<nDigits(m[i][j]))
          max = nDigits(m[i][j]);

    // number of digits per cell
    for (int i=0;i<m.length;i++) {
      System.out.print("{ ");
      for(int j=0;j<m[0].length;j++) {
        for(int k=0;k<max-nDigits(m[i][j]);k++)
          System.out.print(" ");
        System.out.print(m[i][j]+" ");
      }
      System.out.println("}");
    }
  }

  //*******************************

  public static void multMatrix( int[][] a, int[][] b, int[][] c) {
    for(int i=0;i<a.length;i++)
      for(int j=0;j<b[0].length;j++)
        for(int k=0;k<a[0].length;k++)
           c[i][j] += a[i][k]*b[k][j];
  }

  //*******************************

  public static long ordMatrix( int[] r, int[][] s ) {

    long[][] m = new long[r.length-1][r.length-1];

    for(int DELTA=1;DELTA<r.length-1;DELTA++)
      for(int i=0;i<r.length-1-DELTA;i++) {
        int j = i + DELTA;
        m[i][j] = Long.MAX_VALUE;
        for(int k=i;k<j;k++) {
          long q = m[i][k] + m[k+1][j] + r[i]*r[k+1]*r[j+1];
          if (q<m[i][j]) {
            m[i][j] = q;
            s[i][j] = k;
          }
        }
      }
    return m[0][r.length-2];
  }

  //*******************************

  public static int[][] ordMultMatrix(int [][][] A, int[][] s, int i, int j ) {
    if (j>i) {
      int [][] X = ordMultMatrix(A,s,i,s[i][j]);
      int [][] Y = ordMultMatrix(A,s,s[i][j]+1,j);
      int [][] Z = new int[X.length][Y[0].length];
      multMatrix(X,Y,Z);
      return Z;
    }
    return A[i];
  }

  ///////////////////////////////////////////

  public static long fib1( int n ) {
    long[] solutions = new long[n+1];

    solutions[0] = 1;
    solutions[1] = 1;

    for(int i=2;i<=n;i++)
      solutions[i] = solutions[i-2] + solutions[i-1];

    return solutions[n];
  }

  //*******************************

  private static final int UNKNOWN = -1;

  public static long fib(int n) {

    long[] sols = new long[n+1];

    for(int i=0;i<=n;i++)
      sols[i] = UNKNOWN;

    return fib(sols,n);
  }

  public static long fib( long[] sols, int n ) {
    if (sols[n] != UNKNOWN)
      return sols[n];

    if (n==0 || n==1)
      return sols[n] = 1;

    return sols[n] = fib(sols,n-1) + fib(sols,n-2);
  }

  ///////////////////////////////////////////

  private static int[][] lcsMatrix(String a, String b) {
    int[][] m = new int[a.length()+1][b.length()+1];

    for(int i=1;i<=a.length();i++)
      for(int j=1;j<=b.length();j++)
         if (a.charAt(i-1)==b.charAt(j-1))
           m[i][j] = m[i-1][j-1] + 1;
         else
           m[i][j] = m[i-1][j] >= m[i][j-1] ? m[i-1][j] : m[i][j-1];

    return m;
  }

// using memoization

  private static int[][] lcsMatrix2(String a, String b) {
    int[][] sols = new int[a.length()+1][b.length()+1];

    for(int i=0;i<=a.length();i++)
      for(int j=0;j<=b.length();j++)
        sols[i][j] = UNKNOWN;

    lcsMatrix2Aux(sols,a,b,a.length(),b.length());

    return sols;
  }


  private static int lcsMatrix2Aux(int[][] sols, String a, String b, int n, int m) {

    if (sols[n][m] != UNKNOWN)
      return sols[n][m];

    if (n==0 || m==0)
      return sols[n][m] = 0;

    if (a.charAt(n-1)==b.charAt(m-1))
      sols[n][m] = 1+lcsMatrix2Aux(sols,a,b,n-1,m-1);
    else {
      int n1 = lcsMatrix2Aux(sols,a,b,n,m-1),
          m1 = lcsMatrix2Aux(sols,a,b,n-1,m);
      sols[n][m] = n1>m1 ? n1 : m1;
    }

    return sols[n][m];
  }

  //***************************
  private static String getLcsAux(String a, int[][] m, int i, int j) {
    if (i==0 || j==0)
      return "";
    if ((m[i][j] == m[i-1][j-1] + 1) &&
        (m[i][j] >  m[i-1][j]) && (m[i][j] >  m[i][j-1]))
      return getLcsAux(a,m,i-1,j-1) + a.charAt(i-1);
    else
      if (m[i-1][j] >= m[i][j-1])
        return getLcsAux(a,m,i-1,j);
      else
        return getLcsAux(a,m,i,j-1);
  }

  public static String getLcs(String a, String b) {
    return getLcsAux(a,lcsMatrix2(a,b),a.length(),b.length());
  }

  //*******************************

  static int now;

  private static void permutations(String original, char[] s, int k) {

    now++;
    s[k] = original.charAt(now);

    if (now+1==s.length) // print permutation
      System.out.print(String.valueOf(s));

    for(int t=1;t<s.length;t++)
      if (s[t] == 'n')
        permutations(original,s,t);

    s[k] = 'n';
    now--;
  }

  public static void showPermutations(String original) {
    now = -1;

    char[] s = new char[original.length()+1];
    for(int i=0;i<=original.length();i++)
      s[i] = 'n';

    permutations(" "+original,s,0);
  }

  //*******************************

  /**
   * Verifica se o 1º jogador ganha
   * @param N     O número de pedras inicial da mesa
   * @param moves Quais as jogadas possíveis (inclui 1)
   * @return      TRUE se o 1º jogador ganha, FALSE c.c.
   */
  public static boolean bachet(int N, int[] moves) {
    boolean[] s = new boolean[N+1];

    for(int i=1;i<=N;i++) {
      for(int j=0;j<moves.length;j++)
        if (i>=moves[j] && !s[i-moves[j]]) {
          s[i] = true;
          break;
        }
    }
    return s[N];
  }

  /**
   * Verifica se o proximo jogador ganha - SOLUÇAO EXPONENCIAL
   * @param N     O número de pedras inicial da mesa
   * @param moves Quais as jogadas possíveis (inclui 1)
   * @return      TRUE se o proximo jogador ganha, FALSE c.c.
   */
  public static boolean bachet2(int N, int[] moves) {

    for(int i=0;i<moves.length;i++)
      if (N==moves[i] || (N>=moves[i] && !bachet2(N-moves[i],moves)))
        return true;

    return false;
  }

  /**
   * Verifica se o proximo jogador ganha - SOLUÇAO COM MEMORIZAÇÃO
   * @param N     O número de pedras inicial da mesa
   * @param moves Quais as jogadas possíveis (inclui 1)
   * @return      TRUE se o proximo jogador ganha, FALSE c.c.
   */
  public static boolean bachet3(int N, int[] moves) {
    int[] sols = new int[N+1];

    for(int i=0;i<=N;i++)
      sols[i] = UNKNOWN;

    boolean b = b3(N,moves,sols);

    for(int i=0;i<sols.length;i++)
      System.out.print(sols[i]+",");

    return b;
  }

  public static boolean b3(int N, int[] moves, int[] sols) {
    if (sols[N] != UNKNOWN)
      return sols[N]==1;

    for(int i=0;i<moves.length;i++)
      if (N==moves[i] || (N>=moves[i] && !b3(N-moves[i],moves,sols))) {
          sols[N] = 1;
          return true;
        }

    sols[N] = 0;
    return false;
  }


  //*******************************

  public static void main(String[] args) {

    int[] m = {4, 7};

    bachet3(12,m);

/*    for (int i=1;i<10;i++) {
      System.out.print((bachet(i,m)?"Primeiro":"Segundo"));
      System.out.print((bachet2(i,m)?"/Primeiro":"/Segundo"));
      System.out.println((bachet3(i,m)?"/Primeiro":"/Segundo"));
    }
*/
//  showPermutations("abcd");
//    System.out.println(fib(2));

/*    int[][] A0 = { {0,1,2}, {1,2,3} };  //2x3
    int[][] A1 = { {0,1,2}, {1,2,3}, {2,3,4} };  //3x3
    int[][] A2 = { {0,1,2,3}, {1,2,3,4}, {2,3,4,5} };  //3x4
    int[][] A3 = { {1,2,3}, {2,3,4}, {3,4,5}, {4,5,6} };  //4x3
    int[][] A4 = { {1,2}, {2,3}, {3,4} };  //3x2

    int[] r = {2, 3, 3, 4, 3, 2};  //2x3 3x3 3x4 4x3 3x2
    int[][] s = new int[r.length-1][r.length-1];

    System.out.println(ordMatrix(r,s));

    int[][][] A = { A0, A1, A2, A3, A4 };

    int[][] R = ordMultMatrix(A,s,0,3);
*/
//    printMatrix(lcsMatrix("abcdefghijklmnopqsrtuv","beghijkmnoooo"));
/*
    String a = "abcdefg";
    String b = "efaefg";

    int s[][];

    s = lcsMatrix(a,b);
    printMatrix(s);

    s = lcsMatrix2(a,b);
    printMatrix(s);

    System.out.println(getLcs(a,b));
*/
    System.out.println(fib1(100) + ":" + fib(100));

  }
}