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=2282

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

    /**
     * @param args the command line arguments
     */
    public static void recurse(int [] digit,int n,int count){
        if(n<=0) return;
        int oneNo=n%10,tenNo;
        int m=n/10;
        tenNo=m;
        for(int i=0;i<=oneNo;i++){
            digit[i]+=count;
        }
        while(tenNo!=0){
            digit[tenNo%10]+=(oneNo+1)*count;
            tenNo/=10;
        }
        for(int i=0;i< 10;i++){
            digit[i]+=count*m;
        }
        digit[0]-=count;
        recurse(digit,m-1,10*count);
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(true){
            int [] digita=new int[10];
            int [] digitb=new int[10];
            int a=sc.nextInt();
            int b=sc.nextInt();
            if(a==b&&b==0) break;
            if(a>b){
                int t=b;
                b=a;
                a=t;
            }
            recurse(digita,a-1,1);
            recurse(digitb,b,1);
            for(int i=0;i< 10;i++){
                System.out.print(Math.abs(digitb[i]-digita[i])+" ");
            }
            System.out.println();
        }
    }

}

							

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

#include"algorithm"
#include"math.h"
#include<iostream>
using namespace std;

double const pi=3.1415926535898;

struct point
{
    double x,y;
    int r;
    enum {up,down}side;
    double th;
}p[1010],ptemp[1010];

int n;

//degree
//from n-1 to j

double theta(int j)
{
    return atan2(p[j].y-p[n-1].y,p[j].x-p[n-1].x);
}
bool cmp(point a,point b)
{
    return a.th<b.th;
}
////
void sortit(int k)
{
    int i;
    swap(p[k],p[n-1]);
    
    for(i=0;i<n-1;i++)
    {
        p[i].th=theta(i);
        
        if(p[i].th==pi)    
            p[i].th=0,    p[i].side=point::down;
        else if(p[i].th<0)    
            p[i].th=pi+p[i].th,    p[i].side=point::down;
        else p[i].side=point::up;
    }
    
    sort(p,p+n-1,cmp);
}
//
int count(int &up_0,int &up_1,int &down_0,int &down_1,int &on)
{
    on=1;up_0=up_1=down_0=down_1=0;
    
    int i=0,ii;
    for(;i<n-1&&p[i].th==0;i++)
        on++;
    ii=i;

    for(;i<n-1;i++)
        if(p[i].r==1)
        {
            if(p[i].side==point::up)up_1++;
            else down_1++;
        }
        else
        {
            if(p[i].side==point::up)up_0++;
            else down_0++;
        }
    return ii;
}

//k>kk
int rotate(int k,int kk,int &up_0,int &up_1,int &down_0,int &down_1,int &on)
{
    double dgree=p[k].th;
    
    int i;
    for(i=kk;i<k;i++)
    {
        on--;
        if(p[i].r==1)
        {
            if(p[i].side==point::up)down_1++;
            else up_1++;
        }
        else
        {
            if(p[i].side==point::up)down_0++;
            else up_0++;
        }
    }
    
    for(;i<n-1&&fabs(p[i].th-dgree)<1e-8;i++)
    {
        on++;
        if(p[i].r==1)
        {
            if(p[i].side==point::up)up_1--;
            else down_1--;
        }
        else
        {
            if(p[i].side==point::up)up_0--;
            else down_0--;
        }
    }
    return i;
}

void init()
{
    for(int i=0;i<n;i++)
        cin>>ptemp[i].x>>ptemp[i].y>>ptemp[i].r;
    return;
}

int doit()
{
    int best=0,i,k,kk,t;
    int up_0,up_1,down_0,down_1,on;

    for(i=0;i<n;i++)
    {    
        copy(ptemp,ptemp+n,p);
        sortit(i);
        k=count(up_0,up_1,down_0,down_1,on);

        if(best<up_0+down_1+on)best=up_0+down_1+on;
        if(best<up_1+down_0+on)best=up_1+down_0+on;

        kk=0;

        for(;k<n-1;)
        {
            t=rotate(k,kk,up_0,up_1,down_0,down_1,on);
            kk=k;
            k=t;
            if(best<up_1+down_0+on)best=up_1+down_0+on;
            if(best<up_0+down_1+on)best=up_0+down_1+on;
        }
    }

    return best;
}

int main()
{
    while(1)
    {
        cin>>n;
        if(n==0)break;
        init();
        cout<<doit()<<endl;
    }
    return 0;
}


							

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

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

public class Main {

/**
 * @param args
 */
public static void main(String[] args) throws Exception{
  // TODO Auto-generated method stub

  BigInteger  num ,b;//= new BigInteger;
  num=BigInteger.valueOf(1);
        
  Scanner cin = new Scanner(System.in);
        
   int n,i,j,sum,t;
   int way[] = new int[100];
   int flag[][] = new int[100][100];
        
   while(cin.hasNext())
   {
    n = cin.nextInt();
    if(n==0) break;
    for(i=1,sum=0;i<=n;++i)
    {
        way[i]=cin.nextInt();
        sum+=way[i];
    }
        
    num = BigInteger.valueOf(1);
        
    for(i=2;i<=sum;++i)
    {
        b = BigInteger.valueOf(i);
        num = num.multiply(b);
    }
            
    //System.out.println(num);
    for(i=1;i<=n;++i) for(j=1;j<=way[i];++j)
    {
        sum=way[i]-j;
        for(t=i+1;t<=n;++t) if(way[t]>=j) sum++;
                
        sum++;
        b = BigInteger.valueOf(sum);
        //System.out.println(b);
        num = num.divide(b);
    }
            
    System.out.println(num);
            
    }
 }

}

							

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

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


public class Main {
 public static void main(String[] args)
 {
    Scanner in = new Scanner(System.in);
    while(true)
    {
        String input = in.nextLine();
        if(input.equals("R0C0"))
            break;
        int index = 0;
        while(input.charAt(index)!='C')
        {
            index++;
        }
        int num = Integer.parseInt(input.substring(1, index));
        int letter = Integer.parseInt(input.substring(index+1, input.length()));
            
        String result = "";
        result = change(letter) + result;
        while(true)
        {
            if(letter/26.0>1)
            {
                if(letter%26!=0)
                {
                    letter = letter/26;
                    result = change(letter) + result;
                }
                else
                {
                    letter = letter/26;
                    letter--;
                    result = change(letter) + result;
                }
            }
            else
                break;
        }
        System.out.println(result+num);
    }
   }
    
  public static char change(int letter)
  {
    char m;
    if(letter % 26 == 0)
        m = 'Z';
    else
        m = (char) (letter%26 + 'A' -1);
    return m;
  }
}

							

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


