UVA 10075 solution C++ Code

Another all pairs shortest path problem. The most difficult part is in determining the shortest distance on a sphere (earth). It is hard to solve this problem without knowing the formula, please refer to my computational geometry section to find out the formula. With this formula, the rest is solvable using Floyd Warshall.



Code: 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<iostream>
#include<vector>

#define MAXN 102
#define RADIO 6378.0
#define INF 2147483647


#define myRound(x) ( x 0.5f )
#define radianes(x) ( x * PIx / 180 )
#define ra(x) radianes(x)

#define cost(la1,lo1,la2,lo2) (myRound( ( 2 * atan2(sqrt( (sin( (ra(la2) - ra(la1) ) /2)*sin((ra(la2) - ra(la1))/2))   cos(ra(la1)) * cos(ra(la2)) * (sin((ra(lo2) - ra(lo1))/2)*sin((ra(lo2) - ra(lo1))/2)) ), sqrt(1- ((sin((ra(la2) - ra(la1))/2)*sin((ra(la2) - ra(la1))/2))   cos(ra(la1)) * cos(ra(la2)) * (sin((ra(lo2) - ra(lo1))/2)*sin((ra(lo2) - ra(lo1))/2)) ) ) ) )*RADIO ) )

using namespace std;

double PIx=3.141592653589793;
double lon2,lon1,lat2,lat1,dlon,dlat,a1,angulo;


vector< vector < long > > A(102,vector<long>(102));

map < string,int > ma;

int n;

inline void Ini() {
int i,j;
for(i = 1; i<=n; i  ){
for(j = i 1; j <=n; j  )
A[i][j]=A[j][i]=INF;
A[i][i]=0;
}
}

inline void floyd() {
int i, j, k;
for(k = 1; k <= n; k   ) {
for(i = 1; i <= n; i  ) {
for(j = 1; j<=n; j   ) {
if ((A[i][k] * A[k][j] != 0) && (i != j)&& A[i][k]!=INF && A[k][j]!=INF)
if ((A[i][k]   A[k][j] < A[i][j]) ||(A[i][j] ==0))
A[i][j]= A[i][k]   A[k][j];

}
}
}
}


int main(){


int i,j,k,m,q,l,p=1;


double lat[101],lon[101];
char a[21],b[21];

while(scanf("%d %d %d",&n,&m,&q)&&n&&m&&q){

Ini();

for(i=1;i<=n;i  ){
scanf("%s %lf %lf",a,&lat[i],&lon[i]);
ma.insert(make_pair(a,i));
}


for(i=1;i<=m;i  )
{
scanf("%s %s",a,b);

k=ma[a];
l=ma[b];

A[k][l]=cost(lat[k],lon[k],lat[l],lon[l]);

}


if(p>1)
printf("\n");

printf("Case #%d\n",p  );


floyd();


for(i=1;i<=q;i  )
{
scanf("%s %s",a,b);

k=ma[a];
l=ma[b];

if(A[k][l]==INF)
printf("no route exists\n");
else
printf("%ld km\n",A[k][l]);
}

ma.clear();

}

return 0;
}

UVA 12036 algorithm and solution C++ Code

All we need to check is whether an element in more than N times or not in the whole list. If does then the answer is true or else false.

For clarification see the following arrangement of 4*4 array. An element can only be at most four times to keep the grid stable. If it is five times then there is no place to put the extra element avoiding repetition .

1  x  x  x
x  1  x  x
x  x  1  x
x  x  x  1

Code:


#include<stdio.h>

int main(){

    int i,m,n,num,t,k,f;
    int frq[102]={0};

    scanf("%d",&t);

    k=0;
    while(++k<=t){

        scanf("%d",&n);

        m=n*n;
        f=1;
        for(i=101;i--;){
        frq[i]=0;
        }


        for(i=m ;i>0;i-- ){
        scanf( "%d", &num);
        frq[num]++;
              if( frq[num]>n ){f=0; break;}
        }
        i--;
        while(i>0){
        scanf( "%d", &num);
        i--;
        }

        if(f) printf("Case %d: yes\n",k);
        else  printf("Case %d: no\n",k);
    }

 return 0;
}

UVA 113 solution C++ Code

Code:

#include&amp;lt;stdio.h&amp;gt;
#include&amp;lt;math.h&amp;gt;

int main()
{

   double n,p;
   while(scanf(&amp;quot;%lf %lf&amp;quot;,&amp;amp;n,&amp;amp;p)!=EOF){
       printf(&amp;quot;%.0lf\n&amp;quot;,exp(log(p)/n));
   }

return 0;
}

