UVa - 755 487--3279

//C++ 5.3.0 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE

#include<stdio.h>

#include<string.h>

#include<stdbool.h>

#define mmset(X) memset(X,0,sizeof(X))

unsigned int a[10000000];

bool flags[10000000];

bool dupes[10000000];

bool noDupes;

unsigned int map[200];

unsigned long idx,iA;

unsigned long cases;

int cPhn,lPhn,lParsed,iParsed,iPhn,tmpInd,mappedInd,iTmp;

char phn[1000],buffer[10];

char parsed[1000];

int main(){

    for(iTmp=0;iTmp<=9;iTmp++) map[iTmp]=iTmp;

    map[17]=2;map[18]=2;map[19]=2;

    map[20]=3;map[21]=3;map[22]=3;

    map[23]=4;map[24]=4;map[25]=4;

    map[26]=5;map[27]=5;map[28]=5;

    map[29]=6;map[30]=6;map[31]=6;

    map[32]=7;map[34]=7;map[35]=7;

    map[36]=8;map[37]=8;map[38]=8;

    map[39]=9;map[40]=9;map[41]=9;

//    freopen("input.txt","r",stdin);

//    freopen("output.txt","w",stdout);   

    scanf("%lu",&cases);

    while(cases--){

        noDupes=true;

        memset(a, 0, sizeof(a));

        memset(flags, false, sizeof(flags));

        memset(dupes, false, sizeof(dupes));

        scanf("%d",&cPhn);

        while(cPhn--){

            scanf("%s",phn);

            lPhn=strlen(phn);

            iParsed=0;

            for(iPhn=0;iPhn<lPhn;iPhn++){

                if(phn[iPhn] != '-'){

                    parsed[iParsed++]=phn[iPhn];

                }

            }

            parsed[iParsed]='\0';

            lParsed=strlen(parsed);

            idx=0;

            for(iParsed=0;iParsed<lParsed;iParsed++){

                tmpInd=parsed[iParsed]-'0';

                mappedInd=map[tmpInd];

                idx=10*idx;

                idx=idx+mappedInd;

            }

            if(dupes[idx]){

                a[idx] += 1;

            }

            else if(flags[idx]){

                a[idx] += 1;noDupes=false;

                dupes[idx]=true;

            }

            else{

                a[idx] += 1;

                flags[idx]=true;

            }

        }

        for(iA=0;iA<=9999999;iA++){

            if(noDupes){printf("No duplicates.\n");break;}

            if(dupes[iA]){

                sprintf(buffer, "%07lu",iA);

                printf("%c%c%c-%c%c%c%c %u\n",buffer[0],buffer[1],buffer[2],buffer[3],buffer[4],buffer[5],buffer[6],a[iA]);

            }

        }

        if(cases != 0) printf("\n");

    }

}

UVa - 113 Power of Cryptography

#include<stdio.h>

#include<float.h>

#include<math.h>

#include<assert.h>

#define EPSILON 0.01

double guess;

double n,p;

double nth_root_rec_bf_bs(double low,double high){

    if(abs(low-high) < EPSILON) return guess;

    guess=(low+high)/2;

    if(abs((pow(guess, n)) - p) <= EPSILON) return guess;

    if(pow(guess, n) > p) return nth_root_rec_bf_bs(low,guess);

    return nth_root_rec_bf_bs(guess,high);

}

inline double nthRoot(double x, double n){

    if(x==1) return 1;

    if(n==1) return x;

    if(x >= 0 and x <= 1) return nth_root_rec_bf_bs(x,1);

    if(x>1) return nth_root_rec_bf_bs(1,x);

assert(1==0);

}

int main(){

//        freopen("input.txt","r",stdin);

//        freopen("output.txt","w",stdout);   

    while (scanf("%lf%lf", &n, &p) == 2){

        printf("%.0lf\n", nthRoot(p,n));

    }

}

UVa - 105 The Skyline Problem

#include<stdio.h>

#include<string.h>

#include<limits.h>

#define  MX 20000

long maxs[MX],iMaxs,maxZ=LLONG_MIN;

long x,y,z,lastItem=0,lastIndex;

int main() {

//    freopen("input.txt","r",stdin);

//    freopen("output.txt","w",stdout);   

    while(scanf("%ld%ld%ld",&x,&y,&z)==3){

        for(iMaxs=x;iMaxs<=z;iMaxs++){

            if(maxs[iMaxs] < y) maxs[iMaxs]=y;

        }

        if(maxZ<z) maxZ=z;

    }

    for(iMaxs=0;iMaxs<=maxZ;iMaxs++){

        if(maxs[iMaxs]!=lastItem){

            if(lastItem>maxs[iMaxs]) printf("%ld %ld",iMaxs-1,maxs[iMaxs]);

            else printf("%ld %ld",iMaxs,maxs[iMaxs]);

            lastItem=maxs[iMaxs];lastIndex=iMaxs;

            if(iMaxs!=maxZ) printf(" ");

        }

    }

    if(maxs[maxZ]!=0) printf(" %ld 0\n",lastIndex);

    return 0;

}

UVa - 102 Ecological Bin Packing

