Pages

Sunday 22 December 2013

UVA - 12626 - I ❤ Pizza

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>

int min(int x,int y){
    if(x<y)
        return x;
    return y;
}

int main()
{
    int n=0;
    scanf("%d",&n);
    while(n--){
        int M=0,A=0,R=0,G=0,I=0,T=0,i=0,z=0;
        char str[600];
        scanf("%s",str);
        z=strlen(str);
        for(i=0;i<z;i++){
            if(str[i]=='M')
                M++;
            else if(str[i]=='A')
                A++;
            else if(str[i]=='R')
                R++;
            else if(str[i]=='G')
                G++;
            else if(str[i]=='I')
                I++;
            else if(str[i]=='T')
                T++;
        }
        int answer=min(min(min(min(min(M,A/3),R/2),G),I),T);
        printf("%d\n",answer);
    }
    return 0;
}


UVA - 12704 - Little Masters

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

int main()
{
    int n=0;
    scanf("%d",&n);
    while(n--){
        float x=0,y=0,r=0;
        scanf("%f %f %f",&x,&y,&r);
        double s=sqrt(x*x+y*y);
        printf("%.2f %.2f\n",r-s,r+s);
    }
    return 0;
}

UVA - 12700 - Banglawash

#include <stdio.h>

int main()
{
    int n=0,cases=1;
    scanf("%d",&n);
    while(n--){
        int matches=0,i=0;
        scanf("%d",&matches);
            char str[11];
            scanf("%s",str);
            int A=0,B=0,T=0,W=0;
            for(i=0;i<matches;i++){
                if(str[i]=='A')
                    A++;
                else if(str[i]=='B')
                    B++;
                else if(str[i]=='T')
                    T++;
                else if(str[i]=='W')
                    W++;
            }
            if((B+A==matches)&& B!=0)
                printf("Case %d: BANGLAWASH\n",cases);
            else if((W+A==matches) && W!=0)
                printf("Case %d: WHITEWASH\n",cases);
            else if(A==matches)
                printf("Case %d: ABANDONED\n",cases);
            else if(B>W)
                printf("Case %d: BANGLADESH %d - %d\n",cases,B,W);
            else if(B<W)
                 printf("Case %d: WWW %d - %d\n",cases,W,B);
            else if(B==W)
                printf("Case %d: DRAW %d %d\n",cases,B,T);
            cases++;
    }
    return 0;
}

Monday 16 December 2013

UVA - 12708 - GCD The Largest

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n=0;
    long x=0;
    scanf("%d",&n);
    while(n--){
        scanf("%ld",&x);
        if(x%2!=0){
            x--;
        }
        printf("%ld\n",x/2);
    }
    return 0;
}

UVA - 12592 - Slogan Learning of Princess

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

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());
        HashMap<String,String> hm=new HashMap<String, String>();
        for (int i = 0; i < cases; i++) {
            hm.put(br.readLine().trim(),br.readLine().trim());
        }
        cases = Integer.parseInt(br.readLine());
        for (int i = 0; i < cases; i++) {
            sb.append(hm.get(br.readLine().trim())).append("\n");
        }
        System.out.print(sb);
    }
}

Friday 6 December 2013