import java.util.*;
/**
 *
 * @author Leo
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static int score(double x,double y){
        double r=x*x+y*y;
        if(r<=9.) return 100;
        if(r<=36.) return 80;
        if(r<=81.) return 60;
        if(r<=144.) return 40;
        if(r<=225.) return 20;
        return 0;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        double x,y;
        int sum1,sum2;
        while(true){
            sum1=0;sum2=0;
            x=sc.nextDouble();
            y=sc.nextDouble();
            if(x==-100) break;
            sum1+=score(x,y);
            for(int i=1;i<=2;i++){
                x=sc.nextDouble();
                y=sc.nextDouble();
                sum1+=score(x,y);
            }
            for(int i=1;i<=3;i++){
                x=sc.nextDouble();
                y=sc.nextDouble();
                sum2+=score(x,y);
            }
            if(sum1>sum2)
                System.out.println("SCORE: "+sum1+" to "+sum2+", PLAYER 1 WINS.");
            else if(sum1==sum2)
                System.out.println("SCORE: "+sum1+" to "+sum2+", TIE.");
            else
                System.out.println("SCORE: "+sum1+" to "+sum2+", PLAYER 2 WINS.");

        }
    }

}

							

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

//* @author: 82638882@163.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
 static int[][] w=new int[256][256];
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int cnt=0;
  while(true)
  {
   cnt++;
   String[] ss=in.readLine().split(" ");
   int n=Integer.parseInt(ss[0]);
   int m=Integer.parseInt(ss[1]);
   if(n==0&&m==0) break;
   for(int i=0;i< n;i++)
    for(int j=0;j< n;j++)
    w[i][j]=0;
   for(int i=0;i< n;i++)
    w[i][i]=1000000000;
   String[] name=new String[n+1];
   int len=0;
   for(int i=0;i< m;i++)
   {
    ss=in.readLine().split(" ");
    int a=-1;
    for(int j=0;j< len;j++)
      if(ss[0].equals(name[j]))
       {
        a=j;
        break;
       }
    if(a==-1){
       a=len;
       name[len++]=ss[0];
    }
    int b=-1;
    for(int j=0;j< len;j++)
      if(ss[1].equals(name[j]))
      {
        b=j;
        break;
       }
    if(b==-1){
      b=len;
      name[len++]=ss[1];
    }
    w[a][b]=w[b][a]=Integer.parseInt(ss[2]);
     }
     ss=in.readLine().split(" ");
     int str=-1,dis=-1;
     for(int i=0;i< n;i++)
      {
    if(ss[0].equals(name[i]))
        str=i;
    if(ss[1].equals(name[i]))
        dis=i;
      }
     for(int k=0;k< n;k++)
    for(int i=0;i< n;i++)
     for(int j=0;j< n;j++)
       w[i][j]=Math.max(w[i][j], Math.min(w[i][k], w[k][j]));
     System.out.println("Scenario #"+cnt);
     System.out.println(w[str][dis]+" tons");
     System.out.println();
    }
  }
}

							

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

import java.util.*;
 public class Main{
   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
      int n=1;
      while(true){
        n=sc.nextInt();
        if(n==0) break;
       test(n);
      }
      
   }
   /* 
   * 8 = 3 + 5 
   * 20 = 3 + 17
   * 42 = 5 + 37 
   */  
  public static void test(int x){ 
      if(6<=x && x < 1000000){ 
          if(x%2!=0){  
            System.out.println("������ݲ���ż��");
           }else{
              boolean b=false;  
            for(int i=3;i+i<=x;i++){  
                if(isPrime(i) && isPrime(x-i)){ 
                    System.out.println(x+" = "+i+" + "+(x-i));  
                   b = true; 
                    break; 
                 }  
            }  
            if(!b)   
               System.out.println("Goldbach's conjecture is wrong."); 
          } 
      }else{ 
          System.out.println("������ݷ�Χ����");
       }  
  }   

   /* 
    * �ж�ij�����Ƿ�Ϊ��������Ƿ���true
    */

    public static boolean isPrime(int x){ 
      for(int i=2;i*i<=x;i++){ 
          if(x%i==0)
              return false;  
     }  
     return true; 
   }
}

							

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

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

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
 // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
    while (true) {
        int n = in.nextInt();
        if (n == 0)
            break;
        Byte[][] matrix = new Byte[n][n];
        int row = 0;
        int sign1 = 0;
        int column = 0;
        int sign2 = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
              matrix[i][j] = in.nextByte();
              sum += matrix[i][j];
            }
            if (sum % 2 == 1) {
                sign1 = i + 1;
                row++;
            }
        }
        if (row > 1) {
           System.out.println("Corrupt");
           continue;
        }
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                           sum += matrix[j][i];
            }
            if (sum % 2 == 1) {
                sign2 = i + 1;
                column++;
            }
        }
        if (column > 1) {
            System.out.println("Corrupt");
            continue;
        }
        if (column == 1 && row == 1)
         System.out.println("Change bit (" + sign1 + "," + sign2 + ")");
        if ((column | row) == 0)
            System.out.println("OK");
        }
    }

}

							

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static String[] names = new String[0];
    static int[] amount = new int[0];
    private static int[][] relation = new int[0][0];

    private static int getIndex(String s) {
        for (int i = 1; i < names.length; i++) {

            if (names[i].equals(s)) {
                return i;
            }
        }

        return -1;
    }


    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        int kase = 0;

        while (true) {
            String line = stdin.readLine();

            String[] temp = line.split("[ ]+");

            int n = Integer.parseInt(temp[0]);
            int k = Integer.parseInt(temp[1]);

            if (n == 0 && k == 0) {
                break;
            }

            kase++;

            names = new String[n + 1];

            for (int i = 1; i <= n; i++) {
                names[i] = stdin.readLine().trim();
            }

            relation = new int[n + 1][n + 1];
            amount = new int[n + 1];

            for (int i = 0; i <= n; i++) {
                amount[i] = 0;

                for (int j = 0; j <= n; j++) {
                    relation[i][j] = 0;
                }
            }

            for (int i = 1; i <= k; i++) {
                line = stdin.readLine();

                temp = line.split("[ ]+");

                int indexA = getIndex(temp[0]);
                int indexB = getIndex(temp[1]);

                if (indexA == -1 || indexB == -1) {
                  //  System.out.println("name==" + temp[0] + "  " + temp[1]);
                    continue;
                }

                relation[indexA][indexB] = 1;

                int m = Integer.parseInt(temp[2]);
                amount[indexA] -= m;

                amount[indexB] += m;
            }


            // firt using foyld wall-shall.
            for (int i = 1; i<= n; i++) {
                for (int j = 1; j<= n; j++) {
                    for (int f = 1; f <= n; f++) {
                        if (relation[i][f] == 1  && relation[f][j] == 1) {
                            relation[i][j] = 1;
                        }
                    }
                }
            }

     System.out.println("Case #" + kase);
     for (int i = 1; i <= n; i++) {
       if (amount[i] < 0) {
          while (amount[i] < 0) {
          for (int j = 1; j<= n; j++) {
            if (amount[j] <= 0) {
               continue;
             }
            if (relation[i][j] == 1) {
              if (amount[j] >= Math.abs(amount[i])) {
                 System.out.println(names[j] + " " + names[i] + " " + Math.abs(amount[i]));
                 amount[j] -= Math.abs(amount[i]);
                 amount[i] = 0;
                 if (amount[i] == 0) {
                    break;
                  }
             } else {
                 System.out.println(names[j] + " " + names[i] + " " + amount[j]);
                 amount[i] += amount[j];
                 amount[j] = 0;
                 break;
             }
           }
          }
      }
     }
    }

    System.out.println();
  }

 }

}


							

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.RoundingMode;

public class Main {

    /**
     * Parse the value.
     * @param s the given string such as  4.5A, 2.5MW
     * @return
     */
    private static double parseValue(String s) {
        int i = 0;
        while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9' || s.charAt(i) == '.') {
            i++;
        }

        if (i == s.length()) {
            return Double.parseDouble(s);
        }

        // in case that the end of string is not reached.

         double value = Double.parseDouble(s.substring(0, i));


        if (s.charAt(i) == 'm') {
            value = value / 1000.0;
        } else if (s.charAt(i) == 'M') {
            value = value * 1000000.0;
        } else if (s.charAt(i) == 'k') {
            value = value * 1000.0;
        }


        return value;

    }

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception  {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        String line = stdin.readLine();

        int n = Integer.parseInt(line);


        for (int i = 1; i<= n; i++){
            line = stdin.readLine();


            String[] t = line.split("[ ,]+");


            boolean u_value = false;
            boolean i_value = false;
            boolean p_value = false;

            double u = 0;
            double I = 0;
            double p = 0;

            for (int j = 0; j < t.length; j++) {

                if (t[j].indexOf("=") > 0) {

                    // split the kind of string like:U=200V
                    String[] temp = t[j].split("[=]");

                    if (temp[0].charAt(0) == 'U') {
                        u_value = true;

                        u = parseValue(temp[1]);
                    } else if (temp[0].charAt(0) == 'P') {
                        p_value = true;
                        p = parseValue(temp[1]);
                    } else if (temp[0].charAt(0) == 'I') {
                        i_value = true;
                        I = parseValue(temp[1]);
                    }

                }

            }

            System.out.println("Problem #" + i);

            if (u_value && i_value) {
                System.out.print("P=");
                System.out.print(new BigDecimal(I * u).setScale(2, RoundingMode.HALF_UP));
                System.out.println("W");
            } else if (p_value && u_value) {
                System.out.print("I=");
                System.out.print(new BigDecimal(p /u).setScale(2, RoundingMode.HALF_UP));
                System.out.println("A");
            } else if (p_value && i_value) {
                System.out.print("U=");
                System.out.print(new BigDecimal(p /I).setScale(2, RoundingMode.HALF_UP));
                System.out.println("V");
            }

            System.out.println();
        }
    }
}


							

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

import java.util.Scanner;

public class Main {

    private static char[] seq = new char[100];
    private static int s = -1;

    public static void getPostOrder(String pre, String in) {
        if (pre.length() == 1 && in.length() == 1) {
            seq[++s] = in.charAt(0);
            // seq[++s] = pre.charAt(0);
            return;
        }

        char root = pre.charAt(0);
        seq[++s] = root;

        int rootIndex = in.indexOf(root);
        if (rootIndex == 0) {
            getPostOrder(pre.substring(1), in.substring(1));
            return;
        } else if (rootIndex == in.length() - 1) {
            getPostOrder(pre.substring(1), in.substring(0, in.length() - 1));
            return;
        } else {
            String in_Left = in.substring(0, rootIndex);
            String in_Right = in.substring(rootIndex + 1);

            int indexLeft = -1;
            for (int i = 0; i < in_Left.length(); i++) {
                int temp = pre.indexOf(in_Left.charAt(i));
                if (temp > indexLeft)
                    indexLeft = temp;
            }

            if (in_Right.length() == 1) {
                seq[++s] = in_Right.charAt(0);
                // return;
            } else {
                String pre_Right = null;
                pre_Right = pre.substring(indexLeft + 1);
                getPostOrder(pre_Right, in_Right);
            }

            if (in_Left.length() == 1) {
                seq[++s] = in_Left.charAt(0);
                return;
            } else {
                String pre_Left = null;
                pre_Left = pre.substring(1, indexLeft + 1);
                getPostOrder(pre_Left, in_Left);
            }

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            s = -1;
            
            String pre = sc.next();
            String in = sc.next();
            
            seq = new char[pre.length() + 1];
            getPostOrder(pre.trim(), in.trim());

            while (s >= 0) {
                System.out.print(seq[s--]);
            }
            System.out.println();
        }
    }

}
							

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

//* @author
//import java.io.File;
//import java.io.FileNotFoundException;
//import java.util.Arrays;
import java.util.Scanner;

