Maybe the most unfamous realistic poet whom is also the only application programmer which know protected mode operating system best in mainland!

http://poj.org/problem?id=2935

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 static int x1,y1,x2,y2,l;
 static boolean[][] p=new boolean[8][8];
 static int[] ax1,ay1,ax2,ay2;
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   String[] ss;
   while(true)
   {
    for(int i=0;i< 8;i++)
        for(int j=0;j< 8;j++)
            p[i][j]=false;
    for(int i=0;i< 8;i++)
    {
        p[0][i]=true;
        p[7][i]=true;
        p[i][0]=true;
        p[i][7]=true;
    }
    ax1=new int[50];
    ay1=new int[50];
    ax2=new int[50];
    ay2=new int[50];
    l=0;
    ss=in.readLine().split(" ");
    y1=Integer.parseInt(ss[0]);
    x1=Integer.parseInt(ss[1]);
    if(x1==0&&y1==0)break;
    ss=in.readLine().split(" ");
    y2=Integer.parseInt(ss[0]);
    x2=Integer.parseInt(ss[1]);
    int a1,a2,b1,b2;
    for(int i=0;i< 3;i++)
    {
        ss=in.readLine().split(" ");
        a1=Integer.parseInt(ss[0]);
        b1=Integer.parseInt(ss[1]);
        a2=Integer.parseInt(ss[2]);
        b2=Integer.parseInt(ss[3]);
        if(a1==a2)
        {
          if(b1>b2)
          {
            int temp=b1;
            b1=b2;
            b2=temp;
           }
           for(int j=b1+1;j<=b2;j++)
           {
            ay1[l]=a1;
            ay2[l]=a1+1;
            ax1[l]=ax2[l]=j;
            l++;
            }
        }
        if(b1==b2)
        {
          if(a1>a2)
          {
            int temp=a1;
            a1=a2;
            a2=temp;
           }
          for(int j=a1+1;j<=a2;j++)
          {
            ax1[l]=b1;
            ax2[l]=b1+1;
            ay1[l]=ay2[l]=j;
            l++;
           }
        }
    }
    bfs();
    System.out.println();
   }

 } 
    
static boolean f(int x,int y,int x1,int y1)
{
  for(int i=0;i< l;i++)
  {
    if(x==ax1[i]&&y==ay1[i]&&x1==ax2[i]&&y1==ay2[i])
        return false;
    if(x1==ax1[i]&&y1==ay1[i]&&x==ax2[i]&&y==ay2[i])
        return false;
   }
  return true;
 }

static void ff(ri tt)
{
    if(tt.root!=null)ff(tt.root);
    if(tt.root==null)return;
    if(tt.x==tt.root.x&&tt.y==tt.root.y+1)
        System.out.print("E");
    else if(tt.x==tt.root.x&&tt.y==tt.root.y-1)
        System.out.print("W");
    else if(tt.x==tt.root.x+1&&tt.y==tt.root.y)
        System.out.print("S");
    else if(tt.x==tt.root.x-1&&tt.y==tt.root.y)
        System.out.print("N");
  }

 static void bfs()
 {
    Queue< ri> qu=new LinkedList< ri>();
    ri orz=new ri(x1,y1,null);
    qu.add(orz);
    p[x1][y1]=true;
    while(!qu.isEmpty())
    {
      ri temp=qu.poll();
      if(temp.x==x2&&temp.y==y2)
      {
        ff(temp);
        return;
      }
      int x=temp.x;
      int y=temp.y;
      if(!p[x+1][y])
      {
        if(f(x,y,x+1,y))
        {
             ri uu=new ri(x+1,y,temp);
          qu.add(uu);
          p[x+1][y]=true;
        }
        }
       if(!p[temp.x-1][temp.y])
       {
        if(f(x,y,x-1,y))
        {
             ri uu=new ri(x-1,y,temp);
          qu.add(uu);
          p[x-1][y]=true;
        }
         }
       if(!p[temp.x][temp.y+1])
       {
        if(f(x,y,x,y+1))
        {
             ri uu=new ri(x,y+1,temp);
          qu.add(uu);
          p[x][y+1]=true;
        }
        }
       if(!p[temp.x][temp.y-1])
       {
        if(f(x,y,x,y-1))
        {
             ri uu=new ri(x,y-1,temp);
          qu.add(uu);
          p[x][y-1]=true;
         }
        }
    }
  }
}
class ri
{
    int x,y;
    ri root;
    public ri(int xx,int yy,ri t)
    {
        x=xx;
        y=yy;
        root =t;
    }
}
							

http://poj.org/problem?id=2933

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

int a[30];
int in[15];
int de[15];
int n, maxs;

bool search( int k, int im, int dm ) {
    int i, t;
    if( k >= n )
        return true;
    for( i=0; i<im; i++ ) {
        if( in[i] <= a[k] ) {
            t = in[i];
            in[i] = a[k];
            if( search( k+1, im, dm ) )
                return true;
            in[i] = t;
        }
    }
    
    for( i=0; i<dm; i++ ) {
        if( de[i] >= a[k] ) {
            t = de[i];
            de[i] = a[k];
            if( search( k+1, im, dm ) )
                return true;
            de[i] = t;
        }
    }
    
    if( im+dm < maxs ) {
        in[im] = a[k];
        if( search( k+1, im+1, dm ) )
            return true;
        de[dm] = a[k];
        if( search( k+1, im, dm+1 ) )
            return true;
    }
    return false;
}

int main( ) {
    int i;

    scanf( "%d", &n );
    for( i=0; i<n; i++ )
        scanf( "%d", a+i );
    for( maxs=1; maxs<=n/2; maxs++ )
        if( search( 0, 0, 0 ) )
            break;
    if( maxs > n/2 )
        maxs = 0;
    printf( "%dn", maxs );
    return 0;
}



							

http://poj.org/problem?id=2930

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

#define count asdljflsdka
#define for_ii(k) for( ii[(k)]=0; ii[(k)]<m; ii[(k)]++ )

char a[20];
char w[110];

char e[6][4] = {
     { 1, 2, 3, 4 },
     { 0, 2, 4, 5 },
     { 0, 1, 3, 5 },
     { 0, 2, 4, 5 },
     { 0, 1, 3, 5 },
     { 1, 2, 3, 4 }
};

char num[20];
char answer[20];
int n, m;
int s[111][6];
bool flag[11][11][11][11][11][11];

void set( int a0, int a1, int a2, int a3, int a4, int a5 ) {
    flag[ a0 ][ a1 ][ a2 ][ a3 ][ a4 ][ a5 ] = true;
    flag[ a0 ][ a2 ][ a3 ][ a4 ][ a1 ][ a5 ] = true;
    flag[ a0 ][ a3 ][ a4 ][ a1 ][ a2 ][ a5 ] = true;
    flag[ a0 ][ a4 ][ a1 ][ a2 ][ a3 ][ a5 ] = true;
}

int clac() {
    int i, j, k, t, best = 0;
    for( i=0; i<6; i++ )
        s[0][i] = ( a[i] == w[0] );
        
    for( i=0; i<n-1; i++ )
    for( j=0; j<6; j++ )
    for( k=0; k<4; k++ )
    if( s[i+1][ e[j][k] ] < ( t = s[i][j] + ( a[ e[j][k] ] == w[i+1] ) ) )
        s[i+1][ e[j][k] ] = t;
    
    for( i=0; i<6; i++ )
        if( s[n-1][i] > best )
            best = s[n-1][i];
            
    return best;
}

int count[10];
int sign[10];

int main( ) {
    int i, ans, ii[6], h, c = 1;
    while( scanf( "%s", w ) == 1 ) {
        n = strlen( w );
        
        memset( count, 0, sizeof count );
        m = 0;
        
        for( i=0; i<n; i++ ) {
            w[i] -= '0';
            if( count[ w[i] ] == 0 )
                num[m++] = w[i];
            count[ w[i] ] ++;
        }
        
        ans = 0;
        if( count[ 0 ] == 0 )
            num[m++] = 0;
        sort( num, num+m );
        memset( flag, 0, sizeof flag );
                
        for_ii(0)for_ii(1)for_ii(2)for_ii(3)for_ii(4)for_ii(5) {
            
            memset( sign, 0, sizeof sign );
            h = 0;
            for( i=0; i<6; i++ ) {
                a[i] = num[ ii[i] ];
                if( !sign[ a[i] ] ) {
                    h += count[ a[i] ];
                    sign[ a[i] ] = true;
                }
            }
            if( h < ans ) continue;
            
            if( flag[ a[0] ][ a[1] ][ a[2] ][ a[3] ][ a[4] ][ a[5 ] ] )
                continue;
     
            set( a[0], a[1], a[2], a[3], a[4], a[5] );
            set( a[5], a[1], a[2], a[3], a[4], a[0] );
            set( a[1], a[0], a[2], a[5], a[4], a[3] );
            set( a[3], a[0], a[2], a[5], a[4], a[1] );
            set( a[2], a[1], a[0], a[3], a[5], a[4] );
            set( a[4], a[1], a[0], a[3], a[5], a[2] );

            set( a[0], a[4], a[3], a[2], a[1], a[5] );
            set( a[5], a[4], a[3], a[2], a[1], a[0] );
            set( a[1], a[4], a[5], a[2], a[0], a[3] );
            set( a[3], a[4], a[5], a[2], a[0], a[1] );
            set( a[2], a[5], a[3], a[0], a[1], a[4] );
            set( a[4], a[5], a[3], a[0], a[1], a[2] );
            
            memset( s, 0, sizeof s );
            
            h = clac();
            
            if( h >= ans ) {
                sort( a, a+6 );
                if( h > ans || ( h==ans && std::lexicographical_compare(a, a+6, answer, answer+6)  ) ) {
                    for( i=0; i<6; i++ )
                        answer[i] = a[i];
                }
                ans = h;
            }
        }
        
        printf( "Dice %d: discrepancy is %d, digits used:", c++, n-ans );
        for( i=0; i<6; i++ )
            printf( " %d", int(answer[i]) );
        printf( "n" );
    }
    return 0;
}



							

http://poj.org/problem?id=2928

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

__int64 x[100010], y[100010];

