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

//* @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 student = in.nextInt();
   if (0 == student)
    break;
   int[] candy = new int[student];
   for (int i = 0; i < student; i++) {
    candy[i] = in.nextInt();
   }
    int temp = 0;
    int turns = 0;
    while (true) {
           for (int i = 0; i < student; i++) {

        if (i == 0) {
                temp = (int) Math.ceil(candy[i] * 0.5);
        candy[i] = ((int) Math.ceil(candy[student - 1] * 0.5))
            + temp;
             }

    else {
        int temp1 = (int) Math.ceil(candy[i] * 0.5);
        candy[i] = (int) Math.ceil(candy[i] * 0.5) + temp;
        temp = temp1;
    }
    }
        turns++;
        int numberOfCandy = candy[0] % 2 == 0 ? candy[0] : candy[0] + 1;
        int count = 0;
        for (int i = 0; i < student; i++) {
            if (candy[i] % 2 == 0 && candy[i] == numberOfCandy)
                count++;
            else if (candy[i] % 2 != 0
                    && (candy[i] + 1) == numberOfCandy)
                count++;
            else
                break;
        }
        if (count == student) {
            System.out.println(turns + " " + numberOfCandy);
            break;
        }
    }
  }
 }

}

							

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

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 *
 *poj1664
 * f(m, n) = f(m-n, n) + f(m, n-1)
 * f(m, n): ��m��ƻ��ŵ�n�������еķ�����
 * f(m, n-1): ��m��ƻ��ŵ�n-1�������еķ�����(����������һ�������)
 * f(m-n, n): ��m��ƻ��ŵ�n��������,����ÿ�������ж���ƻ��(����n���4,��m-n��ź���,Ȼ��ÿ�����ӷ�һ��)
 * @author NC
 */
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        if (scan.hasNext()) {
            int n = scan.nextInt();
            for (int i = 0; i < n; i++) {
                int a = scan.nextInt();
                int b = scan.nextInt();
                System.out.println(f(a, b));
            }
        }
    }

    static int f(int m, int n) {
        /* ��Щ���Ӳ���ƻ���Ѱ���f(m, n - 1)�У�����0*/
        if (m < 0) {
            return 0;
        }
        /* �պ�ÿ�����ӷ�1��ֻ��һ����� */
        if (m == 0) {
            return 1;
        }
        /* ֻ��1�����ӿ��Էţ�Ҳֻ��ȫ��������һ����� */
        if (n == 1) {
            return 1;
        }
        /* n�����������ٶ���1�� + ֻ����n-1�������� */
        return f(m - n, n) + f(m, n - 1);
    }
}


							

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

//* @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 n=new Integer(stdin.readLine());    
        StringTokenizer tokens;
        int x,y;
        for(int i=0;i< n;i++){
            tokens=new StringTokenizer(stdin.readLine());
            x=new Integer(tokens.nextToken());        
            y=new Integer(tokens.nextToken());
            if(x==y||(x-2)==y)System.out.println(x+y-x%2);
            else System.out.println("No Number");
        }
    }
}

							

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

import java.util.Arrays;
import java.util.Scanner;

/**
 * POJ1661
 * @author Bruce
 *
 */

class Board implements Comparable<Board>{
    int lx;
    int rx;
    int h;
    public Board(int x,int y,int h){
        this.lx = x;
        this.rx = y;
        this.h = h;
    }
    public int compareTo(Board b) {        
        return b.h - this.h;//按照高度排序
    }    
}

public class Main{
    static final int MAX_VALUE = 100000000;
    static int[] leftMin;
    static int[] rightMin;    
    static Board[] boards;
    static int max;
    static int N;
    public static int min(int i,boolean isLeft){
        int x;
        int y = boards[i].h;
        if(isLeft)
            x = boards[i].lx;
        else
            x = boards[i].rx;
        int j;
        for(j=i+1;j<=N;j++){
            if(boards[j].lx <= x && boards[j].rx >= x)//下方有板子
                break;
        }
        if(j > N){//下方没有板子
            if(y > max)
                return MAX_VALUE;
            else 
                return y;
        }else{//因下方有板子而break了
            if(y - boards[j].h > max)
                return MAX_VALUE;
            else{
                if(leftMin[j] == -1)
                    leftMin[j] = min(j,true);
                if(rightMin[j] == -1)
                    rightMin[j] = min(j,false);
    return (y - boards[j].h) + Math.min(leftMin[j]+x-boards[j].lx, rightMin[j]+boards[j].rx-x);
            }
        }
            
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i=0;i< T;i++){
            N = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            max = in.nextInt();
            leftMin = new int[N+1];
            rightMin = new int[N+1];    
            Arrays.fill(leftMin, -1);
            Arrays.fill(rightMin, -1);
            
            boards = new Board[N+1];
            boards[0] = new Board(x,x,y);
            for(int j=1;j<=N;j++){
                boards[j] = new Board(in.nextInt(),in.nextInt(),in.nextInt());
            }
            Arrays.sort(boards);
            System.out.println(min(0,true));            
        }
    }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 static int[][] p;
 static ri[] arr;
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int n=Integer.parseInt(in.readLine());
   while((n--)!=0)
   {
    int m=Integer.parseInt(in.readLine());
    p=new int[m][m];
    arr=new ri[m];
    String[] ss=in.readLine().split(" ");
    for(int i=0;i< m;i++)
        arr[i]=new ri(Integer.parseInt(ss[i]),i);
    
    int cnt=0;
    boolean bb=true;
    while(bb)
    {
        Arrays.sort(arr,cnt,m);
        int uu=arr[cnt].num;
        for(int i=0;i< arr[cnt].num;i++)
        {
            arr[cnt+1+i].num--;
            p[arr[cnt].n][arr[cnt+1+i].n]=1;
            p[arr[cnt+1+i].n][arr[cnt].n]=1;
            if(arr[cnt+1+i].num< 0)
            {
                bb=false;
                break;
            }
        }
        cnt++;
        if(cnt==m)break;
    }
    if(!bb)System.out.println("NO");
    else{
        System.out.println("YES");
        for(int i=0;i< m;i++)
        {
            for(int j=0;j< m;j++)
                System.out.print(p[i][j]+" ");
            System.out.println();
        }
    }
    System.out.println();
  }
 }
}
class ri implements Comparable< ri>
{
    int num;
    int n;
    public ri(int a,int b)
    {
        num=a;
        n=b;
    }
    @Override
    public int compareTo(ri arg0) {
        
        return arg0.num-num;
    }
}

							

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

//* @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();
    for(int i = 0; i < n; i++)
    {
          int one = in.nextInt();
      int two = in.nextInt();
      int three = in.nextInt();
      int four = in.nextInt();
      int d1 = two - one;
      int d2 = three - two;
      int d3 = four - three;
     if((d1 == d2)&&(d3 == d2))
      {
       int five = four + d1;
       System.out.println(one+" "+two+" "+three+" "+four+" "+five);
      }
     else
     {
      int five = four * (two/one);
      System.out.println(one+" "+two+" "+three+" "+four+" "+five);
    }
      }
   }
}


							

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

#include <stdio.h>
#include <math.h>
int main()
{
    int t;
    scanf("%d", &t);
 
    char c1, c2;
    int x1, y1, x2, y2;
    int w, h, c, x;
    while (t--)
    {
        getchar();
        scanf("%c%d %c%d", &c1, &y1, &c2, &y2);
        x1 = c1 - 'a' + 1;
        x2 = c2 - 'a' + 1;
 
        c1 = abs(x1 - x2);
        c2 = abs(y1 - y2);
 
        if (c1 + c2 == 0)
        {
            printf("0 0 0 0n");
        }
        else
        {
            if (c1 > c2) w = c1;
            else w = c2;
 
            if (c1 == c2 || x1 == x2 || y1 == y2) h = 1;
            else h = 2;
 
            if (x1 == x2 || y1 == y2) c = 1;
            else c = 2;
 
            if (c1 == c2) x = 1;
            else if ((c1 + c2) % 2 == 0) x = 2;
            else x = -1;
 
            printf("%d %d %d ", w, h, c);
            if (x >= 0)
            {
                printf("%dn", x);
            }
            else
            {
                printf("Infn");
            }
        }
    }
    //system("pause");
    return 0;
}
							

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

import java.util.Scanner;


public class Main {
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  int num = in.nextInt();
  int[][] grids = new int[101][101];
  for(int i = 0; i< num; i++)
   {
    String color = in.next();
    int x = in.nextInt();
    int y = in.nextInt();
    int l = in.nextInt();
    if(color.equals("BLACK"))
    {
        for(int j = x; j< x+l; j++)
        {
        for(int k = y; k< y+l; k++)
        {
            grids[j][k] = 1;
        }
    }
    }
    if(color.equals("WHITE"))
    {
        for(int j = x; j< x+l; j++)
        {
          for(int k = y; k< y+l; k++)
          {
            grids[j][k] = 0;
          }
        }
    }
    if(color.equals("TEST"))
    {
        int count = 0;
        for(int j = x; j< x+l; j++)
        {
            for(int k = y; k< y+l; k++)
            {
                if(grids[j][k] == 1)
                    count++;
            }
        }
        System.out.println(count);
    }
   }
  }
}    

							

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