Facebook Hacker Cup 2014 - Qualification - Problem B - Basketball Game

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader br
            =new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        int t=Integer.parseInt(br.readLine());
        for(int i=0;i<t;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int m=Integer.parseInt(st.nextToken());
            int p=Integer.parseInt(st.nextToken());
            Player[] pls=new Player[n];
            for(int j=0;j<n;j++){
                st=new StringTokenizer(br.readLine());
                pls[j]=new Player(st.nextToken(),
                      Integer.parseInt(st.nextToken()),
                      Integer.parseInt(st.nextToken()));
            }
            Arrays.sort(pls);
            LinkedList<PlayerPlaying> team1
                       =new LinkedList<PlayerPlaying>();
            LinkedList<PlayerPlaying> team1Sit
                       =new LinkedList<PlayerPlaying>();
            LinkedList<PlayerPlaying> team2
                       =new LinkedList<PlayerPlaying>();
            LinkedList<PlayerPlaying> team2Sit
                       =new LinkedList<PlayerPlaying>();
            for(int j=n-1,counter=1;j>-1;j--,counter++){
                if(j%2==0){
                    if(team1.size()<p)
                        team1.add(new PlayerPlaying
                            (pls[j].getName(),counter, 0));
                    else
                        team1Sit.add(new PlayerPlaying
                            (pls[j].getName(),counter, 0));
                }else{
                    if(team2.size()<p)
                        team2.add(new PlayerPlaying
                             (pls[j].getName(),counter, 0));
                    else
                        team2Sit.add(new PlayerPlaying
                            (pls[j].getName(),counter, 0));
                }
            }
            
            for(int j=0;j<m;j++){
                 Iterator<PlayerPlaying> it=team1.iterator();
                 while(it.hasNext()){
                     it.next().incPlayed();
                 }
                 it=team2.iterator();
                 while(it.hasNext()){
                     it.next().incPlayed();
                 }
                 if(!team1Sit.isEmpty()){
                     Collections.sort(team1Sit);
                     PlayerPlaying playteam1=team1Sit.removeLast();
                     Collections.sort(team1);
                     PlayerPlaying sitteam1=team1.remove();
                     team1.add(playteam1);
                     team1Sit.add(sitteam1);
                 }
                 if(!team2Sit.isEmpty()){
                     Collections.sort(team2Sit);
                     PlayerPlaying playteam2=team2Sit.removeLast();

                     Collections.sort(team2);
                     PlayerPlaying sitteam2=team2.remove();

                     team2.add(playteam2);

                     team2Sit.add(sitteam2);
                 }
            }
            sb.append("Case #").append(i+1).append(": ");
            String[]arrNames=new String[2*p];
            for(int j=0;j<p;j++){
                arrNames[j]=team1.remove().getName();
                arrNames[j+p]=team2.remove().getName();
            }
           Arrays.sort(arrNames);
           for(int j=0;j<arrNames.length;j++){
               if(j>0)
                sb.append(" ");
               sb.append(arrNames[j]);
           }
           sb.append("\n");
        }
        System.out.print(sb);
    }
 
    
}

class Player implements Comparable<Player>{
    private String name;
    private int height;
    private int shotPercentage;