int main( ) {
    int n, m, c, C, i, j;

    scanf( "%d%d%d%d", &n, &m, &c, &C );
    
    for( i=0; i<n; i++ )
        scanf( "%I64d", x+i );
    for( j=0; j<m; j++ )
        scanf( "%I64d", y+j );
    
    sort( x, x+n );
    sort( y, y+m );

    if( x[n-1] != y[m-1] ) {
        printf( "Impossiblen" );
        return 0;
    }
    
    __int64 min = 0, max = 0;
    x[n] = y[m] = x[n-1]+1;
        
    i=0, j=0;
    while( 1 ) {
        if( x[i] < y[j] ) {
            min += x[i];
            max += x[i]*(m-j);
            i++;
        }
        else if(x[i] == y[j] ) {
            min += x[i];
            max += x[i]*(n-i+m-j-1);
            i++, j++;
        }
        else {
            min += y[j];
            max += y[j]*(n-i);
            j++;
        }
        
        if( i >= n && j >= m )
            break;
        
    }
                
    printf( "Minimum: %I64d, maximum: %I64dn", min*c, max*C );
    return 0;
}



							

http://poj.org/problem?id=2926

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

double x[100000][5];

int main( ) {
    int n, i, k, j;
    int sign[5];
    double best = 0, min, max, t;
    scanf( "%d", &n );
    
    for( i=0; i<n; i++ )
        scanf( "%lf%lf%lf%lf%lf", x[i], x[i]+1, x[i]+2, x[i]+3, x[i]+4 );
        
    for( k=0; k<32; k++ ) {
        for( i=0; i<5; i++ )
            sign[i] = (k&(1<<i)) ? 1 : -1;
        min = 1e100, max = -1e100;
        for( i=0; i<n; i++ ) {
            t = 0;
            for( j=0; j<5; j++ )
                t += sign[j]*x[i][j];
            if( t > max )
                max = t;
            if( t < min )
                min = t;
        }
        if( max-min > best )
            best = max-min;
    }
    printf( "%.2lfn", best );
    return 0;
}



							

http://poj.org/problem?id=2924

import java.util.*;   
import java.math.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
           
        for(int i = 0; i < num; i++)   
        {   
            String[] str = cin.nextLine().split(" ");   
            BigInteger a = new BigInteger(str[0]);   
            BigInteger b = new BigInteger(str[1]);   
            BigInteger result = new BigInteger("0");   
               
            if((a.intValue() >= 0 && b.intValue() >= 0)    
                    || (a.intValue() < 0 && b.intValue() < 0))   
            {   
                int times = (Math.abs(b.intValue()-a.intValue())+1);   
                result = result.add(a);   
                result = result.add(b);   
                result = result.multiply(new BigInteger(times + ""));   
                result = result.divide(new BigInteger("2"));   
            }   
            else  
            {   
                int times1 = (Math.abs(b.intValue()-0)+1);   
                BigInteger r1 = new BigInteger("0");   
                r1 = r1.add(b);   
                r1 = r1.multiply(new BigInteger(times1 + ""));   
                r1 = r1.divide(new BigInteger("2"));   
                   
                int times2 = (Math.abs(a.intValue()-0)+1);   
                BigInteger r2 = new BigInteger("0");   
                r2 = r2.add(a);   
                r2 = r2.multiply(new BigInteger(times2 + ""));   
                r2 = r2.divide(new BigInteger("2"));   
                   
                result = r1.add(r2);   
            }   
       
            System.out.println("Scenario #" + (i+1) + ":");   
            System.out.println(result.toString());   
            if(i != num-1)   
                System.out.println();   
        }   
  
    }   
  
}  

							

http://poj.org/problem?id=2909

//* @author ������<hongxp11@163.com>
import java.util.Scanner;

public class Main {
 public static boolean isPrime(int n) {
    int root = (int) Math.sqrt(n);
    for (int i = 2; i <= root; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n;
    while ((n = in.nextInt()) != 0) {
        if(n == 4)
        {
            System.out.println(1);
            continue;
        }
        int count = 0;
        for (int i = 3; i <= n / 2; i+=2) {
            if (isPrime(i) && isPrime(n - i)) {
                count ++;
            }
        }
        System.out.println(count);
    }
  }
}

							

http://poj.org/problem?id=2907

#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

int s[11][1<<10][10];
typedef pair<int,int> point;
point p;
point b[10];

int dis( point &a, point &b ) {
    return abs(a.first-b.first) + abs(a.second-b.second);
}

int main( ) {
    int i, j, n, m, se, h, k, l;
    scanf( "%d", &se );
    while( se-- ) {
        scanf( "%d%d", &n, &m );
        scanf( "%d%d", &p.first, &p.second );
        scanf( "%d", &h );
        for( i=0; i<h; i++ )
            scanf( "%d%d", &b[i].first, &b[i].second );
            
        memset( s, -1, sizeof s );
        
        for( i=0; i<h; i++ ) {
            s[0][1<<i][i] = dis( p, b[i] );
        }
            
        for( l=0; l<h-1; l++ ) {
            for( i=0; i<h; i++ )
                for( j=0; j<h; j++ )
                    if( i != j ) {
                        for( k=0; k<(1<<h); k++ )
                            if( s[l][k][i] >= 0 && ((1<<j)&k) == 0 &&    
                                ( s[l+1][(1<<j)|k][j] == -1 || s[l+1][(1<<j)|k][j] > s[l][k][i]+dis( b[i], b[j] ) )
                                ) {
                                    s[l+1][(1<<j)|k][j] = s[l][k][i] + dis( b[i], b[j] );
            //                        printf( "%d %d %dn", l+1, j, s[l+1][(1<<j)|k][j] );
                                }
                    }
        }
        
        int ans = 9999999;
        for( i=0; i<h; i++ )
        for( k=0; k<(1<<h); k++ )
            if( s[h-1][k][i] >= 0 && ans > s[h-1][k][i] + dis( b[i], p ) )
                ans = s[h-1][k][i] + dis( b[i], p );
        printf( "The shortest path has length %dn", ans );
    }
    return 0;
}




							

http://poj.org/problem?id=2897

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
 public static void main(String[] args) throws IOException{
  BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
    int[] number=new int[100];
    int[] answer=new int[100];
    int count=Integer.parseInt(stdin.readLine()),carry, lastIndex,n,k;
    StringTokenizer token;
    for(int j=0;j< count;j++){
     token=new StringTokenizer(stdin.readLine());
    boolean shouldPrint=false;
    n=Integer.parseInt(token.nextToken());
    k=Integer.parseInt(token.nextToken());
    if(n>k){
        System.out.println(0);
        continue;
    }
    number[99]=k;
    carry=0;
    lastIndex=99;
    for(int i=99;i>=0;i--){
        answer[i]=(number[i]*n+carry)%10;
        carry=(number[i]*n+carry)/10;
        if(answer[i]==k){
            if(carry!=0){
                if(i!=0)number[i-1]=answer[i];
                
                continue;
            }
            shouldPrint=true;
            lastIndex=i;
            break;
        }
        if(i!=0)number[i-1]=answer[i];
        
    }
    if(number[lastIndex]==0) shouldPrint=false;
    if(!shouldPrint)System.out.println(0);
    else{
        for(int i=lastIndex;i<=99;i++)    System.out.print(number[i]);
        System.out.println();
    }
    }
  }
}

							

http://poj.org/problem?id=2895

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
int num[26] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
int order[26] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};
int main()
{
    int N;
    while (cin>>N)
    {
        for (int z = 0;z < N;z++)
        {
            int p,w;
            cin>>p>>w;
            string msg;
            do
            {
                getline(cin,msg,'n');
            }while(msg.empty());
            int len = msg.size();
            int time = 0;
            for (int i = 0;i < len;i++)
            {
                if(msg[i] != ' ')
                {
                    msg[i] = toupper(msg[i]);
                    time += order[msg[i] - 'A'] * p;

                    if(i != len - 1 && msg[i + 1] != ' ')
                    {
                        if(num[msg[i] - 'A'] == num[msg[i + 1] - 'A'])
                            time += w;
                    }
                }
                else
                    time += p;
            }
            cout<<time<<endl;
        }
    }
    return 0;
}
/*
Best SMS to Type
Time Limit: 1000MS  Memory Limit: 65536K
Total Submissions: 3068  Accepted: 1277

Description

Using SMS today is more than a pleasing hobby. As the number of messages one sends through this service grows, the need to type them fast is better felt. Sometimes, one wonders how fast a message can be typed. Changing some words to their synonyms, might help type the whole message faster, if we were able to quickly calculate the time needed for a specific message.

In the following, we assume that each message is a string of capital English letters and space character. The letters 'A' through 'Z' are assigned to keys '2' to '9', as in the following figure. To type a letter, one should press its key 1, 2, 3, or 4 times, depending on the position of the letter from left to right.

If two consecutive letters of the message are mapped to one key, one should wait for the first letter to be fixed on the screen and then use the key again to type the second one. For instance, to type the letter 'X', one should press '9' twice. If the next letter of the message is not on the same key, one can continue to type the rest of the message. Otherwise, one has to wait for some time, so that the typed 'X' is fixed, and then the next letter ('W', 'X', 'Y', or 'Z') can be typed. To type whitespace, we use the key '1'.As there is no letter mapped to the key '1', the whitespace needs no time to be fixed.
ͼ���Լ����ֻ�
You are given the time needed to press any key, and the time one should wait for a letter to be fixed. Your program should find the minimum time needed to type a nonempty string, given the above rules.
Input

The input file contains multiple test cases. The first line of the input, contains t, the number of test cases that follow. Each of the following t blocks, describes a test case.

The first line of each block contains p and w (1 <= p,w <= 1000), which show the amount of time in milliseconds for pressing a letter and waiting for it to be fixed, respectively. The second line contains a non-empty string of length at most 1000, consisting of spaces or capital English letters. There is no leading or trailing spaces in a line.

Output

For each test case, output one line showing the time needed to type the message in milliseconds.

Sample Input

1
2 10
ABBAS SALAM

Sample Output

72
Source

Tehran 2005
*/

							

http://poj.org/problem?id=2894

//* @author ������<hongxp11@163.com>
import java.util.Scanner;

public class Main{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int i = 0; i< t; i++)
        {
            int n = in.nextInt();
            int[] result = new int[1012];
            int min = 1000;
            int max = 0;
            for(int j = 0; j< n; j++)
            {
                String x = in.next();
                int begin = in.nextInt();
                int end = in.nextInt();
                for(int k = begin; k< end; k++)
                    result[k]++;
                if(max< end)
                    max = end;
                if(min>begin)
                    min = begin;
            }
            for(int j = min; j< max; j++)
            {
                if(result[j]!=0)
                {
                    char res = (char)(result[j]+'A'-1);
                    System.out.print(res);
                }
            }
            System.out.println();
        }
    }
}

							

