Sum of Consecutive Prime Numbers

ACCEPTED !!! An Opener again from Tokyo 2005/06
____________________________________________________________________
Question: Sum of Consecutive Prime Numbers
____________________________________________________________________

int isprime[10001], ind[10001], primes[10001];

int isPrime(int n) {
       int s = (int)sqrt(n);
       for(int i = 2; i <= s; i++) if(n % i == 0) return 0;
       return 1;
}

int main() {

       int pcount = 0;
       for(int i = 2; i <= 10000; i++) {
               isprime[i] = 0;
               if(isPrime(i)) {
                       isprime[i] = 1;
                       primes[pcount] = i;
                       ind[i] = pcount;
                       pcount++;
               }
       }

       while(1) {

               int n;
               cin >> n;
               if(n == 0) break;

               int p = n;
               while(!isprime[p]) p--;

               int start = ind[p];
               int sum = 0, c = 0;
               int i = start;

               while(i >= 0) {
                       while(n > sum) {
                               sum += primes[i];
                               i--;
                       }
                       if(sum == n) c++;
                       sum -= primes[start];
                       start--;
               }

               cout << c << endl;
       }

}
____________________________________________________________________

Prime Ring problem

ACCEPTED !!! A copy of this one was the opener at Coimbatore regionals 2006/07.
Its infact a simple BACKTRACKING problem
____________________________________________________________________
Question: Prime Ring Problem
____________________________________________________________________

#include "iostream.h"
#include "stdio.h"

int n, mat[17][16], isprime[32];
char seq[16];
bool used[17];

int isPrime(int n) {
   for(int i = 2; i < i ="="">
   return 1;
}

void permute(int count) {
   if(count == n && isprime[seq[0] + seq[n-1]]) {
       for(int i = 0; i <>
           if(i > 0) printf(" ");
           printf("%d", seq[i]);
       }
       printf("\n");
       return;
   }
   int last = seq[count-1];
   int non = mat[last][0];
   for(int i = 1; i <= non; i++) {
       int next = mat[last][i];
       if((next - count) % 2 != 0 && used[next] != 1) {
           used[next] = true;
           seq[count] = next;
           permute(count + 1);
           used[next] = false;
       }
   }
}

int main()
{

   for(int i = 3; i <= 31; i++ ) isprime[i] = isPrime(i);

   seq[0] = 1;
   used[1] = true;

   int t = 1;
   while(cin >> n) {
       if(t > 1) cout <<>
       cout << "Case " <<>
       t++;
       if(n % 2 == 1) continue;

       for(int i = 1 ; i <= n; i++) {
           int c = 0;
           for(int j = 2; j <= n; j++) if(isprime[i+j]) mat[i][++c] = j;
           mat[i][0] = c;
       }

       permute(1);
   }
   return 0;
}

____________________________________________________________________

Expression

ACCEPTED !! Another good one from Dhaka regionals 2006/07
____________________________________________________________________
Question: Expression
____________________________________________________________________

#include "iostream.h>
#include "stack"
using namespace std;

template 
void exchange(T *arr, int a, int b) {
   T temp = arr[a];
   arr[a] = arr[b];
   arr[b] = temp;
}

int main()
{
   int n;
   cin >> n;
   for(int i = 1; i <= n; i++) {
       char expr[200], digits[200];
       cin >> expr >> digits;
       int explen = strlen(expr);
       int dlen = strlen(digits);

       int signarr[dlen];
       int prod = 1, sign = 1;
       stack s;
       int index = 0;
       for(int j = 0; j < explen; j++) {
           if(expr[j] == '+') sign = 1;
           else if(expr[j] == '-') sign = -1;
           else if(expr[j] == '(') {
               prod *= sign;
               s.push(sign);
               sign = 1;
           }
           else if(expr[j] == ')') {
               prod *= s.top();
               s.pop();
           }
           else if(expr[j] == '#') signarr[index++] = prod * sign;
       }

       index--;
       int count = 0;
       int parr[dlen];
       for(int j = explen - 1; j >= 0; j--) {
           if(expr[j] == '#') {
               parr[index] = signarr[index] * ++count;
               index--;
           }
           else count = 0;
       }

       int indexarr[dlen];
       for(int j = 0; j < dlen; j++) indexarr[j] = j;

       int fordarr[dlen];
       for(int j = 0; j < dlen; j++) {
           int s1 = parr[j], x1 = j;
           int s2 = digits[j], x2 = j;
           for(int k = j+1 ; k < dlen; k++) {
               if(parr[k] < s1 || (parr[k] == s1 && indexarr[k] < indexarr[x1])) {
                   s1 = parr[k];
                   x1 = k;
               }
               if(digits[k] < s2) {
                   s2 = digits[k];
                   x2 = k;
               }
           }
           exchange(parr, j, x1);
           exchange(indexarr, j, x1);
           exchange(digits, j, x2);
           fordarr[indexarr[j]] = digits[j];
       }

       cout << "Case " << i << ":\n";

       index = 0;
       long long int sum = 0;
       for(int j = 0; j < explen; j++) {
           long long int val = 0;
           while(expr[j] == '#') {
               cout << char(fordarr[index]);
               int c = fordarr[index] - '0';
               val = val * 10 + signarr[index] * c;
               index++;
               j++;
           }
           if(j < explen) cout << expr[j];
           sum += val;
       }
       cout << endl;
       cout << sum << endl;
   }
   return 0;
}

____________________________________________________________________

Super long sums

Here's the problem statement: Super long sums
Accepted in the 7th try, after getting 6 Time Limit Exceeded errors. Moral of the story: don't use cin or cout as far as possible. Stick to ANSI C standards and use good ol' scanf and printf, though cumbersome!

#include "iostream"
#include "cstdio"

using namespace std;

main()
{
       int a[1000000];
       int n, i, j, x, y, m;

       cin>>n;

       for(i=0; i 0) printf("\n");
               scanf("%d", &m);
               for(j=0; j<m; j++) {
                       scanf("%d%d",&x,&y);
                       a[j] = x+y;
               }
               for(j--; j>=0; j--) {
                       if(a[j] > 9) {
                               a[j-1]++;
                               a[j] -= 10;
                       }
               }
               for(j=0; j<m; j++) printf("%d", a[j]);
               printf("\n");
       }

       return 0;
}

