Monthly Archives: November 2012

uva 10813 (Traditional BINGO)

Ad hoc November 26, 2012 Leave a comment


Algorithm used : Ad hoc, 2D array
long coding … but very easy…

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace  std;

void load_BINGO();
void ifMatchesThenPlaceIt(int num);
bool isGameOver();
void load_announced_numbers();


int BINGO[5][5];
int array[75];

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase;
    cin>>testCase;
    for(int tC = 1; tC<=testCase;tC++){ 
       
     load_BINGO();
    
     load_announced_numbers();
     
     for(int b=1;b<=75;b++){
      ifMatchesThenPlaceIt(array[b-1]);
      
      bool gameOver = isGameOver();
      if(gameOver){
        
         printf("BINGO after %d numbers announced\n",b);
         break;
      }
     }
    }
    return 0;
}

void load_BINGO(){
   for(int i=0;i<5;i++){
     for(int j=0;j<5;j++){
       if(i==2&&j==2)BINGO[2][2] = 0;
       else{
         cin>>BINGO[i][j];
       }
     }
   }     
}

void ifMatchesThenPlaceIt(int num){
   bool found = false;
   for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      if(num==BINGO[i][j]){
        BINGO[i][j] = 0;
        found = true;
        break;
      }
    }
    if(found)break;
   }

}

bool isGameOver(){
     int sum = 0;
     for(int j=0;j<5;j++)sum += BINGO[j][j];
     if(sum==0)return true;
     sum = 0;
     for(int j=0;j<5;j++)sum += BINGO[j][4-j];
     if(sum==0)return true;
     
     for(int i=0;i<5;i++){
     sum =0;
      for(int j=0;j<5;j++)sum += BINGO[i][j];
      //searching match in rows...
      if(sum==0)return true;
      sum = 0;
      for(int j=0;j<5;j++)sum += BINGO[j][i];//searching match in columns...
      if(sum==0)return true;
    }
    
     
     return false;
}

void load_announced_numbers(){
    for(int i=0;i<75;i++)cin>>array[i];
}

uva 10803 (Thunder Mountain)

Floyd-Warshall November 25, 2012 1 Comment


Algorithm used : Floyd-Warshall

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

#define INFINITY 2147483645
#define MAX 102

double adj[MAX][MAX];

void init(int noOfNodes){
  for(int i=1;i<=noOfNodes;i++){
    for(int j=1;j<=noOfNodes;j++){
     adj[i][j] = INFINITY;
    }
  }
}

void floydWarshall(int noOfNodes){
  for(int k=1;k<=noOfNodes;k++){
    for(int i=1;i<=noOfNodes;i++){
      for(int j=1;j<=noOfNodes;j++){
        adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
      }
    }
  }

}

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase;
    cin>>testCase;
    for(int t=1;t<=testCase;t++){
      int N;
      cin>>N;
      init(N);
      int ar[N+1][2];
      for(int i=1;i<=N;i++){
        cin>>ar[i][0];
        cin>>ar[i][1];
      }
      for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
         int h = abs((ar[i][0]-ar[j][0])*(ar[i][0]-ar[j][0]) + (ar[i][1]-ar[j][1])*(ar[i][1]-ar[j][1]));
         double dist = sqrt((double)h);
         if(dist<=10.0)adj[i][j] = dist;
        }
      }
      
      floydWarshall(N);
     
      double maxV = -1.0;
      for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
          maxV = max(maxV,adj[i][j]);
        }
       }
       printf("Case #%d:\n",t);
       if(maxV!=INFINITY)printf("%0.4lf\n\n",(double)maxV);
       else printf("Send Kurdy\n\n");
    }
   return 0;
}

uva 10800 (Not That Kind of Graph)

Ad hoc November 25, 2012 1 Comment


Algorithm used : 2D String. I enjoyed solving this problem

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;