#include<iostream>
using namespace std;
typedef struct edge
{int a;
struct edge *p;
}edge;
edge *a[21000];

int s[21000]; 
int b[21000];
int f[21000];
int fr[21000];
int go;

void find(int from,int to)
{edge *p;
p=a[to];fr[to]=from;
while(p)
{if(p->a==from){p=p->p;continue;}
 find(to,p->a);p=p->p;
}
f[go--]=to;
}





int main()
{int i,j,k,n,t,x,y,m,bl,an;edge *p;
cin>>t;
for(;t>0;t--)
{cin>>n;
for(i=1;i<=n;i++){a[i]=0;s[i]=-1;b[i]=-1;f[i]=-1;}
for(i=1;i<=n-1;i++){cin>>x>>y;p=new edge;p->a=y;p->p=a[x];a[x]=p;
p=new edge;p->a=x;p->p=a[y];a[y]=p;
}
an=n+1;
go=n;
find(0,1);
    
for(k=n;k>=1;k--)
{i=f[k];
    m=1;bl=0;
p=a[i];
while(p)
{if(p->a==fr[i]){p=p->p;continue;}
    if(bl<s[p->a])bl=s[p->a];
 m+=s[p->a];
 p=p->p;}

if(n-m>bl)bl=n-m;
b[i]=bl;
s[i]=m;
if(b[i]<=an){an=b[i];j=i;}
}

cout<<j<<' '<<an<<endl;
}
return 1;
}
							

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

/* @author: */
import java.util.*;
public class Main {
static long get_Area(long x1,long y1, long x2,long y2)
{
        return x1*y2-x2*y1;
}

public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
int move[][]={{0,0},{1,-1},{1,0},{1,1},{0,-1},{0,0},{0,1},{-1,-1},{-1,0},{-1,1}};

    int d,ncase;
    long x0,y0,newx,newy,area; 
    ncase=sc.nextInt();
    String  ss;
    while((ncase--)!=0)
    {
       ss=sc.next();
       
        x0=y0=area=0;
        for(int i=0;i<=ss.length()-1;i++)
        {
            d=ss.charAt(i)-'0';
            newx=x0+move[d][0];
            newy=y0+move[d][1];
            area+=get_Area(x0,y0,newx,newy);      
            x0=newx;
            y0=newy;
        }
        if(area< 0)
           area*=-1;
        if(area%2!=0)
           System.out.printf("%d.5n",area/2);
        else
           System.out.printf("%dn",area/2); 
    }
   }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    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());
     int[] arr=new int[a];
     String[] ss=in.readLine().split(" ");
     for(int i=0;i< a;i++)
        arr[i]=Integer.parseInt(ss[i]);
     int[][] gra=new int[a][a];
     for(int i=2;i< a;i++)
     {
      for(int j=0;j+i< a;j++)
       {
        int min=999999999,u=-1;
        for(int k=j+1;k< j+i;k++)
        {
           u=gra[j][k]+gra[k][j+i]+arr[j]*arr[k]*arr[j+i];
           if(min>u) min=u;
        }
        gra[j][j+i]=min;
        }
      }
      System.out.println(gra[0][a-1]);
    }
}
							

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

/* @author: */
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  double a;
  int d;
  a=sc.nextDouble();
  d=sc.nextInt();
    
  double ans;
  double min=a;
  int v1=0,v2=0,m=1,n=1;
  while(m<=d&&n<=d)
  {
    ans=m*1.0/n*1.0;
    if(ans>=a)
    {
    if(min>ans-a)
    {
      min=ans-a;
      v1=m;
      v2=n;
    }
    n++;
     }
     else if(ans< a)
     {
    if(min>a-ans)
    {
      min=a-ans;
      v1=m;
      v2=n;
    }
    m++;
     }
   }
   System.out.printf("%d %d",v1,v2);
  }
}
							

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

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


#define INF 30000
#define NMAX 13
float N,E,W;
double gety(double x)
{
    return (E-W)/N*x+W;
}
void solve()
{
    int i,j;
    int sum=0;
    double(y);
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            for(int p=0;p<2;p++)
            {
                y=gety(i+p);
                if(y>=j&&y<=j+1)
                {
                    sum++;
                    break;
                }
            }
        }
    }
    printf("%d",sum);
}
int main()
{

#if _DEBUG    
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%f%f%f",&N,&E,&W);
    E=E/100;
    W=W/100;
    solve();
#if _DEBUG
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
							

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

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

public class Main {
  private static class UFSets {
   UFSets(int l) {
    s = new int[l];
    for(int i=0; i!=l; ++i)
        s[i] = i;
  }
  void union(int x, int y) {
    s[find(x)] = s[find(y)];
  }

  int find(int x) {
    if(x>=s.length) while(true) ;
    if(s[x]!=x) return s[x] = find(s[x]);
    return x;
  }

  private int[] s;
}

private static class Node extends LinkedBlockingDeque< Edge>{
  private static final long serialVersionUID = 1L;
  void updatePath(Integer path) {
    if(this.path == null || this.path.compareTo(path) > 0) 
        this.path = path;
  }
  static Node getNearestNodeFrom(Node e) {
    ++cnt;
    return e.getNearesNode();
 }

  private Node getNearesNode() {
    if(lab==cnt) return this;
    lab = cnt;
    Node ans = this;
    for(Edge e: this) {
          Node another = e.target(this).getNearesNode();
      if(another.path == null) continue;
      if(ans.path == null || ans.path.compareTo(another.path)>0) ans = another;
    }
    return ans;
 }
 void update() {
    lab = ++cnt;
    cut = null;
    ans += path;
    for(Edge e: this)
        e.target(this).update(e);
  }

  private void update(Edge edge) {
    if(lab==cnt) return;
    cut = edge;
    lab = cnt;
    for(Edge e: this)
    {
        Node v = e.target(this);
        if(e.compareTo(edge)>0) v.update(e);
        else v.update(edge);
    }
  }

  static int cnt = 0;
    int lab = 0;
    Integer path = null;
    Edge cut;
 }

  private static class Edge implements Comparable< Edge>{
    public int compareTo(Edge e) {
        return this.l-e.l;
    }
    Edge(int cx, int cy, Node x, Node y, int l) {
        this.cx = cx;
        this.cy = cy;
        this.x = x;
        this.y = y;
        this.l = l;
    }
    void activate() {
        x.addFirst(this);
        ix = x.iterator();
        ix.next();
        y.addFirst(this);
        iy = y.iterator();
        iy.next();
        ans += l;
    }
    void disable() {
        ix.remove();
        iy.remove();
        ans -= l;
    }
    Node target(Node v) {
        if(x==v) return y;
        return x;
    }
    final Node x, y;
    Iterator< Edge> ix, iy;
    final int cx, cy, l;
  }
  
  private static final Scanner in = new Scanner(System.in);
  private static final Formatter out = new Formatter(System.out);
  private static final int m = in.nextInt();
  private static List< Node> nodes = new ArrayList< Node>();
  private static List< Edge> edges = new ArrayList< Edge>();
  private static int ans = 0;
  static Map< String, Integer> hash = new HashMap< String, Integer>();
  static {
    nodes.add(new Node());
    hash.put("Park", 0);
  }


  static int getHash(String s) {
    if(!hash.containsKey(s)) {
        hash.put(s, hash.size());
        nodes.add(new Node());
    }
    return hash.get(s);
  }

 public static void main(String[] args) {
    for(int i=0; i!=m; ++i) {
        int x = getHash(in.next());
        int y = getHash(in.next());
        int l = in.nextInt();
        if(y==0) {
            if(x==0) continue;
            y = x;
            x = 0;
        }
        if(x==0) nodes.get(y).updatePath(l);
        else edges.add(new Edge(x, y, nodes.get(x), nodes.get(y), l));
    }
    Collections.sort(edges);
    UFSets s = new UFSets(nodes.size());
    for(Edge e: edges) {
        if(s.find(e.cx)==s.find(e.cy)) continue;
        e.activate();
        s.union(e.cx, e.cy);
    }
    int degree = in.nextInt();
    for(int i=1; i!=nodes.size(); ++i) {
        if(s.find(i)!=i) continue;
        Node v = Node.getNearestNodeFrom(nodes.get(i));
        v.update();
        --degree;
    }
    while(degree-->0) {
        Node v = null;
        for(Node cand: nodes) {
                  if(cand.path == null) continue;
          if(cand.cut == null) continue;
          if(v == null || cand.path - cand.cut.l < v.path - v.cut.l) v = cand;
        }
        if(v==null || v.path - v.cut.l >= 0) break;
        v.cut.disable();
        v.update();
    }
    out.format("Total miles driven: %dn", ans);
  }
}

							

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

//* @author 
import java.util.*; 
import java.util.concurrent.ArrayBlockingQueue; 


public class Main { 
    static int N = 205; 
    static int [] degin, degout, deg, pre; 
    static int [][] cap; 

    private static int maxflow(int s, int t, int size) { 
        Queue<Integer> que = new ArrayBlockingQueue<Integer>(N); 
        int flow = 0, i, ext; 

        while(true) { 
            for(i = 0;i < size;++ i) 
                pre[i] = -1; 
            pre[s] = s; 
            que.clear(); 
            que.add(s); 
            while(!que.isEmpty()) { 
                int k = que.poll(); 
                for(i = 0;i < size;++ i) { 
                    if(pre[i] == -1 && cap[k][i] > 0) { 
                        pre[i] = k; 
                        if(i == t) break; 
                        que.add(i); 
                    } 
                } 
            } 

            if(pre[t] == -1) break; 

            ext = cap[pre[t]][t]; 
            for(i = t;i != s;i = pre[i]) { 
                if(ext > cap[pre[i]][i]) 
                    ext = cap[pre[i]][i]; 
            } 
            flow += ext; 
            for(i = t;i != s;i = pre[i]) { 
                cap[pre[i]][i] -= ext; 
                cap[i][pre[i]] += ext; 
            } 
        } 
        return flow; 
    } 

    public static void main(String [] args) { 
        Scanner cin = new Scanner(System.in); 
        int n, m, s, a, b, d, i, j, p; 
        degin = new int [N]; 
        degout = new int [N]; 
        deg = new int [N]; 
        pre = new int [N]; 
        cap = new int [N][N]; 

        n = cin.nextInt(); 
        while(n -- > 0) { 
            m = cin.nextInt(); 
            s = cin.nextInt(); 
            for(i = 0;i < m + 2;++ i) { 
                degin[i] = degout[i] = deg[i] = 0; 
                for(j = 0;j < m + 2;++ j) 
                    cap[i][j] = 0; 
            } 
            p = 0; 

            for(i = 0;i < s;++ i) { 
                a = cin.nextInt(); 
                b = cin.nextInt(); 
                d = cin.nextInt(); 
                if(d == 0) { 
                    deg[a]++; 
                    deg[b]++; 
                    cap[0][a]++; 
                    cap[a][b]++; 
                    ++p; 
                } 
                else { 
                    degout[a]++; 
                    degin[b]++; 
                } 
            } 

            Boolean flag = true; 
            for(i = 1;i <= m;++ i) { 
                int k = degin[i] + degout[i] + deg[i]; 
                if(k % 2 == 1 || k / 2 < degin[i] || k / 2 < degout[i]) { 
                    flag = false; 
                    break; 
                } 
                cap[i][m + 1] = k / 2 - degin[i]; 
            } 

            if(flag && maxflow(0, m + 1, m + 2) == p) 
                System.out.println("possible"); 
            else 
                System.out.println("impossible"); 
        } 
    } 
}


							

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

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

public class Main {

    BigInteger[][] dp = new BigInteger[51][51];

    BigInteger go(int n, int y) {
        if (y == 1)
            return BigInteger.ONE;
        if (n < y || y < 1)
            return BigInteger.ZERO;
        if(dp[n][y] != null) {
            return dp[n][y];
        }
        return (dp[n][y] =
            go(n-1, y).multiply(new BigInteger(""+y))
            .add(go(n-1, y-1).multiply(new BigInteger(""+(2*n-y)))));
    }

    void run() {
        Scanner cin = new Scanner(System.in);
        int ntc = cin.nextInt();

        for (int i = 0; i < ntc; ++i) {
            int n = cin.nextInt();
            int y = cin.nextInt();

            System.out.println(go(n, y));
        }
    }

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

    }

}

							

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

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