public class Main{
Scanner cin = new Scanner(System.in);

int n;
int cases;
int stone[][];
double map[][];

public void inPut() {
   //File f = new File("D:\ACM\POJ����\2253\test.txt");
  // cin = new Scanner(f);

   while (true) {
    cases ++;
    n = cin.nextInt();
    if (n == 0) {
     return;
    }
    stone = new int[n][2];
    map = new double[n][n];
    for (int i = 0; i < n; i++) {
     stone[i][0] = cin.nextInt();
     stone[i][1] = cin.nextInt();
    }

    for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
      map[i][j] = Math.sqrt((stone[i][0] - stone[j][0])
        * (stone[i][0] - stone[j][0])
        + (stone[i][1] - stone[j][1])
        * (stone[i][1] - stone[j][1]));
     }
    }

    solve();
   }
}

private void solve() {
//   System.out.println(Arrays.deepToString(map));
   System.out.println("Scenario #" + cases);
  
   System.out.printf("Frog Distance = %.3fnn", floyd());
}

private double floyd() {
   for (int i = 0; i < n; i++) {
    for (int k = 0; k < n; k++) {
     for (int j = 0; j < n; j++) {

//���if�������Ķ����иı�,���������Ҫ��}��ʯͷ֮�������·���������(necessary jump range)��С��

//������ܰѴ�ʯͷA��ʯͷB������·�����������С��ֵ�浽map[A][B]��,���map[0][1]�д�ľ�����Ҫ��ֵ
      if (map[k][i] != 0
        && map[i][j] != 0
        && map[k][j] > (map[k][i] > map[i][j] ? map[k][i]
          : map[i][j])) {
       map[k][j] = (map[k][i] > map[i][j] ? map[k][i] : map[i][j]);
      }
     }
    }
   }
   return map[0][1];
}

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

}

							

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

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

class  point {
    int x;
    int y;
    int z;
    int step;

  public point(int x,int y,int z,int step){
    this.x=x;
    this.y=y;
    this.z=z;
    this.step=step;
  }


 public int  getX(){
   return this.x;
 }
 
 public int getY(){
   return this.y;
 }

public int getZ(){
  return this.z;
 }

 public int getStep(){
   return this.step;
}
       
}

public class Main {
  //�ƶ�����������ϣ��£����ң�ǰ���������
 static int dir[][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}};
 char map[][][];//��ά��ͼ,�����
 int R, L, C;

 public Main(char map[][][],int L,int R,int C){
    this.map=map;
    this.L=L;
    this.R=R;
    this.C=C;
}

int bfs(int x, int y, int z) {
    
    ArrayList<point> queue=new ArrayList<point>();

    queue.add(new point(x,y,z,0));
   
    while(queue.size()!=0) {
       
        for(int i = 0; i < 6; i++) {
            //��ͷԪ�س�ӣ�
             point head=queue.get(0);
            int a = head.x + dir[i][0];
            int b = head.y + dir[i][1];
            int c = head.z + dir[i][2];
            if(a >= 0 && a < L && b >= 0 && b < R && c >= 0 && c < C && map[a][b][c] == 'E')
                return head.step + 1;
            if(a >= 0 && a < L && b >= 0 && b < R && c >= 0 && c < C && map[a][b][c] != '#') {
                  //Ԫ����ӣ�
                queue.add(new point(a,b,c,head.step+1));
                
                map[a][b][c] = '#';
              
            }
        }
       queue.remove(0);
    }
    return -1;
}

 
 public static void main(String[] args){
  Scanner in = new Scanner(System.in);
    int a, b, c;
    int L1,R1,C1;
    while(in.hasNext()) {
       L1=in.nextInt();
       R1=in.nextInt();
       C1=in.nextInt();
       if(L1==0&&R1==0&&C1==0) break;
        a = b = c = 0;
  
        char map1[][][]=new char[L1][R1][C1];
   
        for(int i = 0; i < L1; i++)
          for(int j = 0; j < R1; j++){
           map1[i][j]=in.next().toCharArray();
           for(int k=0;k< C1;k++){
                if(map1[i][j][k] == 'S') {
                    a = i;
                    b = j;
                    c = k;
                }
            }
         }

       
        Main m=new Main(map1,L1,R1,C1);
        
        int sum = m.bfs(a, b, c);
        if(sum != -1)
            System.out.printf("Escaped in %d minute(s).n", sum);
        else
            System.out.printf("Trapped!n");
    }
   }
}
							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
 
public class Main{   
  
    private static final int MAXLEN = 101;   
    private static int[][] c = new int[MAXLEN][MAXLEN];   
    private static int[][] b = new int[MAXLEN][MAXLEN];   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in)); 

  
        while (scan.hasNext()) {   
            String s1 = "", s2 = "";   
            while (scan.hasNext()) {   
                String s = scan.nextLine();   
                if (s.startsWith("#")) {   
                    break;   
                }   
                s.trim();   
                s1 = s1 + s + " ";   
            }   
            while (scan.hasNext()) {   
                String s = scan.nextLine();   
                if (s.startsWith("#")) {   
                    break;   
                }   
                s.trim();   
                s2 = s2 + s + " ";   
            }   
            String[] ss1 = s1.trim().split(" ");   
            String[] ss2 = s2.trim().split(" ");   
            lcsLength(ss1, ss2);   
            printLCS(ss1, ss1.length, ss2.length);   
        }   
    }   
  
    public static void lcsLength(String[] x, String[] y) {   
        for (int i = 0; i <= x.length; i++) {   
            c[i][0] = 0;   
        }   
        for (int i = 0; i <= y.length; i++) {   
            c[0][i] = 0;   
        }   
        for (int i = 1; i <= x.length; i++) {   
            for (int j = 1; j <= y.length; j++) {   
                if (x[i - 1].equals(y[j - 1])) {   
                    c[i][j] = c[i - 1][j - 1] + 1;   
                    b[i][j] = 0;   
                } else if (c[i - 1][j] >= c[i][j - 1]) {   
                    c[i][j] = c[i - 1][j];   
                    b[i][j] = 1;   
                } else {   
                    c[i][j] = c[i][j - 1];   
                    b[i][j] = -1;   
                }   
            }   
        }   
    }   
  
    public static void printLCS(String[] x, int m, int n) {   
        int i = m;   
        int j = n;   
        if (i == 0 || j == 0) {   
            return;   
        }   
        if (b[i][j] == 0) {   
            printLCS(x, i - 1, j - 1);   
            System.out.print(x[i - 1] + " ");   
        } else if (b[i][j] == 1) {   
            printLCS(x, i - 1, j);   
        } else {   
            printLCS(x, i, j - 1);   
        }   
    }   
}  

							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {    
    static long[][] M=new long[2000][2000];
    public static long comb(int n,int k){
        if(k>(n/2))k=n-k;
        if(n< 2000&&k< 2000) return M[n][k];
        else if(k==n||k==0) return 1;
        else if(k==1) return n;
        else return comb(n-1,k)+comb(n-1,k-1);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token;
        int n=0,k=0;
        for(int i=0;i< 2000;i++){
            M[i][i]=1;
            M[i][0]=1;
            M[i][1]=i;
            M[0][i]=0;
        }
        for(int i=1;i< 2000;i++){
            for(int j=2;j< 2000;j++){
                if(i!=j){
                    M[i][j]=M[i-1][j-1]+M[i-1][j];
                }
            }
        }
        while(true){
          token=new StringTokenizer(stdin.readLine());
           n=Integer.parseInt(token.nextToken());
           k=Integer.parseInt(token.nextToken());
           if(k==0&&n==0) break;
           System.out.println(comb(n,k));
        }
    }
}
							

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

/* @author: */
import java.util.Scanner;
public class Main{
  static int arr[]=new int[20];
  static int n,minn;
  static int save[]=new int[20];

 static void bfs(int a)
{
   int i,j;
   if(a>=minn)return;
   if(arr[a-1]==n)
   {
     if(a< minn){
    minn=a;
    for(i=0;i< a;i++)
      save[i]=arr[i];
     }
     return;
    }
    for(i=a-1;i>=0;i--)
    {
    for(j=i;j>=0;j--)
    {
       if(arr[i]+arr[j]>n)continue;
       if(arr[i]+arr[j]<=arr[a-1])continue;
       arr[a]=arr[i]+arr[j];
       if(a==minn-2&&arr[a]< n)break;
       bfs(a+1);
    }
    if(j!=0)break;
    }
}

