CodeEval - Play with DNA - Hard

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        String line;
        while ((line = in.readLine()) != null) {
            StringTokenizer st=new StringTokenizer(line);
            String pattern=st.nextToken();
            int allowedMiss=Integer.parseInt(st.nextToken());
            String str=st.nextToken();
            LinkedList<Pattern> list=new LinkedList<Pattern>();
            StringBuilder strb=new StringBuilder();
            for(int i=0;i<pattern.length()-1;i++){
                strb.append(str.charAt(i));
            }
            for(int i=pattern.length()-1;i<str.length();i++){
                 strb.append(str.charAt(i));
                 int dist=levenshteinDistance(pattern, strb.toString());
                 if(dist<=allowedMiss){
                     list.add(new Pattern(dist, strb.toString()));
                 }
                 strb.deleteCharAt(0);
            }
            Collections.sort(list);
            boolean first=true;
            while(!list.isEmpty()){
                if(!first){
                    sb.append(' ');
                }
                sb.append(list.remove().getPattern());
                first=false;
            }
            if(first){
                sb.append("No match");
            }
            sb.append('\n');
        }
       
        System.out.print(sb);
    }
   
    private static int minimum(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    public static int levenshteinDistance(String str1,String str2) {
        int[][] distance = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 0; i <= str1.length(); i++)
            distance[i][0] = i;
        for (int j = 1; j <= str2.length(); j++)
            distance[0][j] = j;

        for (int i = 1; i <= str1.length(); i++)
            for (int j = 1; j <= str2.length(); j++)
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1]+ ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));

        return distance[str1.length()][str2.length()];   
    }

}
class Pattern implements Comparable<Pattern> {
    int score;
    String pattern;

    public Pattern(int score, String pattern) {
        this.score = score;
        this.pattern = pattern;
    }
   

    public String getPattern() {
        return pattern;
    }

    public int getScore() {
        return score;
    }

    public void setPattern(String pattern) {
        this.pattern = pattern;
    }

    public void setScore(int score) {
        this.score = score;
    }

    @Override
    public int compareTo(Pattern o) {
        if(this.score<o.getScore())
            return -1;
        if(this.score>o.getScore())
            return 1;
        return this.pattern.compareTo(o.getPattern());
    }
   
   
}

UVA - 231 - Testing the CATCHER

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int i=1;
        while(true){
            int n=Integer.parseInt(br.readLine());
            if(n<0)
                break;
            if(i>1)
                sb.append("\n");
            Vector<Integer> vec=new Vector<Integer>();
            vec.add(n);
            while(true){
                n=Integer.parseInt(br.readLine());
                if(n<0)
                    break;
                vec.add(n);
            }
            sb.append("Test #").append(i).append(":\n");
            sb.append("  maximum possible interceptions: ").append(LDS(vec)).append("\n");
            i++;
        }
        System.out.print(sb);
    }

    static int LDS(Vector<Integer> vec){
        int[]arr=new int[vec.size()];
        arr[0]=1;
        int maxL=0;
        for(int i=1;i<arr.length;i++){
          int maX=0;
          for(int j=0;j<i;j++){
            if(vec.get(j)>vec.get(i) &&arr[j]>maX){
              maX=arr[j];
            }
          }
          arr[i]=maX+1;
          if(arr[i]>maxL){
              maxL=arr[i];
          }
        }
        return maxL;
    }
}