using namespace std;

int a[40000], n;
int ans[40000];
int id[40000], m;

bool cmp( int s1,int s2 )
{
    return a[s1] < a[s2];
}

int main()
{
    int i, j, s;
    int cas;

    scanf( "%d", &cas );
    while( cas-- )
    {
        scanf( "%d", &n );
        for( i=0; i<n; i++ )
            scanf( "%d", &a[i] );

        ans[0] = 1; id[0] = 0;
        for( i=1, m=1; i<n; i++ )
        {
            if( a[ id[m-1] ] < a[i] )
            {
                id[m] = i;
                ans[i] = ans[ id[m-1] ] + 1;
                m++;
            }
            else
            {
                j = lower_bound( id, id+m, i, cmp ) - id;
                ans[i] = ans[ id[j] ];
                id[j] = i;
            }
        }

        printf( "%dn", ans[ id[m-1] ] );
    }

    return 0;
}



							

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

#include<iostream>
using namespace std;
struct point
{int x,y;};

long cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
long dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)+(c.y-a.y);}


point p[10000];
int n,k[32],begin[32],end[32],m;

void init()
{int i,h=0;char c;
cin>>n;

for(i=0;i<=n;i++)
{begin[i]=h;
while(cin.peek()!='#')
{cin>>p[h].x>>c;
cin>>p[h++].y>>c;

}
cin.get();
end[i]=h;
}

m=h;
}

int side(int a,int b,int s,int key,int sign)
{int i,r;
for(i=begin[s];i<end[s];i++)
if(i!=a&&i!=b)
{r=cheng(p[i],p[a],p[b]);
if(r==0){if(dcheng(p[i],p[a],p[b])<0)return 0;
         if(a<end[0]&&p[i].x==p[a].x&&p[i].y==p[a].y)return 0;
         if(b<end[0]&&p[i].x==p[b].x&&p[i].y==p[b].y)return 0;
        if(a<end[0]&&b>end[0]&&dcheng(p[a],p[i],p[b])<0)return 0;
        if(b<end[0]&&a>end[0]&&dcheng(p[b],p[i],p[a])<0)return 0;
        if(dcheng(p[a],p[i],p[b])*sign>0)return 0;
        }
else if(r*key>0)return 0;
}

return 1;
}





int main()
{long key;int k,h,best,r,sign,s;
init();
int i,j;
best=0;
if(m==2){cout<<1<<endl;return 0;}

for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
if(p[i].x!=p[j].x||p[i].y!=p[j].y)
{
sign=0;
key=0;

for(k=0;k<end[0];k++)
if(k!=i&&k!=j)
    {r=cheng(p[k],p[i],p[j]);
    if(r==0){if(dcheng(p[k],p[i],p[j])<=0)break;
            s=dcheng(p[i],p[k],p[j]);
            if(!sign)sign=s;
            else if(sign*s<0)break;
            }
    else {if(!key)key=r;
        else if(key*r<0)break;
        }
    }

if(k<end[0])continue;

h=0;
if(key)for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);
else {key=-1;for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);
    if(h>best)best=h;h=0;    
        key=1;for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);}
if(h>best)best=h;
}


cout<<best<<endl;
return 0;
}
							

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

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

__int64 p[210],q[210];

inline int geti( char c )
{
    if( c <= 'Z' && c >= 'A' ) return c - 'A' + 26;
    else return c - 'a';
}
int n, m;

void print( __int64 b )
{
    int i;
    
    for( i=0; i<26; i++ )
    if( b & ((__int64)1<<i) ) printf( "%c", 'a'+i );
    
    for( i=26; i<52; i++ )
    if( b & ((__int64)1<<i) ) printf( "%c", 'A'+(i-26) );

    printf( "n" );
}



void init()
{
    int i, j;
    char w1[200],w2[200];

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

    for( i=0; i<n; i++ )
    {
        scanf( "%s%*s%s", w1, w2 );
        p[i] = 0, q[i] = 0;
        
        for( j=0; w1[j]; j++ )
            p[i] |= ( (__int64)1 << geti( w1[j] ) );
        
        for( j=0; w2[j]; j++ )
            q[i] |= ( (__int64)1 << geti( w2[j] ) );

    }

}

__int64 b;


void doit()
{
    int s, i, j;
    bool key;
    char w[200];

    scanf( "%s", w );
    b = 0;
    for( j=0; w[j]; j++ )
    b |= ( (__int64)1 << geti( w[j] ) );

    for( key=true,s=n; key; )
    {
        key = false;
        
        for( i=0; i<s; i++ )
        {
            if( ( b | q[i] ) == b )
            {
                s--;
                swap( q[i], q[s] );
                swap( p[i], p[s] );
                i--;
                continue;
            }

            if( ( b | p[i] ) == b )
            {
                b |= q[i];
                key = true;
                break;
            }
        }
    }
    
    print( b );
}

int main()
{
    init();
    while( m-- )
        doit();

    return 0;
}


							

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

/* @author:����acmilan_fan@yahoo.cn */
import java.io.*;
import java.util.*;
public class Main {
    
 public static void main(String[] args)throws IOException{
       
  BufferedReader br = new BufferedReader(new
                InputStreamReader(System.in));
  String s;
  String ciphertext;
  int codesize;
  int textrow;
  int colnum;
  StringBuilder sb;
  while((s=br.readLine())!=null&&!s.equals("THEEND")){
            
    //length of the code
    codesize = s.length();
    char[] code = compile(s);
    ciphertext = br.readLine();
    //rows of the text
    textrow = ciphertext.length()/codesize;
    sb = new StringBuilder(ciphertext);
    for(int i=0;i< codesize;i++){
      colnum = code[i]-'0';
      for(int j=0;j< textrow;j++){
         sb.setCharAt(j*codesize+colnum, ciphertext.charAt(i*textrow+j));
      }
    }
    System.out.println(sb.toString());
  }
  br.close();
 }
    