http://poj.org/problem?id=2893

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
 static final int M = 1000+2;
 static final int N = 1000000+10;
 static int sort[] = new int[N],map[][] = new int[M][M];
 public static void main(String []args) throws Exception{
        
  int i,j,n,m,top,a,b;
  int num[] = new int[N];
        
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
    n = Get_Num(cin);
    m = Get_Num(cin);
    if(n==0 && m==0) break;
    for(i=top=0;i< n;++i)
      for(j=0;j< m;++j){
        map[i][j] = Get_Num(cin);
      }
    if(m%2==1){
        for(i=0;i< n;++i) 
         for(j=0;j< m;++j) if(map[i][j]>0)
            num[top++] = map[i][j];
    }else{
        for(i=0;i< m;++i)
          for(j=0;j< n;++j) if(map[j][i]>0)
            num[top++] = map[j][i];
    }
    a = merge(num,0,top-1);
    if(m%2==1){
        if(a%2==0) System.out.println("YES");
        else System.out.println("NO");
    }
    else{
        for(i=top=0;i< n;++i)
          for(j=0;j< m;++j)
            map[i][j] = ++top;
        map[n-1][m-1] = 0;
        for(i=top=0;i< m;++i) 
         for(j=0;j< n;++j) if(map[j][i]>0)
            num[top++] = map[j][i];
        b = merge(num,0,top-1);
        if(a%2==b%2) System.out.println("YES");
        else System.out.println("NO");
    }
    }
        
  }

  public static int Get_Num(StreamTokenizer cin)throws Exception{
   cin.nextToken();
   return (int)cin.nval;
  }


  public static int merge(int num[],int left,int right){
        
    if(left==right){
        sort[left] = num[left];
        return 0;
    }
    int mid,i,j,ans=0,top=0;
    mid = (left+right)/2;
    ans = merge(num,left,mid)%2;
    ans += merge(num,mid+1,right)%2;
    
    i = left ; j = mid+1;
    while(i<=mid && j<=right){
        if(num[i]>num[j]){
            ans += (mid-i+1)%2;
            sort[top++] = num[j++];
        }
        else{
            sort[top++] = num[i++];
        }
    }
    while(i<=mid)
        sort[top++] = num[i++];
    while(j<=right)
        sort[top++] = num[j++];
    for(i=left;i<=right;++i)
        num[i] = sort[i-left];
    
    return ans;
  }
}

							

http://poj.org/problem?id=2892

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

map< int, int, less<int> > s;

int query( int k ) {
    map<int, int, less<int> >::iterator it;
    it = s.lower_bound( k );
    if( it->second > k )
        return 0;
    return it->first - it->second + 1;
}

void destroy( int k ) {
    map< int, int, less<int> >::iterator it;
    it = s.lower_bound( k );
    
    if( it->second > k )
        return;

    pair<int,int> p = *it;
    s.erase( it );
    
    
    if( p.second <= k-1 )
        s.insert( pair<int,int>( k-1, p.second ) );
    if( p.first >= k+1 )
        s.insert( pair<int,int>( p.first, k+1 ) );
}

void rebuild( int k ) {
    map< int, int, less<int> >::iterator it1, it2;
    it1 = s.lower_bound( k+1 );
    it2 = s.lower_bound( k-1 );
    
    pair<int,int> p;
    
    if( it1->second == k+1 ) {
        p.first = it1->first;
        s.erase( it1 );
    }
    else
        p.first = k;
    
    if( it2->first == k-1 ) {
        p.second = it2->second;
        s.erase( it2 );
    }
    else
        p.second = k;
    s.insert( p );
}


stack<int> sk;

int main( ) {
    int n, m, k;
    char c[2];
    scanf( "%d%d", &n, &m );
    s.insert( pair<int,int>( n, 1 ) );
    while( m-- ) {
        scanf( "%1s", c );
        if( c[0] == 'D' ) {
            scanf( "%d", &k );
            sk.push( k );
            destroy( k );
        }
        else if( c[0] == 'Q' ) {
            scanf( "%d", &k );
            printf( "%dn", query( k ) );
        }
        else {
            rebuild( sk.top() );
            sk.pop();
        }
            
    }
    return 0;
}


							

http://poj.org/problem?id=2890

#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

vector<int> e[1000];
stack<int> sk;

int sign[1000] = { 0 };
int count = 0;
int c;

int n, m;
bool input() {
    int i, a, b;
    if( scanf( "%d%d", &n, &m ) != 2 )
        return false;
        
    for( i=0; i<n; i++ ) {
        e[i].clear( );
    }
    
    for( i=0; i<m; i++ ) {
        scanf( "%d%d", &a, &b );
        e[a].push_back( b );
    }
    return true;
}

void travel( int k ) {
    int i;
    c++;
    sign[k] = count;
    for( i=0; i<e[k].size(); i++ )
        if( sign[ e[k][i] ] != count )
            travel( e[k][i] );
        
} 
        

int doit() {
    int ans = 0, i;
    for( i=0; i<n; i++ ) {
        count++;
        c=0;
        travel( i );
        ans += c;
    }
    return ans;
}

int main( ) {
    while( input() ) {
        printf( "%dn", doit() );
    }
    return 0;
}



							

http://poj.org/problem?id=2887

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int[] s=new int[1000010];
   int size=0;
   while(true)
   {
    int u=in.read();
    if(u=='n')break;
    s[size++]=u;
    }
   int n=Integer.parseInt(in.readLine());
   int[] arr=new int[n];
   char[] crr=new char[n];
   int l=0;
   for(int i=0;i< n;i++)
   {
    int ww=in.read();
    if(ww=='Q')
    {
        in.read();
     int u=0;
     while(true)
     {
      int temp=in.read();
      if(temp>='0'&&temp<='9')
      {
        u*=10;
        u+=temp-'0';
      }
      else break;
     }
     char ans='';
     for(int j=l-1;j>=0;j--)
     {
      if(arr[j]< u) u--;
      else if(arr[j]==u){
        ans=crr[j];
        break;
      }
     }
    if(ans=='')
        ans=(char)s[u-1];
    System.out.println(ans);
     }
    else if(ww=='I')
    {
    in.read();
    crr[l]=(char)in.read();
    in.read();
    int u=0;
    while(true)
    {
       int temp=in.read();
       if(temp>='0'&&temp<='9')
       {
        u*=10;
        u+=temp-'0';
       }
       else break;
     }
    if(u>l+size) u=l+size+1;
    arr[l]=u;
    l++;
     }
     in.readLine();
   }
 }
}
							

http://poj.org/problem?id=2886

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <iterator>
#include <memory.h>

using namespace std;

int tree[500100*4];
int n;

void init( int l, int r, int s ) {
    tree[s] = r-l;
    if( r > l+1 ) {
        int c = (l+r)/2;
        init( l, c, s*2 );
        init( c, r, s*2+1 );
    }
}

void set( int l, int r, int s, int k ) {
    int c = (l+r)/2;
    
    tree[s]--;
    
    if( r == l+1 )
        return;
    else if( k < c )
        set( l, c, s*2, k );
    else
        set( c, r, s*2+1, k );
}

int id;
void find( int l, int r, int s, int count ) {
    int c = (l+r)/2;
    
    if( r == l+1 )
        id = l;
    else if( tree[s*2] >= count )
        find( l, c, s*2, count );
    else
        find( c, r, s*2+1, count-tree[s*2] );
        
}

int p[500100], s[500100];
void clac_point( ) {
    int i, j, h, c;
    
    memset( p, 0, sizeof(p) );
    
    c = 1;
    for( i=2; c<500000; i++ ) {
        if( !p[i] ) {
            c++;
            for( j=i+i; j<=500000; j+=i )
                if( !p[j] )
                    p[j] = i, c++;
        }
    }
    
    s[1] = 1;
    for( i=2; i<=500010; i++ ) {
        if( !p[i] )
            s[i] = 2;
        else {
            h = i;
            for( j=0; h%p[i]==0; h/=p[i], j++ )
                ;
            s[i] = s[ h ]*(j+1);
        }
    }
}

char name[500010][12];
int num[500010];
int k;
bool input() {
    int i;
    if( scanf( "%d%d", &n, &k ) != 2 )
        return false;
    for( i=0; i<n; i++ ) 
        scanf( "%s%d", name[i], num+i );
    return true;
}

int main( ) {
    int i, m, best, k, j;
    
    clac_point( );
    
    while( input() ) {
        best = 1;
        for( i=2; i<=n; i++ )
            if( s[ best ] < s[ i ] )
                best = i;
                
        init( 0, n, 1 );
        k = ::k-1;
        j = ::k;
        m = n;
        for( i=1; i<best; i++ ) {
            set( 0, n, 1, k );
            m--;
            if( num[k] > 0 )
                j = (j-1+num[k]-1)%m+1;
            else {
                j = (j+num[k]-1)%m;
                if( j < 0 ) j+=m;
                j++;
            }
            find( 0, n, 1, j );
            k = id;
//            printf( "%s %dn", name[k], j );
        }
        
        printf( "%s %dn", name[k], s[best] );
    }
    return 0;
}



							

http://poj.org/problem?id=2876

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  StringBuffer[] sb=new StringBuffer[13];
  sb[0]=new StringBuffer("-");
  for(int i=1;i< 13;i++)
  {
    sb[i]=new StringBuffer(sb[i-1]);
    int k=(int)Math.pow(3, i-1);
    for(int w=0;w< k;w++)
        sb[i].append(" ");
    sb[i].append(sb[i-1]);
   }
  while(in.hasNext())
  {
    int a=in.nextInt();
    System.out.println(sb[a]);
  }
 }
}
							

http://poj.org/problem?id=2871

//* @author ������<hongxp11@163.com>
import java.util.Scanner;


public class Main {
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  double first = in.nextDouble();
  while(true)
   {
    double second = in.nextDouble();
    if(second == 999)
    {
        System.out.println("End of Output");
        break;
    }
    System.out.printf("%2.2f",second - first);
    System.out.println();
    first = second;
    }
  }
}

							