#include<stdio.h>

#include<string.h>

#include<stdbool.h>

#include<limits.h>

char dec[]={'B','C','G'};

char binComb[5],minComb[5];

unsigned long long B[3],G[3],C[3],min=ULLONG_MAX,moves,tmpSum,tmpMin=ULLONG_MAX,minFind,inpMin;

unsigned long long *ptr[24];

int i,ii,j,k,iFind;

long long tmpMax;

inline unsigned long long calcMoves(char color,int pos){

    

    tmpSum=0;

    for(ii=0;ii<3;ii++){

        if(ii==pos) continue;

        tmpSum = tmpSum + ptr[color-'0'][ii];

    }

    return tmpSum;

}

inline unsigned long long minx(){

    minFind=ULLONG_MAX;

    for(iFind=0;iFind<3;iFind++){

        if(B[iFind]<minFind){minFind=B[iFind];}

        if(G[iFind]<minFind){minFind=G[iFind];}

        if(C[iFind]<minFind){minFind=C[iFind];}

    }

    return minFind;

}

int main()

{

    ptr['B'-'0']=B;

    ptr['G'-'0']=G;

    ptr['C'-'0']=C;

//    freopen("input.txt","r",stdin);

//    freopen("output.txt","w",stdout);   

    while(scanf("%llu%llu%llu%llu%llu%llu%llu%llu%llu",&B[0],&G[0],&C[0],&B[1],&G[1],&C[1],&B[2],&G[2],&C[2])==9){

inpMin=minx();

if(inpMin>0){

    for(iFind=0;iFind<3;iFind++){

        B[iFind]-=inpMin;

        G[iFind]-=inpMin;

        C[iFind]-=inpMin;

    }

}

        min=ULLONG_MAX;

        for(i=0;i<3;i++){

            for(j=0;j<3;j++){

                for(k=0;k<3;k++){

                    if(i==j || i==k || j==k) continue;

                    sprintf(binComb,"%c%c%c",dec[i],dec[j],dec[k]);

                    moves=calcMoves(dec[i],0)+calcMoves(dec[j],1)+calcMoves(dec[k],2);

                    if(moves<min) { min=moves;strcpy(minComb,binComb); }

                }  

            }   

        }

        if(inpMin>0) min+=(inpMin*2*3);

        printf("%s %llu\n",minComb,min);

    }

    return 0;

}

UVa - 100 The 3n+1 Problem

#include<stdio.h>

#define SWAP(X, Y) do { typeof(X) TMP = X; X = Y; Y = TMP; } while (0)

unsigned long tmp,max,k,t;

unsigned long cycleLen(unsigned long i,unsigned long n,unsigned long cnt)

{

    if(i==1) { return cnt; }

    if(i%2 == 0) return cycleLen(i/2,n,cnt+1);

return cycleLen(3*i+1,n,cnt+1);

}

unsigned long mxLen(unsigned long i,unsigned long j)

{

    if(i>j) SWAP(i,j);

    max=cycleLen(i,i,0)+1;

    for(k=i+1;k<=j;k++){

        t=cycleLen(k,k,0)+1;

        if(max<t) max=t;

    }

    return max;

}

int main()

{

    unsigned long i,j,mx;

    //freopen("INPUT.TXT","r",stdin);

    //freopen("OUTPUT.TXT","w",stdout);

    while(scanf("%lu%lu",&i,&j)==2)

    {

        mx=mxLen(i,j);

        printf("%lu %lu %lu\n",i,j,mx);

    }

    return 0;

}

UVa - 371 Ackermann Functions DP Solution

#include<stdio.h>

#define MX 10000000

#define swap(xxx, yyy) (xxx) ^= (yyy) ^= (xxx) ^= (yyy)

unsigned long DP[MX];

unsigned long tmp,max,maxItem,k,t;

unsigned long cycleLen(unsigned long i,unsigned long n,unsigned long cnt)

{

    if(i<MX && DP[i]){ DP[n]=cnt+DP[i];return DP[n]; }

    if(i==1) { DP[n]=cnt;return DP[n]; }

    if(i%2 == 0) return cycleLen(i/2,n,cnt+1);

    return cycleLen(3*i+1,n,cnt+1);

}

unsigned long mxLen(unsigned long i,unsigned long j)

{

    if(i>j) swap(i,j);

    if(i==1){

        max=3+1;

        maxItem=1; 

    }

    else{

        max=cycleLen(i,i,0)+1;

        maxItem=i;

    }

    for(k=i+1;k<=j;k++){

        t=cycleLen(k,k,0)+1;

        if(max<t){max=t;maxItem=k;}

    }

    return max;

}

int main(){

    unsigned long a,b,mx;

//    freopen("input.txt","r",stdin);

//    freopen("output.txt","w",stdout);

    while(1)

    {

        scanf("%lu %lu",&a,&b);

        if(a==0 && b==0) break;

        mx=mxLen(a,b);

        if(a>b){swap(a,b);}

        printf("Between %lu and %lu, %lu generates the longest sequence of %lu values.\n",a,b,maxItem,mx-1);

    }

    return 0;

}