    public Player(String str,int s,int h) {
        this.name=str;
        this.shotPercentage=s;
        this.height=h;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public int getShotPercentage() {
        return shotPercentage;
    }

    public void setShotPercentage(int shotPercentage) {
        this.shotPercentage = shotPercentage;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
    

    @Override
    public int compareTo(Player o) {
        if(this.shotPercentage>o.getShotPercentage()){
            return 1;
        }
        else if(this.shotPercentage<o.getShotPercentage()){
            return -1;
        }else{
            if(this.height>o.getHeight()){
                return 1;
            }
            return -1;
        }
    }
    
}

class PlayerPlaying implements Comparable<PlayerPlaying> {
    private int draft;
    private int minPlayed;
    private String name;

    public PlayerPlaying(String name,int draft, int minPlayed) {
        this.name=name;
        this.draft = draft;
        this.minPlayed = minPlayed;
    }

    public int getDraft() {
        return draft;
    }

    public void setDraft(int draft) {
        this.draft = draft;
    }

    public int getMinPlayed() {
        return minPlayed;
    }

    public void setMinPlayed(int minPlayed) {
        this.minPlayed = minPlayed;
    }
    
    public void incPlayed(){
        minPlayed++;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
    
    

    @Override
    public int compareTo(PlayerPlaying o) {
       if(minPlayed<o.getMinPlayed()){
           return 1;
       }
       if(minPlayed>o.getMinPlayed()){
           return -1;
       }else{
           if(draft<o.getDraft()){
               return 1;
           }
           return -1;
       }
    }
    
    
}

    

Facebook Hacker Cup 2014 - Qualification - Problem A - Square Detector

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

public class Solution { 
 
 public static void main(String[] args)
  throws IOException {
        BufferedReader br=new BufferedReader
               (new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        int t=Integer.parseInt(br.readLine());
        for(int i=0;i<t;i++){
            int n=Integer.parseInt(br.readLine());
            boolean[][]arr=new boolean[n][n];
            for(int j=0;j<n;j++){
                String temp=br.readLine();
                for(int z=0;z<temp.length();z++){
                    if(temp.charAt(z)=='#'){
                        arr[j][z]=true;
                    }
                }
            }
            sb.append("Case #").append(i+1)
                  .append(": ");
            if(checkForSquare(arr)){
               sb.append("YES");
            }else{
               sb.append("NO");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
 
    static boolean checkForSquare(boolean[][]arr){
        int iStart=-1,jStart=-1;
        boolean flag=false;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[i].length;j++){
                if(arr[i][j]){
                    iStart=i;
                    jStart=j;
                    flag=true;
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        if(iStart==-1&&jStart==-1){
            return false;
        }
        int iEnd=-1,jEnd=-1;
        flag=false;
        for(int i=arr.length-1;i>-1;i--){
            for(int j=arr[i].length-1;j>-1;j--){
                if(arr[i][j]){
                    iEnd=i;
                    jEnd=j;
                    flag=true;
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        if(iStart==iEnd&&jStart==jEnd){
            return true;
        }
        if(iStart>iEnd || jStart>jEnd){
            return false;
        }
        if(iStart-iEnd!=jStart-jEnd){
            return false;
        }
        for(int i=iStart;i<=iEnd;i++){
            for(int j=jStart;j<=jEnd;j++){
                if(!arr[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
}

Saturday 13 July 2013

UVA - 12602 - Nice Licence Plates

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++){
            String str=br.readLine();
            int n1=(str.charAt(0)-'A')*26*26;
            n1+=(str.charAt(1)-'A')*26;
            n1+=(str.charAt(2)-'A');
            int n2=(str.charAt(4)-'0')*1000;
            n2+=(str.charAt(5)-'0')*100;
            n2+=(str.charAt(6)-'0')*10;
            n2+=(str.charAt(7)-'0');
            if(Math.abs(n1-n2)>100){
                sb.append("not nice\n");
            }else{
                sb.append("nice\n");
            }
        }
        System.out.print(sb);
    }

}

UVA - 12611 - Beautiful Flag

#include <stdio.h>

int main()
{
    int cases,i=1, r;
    scanf("%d",&cases);
    while(cases--){
        scanf("%lf",&r);
        printf("Case %d:\n",i);
        printf("%.0lf %.0lf\n",-2.25*r,1.5*r);
        printf("%.0lf %.0lf\n",2.75*r,1.5*r);
        printf("%.0lf %.0lf\n",2.75*r,-1.5*r);
        printf("%.0lf %.0lf\n",-2.25*r,-1.5*r);
        i++;
    }
    return 0;
}

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

Friday 28 June 2013

UVA - 11364 - Parking

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int cases,n,val;
    scanf("%d",&cases);
    while(cases--){
        scanf("%d",&n);
        int max=0,min=100;
        while(n--){
            scanf("%d",&val);
            if(val>max)
                max=val;
            if(val<min)
                min=val;
        }
        printf("%d\n",2*(max-min));
    }
    return 0;
}

UVA - 12279 - Emoogle Balance

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,val,i=1;
    while(1){
        scanf("%d",&n);
        if(n==0){
            break;
        }
        int treat=0,party=0;
        while(n--){
            scanf("%d",&val);
            if(val==0){
                treat++;
            }else{
                party++;
            }
        }
        printf("Case %d: %d\n",i,(party-treat));
        i++;
    }
    return 0;
}

UVA - 10992 - The Ghost of Programmers

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
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();
        boolean first=true;
        while(true){
            BigInteger bg=new BigInteger(br.readLine());
            if(bg.compareTo(BigInteger.ZERO)==0){
                break;
            }
            if(!first){
                sb.append("\n");
            }
            sb.append(bg).append("\n");
            answer(bg, sb);
            first=false;
        }
        System.out.print(sb);
    }
   
    static void answer(BigInteger bg,StringBuffer sb){
        boolean flag=false;
        if(bg.compareTo(BigInteger.valueOf(2147))==1){
            BigInteger leap=bg.add(BigInteger.ZERO);
            bg=bg.subtract(BigInteger.valueOf(2148));
            if((bg.mod(BigInteger.valueOf(2))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Tanveer Ahsan!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(5))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Shahriar Manzoor!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(7))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Adrian Kugel!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(11))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Anton Maydell!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(15))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Derek Kisman!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(20))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Rezaul Alam Chowdhury!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(28))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Jimmy Mardell!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(36))).compareTo(BigInteger.ZERO)==0){
                sb.append("Ghost of Monirul Hasan!!!\n");
                flag=true;
            }
            if((bg.mod(BigInteger.valueOf(4))).compareTo(BigInteger.ZERO)==0){
                if((leap.mod(BigInteger.valueOf(400))).compareTo(BigInteger.ZERO)==0){
                    sb.append("Ghost of K. M. Iftekhar!!!\n");
                    flag=true;
                }
                if(!((leap.mod(BigInteger.valueOf(100))).compareTo(BigInteger.ZERO)==0)){
                    sb.append("Ghost of K. M. Iftekhar!!!\n");
                    flag=true;
                }
            }
        }
        if(!flag){
            sb.append("No ghost will come in this year\n");
        }
    }
}

Thursday 27 June 2013

UVA - 12060 - All Integer Average

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 sum=0;
            int n=Integer.parseInt(st.nextToken());
            if(n==0){
                break;
            }
            sb.append("Case ").append(cases).append(":\n");
            cases++;
            while(st.hasMoreTokens()){
                sum+=Integer.parseInt(st.nextToken());
            }
            if(sum<0){
                if(sum%n==0){
                    sb.append("- ").append(Math.abs(sum/n)).append("\n");
                }else{
                    int val=(Math.abs(sum/n));
                    String qu="";
                    if(val!=0)
                        qu+=val;
                    int num=sum%n;
                    int gcd=gcd(num,n);
                    String numS=(Math.abs(num/gcd))+"";
                    String denS=Math.abs(n/gcd)+"";
                    for(int i=0;i<qu.length()+denS.length()-numS.length()+2;i++){
                        sb.append(" ");
                    }
                    sb.append(numS).append("\n");
                   
                    sb.append("- ");
                    sb.append(qu);
                    for(int i=0;i<denS.length();i++){
                        sb.append("-");
                    }
                    sb.append("\n");
                   
                    for(int i=0;i<qu.length()+2;i++){
                        sb.append(" ");
                    }
                    sb.append(denS).append("\n");
                }
            }else{
                if(sum%n==0){
                    sb.append(sum/n).append("\n");
                }else{
                    int val=(Math.abs(sum/n));
                    String qu="";
                    if(val!=0)
                        qu+=val;
                    int num=sum%n;
                    int gcd=gcd(num,n);
                    String numS=(Math.abs(num/gcd))+"";
                    String denS=(n/gcd)+"";
                    for(int i=0;i<qu.length()+denS.length()-numS.length();i++){
                        sb.append(" ");
                    }
                    sb.append(numS).append("\n");
                   
                    sb.append(qu);
                    for(int i=0;i<denS.length();i++){
                        sb.append("-");
                    }
                    sb.append("\n");
                   
                    for(int i=0;i<qu.length();i++){
                        sb.append(" ");
                    }
                    sb.append(denS).append("\n");
                }
            }
        }
        System.out.print(sb);
    }

    static int gcd(int x,int y){
        if(y==0){
            return x;
        }
        return gcd(y,x%y);
    }
}

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