 public static void main(String args[])
{
      Scanner sc=new Scanner(System.in);
    while(sc.hasNext())
    {
        n=sc.nextInt();
        if(n==0) break;
     minn=11;
     arr[0]=1;
     bfs(1);
     for(int k=0;k< minn-1;k++)
      System.out.printf("%d ",save[k]);
    System.out.printf("%dn",save[minn-1]);
    }
  }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  TreeSet< Integer> t=new TreeSet< Integer>();
  for(int i=0;i< 50;i++)
  {
   if(Math.pow(2, i)>2000000000) break;
   for(int j=0;;j++)
   {
    int ans2=(int)(Math.pow(2, i)*Math.pow(3, j));
    if(ans2>2000000000) break;
    for(int k=0;;k++)
    {
     int ans1=(int)(Math.pow(2, i)*Math.pow(3, j)*Math.pow(5, k));
     if(ans1>2000000000) break;
     for(int w=0;;w++)
     {
      int ans=(int)(Math.pow(2, i)*Math.pow(3, j)*Math.pow(5, k)*Math.pow(7, w));
      if(ans>2000000000) break;
      t.add(ans);
      }
     }
    }
   }
   Integer[] arr=new Integer[6000];
   t.toArray(arr);
   Scanner in=new Scanner(System.in);
   while(true)
   {
   int n=in.nextInt();
   if(n==0) break;
   if (n % 10==1&&n%100!=11) System.out.println("The "+n+"st humble number is "+arr[n-1]+".");
   else if (n % 10==2&&n%100!=12) System.out.println("The "+n+"nd humble number is "+arr[n-1]+".");
   else if (n % 10==3&&n%100!=13) System.out.println("The "+n+"rd humble number is "+arr[n-1]+".");
   else System.out.println("The "+n+"th humble number is "+arr[n-1]+".");
   }
 }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int count=0;
  while(true)
  {
   count++;
   if(count!=1) System.out.println();    
   int a=in.nextInt();
   if(a==0) break;
   int[] b=new int[a];
   for(int i=0;i< a;i++)
    b[i]=in.nextInt();
   for(int a1=0;a1< a-5;a1++)
    for(int a2=a1+1;a2< a-4;a2++)
     for(int a3=a2+1;a3< a-3;a3++)
      for(int a4=a3+1;a4< a-2;a4++)
       for(int a5=a4+1;a5< a-1;a5++)
    for(int a6=a5+1; a6< a; a6++){
     System.out.println(b[a1]+" "+b[a2]+" "+b[a3]+" "+b[a4]+" "+b[a5]+" "+b[a6]);
    }
    }                    
 }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
   {
    int n=in.nextInt();
    if(n==0)break;
    int i,j,m=1;
    while(true)
    {
          i=0;
      j=n-1;
      while(j!=0)
       {
        i=(i+m-1)%j;
        j--;
        if(i==0) break;
       }
      if(j==0)
       {
        System.out.println(m);
        break;
       }
       m++;
    }
    }
  }
}

							

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

import java.util.*;
public class Main {

 private static int[][] position = new int[8][2];
 private static int[][] chessboard = new int[8][8];

 public Main() {
  initPosition();
 }

 /**
  * ��ʼ��������ߵķ���
  */
 private static void initPosition() {
  position[0][0] = -2;
  position[0][1] = -1;
  position[1][0] = -2;
  position[1][1] = 1;
  position[2][0] = -1;
  position[2][1] = -2;
  position[3][0] = -1;
  position[3][1] = 2;
  position[4][0] = 1;
  position[4][1] = -2;
  position[5][0] = 2;
  position[5][1] = -1;
  position[6][0] = 1;
  position[6][1] = 2;
  position[7][0] = 2;
  position[7][1] = 1;
 }

 private static int[] getRC(String s) {
  int[] rc = new int[2];
  rc[0] = Integer.valueOf(String.valueOf(s.charAt(1))) - 1;
  rc[1] = s.charAt(0) - 'a';
  return rc;
 }

 /**
  * ��������㷨
  * 
  * @param s1
  * @param s2
  */
 public static void bsf(String s1, String s2) {
  int[] rc = getRC(s1);
  int formR = rc[0];
  int formC = rc[1];
  // System.out.println(formR + " ," + formC);
  rc = getRC(s2);
  int toR = rc[0];
  int toC = rc[1];
  // System.out.println(toR + " ," + toC);
  LinkedList< Point> queue = new LinkedList<Point>();

  Point p = new Point();
  p.r = formR;
  p.c = formC;
  p.steps = 0;
  queue.addLast(p);
  chessboard[p.r][p.c] = 1;
  p = null;

  while (!queue.isEmpty()) {
   p = queue.getFirst();
   queue.removeFirst();
   if (p.r == toR && p.c == toC) {
    System.out.println("To get from " + s1 + " to " + s2
      + " takes " + p.steps + " knight moves.");
    break;
   }
   for (int i = 0; i < 8; ++i) {
    Point pp = new Point();
    pp.r = p.r + position[i][0];
    pp.c = p.c + position[i][1];
    pp.steps = p.steps + 1;
    if (pp.r >= 0 && pp.c >= 0 && pp.r <= 7 && pp.c <= 7
      && chessboard[pp.r][pp.c] == 0) {
     queue.addLast(pp);
     chessboard[pp.r][pp.c] = 1;
    }
    pp = null;
   }
   p = null;
  }
 }

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  initPosition();
  while (sc.hasNext()) {
   chessboard = null;
   chessboard = new int[8][8];
   String s1 = sc.next();
   String s2 = sc.next();
   Main.bsf(s1, s2);
  }
 }

}

class Point {
 int r;
 int c;
 int steps;
}


							

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

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    double[] x,y;
    double k1,k2,b1,b2,ox,oy;
    double r;
    while (scanner.hasNext()){
        x=new double[3];
        y=new double[3];
        for (int i=0;i< 3 ;i++ ){
            x[i]=scanner.nextDouble();
            y[i]=scanner.nextDouble();
        }
        if (y[0]==y[1]){
            double t=y[0];
            y[0]=y[2];
            y[2]=t;
            t=x[0];
            x[0]=x[2];
            x[2]=t;
        }
        if (y[0]==y[2]){
            double t=y[0];
            y[0]=y[1];
            y[1]=t;
            t=x[0];
            x[0]=x[1];
            x[1]=t;
        }
    k1=0-(x[0]-x[1])/(y[0]-y[1]);
    b1=(y[0]+y[1])/2-k1*(x[0]+x[1])/2;
    k2=0-(x[0]-x[2])/(y[0]-y[2]);
    b2=(y[0]+y[2])/2-k2*(x[0]+x[2])/2;
    ox=(b2-b1)/(k1-k2);
    oy=k1*ox+b1;
    r=Math.sqrt((ox-x[0])*(ox-x[0])+(oy-y[0])*(oy-y[0]));
    System.out.println(Math.round(2*3.141592653589793*r*100.0)/100.0);
    }
}
}


							

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        int kase = 0;
        while (true) {

            int n = cin.nextInt();

            if (n == 0) {
                break;
            }

            kase++;

            List<T> list = new ArrayList<T>();

            for (int i = 1; i <= n; i++) {
                int x = cin.nextInt();
                int y = cin.nextInt();
                int z = cin.nextInt();

                list.add(new T(x, y, z));
                list.add(new T(y, x, z));

                list.add(new T(x, z, y));
                list.add(new T(z, x, y));

                list.add(new T(y, z, x));
                list.add(new T(z, y, x));

            }

            Collections.sort(list, new Comparator() {

                public int compare(Object arg0, Object arg1) {
                    T t1 = (T) arg0;
                    T t2 = (T) arg1;

                    if (t2.x > t1.x) {
                        return t2.x - t1.x;
                    } else if (t2.x == t1.x && t2.y > t1.y) {
                        return t2.y - t1.y;
                    } else if (t2.x == t1.x && t2.y == t1.y && t2.z > t1.z) {
                        return t2.z - t1.z;
                    }

                    return -1;
                }
            });

            int[] f = new int[list.size() + 1];
            for (int i = 0; i < f.length; i++) {
                f[i] = 0;
            }

            f[0] = list.get(0).z;

            int max = f[0];

            for (int i = 1; i < list.size(); i++) {
                int m = list.get(i).z;

                for (int k = 0; k < i; k++) {

                    if (list.get(k).x > list.get(i).x && list.get(k).y > list.get(i).y) {
                        m = Math.max(m, f[k] + list.get(i).z);
                    }
                }

                max = Math.max(max, m);

                f[i] = m;
            }
            System.out.println("Case " + kase + ": maximum height = " + max);
        }
    }
    
    static class T {

        int x;
        int y;
        int z;

        public T(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

}

							

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

import java.util.*;
public class Main {   
    static int c=0;   
    static String[] str;   
    static double[][] map;   
    static double[] v;   
    static int n,m;   
    static boolean[] visited;   
       
    public static void main(String[] args){   
        Main p=new Main();   
        Scanner cin=new Scanner(System.in);   
        while(true){   
            c++;   
            n=cin.nextInt();   
            if(n==0) return;   
            str=new String[n];   
            map=new double[n][n];   
            v=new double[n];   
            visited=new boolean[n];   
            for(int i=0;i< n;i++){   
                str[i]=cin.next();   
                map[i][i]=1;   
            }   
            m=cin.nextInt();   
            for(int i=0;i< m;i++){   
                String a=cin.next();   
                double r=cin.nextDouble();   
                String b=cin.next();   
                map[p.find(a)][p.find(b)]=r;   
                   
            }      
            p.solve();   
        }   
    }   
    void solve(){   
            floyd(map);   
            for(int i=0;i< n;i++){   
                if(map[i][i]>1){   
                    System.out.println("Case " + c +  ": Yes");   
                    return;   
                }   
            }   
            System.out.println("Case " + c +  ": No");   
    }   
    void floyd(double[][] map){   
        for(int k=0;k < n;k++)   
            for(int i=0;i< n;i++)   
                for(int j=0;j< n;j++)   
                    if(map[i][j]< map[i][k]*map[k][j])   
                        map[i][j]=map[i][k]*map[k][j];   
    }   
    int find(String a){   
        for(int i=0;i< n;i++)   
            if(a.equals(str[i]))   
                return i;   
        return 0;   
    }   
}  


							

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

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

public class Main{
 static boolean[][] g=new boolean[305][100];
 static int[] xm=new int[305];
 static int[] ym=new int[100];
 static boolean[] chk=new boolean[100];
 static int un,vn;
 public static boolean search(int u){
   int v;
   for(v=0;v< vn;v++){
    if(g[u][v]&&!chk[v]){
    chk[v]=true;
    if(ym[v]==-1||search(ym[v])){
      ym[v]=u;
      xm[u]=v;
      return true;
    }            
     }
   }
  return false;
 }

public static int match(){
 int u,ans=0;
 Arrays.fill(xm, -1);
 Arrays.fill(ym, -1);
 for(u=0;u< un;u++)
   if(xm[u]==-1){
    Arrays.fill(chk, false);
    if(search(u)) ans++;
    }
  return ans;
 }

 public static void main(String[] args){
  Scanner cin=new Scanner(new BufferedInputStream(System.in));
  while(cin.hasNext()){
   int n=cin.nextInt();
   un=n;
   vn=84;
   for(int i=0;i< g.length;i++)
    Arrays.fill(g[i], false);
   for(int i=0;i< n;i++){
    int t=cin.nextInt();
    for(int j=0;j< t;j++){
        int p=cin.nextInt();
     int q=cin.nextInt();
     g[i][(p-1)*12+q-1]=true;
    }
    }
    System.out.println(match());
  }
 }
}
							

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

//* @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 max=in.nextInt();
  max*=max;
  int[] ax=new int[a+1];
  int[] ay=new int[a+1];
  int[] arr=new int[a+1];
  int[] bool=new int[a+1];
  for(int i=1;i<=a;i++)
    arr[i]=i;
  for(int i=1;i<=a;i++)
  {
    ax[i]=in.nextInt();
    ay[i]=in.nextInt();
  }
  while(in.hasNext())
  {
   if(in.next().equals("O"))
    {
    int w=in.nextInt();
    if(bool[w]==1) continue;
    for(int j=1;j<=a;j++)
     {
       if(bool[j]==0) continue;
       int u=j;
       while(arr[u]!=u)
        u=arr[u];
       int l=w;
       while(arr[l]!=l)
        l=arr[l];
       if(l==u) continue;
       int x=ax[w]-ax[j];
       int y=ay[w]-ay[j];
       if(x*x+y*y<=max)
        {
        if(u>l) arr[j]=arr[w]=arr[u]=l;
        else arr[j]=arr[w]=arr[l]=u;
        }
      }
    bool[w]=1;
     }
     else
     {
    int r=in.nextInt(),w=r;
    while(arr[w]!=w)
       w=arr[w];
    int t=in.nextInt(),u=t;
    while(arr[u]!=u)
       u=arr[u];
    arr[r]=w;
    arr[t]=u;
    if(arr[w]==arr[u]&&bool[w]==1) System.out.println("SUCCESS");
    else System.out.println("FAIL");
      }
   }
 }
}
							

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