http://poj.org/problem?id=2864

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
 public static void main(String[] args) throws IOException {
  BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer tokens;
   int din,stu;
   boolean[] st=new boolean[100];
   boolean band;
   while(true){
    tokens=new StringTokenizer(stdin.readLine());
    stu=Integer.parseInt(tokens.nextToken());
    din=Integer.parseInt(tokens.nextToken());
    if(stu==0&&din==0)break;
    for(int i=0;i< stu;i++)st[i]=false;
    for(int i=0;i< din;i++){
        tokens=new StringTokenizer(stdin.readLine());
        for(int j=0;j< stu;j++){
            if(tokens.nextToken().equals("0")){
                st[j]=true;
            }
        }
    }
    band=false;
    for(int i=0;i< stu;i++) {if(!st[i]) band=true;}            
    if(band)System.out.println("yes");
    else System.out.println("no");        
  }
 }
}
							

http://poj.org/problem?id=2861

#include <stdio.h>
#include <memory.h>

bool e[120][120];
int s[120][120];
int n;
void input( ) {
    int i, j, k;
    char c[2];
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        for( j=0; j<n; j++ ) {
            scanf( "%1s", c );
            e[i][j] = ( i!=j && c[0] == '1' );
        }
    }
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ ) {
        s[i][j] = 0;
        for( k=0; k<n; k++ )
            if( e[i][k] && e[j][k] )
                s[i][j]++;
        s[j][i] = s[i][j];
    }
}
void doit( ) {
    int i, j, k;
    int ans = 0, sum, t, tt;    
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ ) {
        sum = 0;
        for( k=0; k<n; k++ ) {
            if( e[i][k] && k!=j ) {
                t = s[k][j];
                if( e[i][j] ) t--;
                ans += sum * t % (9901*3);
                sum += t;
            }
        }        
        for( k=0; k<n; k++ )
            if( e[k][j] && k!=i ) {
                t = s[k][i];
                if( e[i][j] ) t--;
                ans -= t*(t-1)/2;
            }
        for( k=0; k<n; k++ )
            if( e[i][k] && e[j][k] ) {
                t = s[k][i];
                tt = s[k][j];
                if( e[i][j] )
                    t--, tt--;
                ans -= t*tt;
            }
        ans %= (9901*3);
    }
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ )
        if( e[i][j] ) {
            ans += s[i][j]*(s[i][j]-1)/2;
        }
    ans %=  (9901*3);
    if( ans < 0 ) ans += (9901*3);
    printf( "%dn", ans/3 );
}
int main( ){
    input( );
    doit( );
    return 0;
}

    
							

http://poj.org/problem?id=2860

//* @author ������<hongxp11@163.com>
import java.util.Scanner;


public class Main {
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[] initial= new int[k];
        int[] finish = new int[k];
        for(int i = 0; i< k; i++)
        {
            initial[i] = in.nextInt();
        }
        for(int i = 0; i< k; i++)
        {
            finish[i] = in.nextInt();
        }
        int sum = 0;
        for(int i = 0; i< k; i++)
        {
            int l = finish[i] - initial[i];
            if(l>0)
                sum += l;
        }
        System.out.println(sum);
    }
}

							

http://poj.org/problem?id=2859

#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

typedef pair<int,int> point;
int n, a, b;
point p[500100];

void input( ) {
    int i;
    scanf( "%d", &n );
    scanf( "%d%d", &a, &b );
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].first, &p[i].second );
}



void doit( ) {
    int i, j, k, l, ans = 0;

    sort( p, p+n );

    p[n].first = p[n+1].first = p[n+2].first = 2000000010;
    p[n].second = -1000000010;
    p[n+1].second = 0;
    p[n+2].second =1000000010;

    for( i=0, j=0, k=0, l=0; l<n; i++ ) {
        if( p[i].first < p[j].first )
            i = j;
        while( p[j].first == p[i].first && p[j].second < p[i].second+b )
            j++;
        if( k <= j ) k = j+1;
        while( p[k].first < p[i].first+a 
            || ( p[k].first == p[i].first+a && p[k].second < p[i].second ) )
            k++;
        if( l <= k ) l = k+1;
        while( p[l].first == p[k].first && p[l].second < p[k].second+b )
            l++;
        if( p[i].first == p[j].first && p[j].second == p[i].second+b &&
            p[k].first == p[l].first && p[l].second == p[k].second+b &&
            p[i].first + a == p[k].first && p[i].second == p[k].second )
            ans++;
    }
    printf( "%dn", ans );
}

int main( ) {
    input( );
    doit( );
    return 0;
}


							

http://poj.org/problem?id=2858

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

using namespace std;

char w[100100][11];
char *p[11][100100];
int pn[11];

bool cmpw( char *a, char *b ) {
    return strcmp( a, b ) < 0;
}

struct tile{
    char c[2];
    int v;
}tiles[10];

bool cmp( tile a, tile b ) {
    return a.v < b.v;
}

char word[1000];
int n, ph;

void input( ) {
    int i, l;
    scanf( "%d", &n );
    
    for( i=0; i<=10; i++ )
        pn[i] = 0;

    for( i=0; i<n; i++ ) {
        scanf( "%s", word );
        if( (l=strlen(word)) > 10 ) {
            i--, n--;
            continue;
        }
        sort( word, word+l );
        strcpy( w[i], word );
        p[l][pn[l]++] = w[i];
    }

    for( i=0; i<=10; i++ )
        sort( p[i], p[i]+pn[i], cmpw );
}

void inputahand( ) {
    int i;
    scanf( "%d", &ph );
    
    for( i=0; i<ph; i++ ) {
        scanf( "%1s %d", tiles[i].c, &tiles[i].v );
    }
    sort( tiles, tiles+ph, cmp );
}

int doahand( ) {
    int i, j, k, v = 0, t, m, best = 0, h, g = ph-1;

    for( i=0; i<ph; i++ )
        best += tiles[i].v;
    
    h = (1<<(ph-1))-1;

    for( i=(1<<ph)-1; i>=1; i-- ) {
        if( v >= best )
            break;
        if( i == h ) {
            best -= tiles[g].v;
            g--;
            h = (1<<(g-1))-1;
        }
        
        k = i, t = 0, m = 0;
        for( j=0; k; k>>=1, j++ )
            if( k&1 ) {
                t += tiles[j].v;
                word[m++] = tiles[j].c[0];
            }
        if( t > v ) {
            word[m] = '';
            sort( word, word+m );
            if( std::binary_search( p[m], p[m]+pn[m], &word[0], cmpw ) )
                v = t;
        }
    }

    return v;
}

int main( ) {
    input( );
    int m;
    scanf( "%d", &m );
    while( m-- ) {
        inputahand( );
        printf( "%dn", doahand( ) );
    }
    return 0;
}




							

http://poj.org/problem?id=2857


import java.util.*;

/**
 *
 * @author leo
 */
public class Main {
  public static int judge(double H,double V,double h,double v,double x,double y,int state){

   if((x>H*h&&y< V*v)||(x< H*h&&y>V*v)){
          return state;
   }else{
      state++;
      if(x< h*H&&y< v*V){
            return judge(H*h,v*V,h,v,x,y,state);
      }else{
         return judge(H*(1.0-h),V*(1.0-v),h,v,x-H*h,y-V*v,state);
      }
   }

 }
 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);
  double H,V,h,v,x,y;
  int n,state,count=1;
  H=sc.nextDouble();
  V=sc.nextDouble();
  h=sc.nextDouble();
  v=sc.nextDouble();
  while(H>1.0e-6){
    n=sc.nextInt();
    System.out.println("Case "+count+":");
    for(int i=1;i<=n;i++){
       x=sc.nextDouble();
       y=sc.nextDouble();
       state=judge(H,V,h,v,x,y,0);

       if(state%2==0)
          System.out.println("black");
       else
          System.out.println("white");


    }
    count++;

    H=sc.nextDouble();
    V=sc.nextDouble();
    h=sc.nextDouble();
    v=sc.nextDouble();
   }
 }
}
							

http://poj.org/problem?id=2853

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
    Scanner in=new Scanner(System.in);
    int u=in.nextInt();
    while((u--)!=0)
    {
        int y=in.nextInt();
     int a=in.nextInt();
     int count=0;
     int t=1;
     for(int i=2;i< (Math.sqrt(2*a)+1);i++)
     {
       t+=i;
       if((a-t)%i==0&&a>=t) count++;
      }
     System.out.println(y+" "+count);
       }    
  }
}
							

http://poj.org/problem?id=2849

//2849
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int Array[32768];
string Program;
string input;
int index;
int inputP;
int PromP;
int cc;
int Programsize;
inline void IncP()
{
    index = (index + 1) % 32768;
}

inline void DecP()
{
    index--;
    if (index == -1)
        index = 32768 - 1;
}

inline void Inc()
{
    Array[index] = (Array[index] + 1) % 256;
}

inline void Dec()
{
    Array[index]--;
    if (Array[index] == -1)
        Array[index] = 255;
}

inline void out()
{
    cout<<(char)Array[index];
}

inline void read()
{
    Array[index] = input[inputP++];
}

inline bool right()
{
    if(Array[index] != 0)
        return true;
    int head = 1;
    PromP++;
    while(1)
    {
        if(Program[PromP] == '[')
            head++;
        if(Program[PromP] == ']')
            head--;
        if(head == 0)
            break;
        PromP++;
        if(PromP >= Programsize)
            return false;
    }
    return true;
}

inline bool left()
{
    if(Array[index] == 0)
        return true;
    int head = 1;
    PromP--;
    while(1)
    {
        if(Program[PromP] == ']')
            head++;
        if(Program[PromP] == '[')
            head--;
        if(head == 0)
            break;
        PromP--;
        if(PromP < 0)
            return false;
    }
    return true;
}

void process()
{
    cout<<"PROGRAM #"<<cc+1<<":"<<endl;
    int len = Program.size();
    int count = 0;
    for(PromP = 0;PromP < len;PromP++)
    {
        if(Program[PromP] == '[')
            count++;
        if(Program[PromP] == ']')
            count--;
    }
    if(count != 0)
    {
        cout<<"COMPILE ERROR"<<endl;
        return;
    }
    for(PromP = 0;PromP < len;)
    {
        if(Program[PromP] == 'S')
        {
            string s;
            s.size();
        }
        bool bComE = true;
        switch(Program[PromP])
        {
        case '>':
            IncP();
            break;
        case '<':
            DecP();
            break;
        case '+':
            Inc();
            break;
        case '-':
            Dec();
            break;
        case '.':
            out();
            break;
        case '[':
            bComE = right();
            break;
        case ']':
            bComE = left();
            break;
        }
        PromP++;
        if(!bComE)
        {
            cout<<"COMPILE ERROR";
            break;
        }
    }
    cout<<endl;
}