 static char[] compile(String code){
        
  char[] array = code.toCharArray();
  StringBuilder sb = new StringBuilder(array.length);
  for(char c='A';c<='Z';c++){
   for(int i=0;i< array.length;i++){
     if(c==array[i]){
         sb.append(i);
     }
   }
 }
 return sb.toString().toCharArray();
}
}
							

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

#include"iostream"
#include"stdlib.h"
#include"memory.h"
//#include"time.h"
using namespace std;


long m[5][100],len[5],n,total,answer;


///////////////////////////
long cas;
///////////////////////////

void init()
{
    n=5;total=0;
    int i,j;
    for(i=0;i<n;i++)
    {
        len[i]=80;
        for(j=0;j<len[i];j++)
        {    
            m[i][j]=rand()%201-100;
            total+=m[i][j];
        }
    }
}


void init1()
{
    n=0;total=0;
    do
    {
        len[n]=0;
        do
        {
            cin>>m[n][len[n]++];
            total+=m[n][len[n]-1];
        }
        while(m[n][len[n]-1]!=9999&&m[n][len[n]-1]!=-9999);
    
        total-=m[n][len[n]-1];
        len[n]--;
        n++;
    }while(m[n-1][len[n-1]]!=-9999);

}

int a[5];long next;int prev[520];

void find(long sum,long max,int rest)
{
    int i;long sa,sb;
    
    if(answer>=0&&max>answer)return;

    if(rest==0)
    {
        answer=max;
        return;
    }

    for(i=0;i<n;i++)
    if(a[i]<len[i])
    {
        if(prev[rest]>=0&&prev[rest]!=i)
        {
            sa=m[prev[rest]][a[prev[rest]]-2];
            if(m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]]>0)sa+=m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]];

            sb=m[i][a[i]];
            if(m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2]>0)sb+=m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2];

            if(sa>sb)continue;
        }


        a[i]+=2;
        sum+=m[i][a[i]-2];
        prev[rest-2]=i;
        find(sum+m[i][a[i]-1],sum>max?sum:max,rest-2);
        sum-=m[i][a[i]-2];
        a[i]-=2;
    }
    return ;
}

void yasuo()
{
    int i,j,k;
    for(i=0;i<n;i++)
    {
        for(j=1,k=0;j<len[i];j++)
        {
            if(m[i][j]==0)continue;
            if((m[i][j]>=0&&m[i][k]>=0)||(m[i][j]<=0&&m[i][k]<=0))m[i][k]+=m[i][j];
            else 
            {
                k++;
                m[i][k]=m[i][j];
            }
        }
    
        len[i]=k+1;
        
        if(m[i][k]>0)m[i][len[i]++]=0;
        m[i][len[i]]=-9999;
    }
    return ;
}

int main()
{
    int t,i,st;long sum;
    cin>>t;
    while(t--)
    {
        init1();
        //init();

        yasuo();
    
        sum=0;st=0;
        for(i=0;i<n;i++)
        {
            a[i]=0;
            if(m[i][0]<=0)
            {
                a[i]++;
                sum+=m[i][0];
            }
            st+=len[i]-a[i];
        }
        answer=-1;prev[st]=-1;
        find(sum,0,st);
        
        cout<<answer<<endl;
    }
    return 0;
}



							

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

#include<iostream>
using namespace std;

int dis[50][50],n;

void init()
{
    char c;
    int i,j,k;
    
    cin>>n;


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            dis[i][j]=9999;
        dis[i][i]=0;
    }
    
    for(i=0;i<n;i++)
    {
        cin.get(c);
        while(cin.peek()!='n')
        {
            cin>>j;
            
            dis[i][j-1]=1;
            dis[j-1][i]=1;
        }
        
    }
    
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    if(dis[i][k]<9999&&dis[k][j]<9999&&dis[i][k]+dis[k][j]<dis[i][j])
        dis[i][j]=dis[i][k]+dis[k][j];

}

void doit()
{
    int m,v[100],i,j,d,k;
    bool sign[100];
    char c;

    cin>>m;

    while(m--)
    {
        for(i=0;i<n;i++)
            sign[i]=0;
        
        i=0;
        if(cin.peek()=='n')
            cin.get(c);
        while(cin.peek()!='n')
        {
            cin>>v[i];
            if(cin.fail())break;
            v[i]--;
            
            if(v[i]<n&&sign[v[i]]==0)
            {
                sign[v[i]]=1;
                i++;
            }
            
        }
        d=i;



        for(i=0;i<n;i++)
        {
            for(j=0;j<d&&sign[i]==0;j++)
            for(k=0;k<d;k++)
                if(dis[v[j]][i]+dis[i][v[k]]==dis[v[j]][v[k]]&&dis[v[j]][v[k]]<9999)
                {
                    sign[i]=1;
                    break;
                }
        }

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

        if(i>=n)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    
}

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

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

import java.util.Arrays;   
import java.util.Scanner;   
  
public class Main {   
    static int[] student;   
    static int[] ans;   
  
    public static void main(String[] args) {   
        Scanner sc = new Scanner(System.in);   
        while (sc.hasNext()) {   
            int n = sc.nextInt();   
            int m = sc.nextInt();   
  
            if (n == 0 && m == 0)   
                break;   
            student = new int[n];   
  
            ans = new int[n];   
            Arrays.fill(ans, 1);   
            for (int i = 0; i < n; ++i) {   
                student[i] = i;   
            }   
            for (int i = 0; i < m; ++i) {   
                int k = sc.nextInt();   
                int x = sc.nextInt();   
                for (int j = 0; j < k - 1; ++j) {   
                    int y = sc.nextInt();   
                    unin(x, y);   
                    // student[y] = x;   
                    // x = y;   
                }   
            }   
            System.out.println(ans[find(0)]);   
            // for (int i = 0; i < n; ++i)   
            // System.out.println(i + ":" + student[i]);   
        }   
    }   
  
    static void unin(int x, int y) {   
  
        int px = find(x);   
        int py = find(y);   
        if (px == py)   
            return;   
        else {   
            // System.out.println("py=" + py + ";px=" + px);   
            if (px > py) {   
                student[py] = px;   
                ans[px] = ans[px] + ans[py];   
                // System.out.println("ans["+px+"]="+ans[px]);   
            } else {   
                student[px] = py;   
                ans[py] = ans[px] + ans[py];   
                // System.out.println("ans["+py+"]="+ans[py]);   
            }   
        }   
    }   
  
    static int find(int x) {   
        // ans++;   
        int p = student[x];   
        // System.out.println("p=" + p);   
        if (p == x)   
            return p;   
        else  
            return find(p);   
    }   
}  


//4�ԣ�<a href="http://blog.csdn.net/lazy_p/archive/2010/06/12/5666596.aspx" target="_blank">http://blog.csdn.net/lazy_p/archive/2010/06/12/5666596.aspx</a>

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
 static final int N = 100+10;
 static int point[][] = new int[N][N],DP[][] = new int[N][N];
 static void init(){
    for(int i=0;i< N;++i) for(int j=0;j< N;++j) point[i][j] = 0;
}

 static int solve(){
    int i,j;
    for(i=0;i< N;++i) DP[0][i] = DP[i][0] = 0;
    for(i=1;i< N;++i) for(j=1;j< N;++j){
        DP[i][j] = Max(DP[i-1][j],DP[i][j-1])+point[i][j];
    }
    return DP[N-1][N-1];
  }

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

 public static void main(String[]args) throws Exception{
  int i,a,b,n;
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
    cin.nextToken();
    n = (int) cin.nval;
    if(n==0){
        System.out.println("*");
        break;
    }else{
        init();
        for(i=0;i< n;++i){
            cin.nextToken();
            a = (int) cin.nval;
            cin.nextToken();
            b = (int) cin.nval;
            ++point[a][b];
        }
        System.out.println(solve());
    }
  }
 }
}

							

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

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