Monday 24 June 2013

UVA - 10433 - Automorphic Numbers

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));
        StringBuilder sb = new StringBuilder();  
        String m="";
        while((m=br.readLine())!=null){
            int val=checkBg(m);
            if(val==0){
                sb.append("Not an Automorphic number.\n");
            }else{
                sb.append(String.format("Automorphic number of %d-digit.\n", val));
            }
        }
        System.out.print(sb);
    }
   
    static int checkBg(String m){
       
        BigInteger bg=new BigInteger(m);
        int n=m.length();
        String str=bg.modPow(BigInteger.valueOf(2), BigInteger.TEN.pow(n)).toString();
        if(str.equals("0") ||str.equals("1"))
            return 0;
        while(str.length()!=n){
           str="0"+str;
        }
        for(int i=0;i<n;i++){
            if(str.charAt(i)!=m.charAt(i))
                return 0;
        }
        return n;
    }
}
  

Thursday 13 June 2013

UVA - 11952 - Arithmetic

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();
        int cases =Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken());
            st.nextToken();
            int y=Integer.parseInt(st.nextToken());
            st.nextToken();
            int z=Integer.parseInt(st.nextToken());
            sb.append(getbase(x,y,z)).append("\n");
            String m="";
        }
         
        System.out.print(sb);
    }
  
    static int getbase(int x,int y,int z){
        if(checkones(x+"") && checkones(y+"") && checkones(z+"")){
            if((x+"").length()+(y+"").length()==(z+"").length())
                return 1;
        }
        for(int i=Math.max(Math.max(minbase(x+""),minbase(y+"")),minbase(z+""));i<19;i++){
            int x2=Integer.parseInt(x+"",i);
            int y2=Integer.parseInt(y+"",i);
            int z2=Integer.parseInt(z+"",i);
            if(x2+y2==z2){
                return i;
            }
        }
        return 0;
    }
  
    static boolean checkones(String val){
        for(int i=0;i<val.length();i++){
            if(val.charAt(i)!='1')
                return false;
        }
        return true;
    }
    static int minbase(String val){
       int max=1;
       for(int i=0;i<val.length();i++){
           int temp=val.charAt(i)-'0';
           if(temp>max)
               max=temp;
       }
       return max+1;
    }
}