int main()
{
    int N;
    while (cin>>N)
    {
        for (cc = 0;cc < N;cc++)
        {
            Program.clear();
            input.clear();
            memset(Array,0,sizeof(Array));
            index = 0;
            inputP = 0;
            PromP = 0;
            string Case,s;
            while (1)
            {
                int mid = 0;
                string::size_type index = 0;
                int count = 0;
                getline(cin,s,'n');
                index = s.find("%");
                if(index != string::npos)
                {
                    Case += s.substr(0,index);
                    continue;
                }
                index = s.find("end");
                if(index != string::npos)
                    break;
                Case += s;
            }
            Programsize = Case.size();
            Program = Case;
            process();
        }
    }
    return 0;
}

/*
brainf*ck
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 1039  Accepted: 439 

Description

brainf*ck is the ungodly creation of Urban Mller, whose goal was apparently to create a Turing-complete language for which he could write the smallest compiler ever. http://en.wikipedia.org defines it as ��a computer programming language designed to challenge and amuse programmers, and is not suitable for practical use. Its name has been variously euphemized, as in brainf*ck.�� 

A brainf*ck program has an implicit byte pointer, called ��the pointer��, which is free to move around within an array of 32768 bytes, initially all set to zero. The pointer itself is initialized to point to the beginning of this array. 

The brainf*ck programming language consists of seven commands, each of which is represented as a single character. Note: ��Industry standard�� brainf*ck actually has eight commands, but for the purposes of this problem one command was intentionally omitted. 




COMMAND  OPERATION  
>  Increment the pointer.  
 Incrementing a pointer value of 32767  
 results in a pointer value of 0.  
<  Decrement the pointer.  
 Decrementing a pointer value of 0  
 results in a pointer value of 32767.  
+  Increment the byte at the pointer.  
 Incrementing the byte value 255 results  
 in the byte value 0.  
-  Decrement the byte at the pointer.  
 Decrementing the byte value 0 results  
 in the byte value 255.  
.  Output the character whose ASCII  
 value is the byte at the pointer  
[  Jump forward past the matching ] if the  
 byte at the pointer is zero.  
]  Jump backward to the matching [  
 unless the byte at the pointer is zero.  


For this problem, you will write a program that reads in, parses and executes a brainf*ck program.

Input

The first line of input contains an integer N, (1 �� N �� 100) , which is the number of brainf*ck programs that follow. Each program consists of one or more lines of brainf*ck commands ending with a line that consists of the word `end'. Your program should ignore any illegal characters (I.E. any character not in the set: <>+-.[]), If a percent sign (%) is encountered during parsing, the remainder of the line should be discarded. This constitutes a comment. The maximum number of commands in a brainf*ck program is 128000.

Output

For each brainf*ck program, your program should output the text ��PROGRAM #n:�� on a single line (where n is the program number: 1 �� n �� N), followed by the output generated by the brainf*ck program, followed by a single newline character. The only possible parsing error that can occur is if there is an unmatched [ or ] in the brainf*ck program. If your program encounters such an error, it should simply print ��COMPILE ERROR�� instead of executing the program. All brainf*ck programs will use no more than the specified 32768 bytes of memory.

Sample Input

3
++++++++[>+++++++++ % hello-world.
<-]>.<+++++[>++++++<-]>-.+++++++..
+++.<++++++++[>>++++<<-]>>.<<++++[>
------<-]>.<++++[>++++++<-]>.+++.
------.--------.>+.
end
+++[>+++++++[.
end
%% Print alphabet, A-Z.
+ + + + + +++++++++++++++++++++>
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
+< [ >.+<- ]
end
Sample Output

PROGRAM #1:
Hello World!
PROGRAM #2:
COMPILE ERROR
PROGRAM #3:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
*/
							

http://poj.org/problem?id=2847

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    String num;
    boolean ok;
    
    void DFS(int dep, String b) {
        if(b.length() == num.length())
            return;
        int i, j;
        for(i = 0; i <= 9; ++i) {
            BigInteger now = new BigInteger(""+i+b);
            String nows = now.multiply(now).multiply(now).toString();
            if(nows.length() >= num.length() && nows.substring(nows.length()-num.length()).equals(num)) {
                ok = true;
                System.out.println(now);
                return;
            }
            if(nows.length() > dep) {
                int all = Math.min(dep, num.length()-1);
                for(j = 0; j <= all; ++j) {
                    if(nows.charAt(nows.length()-1-j) != num.charAt(num.length()-1-j))
                        break;
                }
                if(j > all) {
                    DFS(dep+1, ""+i+b);
                    if(ok) return;
                }
            }
        }
    }

    void run() {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            num = cin.next();
            ok = false;
            DFS(0, "");
            if(!ok) while(true);
        }
    }

    public static void main(String[] args) {
        new Main().run();

    }

}

							

http://poj.org/problem?id=2845

 import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         int pnum = Integer.valueOf(cin.nextLine()).intValue();  
           
         for(int i = 1; i <= pnum; i++)  
         {  
             String[] str = cin.nextLine().split(" ");  
             String a = removePreZero(str[0]);  
             String b = removePreZero(str[1]);  
               
             a = reverse(a);  
             b = reverse(b);  
               
             String result = addBinary(a, b);  
             result = reverse(result);  
             result = removePreZero(result);  
             System.out.println(i + " " + result);  
         }  
   
     }  
       
     private static String addBinary(String a, String b)  
     {  
         StringBuffer sb = new StringBuffer();  
         int loa = a.length();  
         int lob = b.length();  
           
         String newa = a;  
         String newb = b;  
         if(loa > lob)  
         {  
             newa += "0";  
             for(int i = 0; i <= (loa-lob);i++)  
                 newb += "0";  
         }else if(loa == lob)  
         {  
             newa += "0";  
             newb += "0";  
         }else  
         {  
             newb += "0";  
             for(int i = 0; i <= (lob-loa);i++)  
                 newa += "0";  
         }  
           
         int carry = 0;  
       
         for(int i = 0; i < newa.length(); i++)  
         {  
             char c1 = newa.charAt(i);  
             char c2 = newb.charAt(i);  
             int tmp = c1 + c2 - 96 + carry;  
             if(tmp == 0)  
             {  
                 sb.append('0');  
                 carry = 0;  
             }else if(tmp == 1)  
             {  
                 sb.append('1');  
                 carry = 0;  
             }else if(tmp == 2)  
             {  
                 sb.append('0');  
                 carry = 1;  
             }else  
             {  
                 sb.append('1');  
                 carry = 1;  
             }  
         }  
           
         return sb.toString();  
     }  
       
     private static String reverse(String str)  
     {  
         StringBuffer sb = new StringBuffer();  
           
         for(int i = str.length() - 1; i >= 0; i--)  
         {  
             sb.append(str.charAt(i));  
         }  
           
         return sb.toString();  
           
     }  
       
     private static String removePreZero(String str)  
     {  
         int index = 0;  
           
         while(index < str.length())  
         {  
             if(str.charAt(index) == '0')  
                 index++;  
             else  
                 break;  
         }  
           
         if(index == str.length())  
             return "0";  
           
         return str.substring(index);  
     } 
}

							

http://poj.org/problem?id=2842

#include <stdio.h>


int an[10], bn[10];
int sa[10], sb[10];
int p[10], n, m, g, h;
int S[500000], T[500000];

int get_T( int *a ) {
    int index = 0, i;
    for( i=0; i<n; i++ )
        index += a[i]*sa[i];
    return T[ index ];
}

int get_S( int *a ) {
    int index = 0, i;
    for( i=0; i<n; i++ )
        index += (a[i]+p[i])*sb[i];
    return S[ index ];
}

bool check( ) {
    int a[10] = { 0 }, i, k;
    for( i=0; i<m; i++ ) {
        if( get_T( a ) != get_S( a ) )
            return false;
        for( k=n-1; a[k] == an[k]-1 && k; k-- )
            ;
        a[k]++;
        while( k++ < n-1 )
            a[k] = 0;
    }
    return true;
}

void search( ) {
    int i, k;
    for( i=0; i<g; i++ ) {
        if( check( ) )
            return;
        for( k=n-1; p[k] == bn[k]-an[k] && k; k-- )
            ;
        p[k]++;
        while( k++ < n-1 )
            p[k] = 0;
    }
    return;
}

int main( ) {
    int i;
    g = m = h = 1;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf( "%d", bn+i );
    for( i=0; i<n; i++ ) {
        scanf( "%d", an+i );
        m *= an[i];
        g *= bn[i]-an[i]+1;
        h *= bn[i];
    }

    for( i=0; i<h; i++ )
        scanf( "%d", S+i );
    for( i=0; i<m; i++ )
        scanf( "%d", T+i );

    sb[n-1] = sa[n-1] = 1;

    for( i=n-2; i>=0; i-- ) {
        sa[i]=an[i+1]*sa[i+1];
        sb[i]=bn[i+1]*sb[i+1];
    }

    search( );
    for( i=0; i<n; i++ )
        printf( "%d ", p[i]+1 );
    printf( "n" );
    return 0;
}
							

http://poj.org/problem?id=2840

 import java.util.*;  
   
 public class Main {  
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         int num = Integer.valueOf(cin.nextLine()).intValue();  
         for(int i = 0; i < num; i++)  
         {  
             String[] str = cin.nextLine().split(":");  
             int hour = Integer.valueOf(str[0]).intValue();  
             int minute = Integer.valueOf(str[1]).intValue();  
               
             if(minute != 0)  
                 System.out.println("0");  
             else  
             {  
                 if(hour >= 0 && hour <= 12)  
                     System.out.println(hour+12);  
                 else  
                     System.out.println(hour-12);  
             }  
         }  
     }  
   }
							

http://poj.org/problem?id=2838

#include <stdio.h>


struct edge {
    edge *pri;
    edge *next;
};

edge *e[1010];
edge temp[1010][1010];

void add( int from, int to ) {
    temp[from][to].next = e[from];
    temp[from][to].pri = 0;
    if( e[from] ) e[from]->pri = temp[from]+to;
    e[from] = temp[from]+to;
}

void del( int from, int to ) {
    if( temp[from][to].pri )
        temp[from][to].pri->next = temp[from][to].next;
    if( temp[from][to].next )
        temp[from][to].next->pri = temp[from][to].pri;
    if( e[from] == temp[from]+to )
        e[from] = e[from]->next;
}