public class Main{
 public static void main(String[] args) throws Exception{
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    System.out.printf("Cards  Overhangn");
    int n;
    double d;
    while (scanner.hasNext()){
        n=scanner.nextInt();
        d=0;
        for (int i=1;i<=n ;i++ ){
            d=d+1.0/(2*i);
        }
        System.out.printf("%5d  %8.3fn",n,d);
    }
 }
}


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] b2=new int[]{6,2,4,8};
  int[] b3=new int[]{1,3,9,7};
  int[] b7=new int[]{1,7,9,3};
  int[] b9=new int[]{1,9,1,9};
  while(in.hasNext())
  {
   int n=in.nextInt();
   int e,a2=0,a3=0,a5=0,a7=0,a9=0;
   e=n;while((e=e/2)!=0) a2+=e;
   e=n;while((e=e/5)!=0) a5+=e;
   a3=f(n,3);
   a7=f(n,7);
   a9=f(n,9);
   int ans=1;
   a2-=a5;
   if(a2!=0){
        a2=a2%4;
        ans*=b2[a2];
    }
    ans*=b3[a3%4];
    ans=ans%10;
    ans*=b7[a7%4];
    ans=ans%10;
    ans*=b9[a9%4];
    ans=ans%10;
    System.out.printf("%5d",n);
    System.out.println(" -> "+ans);
   }
}

    public static int f(int n,int a)
    {
        if(n==0) return 0;
        else return f(n/2,a)+g(n,a);
    }
    public static int g(int n,int a)
    {
        if(n==0) return 0;
        else if(n%10< a) return n/10+g(n/5,a);
        else return n/10+1+g(n/5,a);
    }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 static int[][] w=new int[21][21];
 static final int n=20;
 public static void main(String[] args)
 {
   Scanner in=new Scanner(System.in);
   int cnt=0;
   while(in.hasNext())
   {
    cnt++;
    for(int i=0;i< n;i++)
        for(int j=0;j< n;j++)
            w[i][j]=9999999;
    for(int i=0;i< n-1;i++)
    {
        int u=in.nextInt();
        for(int j=0;j< u;j++)
        {
            int v=in.nextInt();
            w[i][v-1]=w[v-1][i]=1;
        }
    }
    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.min(w[i][j], w[i][k]+w[k][j]);
    int c=in.nextInt();
    System.out.println("Test Set #"+cnt);
    while((c--)!=0)
    {
        int a1=in.nextInt();
        int a2=in.nextInt();
        System.out.println(a1+" to "+a2+": "+w[a1-1][a2-1]);
    }
    System.out.println();
  }
 }
}
							

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

//* @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)));
    String[] kws;
    String[] exs,exsk;
    int[] kn;
    String fl;
    int n,m,max;
    int index=1;
    while (scanner.hasNext()){
        fl=scanner.nextLine();
        String[] t=fl.split(" ");
        n=Integer.parseInt(t[0]);
        m=Integer.parseInt(t[1]);
        kws=new String[n];
        exsk=new String[m];
        exs=new String[m];
        kn=new int[m];
        for (int i=0;i < n ;i++ ){
            kws[i]=scanner.nextLine().toLowerCase();
        }
    for (int i=0;i< m ;i++ ){
        exsk[i]=scanner.nextLine();
        exs[i]=exsk[i].toLowerCase();
        String tmp="";
        for (int j=0;j< exs[i].length() ;j++ ){
        if (Character.isLetter(exs[i].charAt(j))){
            tmp=tmp+exs[i].charAt(j);
        }
        else{
            tmp=tmp+"#";
        }
    }
    exs[i]=tmp;
    for (int j=0;j< n ;j++ ){
        if (exs[i].indexOf("#"+kws[j]+"#")!=-1){
            kn[i]++;
        }
        else if (exs[i].indexOf(kws[j]+"#")==0){
            kn[i]++;
        }
    else if (exs[i].indexOf("#"+kws[j])+kws[j].length()+1==exs[i].length()){
            kn[i]++;
        }
    }
 }
    max=kn[0];
    for (int i=1;i< kn.length ;i++ ){
        if (kn[i]>max){
            max=kn[i];
    }
}
System.out.println("Excuse Set #"+index++);
  for (int i=0;i< m ;i++ ){
    if (kn[i]==max){
        System.out.println(exsk[i]);
    }
  }
            System.out.println();
        }
    }
}


							

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int s=0,m=0,ac=0;
        boolean[] bands;
        boolean flaj;
        while(scan.hasNext()){
            s=scan.nextInt();
            m=scan.nextInt();
            bands=new boolean[m+1];
            flaj=true;
            ac=0;
            for(int i=0;i< m;i++){
                if(bands[ac]){
                    flaj=false;
                    break;
                }
                bands[ac]=true;
                ac+=s;
                ac=ac%m;
            }
            ac=10-(s+"").length();
            for(int i=0;i< ac;i++)System.out.print(" ");
            System.out.print(s);
            ac=10-(m+"").length();
            for(int i=0;i< ac;i++)System.out.print(" ");
            if (flaj) System.out.print(m+"    Good Choicenn");
            else System.out.print(m+"    Bad Choicenn");
        }
    }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
   int[] arr=new int[]{
    1,2,3,5,7,11,13,17,19,23,29,31,37,41,
    43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
    109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,
    193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,
    277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,
    373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,
    461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,
    569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,
    653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,
    757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,
    859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,
    971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,
    1063,1069,1087,1091,1093,1097
    };
    Scanner in=new Scanner(System.in);
    while(in.hasNext())
    {
     int a=in.nextInt();
     int b=in.nextInt();
     System.out.print(a+" "+b+":");
     int max=184;
     int min=0;
     int mid=92;
     while(min< max)
      {
        mid=(max+min)/2;
        if(arr[mid]==a){
            min=mid+1;
            break;
        }
        if(arr[mid]>a)max=mid;
        else if(arr[mid]< a) min=mid+1;
       }
      if(min%2==1){
        mid=min/2-b+1;
        max=min/2+b-1;
        if(mid< 0) mid=0;
        if(max>min)max=min-1;
       }
       else{
        mid=min/2-b;
        max=min/2+b-1;
        if(mid< 0) mid=0;
        if(max>min) max=min-1;
      }
      for(int i=mid;i<=max;i++)
        System.out.print(" "+arr[i]);
      System.out.println();
      System.out.println();
    }
  }
}
							

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

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

public class Main{
 public static void main(String[] args){
  LinkedList< Integer> list;
  Scanner in = new Scanner(System.in);
  int n;
  int left;
  int i, j;
  int count = 1;
  while(in.hasNext()){
    n = in.nextInt();
   left = in.nextInt();
   list = new LinkedList< Integer>();
   BinarySearchTreeWithRank bt = new BinarySearchTreeWithRank();
   for(i = 1; i <= n; i++){
    bt.insert(i);
   }
   for(i = 0; i < 20; i++){
    list.addLast(in.nextInt());
   }
   j = 0;
   //bt.inorder(bt.root);
   //System.out.println();
   while(j < list.size()){
     int cut = list.get(j);
     int p = cut, q = 0;
     int size0 = bt.size;
     while(p <= size0){
    if(bt.findKth(p-q) != -1){
      bt.remove(bt.findKth(p-q));
      q++;
    }
    //System.out.println(p +" : " + bt.size + " : " + q);
    p += cut;
    if(bt.size == left){
       break;
    }
    //bt.inorder(bt.root);
    //System.out.println();
    }
    if(bt.size == left){
    break;
    }
    j++;
  }
  System.out.println("Selection #" + count++);
  for(i = 1; i < left; i++){
    System.out.print(bt.findKth(i) + " ");
  }
  System.out.println(bt.findKth(left));
    System.out.println();
 }
}
}

class BinarySearchTreeWithRank{
    
  BinaryNodeWithRank root;
  int size;
    
  class BinaryNodeWithRank{
    int v;
    BinaryNodeWithRank left, right;
    int rank;
    int height;
  }
    
  public BinaryNodeWithRank insert(int v, BinaryNodeWithRank t){
    if(t == null){
         t = new BinaryNodeWithRank();
      t.v = v;
      t.rank = 1;
      return t;
    }
    if(v < t.v){
      t.left = insert(v, t.left);
      t.rank ++;
            
      if(height(t.left) - height(t.right) == 2){
        if(v < t.left.v){
            t =  rotateWithLeftChild(t);
        }
        else{
            t = doubleWithLeftChild(t);
        }
      }
    }
    else if(v > t.v){
        t.right = insert(v, t.right);
        if(height(t.right) - height(t.left) == 2){
            if(v > t.right.v){
                t = rotateWithRightChild(t);
            }
            else{
                t = doubleWithRightChild(t);
            }
        }
     }
    t.height = Math.max(height(t.left), height(t.right)) + 1;
    return t;
    }
    
    private int height(BinaryNodeWithRank t){
        return t == null ? -1 : t.height;
    }
    
    public void insert(int v){
        root = insert(v, root);
        size++;
    }
    public void remove(int v){
        root = remove(v, root);
        size--;
    }
    public int findKth(int k){
        return findKth(k, root);
    }
    public int findKth(int k, BinaryNodeWithRank t){
        if(t == null){
            return -1;
        }
        if(t.rank < k){
            return findKth(k - t.rank, t.right);
        }
        else if(t.rank > k){
            return findKth(k, t.left);
        }
        else{
            return t.v;
        }
    }
    
    public BinaryNodeWithRank remove(int v, BinaryNodeWithRank t){
        if(v < t.v){
            t.left = remove(v, t.left);
            t.rank--;
        }
        else if(v > t.v){
            t.right = remove(v, t.right);
        }
        else if(t.left != null && t.right != null){
            t.v = findMin(t.right).v;
            t.right = removeMin( t.right );
        }
        else{
            return (t.left == null ? t.right : t.left);
        }
        return t;
    }
    
    private BinaryNodeWithRank removeMin(BinaryNodeWithRank tt){
        BinaryNodeWithRank t = tt;
        if( t.left == null )
            return t.right;
            
        t.left = removeMin( t.left );
        t.rank--;
        return t;
    }
    
    public BinaryNodeWithRank findMin(BinaryNodeWithRank t){
        while(t.left != null){
            t = t.left;
        }
        return t;
    }
    public void inorder(BinaryNodeWithRank t){
        if(t != null){
            inorder(t.left);
            System.out.print(t.v +" ");
            inorder(t.right);
        }
    }
    
