CodeEval - Distinct Subsequences - 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.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,",");
           wholeStr=st.nextToken();
           str=st.nextToken();
           sb.append(getOccurence(0, 0, new StringBuilder()));
           sb.append('\n');
        }
        System.out.print(sb);
    }
   
    static String str;
    static String wholeStr;
   
    static int getOccurence(int j,int i,StringBuilder string){
        if(j==str.length())
            return 1;
        if(i==wholeStr.length())
            return 0;
        int counter=0;
        if(str.charAt(j)==wholeStr.charAt(i)){
            counter=getOccurence(j+1,i+1,string);
        }
        return  getOccurence(j,i+1,string)+counter;
    }

}

CodeEval - Telephone Words - 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;


public class Main {

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

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb2 = new StringBuffer();
        String line;
        while ((line = in.readLine()) != null) {
           sb=new StringBuffer();
           str=line;
           getWords(new StringBuilder());
           sb2.append(sb);
           sb2.append('\n');
        }
        System.out.print(sb2);
    }
   
    static String str;
    static StringBuffer sb;
 static void getWords(StringBuilder word){
     int index=word.length();
     if(index==7){
         if(sb.length()!=0){
             sb.append(',');
         }
         sb.append(word);
         return;
     }
     char c=str.charAt(index);
     if(c=='0' || c=='1'){
        word.append(c);
        getWords(word);
        word.deleteCharAt(word.length()-1);
     }
     else{
         int valz=c-'0'-2;
         int counter=0;
         if(valz>5)
             counter=1;
         char ca=(char) ('a'+valz*3+counter);
         word.append(ca);
         getWords(word);
         word.deleteCharAt(word.length()-1);
         char cb=(char) ('b'+valz*3+counter);
         word.append(cb);
         getWords(word);
         word.deleteCharAt(word.length()-1);
         char cc=(char) ('c'+valz*3+counter);
         word.append(cc);
         getWords(word);
         word.deleteCharAt(word.length()-1);
         if(valz==5 || valz==7){
            char cd=(char) ('d'+valz*3+counter);
            word.append(cd);
            getWords(word);
            word.deleteCharAt(word.length()-1);
         }
     }
 }

}

UVA - 11205 - The broken pedometer

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));
        StringBuilder sb = new StringBuilder();
        int cases=Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            int leds=Integer.parseInt(br.readLine());
            int numbers=Integer.parseInt(br.readLine());
            int[] arr=new int[numbers];
            for(int j=0;j<numbers;j++){
                StringBuilder str=new StringBuilder();
                StringTokenizer st=new StringTokenizer(br.readLine());
                for(int l=0;l<leds;l++){
                    str.append(st.nextToken());
                }
                arr[j]=Integer.parseInt(str.toString(),2);
            }
            int min=Integer.MAX_VALUE;
            for(int j=1;j<Math.pow(2, leds);j++){
                if(checkUnique(j,leds,arr)){
                    int counter=countbits(j);
                    if(min>counter)
                        min=counter;
                }
            }
            sb.append(min).append("\n");
        }
        System.out.print(sb);
    }
   
      static boolean checkUnique(int mask,int leds,int[]arr){
          boolean[]temp=new boolean[(int)Math.pow(2, leds)+1];
          for(int i=0;i<arr.length;i++){
              int tempNum=mask&arr[i];
              if(temp[tempNum]){
                  return false;
              }
              temp[tempNum]=true;
          }
          return true;
      }
     
      static int countbits(int j){
          String temp=Integer.toBinaryString(j);
          int counter=0;
          for(int i=0;i<temp.length();i++){
              if(temp.charAt(i)=='1'){
                  counter++;
              }
          }
          return counter;
      }
}

UVA - 11565 - Simple Equations

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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();
        int cases = Integer.parseInt(br.readLine());
        for (int i = 0; i < cases; i++) {
            StringTokenizer str=new StringTokenizer(br.readLine());
            int A=Integer.parseInt(str.nextToken());
            int B=Integer.parseInt(str.nextToken());
            int C=Integer.parseInt(str.nextToken());
            ArrayList<Integer> arr=new ArrayList<Integer>();
            for(int j=1;j<(B/2)+1;j++){
                if(B%j==0){
                    arr.add(j);
                    arr.add(-j);
                }
            }
            arr.add(B);
            arr.add(-B);
            Collections.sort(arr);
            boolean flag=false;
            for(int x=0;x<arr.size();x++){
                for(int y=x+1;y<arr.size();y++){
                    for(int z=y+1;z<arr.size();z++){
                        if(arr.get(x)*arr.get(y)*arr.get(z)==B){
                            if(arr.get(x)+arr.get(y)+arr.get(z)==A){
                                if((arr.get(x)*arr.get(x))+
                                        (arr.get(y)*arr.get(y))+
                                            (arr.get(z)*arr.get(z))==C){
                                    sb.append(arr.get(x)).append(" ")
                                      .append(arr.get(y)).append(" ")
                                      .append(arr.get(z)).append("\n");
                                    flag=true;
                                    break;
                                }
                            }
                        }
                    }
                    if(flag){
                        break;
                    }
                }
                if(flag){
                    break;
                }
            }
            if(!flag){
              sb.append("No solution.").append("\n"); 
            }
        }
        System.out.print(sb);
    }

}