Potentiometers

ACCEPTED !! Another one from Dhaka regionals 2006/07
____________________________________________________________________
Question: Potentiometers
____________________________________________________________________

#include "iostream.h"
#include "math.h" 

int main()
{

   int t = 1;
   while(1) {
       int n;
       cin >> n;
       if(n == 0) break;
       if(t > 1) cout << endl;
       int parr[n];
       int r = ceil(sqrt(n));
       int c = sqrt(n);
       int sparr[r];
       for(int i = 0; i < r; i++) sparr[i] = 0;
       for(int i = 0; i < n; i++) {
           cin >> parr[i];
           sparr[i/c] += parr[i];
       }
       cout << "Case " << t << ":\n";
       while(1) {
           char command[4];
           cin >> command;
           if(strcmp(command, "END") == 0) break;
           if(strcmp(command, "S") == 0) {
               int x, r;
               cin >> x >> r;
               x--;
               sparr[x/c] += r - parr[x];
               parr[x] = r;
           }
           else if(strcmp(command, "M") == 0) {
               int x, y;
               cin >> x >> y;
               x--;
               y--;
               int sr = x/c;
               int er = y/c;
               int res = 0;
               for(int i = sr; i < er; i++) res += sparr[i];
               for(int i = sr*c; i < x; i++) res -= parr[i];
               for(int i = er*c; i <= y; i++) res += parr[i];
               cout << res << endl;
           }
       }
       t++;
   }
   return 0;
}

____________________________________________________________________

Andy's Shoes

Here's the problem statement: Andy's Shoes
Accepted in the 3rd try. The last one was with Dileep's help.

#include <iostream>
using namespace std;

void swap(int *arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}

int main() {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
                int m;
                cin >> m;
                int arr[2*m], pair[10001];
                for(int j = 0; j < 2*m; j++) {
                        cin >> arr[j];
                        pair[arr[j]] = j;
                }
  
  int s = 0;
                for(int j = 0; j < 2*m; j+=2) {
                        if(arr[j] != arr[j+1]) {
                                if(pair[arr[j+1]] < pair[arr[j]])
                                        pair[arr[j+1]] = pair[arr[j]];
                                swap(arr, pair[arr[j]], j+1);
                                s++;
                        }
                }
                cout << s << endl;
        }
}

Mobile Casanova

ACCEPTED !! Yet another opener...this one from last year's Dhaka regionals
____________________________________________________________________
Question: Mobile Casanova
____________________________________________________________________