import java.util.Scanner;


public class Main {

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   while(true) {
   int n = cin.nextInt();
   int i = 0;
   int[] a = new int[n];
   while(n > 0) {
    a[i++] = cin.nextInt();
    n--;
   }
    for(i=1 ; i< a.length; i++)
     a[i]=a[i]^a[i-1];
    if(a[a.length-1] != 0)
     System.out.println("Yes");
    else 
     System.out.println("No");
   }
  
}

}


							

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

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static BigInteger getVolume(int[] a, int n) {
        BigInteger sum = new BigInteger("0");
        BigInteger s = new BigInteger("0");
        int i = 0;
        for (; i < n - 1; i++) {
            s = s.add(new BigInteger(String
                .valueOf((Math.abs(a[0] - a[i + 1])))));
        }
        sum = new BigInteger(String.valueOf(s)).add(sum);
        i = 1;
        while (i < n) {
        s = s.subtract(new BigInteger(String.valueOf(new BigInteger(String
            .valueOf((n - 2 * i))).multiply(new BigInteger(String
            .valueOf((Math.abs(a[i] - a[i - 1]))))))));
        sum = sum.add(new BigInteger(String.valueOf(s)));
            i++;
        }
        return sum;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        Arrays.sort(a);
        System.out.println(Main.getVolume(a, n));
    }

}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] arr=new int[1000001];
  arr[1]=1;
  arr[2]=2;
  for(int i=3;i< 1000001;i++)
   {
    if(i%2==0) arr[i]=(arr[i-2]+arr[i/2])%1000000000;
    else arr[i]=arr[i-1];
   }
  int a=in.nextInt();
  System.out.println(arr[a]);
 }
}

							

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

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

 
static  int maxs=Integer.MAX_VALUE/3;
int f[][][]=new int[2][3831][2];
int g[][][]=new int[2][3831][2];
int a[]=new int[3831];
int n,m;
int maxv(int x,int y){
  return x>y?x:y;
 }
void dp(){
    int pre=0,cur=1;
    for(int i=0;i<=m;i++) f[1][i][0]=f[1][i][1]=g[1][i][0]=g[1][i][1]=-maxs;
    f[1][0][0]=f[1][1][1]=0;
    g[1][0][0]=0; g[1][1][1]=a[1];
    for(int i=2;i<=n;i++){
        pre=cur; cur=(cur+1)%2;
        f[cur][0][1]=-maxs;
        g[cur][0][1]=-maxs;
        for(int j=1;j<=m;j++){
           f[cur][j][0]=maxv(f[pre][j][0],f[pre][j][1]);
           f[cur][j][1]=maxv(f[pre][j-1][0],f[pre][j-1][1]+a[i]);
           g[cur][j][0]=maxv(g[pre][j][0],g[pre][j][1]);   
           g[cur][j][1]=maxv(g[pre][j-1][0],g[pre][j-1][1]+a[i]);       
        }        
    }     
    int result=maxv(maxv(f[cur][m][0],f[cur][m][1]),g[cur][m][1]);
    System.out.printf("%dn",result);
}

  void init(){
   Scanner sc=new Scanner(System.in);
     n=sc.nextInt();
    m=sc.nextInt();

    for(int i=1;i<=n;i++)
    a[i]=sc.nextInt();
  }
 public static void main(String args[]){
    Main m=new Main();
     m.init();
     m.dp();
   }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class WHO implements Comparable{
    String name;
    int index;
    public int compareTo(Object temp){
        WHO tmp = (WHO)temp;
        if(tmp.index< this.index) return -1;
        return 1;
    }
}
public class Main {
    static final int N = 100000;
    static WHO who[] = new WHO[N];
    static void start(){
        for(int i=0;i< N;++i)
            who[i] = new WHO();
    }

  public static void main(String[]args) throws Exception{
    int i,j,n,t=0;
    start();
    Scanner cin = new Scanner(System.in);
    //Scanner cin = new Scanner(new FileInputStream("input.txt"));
    while(cin.hasNext()){
        n = 0;
        who[n].name = cin.next();
        who[n].name = cin.next();
        while(!who[n].name.equals("END")){
            j = cin.nextInt();
            i = cin.nextInt();
            who[n].index = i-j;
            ++n;
            who[n].name = cin.next();
        }
        Arrays.sort(who,0,n);
        if(t>0) System.out.println();
        for(i=0;i< n;++i)
            System.out.println(who[i].name);
        t = 1;
    }
   }
}

							

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

//* @author:
import java.io.*;
import java.util.*;
public class Main { 
   static int SZ=1005;
   public static void main(String[] args) throws Exception {
        int r,c,q;
        int sum;
        int i,j,x1,y1,x2,y2; 
       int[][] area=new int[SZ][SZ]; 
       for(i=0;i< SZ;++i) area[i][0]=0; 
       Scanner cin=new Scanner(System.in); 
        int T=cin.nextInt(); 
       while(--T>=0) {
         r=cin.nextInt(); 
         c=cin.nextInt(); 
         for(i=0;i< r;++i)
           for(j=1;j<=c;++j){  
          area[i][j]=cin.nextInt(); 
           area[i][j]+=area[i][j-1];
          } 
          q=cin.nextInt();
          while(--q>=0)
           { 
           x1=cin.nextInt(); 
           y1=cin.nextInt(); 
           x2=cin.nextInt(); 
           y2=cin.nextInt(); 
           sum=0; 
           for(i=x1-1;i< x2;++i) 
               sum+=area[i][y2]-area[i][y1-1]; 
              System.out.println("Absolutni hodnota pohodlnosti je "+sum+" bodu.");
            }  
          System.out.println("");
        }  
 }  
}  
							

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

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


public class Main {
 public static void main(String[] args)
 {
    Scanner in = new Scanner(System.in);
    int numOfSon = in.nextInt();
    int power = in.nextInt();
    int[] potential = new int[numOfSon];
    int sum = 0;
    if(power%2==1)
    {
         for(int i = 0; i< numOfSon; i++)    
      {
        potential[i] = in.nextInt();
        if(potential[i]>0)
            sum = (int) (sum + Math.pow(potential[i],power));        
      }
    }
    else
    {
      for(int i = 0; i< numOfSon; i++)    
    {
    potential[i] = in.nextInt();
    sum = (int) (sum + Math.pow(potential[i],power));        
       }
    }
   System.out.println(sum);
  }
}

							

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

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