int main(){
    char graph[102][55];
    int testCase;
    cin>>testCase;
    for(int t = 1;t<=testCase;t++){
     for(int i=0;i<102;i++){
      strcpy(graph[i],"|                                                   ");
      graph[i][52]='\0';
     }
     
     char input[55];scanf("%s",&input);
     int currentY,maxY,minY;
     currentY = maxY = minY = 50;
     bool simpleFlag = false; 
     
     for(int i=0;i<strlen(input);i++){
       if(input[i]=='C'){
        simpleFlag = true;
        graph[currentY][i+2] = '_';
        maxY = max(maxY,currentY);
        minY = min(minY,currentY); 
       }
       if(input[i]=='F'){
        if(simpleFlag)currentY++;
        graph[currentY][i+2] = '\\';
        maxY = max(maxY,currentY);
        simpleFlag = true;
       }
       if(input[i]=='R'){
        simpleFlag = true;
        graph[currentY][i+2] = '/';
        minY = min(minY,currentY);
        currentY--;
       }
     }
     printf("Case #%d:\n",t);
     for(int i=minY;i<=maxY;i++){
     for(int j=52;j>=0;j--)if(graph[i][j]=='_' || graph[i][j]=='/' || graph[i][j]=='\\'){
      graph[i][j+1]= '\0';
      break;
     }
     cout<<graph[i]<<endl;
     }
     cout<<"+-";
     for(int i=0;i<=strlen(input);i++)cout<<'-';
     cout<<endl<<endl;
    
    
    }
    
    
    return 0;
}

uva 10812 (Beat the Spread!)

Math November 24, 2012 Leave a comment


Algorithm used : Math

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase;
    cin>>testCase;
    
    for(int i=1;i<=testCase;i++){
    int sum, diff;
    cin>>sum;cin>>diff;
    if(sum<diff)printf("impossible\n");
    else if((sum+diff)%2)printf("impossible\n");
    else {
     printf("%d %d\n",max((sum+diff)/2,sum-(sum+diff)/2),min((sum+diff)/2,sum-(sum+diff)/2));
    }
    
    }
    return 0;
}

uva 10878 (Decode the tape)

Ad hoc November 24, 2012 Leave a comment


Algorithm used : Ad hoc

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

int main(){
   freopen("inMe.txt","r",stdin);
   freopen("outMe.txt","w",stdout);

   char input[100];
   while(gets(input)){
   int bits[10];
   int c = 0;
   if(input[0]=='|'){
    for(int i=1;i<strlen(input)-1;i++){
      if(input[i]==' ')bits[c++] = 0;
      else if(input[i]=='o')bits[c++] = 1;
    }
    int sum = 0;
    for(int i=c-1;i>=0;i--){
     sum += bits[i]*pow((double)2,c-1-i);
    }
    printf("%c",sum);
   }
   }
   
   
   
   
    
   
    return 0;
}

uva 10879 (Code Refactoring)

Ad hoc November 24, 2012 Leave a comment


Algorithm used : Factors.. Ad hoc

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase;
    cin>>testCase;
    for(int i=1;i<=testCase;i++){
     int K;
     cin>>K;
     int lastNum = 0;
     int count = 0,res[10];
     for(int j=2;j<K;j++){
        if(K%j==0){
           if(K/j!=lastNum && j!=lastNum){
            res[count++] = K/j;res[count++] = j;
            lastNum = res[0];
           }
        }
        if(count>3)break;
     }
      printf("Case #%d: %d = %d * %d = %d * %d\n",i,K,res[0],res[1],res[2],res[3]);
     }
    
    return 0;
}

uva 10852 (Less Prime)

Prime Numbers (Sieve Algorithm) November 24, 2012 Leave a comment


Algorithm used : Prime Numbers Sieve…

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

#define MAX 10001
char isPrime[MAX];

void sieve(){
   for(int i=2;i<MAX;i++)isPrime[i] = 1;
   
   int k = 2;
   for(int i=1;i<=sqrt((double)MAX);i++){
    for(int j=k+k;j<MAX;j=j+k)isPrime[j] = 0;
    for(k=k+1;!isPrime[k];k++);
   }     

}


int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    sieve();
    
    int testCase;
    cin>>testCase;
    
    for(int i=1;i<=testCase;i++){
      int N;cin>>N;
      for(int j=2;j<=N;j++){
       if(isPrime[j]){
        if(2*j>N){
         cout<<j<<endl;
         break;
        }
       }
      }
    }
    
    
    
    return 0;
}

uva 488 (Triangle Wave)

Ad hoc November 24, 2012 Leave a comment


Algorithm used : Ad hoc

#include< stdio.h >