#include "iostream.h"
#include "math.h"

int compareEnds(int start, int end) {
   int n = floor(log(start)) + 1;
   int p = 1;
   for(int i = 0; i <= n; i++) {
       if(start / p == end / p) return i;
       p *= 10;
   }
}

void printRange(int start, int count) {
   cout << "0";
   if(count == 0) cout << start << endl;
   else {
       int end = start + count;
       int d = compareEnds(start, end);
       cout << start << "-" << end % (int)pow(10, d) << endl;;
   }
}

int main()
{

   int t = 1;
   while(1) {
       int n;
       cin >> n;
       if(n == 0) break;
       cout << "Case " << t << ":\n";
       int count = 0,start;
       cin >> start;
       for(int i = 1; i < n; i++) {
           int curr;
           cin >> curr;
           if(curr == start + count + 1) count++;
           else {
               printRange(start, count);
               count = 0;
               start = curr;
           }
       }
       printRange(start, count);
       cout << endl;
       t++;
   }
   return 0;
}
____________________________________________________________________

All Integer Average

ACCEPTED !!! The opener in Dhaka regional 2004/05
____________________________________________________________________
Question: All Integer Average
____________________________________________________________________

#include "iostream.h"
#include "math.h"
#include "iomanip.h"

int HCF(int a, int b) {
   if(a % b == 0) return b;
   return HCF(b, a % b);
}

void printFraction(int n, int d) {
   int neg = 0;
   if(n < 0) {
       neg = 1;
       n *= -1;
   }
   if(d == 1) {
       if(neg) cout << "- " << n << endl;
       else cout << n << endl;
   }
   else {
       int whole = n / d;
       int fnum = n % d;
       int fden = d;
       int flen = int(floor(log(fden) / log(10)) + 1);
       int wlen = 0;
       if(whole > 0) wlen = int(floor(log(whole) / log(10)) + 1);
       int offset = wlen + flen;
       if(neg) offset += 2;
       cout << setw(offset) << fnum << endl;
       if(neg) cout << "- ";
       if(whole > 0) cout << whole;
       for(int i = 0; i < flen; i++) cout << "-";
       cout << setw(offset) << fden << endl;
   }
}

int main()
{
   int count = 1;
   while(1) {
       int n;
       cin >> n;
       if(n == 0) break;
       int sum, den = n;
       cin >> sum;
       for(int i = 2; i <= n; i++) {
           int num;
           cin >> num;
           sum += num;
       }
       int c = HCF(abs(sum), den);
       sum /= c;
       den /= c;
       cout << "Case " << count << ":\n";
       printFraction(sum, den);
       count++;
   }
   return 0;
}
____________________________________________________________________

Bachelor Arithmetic

ACCEPTED !!! I missed this one during the Dhaka regionals due to a silly error...
____________________________________________________________________
Question: Bachelor Arithmetic
____________________________________________________________________

#include "iostream.h"

int main()
{
  int count = 1;
  while(1) {
      long long int b, s;
      cin >> b >> s;
      if(b == 0 && s == 0) break;
      cout << "Case " << count << ": :-";
      if(b <= s) {
           if(b == 1) cout << "\\";
           else cout << "|";
      }
      if(b > s) cout << "(";
      cout << endl;
      count++;
  }
  return 0;
}
____________________________________________________________________

Nested Squares

This is my only ACCEPTED submission during the Dhaka regionals !!!  
____________________________________________________________________
Question: Nested Squares
____________________________________________________________________

#include "iostream.h"

int main()
{
   int ns;
   cin >> ns;
   for(int i = 1; i <= ns; i++) {
       cout << "Square " << i << ":" << endl;
       char strin[50002];
       int nq;
       cin >> strin >> nq;
       int len = strlen(strin);
       int doublen = 2 * len;

       for(int j = 1; j <= nq; j++) {
           cout << "Query " << j << ":" << endl;
           int sx, sy, bx, by;
           cin >> sx >> sy >> bx >> by;

           for(int k = sx; k <= bx; k++) {
               for(int l = sy; l <= by; l++) {
                   int x = k, y = l;
                   if(k > len) x = doublen - k;
                   if(l > len) y = doublen - l;
                   int min = (x < y)?x:y;
                   cout << strin[min-1];
               }
               cout << endl;
           }
       }
       cout << endl;
   }
   return 0;
}
____________________________________________________________________