    private BinaryNodeWithRank rotateWithLeftChild(BinaryNodeWithRank k2){
        BinaryNodeWithRank k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height) + 1;
        if(k2.left == null){
            k2.rank = 1;
        }
        else{
            k2.rank = k2.left.rank + 1;
        }
        return k1;
    }
    private BinaryNodeWithRank rotateWithRightChild(BinaryNodeWithRank k2){
        BinaryNodeWithRank k1 = k2.right;
        k2.right = k1.left;
        k1.left  = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.right), k2.height) + 1;
        k1.rank += k2.rank;
        return k1;
    }
    private BinaryNodeWithRank doubleWithLeftChild(BinaryNodeWithRank k3){
        k3.left = rotateWithRightChild(k3.left);
        
        return rotateWithLeftChild(k3);
    }
    private BinaryNodeWithRank doubleWithRightChild(BinaryNodeWithRank k3){
        k3.right = rotateWithLeftChild(k3.right);
        
        return rotateWithRightChild(k3);
    }
}


							

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

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

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
    Map<Character,Character> map = new HashMap<Character,Character>();
    map.put('A','A');
    map.put('E','3');
    map.put('H','H');
    map.put('I','I');
    map.put('J','L');
    map.put('L','J');
    map.put('M','M');
    map.put('O','O');
    map.put('S','2');
    map.put('T','T');
    map.put('U','U');
    map.put('V','V');
    map.put('W','W');
    map.put('X','X');
    map.put('Y','Y');
    map.put('Z','5');
    map.put('1','1');
    map.put('2','S');
    map.put('3','E');
    map.put('5','Z');
    map.put('8','8');
        while(sc.hasNext())
    {
        String original = sc.next();
        boolean isPalindrome = true;
        boolean isMirrored = true;
        int len = original.length();
        for(int i = 0; i < len/2; i++)
        {
            if(original.charAt(i) != original.charAt(len - i - 1))
        {
            isPalindrome = false;
            break;
        }
        }
        for(int i = 0; i <= len/2; i++)
        {
            Character mirror = map.get(map.get(original.charAt(len - i -1)));
            if(mirror == null || original.charAt(i) != map.get(mirror).charValue())
        {
            isMirrored =false;
            break;
        }
        }
        System.out.print(original + " -- is ");
        if(isPalindrome && isMirrored)
        {
            System.out.println("a mirrored palindrome.");
        }else if(isPalindrome)
        {
            System.out.println("a regular palindrome.");
        }else if(isMirrored)
        {
            System.out.println("a mirrored string.");
        }else
        {
            System.out.println("not a palindrome.");
        }
        System.out.println();
    }
    }
}

							

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

//* @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 n=new Integer(stdin.readLine());
    String nombre="",winner="";
    int sub,pena,solved,time;
    int maxsolved=0,mintime=0;
        
    StringTokenizer tokens;
    for(int i=0;i< n;i++){
        tokens=new StringTokenizer(stdin.readLine());
        nombre=tokens.nextToken();
        solved=0;
        time=0;
        for(int j=0;j< 4;j++){
            sub=new Integer(tokens.nextToken());
            pena=new Integer(tokens.nextToken());
            if(pena!=0){
                solved++;            
                time+=(sub-1)*20+pena;
            }
        }
        if(solved>maxsolved||(solved==maxsolved&&time< mintime)||i==0){
            winner=nombre;
            maxsolved=solved;
            mintime=time;
        }
    }
    System.out.println(winner+" "+maxsolved+" "+mintime);
   }
}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
  {
   Scanner in=new Scanner(System.in);
   while(true)
    {
    String s1=in.next();
    if(s1.equals("-1"))break;
    String s2=in.next();
    int max=0;
    for(int i=0;i< s1.length();i++)
    {
      int count =0;
      for(int j=0;j< s2.length();j++)
       {
        boolean bb=true;
        if(i+j>=s1.length())
        {
            bb=false;
            break;
        }
        if(!bb)break;
        if(s1.charAt(i+j)==s2.charAt(j))count++;
        }
       if(count>max)max=count;
    }
    for(int i=0;i< s2.length();i++)
    {
    int count =0;
    for(int j=0;j< s1.length();j++)
     {
        boolean bb=true;
        if(i+j>=s2.length())
        {
            bb=false;
            break;
        }
        if(!bb)break;
        if(s2.charAt(i+j)==s1.charAt(j))count++;
     }
    if(count>max)max=count;
        }
    int total=s1.length()+s2.length();
    int sum=max*2;
    System.out.print("appx("+s1+","+s2+") = ");
    if(sum==0)System.out.println(0);
    else if(sum==total)System.out.println(1);
    else 
    {
      while(true)
       {
        boolean bb=false;
        for(int i=2;i<=sum;i++)
        {
              if(sum%i==0&&total%i==0)
            {
            sum/=i;
            total/=i;
            bb=true;
             }
        }
        if(!bb)break;
        }
       System.out.println(sum+"/"+total);
    }
            
   }
 }
}
							

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

//* @author: SmilingWang
import java.util.*;
public class Main {
  public static void main(String[] args){
   Scanner in =new Scanner(System.in);
   BinarySearchTree< Character> bt = new BinarySearchTree< Character>();
   boolean stop = false;
   while(true){
    String input = in.next();
            
    LinkedList< String> list = new LinkedList< String>();
    while(input.charAt(0) != '*'){
    if(input.charAt(0) == '$'){
      stop = true;
      break;
    }
    list.addFirst(input);
       input = in.next();
    }
            
    for(int i = 0; i < list.size(); i++){
      input = list.get(i);
      for(int j = 0; j < input.length(); j++){
       bt.insert((Character)input.charAt(j));
      }
    }
    bt.printTree();
    if(stop){
       return;
    }
    System.out.println();
    bt = new BinarySearchTree< Character>();
    }
  }
    
}

class BinaryNode< T extends Comparable< ? super T>> {
    BinaryNode< T> left;
    BinaryNode< T> right;
    T element;
    
    public BinaryNode(T theElement){
        this(theElement, null, null);
    }
    public BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt){
        element = theElement;
        left = lt;
        right = rt;
    }
    public T getElement(){
        return this.element;
    }
    public BinaryNode< T> getLeft(){
        return this.left;
    }
    public BinaryNode< T> getRight(){
        return this.right;
    }
    public String toString(){
        return element + "";
    }
}

class BinarySearchTree< T extends Comparable< ? super T>>{
    private BinaryNode< T> root;

    public BinarySearchTree(){
        root = null;
    }
    public BinarySearchTree(BinaryNode< T> t){
        root = t;
    }
    public void makeEmpty(){
        root = null;
    }
    public boolean isEmpty(){
        return root == null;
    }
    public T find(T x){
        return elementAt(find(x, root));
    }
    
    public void insert(T x){
        root = insert(x, root);
    }
    public void printTree(){
        printTree(root);
    }
    
    private T elementAt(BinaryNode< T> t){
        return t.element;
    }
    private BinaryNode< T> find(T x, BinaryNode< T> t){
        if(t == null){
            return null;
        }
        if(x.compareTo(t.element) < 0){
            return find(x, t.left);
        }
        else if(x.compareTo(t.element) == 0){
            return t;
        }
        else{
            return find(x, t.right);
        }
    }
    
    private BinaryNode< T> insert(T x, BinaryNode< T> t){
        if(t == null){
            t = new BinaryNode< T>(x, null, null);
        }
        else if(x.compareTo(t.element) < 0){
            t.left = insert(x, t.left);
        }
        else if(x.compareTo(t.element) > 0){
            t.right = insert(x, t.right);
        }
        else;
        return t;
    }
    private void printTree(BinaryNode< T> t){
        if(t != null){    
            System.out.print(t.element);
            printTree(t.left);
            printTree(t.right);
        }
    }
    
   
}


							

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