UVA - 10100 - Longest Match

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int cases = 1;
        String m = "";
        while ((m = br.readLine()) != null) {
            if (m.equals("#")) {
                break;
            }
            sb.append(String.format("%2d. ", cases));
            cases++;
            String str = br.readLine();
            if (m.equals("") || str.equals("")) {
                sb.append("Blank!\n");
                continue;
            }
            StringBuilder temp = new StringBuilder();
            LinkedList<String> list=new LinkedList<String>();
            for (int i = 0; i < m.length(); i++) {
                char c = m.charAt(i);
                if (c >= 'a' && c <= 'z') {
                    temp.append(c);
                } else if (c >= 'A' && c <= 'Z') {
                    temp.append(c);
                } else if (c >= '0' && c <= '9') {
                    temp.append(c);
                } else {
                    if (!temp.toString().equals("")) {
                        list.add(temp.toString());
                        temp = new StringBuilder();
                    }
                }
            }
            if (!temp.toString().equals("")) {
                list.add(temp.toString());
            }
            LinkedList<String> list2=new LinkedList<String>();
            temp = new StringBuilder();
            int counter = 0;
            HashSet<String> tempSet = new HashSet<String>();
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (c >= 'a' && c <= 'z') {
                    temp.append(c);
                } else if (c >= 'A' && c <= 'Z') {
                    temp.append(c);
                } else if (c >= '0' && c <= '9') {
                    temp.append(c);
                } else {
                    if (!temp.toString().equals("")) {
                        list2.add(temp.toString());
                        temp = new StringBuilder();
                    }
                }
            }
            if (!temp.toString().equals("")) {
                list2.add(temp.toString());
            }
            String[]arr=new String[list.size()],arr2=new String[list2.size()];
            int index=0;
            while(!list.isEmpty()){
                arr[index]=list.remove();
                index++;
            }
            index=0;
            while(!list2.isEmpty()){
                arr2[index]=list2.remove();
                index++;
            }
            sb.append("Length of longest match: ").append(LCS(arr, arr2)).append("\n");
        }
        System.out.print(sb);
    }
   
    static int LCS(String[] m, String[] n) {
        int[][] arr = new int[m.length + 1][n.length + 1];
        for (int i = 0; i < m.length + 1; i++) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < n.length + 1; i++) {
            arr[0][i] = 0;
        }
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < n.length; j++) {
                if (m[i].equals(n[j])) {
                    arr[i + 1][j + 1] = arr[i][j] + 1;
                }else{
                   arr[i+1][j+1]=Math.max(arr[i+1][j],arr[i][j+1]);
                }
            }
        }
        return arr[m.length][n.length];
    }
}

UVA - 10891 - Game of Sum

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String m="";
        while(true){
            int n=Integer.parseInt(br.readLine());
            if(n==0){
                break;
            }
            StringTokenizer str=new StringTokenizer(br.readLine());
            int[]arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=Integer.parseInt(str.nextToken());
            }
            long[][]dp=new long[n][n];
            for(int i=0;i<n;i++){
               for(int j=0;j<n;j++){
                   dp[i][j]=Long.MIN_VALUE;
                }
            }
            sb.append(maxSum(0, n-1, arr, dp)).append("\n");
        }
        System.out.print(sb);
    }
 
    static long maxSum(int i,int j,int[] arr,long[][]dp){
        if(i==j)
            return arr[i];
        if(dp[i][j]>Long.MIN_VALUE){
            return dp[i][j];
        }
        long sum=0;
        long value=Long.MIN_VALUE;
        for(int k=i;k<j;k++){
            sum+=arr[k];
            value=Math.max(value,sum-maxSum(k+1, j, arr, dp));
        }
        value=Math.max(value,sum+arr[j]);
        sum=0;
        for(int k=j;k>i;k--){
            sum+=arr[k];
            value=Math.max(value,sum-maxSum(i, k-1, arr, dp));
        }
        dp[i][j]=Math.max(value,sum+arr[i]);
        return dp[i][j];
    }
}

UVA - 481 - What Goes Up

#include <vector>
#include <cstdio>

using namespace std;

void LIS(vector<int> &input, vector<int> &lis){
    vector<int> temp(input.size());
    lis.push_back(0);
    int s, e;
    for (size_t i = 1; i < input.size(); i++){
        if (input[lis.back()] < input[i]){
            temp[i] = lis.back();
            lis.push_back(i);
            continue;
        }
        s = 0;
        e = lis.size()-1;
        while (s < e){
            int m = (s + e) / 2;
            if (input[lis[m]] < input[i])
                s=m+1;
            else
                e=m;
        }
        if (input[i] < input[lis[s]]){
            if (s > 0)
                temp[i] = lis[s-1];
            lis[s] = i;
        }
    }
    for (s = lis.size(), e = lis.back(); s--; e = temp[e])
        temp[s] = e;
}


int main()
{
    int x;
    vector<int> seq;
    while(scanf("%d",&x)==1){
        if(x==22)
            break;
        seq.push_back(x);
    }
    vector<int> lis;
    LIS(seq, lis);
    printf("%d\n-\n", lis.size());
    for (unsigned int i = 0; i < lis.size(); i++)
        printf("%d\n", seq[lis[i]]);
    return 0;
}

