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


Advertisements

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 11567 – Moliu Number Generator

#include <cstdio>
#include <algorithm>

using namespace std;

unsigned int solve (unsigned int i){

    unsigned int count = 1;
    while (i>1){
        if ((i&1)>0)
            return (count  + min(solve(i+1),solve(i-1)));
        count+=1+(1&i);
        i>>=1;
    }
    return count;
}

int main()
{
    unsigned int n;
    while (scanf("%d",&n)==1){
        if (n)
            printf("%d\n",solve(n));
        else
            printf("0\n");

    }

}

UVa 574 – Sum It Up


#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int n,t,nums[13];
map <string,char> mymap ;

char* itoa(int val, int base){
    static char buf[32] = {0};
    int i = 30;
    for(; val && i ; --i, val /= base)
        buf[i] = "0123456789abcdef"[val % base];
    return &buf[i+1];
}

void solve(int i, int sum,string collect){
    if (sum == t){
        string T = collect.substr(0,collect.length()-1);
        if (mymap.find(T) == mymap.end()){
            cout<<T<<endl;
            mymap[T]++;
        }
    }else if (sum > t)
        return ;
    else for (int j = i ; j > -1;j--){
        solve(j-1,sum+nums[j],collect+itoa(nums[j],10)+"+");
    }
}

int main()
{
    while (cin>>t>>n &&n&&t){
        for (int i = 0 ; i < n; i++){
            cin>>nums[i];
        }
        cout<<"Sums of "<<t<<":"<<endl;
        sort(nums,nums+n);
        mymap.clear();
        solve(n - 1,0,"");
        if (!mymap.size())
            cout<<"NONE"<<endl;
    }
}

UVa 154 – Recycling

one of the silliest¬†problems you can ever solve, so don’t get :@ ¬†if u got several WAs.

#include <iostream>
#include <map>
using namespace std ;

int main(){
    map<char, int> colors;
    map<char, int> materials;
    int cities[101][5];
    string s;
    int i,j,k,cnt,dif,minDif,min;
    colors['b'] = 0;
    colors['g'] = 1;
    colors['o'] = 2;
    colors['r'] = 3;
    colors['y'] = 4;
    materials['A'] = 0;
    materials['G'] = 1;
    materials['N'] = 2;
    materials['P'] = 3;
    materials['S'] = 4;

    while (true){
        cnt = 0;
        while (true){
            cin>>s;
            if (s[0]=='e')
                goto solve;
            else if (s[0]=='#')
                return 0;
            j = 0;
            while (j < s.length()){
                    cities[cnt][colors[s[j]]] = materials[s[j+2]];
                    j+=4;
            }
            cnt++;
        }
        solve:
        minDif = 100000;
        min = 0 ;

        //loop over history to find the winner city
        for(i = 0 ; i < cnt ; i ++){
            dif = 0;
            for(j = 0 ; j < cnt ; j++){
                if (i == j)continue;
                for(k = 0 ; k < 5 ; k++){
                    if (cities[i][k]!=cities[j][k])
                        dif++;
                }

            }
            if (dif<minDif){
                minDif = dif;
                min = i;
            }
        }
        cout<<min+1<<endl;
    }
    return 0;
}

UVa 11005 – Cheapest Base

#include <strings.h>

void itoa(int n, char s[])
{
    int i = 0 ,j=0;
    char temp ;
    do {
        s[i++] = n % 10 + '0';
    } while ((n /= 10) > 0);
    s[i] = '\0';
    i--;
    for (j=0;j<=i/2;j++){
        temp = s[j];
        s[j] = s[i-j];
        s[i-j] = temp;
    }
}

int main()
{
    int c[37],tc,t,n,i,min ,temp,m = 0,l=1;
    char ans[150] ,collect[4];
    scanf("%d",&tc);

    while(tc--){
        scanf("%d %d %d %d %d %d %d %d %d",&c[0],&c[1],&c[2],&c[3],&c[4],&c[5],&c[6],&c[7],&c[8]);
        scanf("%d %d %d %d %d %d %d %d %d",&c[9],&c[10],&c[11],&c[12],&c[13],&c[14],&c[15],&c[16],&c[17]);
        scanf("%d %d %d %d %d %d %d %d %d",&c[18],&c[19],&c[20],&c[21],&c[22],&c[23],&c[24],&c[25],&c[26]);
        scanf("%d %d %d %d %d %d %d %d %d",&c[27],&c[28],&c[29],&c[30],&c[31],&c[32],&c[33],&c[34],&c[35]);

        scanf("%d",&t);
        if (m)printf("\n");
        printf("Case %d:\n",l++);

        while(t--){
            scanf("%d",&m);

            min = 1<<25;

            for(i=2;i<37 ;i++){
                n = m;
                temp = 0;

                while(n>0){
                    temp+=c[n%i];
                    n/=i;
                }

                if (temp < min){
                    min = temp;
                    itoa(i,ans);
                }

                else if (temp == min){
                    itoa(i,collect);
                    strcat(ans, " ");
                    strcat(ans, collect);
                }

            }
            printf("Cheapest base(s) for number %d: %s\n",m,ans);
        }
    }

    return 0;
}