[UVa] 12032 - The Monkey and the Oiled Bamboo

A very simple problem but the conditions have to be understood very carefully.

Method: Simple, on the fly.

Initialize the value of k with the first jump (from ground to first rung)
If (jump == capacity)
    capacity decreases by 1
If (jump > current capacity)
    Check if jump == k, increase k by 1. Reset capacity to k
    Check if jump > k, set k = jump, Reset capacity to k-1
    Check if jump < k increase k by 1. Reset capacity to k

#include <stdio.h>

typedef int lint;



lint val[100000 + 10];

int main( void ) {
 
 lint n, i, k, v, kase=1, kounter;
 
 val[0]=0;
 
 scanf("%d",&kounter);
 
 while (kounter--) {
  scanf("%d",&n);
  
  for (i=1 ; i<=n ; i++) {
   scanf("%d",&val[i]);
  }
  
  k = val[1];
  v = val[1];
  
  for (i=0 ; i<n ; i++) {
   if (val[i+1]-val[i]>v) {
    if (val[i+1]-val[i]==k) {
     k++;
     v=k;
    } else if (val[i+1]-val[i]>k) {
     k=val[i+1]-val[i];
     v=k-1;
    } else {
     k++;
     v=k;
    }
   } else if (val[i+1]-val[i]==v) {
    v--;
   }
   
  }
  printf("Case %d: %d\n",kase++,k);
 
 }
 return 0;
}

[UVa] 12414 - Calculating Yuan Fen

Method: Simulate it, nothing special. But don't handle with strings. TLE for sure then.

#include <stdio.h>

int y(char *s, int st) {
 int val[100], stor[100], v, i, j, k=0;
 for (i=0 ; s[i] ; i++) {
  v = s[i]+st-'A';
  for (j=0 ; v ; j++, v/=10) {
   stor[j] = v%10;
  }
  for (--j ; j>=0 ; j--, k++) {
   val[k] = stor[j];
   
  }
 }
 
 
 while (k>2) {
  for (i=0, j=0 ; j<k ; j++, i++) {
   val[i] = (val[j]+val[j+1])%10;
  }
  if (k==4) {
   if (val[0]==1 && val[1]==0 && val[2]==0) {
    return 100;
   }
  }
  k--;
 }
 return 0;
}

int main( void ) {
 char input[20];
 int i, found, result;
 while ( gets(input) ) {
  
  for (i=1, found=0 ; i<=10000 && found==0 ; i++) {
   result = y(input, i);
   if (result == 100) {
    found = 1;
   }
  }
  if (found == 1) {
   printf("%d\n",i-1);
  } else {
   printf(":(\n");
  }
 }
 return 0; 
}

[UVa] 10940 - Throwing Cards Away II

This is a problem of case study and math. Create a program that simulates the process and find the pattern.

Inputs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Outputs:

1
2
2
4
2
4
6
8
2
4
6
8
10
12
14
16
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32

Once you find the pattern its straightforward.
1. Find the nearest 2^X such that 2^X <= N
2. If 2^X == N, output N
    Else output (N-2^X)*2

[Codechef] ATM (HS08TEST)

The problem is totally straightforward. Only possible cause for wrong answer response is if x = y. In that case you should check if x+0.5 > y or not.

#include <stdio.h>

int main()
{
    int x;
    double y;
    while (scanf("%d %lf",&x,&y)==2)
    {
        if (!(((double)x+0.5)>y) && !(x%5))
            printf("%.2lf\n",y-(double)x-0.5);
        else
            printf("%.2lf\n",y);
    }
    return 0;
}

[UVa] 11150 - Cola

It was pretty disgusting for me all this time that I couldn't solve this one. I've been a pro at all of it's similar ones. This one actually gave me a very generalized approach.
I exhaustively checked for every possible borrowing. For one thing to be noted, you can borrow a max of 2 bottles. How? Just examine the 200 case without borrowing. In the end you'll have 2 unused bottles. Since it's the highest case, so there can be a max of 2 unused bottles, so a max of 2 returnable bottles/borrowable bottles. :|

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;


int proc(int n, int borrow)
{
    int cola = 0-borrow;
    while (n>=3)
    {
        cola += n;
        cola -= n%3;
        n = (n/3 + (n%3));
    }
    cola += n;
    if (n<borrow) return -1;
    else return cola;
}

int results[300];

