Repeated Squaring

http://www.algorithmist.com/index.php/Repeated_Squaring

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute xy for an arbitrary integer y.

 

// Calculates n to the p power, where p is a positive number.
func power( var n as integer, var p as integer )
   if p = 0 return 1
   if p = 1 return n
   if p is odd
      return n * power( n * n, (p-1) / 2 )
   else
      return power( n * n, p / 2 )
end func

quadtree

http://en.wikipedia.org/wiki/Quadtree

UVa problem: 297: Quadtrees

refer to forum: http://acm.uva.es/board/viewtopic.php?f=2&t=700&p=2691&hilit=297&sid=156699fafa75aaeacf281e1af3a8006c#p2691

#include <iostream>

#define M 32
int p[M];
int idx;

int mask[] = {
  0, 0x1, 0x3, 0, // 0-3
  0xf, 0, 0, 0, 0xff, //4-8
  0,0,0,0,0,0,0,0xffff, // 16
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xffffffff // 32
};

#ifndef ONLINE_JUDGE
// couting 1's
int count_bit(int n) {
    int bits = 0;
    while(n) {
        n &= n-1;
        ++bits;
    }
    return bits;
}
#endif

void color (char *str, int size, int x, int y) {
  if (str[idx] == 'p') {
    idx ++;
    int sz = size>>1;
    color(str, sz, x+sz, y);
    color(str, sz, x, y);
    color(str, sz, x, y+sz);
    color(str, sz, x+sz, y+sz);
  }
  else if (str[idx] == 'f') {
    idx ++;
    for (int i = y; i < y + size; i ++)
      p[i] |= mask[size] << x;
  }
  else idx++;
}
int main () {
  int num;
  char tree1[1500], tree2[1500];

  scanf("%d\n", &num);
  while(num--) {
    scanf("%s\n%s\n", tree1, tree2);

    memset(p, 0, sizeof(p));

    idx=0;
    color(tree1, M, 0, 0);

    idx=0;
    color(tree2, M, 0, 0);

    int total = 0;
    for (int i = 0; i < M; i ++)
#ifndef ONLINE_JUDGE
      total += count_bit(p[i]);
#else
      total += __builtin_popcount(p[i]);
#endif

    printf("There are %d black pixels.\n", total);
  }
  return 0;
}

UVa problem: 752 - Unscrambling Images

#include <iostream>
#include <deque>
using namespace std;
int q[16][16];
int e[16][16]; // encrypted

int d[16][16]; // decoded
inline int getxy(int size, int k, int &x, int &y) {

  deque<int> Q;
  while(k > 0) {
    int r = k % 4;
    if (r == 0) {
      r = 4;
      k = (k-4) >> 2;
    } else
      k = k >>2;

    Q.push_front(r);
  }

  x = 0, y = 0;
  for(int i = 0; i < Q.size(); ++i) {
    size = size >> 1;
    int idx = Q[i];

    if (idx == 2)
      y += size;
    if (idx == 3)
      x += size;
    if (idx == 4) {
      x += size;
      y += size;
    }
  }
  return size;
}

int main() {
  int ndata;
  scanf("%d ", &ndata);
  int nd = 1;
  while(nd <= ndata) {
    if(nd > 1) printf("\n");
    printf("Case %d\n\n", nd++);
    int n;
    scanf("%d ", &n);

    // quadtree reset to all 0
    memset(q, 0, sizeof(q));

    int m; // number of leaf nodes

    scanf("%d ", &m); 
    int k;
    int intensity;
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          q[i][j] = intensity;      
    }
/*
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", q[i][j]);
      printf("\n");
    }
    printf("\n");
*/
    scanf("%d ", &m);

    // encrypted quadtree reset to all 0
    memset(e, 0, sizeof(e));
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          e[i][j] = intensity;
    }

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        int x = q[i][j] / n;
        int y = q[i][j] % n;
        d[x][y] = e[i][j];
      }
    }
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", d[i][j]);
      printf("\n");
    }
  }
}

Add without +

Write a program to add two numbers a and b.
1. Without Using + operator
2. Without using any loops

Sum = A XOR B
Carry = A AND B

#include <iostream>

int add(int p, int q)
{
  if(q == 0)
    return p;
  int k, r;
  k = p ^ q;
  r = p & q;
  return add(k, r<<1); // carry left shift 1 bit
}

int main() {
  printf("%d\n", add(4,7));
  printf("%d\n", add(401,7));
  printf("%d\n", add(14,7));
  printf("%d\n", add(4,47));
  printf("%d\n", add(4,-97));
  printf("%d\n", add(-4,-97));
}

output:

11
408
21
51
-93
-101

Tree Recovery

Problem UVa: 536 - Tree Recovery

给了pre-order 和 in-order traversal 序列，要求输出post-order

The idea behind the code below is this:
1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree

/* 536 - Tree Recovery */
/* recursion */

#include <iostream>
char preorder[30];
char inorder[30];

void recover(int x1, int y1, int x2, int y2) {

    char t = preorder[x1];
    if(x1 == y1) {
        printf("%c", t);
        return;
    }  

    // locate the root position in in-order 
    // which split the travel seq into two halves
    int pos;
    for(int i = x2; i <= y2; ++i)
        if(inorder[i] == t) {
            pos = i;
            break;
        }

    int p = x1+pos-x2;

    // visit left sub-tree
    if(pos-1 >= x2)
        recover(x1+1, p , x2, pos-1);
    // visit right sub-tree
    if(y2 >= pos+1)
        recover(p+1, y1, pos+1, y2);

    // postorder -> print root at last
    printf("%c", t);
}
int main() {

    while(scanf("%s %s ",preorder, inorder) != EOF) {
        int L = strlen(preorder) - 1;
        recover(0, L, 0, L); // first <0,L> is preorder index, second <0,L> is in-order index
        printf("\n");
    }
}

Problem UVa: 10410 Tree Reconstruction

给了BFS和DFS traversal序列，要输出每个节点和它相应的叶子结点