[UVa] 10391 - Compound Words

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<string> words;

class kmap
{
    public:
    kmap (const int &v):defVal (v)
    {
    }
    int &getVal(const string &k)
    {
        if (m.find(k) == m.end())
            return defVal;
        else
            return m[k];
    }
    int &operator[] (const string &k)
    {
        return m[k];
    }
    std::map<string,int> m;
    int defVal;
};

kmap ver(-1);

int main()
{
    string word, s1, s2;
    int i, j;

    i=0;
    while (cin >> word)
    {
        words.push_back(word);
        ver[word]=i++;
    }
    int list_len = words.size();

    for (i=0 ; i<list_len ; i++)
    {
        int wlen = words[i].length();
        //cout << words[i] << endl;
        for (j=1 ; j<wlen ; j++)
        {
            s1 = words[i].substr(0,j);
            s2 = words[i].substr(j,wlen);

            //cout << "\t" << ver[s1] << "--" << ver[s2] << endl;

            if (ver.getVal(s1)!=-1 && ver.getVal(s2)!=-1 && ver[s1]!=i && ver[s2]!=i)
            {
                cout << words[i] << endl;
                break;
            }
        }
    }
    return 0;
}

[UVa] 12195 - Jingle Composing

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define ERROR 1e-11
using namespace std;

char input[1000000];
int main()
{
    int counter, i;
    double sum;
    char *p;
    while (gets(input))
    {
        if (!strcmp(input,"*")) break;


        counter=0;
        p = strtok(input,"/");
        while (p!=NULL)
        {
            for (i=0, sum=0 ; p[i]>='A'&&p[i]<='Z' ; i++)
            {
                if (p[i]=='W') sum += 1.0;
                else if (p[i]=='H') sum += 1.0/2.0;
                else if (p[i]=='Q') sum += 1.0/4.0;
                else if (p[i]=='E') sum += 1.0/8.0;
                else if (p[i]=='S') sum += 1.0/16.0;
                else if (p[i]=='T') sum += 1.0/32.0;
                else if (p[i]=='X') sum += 1.0/64.0;
            }
            if (fabs(sum-1)<ERROR) counter++;
            p = strtok(NULL,"/");
        }
        printf("%d\n",counter);
    }
    return 0;
}

[UVa] 392 - Polynomial Showdown

Just conditioning, loads of ifs

If you're getting PE or WA just test with some isolated values for different coefficients. Some of my test cases are.

0    0    0    1   22 -333    0    1   -1
0    0    0    0    0    0  -55    5    0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 -1 0
0 0 0 0 0 0 -1 0 0
0 0 0 0 0 -1 0 0 0
0 0 0 0 -1 0 0 0 0
0 0 0 -1 0 0 0 0 0
0 0 -1 0 0 0 0 0 0
0 -1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

x^5 + 22x^4 - 333x^3 + x - 1
-55x^2 + 5x
0
-1
-x
-x^2
-x^3
-x^4
-x^5
-x^6
-x^7
-x^8
0

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

int a[10];

int main()
{
    int i, print, z;
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);
    while (scanf("%d %d %d %d %d %d %d %d %d",&a[8],&a[7],&a[6],&a[5],&a[4],&a[3],&a[2],&a[1],&a[0])==9)
    {
        for (i=0, z=1 ; i<9 && z; i++)      //-----|Checking if the
            if (a[i]) z=0;                  //-----|polynomial is zero

        if (z) {                            //-----|The polynomial is found
            printf("0\n");                  //-----|to be zero in fact
            continue;
        }

    //-[ The first value of the equation is not printed yet ]
        print=0;
        for (i=8 ; i>1 ; i--)
        {
            if (print && a[i]) printf(" ");

            if (a[i]==-1)
            {
                (print? printf("- x^%d",i) : printf("-x^%d",i) );
            } else if (a[i]==1)
            {
                (print? printf("+ x^%d",i) : printf("x^%d",i) );
            } else if (a[i]<0)
            {
                (print? printf("- %dx^%d",-1*a[i],i) : printf("%dx^%d",a[i],i) );
            } else if (a[i])
            {
                (print? printf("+ %dx^%d",a[i],i) : printf("%dx^%d",a[i],i) );
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]==-1)
            {
                (print? printf("- x") : printf("-x") );
            } else if (a[i]==1)
            {
                (print? printf("+ x") : printf("x") );
            } else if (a[i]<0)
            {
                (print? printf("- %dx",-1*a[i]) : printf("%dx",a[i]) );
            } else if (a[i])
            {
                (print? printf("+ %dx",a[i]) : printf("%dx",a[i]));
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        i--;
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]<0)
            {
                (print ? printf("- %d",-1*a[i]) : printf("%d",a[i]) );
            } else if (a[i])
            {
                (print ? printf("+ %d",a[i]) : printf("%d",a[i]) );
            }
        }

        printf("\n");
    }
    return 0;
}

[UVa] 10190 - Divide but not quite conquer

Critical point:
If n<2 or m<2, it's "Boring!"
If at some point (n%m != 0), it's "Boring!" to the limit :P
Method:
I store the result in a string (char arrray) when the division is taking place. If the sequence is found to be not boring, print the string.

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