public class Main {
 static double area( double l1, double l2, double l3 )
{
    double p = ( l1 + l2 + l3 ) / 2;
    return Math.sqrt( p * (p-l1) * (p-l2) * (p-l3) );
}

static double sq( double a )
{
    return a * a;
}

static public void main( String [] str ) throws Exception{
       Scanner sc = new Scanner(System.in);
     double ab,ad,ac,bc,bd,cd,ah,dh,af,sabc,sbcd, hi, v, bh1, bh2;
       ab=sc.nextDouble();
       ac=sc.nextDouble();
       ad=sc.nextDouble();
       bc=sc.nextDouble();
       bd=sc.nextDouble();
       cd=sc.nextDouble();

    
    sabc = area( ab, bc, ac );
    sbcd = area( bc, cd, bd );
    
    ah = sabc * 2 / bc;
    dh = sbcd * 2 / bc;


    bh1 = Math.sqrt( bd*bd - dh*dh );
    if( cd*cd > bd*bd + bc*bc ) bh1 = -bh1;

    bh2 = Math.sqrt( ab*ab - ah*ah );
    if( ac*ac > ab*ab + bc*bc ) bh2 = -bh2;
    
    af = Math.sqrt( ad*ad - sq( bh1 - bh2 ) );
    hi = area( af, dh, ah ) * 2 / ah;
    v = sabc * hi / 3;

    System.out.printf( "%.4fn", v );

  }
}


							

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

//* @author popop0p0popo
public class Main{
    public static void main(String[] args){
        int t,h,w;
        for (int i=2992;i< 10000 ;i++ ){
            t=getI(i);
            h=getD(Integer.toHexString(i));
            w=getD(Integer.toString(i,12));
            if (t==h&&h==w){
                System.out.println(i);
            }
        }
    }

    public static int getD(String n){
        int d=0;
        for (int i=0;i< n.length() ;i++ ){
            if (Character.isLetter(n.charAt(i))){
                d=d+10+(int)(n.charAt(i)-'a');
            }
            else{
                d=d+(int)(n.charAt(i)-'0');
            }
        }
        return d;
    }

    public static int getI(int n){
        int a=n/1000;
        int b=(n-1000*a)/100;
        int c=(n-1000*a-100*b)/10;
        int d=n-1000*a-100*b-10*c;
        return a+b+c+d;
    }
}


							

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

#include <vector>

using namespace std;

typedef int type;                //��������

const int size = 210;            //ͼ�Ķ���ģ
const type MAX_FEE = 10000000;        //��������
const int MAX = 1000;            //�������

class minfee_flow
{

public:

    //ɾ�����б�
    void clear();
    //���һ���from��to ����Ϊc ��λ������Ϊw �ı�
    void insert_edge( int from, int to, int c, type w );
    
    //    ����С�����������ط���
    //    nodenum���� ( �����0,1...nodenum-1 )
    //    beginΪԴ��endΪ�㣬flow��4���������( NULL��ʾ������ )
    type min_fee_max_flow( int nodenum, int begin, int end, int *flow );


private:
    /*    needn't care */

    struct edge
    {
        int c,f;
        type w;
        int to;
        int rev_i;
    };                    //�ߵĶ���

    vector<edge> e[size];                    //�ڽӱ�
    
    type fee, sum, dis[size+1], l[size];    //�ܷ��ã����·���úͣ�(dijstra)��̾��룬��4�޸ı�Ȩ�ı��
    bool sign[size];                        //(dijstra)�Ƿ�ȷ�����·
    edge *from[size];                        //(dijstra)���·���У��õ�����
    int pri[size];                            //(dijstra)..�õ��ǰ��
    int n, s, t;                            //������Դ����
    int maxflow, add;                        //�����ÿ�ε�����

    bool dijstra( );                    //(dijstra)
    void increse( edge *ep, int d );    //����*ep�����d
    void modify( );                        //�޸�l,�������·���

};

///////////////////////////////////////////////////////////////////////
//    ����ʵ��

void minfee_flow::clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i].clear();
}

bool minfee_flow::dijstra( )
{
    int i, j, k, to, v;

    for( i=0; i<=n; i++ )
        dis[i] = MAX_FEE;

    memset( sign, 0, sizeof(bool)*n );

    dis[ s ] = 0;

    for( i=0; i<n; i++ )
    {
        k = n;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[k] > dis[j] )
                k = j;

        if( k == n )
            break;

        sign[ k ] = true;

        for( j=0; j<e[k].size(); j++ )
        if( e[k][j].f != e[k][j].c )
        {
            to = e[k][j].to;
            if( !sign[to] && dis[ to ] > ( v = dis[ k ] + l[k] - l[to] + e[k][j].w ) )
            {
                dis[ to ] = v;
                pri[ to ] = k;
                from[ to ] = &e[k][j];
            }
        }
    }

    return sign[t] == true;
}

void minfee_flow::increse( edge *ep, int d )
{
    ep->f += d;
    e[ep->to][ep->rev_i].f -= d;
}

void minfee_flow::modify( )
{
    int i, temp;

    add = MAX; sum = 0;
    for( i=t; i!=s; i = pri[i] )
    {
        sum += l[pri[i]] - l[i] + from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }

    sum += l[t];

    for( i=t; i!=s; i = pri[i] )
        increse( from[i], add );

    for( i=0; i<n; i++ )
        l[i] += dis[i];

    return;
}

void minfee_flow::insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, to, e[to].size() }, eg2 = { 0, 0, -w, from, e[from].size() };
    e[from].push_back( eg1 );
    e[to].push_back( eg2 );
}

type minfee_flow::min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;
    memset( l, 0, sizeof(type)*n );

    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }
    
    if( flow )
        *flow = maxflow;

    return fee;
}

///////////////////////////////////////////////////////////////////////////////////////////

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

minfee_flow mf;
char map[110][110];

int main()
{
    int n, m, a, b, i, j, h;
    int x1[100], y1[100], x2[100], y2[100]; 

    while( 1 )
    {
        scanf( "%d %d", &n, &m );
        
        if( n == 0 && m == 0 )
            break;
        
        for( i=0; i<n; i++ )
            scanf( "%s", map[i] );
        
        a = 0, b = 0;
        for( i=0; i<n; i++ )
        for( j=0; j<m; j++ )
            if( map[i][j] == 'H' )
            {
                x1[a] = i, y1[a] = j;
                a++;
            }
            else if( map[i][j] == 'm' )
            {
                x2[b] = i, y2[b] = j;
                b++;
            }

        mf.clear( );

        h = a+b+2;
        for( i=0; i<a; i++ )
        for( j=0; j<b; j++ )
            mf.insert_edge( 2+i, 2+a+j, 1, abs( x1[i]-x2[j] ) + abs( y1[i]-y2[j] ) );

        for( i=0; i<a; i++ )
            mf.insert_edge( 0, 2+i, 1, 0 );
        for( i=0; i<b; i++ )
            mf.insert_edge( 2+a+i, 1, 1, 0 );

        printf( "%dn", mf.min_fee_max_flow( h, 0, 1, 0 ) );
    }

    
    return 0;
}



							

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

//* @author: 
import java.util.*;
public class Main
{
 public static void main(String[] args){
   Scanner sc=new Scanner(System.in);
     
   long dp[][]=new long[11][2010];
   int nn=sc.nextInt();
   for (int i=1;i<=2000;i++) dp[1][i]=1;
   for (int i=2;i<=10;i++)
        for (int j=i;j<=2000;j++)
        for (int k=1;k<=j/2;k++) dp[i][j]+=dp[i-1][k];
    for (int ii=1;ii<=nn;ii++) {
        int n=sc.nextInt();
        int m=sc.nextInt();
     long ans=0;
    for (int i=n;i<=m;i++) ans+=dp[n][i];
    System.out.printf("Case %d: n = %d, m = %d, # lists = %dn",ii,n,m,ans);
    }
  }
}

							

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main{

  public static void main(String[] args) throws Exception{

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    for(int a=1;a<=n;a++){
        String strTemp = in.readLine();
        StringTokenizer toke = new StringTokenizer(strTemp);
        String str1 = toke.nextToken();
        String str2 = toke.nextToken();
        String str = toke.nextToken();
        int length1 = str1.length();
        int length2 = str2.length();
        //array[i][j]表示str1[i]和str2[j]能否组成str[i+j]
        boolean array[][] = new boolean[length2+1][length1+1];
        for(int i=1;i<=length1;i++){
            if(str1.substring(0, i).equals(str.substring(0,i)))
                array[0][i] = true;
            else
                array[0][i] = false;
        }
        for(int i=1;i<=length1;i++){
            if(str2.substring(0, i).equals(str.substring(0,i)))
                array[i][0] = true;
            else
                array[i][0] = false;
        }
        
        for(int i=1;i<=length2;i++){
            for(int j=1;j<=length1;j++){
    if(array[i][j-1]&&str1.charAt(j-1)==str.charAt(i+j-1)||array[i-1][j]&&str2.charAt(i-1)==str.charAt(i+j-1))
                    array[i][j] = true;
                else
                    array[i][j] = false;
            }
        }
        if(array[length2][length1])
            System.out.println("Data set "+a+": yes");
        else
            System.out.println("Data set "+a+": no");
    }
  }
}


							

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

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
         String[] store={"23 * 89 = 2047 = ( 2 ^ 11 ) - 1",
        "47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1",
        "233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1",
        "223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1",
        "13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1",
        "431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1",
        "2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1",
        "6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1",
        "179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1"};
    int[] p={11,23,29,37,41,43,47,53,59};
    Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int n=scanner.nextInt();
    for (int i=0;i< p.length ;i++ ){
        if (p[i]< n){
            System.out.println(store[i]);
        }
        else{
            break;
        }
    }
 }
}


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  String a=in.next();
  int t=0;
  int n=-1;
  for(int i=0;i< 10;i++)
  {
    char c=a.charAt(i);
    if(c!='?'&&c!='X'){
      t+=(c-'0')*(10-i);
    }
    else if(c=='X') t+=10;
    else if(c=='?') n=10-i;
   }
   int ans=-1;
   if(n!=1)
    for(int i=0;i< 10;i++)
    {
    if((t+n*i)%11==0){
        ans=i;
        break;
    }
    }
    else if(n==1)
    {
    for(int i=0;i< 11;i++)
      if((t+i)%11==0){
        ans=i;
        break;
      }
    }
    if(ans==10) System.out.println("X");
    else
    System.out.println(ans);
  }
}
							

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

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