bool search( int from, int to ) {
    bool sign[1010] = { false };
    int qh = 0, qe = 0, q[1010], t, k;
    
    q[qh++] = from;
    sign[from] = true;

    while( qe < qh ) {
        t = q[qe++];
        for( edge *p = e[t]; p; p = p->next )
            if( !sign[k=p-temp[t]] ) {
                if( k == to )
                    return true;
                sign[k] = true;
                q[qh++] = k;
            }
    }

    return false;
}

int main( ) {
    int u, v, n, q;
    char c[2];
    scanf( "%d%d", &n, &q );
    while( q-- ) {
        scanf( "%1s%d%d", c, &u, &v );
        if( c[0] == 'I' ) {
            add( u, v );
            add( v, u );
        }
        else if( c[0] == 'D' ) {
            del( u, v );
            del( v, u );
        }
        else
            printf( "%cn", (u==v||search( u, v ))?'Y':'N' );

    }
    return 0;
}
							

http://poj.org/problem?id=2837

#include <stdio.h>


int ans[512][512];

int main( ) {
    int i, j, k, n;
    ans[0][0] = 1;

    scanf( "%d", &n );

    for( i=1; i<(1<<n); i<<=1 ) {
        for( j=i; j<i*2; j++ )
        for( k=i; k<i*2; k++ )
            ans[j][k] = ans[j-i][k-i];
        for( j=0; j<i; j++ )
        for( k=i; k<i*2; k++ )
            ans[j][k] = ans[j][k-i] + i*2;
        for( j=i; j<i*2; j++ )
        for( k=0; k<i; k++ )
            ans[j][k] = ans[j-i][k] + i*2 + (j-i==k?-1:0);
    }
    
    for( i=0; i<(1<<n); i++ )
    for( j=0; j<(1<<n); j++ )
        printf( "%d%c", ans[i][j], j==(1<<n)-1?'n':' ' );

    return 0;
}
							

http://poj.org/problem?id=2834

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> e[10010], dest;
int n, m;
vector< pair<int,int> > jon, cely;

void input( ) {
    int a, b;

    scanf( "%d", &n );
    scanf( "%d", &m );

    while( m-- ) {
        scanf( "%d%d", &a, &b );
        e[a].push_back( b );
        e[b].push_back( a );
    }

    scanf( "%d", &m );
    while( m-- ) {
        scanf( "%d", &a );
        dest.push_back( a );
    }

    scanf( "%d", &m );
    while( m-- ) {
        scanf( "%d%d", &a, &b );
        cely.push_back( make_pair( a, b ) );
    }

}
int dis[10010];

void BFS( ) {
    int i, q[10010], qh = 0, qe = 0, s;

    memset( dis, -1, sizeof dis );

    dis[0] = 0;
    q[qh++] = 0;

    while( qe < qh ) {
        s = q[qe++];
        for( i=0; i<e[s].size(); i++ ) {
            if( dis[e[s][i]] < 0 ) {
                dis[e[s][i]] = dis[s] + 5;
                q[qh++] = e[s][i];
            }
        }
    }
}

void doit( ) {
    int i, j, sum = 0;
    
    BFS( );
    
    jon.push_back( make_pair( 0, 0 ) );
    
    for( i=0; i<dest.size(); i++ ) {
        if( dis[ dest[i] ] > 0 ) {
            jon.push_back( make_pair( dest[i], sum+=dis[dest[i]] ) );
            jon.push_back( make_pair( 0, sum+=dis[dest[i]] ) );
        }
        else {
            jon.push_back( make_pair( dest[i], 1<<31 ) );
            break;
        }
    }

    i=0, j=0;
    for( j=0; j<cely.size(); j++ ) {
        while( i<jon.size() && jon[i].second < cely[j].second )
            i++;
        if( i<jon.size() && jon[i] == cely[j] )
            break;
        if( i == jon.size() && cely[j].first == 0 && cely[j].second >= jon[i-1].second )
            break;
    }

    if( j < cely.size() )
        printf( "%dn", cely[j].second );
    else
        printf( "Being expected..n" );

}

int main( ) {
    input( );
    doit( );
    return 0;
}



							

http://poj.org/problem?id=2833

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  StringBuffer buf=new StringBuffer();
  try {
    while(true)
    {
         char c;
      int[] u=new int[3];
      for(int i=0;i< 3;i++)
      {
        while(true)
        {
        c=(char)in.read();
        if(c==32||c==13)
            break;
        buf.append(c);
         }
         u[i]=Integer.parseInt(buf.toString());
         buf.delete(0,buf.length());
       }
      if(u[0]==0&&u[1]==0&&u[2]==0)break;
      int[] max=new int[u[0]];
      int[] min=new int[u[1]];
      for(int i=0;i< u[1];i++)
        min[i]=9999999;
      double total=0;
      in.read();
      for(int i=0;i< u[2];i++)
      {
       while(true)
       {
        c=(char)in.read();
        if(c==32||c==13)
            break;
        buf.append(c);
        }
       int w=Integer.parseInt(buf.toString());
       buf.delete(0,buf.length());
       if(max[0]< w)max[0]=w;
       if(min[u[1]-1]>w)min[u[1]-1]=w;
       Arrays.sort(max);
       Arrays.sort(min);
       total+=w;
      }
     for(Integer e:max)
        total-=e;
    for(Integer e:min)
        total-=e;
    in.read();
    System.out.printf("%.6fn",total/(u[2]-u[1]-u[0]));
   }
  } catch (IOException e) {}
 }
}

							

http://poj.org/problem?id=2823

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1000100], l[1000100], ans[1000100];
int pt[1000100], st[1000100], n, k, m;
bool cmp( int x, int y ) {
    return a[x] < a[y];
}
void calc( ) {
    int i, j, h, sn;    
    for( i=0; i<n; i++ )
        l[i] = i-1, ans[i] = (1<<31), pt[i] = i;    
    l[0] = -10000000;
    sort( pt, pt+n, cmp );
    for( i=0; i<m; i++ ) {
        h = pt[i];
        st[ 0 ] = h;
        sn = 1;
        for( j=l[h]; j>h-k; j=l[j] )
            st[ sn++ ] = j;
        while( sn-- ) {
            l[ st[sn] ] = j;
            if( ans[ st[sn] ] == (1<<31) )
                ans[ st[sn] ] = a[ h ];
        }
    }
}
int main( ) {
    int i;        
    scanf( "%d%d", &n, &k );
    for( i=0; i<n; i++ )
        scanf( "%d", a+i );    
    m = n-k+1;
    calc( );
    for( i=0; i<m; i++ ) {
        printf( "%d", ans[i] );
        if( i != m-1 )printf( " " );
        else printf( "n" );
    }
    for( i=0; i<n; i++ )
        a[i] = -a[i];
    calc( );
    for( i=0; i<m; i++ ) {
        printf( "%d", -ans[i] );
        if( i != m-1 )printf( " " );
        else printf( "n" );
    }
    return 0;
}



							

http://poj.org/problem?id=2818

/* @author: */
import java.util.Scanner;   
import java.util.Arrays;
public class Main {   
   

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int sum,a[]=new int[4],b[]=new int[4],sum1=0;
    while(true)
    {
       a[0]=sc.nextInt();
       a[1]=sc.nextInt();
       a[2]=sc.nextInt();
       a[3]=sc.nextInt();
       sum=sc.nextInt();
       if(a[0]==0 && a[1]==0 && a[2]==0 &a[3]==0 && sum==0)
         break;
       for(int i=0;i< 4;i++)
          b[i]=a[i];
       for(int i=0;i<=a[0] && i*25<=sum;i++)
       for(int j=0;j<=a[1] && j*10<=sum;j++)
       for(int x=0;x<=a[2] && x*5<=sum;x++)
       for(int y=0;y<=a[3] && y<=sum;y++)
         if(i*25+j*10+x*5+y==sum)
         {
              if(i+j+x+y<=b[0]+b[1]+b[2]+b[3])
              {
                 b[0]=i;
                 b[1]=j;
                 b[2]=x;
                 b[3]=y;   
                 sum1=1;                            
              }                       
         }
      if(sum1==0)
         System.out.printf("Cannot dispense the desired amount.n");
      else
        System.out.printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.n",b[0],b[1],b[2],b[3]);  
       sum1=0;  
    }
   }
}
							

http://poj.org/problem?id=2817

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


int ans[12][1024][10];

int link[10][10];
int len[10];

char w[10][20];

int join_num( int i, int j ) {
    int k, l, ans = 0, h;
    for( k=0; w[i][k]; k++ ) {
        for( l=0, h=0; w[i][k+l] && w[j][l]; l++ )
            h += ( w[i][k+l] == w[j][l] );
        if( ans < h )
            ans = h;
    }
    for( k=0; w[j][k]; k++ ) {
        for( l=0, h=0; w[j][k+l] && w[i][l]; l++ )
            h += ( w[j][k+l] == w[i][l] );
        if( ans < h )
            ans = h;
    }
    return ans;
}


int main( ) {
    int n, i, j, k, m, l, answer, t;
    while( 1 ) {
        scanf( "%d", &n );
        if( n <= 0 )
            break;

        for( i=0; i<n; i++ ) {
            scanf( "%s", w[i] );
            len[i] = strlen( w[i] );
        }

        k = 0;
        for( j=0; j<n; j++ )
        for( i=j+1; i<n; i++ )
            link[i][j] = link[j][i] = join_num( i, j );
        
        memset( ans, -1, sizeof ans );
        
        for( i=0; i<n; i++ )
            ans[1][1<<i][i] = 0;
        m = (1<<n);
        
        answer = 10000;
        
        for( i=1; i<n; i++ )
        for( j=0; j<m; j++ )
        for( k=0; k<n; k++ )
        {
            if( ans[i][j][k] >= 0 ) {
                for( l=0; l<n; l++ )
                    if( !( j & (1<<l) ) ) {
                        t = ( j | (1<<l) );
                        if( ans[i+1][t][l] < 0 || 
                            ans[i+1][t][l] < ans[i][j][k]+link[k][l] ){
                                ans[i+1][t][l] = ans[i][j][k]+link[k][l];
                            }
                    }
            }
        }
        answer = 0;
        for( j=0; j<m; j++ )
        for( k=0; k<n; k++ )
        if( ans[n][j][k] > answer )
            answer = ans[n][j][k];
        printf( "%dn", answer );
    }
    return 0;
}
							

http://poj.org/problem?id=2816

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


char map[200][200];
bool ok[200][200];

int gx, gy, n, m, t, r;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = {  0, 1, 0, -1 };