UVA - 10365 - Blocks

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();
        int cases=Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            int x=Integer.parseInt(br.readLine());
            sb.append(getArea(x)).append("\n");
        }
        System.out.print(sb);
    }

    static int getArea(int x) {
        int value = Integer.MAX_VALUE;
        for (int j = 1; j < x + 1; j++) {
            if (x % j == 0) {
                int part = x / j;
                for (int z = 1; z < part + 1; z++) {
                    if (part % z == 0) {
                        int tempArea = 2 * ( part + x / z + j * z);
                        if (tempArea < value) {
                            value = tempArea;
                        }
                    }
                }
            }
        }
        return value;
    }
}

UVA - 10487 - Closest Sums

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        int cases=1;
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }
            sb.append("Case ").append(cases).append(":\n");
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }
            ArrayList<Integer> sum=new  ArrayList<Integer>(n*n);
            for (int i = 0; i < n; i++) {
               for (int j = i; j < n; j++) {
                   if(i!=j){
                       sum.add(arr[i]+arr[j]);
                   }
                }
            }
            Collections.sort(sum);
            int m = Integer.parseInt(br.readLine());
            for(int i = 0; i < m; i++){
                int q=Integer.parseInt(br.readLine());
                int min=Integer.MAX_VALUE,ans=-1;
                for(int j=0;j<sum.size();j++){
                    int dif=Math.abs(q-sum.get(j));
                    if(dif<min){
                        min=dif;
                        ans=sum.get(j);
                    }
                }
                sb.append("Closest sum to ").append(q).append(" is ").append(ans).append(".\n");
            }
            cases++;
        }
        System.out.print(sb);
    }
}

UVA - 10125 – Sumsets

//Data Set is weak ...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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;
            }
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(br.readLine().trim());
            }
            Arrays.sort(arr);
            boolean flag = false;
            long max = Integer.MIN_VALUE;
            for (int i = n - 1; i > -1; i--) {
                for (int j = 0; j < n; j++) {
                    if (arr[i] == arr[j]) {
                        continue;
                    }
                    for (int z = j + 1; z < n; z++) {
                        if (arr[z] == arr[i]) {
                            continue;
                        }
                        for (int k = z + 1; k < n; k++) {
                            if (arr[k] == arr[i]) {
                                continue;
                            }
                            if (arr[i] == (arr[j] + arr[k] + arr[z])) {
                                sb.append(arr[i]).append("\n");
                                flag = true;
                                break;
                            }
                        }
                        if (flag) {
                            break;
                        }
                    }
                    if (flag) {
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            if (!flag) {
                sb.append("no solution\n");
            }
        }
        System.out.print(sb);
    }
}

UVA - 725 - Division

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        int[]idnum=new int[30240];
        for(int i=98765,j=0;i>1233;i--){
            boolean[]arr=new boolean[10];
            if(i<10000)
                arr[0]=true;
            int temp=i;
            boolean flag=true;
            while(temp>0){
                int index=temp%10;
                if(arr[index]){
                    flag=false;
                    break;
                }
                arr[index]=true;
                temp/=10;
            }
            if(flag){
               idnum[j]=i;
               j++;
            }
        }
        LinkedList<String>[] list=new LinkedList[80];
        for(int i=0;i<80;i++){
            list[i]=new LinkedList<String>();
        }
        Arrays.sort(idnum);
        for(int i=3024;i<idnum.length;i++){
            int tempX=idnum[i];
           for(int j=0;j<i;j++){
               int tempY=idnum[j];
               if(idnum[i]%idnum[j]==0 && checkIdent(idnum[i],idnum[j])){
                   int div=idnum[i]/idnum[j];
                   if(div>79){
                       break;
                   }else{
                       if(idnum[j]<10000){
                           list[div].add(idnum[i]+" / 0"+idnum[j]);
                       }else{
                           list[div].add(idnum[i]+" / "+idnum[j]);
                       }
                   }
               }
            }
        }
        boolean first =true;
        while(true){
            int x=Integer.parseInt(br.readLine());
            if(x==0){
                break;
            }
            if(!first){
                sb.append("\n");
            }
            first=false;
            if(!list[x].isEmpty()){
                for(int i=0;i<list[x].size();i++){
                    sb.append(list[x].get(i)).append(" = ").append(x).append("\n");
                }
            }else{
                sb.append("There are no solutions for ").append(x).append(".\n");
            }
        }
        System.out.print(sb);
    }
   
    static boolean checkIdent(int x,int y){
        boolean[] arr=new boolean[10];
        if(x<10000)
            arr[0]=true;
        int temp=x;
        while(temp>0){
            int rem=temp%10;
            arr[rem]=true;
            temp/=10;
        }
        temp=y;
        if(y<10000){
            if(arr[0])
               return false;
        }
        while(temp>0){
            int rem=temp%10;
            if(arr[rem]){
                return false;
            }
            temp/=10;
        }
        return true;
    }
}