int main()
{
    int i, res1, res2, res3;

    for (i=0 ; i<=200 ; i++)
    {
        res1 = proc(i, 0);

        res2 = proc(i+1, 1);

        res3 = proc(i+2, 2);


        results[i] = max(max(res1,res2),max(res2,res3));
    }

 //freopen("input.txt","r+",stdin);
 //freopen("output.txt","w+",stdout);/**/

 //    TEST CASE     //
 /*int kase=1, kounter=1;/**/

 while (scanf("%d",&i)==1)
 {
     printf("%d\n",results[i]);
 }
 return 0;
}

[UVa] 11679 - Sub Prime

At a first glance, in particular after reading the name, at least I thought it's about Primes :P. It's pure ad hoc, simulation.

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

class bank
{
    public:
    int tot_money;
    vector< pair<int,int> > dList;
    void init() {tot_money=0; dList.clear();}
};

bank banks[30];

int main()
{

    //freopen("in.txt","r+",stdin);
    //freopen("out.txt","w+",stdout);


    int b, n, d, c, m, i, j, increase, decrease;
    bool valid;

    while (scanf("%d %d",&b,&n)==2)
    {
        if (!b && !n)
            break;
// Input Start
        for (i=1 ; i<=b ; i++)
        {
            banks[i].init();
            scanf("%d",&banks[i].tot_money);

        }

        for (i=1 ; i<=n ; i++)
        {
            scanf("%d %d %d",&d,&c,&m);

            banks[d].dList.push_back( make_pair(c,m) );
        }
// Input End


// Process Start
        for (i=1 ; i<=b ; i++)
        {
            for (j=0 ; j<banks[i].dList.size() ; j++)
            {
                increase = banks[i].dList[j].first;
                decrease = banks[i].dList[j].second;

                banks[increase].tot_money+=decrease;
                banks[i].tot_money-=decrease;
            }
        }


        for (i=1, valid=true ; i<=b ; i++)
        {
            if (banks[i].tot_money<0)
            {
                valid = false;
                break;
            }
        }

        if (valid) printf("S\n");
        else printf("N\n");

// Process End

    }
    return 0;
}

[UVa] 12114 - Bachelor Arithmetic

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ERROR 1e-11
using namespace std;
typedef double dt;

dt min(dt a, dt b)
{
    return (a<b?a:b);
}

int main()
{
    dt s, b, nx_pro, pr_pro;
    int kase=1;

    while (cin >> b >> s)
    {
        if (fabs(b-0.00)<ERROR && fabs(s-0.00)<ERROR) break;

        cout << "Case " << kase++ << ": ";
        pr_pro = min(s/b,(dt)1);
        if (b==1.00)
        {
            cout << ":-\\" << endl;
            continue;
        }
        nx_pro = min((s-(dt)1)/(b-(dt)1),(dt)1);

        if (nx_pro>pr_pro) cout << ":-)" << endl;
        else if (nx_pro<pr_pro) cout << ":-(" << endl;
        else cout << ":-|" << endl;
    }

    return 0;
}

[UVa] 11958 - Coming Home

#include <stdio.h>

int main()
{
    int test, bn, ch, cm, ah, am, dur, i, cur_time, arr_time, min_time, spend, kase=1;
    scanf("%d",&test);

    while (test--)
    {
        min_time = 1000000;

        scanf("%d %d:%d",&bn,&ch,&cm);

        cur_time = ch*60 + cm;

        for (i=0 ; i<bn ; i++)
        {
            scanf("%d:%d %d",&ah,&am,&dur);

            arr_time = ah*60 + am;

            if (arr_time<cur_time) spend = 1440 - cur_time + arr_time + dur;
            else spend = arr_time - cur_time + dur;

            if (min_time>spend) min_time = spend;
        }

        printf("Case %d: %d\n",kase++,min_time);
    }

    return 0;
}

[UVa] 10161 - Ant on a Chess Board

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

ll sum(ll n)
{
    return n*n;
}

