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 11742 – Social Constraints

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int n,m,i,ways,incr,temp,first[21],second[21],dif[21],perm[9];

	while (true){
		cin>>n>>m;
		if (n==0 && m==0) return 0;
		for (i = 0 ; i < m ;i++)
			cin>>first[i]>>second[i]>>dif[i];

		for(i= 0 ; i  < n ; i++)
			perm[i] = i;

		ways = 0;
		incr = 0;
		do{
			incr = 1;
			for(i =0 ; i < m ; i ++){
				temp = abs(perm[first[i]] - perm[second[i]]);
				if ((dif[i]>0 && temp>dif[i]) || (dif[i]<0 && temp<-dif[i]) ){
					incr = 0;
					break;
				}
			}
			ways+=incr;
		}while (next_permutation(perm,perm+n));

		cout<<ways<<endl;
	}
	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 12024 – Hats


#include <iostream>
using namespace std;

//int  factorial[14] ;
int wrong[14];
int m;

int C(int n, int r){
	return factorial[n]/factorial[n-r]/factorial[r];
}

int solve (int n){
	if (wrong[n] != -1)return wrong[n];
	else{
		wrong[n] = 0;
		for(int i=1;i<=n;i++){
			wrong[n] += C(n,i)*solve(n-i);
		}
		wrong[n] = factorial[n] - wrong[n];
		return wrong[n];
	}
}

int main(){
	int tc,i;

   //calculating the first 14 factorial;
	factorial[0] = 1;
	for (i = 1 ; i <= 14; i ++){
		factorial[i] = i*factorial[i-1];
		wrong [i]= -1;
	}


	wrong[0]= 1;
	wrong[1]= 0;
	cin>>tc;
	while(tc--){
		cin>>m;
		cout<<solve(m)<<"/"<<factorial[m]<<endl;
	}

   //all possible cases = n! == P(n,n);
   //no one has a right hat = all possible cases - (1 has right hat + 2 have right hats + .... + n have right hats)
   // solve (n) = n! - solve (n-1);
   //it's the power of recursion 😀 😀

	return 0;
}

UVa 11879 – Multiple of 17


#include <cstdio>
using namespace std ;

int main(){
    int n[101],i,j,d,d1,d2;
    char temp ;
    while (true){
        i = 0;
        while (true){
            temp = getchar();

            if (temp == '\n')break;
            n[i++] = temp - '0';
        }
        if (i == 1 && n[0]==0)return 0;

        i--;

        for(j = i ; j>2 ; j--){

            d = n[j]*5; // d = d1+d2*10;
            d1 = d%10;
            d2 = d/10;

            if (n[j-1]>d1){
                n[j-2]--;
                n[j-1] = n[j-1]+10-d1;
            }else
                n[j-1] = n[j-1]-d1;

            if (n[j-2]>d2){
                n[j-3]--;
                n[j-2] = n[j-2]+10-d2;
            }else
                n[j-2] = n[j-2]-d2;

        }

        if (i == 1){
            temp = n[0];
            d = 5*n[1];
        }
        else {
            temp = n[1]+n[0]*10;
            d = 5*n[j];
        }

        if ((temp-d)%17==0)
            printf("1\n");
        else
            printf("0\n");

    }
    return 0;
}