Multifactorials

ACCEPTED !!! The UVa forum posts contain very handy test cases.. 
____________________________________________________________________
Question: Multifactorials
____________________________________________________________________

#include "iostream.h"
#include "math.h"

long long int max = pow(10, 18);
int primes[1000], pcount;

int isPrime(int n) {
   double sq = sqrt(n);
   for(int i = 2; i <= sq; i++) if(n % i == 0) return 0;
   return 1;
}

void updateFactors(int t, int *pfactorcount) {
   for(int i = 0; i < pcount; i++) {
       int p = primes[i];
       while(t % p == 0) {
           t /= p;
           pfactorcount[p]++;
       }
       if(t == 1) break;
   }
}

long long int multiFactovisors(int n, int k) {
   int stop;
   if(k == 0) stop = n;
   else {
       if(n % k == 0) stop = k;
       else stop = n % k;
   }
   int pfactorcount[1000];
   for(int i = 0; i < 1000; i++) pfactorcount[i] = 0;
   int i = 0;
   while(1) {
       int t = n - k * i;
       updateFactors(t, pfactorcount);
       i++;
       if(t == stop) break;
   }
   long long int prod = 1;
   for(int i = 0; i < pcount; i++) {
       prod *= (pfactorcount[primes[i]] + 1);
       if(prod > max || prod < 1) return 0;
   }
   return prod;
}

int main()
{
   int pindex = 0;
   for(int i = 2; i < 1000; i++) if(isPrime(i)) primes[pindex++] = i;
   pcount = pindex;

   int t;
   cin >> t;
   for(int i = 1; i <= t; i++) {
       char inp[25];
       cin >> inp;
       int n = atoi(inp);
       long long int r;
       if(n <= 0) r = 1;
       else {
           int j;
           for(j = 0; inp[j] != '!'; j++);
           int k = strlen(inp) - j;
           r = multiFactovisors(n, k);
       }
       cout << "Case " << i << ": ";
       if(r > 0) cout << r << endl;
       else cout << "Infinity\n";
   }
   return 0;
}
____________________________________________________________________

Newspaper

The UVa forum to the rescue again... ACCEPTED !!!  
____________________________________________________________________
Question: Newspaper
____________________________________________________________________

#include "iostream.h"
#include "iomanip.h"

int main()
{
   int n;
   cin >> n;
   for(int t = 0; t < n; t++) {

       unsigned long long int arr[256];
       for(int i = 0; i < 256; i++) arr[i] = 0;

       int k;
       cin >> k;
       for(int j = 0; j < k; j++) {
           cin.ignore();
           unsigned char key = cin.get();
           long long int value;
           cin >> value;
           arr[int(key)] = value;
       }

       int m;
       unsigned long long int pay = 0;
       cin >> m;
       cin.ignore();
       for(int i = 0; i < m; i++) {
           unsigned char c = cin.get();
           while(c != '\n') {
               pay += arr[int(c)];
               c = cin.get();
           }
       }
       cout.setf(ios::fixed);
       cout << setprecision(2) << pay / 100 << "." << setw(2) << setfill('0') << pay % 100 <<"$" << endl;
   }
   return 0;
}
____________________________________________________________________

Exhibition

ACCEPTED !! Though late, i realize how useful the UVa forum is.... 
____________________________________________________________________
Question: Exhibition
____________________________________________________________________

#include "iostream.h"
#include "iomanip.h"

int main()
{
   int t;
   cin >> t;
   for(int i = 1; i <= t; i++) {
       int type[10001];
       for(int j = 0; j < 10001; j++) type[j] = 0;
       int mat[50][52];
       int n;
       cin >> n;
       for(int j = 0; j < n; j++) {
           int m;
           cin >> m;
           mat[j][0] = m;
           mat[j][1] = 0;
           for(int k = 0; k < m; k++) {
               cin >> mat[j][k+2];
               type[mat[j][k+2]]++;
           }
       }

       int ucount = 0;
       for(int j = 0; j < n; j++) {
           for(int k = 0; k < mat[j][0]; k++) {
               type[mat[j][k+2]]--;
           }

           for(int k = 0; k < mat[j][0]; k++) {
               if(type[mat[j][k+2]] == 0) {
                   mat[j][1]++;
                   ucount++;
               }
               type[mat[j][k+2]]++;
           }
       }

       cout << "Case " << i << ":";

       cout.setf(ios::fixed);
       for(int j = 0; j < n; j++) {
           double perc = 33.333333;
           if(ucount != 0) perc = mat[j][1] * 100.00 / ucount;
           cout << setprecision(6) << " " << perc << "%";
       }
       cout << endl;
   }
   return 0;
}
____________________________________________________________________