int main()
{
    ll i, lev, lim, mid;

    while (cin >> i && i)
    {
        lev = (ll)ceil(sqrt(i));
        if (lev&1)
        {
            lim = lev*lev;
            mid = lim - (lev-1);
            if (i<mid)
            {
                cout << lev << " " << i-(lev-1)*(lev-1) << endl;
            } else
            {
                cout << lim-(i)+1 << " " << lev << endl;
            }
        } else
        {
            lim = lev*lev;
            mid = lim - (lev-1);
            if (i>=mid)
            {
                cout << lev << " " << lim-i+1 << endl;
            } else
            {
                cout << i-(lev-1)*(lev-1) << " " << lev << endl;
            }
        }
    }
    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] 11428 - A Minimum Land Price

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
ll pr(ll a, ll t)
{
    ll ret=1;
    while (t--)
        ret*=a;
    return ret;
}
ll a[100];
int cmp (const void *a, const void *b)
{
    return *(ll*)b-*(ll*)a;
}
int main()
{
    ll test, i, sum, j;
    scanf("%lld",&test);

    while (test--)
    {
        for (i=0 ; scanf("%lld",&a[i]) && a[i] ; i++);
        qsort(a,i,sizeof(ll),cmp);

        for (sum=0, j=0 ; j<i ; j++ )
        {
            sum += (pr(a[j],j+1));
        }
        sum *= 2;
        if (sum<=5000000)
            printf("%lld\n",sum);
        else
            printf("Too expensive\n");
    }
    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] 11850 - Alaska

With this, I finish 300 solves in UVa. :) Took too long.
My stats at the moment:

Submissions: 1701
Problems tried: 322
Problems solved: 300
First submission: 2009-11-17
Last submission: 2011-10-21

And details on the last submission:
Problem number: 11850
Rank of solution: 225
Submission number: 9395891
Date: 2011-10-21
Time: 20:54:39
Runtime: 0.008

Method:
1. Take the input and sort the array.
2. Check if between two consecutive stations the distance is > 200. If so IMPOSSIBLE
3. At last she has to go to the destination and come back to the last station, so check if (1422-[last station])X2 > 200.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
int miles[4000];
int main()
{
    int n, i, set;
    while (scanf("%d",&n) && n)
    {
        for (i=0 ; i<n ; i++)
            scanf("%d",&miles[i]);
        qsort(miles,n,sizeof(int),cmp);
        set=1;

        for (i=1 ; i<n && set ; i++)
        {
            if (miles[i]-miles[i-1]>200) set=0;
        }
        if (2*(1422-miles[n-1])>200) set=0;
        if (set) printf("POSSIBLE\n");
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

[UVa] 10432 - Polygon inside a circle

#include <stdio.h>
#include <math.h>
#define PI (2*acos(0))
int main()
{
    double area, r, n;
    while (scanf("%lf %lf",&r,&n)==2)
    {
        area = r*r*sin(2*PI/n)/2.0;
        printf("%.3lf\n",area*n);
    }
    return 0;
}

[UVa] 11650 - Mirror Clock

Nice and fun! The only tricky case probably is a time that generated 0 hours, just make it 12 but keep the minute same. I don't know if handling for 24 hours time is needed but added that too.

#include <stdio.h>

int main()
{
    int tst, h, m, time;
    scanf("%d",&tst);
    while (tst--)
    {
        scanf("%d:%d",&h,&m);
        time = h*60 + m;
        if (time>720) time-=720;
        time = 720-time;

        h = (time/60);
        m = time%60;

        if (!h) h = 12;

        if (h<10)
            printf("0%d:",h);
        else
            printf("%d:",h);
        if (m<10)
            printf("0%d\n",m);
        else
            printf("%d\n",m);
    }
    return 0;
}

[UVa] 10550 - Combination Lock

#include <stdio.h>

/* Guilty by association */

int main()
{
    int i, a, b, c, deg;
    while (scanf("%d %d %d %d",&i,&a,&b,&c)==4)
    {
        if (!i && !a && !b && !c) break;

        deg = 720+360 + (((a>i?(40-a)+i:(i-a)) + (b<a?(40-a)+b:(b-a)) + (c>b?(40-c)+b:(b-c))))*9;

        printf("%d\n",deg);
    }
    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] 278 - Chess

Analyze all 4 cases and soon you'll equations for all of them. The given advantage is the lower limit of 4. Below that the derived theorems fail.

#include <stdio.h>
#include <string.h>
#define min(a,b) (a<b?a:b)
char inp[100];
int main()
{
    int test, x, y;
    char a;
    scanf("%d",&test);
    getchar();
    while (test--)
    {
        gets(inp);


        sscanf(inp,"%c %d %d",&a,&x,&y);
        if (a=='k')
        {
            printf("%d\n",(x*y+1)/2);
        } else if (a=='K')
        {
            printf("%d\n",((x+1)/2) * ((y+1)/2));
        } else if (a=='Q'||a=='r')
        {
            printf("%d\n",min(x,y));
        }
    }
    return 0;
}