void flag_ok( ) {
    int i, j;
    for( i=gx, j=gy; map[i][j] != 'X'; i++ )
        ok[i][j] = true;
    for( i=gx, j=gy; map[i][j] != 'X'; i-- )
        ok[i][j] = true;
    
    for( i=gx, j=gy; map[i][j] != 'X'; j++ )
        ok[i][j] = true;
    for( i=gx, j=gy; map[i][j] != 'X'; j-- )
        ok[i][j] = true;
}

bool go( int x, int y ) {
    bool key = true;
    int i;
    
    for( i=0; i<4; i++ )
    if( map[x+dx[i]][y+dy[i]] != 'X' )
        t = i;
    
    r = (t+1)%4;
    
    while( 1 ) 
    {
        if( ok[x][y] )
            return true;
        if( !key && map[x][y] == 'E' )
            return false;

        if( map[x+dx[r]][y+dy[r]] != 'X' ) {
            t = r;
            r = (t+1)%4;
        }

        for( i=0; i<4; i++ )
            if( map[x+dx[t]][y+dy[t]] == 'X' ) {
                t = (t+3)%4;
                r = (t+1)%4;
            }
            else
                break;

        if( i < 4 ) {
            x += dx[t];
            y += dy[t];
        }
        else
            return false;
        key = false;
    }
    return false;        
}

int main( ) {
    int n, m, i, j, a, b;
    char c;
    
    while( 1 ) {
        scanf( "%d%d", &m, &n );
        if( n < 3 && m < 3 )
            break;
        memset( map, 'X', sizeof map );
        memset( ok, 0, sizeof ok );
        
        getchar( );
        getchar( );
        for( i=0; i<n; i++ ) {
            for( j=1; ;j++ ) {
                c=getchar( );
                if( c == 'n' )
                    break;
                if( c == 'G' )
                    gx = i, gy = j;
                map[i][j] = c;
            }
        }
        
        flag_ok( );
        a = b = 0;
        for( i=0; i<n; i++ )
        for( j=1; j<=m; j++ )
        if( map[i][j] == 'E' )
        {
            b++;
            if( go( i, j ) )
                a++;
        }
        
        printf( "The goal would be found from %d out of %d entrances.n", a, b );
    }
    return 0;
}
							

http://poj.org/problem?id=2815

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

double get_angle( double s, double f, double m ) {

    if( s >= 12 )
        s -= 12;
    s = ( s+f/60+m/7200 ) / 12 * 360;
    f = ( f+m/120 )/60 * 360;
    f -= s;
    if( f < 0 )
        f += 360;
    return f;
}
double ans[24][60][120];
int main( ) {
    int i, j, k, a, ii, jj, kk;
    double t;
    for( i=0; i<24; i++ )
    for( j=0; j<60; j++ )
    for( k=0; k<120; k++ ) 
        ans[i][j][k] = get_angle( i, j, k );
//    printf( "%lf %lf %lfn", ans[9][16][21*2], ans[9][16][21*2+1], ans[9][16][22*2] );
    while( 1 ) {
        scanf( "%d %d:%d:%d", &a, &i, &j, &k );
        t = ans[i][j][k*2];        
        if( a < 0 )
            break;            
        if( fabs( t - a ) < 1e-7 ) {
            printf( "%02d:%02d:%02dn", i, j, k );
            continue;
        }
        ii = i, jj = j, kk = k;
        for(  ; ; i=(i+1)%24 )
        for( j%=60; j<60; j++ )
        for( k%=60; k<60; k++ )
        if( k != kk )
        {
            if( ans[i][j][2*k] - t > 0 ) {
                if(    ans[i][j][k*2]-a > 0 && 0 <= a-t )
                        goto over;
            }
            else if( a-t >= 0 || 0 < ans[i][j][2*k]-a )
                goto over;
            t = ans[i][j][2*k];
            ii=i, jj=j, kk=k;
//            printf( "%lfn", t );
        }        
over:
        printf( "%02d:%02d:%02dn", ii, jj, kk );
    }
    return 0;
}
        
            
            
        
    
							

http://poj.org/problem?id=2812

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class POINT{
    double x,y;
}
public class Main {
    static final int N = 100000;
    static POINT point[] = new POINT[N];
    static int n;
    static void start(){
        for(int i=0;i< N;++i) point[i] = new POINT();
    }
    static double Get_Num(StreamTokenizer cin) throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    
public static void main(String[]args) throws Exception{
  int i;
  double V;
  start();
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
        n = (int) Get_Num(cin);
        if(n< 3) break;
        for(i=0;i< n;++i){
            point[i].x = Get_Num(cin);
            point[i].y = Get_Num(cin);
        }
        V = Get_Num(cin);
        System.out.printf("BAR LENGTH: %.2fn",solve(V));
    }
    }
    
 static double corss(POINT a,POINT b,POINT c){
        return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    }
    static double solve(double V){
        double ans=0.0;
        for(int i=2;i< n;++i){
            ans+=corss(point[0],point[i-1],point[i]);
        }
        ans = ans< 0.0?ans/-2.0:ans/2.0;
        return V/ans;
    }
}

							

http://poj.org/problem?id=2810

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <string>
using namespace std;

vector<string> v;
int main( ) {
    double a, b;
    int i, j;
    char w[1000], unit[1000];
    
    while( 1 ) {
        scanf( "%lf %s %lf %1s", &a, unit, &b, w );
        
        gets( w+1 );

        if( a < 0 )
            break;
        
        if( a >= b*0.01 ) {
            for( i=0; w[i]; i++ )
                printf( "%c", w[i] );
            printf( " %.1lf %s %.0lf%%n", a, unit, a/b*100 );
        }
        else
            v.push_back( string(w) );
    }

    printf( "Provides no significant amount of:n" );
    for( i=0; i<v.size( ); i++ ) {
        for( j=0; j<v[i].size(); j++ )
            printf( "%c", v[i][j] );
        printf( "n" );
    }

    return 0;
}


							

http://poj.org/problem?id=2800

//* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    long n,k;
    while(sc.hasNext())
    {
        n = sc.nextLong();
        k = sc.nextLong();
        long sum;
        if(n<=k)
        {
            sum = sumMod(k,n);
        }else
        {
            sum = sumMod(k,k);
        sum += (n-k)*k;
        }

        System.out.println(sum);
    }
    }

    static long sumMod(long k, long n)
    {
        long sum = 0;
    long d = k/n;
    long t1 = n;
    long t2 = k/(d+1);
    while(k/d - t2 > 10)
    {
        long s = k%t1;
        long e = k%(t2+1);
        sum += (s+e)*(t1-t2)/2;
        d++;
        t1 = t2;
        t2 = k/(d+1);
    }

    for(long i=2;i<=t1;i++)
    {
        sum += k%i;
    }

    return sum;
    }
}

							

http://poj.org/problem?id=2799

//* @author: SmilingWang
import java.util.*;
import java.io.*;

public class Main {
 public static void main(String[] args) throws Exception{
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
   int n = Integer.parseInt(br.readLine());
   IPAddress[] ips = new IPAddress[n];
   for(int i = 0; i < n; i++){
    ips[i] = new IPAddress();
    ips[i].read(br.readLine());
   }
  int minlen = -1;
  for(int i = 1; i < n; i++){
    for(int j = 31; j >= 0; j--){
    if(ips[i].bitSet.get(j) != ips[0].bitSet.get(j)){
       if(j > minlen){
        minlen = j;
       }
       break;
    }
    }
  }
  for(int i = minlen; i >= 0; i--){
    ips[0].bitSet.set(i, false);
  }
  System.out.println(ips[0].write());
  IPAddress mask = new IPAddress();
  for(int i = 31; i > minlen; i--){
    mask.bitSet.set(i, true);
   }
  System.out.println(mask.write());
 }
}

class IPAddress{
 BitSet bitSet = new BitSet(32);
 IPAddress(){        
 }

 public void read(String s){
   StringTokenizer st = new StringTokenizer(s, ".");
   LinkedList< Integer> stk = new LinkedList< Integer>();
    
   int k = 31;
   while(st.hasMoreTokens()){
    int t = Integer.parseInt(st.nextToken());
    int c = 0;
    while(t > 0){
    stk.addFirst((t%2));
    t /= 2;
    c++;
     }
     while(c < 8){
    stk.addFirst(0);
    c++;
     }
     while(!stk.isEmpty()){
    int v = stk.removeFirst();
    //q.addLast(v);
    bitSet.set(k, v == 1);
    k--;
      }
     }
   }

   public String write(){
     //System.out.println(bitSet);
     String strOut = "";
     for(int i = 31; i >= 0; i -= 8){
    int sum = 0;
    for(int j = i; j > i-8; j--){
        sum = sum * 2 + (bitSet.get(j) ? 1 : 0);
    }
    strOut += sum;
    if(i > 8){
        strOut += ".";
    }
     }
     return strOut;
   }
}

							

http://poj.org/problem?id=2796

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] b,c;
 static long[] e,d,p;
 public static void main(String[] args)throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    int a=Integer.parseInt(in.readLine());
    p=new long[a+2];
    b=new int[a+1];
    c=new int[a+1];
    d=new long[a+1];
    e=new long[a+1];
    String[] ss=in.readLine().split(" ");
    for(int i=1;i<=a;i++)
        e[i]=d[i]=p[i]=Long.parseLong(ss[i-1]);
    p[0]=p[a+1]=-1;
    long max=-1;
    for(int i=1;i<=a;i++)
    {
         b[i]=1;
      int j=i;
      while(p[j-b[j]]>=p[i])
      {
        j-=b[j];
        b[i]+=b[j];
        d[i]+=d[j];
       }
    }
    for(int i=a;i>0;i--)
    {
      c[i]=1;
      int j=i;
      while(p[j+c[j]]>=p[i])
      {
        j+=c[j];
        c[i]+=c[j];
        e[i]+=e[j];
       }
    }
    int st=-1,ed=-1;
    for(int i=1;i<=a;i++)
    {
       long sum=d[i]+e[i]-p[i];
       sum*=p[i];
       if(sum>max)
       {
        max=sum;
        st=i-b[i]+1;
        ed=i+c[i]-1;
       }
     }
    
    System.out.println(max);
    System.out.println(st+" "+ed);
   }
}

							