The Huge One

ACCEPTED !!!  really HUGE but straightforward ...
____________________________________________________________________
Question: The Huge One

____________________________________________________________________

#include "iostream.h"
#include "string.h"

int divisible(char *num, int k) {
   int len = strlen(num), v, v0, v1, v2, last2, last3, sum, sum1, sum2, i;
   char bkp[1002];
   switch(k) {
   case 1:
        return 1;
   case 2:
        v0 = num[len - 1] - '0';
        if(v0 % 2 == 0) return 1;
        return 0;
   case 3:
        sum = 0;
        for(int i = 0; i < len; i++) sum += num[i] - '0';
        if(sum % 3 == 0) return 1;
        return 0;
   case 4:
        v0 = num[len - 1] - '0';
        v1 = num[len - 2] - '0';
        last2 = v1 * 10 + v0;
        if(last2 % 4 == 0) return 1;
        return 0;
   case 5:
        if((num[len - 1] - '0') % 5 == 0) return 1;
        return 0;
   case 6:
        v0 = num[len - 1] - '0';
        sum = 0;
        for(int i = 0; i < len; i++) sum += num[i] - '0';
        if(v0 % 2 == 0 && sum % 3 == 0) return 1;
        return 0;
   case 7:
        strcpy(bkp, num);
        i = 0;
        while(i < len - 1) {
            v1 = bkp[i] - '0';
            v0 = bkp[i + 1] - '0';
            v = v1 * 3 + v0;
            bkp[i] = v / 10 + '0';
            bkp[i + 1] = v % 10 + '0';
            if(bkp[i] == '0') i++;
        }
        if((bkp[i] - '0') % 7 == 0) return 1;
        return 0;
   case 8:
        v0 = num[len - 1] - '0';
        v1 = num[len - 2] - '0';
        v2 = num[len - 3] - '0';
        last3 = v2 * 100 + v1 * 10 + v0;
        if(last3 % 8 == 0) return 1;
        return 0;
   case 9:
        sum = 0;
        for(int i = 0; i < len; i++) sum += num[i] - '0';
        if(sum % 9 == 0) return 1;
        return 0;
   case 10:
        if((num[len - 1] - '0') == 0) return 1;
        return 0;
   case 11:
        sum1 = 0;
        sum2 = 0;
        for(int i = 0, j = 1; i < len || j < len; i += 2, j += 2) {
            if(i < len) sum1 += num[i] - '0';
            if(j < len) sum2 += num[j] - '0';
        }
        if((sum1 - sum2) % 11 == 0) return 1;
        return 0;
   case 12:
        sum = 0;
        for(int i = 0; i < len; i++) sum += num[i] - '0';
        v0 = num[len - 1] - '0';
        v1 = num[len - 2] - '0';
        last2 = v1 * 10 + v0;
        if(sum % 3 == 0 && last2 % 4 == 0) return 1;
        return 0;
   default:
        return 1;
   }
}

int main()
{
   int n;
   cin >> n;
   for(int t = 1; t <= n; t++) {
       char hugenum[1002];
       cin >> hugenum;
       int m;
       cin >> m;
       int j, k;
       for(j = 0; j < m; j++) {
           cin >> k;
           int r = divisible(hugenum, k);
           if(r == 0) break;
       }
       cout << hugenum;
       if(j == m) cout << " - Wonderful." << endl;
       else cout << " - Simple." << endl;
       while(m > ++j) cin >> k;
   }
   return 0;
}
____________________________________________________________________

Symmetric Matrix

