UVa 10812 – Beat the Spread!

#include <iostream>

using namespace std;

int main(){
   int sum,dif,tc;
   cin>>tc;
   while (tc--){
       cin>>sum>>dif;

       if (dif>sum || ((sum^dif)&1)) // one odd and other even
           cout<<"impossible"<<endl;

       else {
           dif = (sum+dif)/2;
           cout<<dif<<" "<<sum-dif<<endl;
       }

   }
   return 0;
}

UVa 11661 – Burger Time?

#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main(){
	int n,min,lastD,lastR;
	string s;

	while (cin>>n){
		if(n==0 )
			break;

		cin>>s;
		min = 1<<25;

		lastD = lastR = -1;
		for(int i = 0 ; i<n ; i++){
			if(s[i]=='.')
				continue;
			else if (s[i]=='Z'){
				min = 0;
				break;
			}
			else if (s[i]=='D'){
				lastD = i;
				if (i-lastR<min && lastR!= -1)
					min = i-lastR;
			}
			else {
				lastR = i;
				if (i-lastD<min && lastD!=-1)
					min = i-lastD;
			}

		}
		cout<<min<<endl;
	}
	return 0;
}


UVa 11723 – Numbering Roads

#include <iostream>
#include <math.h>

using namespace std ;

int main(){
	int r, n ,ret ,t = 1;
	while (cin>>r>>n){
		if (r==0 || n==0)
			return 0;
		ret = n >=r ? 0 :ceil((double) (r-n)/n);
		if (ret>26)
			cout<<"Case "<<t<<": impossible"<<endl;
		else
			cout<<"Case "<<t<<": "<<ret << endl;
		t++;
	}
	return 0;
}

UVa 11780 – Miles 2 Km

#include <iostream>
#include <stdio.h>

using namespace std;

/*
  diff
  5 : 0.0
  3 : 0.2
  2 : 0.2
  1 : 0.4
  */

  int main (){
  	int n;
  	while (cin>>n){
  		if (n == 0 )break;
  		n = n%5;
  		switch (n){
  			case 0:cout<<"0.00"<<endl;break;
  			case 1:cout<<"0.40"<<endl;break;
  			case 2:cout<<"0.20"<<endl;break;
  			case 3:cout<<"0.20"<<endl;break;
  			case 4:cout<<"0.40"<<endl;break;
  		}

  	}
  	return 0;
  }

UVa 11875 – Brick Game

this solutions is O(nlog(n)), it can be solved in expected O(n) using order statistic partitioning. The best solution i know is O(n) using median of median algorithm.


#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std ;

int main(){
	int tc,t=0,n,temp;
	int ages[12];

	cin>>tc;
	while(t++<tc){
		cin>>n;
		temp = 0;
		while(temp<n)
			cin>>ages[temp++];
		sort(ages,ages + n);
		cout<<"Case "<<t<<": "<<ages[n/2]<<endl;
	}
	return 0;
}

UVa 11059 – Maximum Product

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int n, i,j,nums[19];
long long p ;
long long maxP = 0 ;

long long search() {
    maxP = 0;
    for (i = 0 ; i < n ; i ++){
        p = 1;
        for (j=i ; j < n && p ; j++){
            p*=nums[j];
            if ( p>maxP)
                maxP = p;
        }
    }
    return maxP;
}

int main()
{
    int t = 0;
    while (scanf("%d", &n)==1){
        for(int i = 0; i < n; ++i) {
            scanf("%d",&nums[i]);
        }
        printf("Case #%d: The maximum product is %lld.\n\n", ++t, search());
    }
}