UVA - 10036 - Divisibility

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m="";
        int cases=Integer.parseInt(br.readLine());
        for (int i = 0; i < cases; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int num=Integer.parseInt(st.nextToken());
            int rem=0;
            st=new StringTokenizer(br.readLine());
            int temp[]=new int[n];
            short[][]arr=new short[n+1][101];
            for(int j=0;j<n;j++){
                temp[j]=Math.abs(Integer.parseInt(st.nextToken()));
            }
            for(int j=0;j<n;j++){
                for(int l=0;l<101;l++){
                    arr[j][l]=2;
                }
            }
            if(sum(temp, 0, num, 0,arr)==0){
                sb.append("Divisible\n");
            }else{
                sb.append("Not divisible\n");
            }
        }
        System.out.print(sb);
    }
  
    static short sum(int[]nums,int i,int k,int sum,short[][] arr){
        if(i==nums.length){
            if(sum%k==0){
                return 0;
            }
            return 1;
        }
        int mod=sum%k;
        if(mod<0)
            mod+=k;
        if(arr[i][mod]!=2){
            return arr[i][mod%k];
        }
        arr[i][mod]=(short) Math.min(sum(nums,i+1,k,(sum+nums[i]),arr),sum(nums,i+1,k,(sum-nums[i]),arr));
        return arr[i][mod];
    }
}

UVA - 531 - Compromise

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer("");
        String m="";
        while((m=br.readLine())!=null){
            Queue<String> qu=new LinkedList<String>();
            while(true){
                StringTokenizer st=new StringTokenizer(m);
                int countTok=st.countTokens();
                for(int i=0;i<countTok;i++){
                    qu.add(st.nextToken());
                }
                m=br.readLine();
                if(m.trim().equals("#")){
                    break;
                }
            }
            String[]arr1=new String[qu.size()];
            for(int i=0;i<arr1.length;i++){
                arr1[i]=qu.remove();
            }
            Queue<String> qu2=new LinkedList<String>();
            while(true){
                StringTokenizer st=new StringTokenizer(m);
                int countTok=st.countTokens();
                for(int i=0;i<countTok;i++){
                    qu2.add(st.nextToken());
                }
                m=br.readLine();
                if(m.trim().equals("#")){
                    break;
                }
            }
            String[]arr2=new String[qu2.size()];
            for(int i=0;i<arr2.length;i++){
                arr2[i]=qu2.remove();
            }
            LinkedList<String> list=LCS(arr1, arr2);
            boolean first=true;
            while(!list.isEmpty()){
                if(!first)
                    sb.append(" ");
                sb.append(list.remove());
                first=false;
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
  
    static LinkedList<String> LCS(String[] m, String[] n) {
        int[][] arr = new int[m.length + 1][n.length + 1];
        for (int i = 0; i < m.length + 1; i++) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < n.length + 1; i++) {
            arr[0][i] = 0;
        }
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < n.length; j++) {
                if (m[i].equals(n[j])) {
                    arr[i + 1][j + 1] = arr[i][j] + 1;
                }else{
                   arr[i+1][j+1]=Math.max(arr[i+1][j],arr[i][j+1]);
                }
            }
        }
        int mpos = m.length, npos = n.length;
        LinkedList<String> result = new LinkedList<String>();

        while (mpos != 0 && npos != 0) {
            if (m[mpos - 1].equals(n[npos - 1])) {
                result.add(m[mpos - 1]);
                mpos--;
                npos--;
            } else if (arr[mpos][npos - 1] >= arr[mpos][npos]) {
                npos--;
            } else {
                mpos--;
            }
        }
        Collections.reverse(result);
        return result;
    }

}

UVA - 12484 - Cards

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m="";
        while((m=br.readLine())!=null){
            int n=Integer.parseInt(m);
            long[]arr=new long[n];
            String[]str=br.readLine().split(" ");
            for(int i=0;i<n;i++){
                arr[i]=Integer.parseInt(str[i]);
            }
            long[][]sum=new long[2][n];
            boolean flag=true;
            for(int i=1;i<n;i++){
                if(flag){
                   for(int j=0;j<n-i;j++){
                       sum[1][j]=Math.max(sum[0][j] + arr[i + j], arr[j] + sum[0][j + 1]);
                   }
                   flag=false;
                }else{
                    for(int j=0;j<n-i;j++){
                        sum[0][j]=Math.min(sum[1][j], sum[1][j + 1]);
                    }
                  flag=true;
                }
            }
            sb.append(sum[1][0]).append("\n");
        }
        System.out.print(sb);
    }
}