ACCEPTED...Among the simplest i have seen.
____________________________________________________________________
Question: Symmetric Matrix
____________________________________________________________________
#include "iostream.h"
#include "math.h"
int main()
{
int t;
cin >>t;
for(int i = 1; i <= t; i++) {
    cin.ignore(4);
    int n, sym = 1;
    cin >> n;
    long long int mat[n][n];
    for(int j = 0; j < k =" 0;">> mat[j][k];
    for(int j = 0; j <= ceil(n/2); j++) for(int k = 0; k < n; k++) if(mat[j][k] < 0 || mat[j][k] != mat[n - j - 1][n - k - 1]) sym = 0;
    cout << "Test #" << i << ": ";
    if(sym) cout << "Symmetric.\n";
    else cout << "Non-symmetric.\n";
}
return 0;
}
____________________________________________________________________ 

Rectangles

Back in preparation after a while ... ACCEPTED !
____________________________________________________________________
Question: Rectangles
____________________________________________________________________

#include "iostream.h"

int max(int a, int b) {
  return (a > b)? a : b;
}

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

int main()
{
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
      int m;
      cin >> m;
      int smallx, smally, bigx, bigy;
      cin >> smallx >> smally >> bigx >> bigy;
      int j;
      for(j = 1; j < m; j++) {
          int sx, sy, bx, by;
          cin >> sx >> sy >> bx >> by;
          smallx = max(smallx, sx);
          smally = max(smally, sy);
          bigx = min(bigx, bx);
          bigy = min(bigy, by);
          if(smallx > bigx || smally > bigy) break;
      }
      int dummy;
      while(j++ < (m - 1)) cin >> dummy >> dummy >> dummy >> dummy;
      long long int area = (bigx - smallx) * (bigy - smally);
      if(area <= 0) area = 0;
      cout << "Case " << i << ": " << area << endl;
  }
  return 0;
}

____________________________________________________________________

Strings

Problem Statement: Strings
I couldn't verify my answer coz it's from an IIT site - no solution verifier. So I'm just posting my algo, not the code...

Key:
n : number of chars per string
k : number of strings
alpha[] : a 26 element int array which stores the number of occurrences of each alphabet in a column

input n,k;
input the strings;
for i = 1 to n { //for each character
for j = 1 to k { //for each string
InitAlpha();
alpha[strs[j][i]-'a']++;
}
noOfM += FindNoOfMaxAlpha();
dist += k - alpha[FindMaxAlpha()];
}

InitAlpha()
{
for i=1 to 26
alpha[i] = 0;
}

FindMaxAlpha() //returns index (a=1,b=2,...) of the alphabet that has occurred max times in arr alpha[]
{
max = 0;
maxAlpha = 0; //index of alphabet that occurs max no of times
for i = 1 to 26 {
if alpha[i] > max {
max = alpha[i]
maxAlpha = i;
}
}
return i;
}

/* FindNoOfMaxAlpha()
* if only one char occurs max times in alpha[] returns 1
* otherwise, if there are >1 chars which occur max times, returns the no of such chars
*/
FindNoOfMaxAlpha()
{
noOfMax = 0;
max = 0;
for i = 1 to k {
if (alpha[i] > max) {
max = alpha[i];
noOfMax = 1;
}
else if (alpha[i] == max) noOfMax++;
}
return noOfMax;
}

Coupons

ACCEPTED in the 5th attempt !! Too many careless errors....
____________________________________________________________________
Question: Coupons
____________________________________________________________________

#include "iostream.h"
#include "math.h"
#include "iomanip.h"

long long int HCF(long long int big, long long int small) {
      if(big % small == 0) return small;
      return HCF(small, big % small);
}

long long int LCM(long long int a, long long int b) {
      return a * b / HCF(a, b);
}

long long int nLCM(int n) {
      if(n == 1) return 1;
      return LCM(n, nLCM(n - 1));
}

int countDigits(long long int n) {
      int i;
      if(!n) return 1;
      for(i = 0; n; i++) n/=10;
      return i;
}

int max(int a, int b) {
      return (a > b)? a : b;
}

int main() {
      int n;
      while(cin >> n) {
              long long int numer = 0;
              long long int denom = nLCM(n);
              for(int k = 1; k <= n; k++) numer += denom / k;
              denom /= n;
              long long int hcf = HCF(numer, denom);
              numer /= hcf;
              denom /= hcf;
              long long int whole = numer / denom;
              numer = numer % denom;
              int wn = countDigits(whole);
              int fn = max(countDigits(numer), countDigits(denom));
              if(numer == 0) cout << whole << endl;
              else {
                      cout << setw(wn + 1) << " " << numer << endl;
                      cout << whole << " " << setw(fn) << setfill('-') << "" << endl;
                      cout << setw(wn + 1) << setfill(' ') << " " << denom << endl;
              }
      }
      return 0;
}
____________________________________________________________________

