Pages

Showing posts with label Bitmask. Show all posts
Showing posts with label Bitmask. Show all posts

Sunday, 7 September 2014

CodeEval - Juggling With Zeros - Easy

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) {
            if(line.equals("#")){
                break;
            }
            StringTokenizer st=new StringTokenizer(line);
            StringBuilder strBin=new StringBuilder();
            while(st.hasMoreTokens()){
                String rule=st.nextToken();
                if(rule.equals("0")){
                    strBin.append(st.nextToken());
                }else{
                    int n=st.nextToken().length();
                    for(int i=0;i<n;i++){
                       strBin.append(1);
                    }
                }
            }
            sb.append(Long.parseLong(strBin.toString(), 2)).append('\n');
        }
        System.out.print(sb);
    }
   
}

Thursday, 27 June 2013

UVA - 594 - One Little, Two Little, Three Little Endians

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) {
            StringBuilder temp=null ;
            if(m.charAt(0)=='-'){
                String str=m.substring(1);
                str= Long.toBinaryString(Long.parseLong(str));
                temp = new StringBuilder(twoSComplement(str));
            }else{
                temp = new StringBuilder(Long.toString(Integer.parseInt(m), 2));
            }
            sb.append(m).append(" converts to ").append(operation(temp)).append("\n");
        }
        System.out.print(sb);
    }

    static String operation(StringBuilder temp) {
        while (temp.length() < 32) {
            temp.insert(0, "0");
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < 8; i++) {
            ans.append(temp.charAt(i + 24));
        }
        for (int i = 0; i < 8; i++) {
            ans.append(temp.charAt(i + 16));
        }
        for (int i = 0; i < 8; i++) {
            ans.append(temp.charAt(i + 8));
        }
        for (int i = 0; i < 8; i++) {
            ans.append(temp.charAt(i));
        }
        return StringMan(ans);
    }

    static String StringMan(StringBuilder temp) {
        if (temp.charAt(0) == '1') {
            StringBuilder oneComplement = new StringBuilder();
            for (int i = 0; i < temp.length(); i++) {
                if (temp.charAt(i) == '0') {
                    oneComplement.append('1');
                } else {
                    oneComplement.append('0');
                } 
            }
            long h=Long.parseLong(oneComplement.toString(),2)+1;
            return "-"+h;
        }
        return Integer.parseInt(temp.toString(), 2) + "";
    }
   
    static String twoSComplement(String temp){
            StringBuilder oneComplement = new StringBuilder();
            while(temp.length()<32){
                temp='0'+temp;
            }
            for (int i = 0; i < temp.length(); i++) {
                if (temp.charAt(i) == '0') {
                    oneComplement.append('1');
                } else {
                    oneComplement.append('0');
                } 
            }
            long h=Long.parseLong(oneComplement.toString(),2)+1;
            return Long.toBinaryString(h);
    }
}

Wednesday, 13 February 2013

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;
      }
}