/* @author:����acmilan_fan@yahoo.cn */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
 public static void main(String[] args) throws Exception{
   BufferedReader br = new BufferedReader(new
               InputStreamReader(System.in));
   String s,board;
   String[] ss;
   int n;
   int[] p;
   boolean flag=false;
   while((s=br.readLine())!=null&&!s.startsWith("0")){
    ss=s.split(" ",3);
    p=new int[parseInt(ss[0])];
    for(int i=0;i< p.length;i++)
         p[i]=-1;
    n=parseInt(ss[2]);
    board=br.readLine();
    for(int i=0;i< n;i++){
      s=br.readLine();
      if(flag)continue;
      if(win(p,board,s,i)){
        flag=true;
        System.out.println("Player "+(i%p.length+1)+" won after "+(i+1)+" cards.");
      }
    }
    if(flag){
      flag=false;
    }else{
      System.out.println("No player won after "+n+" cards.");
       }
    }
    br.close();
   }


 static int parseInt(String s){
   int t = 0;
   for(char ch: s.toCharArray()){
      t *= 10;
      t += ch-'0';
   }
   return t;
 }

 static boolean win(int[] p,String board,String instruction,int n){
        
   int pos=n%p.length;
   char target=instruction.charAt(0);
   try {
    for(int i=0;i< instruction.length();i++){
     do{
           p[pos]++;
      }while(board.charAt(p[pos])!=target);
      } 
   }catch(StringIndexOutOfBoundsException e) {
    return true;
   }
   return p[pos]==board.length()-1;
  }
}

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[][] sorce;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
    String s=in.readLine();
    if(s.equals("end"))break;
    boolean bb=true,b1=false,b2;
    for(int i=0;i< s.length();i++)
    {
        if(isv(s.charAt(i)))
        {
              b1=true;
          break;
        }
    }
    if(!b1){
      System.out.println("<"+s+"> is not acceptable.");
      continue;
    }
    int cv=0,cf=0,mav=0,maf=0;
    for(int i=0;i< s.length();i++)
    {
       if(cv!=0||cf!=0){
        if(s.charAt(i)==s.charAt(i-1)&&s.charAt(i)!='e'&&s.charAt(i)!='o')
        {
                    mav=100;
            break;
            }
        }
        if(isv(s.charAt(i)))
        {
        cv++;
        if(maf< cf) maf=cf;
        cf=0;
         }
        else
        {
        cf++;
        if(mav< cv) mav=cv;
        cv=0;
        }
        if(cv>mav) mav=cv;
        if(cf>maf) maf=cf;
        if(mav>2||maf>2) break;
    }
    if(mav>2||maf>2)
    {
        System.out.println("<"+s+"> is not acceptable.");
        continue;
    }
    System.out.println("<"+s+"> is acceptable.");
   }
 }

  public static boolean isv(char c)
   {
    switch(c)
    {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
      return true;
    }
    return false;
   }
}


							

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

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

public class Main {
  private int x[];
  private int y[];
  private int z[];
  private int a[]=new int[7],b[]=new int[7],c[]=new int[7],ax[]=new int[7],use[]=new int[7];
  private int max;

 public Main(int x[],int y[],int z[]){
    this.x=x;
    this.y=y;
    this.z=z;
    max=0;
   for(int i = 0;i < 7;i ++) use[i] = 0;
  }

public int  dfs(int p){
for(int i = 1;i <= 6;i ++) //ÿ���������6�ַŷ�
{
   if(use[i]!=0) continue;//ǰ������ηŹ��λ�ò����ٷ�
   for(int j = 1;j <= 3;j ++)//ÿ��������ֿɽ�����ת
   {
    if(j == 1) {a[p] = x[i];b[p] = y[i];c[p] = z[i];}
    if(j == 2) {a[p]=y[i];b[p]=z[i];c[p] = x[i];}
    if(j == 3) {a[p] = z[i];b[p] = x[i];c[p] = y[i];}
    if(p != 1 && c[p] != b[p-1]) //���ܹؼ�,����߳����
     continue;
    if(p == 1)
     ax[p] = a[p];
    else
     ax[p] = ax[p-1] + a[p];
    use[i] = 1;
    if(p< 6)
     dfs(p + 1);
    else
    {
     if(b[p] == c[1]) // ͬ��,������׺���
     {
      if(max < ax[p]) 
       max = ax[p];//ȡ����ֵ
     }
    }
   }
   use[i] = 0;
}
 return max;
}

  public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   char ch;
   int x[]=new int[7],y[]=new int[7],z[]=new int[7];
   while(in.hasNext()){
   
   for(int i = 1;i <= 6;i ++) {
    x[i]=in.nextInt();
    y[i]=in.nextInt();
    z[i]=in.nextInt();
   }
    
    Main m=new Main(x,y,z);
   int max=m.dfs(1);
   if(max == 0)
    System.out.printf("nonen");
   else
    System.out.printf("%dn",max);
    ch=in.next().charAt(0);
   if(ch=='$')
       break;
  }
 }
}
							

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

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


public class Main
{
    public static int[] numbers = {5,7,5};
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        sc.useDelimiter("n");
        while(true)
        {
            String line = sc.next();
            line = line.trim();
            if(line.equals("e/o/i"))
            {
                break;
            }
            String[] parts = line.split("/");
            int i;
            for(i = 0; i < parts.length; i++)
            {
                String[] words = parts[i].split("\s+");
                int numOfSyllables = 0;
                for(String word : words)
                {
                    numOfSyllables += getNumOfSyllables(word);
                }
                if(numOfSyllables != numbers[i])
                {
                    break;
                }
            }
            if( i == parts.length)
            {
                System.out.println("Y");
            }else
            {
                System.out.println(i+1);
            }
        }
    }
    
    public static int getNumOfSyllables(String word)
    {
        boolean pre = false;
        int result = 0;
        for(int i = 0; i < word.length(); i++)
        {
            if(isSyllable(word.charAt(i)))
            {
                if(!pre)
                {
                    result++;
                    pre = true;
                }
            }else
            {
                pre = false;
            }
        }
        return result;
    }
    
    public static boolean isSyllable(char ch)
    {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o'
                || ch == 'u' || ch == 'y';
    }
}

							

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

/* @author: */
import java.util.Scanner;
public class Main{
  static int sum,n;
  static int arr[]=new int[20];
  static int j,FLAG;
  static boolean used[]=new boolean[20];

  static void f(int now,int total)
  {
   int i;
   if(total==sum)
   {
     FLAG=1;
     for(i=0;i< n;i++)
     if(used[i])
     {
    System.out.printf("%d",arr[i]);
      break;
      }
     for(i++;i< n;i++)
     {
    if(used[i])
      System.out.printf("+%d",arr[i]);
      }
      System.out.println("");
    return;
     }
     for(i=now;i< n;i++)
     {
    if(total+arr[i]>sum) continue;
    if(i>0&&arr[i]==arr[i-1]&&!used[i-1]) continue;
    used[i]=true;
    f(i+1,total+arr[i]);
    used[i]=false;
      }
   }
public static void main(String args[])
{
   Scanner sc=new Scanner(System.in);
   while(true)
   {
    sum=sc.nextInt();
    n=sc.nextInt();
   if(n==0) break;
    FLAG=0;
   for(j=0;j< n;j++)
     arr[j]=sc.nextInt();
   System.out.printf("Sums of %d:n",sum);
   f(0,0);
   if(FLAG==0) System.out.println("NONE");
   }
  }
}

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
   {
    Scanner in=new Scanner(System.in);
    while(true)
    {
    int a=in.nextInt();
    int b=in.nextInt();
    if(a==0&&b==0)break;
    int count=0;
    int[][] arr=new int[a+2][b+2];
    for(int i=1;i<=a;i++){
        String s=in.next();
        for(int j=1;j<=b;j++)
              arr[i][j]=s.charAt(j-1);
    }
    for(int i=1;i<=a;i++)
      for(int j=1;j<=b;j++)
        if(arr[i][j]==64){
            find(arr,i,j);
            count++;
        }
    System.out.println(count);
        }
                
     }
    
 public static void find(int[][] a,int i,int j)
  {
    a[i][j]=65;
    for(int k=i-1;k<=i+1;k++)
          for(int w=j-1;w<=j+1;w++)
        if(a[k][w]==64)find(a,k,w);
 }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
   while(in.hasNext())
   {
    StringBuffer bb=new StringBuffer();
    int[] a=new int[9];
    boolean b=true;
    for(int i=0;i< 9;i++)
        a[i]=in.nextInt();
    for(int i=0;i< 8;i++)
    {
     if(a[i]!=0)
     {
       if(b){
        if(a[i]< 0) bb.append("-");
        b=false;
      }
      else if(a[i]>0) bb.append(" + ");
      else if(a[i]< 0) bb.append(" - ");
      bb.append((Math.abs(a[i])==1?"":Math.abs(a[i]))+"x"+((8-i)==1?"":"^"+(8-i)));
     }
    }
    if(b)bb.append(a[8]);
    else if(a[8]>0)bb.append(" + "+Math.abs(a[8]));
    else if(a[8]< 0)bb.append(" - "+Math.abs(a[8]));
    System.out.println(bb);
      }
  }
}
							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        while(true)   
        {   
            String temp = cin.nextLine();   
            if(temp.equals("-1"))   
                break;   
            temp = temp.substring(0, temp.length()-1).trim();   
  
            int[] num = new int[15];   
            String[] str = temp.split(" ");   
            for(int i = 0; i < str.length; i++)   
                num[i] = Integer.valueOf(str[i]).intValue();   
           
            int result = 0;   
            for(int i = 0; i < str.length; i++)   
            {   
                for(int j = 0; j < str.length; j++)   
                    if(num[i] == num[j] * 2)   
                        result++;   
            }   
            System.out.println(result);   
        }   
  
    }   
  
}  


							

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

/* @author: */
import java.util.*;
public class Main {
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  int x[]=new int[1000], y[]=new int[1000];
  boolean sign[]=new boolean[1000];
  int a, b, n, m, i, ans;
  while( true )
  {
     n = 0;
     while( true )
     {
        x[n]=sc.nextInt();
        y[n]=sc.nextInt();
        if( x[n] < 0 && y[n] < 0 ) return ;
        if( x[n] == 0 && y[n] == 0 ) break;
        sign[n] = false;
        n++;
     }
                
     for( m=0, ans = 0; m< n; ans++ )
     {
        a = 0;
        b= 0;
        for( i=0; i< n; i++ )
          if( !sign[i] && x[i]>=a && y[i] >=b )
          {
            sign[i] = true;
            m++;
            a = x[i];
            b = y[i];
          }
   }
           
   System.out.printf( "%dn", ans );
  }
 }
}                

							

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