char output[1000000], temp[1000000];
int addStr(char *des, int val, int len)
{

    if (!len)
        sprintf(des,"%d",val);
    else
    {
        int i, j;
        sprintf(temp," %d",val);
        int ln = strlen(temp);
        for (i=len, j=0 ; j<ln ; i++, j++)
        {
            des[i]=temp[j];
        }
        des[i]='\0';
        return (len+j);
    }
    return strlen(des);
}

int main()
{
    int n, m;
    while (scanf("%d %d",&n,&m)==2)
    {
        int lnt = 0;
        int b=0;
        if (n<2 || m<2)
        {
            printf("Boring!\n");
            continue;
        }
        while (n>1)
        {
            lnt=addStr(output,n,lnt);
            if (n%m != 0)
                b=1;
            n/=m;
        }
        lnt=addStr(output,n,lnt);


        if (b)
            printf("Boring!\n");
        else
            printf("%s\n",output);
    }
    return 0;
}

[UVa] 11830 - Contract Revision

#include <stdio.h>
#include <string.h>
char input[100000], pro[100000];
int rmv(char *a, char c)
{
    int i, z, len=strlen(a);

    for (i=0 ; i<len ; i++)
    {
        if (a[i]==c)
            a[i]='\\';
    }
    for (i=0, z=1 ; i<len ; i++)
    {
        if (a[i]!='0' && a[i]!='\\')
            z=0;
        if (!z && a[i]!='\\')
            putchar(a[i]);
    }

    if (z)
        printf("0");
    putchar('\n');
    return 0;
}

int main()
{
    char c;
    while (gets(input))
    {
        if (!strcmp("0 0",input))
            break;
        sscanf(input,"%c %s",&c,pro);

        rmv(pro,c);
    }
    return 0;
}

[UVa] 343 - What base is this?

I was too lazy when I saw this problem for the very first time 2 years ago. Solving problems that required parsing a string were too tedious for me back then. Well, guess what it generated a great code for future problems from this domain.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define isChar(i) ((i>='A'&&i<='Z')||(i>='0'&&i<='9'))
typedef unsigned long long ULL;
int vals[1000];
char input[1000], val1[1000], val2[1000];
ULL getVal(char *a, int base, int ln)
{
    int len = ln, i;
    ULL val=0;
    for (i=len-1 ; i>=0 ; i--)
    {
        val = val + (vals[a[i]]) * (int)pow((double)base,(len-1-i));
    }
    return val;
}

int setVals()
{
    int i;
    for (i=0 ; i<=9 ; i++)
    {
        vals[i+'0'] = i;
    }
    for (i='A' ; i<='Z' ; i++)
    {
        vals[i] = (i-55);
    }
}

int parser(char *a, int *l1, int *l2, int *mb1, int *mb2)
{
    int i, j, min;
    for (i=0 ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val1[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val1[j]='\0';
    *l1=j;
    *mb1=min+1;

    for ( ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val2[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val2[j]='\0';
    *l2=j;
    *mb2=min+1;
}

int main()
{
    int l1, l2, minb1, minb2, f, i, j;
    setVals();

    while (gets(input))
    {
        parser(input,&l1,&l2,&minb1,&minb2);

        f=0;

        for (i=(minb1>1?minb1:2) ; i<=36 && !f ; i++)
        {
            for (j=(minb2>1?minb2:2) ; j<=36 && !f ; j++)
            {
                if (getVal(val1,i,l1) == getVal(val2,j,l2))
                {
                    printf("%s (base %d) = %s (base %d)\n",val1,i,val2,j);
                    f=1;
                }
            }
        }

        if (!f) printf("%s is not equal to %s in any base 2..36\n",val1,val2);

    }
    return 0;
}

[UVa] 455 - Periodic Strings

#include <stdio.h>
#include <string.h>
char input[10000];
int finder(char *a)
{
    int len = strlen(a), l, v, i, j;
    char q[100];

    for (l=1 ; l<=(len/2) ; l++)
    {
        for (i=0 ; i<l ; i++)
        {
            q[i]=a[i];
        }
        q[i]='\0';
        v=1;
        for (i=0 ; i<len && v ; i+=l)
        {
            for (j=0 ; j<l && v ; j++)
            {
                if (q[j]!=a[i+j]) v=0;
            }
        }
        if (v) return l;
    }
    return len;

}
int main()
{
    int test, kase=1;
    scanf("%d",&test);
    getchar();
    while (test--)
    {
        gets(input);
        gets(input);
        if (kase++>1) printf("\n");
        printf("%d\n",finder(input));

    }
    return 0;
}

[UVa] 12289 - One-Two-Three

Any efficient you know about? :(

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

int tester(char *in)
{
    int len = strlen(in), i, f1, f2, f3;

    if (len == 3)
    {
        char one[]="one", two[]="two";
        for (i=0, f1=0, f2=0 ; i<3 ; i++)
        {
            if (one[i]!=in[i]) f1++;
            if (two[i]!=in[i]) f2++;
        }
        if (f1<2) return 1;
        if (f2<2) return 2;

    } else if (len == 5)
    {
        char three[]="three";
        for (i=0, f3=0 ; i<5 ; i++)
        {
            if (three[i]!=in[i]) f3++;
        }
        if (f3<2) return 3;
    }
    return 0;
}

int main()
{
    int test, res;
    char input[100];

    scanf("%d",&test);

    while (test--)
    {
        scanf("%s",input);
        res = tester(input);
        printf("%d\n",res);
    }
    return 0;
}