int main()
{

int a,b,c,h,i,l,j,k;
freopen("in.txt","r",stdin);

scanf("%d ",&a);

	for(h=0;h < a;h++)
	{
		scanf("%d\n%d",&b,&c);
		for(i=0;i<c;i++)
		{
			for(l=1;l<=b;l++)
			{
				for(k=1;k<=l;k++)printf("%d",l);
				printf("\n");
			}

			for(j=b-1;j>0;j--)
			{
				for(k=j;k>0;k--) printf("%d",j);
				printf("\n");
			}

			if(i==c-1&&h==a-1)	continue;
			printf("\n");
		}

	}


return 0;
}

uva 10946 (You want what filled?)

Flood Fill Algorithm November 23, 2012 Leave a comment


Algorithm used : Flood Fill

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define MAX 100
char graph[MAX][MAX];
int countER;
int floodFill(int r, int c, char target);
int row,col;

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase = 1;
    
    
    while(scanf("%d %d",&row,&col)==2 && !(row==0&&col==0)){   
     for(int i=0;i<row;i++)scanf("%s",&graph[i]);
     
     int charArray[5000];
     int freq[5000];
     int start = 0;
     for(int i=0;i<row;i++){
       for(int j=0;j<col;j++){
        if(graph[i][j]>='A'&&graph[i][j]<='Z'){
         countER = 0;
         
         charArray[start] = (int)graph[i][j];
         freq[start] = floodFill(i,j,graph[i][j]); 
         if(freq[start]==0)freq[start]=1;
         start++; 
        }
       }
     }
    
   
    
    for(int a=1;a<start;++a){
     for(int b=start-1;b>=a;--b){
      if(freq[b-1]<freq[b] || (freq[b-1]==freq[b]&&charArray[b-1]>charArray[b]) ){
         int temp=freq[b-1];
       freq[b-1]=freq[b];
       freq[b]=temp;
       
        temp=charArray[b-1];
        charArray[b-1]=charArray[b];
        charArray[b]=temp;
       
      }

     }
     }
     printf("Problem %d:\n",testCase++);
     for(int i=0;i<start;i++){
      printf("%c %d\n",charArray[i],freq[i]);
    }
    
    }
    return 0;
}

int floodFill(int r, int c, char target){
    int temp1,temp2;
    temp1=r;
    temp2=c+1;
    if(temp2<col&&(graph[temp1][temp2]==target)){
        countER++;
        graph[temp1][temp2]='.';
       floodFill(temp1,temp2,target);
    }
    temp1=r;
    temp2=c-1;
    if(temp2>=0&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    temp1=r-1;
    temp2=c;
    if(temp1>=0&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    temp1=r+1;
    temp2=c;
    if(temp1<row&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    
   return countER; 

}

uva 10926 (How Many Dependencies)

DFS November 23, 2012 Leave a comment


Algorithm used : DFS

/*
  Name: How Many Dependencies
  Copyright: golammostaeen.wordpress.com 
  Author: Golam Mostaeen
  Date: 22/11/12 22:37
  Description: Simple DFS...
*/


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

#define MAX 105

int adj[MAX][MAX];
void init(int N){
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++)adj[i][j] = 0;
  }
}

int nodeColor[MAX];

void DFS_VISIT(int source, int N){
     nodeColor=1;
  for(int i=1;i<=N;i++){
   if(nodeColor[i]==0&&i!=source&&adj[i]==1)DFS_VISIT(i,N);
  }
  nodeColor = 2;
}

int DFS(int source, int N){
  for(int i=1;i<=N;i++)nodeColor[i] = 0;
  
  for(int i=1;i<=N;i++){
   if(i!=source && adj[i]==1&&nodeColor[i]==0)DFS_VISIT(i,N);
  }
  int counter = 0;
  
  for(int i=1;i<=N;i++)if(nodeColor[i]==2)counter++;
  
  return counter;
}


int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    
    
    int N;
    while(scanf("%d",&N)==1 && N!=0){
      init(N);
      for(int i=1;i<=N;i++){
       int m;cin>>m;
       for(int j=1;j<=m;j++){
        int h;cin>>h;adj[i][h]=1;
       }
      }
      int maxD = -1;
      int ID = 0;
      for(int i=1;i<=N;i++){
       int hold=DFS(i,N);
       if(hold>maxD){
         maxD = hold;
         ID = i;
         
       }
      } 
      cout<<ID<<endl;       
    }
  return 0;
}