UVA - 10930 - A-Sequence

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        int ind=1;
        while ((m = br.readLine()) != null) {
            String[]str=m.split(" ");
            int n=Integer.parseInt(str[0]);
            int[]arr=new int[n];
            sb.append("Case #").append(ind).append(":");
            int sumAll=0;
            boolean flag=true;
            for(int i=0;i<n;i++){
                arr[i]=Integer.parseInt(str[i+1]);
                sumAll+=arr[i];
                sb.append(" ").append(arr[i]);
            }
            sb.append("\n");
            if(flag){
                for(int i=0;i<n-1;i++){
                    if(arr[i]>=arr[i+1]){
                        flag=false;
                        break;
                    }
                }
            }
            if(flag){
                flag=sumCheck(arr, sumAll);
            }
            if(flag){
                sb.append("This is an A-sequence.\n");
            }else{
                sb.append("This is not an A-sequence.\n");
            }
            ind++;
        }
        System.out.print(sb);
    }
   
    static boolean sumCheck(int[] arr,int sum){
        boolean flag = true;
        int last = 0;
        boolean[] poss = new boolean[sum + 1];
        poss[0] = true;
        for (int i = 0; i < arr.length; i++) {
            flag = flag && (arr[i] > last) && (poss[arr[i]] == false);
            last = arr[i];
            for (int j = sum; j >= arr[i]; j--) {
                poss[j] |= poss[j - arr[i]];
            }
        }
        return flag;
    }
}

UVA - 12511 - Virus

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        int n=Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
           String[] str=br.readLine().split(" ");
           int[]x=new int[Integer.parseInt(str[0])];
           for(int j=0;j<x.length;j++){
               x[j]=Integer.parseInt(str[j+1]);
           }
           str=br.readLine().split(" ");
           int[]y=new int[Integer.parseInt(str[0])];
           for(int j=0;j<y.length;j++){
               y[j]=Integer.parseInt(str[j+1]);
           }
           sb.append(LCIS(x,y)).append("\n");
        }
        System.out.print(sb);
    }
  
  static int LCIS(int[]x,int[]y){
    int N=x.length,M=y.length;
    int []common=new int[1501],previous=new int[1501];
    int current,last;
    for(int i=0;i<N;i++){
        current=0;
        last=-1;
        for(int j=0;j<M;j++){
            if (x[i]==y[j] && current>=common[j]){
               common[j]=current+1;
               previous[j]=last;
            }
            if (x[i]>y[j] && current<common[j])
            {
               current=common[j];
               last=j;
            }
        }
    }

    int l=0,ind=-1;
    for(int i=0;i<M;i++)
        if (common[i]>l)
        {
            l=common[i];
            ind=i;
        }
    return l;
}
  
}

UVA - 10943 - How do you add?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        BigInteger arr[][] =new BigInteger[101][101];
        for(int i=1;i<101;i++){
            arr[1][i]=BigInteger.valueOf(i);
            arr[i][1]=BigInteger.ONE;
        }
        for(int i=2;i<101;i++){
            for(int j=2;j<101;j++){
                arr[i][j]=arr[i-1][j].add(arr[i][j-1]);
            }
        }
        while (true) {
            String[] str=br.readLine().split(" ");
            int i=Integer.parseInt(str[0]);
            int j=Integer.parseInt(str[1]);
            if(i==0 && j==0)
                break;
            sb.append(arr[i][j].mod(BigInteger.valueOf(1000*1000))).append("\n");
        }
        System.out.print(sb);
    }
}

UVA - 11137 - Ingenuous Cubrency

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        int coins[] =new int[21];
        for(int i=1;i<22;i++){
            coins[i-1]=i*i*i;
        }
        long arr[] = count(coins, coins.length, 10000);
        while ((m = br.readLine()) != null) {
            int x=Integer.parseInt(m.trim());
            if(x==0)
                  break;
            sb.append(arr[x]).append("\n");
        }
        System.out.print(sb);
    }

    static long[] count(int coins[], int m, int n) {
        long[] temp = new long[n + 1];
        temp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = coins[i]; j < n+1; j++) {
                temp[j] += temp[j - coins[i]];
            }
        }
        return temp;
    }
}