UVA 105 solution C++ Code

#include<stdio.h>

int main(){
    int a[20001],i,l,r,pv,h,max,f;
    for(i=0;i<20000;i++)
    a[i]=0;max=0;
    while(scanf("%d%d%d",&l,&h,&r)!=EOF){
        if(l==-1)break;
        for(i=l;i<r;i++){
            if(a[i]<h)a[i]=h;
            if(r>max)max=r;
        }
}

       for(i=0,pv=0,f=1;i<=max+1;i++){
           if(pv!=a[i]){
           pv=a[i];
           if(f){printf("%d %d",i,pv);f=0;}
           else printf(" %d %d",i,pv);}
       }
       printf("\n");


 return 0;
}

Speed Up Your Code Using Bitwise Operators

Speed up Your Code Using Bitwise Operators  :

 x/2=x>>1
 x/4=x>>2
 x/8=x>>3
..................and so on

x*2=x<<1
x*3=(i<<1)+x
x*4=x<<2
x*5=(x<<2)+x
x*6=(x<<2)+(x<<1)
x*7=(x<<3)-x
x*8=x<<3
................and so on

x%2=x&1
x%4=x&3
x%8=x&7
..............and so on

Bitwise Operator :
The bitwise operators operate on numbers (always integers) as if they were sequences of binary bits (which, of course, internally to the computer they are). These operators will make the most sense, therefore, if we consider integers as represented in binary, octal, or hexadecimal (bases 2, 8, or 16), not decimal (base 10). Remember, you can use octal constants in C by prefixing them with an extra 0 (zero), and you can use hexadecimal constants by prefixing them with 0x (or 0X).

List of bitwise Operators :   

       &  -  bitwise and
       |    -  bitwise or
       ^  -  bitwise xor
       ~  -  bitwise not
     <<  -  bitwise shift left
     >>  -  bitwise shift right


Bitwise AND ( & ) :
Bitwise AND operation between x and y :
       x  = 101010    
    & y  = 011011     
  ---------------------------
      z   = 001010

Bitwise OR ( | ) :    
Bitwise OR operation between x and y :
     x = 101010    
   | y = 011011     
  -----------------------
     z = 111011

Bitwise XOR ( ^ ) :
Bitwise XOR operation between x and y :
      x  = 101010    
   ^ y  =  011011     
  -----------------------
     z   = 110001
    
Bitwise NOT ( ~ ) :
Bitwise NOT operation on x :
     x= 101010    
    ~x= 010101

Bitwise Left Shift ( << ) :
Bitwise left shift operation on x :
         x  =  0000 1011  
 x << 3  =  0101 1000    
    
Bitwise Right Shift ( >> ) :
Bitwise right shift operation on x :    
         x   =  0000 1010
 x >> 1  =   0000 0101
    
Some examples of bit operations :

1.Check an integer is even or odd:
    if ((x & 1) == 0) {
         x is even
        }
    else {
        x is odd
        }
2. Test the n-th bit set :
      if (x & (1<<n)) {
           n-th bit is set
            }
      else {
           n-th bit is not set
          }
3.Set the n-th bit :
            y= x | (1<<n )       
4. Unset the n-th bit :
            y = x & ~(1<<n)
5. Toggle the n-th bit :
            y = x ^ (1<<n)
6.Turn off the rightmost 1-bit :
            y = x & (x-1)
7.Isolate the rightmost 1-bit :
            y = x & (-x)
8.Right propagate the rightmost 1-bit :     
            y = x | (x-1)
9.Isolate the rightmost 0-bit :
            y = ~x & (x+1)
10. Turn on the rightmost 0-bit :
            y = x | (x+1)
11. Find maximum :
            r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
12. Find Minimum :
            r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
13.Swap between two integer :

       x ^=y ^= x ^= y ;

 Some Codes :

 ## Print binary representation in C:

   void int_to_bin(int num) {

      char str[9] = {0};     // integer is 8 bit

      int i;

    for (i=7; i>=0; i--) {

       str[i] = (num&1)?'1':'0';

       num >>= 1;

       }

       printf("%s\n", str);

     }

 ## Number of 1 bits :

    int number_of_ones(unsigned int x) {

           int total_ones = 0;

           while (x != 0) {

             x = x & (x-1);

             total_ones++;

            }

        return total_ones;

       }

 ## GCD CODE :

int gcd(int a, int b)

       {

        while(b) b ^= a ^= b ^= a %= b;

       return a;

       }

Resources :

1. Link 1

2. Link 2 

3. Link 3