int n,p,c;
int s[1001];

int main()
{
    int i, j, k;
    scanf( "%d %d %d", &n, &p, &c );

    memset( s, 0, sizeof( s ) );

    for( i=0; i<n; i++ )
    {
        scanf( "%d", &j );
        s[j]++;
    }
    s[0] = 0;

    for( i=1; i<p; i++ )
    s[i] += s[i-1];

    k = -1;
    for( i=1; i<p; i++ )
    {
        j = lower_bound( s, s+i, s[i] - c ) - s;
        if( i-j > k )k = i - j;
    }

    printf( "%dn", k );

    return 0;
}

    


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main{
 static long ans=0;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  ans=0;
  int[] arr=new int[a];
  int[] aww=new int[a];
  for(int i=0;i< a;i++)
  {
   String[] ss=in.readLine().split(" ");
   arr[i]=Integer.parseInt(ss[0]);
   aww[i]=Integer.parseInt(ss[1]);
  }
  for(int i=0;i< a;i++)
  {
   for(int j=0;j< a;j++)
    {
    if(arr[i]==aww[j])
    {
      arr[i]=j;
      break;
    }
     }
   }
  mergesort(arr,0,a);
  System.out.println(ans);
    
  }

  static void mergesort(int[] arr,int f,int n)
   {
   int n1,n2;
   if(n>1)
   {
    n1=n/2;
    n2=n-n1;
    mergesort(arr,f,n1);
    mergesort(arr,f+n1,n2);
    merge(arr,f,n1,n2);
    }
  }


  static void merge(int[] arr,int f,int n1,int n2)
   {
    int[] temp=new int[n1+n2];
    int cp=0,cp1=0,cp2=0,i=0;
    while((cp1< n1)&&(cp2< n2))
     {
    if(arr[f+cp1]< arr[f+n1+cp2])
    temp[cp++]=arr[f+(cp1++)];
    else {
        temp[cp++]=arr[f+n1+(cp2++)];
        ans+=n1-cp1;
    }
     }
     while(cp1< n1)
    temp[cp++]=arr[f+(cp1++)];
     while(cp2< n2)
    temp[cp++]=arr[f+n1+(cp2++)];
     for(i=0;i< cp;i++)
    arr[f+i]=temp[i];
   }
}
							

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

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

////////////////////////////////
typedef int Type;/*????????*/
////////////////////////////////

//????????
struct point
{
    Type x,y;
    point(){x=y=0;}
    point(Type x,Type y):x(x),y(y){;}
    bool operator==(point &a){return x==a.x&&y==a.y;}
};
//????
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}

//????
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}

//??????????
int dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}


int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}


////////////////////////////////////////////////////////////
//O(n*log(n))
//??????,??????????????????????wall:????????????
//security

//p????????????!!!

const long convex_size=50010;
int stack[convex_size],sign[convex_size];

int convex(point *p,int n,point *wall)
{
    int i;int st;Type h;

    st=0;
    stack[st++]=0;
    stack[st++]=1;

    for(i=0;i<n;i++)sign[i]=0;

    sign[1]=1;
    i=2;

    while(i<n)
    {
        while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ > /**/ 0)
        //????????????????use '>';    ??????????????????????||n<3,??????'>'??????????
        {
            st--;
            if(h)sign[stack[st]]=0;
        }
        stack[st++]=i;sign[i]=1;
        i++;
    }

    i--;

    while(i>=0)
    {
        while(sign[i])i--;

        while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ > /**/ 0)st--;
                                                                //????
        stack[st++]=i;
        i--;
    }

    st--;

    if(wall)
    {
        for(i=0;i<st;i++)wall[i]=p[stack[i]];
    }

    return st;
}
///////////////////////////////////////////////////////////////////


point p[50010], pt[50010];
int n;


inline int dis_squr( point &a, point &b )
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

int main()
{
    int i, j;
    int temp, best;
    point a, b;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf("%d %d", &pt[i].x, &pt[i].y );

    sort( pt, n );

    n = convex( pt, n, p );
    
    best = 0;
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ )
        if( ( temp = dis( p[i], p[j] ) ) > best )
            best = temp;

    printf( "%dn", best );

    return 0;
}


							

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

//PKU_2186_Popular Cows_ǿlͨ��_���(kosaraju)

#include <iostream>
using namespace std;

struct Point
{
    int Index;
    Point *Next;

    Point(int index = 0)
    {
        Index = index;
        Next = NULL;
    }
};

struct HeadPoint
{
    Point *List;
    Point *LastPoint;
    HeadPoint()
    {
        List = NULL;
        LastPoint = NULL;
    }

    void Add(int index)
    {
        if (LastPoint != NULL)
        {
            LastPoint->Next = new Point(index);
            LastPoint = LastPoint->Next;
        }
        else
        {
            LastPoint = List = new Point(index);
        }
    }

    ~HeadPoint()
    {
        Point *p = List;
        while (p != NULL)
        {
            Point *q = p;
            p = p->Next;
            delete q;
        }
    }
};
HeadPoint *MAP = NULL;
HeadPoint *MAP2 = NULL;
HeadPoint *FinalMap = NULL;
int *nPost = NULL;
int *nBelong = NULL;
bool *visited = NULL;
int nPostorder = 0;
int nBe = 0;
int N,M;

void DFS1(int index)
{
    visited[index] = true;
    for (Point *p = MAP[index].List;p != NULL;p = p->Next)
    {
        if (!visited[p->Index])
            DFS1(p->Index);
    }
    nPost[++nPostorder] = index;
}

void DFS2(int index)
{
    visited[index] = true;
    for (Point *p = MAP2[index].List;p != NULL;p = p->Next)
    {
        if (!visited[p->Index])
            DFS2(p->Index);
    }
    nBelong[index] = nBe;
}

void init()
{
    scanf("%d%d",&N,&M);
    MAP = new HeadPoint[N + 1];   //0 not use
    MAP2 = new HeadPoint[N + 1];
    nPost = new int[N + 1];
    visited = new bool[N + 1];
    nBelong = new int[N + 1];
    for (int i = 0;i < M;i++)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        MAP[m].Add(n);
        MAP2[n].Add(m);
    }
}

void clear()
{
    delete []MAP;
    delete []MAP2;
    delete []FinalMap;
    delete []nPost;
    delete []visited;
    delete []nBelong;
}

void kosaraju()
{
    nBe = nPostorder = 0;
    memset(visited,false,(N + 1) * sizeof(bool));
    for (int i = 1;i < N + 1;i++)
    {
        if (!visited[i])
            DFS1(i);
    }
    memset(visited,false,(N + 1) * sizeof(bool));
    for (int i = N ;i > 0;i--)
    {
        if (!visited[nPost[i]])
        {
            nBe++;
            DFS2(nPost[i]);
        }
    }
}

int Answer()
{
    FinalMap = new HeadPoint[nBe + 1];
    for (int i = 1;i < N + 1;i++)
    {
        for (Point *p = MAP[i].List;p != NULL;p = p->Next)
        {
            if (nBelong[i] != nBelong[p->Index])
                FinalMap[nBelong[i]].Add(nBelong[p->Index]);
        }
    }
    int FIndex = -1;
    int sum = 0;
    for (int i = 1;i < nBe + 1;i++)
    {
        if (FinalMap[i].List == NULL)
        {
            FIndex = i;
            sum++;
        }
    }
    if(sum == 1)
    {
        int ret = 0;
        for(int i = 1;i < N + 1;i++)
        {
            if(nBelong[i] == FIndex)
                ret++;
        }
        return ret;
    }
    else
        return 0;
}

int main()
{
    init();
    kosaraju();
    cout<<Answer()<<endl;
    clear();

    return 0;
}

/*
Description

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is 
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow. 

Input

* Line 1: Two space-separated integers, N and M 

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular. 

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow. 

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

Hint

Cow 3 is the only cow of high popularity. 

*/

							

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