UVA - 357 - Let Me Count The Ways

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        int coins[] = {50,25,10,5,1};
        long arr[] = count(coins, coins.length, 30000);
        while ((m = br.readLine()) != null) {
            int x=Integer.parseInt(m);
            if(x<5)
                sb.append("There is only 1 way to produce ").append(x).append(" cents change.\n");
            else
                sb.append("There are ").append(arr[x]).append(" ways to produce ").append(x).append(" cents change.\n");
        }
        System.out.print(sb);
    }

    static long[] count(int coins[], int m, int n) {
        long[] temp = new long[n + 1];
        temp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = coins[i]; j < n+1; j++) {
                temp[j] += temp[j - coins[i]];
            }
        }
        return temp;
    }
}

UVA - 674 - Coin Change

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        int coins[] = {50,25,10,5,1};
        long arr[] = count(coins, coins.length, 7489);
        while ((m = br.readLine()) != null) {
            int x=Integer.parseInt(m);
            sb.append(arr[x]).append("\n");
        }
        System.out.print(sb);
    }

    static long[] count(int coins[], int m, int n) {
        long[] temp = new long[n + 1];
        temp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = coins[i]; j < n+1; j++) {
                temp[j] += temp[j - coins[i]];
            }
        }
        return temp;
    }
}

UVA - 147 - Dollars

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        int coins[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        long arr[] = count(coins, 11, 30001);
        while ((m = br.readLine()) != null) {
            StringBuilder temp = new StringBuilder();
            for (int i = 0; i < m.length(); i++) {
                if (m.charAt(i) >= '0' && m.charAt(i) <= '9') {
                    temp.append(m.charAt(i));
                }
            }
            int x = Integer.parseInt(temp.toString());
            if (x == 0) {
                break;
            }
            for (int i = m.length(); i < 6; i++) {
                sb.append(' ');
            }
            sb.append(m);
            String ans = arr[x] + "";
            for (int i = ans.length(); i < 17; i++) {
                sb.append(' ');
            }
            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }

    static long[] count(int coins[], int m, int n) {
        long[] temp = new long[n + 1];
        temp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = coins[i]; j < n+1; j++) {
                temp[j] += temp[j - coins[i]];
            }
        }
        return temp;
    }
}

UVA - 10733 - The Colored Cubes

//Using Burnside's Lemma
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        BigInteger []bg=new BigInteger[1001];
      
        for (long i = 0; i < bg.length; i++) {
            long temp=i*i;
            long temp2=temp*temp;
            temp=((temp2*temp)+(3*temp2)+(12*temp*i)+(8*temp))/24;
            bg[(int)i]=BigInteger.valueOf(temp);
        }
        while (true) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                break;
            }
            sb.append(bg[x]).append("\n");
        }
        System.out.print(sb);
    }
}

UVA - 10918 - Tri Tiling (C Solution)

#include <stdio.h>

int main()
{
    int x,i;
    long arr[31];
    long arr2[31];
    arr[0] = arr2[1] = 1;
    arr[1] = arr2[0] = 0;
    for (i = 2; i < 31; i++) {
            arr[i] = arr[i - 2] + 2 * arr2[i - 1];
            arr2[i] = arr[i - 1] + arr2[i - 2];
        }
    while(1){
        scanf("%d",&x);
        if(x<0){
            break;
        }
        if(x%2==1){
            puts("0");
        }else{
            printf("%ld\n",arr[x]+arr2[x]);
        }
    }
    return 0;
}

UVA - 10918 - Tri Tiling (Java Solution)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        long arr[] = new long[31];
        long arr2[] = new long[31];
        arr[0] = arr2[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 2] + 2 * arr2[i - 1];
            arr2[i] = arr[i - 1] + arr2[i - 2];
        }
        while (true) {
            int x = Integer.parseInt(br.readLine());
            if (x < 0) {
                break;
            }
            if (x % 2 == 1) {
                sb.append("0\n");
            } else {
                sb.append(arr2[x] + arr[x]).append("\n");
            }
        }
        System.out.print(sb);
    }
}