http://poj.org/problem?id=2785

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String s=in.readLine();
    int a=Integer.parseInt(s);
    int[] t1=new int[a];
    int[] t2=new int[a];
    int[] t3=new int[a];
    int[] t4=new int[a];
    int[] t5=new int[a*a];
    int[] t6=new int[a*a];
    int abl=0,cdl=0;
    String[] ss;
    for(int i=0;i< a;i++)
    {
         ss=in.readLine().split(" ");
      t1[i]=Integer.parseInt(ss[0]);
      t2[i]=Integer.parseInt(ss[1]);
      t3[i]=Integer.parseInt(ss[2]);
      t4[i]=Integer.parseInt(ss[3]);
    }
    for(int i=0;i< a;i++)
      for(int j=0;j< a;j++)
      {
       t5[abl++]=t1[i]+t2[j];
       t6[cdl++]=t3[i]+t4[j];
      }
    Arrays.sort(t5);
    Arrays.sort(t6);
    int l1=0,l2=cdl-1,ans=0,k,m;
    while(l1< abl&&l2>-1)
    {
      if(t5[l1]+t6[l2]==0){
        k=0;
        m=0;
        for(int i=l1;i< abl;i++)
             if(t5[l1]!=t5[i]) break;
          else k++;
        l1+=k;
        for(int i=l2;i>-1;i--)
          if(t6[l2]!=t6[i]) break;
          else m++;
        l2-=m;
        ans+=k*m;
      }
      else if(t5[l1]+t6[l2]>0) l2--;
      else l1++;
      }
      System.out.println(ans);
  }
}

							

http://poj.org/problem?id=2782

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int b=in.nextInt();
  ArrayList< Integer> t=new ArrayList< Integer>();
  while((a--)!=0)
    t.add(in.nextInt());
  Collections.sort(t);
  int count=0;
  int u=t.size()-1;
  int k=0;
  while(k<=u)
  {
    int q=b;
    q-=t.get(u--);
    if(q>=t.get(k))
        k++;
    count++;
   }
  System.out.println(count);
 }
}
							

http://poj.org/problem?id=2781

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


#define INF 3000000
#define NMAX 1000000
int N;
typedef struct 
{
    int len;
    int next[101];
}DATA;
DATA a[NMAX];
int st,ed;
void input()
{
    int i,j;
    scanf("%d",&N);
    int tmp;
    for(i=0;i<N;i++)
    {
        scanf("%d%d",&tmp,&a[i].len);
        for(j=0;j<a[i].len;j++)
        {
            scanf("%d",&a[i].next[j]);
        }
        a[i].next[j]=-1;
    }
    scanf("%d%d",&st,&ed);
}
int m[NMAX]={0};
int p,q;
int que[NMAX];

void solve()
{
    int i;
    for(i=0;i<N;i++)
        m[i]=INF;
    que[0]=st;
    p=0;
    q=1;
    m[st]=0;
    int cp;
    while(p<q)
    {
        cp=que[p++];
        for(i=0;i<a[cp].len;i++)
        {
            if(m[a[cp].next[i]]>m[cp]+1)
            {
                m[a[cp].next[i]]=m[cp]+1;
                que[q++]=a[cp].next[i];
            }
        }

    }
    printf("%d %d %d",st,ed,m[ed]-1);
    
}
int main()
{

#if _DEBUG    
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

#endif
    input();
    solve();
    
        
#if _DEBUG
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
							

http://poj.org/problem?id=2780

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Point implements Comparable {
    double x,y;
    public int compareTo(Object obj){
        Point temp = (Point) obj;
        if(temp.x!=this.x){
            if(temp.x< this.x) return 1;
            return -1;
        }
        if(temp.y< this.y) return 1;
        return -1;
    }
}
public class Main {
 static final int N = 1000+10;
 static int n;
 static double p[] = new double[N];
 static Point point[] = new Point[N];
 static void start(){
    for(int i=0;i< N;++i)
        point[i] = new Point();
}

public static void main(String[]args) throws Exception{
  int i;
  start();
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
  while(cin.nextToken()!=StreamTokenizer.TT_EOF){
    n = (int) cin.nval;
    for(i=0;i< n;++i){
        cin.nextToken();
        point[i].x = cin.nval;
        cin.nextToken();
        point[i].y = cin.nval;
    }
    if(n<=2) System.out.println(n);
    else System.out.println(solve());
   }
}

public static int solve(){
 int i,j,k,cnt,ans=1;
 Arrays.sort(point,0,n);
 for(i=0;i< n;++i){
    for(k=0,j=i+1;j< n;++j){
        if(point[i].x==point[j].x)
            p[k++] = 10000000000.0;
        else
            p[k++] = (point[j].y-point[i].y)/(point[j].x-point[i].x);
    }
    Arrays.sort(p,0,k);
    cnt = 1;
    //for(j=0;j< k;++j) System.out.print(p[j]+" ");System.out.println();
    for(j=1;j< k;++j){
        if(p[j]==p[j-1])
            ++cnt;
        else{
            ans = cnt>ans?cnt:ans;
            cnt = 1;
        }
    }
    ans = cnt>ans?cnt:ans;
  }
    return ans+1;
 }
}

							

http://poj.org/problem?id=2777

import java.io.*;
import java.util.*;
public class Main
{
  static  tree[] mytree=new tree[300003];
  static boolean[] flag=new boolean[35];
  public static void main(String args[]) throws Exception
  {
     InputStreamReader is=new InputStreamReader(System.in);
     BufferedReader in=new BufferedReader(is);
     String[] ss=in.readLine().split(" ");
     int l=Integer.parseInt(ss[0]);
     int t=Integer.parseInt(ss[1]);
     int o=Integer.parseInt(ss[2]);
     buildtree(1,l,1);
     while(o--!=0)
      {
         ss=in.readLine().split(" ");
         if(ss[0].equals("C"))
         {
           int A=Integer.parseInt(ss[1]);
           int B=Integer.parseInt(ss[2]);
           if(A>B) 
           {
            int temp=A;
            A=B;
            B=temp;
           }
           int p=Integer.parseInt(ss[3]);
           insert(A,B,p,1);
                            
         }
          if(ss[0].equals("P"))
           {
            int A=Integer.parseInt(ss[1]);
            int B=Integer.parseInt(ss[2]);
            if(A>B) 
            {
              int temp=A;
              A=B;
              B=temp;
           }
           Arrays.fill(flag, false);
           query(A,B,1);
           int count=0;
           for(int i=0;i< 35;i++)
            if(flag[i])
              count++;
           System.out.println(count);
                            
       }
     }
   }
            
   public static void buildtree(int a,int b,int i)
    {
         mytree[i]=new tree();
          mytree[i].left=a;
       mytree[i].right=b;
          mytree[i].color=1;
       if(a!=b)
        {
          int mid=(a+b)/2;
          buildtree(a,mid,i*2);
          buildtree(mid+1,b,i*2+1);
        }
   }
            
   public static void insert(int a,int b,int c,int i)
    {
       if(mytree[i].left==a&&mytree[i].right==b)
         mytree[i].color=c;
       else
       {
         if( mytree[i].color !=-1)         
          {
            mytree[i*2].color =mytree[i].color ;
            mytree[i*2+1].color =mytree[i].color ;
            mytree[i].color =-1;        
          }
        int mid=(mytree[i].left+mytree[i].right)/2;
        if(b<=mid)
           insert(a,b,c,2*i);
        else if(a>=mid+1)
           insert(a,b,c,2*i+1);
        else
        {
           insert(a,mid,c,2*i);
           insert(mid+1,b,c,2*i+1);
        }  
     }
       
  }
            
   public static void query(int a,int b,int i)
    {
     if(mytree[i].color==-1)
     {
        if(mytree[2*i]==mytree[2*i+1]&&mytree[2*i].color!=-1)
            mytree[i].color=mytree[2*i+1].color;
     }
     if(mytree[i].color!=-1)
     {
         flag[mytree[i].color]=true;
      }
     else
     {
        int mid=(mytree[i].left+mytree[i].right)/2;
        if(b<=mid&&mytree[2*i]!=null)
           query(a,b,2*i);
        else if(a>=mid+1&&mytree[2*i+1]!=null)
           query(a,b,2*i+1);
        else
        {
           if(mytree[2*i]!=null)
            query(a,mid,2*i);
           if(mytree[2*i+1]!=null)
            query(mid+1,b,2*i+1);
        }
      }
   }
}

class tree
{
    int left;
    int right;
    int color;
}
							

http://poj.org/problem?id=2775

#include "stdio.h"


struct tree{
    int l, r;
    int v;
    int ans;
    int nds;
}t[200];
int n, m;

int new_node( int value ) {
    t[m].l = t[m].r = -1;
    t[m].v = value;
    t[m].nds = 1;
    m++;
    return m-1;
}

int a[200];

void insert( int value, int i ) {
    t[i].nds++;
    if( value <= t[i].v ) {
        if( t[i].l < 0 )
            t[i].l = new_node( value );
        else
            insert( value, t[i].l );
    }
    else {
        if( t[i].r < 0 )
            t[i].r = new_node( value );
        else
            insert( value, t[i].r );
    }
}

void creat() {
    int i;
    m = 0;
    new_node( a[0] );
    for( i=1; i<n; i++ )
        insert( a[i], 0 );
}

int gcd( int a, int b ) {
    int c;
    while( b ) {
        c = b;
        b = a%b;
        a = c;
    }
    return a;
}

int jc( int c, int a, int b ) {
    int i, j, k, t;
    int s[201], ans;

    for( i=c; i>a; i-- )
        s[c-i] = i;

    for( i=2; i<=b; i++ ) {
        k = i;
        for( j=0; k>1; j++ )
            if( ( t = gcd( k, s[j] ) ) > 1 )
                k/=t, s[j]/=t;
    }

    ans = 1;
    for( j=0; j<c-a; j++ )
        ans = ans*s[j]%9901;

    return ans;
}

void clac( int i ) {
    if( i < 0 )
        return;

    clac( t[i].l );
    clac( t[i].r );


    if( t[i].l < 0 ) {
        if( t[i].r < 0 )
            t[i].ans = 1;
        else
            t[i].ans = t[ t[i].r ].ans;
    }
    else if( t[i].r < 0 )
        t[i].ans = t[ t[i].l ].ans;
    else
        t[i].ans = t[ t[i].l ].ans * t[ t[i].r ].ans % 9901
        * jc( t[i].nds-1, t[t[i].l].nds, t[t[i].r].nds ) % 9901;
}

int main( ) {
    int i;
    while( scanf( "%d", &n ) == 1 ) {
        if( n <=0 )break;

        for( i=0; i<n; i++ )
            scanf( "%d", a+i );
        creat();
        clac( 0 );
        printf( "%dn", t[0].ans );
    }
    return 0;
}