#include <stdio.h>


char map[10000][80];
int n,m;
bool sign[75][10000];

int main()
{
    int i, j, n, m, k, h, l;
    bool key;

    scanf( "%d %d", &n, &m );
    
    for( i=0; i<n; i++ )
    scanf( "%s", map[i] );

    for( k=1; k<m; k++ )
    {
        key = true;
        for( i=0; i<n&&key; i++ )
        for( j=k; j<m; j++ )
        if( map[i][j] != map[i][j%k] )
        {
            key = false;
            break;
        }
        if( key )break;
    }

    for( h=1; h<n; h++ )
    {
        key = true;
        for( j=0; j<m&&key; j++ )
        if( !sign[j][h] )
        {
            for( i=h; i<n; i++ )
            if( map[i][j] != map[i%h][j] )
            {
                key = false;
                break;
            }
            if( key )
            {
                for( l=1; l*h < n; l++ )
                sign[j][l*h] = true;
            }
        }
        if( key )break;
    }

    printf( "%dn", k*h );

    return 0;
}
							

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

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

bool mem[200100],*sign = mem+100000;
int mem2[200100],*ans = mem2+100000;

typedef pair<int,int> node;
node c[100];
int n;

node mem3[2][100000],*s = mem3[0], *t = mem3[1];
int sn,tn;

int main()
{
    int i, j, n, k, h, m, v;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf( "%d %d", &c[i].first, &c[i].second );

    memset( sign-1000*n-5, 0, sizeof(bool) * ( 1000*2*n+10 ) );

    sign[0] = true;
    ans[0] = 0;
    sn = 0;

    s[sn].first = 0;
    s[sn].second = 0;
    sn++;

    for( i=0; i<n; i++ )
    {
        for( m=sn, j=0 ; j < m ; j++ )
        {
            h = s[j].second + c[i].second;
            k = s[j].first + c[i].first;

            if( ! sign[k] )
            {
                sign[k] = true;
                ans[k] = h;
                
                s[sn].first = k;
                s[sn].second = h;
                sn++;
            }
            else if( h > ans[k] )
            {
                ans[k] = h;

                s[sn].first = k;
                s[sn].second = h;
                sn++;
            }

        }
        
        std::merge( s, s+m, s+m, s+sn, t, greater<node>() );
        swap( t, s );

        m = sn;
        v = s[0].second;
        tn = 0;
        t[tn++] = s[0];

        for( j = 1; j<m; j++ )
        {
            if( s[j].second > v )
            {
                t[tn++] =  s[j];
                v = s[j].second;
            }
        }

        swap( t, s);
        swap( tn, sn);

        if( tn >= 100000 || sn >=100000 )
            while(1) printf( "faintn" );
        
    }

    int answer = 0;
    
    for( i=0; i<=1000*n; i++ )
        if( sign[i] && ans[i] >=0 && i + ans[i] > answer )
            answer = i + ans[i];

    printf( "%dn", answer );

    return 0;
}




							

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

//* @author: <strong>
import java.util.*;
public class Main
{
 private int t;
 private int b[];

 public Main(int t){
   this.t=t;
   b=new int[1000000];
 }

 private void doIt(){
   int st=0;
   while(true){
    t/=10;
    t%=10000;//ȡt���м���λ
    t*=t;//ƽ��
    t%=1000000;//ȡt�ĺ���λ
    if (b[t]!=0){//���t���ֹ�,����ѭ����
      st++;
      System.out.println(t+" "+(st-b[t])+" "+st);//ѭ���ڵĵ�һ����ѭ���ڴ�С����Ҫ���η���ѭ����

      break;
    }
    b[t]=++st;//��¼����Ĵ���
  }
}
 public static void main(String[] args){
     Scanner sc=new Scanner(System.in);
     while(sc.hasNext()){
        int t=sc.nextInt();
        Main m=new Main(t);
        m.doIt();
     }
    
  }
}


							

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

/* @author: */
import java.util.Scanner;
public class Main{
  public static void  main(String args[]) 
{
  int p[]=new int[8010];
  int q[]=new int[8080];
  int n,k;
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  p[0]=0;
  for(int i=1;i< n;i++)
  {
     k=sc.nextInt();
     for(int j=i;j>k;j--)
      p[j]=p[j-1];
      p[k]=i;
  }
  for(int i=0;i< n;i++)
    q[p[i]]=i;
  for(int i=0;i< n;i++)
    System.out.printf("%dn",q[i]+1);
  }
}
							

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

//* @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();
  boolean flag=true;
  int sum=0;
  int[] arr=new int[a+1];
  for(int i=0;i< a;i++)
    arr[i]=in.nextInt();
  for(int i=0;i< a;i++)
  {
    if(flag)
    {
     if(arr[i]>arr[i+1])
     {
      sum+=arr[i]; 
      flag=false;
     }
    }
    else{
     if(arr[i]< arr[i+1])
      { 
         sum-=arr[i]; flag=true;
      } 
     }
    }
    System.out.println(sum);
  }
}
							

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

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


#define y1 yy1

const int size = 210;
int dis[size][size], n, m;
int x1[100], y1[100], x2[100], y2[100];

int s2[100], lim2[100];
int f[100][100];

inline int distance( int i, int j )
{
    return abs( x1[i] - x2[j] ) + abs( y1[i] - y2[j] ) + 1;
}

void init( )
{
    int i, j, t;
    
    for( i=0; i<n; i++ )
        scanf( "%d %d %*d", &x1[i], &y1[i] );
    for( j=0; j<m; j++ )
        scanf( "%d %d %d", &x2[j], &y2[j], &lim2[j] );

    memset( dis, 0x01, sizeof dis );
    memset( s2, 0, sizeof s2 );

    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    {
        scanf( "%d", &f[i][j] );
        t = distance( i, j );

        if( f[i][j] > 0 )
        {
            s2[j] += f[i][j];
            dis[2+n+j][2+i] = -t;
        }

        dis[2+i][2+n+j] = t;
    }

    for( i=0; i<n; i++ )
        dis[0][i+2] = 0;

    for( j=0; j<m; j++ )
    {
        if( lim2[j] > s2[j] )
            dis[2+n+j][1] = 0;
        dis[1][2+n+j] = 0;
    }

}

int from[size];
bool sign[size];

void doit( )
{
    int i, j, k, h = n+m+2, t, l;
    bool key;

    sizeof( from, 0, sizeof from );

    for( k=0, key=false ; k<h && !key; k++ )
    {
        key = true;
        for( i=0; i<h; i++ )
        for( j=0; j<h; j++ )
        if( ( t = dis[0][i] + dis[i][j] ) < dis[0][j] )
        {
            dis[0][j] = t;
            from[j] = i;
            key = false;
            l = j;
        }
    }

    if( key )
        printf( "OPTIMALn" );
    else
    {
        memset( sign, 0, sizeof sign );
        
        for( k = l; !sign[k]; k = from[k] )
            sign[k]  = true;

        j = k;
        do
        {
            i = from[j];
            if( i > 1 && j > 1 )
            {
                if( i< 2+n )
                    f[i-2][j-n-2]++;
                else
                    f[j-2][i-n-2]--;
            }
            j = i;
        }while( j != k );

        printf( "SUBOPTIMALn" );
        for( i=0; i<n; i++ )
        for( j=0; j<m; j++ )
        {
            printf( "%d", f[i][j] );
            if( j < m-1 )
                printf( " " );
            else
                printf( "n" );
        }

    }

    return ;
}

int main( )
{
    while( scanf( "%d %d", &n, &m ) == 2 )
    {
        init( );
        doit( );
    }

    return 0;
}
							

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

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

using namespace std;

typedef pair<int,int> point;
int w, h, n;
int a[110], x[110], y[110], m;

point p[110];

void init( )
{
    int i, xx, yy;
    m = 0;
    n = 0;

    scanf( "%d %d %d", &n, &w, &h );

    a[m++] = 0, a[m++] = h;

    for( i=0; i<n; i++ )
    {
        scanf( "%d %d", &xx, &yy );
        p[i] = point( xx, yy );
        a[m++] = yy;
    }
    
    p[n] = point( w, h );
    n++;

    sort( a, a+m );
    m = unique_copy( a, a+m, a ) - a;
    
    sort( p, p+n );
}

int left[110];

void doit( )
{
    int i, j, k, ans=0, bx, by, t, l, xx;
    
    memset( left, 0, sizeof left );

    for( i=0; i<n; i=j )
    {
        xx = p[i].first;
        for( j=0; j<m; j++ )
        {
            t = xx;
            for( k=j+1; k<m; k++ )
            {
                l = t;
                if( l > a[k]-a[j] )
                    l = a[k]-a[j];

                if( l > ans )
                {
                    ans = l;
                    bx = xx-l;
                    by = a[j];
                }
                
                if( xx - left[k] < t )
                    t = xx - left[k];
            }
        }

        for( j=i; p[i].first == p[j].first; j++ )
        {
            k = lower_bound( a, a+m, p[j].second ) - a;
            left[ k ] = p[i].first;
        }
    }

    printf( "%d %d %dn", bx, by, ans );
}

int main( )
{
    init( );
    doit( );

    return 0;
}