Sunday 31 March 2013

UVA - 10341 - Solve It

//Root finding algorithm using newton method
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((m=br.readLine())!=null){
            if("#".equals(m.trim()))
                break;
            StringTokenizer st=new StringTokenizer(m);
            int p=Integer.parseInt(st.nextToken()),
                    q=Integer.parseInt(st.nextToken()),
                    r=Integer.parseInt(st.nextToken()),
                    s=Integer.parseInt(st.nextToken()),
                    t=Integer.parseInt(st.nextToken()),
                    u=Integer.parseInt(st.nextToken());
            if(function(0, p, q, r, s, t, u) *function(1, p, q, r, s, t, u)>0){
               sb.append("No solution\n");
            }else{
               sb.append(String.format("%.4f\n",netwonMethod(p, q, r, s, t, u)));
            }
        }
        System.out.print(sb);
    }
    static double function(double i,int p,int q,int r,
                            int s,int t,int u){
        return 1.0*p*Math.exp(-i)+1.0*q*Math.sin(i)
                        +1.0*r*Math.cos(i)+1.0*s*Math.tan(i)+t*i*i+u;
    }
  
    static double dfunction(double i,int p,int q,int r,
                            int s,int t,int u){
        return -1.0*p*Math.exp(-i)+1.0*q*Math.cos(i)
                        -1.0*r*Math.sin(i)+1.0*s/(Math.cos(i)*Math.cos(i))+2*t*i;
    }
  
    static double netwonMethod(int p,int q,int r,
                            int s,int t,int u){
        if(function(0, p, q, r, s, t, u) ==0)
            return 0;
        double ans=0.5;
        while (true){
            double newans = ans - function(ans, p, q, r, s, t, u)/dfunction(ans, p, q, r, s, t, u);
            if (Math.abs(newans-ans) < eps)
                return ans;
            ans=newans;
        }
    }
    static double eps=1E-7;
}


Thursday 28 March 2013

