UVA - 880 - Cantor Fractions

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));
        StringBuilder sb = new StringBuilder();
        String m="";
        while((m=br.readLine())!=null){
            long val=Long.parseLong(m);
            long n =(long) Math.ceil((Math.ceil(Math.sqrt(8*val+1))-1)/2) ;
            long upbound= n*(n+1)/2;
            sb.append(String.format("%d/%d\n",upbound-val+1,(n+val-upbound)));
        }
        System.out.print(sb);
    }
}

UVA - 264 - Count on Cantor

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));
        StringBuilder sb = new StringBuilder();
        int[]arr=new int[1000*1000*10+1];
        int[]den=new int[1000*1000*10+1];
        for(int i=1,counter=0;i<arr.length;i+=2){
            for(int j=1;j<2*i;j++){
                if(j>i){
                    arr[counter]=2*i-j;
                }else{
                    arr[counter]=j;
                }
                counter++;
                if(counter>=arr.length){
                    break;
                }
            }
            if(counter>=arr.length){
                    break;
                }
        }
       
        for(int i=2,counter=0;i<den.length;i+=2){
            for(int j=1;j<2*i;j++){
                if(j>i){
                    den[counter]=2*i-j;
                }else{
                    den[counter]=j;
                }
                counter++;
                if(counter>=arr.length){
                    break;
                }
            }
            if(counter>=arr.length){
                    break;
                }
        }
        String m="";
        while((m=br.readLine())!=null){
            int n=Integer.parseInt(m);
            sb.append(String.format("TERM %d IS %d/%d\n", n,arr[n-1],den[n-1]));
        }
        System.out.print(sb);
    }
}

UVA - 12405 - Scarecrow

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));
        StringBuilder sb = new StringBuilder();
        int cases = Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            br.readLine();
            String str=br.readLine();
            int counter=0;
            for(int j=0;j<str.length();j++){
                if(str.charAt(j)=='.'){
                    counter++;
                    j+=2;
                }
            }
            String ans=String.format("Case %d: %d", i+1,counter);
            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }
}

UVA - 11063 - B2-Sequence

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
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();
        String m;
        int cases = 1;
        while ((m = br.readLine()) != null) {
            int[] arr = new int[Integer.parseInt(m)];
            StringTokenizer st = new StringTokenizer(br.readLine());
            HashSet<Integer> hs = new HashSet<Integer>();
            for (int i = 0; i < arr.length; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            boolean flag = false;
            if (arr[0] < 1) {
                flag = true;
            }
            if (flag) {
                sb.append("Case #").append(cases).append(": It is not a B2-Sequence.\n\n");
                cases++;
                br.readLine();
                continue;
            }
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] >= arr[i + 1]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                sb.append("Case #").append(cases).append(": It is not a B2-Sequence.\n\n");
                cases++;
                br.readLine();
                continue;
            }
           
            for (int i = 0; i < arr.length; i++) {
                for (int j = i ; j < arr.length; j++) {
                    int temp = arr[i] + arr[j];
                    if (hs.contains(temp)) {
                        flag = true;
                        break;
                    }
                    hs.add(temp);
                }
                if (flag) {
                    break;
                }
            }
            if (flag) {
                sb.append("Case #").append(cases).append(": It is not a B2-Sequence.\n\n");
                cases++;
            } else {
                sb.append("Case #").append(cases).append(": It is a B2-Sequence.\n\n");
                cases++;
            }
            br.readLine();
        }
        System.out.print(sb);
    }
}

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 - 11608 - No Problem

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=1;
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            if (x <0) {
                break;
            }
            sb.append("Case ").append(cases).append(":\n");
            st = new StringTokenizer(br.readLine());
            int []month=new int[13];
            month[0]=x;
            for(int i=1;i<13;i++){
                month[i]=Integer.parseInt(st.nextToken());
            }
            int sum=x;
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<13;i++){
                int temp=Integer.parseInt(st.nextToken());
                if(sum>=temp){
                    sb.append("No problem! :D\n");
                    sum-=temp;
                }else{
                    sb.append("No problem. :(\n");
                }
                sum+=month[i];
            }
            cases++;
        }
        System.out.print(sb);
    }
}

UVA - 10703 - Free spots

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();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int qu = Integer.parseInt(st.nextToken());
            if (x == 0 && y == 0 && qu == 0) {
                break;
            }
            boolean arr[][] = new boolean[x + 1][y + 1];
            for (int c = 0; c < qu; c++) {
                st = new StringTokenizer(br.readLine());
                int x1 = Integer.parseInt(st.nextToken());
                int y1 = Integer.parseInt(st.nextToken());
                int x2 = Integer.parseInt(st.nextToken());
                int y2 = Integer.parseInt(st.nextToken());
                for (int i = Math.min(x1, x2); i < Math.max(x1, x2) + 1; i++) {
                    for (int j = Math.min(y1, y2); j < Math.max(y1, y2) + 1; j++) {
                        arr[i][j] = true;
                    }
                }
            }
            int counter = 0;
            for (int i = 1; i < x + 1; i++) {
                for (int j = 1; j < y + 1; j++) {
                    if (!arr[i][j]) {
                        counter++;
                    }
                }
            }if(counter==0){
                sb.append("There is no empty spots.\n");
            }else if(counter==1){
                sb.append("There is one empty spot.\n");
            }else{
                sb.append("There are ").append(counter).append(" empty spots.\n");
            }
            br.readLine();
        }
        System.out.print(sb);
    }
}

UVA - 11496 - Musical Loop

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();
       while(true){
           StringTokenizer st=new StringTokenizer(br.readLine());
           int n=Integer.parseInt(st.nextToken());
           if(n==0){
               break;
           }
           st=new StringTokenizer(br.readLine());
           int a0=Integer.parseInt(st.nextToken());
           boolean up=true,first=true;
           int last=Integer.parseInt(st.nextToken());
           if(last<a0){
               up=false;
               first=false;
           }
           int current=0;
           int counter=1;
           for(int i=2;i<n;i++){
               current=Integer.parseInt(st.nextToken());
               if(up){
                  if(last>current){
                      counter++;
                      up=false;
                  }
               }else{
                  if(last<current){
                      counter++;
                      up=true;
                  }
               }
               last=current;
           }
           if(up){
               if(last>a0 && first){
                      counter++;
                  }
           }else{
               if(last<a0 && !first){
                      counter++;
                  }
           }
            sb.append(counter).append("\n");
       }
       System.out.print(sb);
    }
  
}

UVA - 10391 - Compound Words

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringBuffer sb = new StringBuffer("");
        String m="";
        HashSet<String> hs=new HashSet<String>();
        LinkedList<String> str=new LinkedList<String>();
        while((m=br.readLine())!=null){
           hs.add(m);
           str.add(m);
        }
        while(!str.isEmpty()){
            String temp=str.remove();
            StringBuilder tempS=new StringBuilder();
            boolean flag=false;
            for(int i=0;i<temp.length()-1;i++){
                tempS.append(temp.charAt(i));
                if(hs.contains(tempS.toString())){
                   StringBuilder  tempS2=new StringBuilder();
                   for(int j=i+1;j<temp.length();j++){
                       tempS2.append(temp.charAt(j));
                   }
                    if(hs.contains(tempS2.toString())){
                        flag=true;
                        break;
                    }
                }
            }
            if(flag){
                sb.append(temp).append("\n");
            }
        }
        System.out.print(sb);
    }
}