Light, More Light

ACCEPTED !! Simpler than i thought....
____________________________________________________________________
Question: Light, More Light

____________________________________________________________________

#include "iostream.h"
#include "math.h"

int main() {
       while(true) {
               unsigned int n;
               cin >> n;
               if(n == 0) break;
               int root = sqrt(n);
               if((root * root) == n) cout << "yes\n";
               else cout << "no\n";
       }
       return 0;
}

____________________________________________________________________

Dropping Water Balloons

ACCEPTED again !!! This one was good....
____________________________________________________________________
Question: Dropping Water Balloons

____________________________________________________________________

#include "iostream.h"

long long int floor[64][101];

long long int maxFloors(int t, int k) {
       if(floor[t][k] != 0) return floor[t][k];
       if(t == 1) floor[t][k] = 1;
       else if(k == 1) floor[t][k] = t;
       else floor[t][k] = 1 + maxFloors(t - 1, k - 1) + maxFloors(t - 1, k);
       return floor[t][k];
}

int main() {
       long long int n;
       int k, t;
       while(true) {
               cin >> k;
               cin >> n;
               if(k == 0) break;
               for(t = 1; t <= 63; t++) if(maxFloors(t, k) >= n) break;
               if(t > 63) cout << "More than 63 trials needed.\n";
               else cout << t << endl;
       }
       return 0;
}
____________________________________________________________________

Funny Encryption

I am seeing myself ACCEPTED more often nowadays...
____________________________________________________________________
Question: Funny Encryption Method
____________________________________________________________________

#include "iostream.h"

int countSetBits(int n) {
       int count = 0;
       while(n) {
               n = n & (n - 1);
               count++;
       }
       return count;
}

int main() {
       int n, m, b1, b2;
       cin >> n;
       for(int i = 1; i <= n; i++) {
               cin >> m;
               b1 = countSetBits(m);
               b2 = 0;
               while(m) {
                       b2 += countSetBits(m % 10);
                       m = m / 10;
               }
               cout << b1 << " " << b2 << endl;
       }
       return 0;
}
____________________________________________________________________

Euclidian Clock

I chose this one randomly from Algorithmist
____________________________________________________________________
Question: Euclidian Clock
____________________________________________________________________

#include "iostream.h"
#include "math.h"
#include "iomanip.h"

int main() {
     double d, h, m, s, u;
     double hrs1, hrs2, pi = 2*acos(0), ans, area, r;
     cin >> d;
     for(int i = 1; i <= d; i++) {
             cin >> h>> m>> s >> u;
             hrs1 = h + m/60 + s/3600 + u/360000;
             cin >> h>> m>> s >> u;
             hrs2 = h + m/60 + s/3600 + u/360000;
             cin >> r;
             area = pi * r * r;
             ans = (hrs2 - hrs1)/12 * area;
             cout << i << ". " << fixed << setprecision(3) << ans << endl;
     }
     return 0;
}
____________________________________________________________________

Cutting Sticks

Yeah!!! Another one ACCEPTED...
____________________________________________________________________
Question: Cutting Sticks
____________________________________________________________________

#include "iostream.h"

int cut[52], cost[52][52];

int minCost(int start, int end) {
   if(cost[start][end] != -1) return cost[start][end];
   if(start + 1 == end) return cost[start][end] = 0;
   int min = 65536;
   for(int i = start + 1; i < end; i++) {
       int c = minCost(start, i) + minCost(i, end) + (cut[end] - cut[start]);
       if(c < min) min = c;
   }
   return cost[start][end] = min;
}

int main()
{
   int l, n;
   while(true) {
        cin >> l;
        if(l == 0) break;
        cin >> n;
        cut[0] = 0;
        for(int i = 1; i <= n; i++) cin >> cut[i];
        cut[n + 1] = l;
        for(int i = 0; i <= n + 1; i++) for(int j = 0; j <= n + 1; j++) cost[i][j] = -1;
        cout << "The minimum cutting is " << minCost(0, n + 1) << ".\n";
   }
   return 0;
}

____________________________________________________________________

Wythoff's Game

This one is not there in UVa online judge . Hope it works !
____________________________________________________________________
Question: Wythoff's Queen Game
____________________________________________________________________

#include "iostream.h"
#include "math.h"