UVA - 10363 - Tic Tac Toe


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().trim());
        for (int i = 0; i < cases; i++) {
            if (i > 0) {
                br.readLine();
            }
            int counterX = 0, counterO = 0;
            String str = "";
            boolean[][] arrX = new boolean[3][3];
            boolean[][] arrO = new boolean[3][3];
            for (int j = 0; j < 3; j++) {
                str = br.readLine();
                for (int z = 0; z < 3; z++) {
                    if (str.charAt(z) == 'X') {
                        counterX++;
                        arrX[j][z] = true;
                    }
                    if (str.charAt(z) == 'O') {
                        counterO++;
                        arrO[j][z] = true;
                    }
                }
            }
            if (win(arrX) && win(arrO)) {
                sb.append("no\n");
            }else if (win(arrO) &&counterX!=counterO) {
                sb.append("no\n");
            }else if (win(arrX) &&counterX!=counterO+1) {
                sb.append("no\n");
            }else {
                if (counterO == counterX) {
                    sb.append("yes\n");
                } else if (counterO + 1 == counterX) {
                    sb.append("yes\n");
                } else {
                    sb.append("no\n");
                }
            }
        }
        System.out.print(sb);
    }

    static boolean win(boolean[][] arr) {
        for (int i = 0; i < 3; i++) {
            boolean flag = true;
            for (int j = 0; j < 3; j++) {
                flag &= arr[i][j];
            }
            if (flag) {
                return true;
            }
        }
        for (int i = 0; i < 3; i++) {
            boolean flag = true;
            for (int j = 0; j < 3; j++) {
                flag &= arr[j][i];
            }
            if (flag) {
                return true;
            }
        }
        if (arr[0][0] && arr[1][1] && arr[2][2]) {
            return true;
        }
        if (arr[2][0] && arr[1][1] && arr[0][2]) {
            return true;
        }
        return false;
    }
}


Thursday 14 March 2013

Sunday 10 March 2013

UVA - 320 - Border


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++) {
            sb.append("Bitmap #").append(i+1).append("\n");
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            char[][] arr = new char[32][32];
            for (int j = 0; j < 32; j++) {
                for (int z = 0; z < 32; z++) {
                    arr[j][z] = '.';
                }
            }
            StringBuilder str = new StringBuilder(br.readLine());
            for (int j = 0; j < str.length(); j++) {
                 if (str.charAt(j) == 'E') {
                    x++;
                    arr[x-1][y-1] = 'X';
                   
                } else if (str.charAt(j) == 'W') {
                        x--;
                        arr[x][y] = 'X';
                       
                } else if (str.charAt(j) == 'N') {
                        y++;
                        arr[x][y-1] = 'X';
                } else if (str.charAt(j) == 'S') {
                    y--;
                    arr[x-1][y] = 'X';
                }
            }
            for (int j = 31; j >-1; j--) {
                for (int z = 0; z < 32; z++) {
                    sb.append(arr[z][j]);
                }
                sb.append("\n");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

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

Thursday 7 March 2013

UVA - 12043 - Divisors

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();
        long[] sums = new long[100 * 1000 + 1], counters = new long[100 * 1000 + 1];
        for (int i = 1; i < 100 * 1000 + 1; i++) {
            Point p = factors(i);
            counters[i] = (int) p.getX();
            sums[i] = (int) p.getY();
        }
        int cases = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < cases; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int a = 0, b = 0, k = 0;
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            long sum = 0;
            long counter = 0;
            for (int j = a; j < b + 1; j++) {
                if (j % k == 0) {
                    counter += counters[j];
                    sum += sums[j];
                }
            }
            sb.append(counter).append(" ").append(sum).append("\n");
        }
        System.out.print(sb);
    }

    static Point factors(int x) {
        long sum = 0;
        long counter = 0;
        for (int i = 1; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                counter++;
                sum += i;
                if (x / i != i) {
                    sum += x / i;
                    counter++;
                }
            }
        }
        return new Point(counter, sum);
    }
}
class Point {
    private long x;
    private long y;

    public Point(long x, long y) {
        this.x = x;
        this.y = y;
    }

    public long getX() {
        return x;
    }

    public void setX(long x) {
        this.x = x;
    }

    public long getY() {
        return y;
    }

    public void setY(long y) {
        this.y = y;
    }
   
}

Monday 25 February 2013

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

Sunday 24 February 2013

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