import java.util.*;   
  
class Clay   
{   
    private int l = 0;   
    private int w = 0;   
    private int h = 0;   
    private String name;   
    private int size = 0;   
       
    public Clay(String l, String w, String h, String name)   
    {   
        this.l = Integer.valueOf(l).intValue();   
        this.w = Integer.valueOf(w).intValue();   
        this.h = Integer.valueOf(h).intValue();   
        this.name = name;   
        this.size = this.l * this.w * this.h;   
    }   
       
    public int getSize()   
    {   
        return size;   
    }   
       
    public String getName()   
    {   
        return name;   
    }   
       
}   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        while(true)   
        {   
            int num = Integer.valueOf(cin.nextLine()).intValue();   
            if(num == -1)   
                break;   
               
            List list = new ArrayList();   
            for(int i = 0; i < num; i++)   
            {   
                String[] str = cin.nextLine().split(" ");   
                Clay clay = new Clay(str[0], str[1], str[2], str[3]);   
                list.add(clay);   
            }   
            Iterator iter = list.iterator();   
            int max = 0;   
            int min = 250;   
            String maxName = null;   
            String minName = null;   
            while(iter.hasNext())   
            {   
                Clay theone = (Clay)iter.next();   
                if(theone.getSize() > max)   
                {   
                    max = theone.getSize();   
                    maxName = theone.getName();   
                }   
                if(theone.getSize() < min)   
                {   
                    min = theone.getSize();   
                    minName = theone.getName();   
                }   
            }   
               
            System.out.println(maxName + " took clay from " + minName + ".");   
        }   
  
    }   
  
}  


							

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

import java.io.*;
import java.util.*;
import java.math.*;
/**
 *
 * @author gongshaoqing
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        // TODO code application logic here
        Scanner cin=new Scanner(System.in);
        String str;
        int inbas,oubas;
        while(cin.hasNext())
        {
            str=cin.next();
            inbas=cin.nextInt();
            oubas=cin.nextInt();
            BigInteger tmp=new BigInteger(str,inbas);
      
            str=tmp.toString(oubas);
            int len=str.length();
            if(len>7)System.out.println("  ERROR");
            else
            {
                str=str.toUpperCase(Locale.FRENCH);
                for(int i=0;i< 7-len;i++)System.out.print(" ");
                System.out.println(str);
            }
        }
    }

}
 


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
  {
   Scanner in=new Scanner(System.in);
   int a=in.nextInt();
   for(int i=6;i<=a;i++)
    {
     for(int j=2;j< a;j++)
    for(int m=j;m< a;m++)
     for(int n=m;n< a;n++)
      {
       if((n*n*n+m*m*m+j*j*j)==i*i*i)
        System.out.println("Cube = "+i+", Triple = ("+j+","+m+","+n+")");
      }
     }
  }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
  {
    Scanner in=new Scanner(System.in);
    System.out.println("PERFECTION OUTPUT");
    while(true)
    {
         int a=in.nextInt();
     if(a==0) break;
      double w=Math.sqrt(a);
      int total=1;
      for(int i=2;i< w;i++)
      {
        if(a%i==0) total+=(a/i+i);
      }
      if(a%w==0) total+=w;
      System.out.printf("%5d  ",a);
      if(a==1) System.out.println("DEFICIENT");
      else if(total>a) System.out.println("ABUNDANT");
      else if(total< a) System.out.println("DEFICIENT");
      else System.out.println("PERFECT");
    }
    System.out.println("END OF OUTPUT");
  }
}
							

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

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

public class Main{
 static Scanner cin;
 static int count=0;
 public static void main(String args[]){
  cin = new Scanner(System.in);
  int n;
  while((n=cin.nextInt())!=0)
   run(n);
  }
    
 static void run(int n){
   Point start,end;
   start = new Point(n, cin);
   end   = new Point(n, cin);
        
   ArrayList< PointSet> Mset = new ArrayList< PointSet>();
        
   PointSet startSet = new PointSet();
   PointSet endSet = new PointSet();
   startSet.add(start);
   endSet.add(end);
    
   Mset.add(startSet);
   Mset.add(endSet);
        
   Point A,B;
   PointSet setA=new PointSet(), setB=new PointSet();
   while(true){
    if(cin.hasNext("-1") == true){
     cin.nextInt();
     break;
    }
                
    setA = null;
    setB = null;
    A = new Point(n, cin);
    B = new Point(n, cin);
            
    for(PointSet set:Mset){
    if(set.contains(A))
      setA = set;
    if(set.contains(B))
      setB = set;
    }
            
   if((setA != null)&&(setB != null)){
    if(setA != setB){
    setA.addAll(setB);
    Mset.remove(setB);
    }    
   }
   else if(setA != null)
    setA.add(B);
   else if(setB != null)
    setB.add(A);
   else{
    setA = new PointSet();
    setA.add(A);
    setA.add(B);
    Mset.add(setA);
   }
                                        
 }
        
 startSet = null;
 endSet   = null;
 for(PointSet set:Mset){
  if(set.contains(start))
    startSet = set;
  if(set.contains(end))
    endSet = set;
  }
        
  if(startSet == endSet)
    System.out.println("Maze #"+(++count)+" can be travelled");
  else
    System.out.println("Maze #"+(++count)+" cannot be travelled");
 }
}

class Point implements Comparable{
 int num;
        
 public Point(int n, Scanner cin){
   num=0;
 for(int i=0;i< n;i++)
  num = 10*num+cin.nextInt();
}
    
 public int compareTo(Object another){
   Point p = (Point)another;
    
   return this.num-p.num;
 }
}

class PointSet extends TreeSet< Point>{
    
}
							

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

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

/**
 * Accepted.
 * 
 * 
 * @author hong
 * 
 */
public class Main {
 private static Node[] nodes = new Node[1000];
 private static boolean[] used = new boolean[1000];
 private static int count = 0;
 static int p = 0;

 private static int getIndex(char s) {
  for (int i = 0; i < p; i++) {
   if (nodes[i].c == s) {
    return i;
   }
  }

  return -1;
 }

 /**
     * Construct the Huffman Tree.
     * 
     * @return
     */
 private static void constructHuffmanTree() {

  for (int i = 0; i < p; i++) {
   used[i] = false;
  }

  while (true) {

   // first find the min occurence for unused node, there always be such one node.
   int min = Integer.MAX_VALUE;
   int min1_index = 0;

   for (int i = 0; i < p; i++) {
    if (!used[i] && nodes[i].occur < min) {
     min = nodes[i].occur;
     min1_index = i;
    }
   }

   // use the min1_index node.
   used[min1_index] = true;

   // try to find the second min node, if this node is not found, break the while.
   int min2 = Integer.MAX_VALUE;
   int min2_index = 0;

   for (int i = 0; i < p; i++) {
    if (!used[i] && nodes[i].occur < min2) {
     min2 = nodes[i].occur;
     min2_index = i;
    }
   }

   if (min2 == Integer.MAX_VALUE) {
    break;
   }

   used[min2_index] = true;

   // construct a new Node.
   Node newNode = new Node();
   newNode.occur = nodes[min1_index].occur + nodes[min2_index].occur;
   newNode.left = nodes[min1_index];
   newNode.right = nodes[min2_index];

   nodes[p] = newNode;
   used[p] = false;
   p++;
  }
 }

 private static void travTree(Node tree, int depth) {
  if (tree != null) {

   tree.depth = depth;

   if (tree.left == null && tree.right == null) {
    // find a leaf.
    count += tree.occur * depth;
   }

   if (tree.left != null) {
    travTree(tree.left, depth + 1);
   }

   if (tree.right != null) {

    travTree(tree.right, depth + 1);
   }
  }
 }

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

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

   if ("END".equals(line)) {
    break;
   }

   p = 0;

   for (int i = 0; i < line.length(); i++) {

    int index = getIndex(line.charAt(i));

    if (index == -1) {
     Node node = new Node(line.charAt(i));
     node.occur = 1;

     nodes[p] = node;
     p++;
    } else {
     nodes[index].occur++;
    }
   }

   constructHuffmanTree();

   int current = 8 * line.length();

   if (p == 1) {
    count = line.length();

    System.out.println(current + " " + count + " "
      + new BigDecimal(current * 1.0 / count).setScale(1, RoundingMode.HALF_UP));

   } else {

    count = 0;

    travTree(nodes[p - 1], 0);

    System.out.println(current + " " + count + " "
      + new BigDecimal(current * 1.0 / count).setScale(1, RoundingMode.HALF_UP));
   }

  }

 }

 static class Node {
  char c;
  int depth = 0;
  int occur;
  Node left = null;
  Node right = null;

  public Node(char c) {
   this.c = c;
  }

  public Node() {
  }

 }

}