int main() {
     int n, x, y, small, big, diff;
     float phi = (sqrt(5) + 1)/2;
     cin >> n >> x >> y;
     x--;
     y = n - y;
     small = (x < y)?x:y;
     big = x + y - small;
     diff = floor(small / phi);
     if(small + diff + 1 == big) cout << "2\n";
     else cout << "1\n";
     return 0;
}
____________________________________________________________________

Jolly Jumpers

Corrected & Accepted !!! (Thanks to xanden for his comments) 
____________________________________________________________________
Question: Jolly Jumpers
____________________________________________________________________

#include "iostream.h"

int main()
{
 int n, n1, n2, arr[3001], diff, flag;
 while(cin >> n) {
     for(int i = 1; i < n; i++) arr[i] = 0;
     cin >> n1;
     flag = 0;
     for(int i = 1; i < n; i++) {
         cin >> n2;
         diff = (n1 > n2)?(n1 - n2):(n2 - n1);
         if(diff > 0 && n > diff) {
             if(arr[diff] != 1) arr[diff] = 1;
             else flag = 1;
         }
         else flag = 1;
         n1 = n2;
     }
     if(flag == 0) cout << "Jolly" << endl;
     else cout << "Not jolly" << endl;
 }
 return 0;
}
____________________________________________________________________

The Trip

I have absolutely no clue of why This one is getting a WRONG ANSWER !!!!
____________________________________________________________________
Question: The Trip
____________________________________________________________________

#include "iostream.h"
#include "math.h"

int main()
{
  double sum;
  float avg, arr[1000], xchg, diff;;
  int n;
  while(true) {
      cin >> n;
      if(n == 0) break;
      sum = 0;
      for(int i = 0; i < n; i++) {
          cin >> arr[i];
          sum += arr[i];
      }
      avg = sum / n;
      avg = floor(avg * 100 + 0.5) / 100;
      xchg = 0;
      for(int i = 0; i < n; i++) {
          diff = arr[i] - avg;
          if(diff > 0) xchg += diff;
      }
      cout << "$" << xchg << endl;
  }
  return 0;
}

____________________________________________________________________

Minesweeper

ACCEPTED at last after a long stand with a presentation error!!!
____________________________________________________________________
Question: Minesweeper
____________________________________________________________________

#include "iostream.h"

int arr[102][102];

void increment(int i, int j) {
if(arr[i][j] != -1) arr[i][j]++;
}

int main()
{
int n, m;
char c;

int count = 1;
while(true) {
    cin >> n >> m;
    if(n == 0 && m == 0) break;
    if(count > 1) cout << "\n"; 
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) arr[i][j] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> c;
            if( c == '*') {
                arr[i][j] = -1;
                increment(i, j + 1);
                increment(i, j - 1);
                increment(i + 1, j);
                increment(i + 1, j + 1);
                increment(i + 1, j - 1);
                increment(i - 1, j);
                increment(i - 1, j + 1);
                increment(i - 1, j - 1);
            }
        }
    }

    cout << "Field #" << count++ << ":" << endl;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(arr[i][j] == -1) cout << '*';
            else cout << arr[i][j];
        }
        cout << endl;
    }
}
return 0;
}
____________________________________________________________________

3n + 1 problem

Phewwww...At last i got my first correct submission at UVa online judge. Not anything spectacular. Its the same old 3n + 1 problem....Here is the perfect working code
____________________________________________________________________
Question: 3n + 1 problem
____________________________________________________________________

#include "iostream.h"

int cyclen[1000001];

int findCycleLength(int num) {
   int l = 0, index = num;
   long long n = num;
   if(cyclen[n] != 0) return cyclen[n];
   while(n != 1) {
       if(n <= 1000000) if(cyclen[n] != 0 ) return cyclen[index] = l + cyclen[n];
       if(n % 2 == 0) n/= 2;
       else n = 3 * n + 1;
       l++;
   }
   return cyclen[index] = l + 1;
}

int main()
{
   int i,j;

   while(true) {
       cin >> i >> j;
       if(cin.eof()) break;
       int min = (i < j)? i : j;
       int max = (i > j)? i : j;
       int maxlen = 0,len;
       for(int k = 0; k <= 1000000; k++) cyclen[k] = 0;
       for(int k = min; k <= max; k++) if((len = findCycleLength(k)) > maxlen) maxlen = len;
       cout << i << " " << j << " " << maxlen << endl;
   }
   return 0;
}

____________________________________________________________________