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

/* @author: */
import java.util.Scanner;
public class Main {
 static final double EPS =1e-7;
 
  //����x*y �ܷ���� a*b ��
static  boolean canfit( double a, double b, double x, double y )
{
   double t;
   double l=Math.sqrt(x*x+y*y),ll=x*x+y*y;
   if(x*x+y*y - a*a-b*b > EPS)
    return false;
    
   if(x< y)
    {
    t=x;x=y;y=t;
    }
   if(a< b)
   {
    t=a;a=b;b=t;
   }
   if( x-b >EPS && y -b > EPS )return false;
    double s=(4*x*y*b+Math.sqrt(16*x*x*y*y*b*b-4*ll*(4*x*x*y*y-ll*ll+b*b*ll) ) )/ll/2;

   if(s-a > EPS)
    return false;
   else return true;
}

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    
    double a, b, c, d, e;
    a=sc.nextDouble();
    b=sc.nextDouble();
    c=sc.nextDouble();
    d=sc.nextDouble();
    e=sc.nextDouble();

    if( canfit( d, e, a, b ) || canfit( d, e, a, c ) || canfit( d, e, b, c ) )
    System.out.printf( "YESn" );
    else
    System.out.printf( "NOn" );
    
  }
}


							

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

//* @author: 
import java.util.*;
public class Main
{
 
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int m=sc.nextInt();
   int n=sc.nextInt();
   int k=sc.nextInt();
   node a[]=new node[k+1];
   for(int i=0;i<=k;i++)
     a[i]=new node();
    for (int i=1;i<=k;i++) {
        a[i].p=sc.nextDouble();
        a[i].pm=a[i-1].pm+a[i].p;
        a[i].pn=a[i-1].pn+a[i].p;
        if (i>m) a[i].pm-=a[i-m].p;
        if (i>n) a[i].pn-=a[i-n].p;
    }
    for (int i=n;i<=k;i++) {
        if (a[i].pm/m>a[i].pn/n&&(a[i-1].pm/m< a[i-1].pn/n||i==n)) 
          System.out.printf("BUY ON DAY %dn",i);
        else if (a[i].pm/m< a[i].pn/n&&(a[i-1].pm/m>a[i-1].pn/n||i==n))
          System.out.printf("SELL ON DAY %dn",i);
    }
  }
}

class node{
   double p;
   double pm;
   double pn;
 
   public node(){
   }
}
							

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

 import java.io.BufferedReader;
 import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;

 public class Main {

     public static void main(String[] args) throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String chips = null;
         String source;
         boolean flg;
         while ((chips = read.readLine()) != null) {
             source = read.readLine();
             flg = true;
             List<Integer> list1 = new ArrayList<Integer>();
             List<Integer> list2 = new ArrayList<Integer>();
             list1 = getDifferent(chips, list1);
             list2 = getDifferent(source, list2);
             if (list1.size() != list2.size()) {
                 flg = false;
             } else {
                 Collections.sort(list1);
                 Collections.sort(list2);
                 for (int i = 0; i < list1.size(); i++) {
                     if (list1.get(i) != list2.get(i)) {
                         flg = false;
                     }
                 }
             }
             if (flg) {
                 System.out.println("YES");
             } else {
                 System.out.println("NO");
             }
         }
     }

     public static List getDifferent(String s, List list) {
         char[] c = s.toCharArray();
         String used = "";
         int index = 0;
         for (int i = 0; i < c.length; i++) {
             if ((index = used.indexOf(c[i])) == -1) {
                 used += c[i];
                 list.add(1);
             } else {
                 list.set(index, (Integer) list.get(index) + 1);
             }
         }
         return list;
     } 
}

							

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

import java.util.Scanner;

public class Main {

    private static int[][] matrix = new int[1001][1001];
    private static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testNum = sc.nextInt();
        for (int i = 0; i < testNum; ++i) {
            matrix = new int[1001][1001];
            n = sc.nextInt();
            int t = sc.nextInt();
            for (int j = 0; j < t; ++j) {
                String c = sc.next();
                if (c.equals("C")) {
                    int x1 = sc.nextInt();
                    int y1 = sc.nextInt();
                    int x2 = sc.nextInt();
                    int y2 = sc.nextInt();
                    change(x1 , y1 , 1);
                    change(x1 , y2+1 , -1);
                    change(x2+1 , y2+1 , 1);    
                    change(x2+1 , y1 , -1);        
                } else if (c.equals("Q")) {
                    int x = sc.nextInt();
                    int y = sc.nextInt();
                    int v = getSum(x, y) & 1;
                    // System.out.println(getSum(x , y));
                    if (v == 0)
                        System.out.println(0);
                    if (v == 1)
                        System.out.println(1);
                }
            }
            System.out.println();
        }
    }

    public static void change(int x1, int y1, int x2, int y2) {

        for (int i = x1; i <= x2; ++i) {
            change(i, y1, 1);
            change(i, y2 + 1, -1);
        }
        // for (int i = x1; i <= x2; ++i) {
        // for (int j = y1; j <= y2; ++j) {
        //
        // if (matrix[i][j] == 0)
        // matrix[i][j] = 1;
        // else
        // matrix[i][j] = 0;
        // }
        // }
    }

    public static int lowbit(int i) {
        return i & -i;
    }

    public static void change(int i, int j, int value) {
        while (i <= n) {
            int temp = j;
            while (temp <= n) {
                matrix[i][temp] += value;
                temp += lowbit(temp);
            }
            i += lowbit(i);
        }
    }

    public static int getSum(int i, int j) {
        int sum = 0;
        while (i > 0) {
            int tmp = j;
            while (tmp > 0) {
                sum += matrix[i][tmp];
                tmp -= lowbit(tmp);
            }
            i -= lowbit(i);
        }
        return sum;
    }

}
							

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

//* @author: 82638882@163.com
import java.util.HashMap;
import java.util.Scanner;

public class Main
{    
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int n=in.nextInt();
  int[] arr=new int[n];
  HashMap< String,Integer> hs=new HashMap< String,Integer>();
  String s=in.nextLine();
  int tag=-1;
  for(int i=0;i< n;i++)
  {
    s=in.nextLine();
    s=s.trim();
    if(s.equals("Li Ming"))tag=i;
    hs.put(s, i);
   }
   int m=in.nextInt();
   for(int i=0;i< m;i++)
   {
    for(int j=0;j< n;j++)
    {
        int num=in.nextInt();
        s=in.nextLine();
        s=s.trim();
        int u=hs.get(s);
        arr[u]+=num;
    }
    int ww=arr[tag];
    int cnt=1;
    for(int j=0;j< n;j++)
        if(arr[j]>arr[tag])cnt++;
    System.out.println(cnt);
    }
        
  }
    
}


							

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

//* @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 code=scanner.nextLine();
        String sent=scanner.nextLine();
        String decode="";
        for (int i=0;i< sent.length() ;i++ ){
            decode=decode+getChar(sent.charAt(i),code);
        }
        System.out.print(decode);
    }

    public static char getChar(char c,String code){
        if (c-'a'< 26&&c-'a'>=0){
            return Character.toLowerCase(code.charAt(c-'a'));
        }
        else if (c-'A'< 26&&c-'A'>=0){
            return Character.toUpperCase(code.charAt(c-'A'));
        }
        else{
            return c;
        }
    }
}


							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        while(cin.hasNext())   
        {   
            int num = cin.nextInt();   
            int ways = 1;   
               
            int index = num/2+1;   
               
            for(int i = index; i > 1; i--)   
            {   
                int tmpNum = i;   
                for(int j = i - 1; j > 0; j--)   
                {   
                    tmpNum += j;   
                    if(tmpNum == num)   
                    {   
                        ways++;   
                        break;   
                    }else if(tmpNum > num)   
                        break;   
                }   
            }   
            System.out.println(ways);   
               
               
        }   
  
    }   
  
}  

							

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

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int D;
string ori;
string v[1005];
int l[1005];
int longgest;
bool visited[1005];
vector<string> vre;
void search(string &str,int z)
{
    bool Find = false;
    visited[z] = true;
    for(int i = 1;i <= D;i++)
    {
        if(l[i] == l[z] + 1)
        {
            string::size_type index = 0;
            bool lost = false;
            for(int j = 0;j < l[z];j++)
            {
                index = v[i].find(str[j],index);
                if(index == string::npos)
                {
                    lost = true;
                }
                index++;
            }
            if(!lost)
            {
                if(!visited[i])
                {
                    search(v[i],i);
                }
                Find = true;
            }
        }
    }
    if(!Find)
    {
        vre.push_back(str);
    }
}

int main()
{
    while(cin>>D)
    {
        cin>>v[0];
        l[0] = v[0].size();
        vre.clear();
        longgest = 0;
        memset(visited,0,sizeof(visited));
        for(int i = 1;i <= D;i++)
        {
            cin>>v[i];
            l[i] = v[i].size();
        }
        search(v[0],0);
        int length = 0;
        int pos = 0;
        for(int i = 0;i < vre.size();i++)
        {
            if(vre[i].size() > length)
            {
                length = vre[i].size();
                pos = i;
            }
        }
        //cout<<endl;
        cout<<vre[pos]<<endl;
    }
    return 0;
}


/*
Travel Games
Time Limit: 3000MS  Memory Limit: 65536K 
Total Submissions: 1850  Accepted: 647 

Description

The cows are taking a trip to the lakes in Minnesota. Like everyone else, they are bored and are playing "travel games" to pass the time away. 

In this travel game, the first cow thinks of a three letter word from the Sacred Travel Game Dictionary (STGD). The next cow in line must add a letter to the word (at the beginning, between two letters, or at the end) to make another word in the STGD. The cows are curious as to just how big the final word can be. 

Given a dictionary of D (1 <= D <= 1000) words and a starting word, find any of the longest possible words that can be formed playing this travel game. 

Input

* Line 1: The integer D followed by a space followed by a legal three letter word. 

* Line 2 through D+1: Each line contains a legal word no longer than 80 characters, consisting only of lowercase letters, from the STGD. 

Output

A single line with the longest word that can be formed by extending the input seed. 
The input ensure the correct result will be unique.
Sample Input

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

Sample Output

chorale

Hint

[From the sequence: cal, coal, coral, choral, chorale]
*/
							

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

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int map[2][50][202];
int len[202];
int N;
int S;
double calc(double x1,double y1,double x2,double y2)
{
    return sqrt((x1 - x2) * (x1 - x2)  +  (y1 - y2) * (y1 - y2));
}
double value[1000][1000];
bool visited[1000][1000];
double search(int i,int j)
{
    double min = 99999999999;
    double sum;
    if (j == N)
    {
        for (int z = 1;z <= len[1];z++)
        {
            double sum2 = calc(map[0][S][1],map[1][S][1],map[0][i][j],map[1][i][j]);

            if (sum2 < min)
                min = sum2;
        }
        return min;
    }
    for (int z = 1;z <= len[j + 1];z++)
    {
        visited[i][j] = true;
        double r = calc(map[0][i][j],map[1][i][j],map[0][z][j + 1],map[1][z][j + 1]);
        if (!visited[z][j + 1])
        {
            sum = search(z,j + 1);
        }
        else
        {
            sum = value[z][j + 1];
        }
        if (sum + r < min)
            min = sum + r;
    }
    value[i][j] = min;
    return min;
}
int main()
{
    while (cin>>N)
    {
        for (int i = 1;i <= N;i++)
        {
            cin>>len[i];
            for (int j = 1;j <= len[i];j++)
            {
                cin>>map[0][j][i]>>map[1][j][i];
            }
        }


        double min = 99999999999;
        for (int i = 1;i <= len[1];i++)
        {
            for (int i = 0;i < 50;i++)
            {
                for (int j = 0;j < 200;j++)
                {
                    value[i][j] = 0;
                    visited[i][j] = false;
                }
            }
            S = i;
            double v = search(i,1);
            if (v < min)
                min = v;
        }
        int res = min * 100;
        printf("%dn",res);
    }
    return 0;
}


/*
Cowties
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 1514  Accepted: 468 

Description

N cows (3 <= N <= 100) are eating grass in the middle of a field. So that they don't get lost, Farmer John wants to tie them together in a loop so that cow i is attached to cows i-1 and i+1. Note that cow N will be tied to cow 1 to complete the loop. 

Each cow has a number of grazing spots she likes and will only be happy if she ends up situated at one of these spots. Given that Farmer John must ensure the happiness of his cows when placing them, compute the shortest length of rope he needs to tie them all in a loop. It is possible for different parts of the loop to cross each other. 

Input

* Line 1: The integer N. 

* Lines 2..N+1: Each line describes one cow using several space-separated integers. The first integer is the number of locations S (1 <= S <= 40) which are preferred by that cow. This is followed by 2*S integers giving the (x,y) coordinates of these locations respectively. The coordinates lie in the range -100..100. 

Output

A single line containing a single integer, 100 times the minimum length of rope needed (do not perform special rounding for this result). 

Sample Input

4
1 0 0
2 1 0 2 0
3 -1 -1 1 1 2 2
2 0 1 0 2

Sample Output

400

Hint

[Cow 1 is located at (0,0); cow 2 at (1,0); cow 3 at (1,1); and cow 4 at (0,1).] 
*/
							

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

#include<iostream>
#include"stdio.h"
#include"vector"
using namespace std;
struct edge
{
    int from;
    int to;
    int len;
    int opp;
};

vector<edge> e[1010];
int from[1010],dis[1010],n,m;
bool sign[1010];
edge *along[1010];

void dijstra()
{
    int i,j,k,to;
    for(i=0;i<n;i++)
    {
        sign[i]=0;
        dis[i]=999999999;
    }

    sign[0]=0;
    from[0]=-1;
    dis[0]=0;

    for(;;)
    {
        k=-1;
        for(j=0;j<n;j++)
            if(!sign[j]&&(k<0||dis[j]<dis[k]))
                k=j;
        if(k<0)break;
        
        sign[k]=1;
        
        for(j=0;j<e[k].size();j++)
            if(dis[to=e[k][j].to]>dis[k]+e[k][j].len)
            {
                dis[to]=dis[k]+e[k][j].len;
                from[to]=k;
                sign[to]=0;
                along[to]=&e[k][j];
            }
    }
}

void init()
{
    int i,a,b,c;
    edge eg;
    scanf("%d %d",&n,&m);
    
    for(i=0;i<n;i++)
        e[i].clear();

    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        a--,b--;
        eg.len=c;
        
        eg.to=b;eg.from=a;
        e[a].push_back(eg);
        
        eg.to=a;eg.from=b;
        e[b].push_back(eg);

        e[a][e[a].size()-1].opp=e[b].size()-1;
        e[b][e[b].size()-1].opp=e[a].size()-1;
    }
}

int ans;
void doit()
{
    int i;
    dijstra();
    ans=dis[n-1];
        
    i=n-1;
    while(from[i]>=0)
    {
        e[i][along[i]->opp].len*=-1;
        along[i]->len=99999999;
        i=from[i];
    }
    dijstra();
    ans+=dis[n-1];
}

int main()
{
    init();
    doit();
    printf("%dn",ans);
    return 0;
}


							

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

#include<iostream>
using namespace std;

long a[140000],s[140000];

int main()
{
    long i,n,m,j;long result;
    long begin[200],st,k,ss;
    char c;
    while(1)
    {
    cin>>m>>n;
    if(cin.fail())break;
    
    long h;
    h=(1<<16);
    result=0;
    for(j=0;j<m;j++)
    {
        cin>>c;
        result*=2;
        result+=c-'0';
    }
            
            
    for(i=0;i<n;i++)
    {
        begin[i]=0;
        for(j=0;j<m;j++)
        {
            cin>>c;
            begin[i]*=2;
            begin[i]+=c-'0';
        }
        a[i]=begin[i];
    }
    for(i=0;i<h;i++)
    s[i]=-1;
    
    //for(i=0;i<n;i++)
    //s[begin[i]]=0;
    
    ss=0;k=0;
    for(st=n;st<h+n&&st!=k;)
    {
        k=st;
        for(i=ss;i<k;i++)
        for(j=0;j<n;j++)
        {    
            if(s[a[i]^begin[j]]<0)
            {
                s[a[i]^begin[j]]=(s[a[i]]>=0?s[a[i]]:0)+1;
                a[st++]=a[i]^begin[j];
            }
        }
        ss=k;
    }
    
    
    long best,bi,need;
    bi=-1;
    for(i=0;i<h;i++)
    if(s[i]>=0)
    {
        need=0;
        for(j=0;j<m;j++)
        if((result&(1<<j))!=(i&(1<<j)))need++;
        

        if(bi<0||(need<best||(need==best&&s[i]<s[bi])))
        {
            bi=i;
            best=need;
        }
    }
    if(bi<0)while(1)cout<<"sadfsdf";
    cout<<s[bi]<<endl;
    for(i=m-1;i>=0;i--)
    cout<<((bi>>i)&1);
    cout<<endl;
    }
    return 0;
}
							

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

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


public class Main {
    
  static int N = 26; 
  int n;
  int M;
  int[][] adj = new int[26][26];
  boolean[] chk = new boolean[26];
    
  boolean DFS(int K, int m) {
   chk[m] = true;
   if(m == 1) 
       return true;
   int i;
   for(i = 0; i < n; ++i) if(!chk[i])
    if(adj[m][i]!=0 && adj[m][i] % K == 0)
         if(DFS(K, i))
        return true;
    return false;
   }
    
 BigInteger GCD(BigInteger x, BigInteger y) {
   if(x.compareTo(y) < 0) 
    return GCD(y, x);
   while(y.compareTo(BigInteger.ZERO) > 0) {
     BigInteger tmp = y;
    y = x.mod(y);
    x = tmp;
   }
   return x;
 }
    
 BigInteger LCM(BigInteger x, BigInteger y) {
   BigInteger ret = x.multiply(y);
   ret = ret.divide(GCD(x, y));
   return ret;
  }
    
  void run() {
   Scanner cin = new Scanner(System.in);
   n = cin.nextInt();
   int i, j;
   M = 0;
   for(i = 0; i < n; ++i)
    for(j = 0; j < n; ++j) {
         adj[i][j] = cin.nextInt();
      if(adj[i][j] > M)
        M = adj[i][j];
    }
        
    BigInteger ans = new BigInteger("1");
    for(i = 1; i <= M; ++i) {
      for(j = 0; j < n; ++j)
        chk[j] = false;
      if(DFS(i, 0)) {
//        System.out.println(i + " " + ans);
        ans = LCM(ans, new BigInteger(""+i));
       }
    }
    System.out.println(ans);
    }

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

  }

}

							

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

/* @author: */
import java.util.*;
public class Main {
  static int ans[][], xf[][], yf[][];
  static int as[][], len[];
  static public void main( String [] str ) throws Exception{
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt(), m;
    int [] a, b;
    a = new int[n];
    for( int i=0; i< n; i++ )
    a[i] = cin.nextInt();
    m = cin.nextInt();
    b = new int[m];
    for( int i=0; i< m; i++ )
    b[i] = cin.nextInt();
        
    ans = new int[n][m];
    xf = new int[n][m];
    yf = new int[n][m];
    as = new int[n][m];
    len = new int[n];
            
    for( int i=0; i< n; i++ ) {
    for( int j=0; j< m; j++ )
      if( a[i] == b[j] )
         as[i][len[i]++] = j;
            
       int [] t = new int[len[i]];
       System.arraycopy( as[i], 0, t, 0, len[i] );
       as[i] = t;
    }
            
    int bx = -1, by = -1;
    for( int i=n-1; i>=0; i-- )
    for( int j=m-1; j>=0; j-- ) 
      if( a[i] == b[j] ){
        int t, best = 0;
        xf[i][j] = yf[i][j] = -1;
           for( int k=i+1; k< n; k++ ) 
          if( a[k] > a[i]) {
         t = Arrays.binarySearch( as[k], j+1 );
         if( t < 0 )
           t = -t-1;
         if( t != as[k].length ) {
           t = as[k][t];
           if( ans[k][t] > best ) {
             best = ans[k][t];
             xf[i][j] = k;
             yf[i][j] = t;
            }
          }
          }
       ans[i][j] = best+1;
       if( bx < 0 || ans[i][j] > ans[bx][by] ) {
        bx = i;
        by = j;
       }
     }
        
    if( bx < 0 )
      System.out.println( 0 + "n" );
    else {
      System.out.println( ans[bx][by] );
    while( bx != -1 ) {
      System.out.print( a[bx] );
      int x = xf[bx][by], y = yf[bx][by];
      bx = x;
      by = y;
      if( bx != -1 )
        System.out.print( " " );
    }
    System.out.println();
    }
    return;
   }
}
							

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

//* @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)));
    int n=Integer.parseInt(scanner.nextLine());
    if (n< 2){
        System.out.println("YES");
    }
    else if (n==2){
        int a=scanner.nextInt();
        int b=scanner.nextInt();
        int c=scanner.nextInt();
        if (b*b-4*a*c>=0){
            System.out.println("NO");
        }
        else{
            System.out.println("YES");
        }
    }
    else{
        System.out.println("NO");
    }
 }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 static String[] Num=new String[]{
    "zero","one","two","three","four","five","six","seven","eight","nine","ten",
    "eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen",
    "nineteen","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety",
    "hundred","thousand","million"
  };

  public static void main(String[] args) throws IOException
  {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   String s;
   while(true)
    {
      s=in.readLine();
      if(s.equals("")) break;
      boolean bb=true;
      String[] ss=s.split(" ");
      int len=ss.length;
      long sum=0;
      long temp=0;
      int tag=0;
      if(ss[0].equals("negative")){
     bb=false;
     tag=1;
      }
      for(int i=tag;i< len;i++)
      {
     for(int j=0;j< 31;j++)
     {
        if(ss[i].equals(Num[j]))
        {
         if(j<=20) temp+=j;
         else if(j< 28) temp+=(j-18)*10;
         else if(j==28) temp*=100;
         else if(j==29)
         {
               temp*=1000;sum+=temp;temp=0;
         }
         else if(j==30)
         {
           sum+=temp;sum*=1000000;temp=0;
         }
         break;
         }
      }
       }
       sum+=temp;
       if(!bb) sum=-sum;
       System.out.println(sum);
    }
  }
}
							

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

#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair< int, int > edge;
vector< edge > e[10010];
int v[10010],s[10010];
int st[10010],sn;
bool sign[10010];
int n;
int find_root_search( int r, int f )
{
    int temp,i,j;
    v[r] = 0;
    s[r] = 1;
    st[sn++] = r;
    for( i=0; i<e[r].size(); i++ )
    {
        j = e[r][i].first;
    
        if( j != f && sign[j] )
        {
            temp = find_root_search( j , r );
            if( temp > v[r] ) v[r] = temp;
            s[r] += temp;
        }
    }

    return s[r];
}
int find_root( int r, int f )
{
    int i,h,j,t;
    
    sn = 0;
    h = find_root_search( r, f );

    r = st[0];
    for( i=0; i<sn; i++ )
    {
        j = st[i];
        if( ( t = h - s[j] ) > v[j] ) v[j] = t;
        if( v[j] < v[r] ) r = j;
    }

    return r;
}
int _dis[100],mm;
int dis[100],m;
int id[100];
int ans[10010],*temp=st,ans_n;
bool ok[100];
int cn;
void calc_dis( int r, int len, int f )
{
    int i, j;
    ans[cn++] = len;    
    for( i=0; i<e[r].size(); i++ )
    {
        j = e[r][i].first;    
        if( j != f && sign[j] )
        {
            calc_dis( j, len + e[r][i].second, r );
        }
    }
}
void search( int r, int num, int f, int len )
{
    int i,j,h,a,num1,rr=r,t;
    int *p1,*p2,*q1,*q2,*p;
    ans[ans_n++] = 0;
    sn = 0;
    r = find_root( r, f );
    sign[r] = false;
    for( i=0; i<e[r].size(); i++ )
    if( sign[ j = e[r][i].first ] )
    {
        h = e[r][i].second;
        num1 = ans_n;
        search( j, num1, r, h );
        if( m == 0 )
            return;
        p1 = ans + num; q1 = ans + num1;
        p2 = ans + num1; q2 = ans + ans_n;
        if( q1-p1 > q2-p2 )
        {
            swap( p1, p2 );
            swap( q1, q2 );
        }
        for( p=p1; p<q1; p++ )
        {
            for( a=0; a<m; a++ )
            {
                t = dis[a]-*p;
                if( t >= *p2 && t<=*(q2-1) && binary_search( p2, q2, t ) )
                {
                    ok[ id[a] ] = true;
                    dis[a] = dis[m-1];
                    id[a] = id[m-1];
                    m--;
                    a--;
                }
            }
        }
        merge( p1, q1, p2, q2, temp );
        copy( temp, temp+ans_n-num, ans+num );
    }
    sign[r] = true;
    cn = num;
    calc_dis( rr, len, f );
    sort( ans+num, ans+ans_n );
}
bool init()
{
    int i,d,c;
    scanf( "%d", &n );
    if( n == 0 )return false;
    for( i=0; i<n; i++ )
    {
        e[i].clear();
        sign[i] = true;
    }
    for( i=0; i<n; i++ )
    while( 1 )
    {
        scanf( "%d", &d );
        if( d == 0 ) break;
        scanf( "%d", &c );
        e[i].push_back( edge( d-1, c ) );
        e[d-1].push_back( edge( i, c ) );
    }
    m = 0;
    while( 1 )
    {
        scanf( "%d", &dis[m] );
        if( dis[m] == 0 )break;
        
        _dis[m] = dis[m];
        id[m] = m;
        ok[m] = false;
        m++;
    }
    mm = m;
    ans_n = 0;
    return true;

}
int main()
{
    int i;

    while( init() )
    {
        search( 0, 0, -1, 0 );

        for( i=0; i<mm; i++ )
        {
            if( ok[i] )    printf( "AYEn" );
            else printf( "NAYn" );
        }
        printf( ".n" );
    }
    return 0;
}




							

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

#include<iostream> 
using namespace std;
#define null 0

const int size=1010;

long dis[size][size],k,m,c,up,w[size][size];

int maxmatch(int n,int m,long w[][size],int *p)

{
       int p_n[size];
       int p_m[size];
       bool sign[size];
       int q[size],from[size],s,t;


       int i,j,link,now,h;

       for(i=0;i<n;i++)p_n[i]=-1;
       for(j=0;j<m;j++)p_m[j]=-1;

       for(i=0;i<n;i++)
       if(p_n[i]==-1)
       {
              for(j=0;j<m;j++)sign[j]=0;
                 

              s=1;link=-1;


              from[0]=-1;
              q[0]=size-1;
              p_m[size-1]=i;
              

              for(t=0;t<s;t++)
              {
                     now=q[t];
                     for(j=0;j<m;j++)
                     {
                            if(w[p_m[now]][j]<=up&&sign[j]==0)
                            {
                                   sign[j]=1;
                                   q[s]=j;
                                   from[s++]=t;
                                   

                                   if(p_m[j]==-1)
                                   {
                                          link=s-1;
                                          break;
                                   }
                            }
                     }

                     if(j<m)break;
              }

              if(t<s)
              {
                     while(from[link]!=-1)
                     {
                            h=from[link];
                            p_m[q[link]]=p_m[q[h]];

                            p_n[p_m[q[h]]]=q[link];
                            link=h;
                     }
              }
       }

       int an;
       for(i=0,an=0;i<n;i++)
       {
              if(p)p[i]=p_n[i];
              if(p_n[i]>=0)an++;
       }

       return an;

}

void init()
{
    int i,j,s,l;
    cin>>k>>c>>m;
    s=k+c;
    for(i=0;i<s;i++)
    for(j=0;j<s;j++)
    {
        cin>>dis[i][j];
        if(i!=j&&dis[i][j]==0)dis[i][j]=9999999;
    }
    
    for(l=0;l<s;l++)
    for(i=0;i<s;i++)
    for(j=0;j<s;j++)
    {
        if(dis[i][l]+dis[l][j]<dis[i][j])
        dis[i][j]=dis[i][l]+dis[l][j];
    }
    
   for(i=0;i<k;i++)
   for(j=0;j<m;j++)
   for(l=k;l<s;l++)
   w[l-k][i*m+j]=dis[l][i];
       
}

int main()
{
    long s,a,b,i,j;
    init();
        
    k*=m;
    a=0;b=200*250;
    while(a<b-1)
    {
        up=(a+b)/2;
        if(maxmatch(c,k,w,0)==c)b=up;
        else a=up;
    }
    cout<<b<<endl;
    
    return 0;

}
							

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

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
 
    static final BigInteger TWO = new BigInteger("2");
    static final BigInteger ONE = BigInteger.ONE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // k^n=p findK;
          BigInteger p;
          int n;
        BigInteger ks, kl;
        while (in.hasNextInt()) {
            boolean find=false;
            n = in.nextInt();
            p = in.nextBigInteger();
            ks = ONE;
            kl = p;
            while (ks.compareTo(kl) <= 0) {
                BigInteger mid = ks.add(kl).divide(TWO);
                int ret = mid.pow(n).compareTo(p);
                if (ret == 0) {
                    find=true;
                    System.out.println(mid);
                    break;
                } else if (ret == -1) {
                    ks = mid.add(ONE);
                } else {
                    kl = mid.subtract(ONE);
                }
            }
            if(!find){
                System.out.println(ks.subtract(ONE));
            }
        }

    }
}


							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
  
  
           
        for(int i = 0; i < num; i++)   
        {   
            String str, temp;   
            int a,b,c,d = 0;   
            StringBuffer sb = new StringBuffer();   
               
            str = cin.nextLine();   
            temp = str.substring(0, 8);   
            sb.append(convert(temp));   
            sb.append('.');   
            temp = str.substring(8, 16);   
            sb.append(convert(temp));   
            sb.append('.');   
            temp = str.substring(16, 24);   
            sb.append(convert(temp));   
            sb.append('.');   
            temp = str.substring(24);   
            sb.append(convert(temp));   
  
            System.out.println(sb.toString());   
        }   
  
    }   
       
    private static int convert(String str)   
    {   
        int value = 0;   
        if(str.charAt(0) == '1')   
            value += 128;   
        if(str.charAt(1) == '1')   
            value += 64;   
        if(str.charAt(2) == '1')   
            value += 32;   
        if(str.charAt(3) == '1')   
            value += 16;   
        if(str.charAt(4) == '1')   
            value += 8;   
        if(str.charAt(5) == '1')   
            value += 4;   
        if(str.charAt(6) == '1')   
            value += 2;   
        if(str.charAt(7) == '1')   
            value += 1;   
           
        return value;   
    }   
  
}  

							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss=in.readLine().split(" ");
  int a=Integer.parseInt(ss[0]);
  int k=Integer.parseInt(ss[1]);
  my[] p=new my[a];
  ss=in.readLine().split(" ");
  for(int i=0;i< a;i++)
    p[i]=new my(i,Integer.parseInt(ss[i]));
  Arrays.sort(p);
  while((k--)!=0)
   {
    ss=in.readLine().split(" ");
    int l=Integer.parseInt(ss[0])-1;
    int r=Integer.parseInt(ss[1]);
    int cnt=Integer.parseInt(ss[2]);
    for(int i=0;i< a;i++)
    {
          if(p[i].num>=l&&p[i].num< r)
       {
        cnt--;
        if(cnt==0)
         {
        System.out.println(p[i].t);
        break;
         }
       }
    }
     }
   }

 }

 class my implements Comparable< my>
 {
    int num,t;
    public my(int a,int b)
    {
        num=a;
        t=b;
    }
    public int compareTo(my arg0) {
        return t-arg0.t;
    }
}

							

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

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

public class Main {
 static int oneNum[] = new int[65536];
 static BigInteger arr[] = new BigInteger[20];
 static int n;
 static BigInteger list[] = new BigInteger[65536];

public static void main(String[] args) {
  for(int i = 0; i < 16; i ++) {
   for(int j = 1<< i; j < 1<< i+1; j ++) {
    oneNum[j] = oneNum[j ^ (1<< i)] + 1;
   }
  }
   ///init over!
   Scanner scan = new Scanner(System.in);
   n = scan.nextInt();
  BigInteger ans1 = BigInteger.ZERO, ans2 = BigInteger.ONE;
  for(int i = 0; i < n; i ++) {
   arr[i] = scan.nextBigInteger();
   ans2 = ans2.multiply(arr[i]).divide(ans2.gcd(arr[i]));
  }

  list[0] = BigInteger.ONE;
  for(int i = 0; i < n; i ++) {
   for(int j = 1<< i; j < 1<< i+1; j ++) {
     list[j] = list[j^(1<< i)].multiply(arr[i]).divide(list[j^(1<< i)].gcd(arr[i]));
     if((oneNum[j] & 1) == 1) {
    ans1 = ans1.add(ans2.divide(list[j]));
     } else {
    ans1 = ans1.subtract(ans2.divide(list[j]));
     }
    }
   }

   BigInteger g = ans1.gcd(ans2);
   ans1 = ans1.divide(g);
   ans2 = ans2.divide(g);

   System.out.println(ans1);
   System.out.println(ans2);
 }
}
							

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

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   int n = cin.nextInt();
   int e = cin.nextInt();
   double l1 = 0, l2 = 0;
   while(--n > 0) {
    l1 += cin.nextInt();
   }
   while(--e > 0) {
    l2 += cin.nextInt();
   }
   l1 = Math.hypot(l1, l2);
   System.out.println((int)Math.ceil(l1));
}

}


							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  HashMap< Integer,Integer> ts=new HashMap< Integer,Integer>();
  while(true)
  {
   String[] ss=in.readLine().split(" ");
   int x=Integer.parseInt(ss[0]);
   int y=Integer.parseInt(ss[1]);
   if(x==0&&y==0)break;
   for(int i=0;i< x;i++)
   {
    ss=in.readLine().split(" ");
    for(int j=0;j< y;j++)
    {
      int u=Integer.parseInt(ss[j]);
      ts.put(u, ts.containsKey(u)?ts.get(u)+1:1);
    }
    }
    List< Map.Entry< Integer, Integer>> ww=
           new ArrayList< Map.Entry< Integer, Integer>>(ts.entrySet());
    Collections.sort(ww,new Comparator< Map.Entry< Integer, Integer>>(){

    @Override
    public int compare(Entry< Integer, Integer> arg0,
    Entry< Integer, Integer> arg1) {
      int r1=arg1.getValue();
      int r0=arg0.getValue();
      if(r1!=r0) return r1-r0;
      else return arg0.getKey()-arg1.getKey();
        }
     });
    int k=ww.get(1).getValue();
    System.out.print(ww.get(1).getKey());
    for(int i=2;i< ww.size();i++)
    {
      if(ww.get(i).getValue()==k) System.out.print(" "+ww.get(i).getKey());
      else break;
    }
    System.out.println();
    ts.clear();
  }    
 }
}
							

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

#include<iostream>
#include"algorithm"
using namespace std;

int dis[21][21];
int tim[21],n;
int id[21],mint[21];

int cmp(int a,int b)
{
    return mint[a]<mint[b];
}

void init()
{
    int i,j,k;
    for(i=0;i<n;i++)
    cin>>tim[i];
    
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        cin>>dis[i][j];
    }
    
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    if(dis[i][k]+dis[k][j]<dis[i][j])
    dis[i][j]=dis[i][k]+dis[k][j];
    
    for(i=0;i<n;i++)
    {
        mint[i]=9999;id[i]=i;
        for(j=0;j<n;j++)
        {
            dis[j][i]+=tim[i];
            if(dis[j][i]<mint[i])mint[i]=dis[j][i];
        }
    }
    std::sort(&id[0],&id[n],cmp);

}

long answer;
long visit;
int ll;
bool find(int a,int s,int rest)
{
    long k;int i,t,limit=5;
    
    if(s>answer)answer=s;
    
    if(answer==n)return 1;
    visit^=1<<a;

    t=0;
    for(i=0;t<=rest&&i<n;i++)
    if(!(visit&(1<<id[i])))
    {
        t+=mint[id[i]];
    }
    
    if(i+s<answer)return 0;

    for(i=0;i<n&&limit;i++)
    {
        if(!(visit&(1<<i))&&rest>=dis[a][i])
        {
            limit--;
            if(find(i,s+1,rest-dis[a][i]))return 1;
        }
    }
        
    visit^=1<<a;
    
    return 0;
}

int main()
{
    int i,t,c=1;

    while(1)
    {
        cin>>n;
        if(n==0)break;
        init();
        
        answer=0;
        for(i=0;i<n;i++)
        if(420>=tim[i])
        {
            visit=0;
            t=find(i,1,420-tim[i]);
        }
        
        cout<<answer<<endl;
    }
    return 0;
}
							

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

#include<iostream>
#include"stdio.h"
#include"math.h"
#include<algorithm>
using namespace std;
/////////////////////////
#define Type double /*�������*/
/////////////////////////
struct point
{
    Type x,y;
    int host;
};
const double pi=3.1415926535898;
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 dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
double jl(point a,point b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
const double eps=0.0000001;
point object(point a,double degree,double len)
{
    point c;
    c.x=a.x+len*cos(degree/180*pi);
    c.y=a.y+len*sin(degree/180*pi);
    c.host=a.host;

    return c;
}
point p[10];
int n;
void throwball(point a,point b,int prev)
{
    point pt;
    int k=-1,i;double l=9999999,t;
    for(i=0;i<n;i++)
    if(i!=prev)
    {
        if(fabs(cheng(p[i],a,b))<eps&&dcheng(p[i],a,b)<-eps)
        {
            t=jl(p[i],a);
            
            if(t<l)
            {
                k=i;
                l=t;
            }
        }
    }
    if(k<0)
    {
        p[n++]=b;
        for(i=0;i<n;i++)
        if(p[i].host==-1)break;
        
        if(i!=0)swap(p[i],p[0]);
    }
    else 
    {
        pt=p[k];
        p[k].host=a.host;
        b.host=pt.host;
        throwball(pt,b,k);
    }
}
int cmp(point a,point b)
{
    return jl(a,p[0])<jl(b,p[0]);
}
void doit()
{
    int key;int use[2]={0,0};
    char name1[100],name2[100];
    cin>>name1>>name2;
    point start;
    double degree,len,t;
    cin>>start.x>>start.y>>degree>>len;
    p[0]=object(start,degree,len);
    p[0].host=-1;
    n=1;
    cin>>start.x>>start.y>>degree>>len;
    start.host=0;
    throwball(start,object(start,degree,len),-1);
    cin>>start.x>>start.y>>degree>>len;
    start.host=1;
    throwball(start,object(start,degree,len),-1);
    int i,j,k;
    for(i=3;i<7;i++)
    {
        k=-1;len=9999999;
        if(use[0]==2)key=0;
        else if(use[1]==2)key=1;
        else for(j=1;j<n;j++)
        {
            t=jl(p[0],p[j]);
            if(k==-1||t<len)
            {
                k=j;
                len=t;
                key=p[j].host;
            }
        }        
        cin>>start.x>>start.y>>degree>>len;
        start.host=1-key;
        if(use[start.host]>=2)while(1);
        use[start.host]++;

        throwball(start,object(start,degree,len),-1);
    }
    i=i;
    sort(&p[1],&p[7],cmp);
    if(p[1].host==0)cout<<name1<<' ';
    else cout<<name2<<' ';
    for(i=1;p[i].host==p[1].host;i++)        ;
    cout<<i-1<<endl;
    return;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        doit();
    }
    return 0;
}



							

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

import java.util.Scanner;

public class Main{
 public static void main(String args[]){

  int n,m; 
  int i,j,k,sum;
  Scanner sc=new Scanner(System.in);
    while(true)    {
       n=sc.nextInt();
       m=sc.nextInt();

          if(n==-1&&m==-1)break;
          sum=0;
          for(i=n;i>=1;i--)
          {
              sum+=(n-i);
              if(sum>=m)break;             
              }               
          for(j=1;j< i;j++) System.out.printf("%d ",j);
          k=m+i-(n-i)*(n-i-1)/2;

          System.out.printf("%d",k);

          for(j=n;j>=i;j--) if(j!=k) System.out.printf(" %d",j);
          System.out.printf("n");              
     }
    }
}
 



							

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

import java.io.*; 
import java.util.*; 
import java.math.BigInteger;
public  class Main { 
 public static void main(String[]args){ 
  Scanner sin=new Scanner(new BufferedInputStream(System.in)); 
   int n;
   int i = 0; 
   BigInteger big[] = new BigInteger[101];
   for(i = 0 ; i < 101 ; i++)
    big[i] = new BigInteger("0");
    big[0] = big[1].add(new BigInteger("1"));
    big[1] = big[1].add(new BigInteger("1"));
  for(i=2; i < 101 ; i++){
   for(int j = 0 ; j < i ; j++){
    big[i] = big[i].add(big[j].multiply(big[i-1-j]));  
   }
}

while(true){ 
 n=sin.nextInt(); 
 if(n == -1)break;
   System.out.println(big[n].toString()); 

}

}
} 

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
class Main
{
 static StringBuffer sb=new StringBuffer();
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
    int a=in.nextInt();
    if(a==-1) break;
    else if(a==1) System.out.println('X');
    else g("",a-1);
    System.out.println("-");
  }
 }


 static void p(int a)
 {
  int t=(int)Math.pow(3, a-1);
  for(int i=0;i< t;i++)
    sb.append(" ");
 }

  static void g(String s,int a)
  {
   if(a==0)
   {
    sb.delete(0, sb.length()+1);
    print(s);
    System.out.println(sb.toString().subSequence(0, sb.lastIndexOf("X")+1));
    return;
    }
    g(s+"A",a-1);
    g(s+"B",a-1);
    g(s+"A",a-1);
        
    }
    

 static void print(String s)
 {
    int l=s.length();
    char c=s.charAt(0);
    if(l==1)
    {
          if(c=='A') sb.append("X X");
      else sb.append(" X ");
      return;
    }
    if(c=='A')
    {
       print(s.substring(1));
       p(l);
       print(s.substring(1));
    }
    else 
    {
       p(l);
       print(s.substring(1));
       p(l);
    }
   }
}
							

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

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

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.text.*;

public class Main{
    public static void main(String[] args) throws IOException{
        Date twoK,res,t1,t2;
        long twoKl,resl,t;
                //��EEEE������4λΪȫ�ƣ������Ϻ���ġ�Locale.US�������ڻ��������Ŷ��
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd EEEE",Locale.US);
        //BufferedInputStream bin = new BufferedInputStream(new FileInputStream("in.txt"));
        //System.setIn(bin);
        Scanner cin = new Scanner(System.in);
        twoK = new Date(100,0,1,8,0,0);
        twoKl=twoK.getTime();
        t1 = new Date(100,0,1,8,0,0);
        t2 = new Date(100,0,2,8,0,0);
        t=t2.getTime()-t1.getTime();//����һ���getTime()��ֵ
        while(cin.hasNext())
        {
            resl=cin.nextLong();
            if(resl==-1)
            {
                break;
            }
            resl=resl*t+twoKl;
            res = new Date(resl);
            System.out.println(sdf.format(res));
        }
    }
}

							

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

#include<iostream>
#include"stdio.h"
#include<algorithm>
//ifstream in("triangle.in");
//#define cin in

using namespace std;

/////////////////////////
#define Type long /*�������*/
/////////////////////////


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;}
};

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);}




const double pi=3.14159265359;

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);
}




//n*log(n)
//��͹��,����͹���ϵĵ�ĸ���wall:͹�������

//p�����������!!!

int convex(point *p,int n,point *wall)
{int i;int st;Type h;
int stack[50011],sign[50011];

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 '>'
{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 wall[50010];
point p[50010];
long n,s;

inline long ab(long a)
{
    return a>0?a:-a;
}

int main()
{
    long i,j,l;long k,h;
    while(1)
    {
        //cin>>n;
        scanf("%ld",&n);
        if(n<0)break;

        for(i=0;i<n;i++)
        {
            //cin>>p[i].x>>p[i].y;
            scanf("%ld%ld",&p[i].x,&p[i].y);
        }

        sort(p,n);
        if(n>3)n=convex(p,n,wall);
        else for(i=0;i<n;i++)wall[i]=p[i];

        s=cheng(wall[0],wall[1],wall[2]);
        s=s>0?s:-s;
        
        for(l=1,i=3;i<n;i++)
        {
            k=0;
            for(j=l;j<i;j++)
            {
                h=ab(cheng(wall[i],wall[j],wall[k]) );
                while(k<j-1&&(h=ab(cheng(wall[i],wall[j],wall[k]) ))<ab(cheng(wall[i],wall[j],wall[k+1])) )
                    k++;
                if(h>s)
                {
                    s=h;
                    l=j;
                }
            }
        }


        printf("%.2lfn",(double)s/2);
    }
    return 0;
}



							

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

#include "stdio.h"


int a[10][10], ans, n;
int k[10],sum[10];

void doit( int s )
{
    int i, maxv;
    
    if( s == n )
    {
        maxv = -1;
        for( i=0; i<n; i++ )
            if( sum[i] > maxv ) maxv = sum[i];
        ans = maxv;
        return;
    }

    for( k[s]=0; k[s]<n; k[s]++ )
    {
        for( i=0; i<n; i++ )
        {
            sum[i] += a[s][ (k[s]+i)%n ];
            if( sum[i] > ans ) break;
        }
    
        if( i == n )doit( s+1 );
    
        for( ; i>=0; i-- )
            sum[i] -= a[s][ (k[s]+i)%n ];
    }
}


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

    while( 1 )
    {
        scanf( "%dn", &n );
        if( n < 0 ) break;

        for( i=0; i<n; i++ )
        for( j=0; j<n; j++ )
        scanf( "%d", &a[i][j] );
        
        ans = 999999;
        for( i=0; i<n; i++ )
        sum[i] = 0;
        
        doit( 0 );
    
        printf( "%dn", ans );
        
    }

    return 0;
}
							

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

#include<iostream>
#include"algorithm"
using namespace std;

int dist[101][101],n,m;

void init()
{
    int i,a,b,d,j,k;
    cin>>n>>m;
    
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    dist[i][j]=9999;
    
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>d;
        a--;b--;
        if(d<dist[a][b])
        {
            dist[a][b]=dist[b][a]=d;
        }
    }
    
    for(i=0;i<n;i++)
    dist[i][i]=0;
    
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    if(dist[i][k]+dist[k][j]<dist[i][j])
    dist[i][j]=dist[i][k]+dist[k][j];

    return ;
}
int answer[101];
int c1,c2;
int cmp(int a,int b)
{
    return dist[a][c2]-dist[a][c1]>dist[b][c2]-dist[b][c1]||
        (dist[a][c2]-dist[a][c1]==dist[b][c2]-dist[b][c1]&&a<b);
}

void doit()
{
    int index[101];long best=99999999,now;
    int bestk;
    int i,j;
    
    for(c2=0;c2<n;c2++)
    for(c1=c2+1;c1<n;c1++)
    {
        bestk=-1;

        for(i=0,j=0;i<n;i++)
            if(i!=c1&&i!=c2)
                index[j++]=i;
        
        std::sort(&index[0],&index[j],cmp);
        
        now=0;
        
        for(i=0;i<n;i++)
        if(i!=c1&&i!=c2)now+=(n-1)*dist[i][c2];
                
        now+=(n-1)*dist[c1][c2];
        
        if(now<best)
        {
            bestk=0;
            best=now;
        }
        
        for(i=1;i<n-1;i++)
        {
            now-=i*(n-i)*dist[c1][c2];
            now+=(i+1)*(n-i-1)*dist[c1][c2];
            now+=(dist[index[i-1]][c1]-dist[index[i-1]][c2])*(n-1);
            if(now<best)
            {
                bestk=i;
                best=now;
            }
        }
        
        if(bestk>=0)
        {
            for(i=0;i<bestk;i++)
                answer[index[i]]=c1+1;
            
            for(;i<n-2;i++)
                answer[index[i]]=c2+1;
                
            answer[c1]=0;
            answer[c2]=0;
        }
    }
    return;
}
            
int main()
{
    int t,i;
    cin>>t;
    while(t--)
    {
        init();
        doit();
        for(i=0;i<n;i++)
        {
            if(i)cout<<' ';
            cout<<answer[i];
        }
        cout<<endl;
    }
    return 0;
}
							

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

//* @author: SmilingWang
import java.util.*;
public class Main {
  public static final int BLOCK = Integer.MAX_VALUE;
  public static final double zero = 1e-6;
  public static double cl;
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    cl = in.nextDouble();
    int pn = in.nextInt();
    double w[][] = new double[pn+1][pn+1];
    for(int i = 1; i <= pn; i++){
        for(int j = 1; j <= pn; j++){
            if(j == i){
                continue;
            }
            w[i][j] = BLOCK;
        }
    }
    Map< String, Integer> map = new HashMap< String, Integer>();
    for(int i = 1; i <= pn; i++){
        String s = in.next();
        map.put(s, i);
    }
    int en = in.nextInt();
    for(int i = 1; i <= en; i++){
        String s1 = in.next();
        String s2 = in.next();
        int i1 = map.get(s1);
        int i2 = map.get(s2);
        w[i1][i2] = in.nextDouble();
        w[i2][i1] = w[i1][i2];
    }
    prim(w, pn);
   }

   public static void prim(double[][] w, int n){
    int nearest[] = new int[n+1];
    double distance[] = new double[n+1];
    int vnear = 0;
        
    Set< Edge> set = new HashSet< Edge>();
    for(int i = 2; i <= n; i++){
        nearest[i] = 1;
        distance[i] = w[1][i];
    }
    for(int v = 2; v <= n; v++){
        double min = BLOCK;
        for(int i = 2; i <= n; i++){
          if(distance[i] >= zero && distance[i] < min){
            vnear = i;
            min = distance[i];
          }
        }
        Edge edge  = new Edge(nearest[vnear], vnear, w[vnear][nearest[vnear]]);
        set.add(edge);
        distance[vnear] = -1;
        for(int i = 2; i <= n; i++){
           if(w[i][vnear] < distance[i]){
            distance[i] = w[i][vnear];
            nearest[i] = vnear;
           }
        }
    }
    //System.out.println(set);
    Iterator< Edge> itr = set.iterator();
    double cost = 0;
    String out = "";
    while(itr.hasNext()){
        cost += (itr.next().weight);
    
    }
    //System.out.println(out);
    if(cost - cl <= zero){
        System.out.printf("Need %.1f miles of cablen",cost);
    }
    else{
        System.out.println("Not enough cable");
    }
   }
}

class Edge{
    int sv;
    int ev;
    double weight;
    
    public Edge(int sv, int ev, double w){
        this.sv = sv;
        this.ev = ev;
        this.weight = w;
    }
    public String toString(){
        return sv + " " + ev + " " + weight + " ";
    }
}



							

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

//* @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())
  {
   float a=in.nextFloat();
   float b=in.nextFloat();
   float c=in.nextFloat();
   if(a==0&&b==0&&c==0) break;
   boolean s=true;
   if(a<=4.5&&b>=150&&c>=200){
     System.out.print("Wide Receiver ");
     s=false;
    }
   if(a<=6&&b>=300&&c>=500){
     System.out.print("Lineman ");
     s=false;
   }

   if(a<=5&&b>=200&&c>=300){
     System.out.print("Quarterback ");
     s=false;
    }
   if(s) System.out.print("No positions");
   System.out.println();
   }
 }
}
							

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

#include<iostream>
#include"stdio.h"
#include"math.h"
using namespace std;
#define sq(a) ((a.x)*(a.x)+(a.y)*(a.y)+(a.z)*(a.z))

int n;
typedef double  det[3][3];
struct point
{
    double x,y,z;
};

double hls(det a)
{
    return a[0][0]*a[1][1]*a[2][2]+a[0][1]*a[1][2]*a[2][0]+a[0][2]*a[1][0]*a[2][1]
          -a[0][2]*a[1][1]*a[2][0]-a[0][1]*a[1][0]*a[2][2]-a[0][0]*a[1][2]*a[2][1];
}

bool qiujie(det s,double s0,double s1,double s2,point &o)
{
    det t={{s0,s[0][1],s[0][2]},{s1,s[1][1],s[1][2]},{s2,s[2][1],s[2][2]}};
    double h=hls(s);
    
    if(h==0)return 0;
    o.x=hls(t)/h;
    t[0][0]=s[0][0];t[1][0]=s[1][0];t[2][0]=s[2][0];
    t[0][1]=s0;t[1][1]=s1;t[2][1]=s2;
    o.y=hls(t)/h;
    
    t[0][1]=s[0][1];t[1][1]=s[1][1];t[2][1]=s[2][1];
    t[0][2]=s0;t[1][2]=s1;t[2][2]=s2;
    o.z=hls(t)/h;
    return 1;
}

bool qiuxin(point a,point b,point c,point d,point &o)
{
    det s={{a.x-b.x,a.y-b.y,a.z-b.z},{b.x-c.x,b.y-c.y,b.z-c.z},{c.x-d.x,c.y-d.y,c.z-d.z}};
    double s0=(sq(a)-sq(b))/2,s1=(sq(b)-sq(c))/2,s2=(sq(c)-sq(d))/2;
    
    return qiujie(s,s0,s1,s2,o);
}

bool qiuxin(point a,point b,point c,point &o)
{    
    det s={{a.x-b.x,a.y-b.y,a.z-b.z},{b.x-c.x,b.y-c.y,b.z-c.z}};
    double s0=(sq(a)-sq(b))/2,s1=(sq(b)-sq(c))/2,s2=0,t;
    t=(b.y-a.y)*(c.z-a.z)-(c.y-a.y)*(b.z-a.z);
    s[2][0]=t;s2+=a.x*t;
    t=(b.x-a.x)*(c.z-a.z)-(c.x-a.x)*(b.z-a.z);
    s[2][1]=-t;s2+=-t*a.y;
    t=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    s[2][2]=t;s2+=t*a.z;
    
    return qiujie(s,s0,s1,s2,o);
}
double jl(point &a,point &b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
point p[31];

bool is_ok(point o,double r)
{
    int i;
    for(i=0;i<n;i++)
    if(jl(p[i],o)>r+0.00001)break;
    
    return i==n;
}

int main()
{
    int i,j,k,l;point o;
    double answer,r;
    while(1)
    {
        cin>>n;
        if(n==0)break;
        
        for(i=0;i<n;i++)
        cin>>p[i].x>>p[i].y>>p[i].z;
        
        answer=999999;
        
        for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
        {
            o.x=(p[i].x+p[j].x)/2;
            o.y=(p[i].y+p[j].y)/2;
            o.z=(p[i].z+p[j].z)/2;
            
            r=jl(o,p[i]);
            if(is_ok(o,r)&&r<answer)answer=r;
            
            for(k=j+1;k<n;k++)
            {
                if(qiuxin(p[i],p[j],p[k],o))
                {
                    r=jl(o,p[i]);
                    if(is_ok(o,r)&&r<answer)answer=r;
                }
                
                for(l=k+1;l<n;l++)
                if(qiuxin(p[i],p[j],p[k],p[l],o))
                {
                    r=jl(o,p[i]);
                    if(is_ok(o,r)&&r<answer)answer=r;
                }    
            }
        }
        
        printf("%.5lfn",answer);
    }
    return 0;
}
							

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

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

class Layer
{
  int cost;
  int frontier[];
  int frontierCode;
  
  Layer(int f[], int c)
  {
    cost = c;
      frontier = new int[f.length];
    frontierCode = 0;
        
    for (int i=0; i< frontier.length; i++)
      frontier[i] = f[i];
    
    for (int i=0; i< frontier.length; i++)
    {
      if ((frontier[i] != Main.NO_PIPE) && (frontier[i] !=
 Main.NEW_PIPE))
      {
        if (i < frontier[i])
          frontierCode += (1 << (2*i));
        else
          frontierCode += (2 << (2*i));
      }
    }
  }
  
  public int hashCode()
  {
    return frontierCode;
  }
  
  public String toString()
  {
    return "Layer " + frontierCode + " with cost " + cost;
  }
    
  public boolean equals(Object o)
  {
      Layer l = (Layer) o;
    return l.frontierCode == frontierCode;
  }
}
    
public class Main
{
  static int MAX_SIZE = 10;
  static int MAX_TABLE_SIZE = 1024*1024;

  static int NO_PIPE = -2;
  static int NEW_PIPE = -1;

  static int INFINITE_COST = 1000000;

  static int lr_costs[][];
  static int ud_costs[][];

  static boolean connected;
  static int lower_row;

  static int nbr_cols;
  static int nbr_rows;

  static HashMap old_costs;
  static HashMap new_costs;

  public static void main(String argv[]) throws Exception
  {
    int n;
    char ch;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    lr_costs = new int[MAX_SIZE][MAX_SIZE];
    ud_costs = new int[MAX_SIZE][MAX_SIZE];
    
    n = Integer.parseInt(br.readLine());

    for (int i=0; i< n; i++)
    {
      StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
      
      nbr_rows = Integer.parseInt(tok.nextToken());
      nbr_cols = Integer.parseInt(tok.nextToken());

      old_costs = new HashMap();
      new_costs = new HashMap();
      
      int fr[] = new int[nbr_cols];
      for (int j=0; j< nbr_cols; j++)
        fr[j] = NO_PIPE;
      Layer null_layer = new Layer(fr, 0);
    
      br.readLine();

      for (int row=0; row< nbr_rows; row++)
      {
        String str = br.readLine();

        for (int col=0; col< nbr_cols-1; col++)
        {
          ch = str.charAt(col*2+2);

          if ('0' <= ch && ch <= '9')
            lr_costs[row][col] = (int) (ch - '0');
          else
            throw(new Exception());
        }

        str = br.readLine();

        if (row < nbr_rows-1)
        {
          for (int col=0; col< nbr_cols; col++)
          {
            ch = str.charAt(2*col+1);

            if ('0' <= ch && ch <= '9')
              ud_costs[row][col] = (int) (ch - '0');
            else
              throw(new Exception());
          }
        }
      }

      // Init first lower layer
      int frontier[] = new int[nbr_cols];

      for (int j=0; j< nbr_cols; j++)
        frontier[j] = NO_PIPE;

      lower_row = -1;
      connected = false;
      extend_layer(frontier, 0, 0, NO_PIPE);

      for (lower_row=0; lower_row< nbr_rows-1; lower_row++)
      {
        old_costs = new_costs;
        new_costs = new HashMap();

        Iterator it = old_costs.values().iterator();
        while (it.hasNext())
        {
          Layer layer = (Layer) it.next();
          extend_layer(layer.frontier, 0, layer.cost, NO_PIPE);
        }
      }
      
      Layer layer = (Layer) new_costs.get(null_layer);
      System.out.println(layer.cost);
    }
  }

  static void extend_layer(int f[], int col, int cost, int from_left)
  {
    int frontier[] = new int[nbr_cols];

    for (int i=0; i< nbr_cols; i++)
      frontier[i] = f[i];

    if (col == nbr_cols)
    {
      if (from_left == NO_PIPE)
      {
          Layer layer = new Layer(frontier, cost);
         Layer layer2 = (Layer) new_costs.get(layer);
        if (layer2 != null)
        {
          if (cost < layer2.cost)
            layer2.cost = cost;
        }
        else
          new_costs.put(layer, layer);
      }
      else
        return;
    }
    else if (from_left == NO_PIPE)
    {
      if (frontier[col] == NO_PIPE)
      {
        // UR pipe
        frontier[col] = NEW_PIPE;  // REMOVE s鋞ts senare
        extend_layer(frontier, col+1, cost, col);
      }
      else
      {
        cost += ud_costs[lower_row][col];

        // DU pipe
        frontier[col] = frontier[col];  // REMOVE
        extend_layer(frontier, col+1, cost, NO_PIPE);

        // DR pipe
        int tmp = frontier[col];
        frontier[col] = NO_PIPE;
        extend_layer(frontier, col+1, cost, tmp);
      }
    }
    else
    {
      cost += lr_costs[lower_row+1][col-1];
      
      if (frontier[col] == NO_PIPE)
      {
        // LR pipe
        frontier[col] = NO_PIPE;  // REMOVE
        extend_layer(frontier, col+1, cost, from_left);

        // LU pipe
        frontier[col] = from_left;
        frontier[from_left] = col;
        extend_layer(frontier, col+1, cost, NO_PIPE);
      }
      else
      {
        cost += ud_costs[lower_row][col];

        // DL pipe
        if (from_left != col)
        {
          frontier[from_left] = frontier[col];
          frontier[frontier[col]] = from_left;
          frontier[col] = NO_PIPE;
          extend_layer(frontier, col+1, cost, NO_PIPE);
        }
        else if ((lower_row+2 == nbr_rows) && !connected)
        {
          connected = true;
          frontier[col] = NO_PIPE;
          extend_layer(frontier, col+1, cost, NO_PIPE);
          connected = false;
        }
      }
    }
  }
}

							

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

//* @author:alpc12
/* Sample solution to D - Pseudo random numbers / Mikael Goldmann
 * First count backwards to recreate the seed number 
 * The count forwards to get T:th number. Try using few columns to
 * save space.
 */
import java.io.*;
import java.util.*;


class Main 
{
    static BufferedReader stdin;
    
    int[][] tab;
    public static void main(String[] ss) throws IOException
    {
    Reader rdr = new InputStreamReader(System.in);
    stdin = new BufferedReader(rdr);
    int n = Integer.parseInt(stdin.readLine());
    for (int i = 1; i <= n; ++i) 
        (new Main()).solve(i);    
    }
    
    void solve(int casenum)  throws IOException
    {
    int i,j;
    
    int B = Integer.parseInt(stdin.readLine());
    String[] tok =stdin.readLine().split("[ ]+");
    int L = Integer.parseInt(tok[0]);
    int T = Integer.parseInt(stdin.readLine());
    int ncol=5;
    
    int[] vals = new int[L];
    for (i=1; i <= L; ++i) 
        vals[i-1] = Integer.parseInt(tok[i]);
    boolean ok=false;
    while(!ok) {
        ok = true;
        try{
        ncol *= 2;
        tab = newtab(L,ncol);
        for (i = 0; i < L; ++i)
            tab[i][0] = vals[i];
        for(i = L-1; i > 0; --i)
            if (! explain(tab,i, ncol, B)) {
            System.out.println("impossible");
            return;
            }
        }
        catch(ArrayIndexOutOfBoundsException e) {
        ok = false;        
        // Retry, doubling number of columns
        }
    }
    // Now tab[0] contains the seed numbers digits

    int ncol1=ncol+1; // One extra column
    
    /* Try finding values on the T:th row
     * If we fail and truncated any row, retry using
     * twice as many columns
     */
    int k;    
    while (true) {
        boolean fullrow = false; // no overflowing row yet
        int[][] v = new int[2][ncol1];
        for (i = 0; i < ncol; ++i)
        v[0][i] = tab[0][i];
        for (i = ncol; i < ncol1; ++i)
        v[0][i] = -1;

        int[] a,b=null;;
        int tmp;    
        ok = true;        
        for (k = 1; k < T; ++k) {
        a = v[1-(k&1)];
        b = v[k&1];
        for (i = 0; i < ncol1; ++i) b[i] = -1;
        
        for (i = 1, j = 0; j < ncol1 &&  i < ncol1; ++i) {
            if (a[i] == -1) break;
            
            tmp = a[i-1]+a[i];
            if (tmp < B) b[j++] = tmp;
            else {
            b[j++] = tmp-B;
            if (j < ncol1) b[j++] = 1;
            }
        }
        if (j == ncol1) fullrow=true;
        if (b[0] == -1) {
            ok = false;
            break;
        }
        }
        if (ok) {
        System.out.println(b[0]);
        return;
        }
        else if(!fullrow) {
        System.out.println("unpredictable");
        return;
        }
        ncol1 *=2;
    }
    }
    
    int[][] newtab(int r, int c) 
    {
    int[][] t = new int[r][c];
    int i,j;    
    for (i=0; i < r; ++i)
        for (j = 0; j < c; ++j) 
        t[i][j] = -1;
    return t;
    
    }
    
/* explain() computes row (i-1) from row i
 * Returns false if impossible. Used to calculate seed
 * from the given sequence
 */
    boolean explain(int[][] tab, int r, int ncol, int B)
    {
    int[] s = new int[ncol];
    int i,j;
    for (i=0; i < ncol; ++i) s[i] = -1;
    i=0;
    j=1;
    int s1,t1;    
    while (i < ncol && tab[r][i] != -1) {
        tab[r-1][j] = (B + tab[r][i] - tab[r-1][j-1]) % B;
        s1 = tab[r-1][j] + tab[r-1][j-1];
        ++i;
        ++j;
        
        if (s1 >= B) {
        if (tab[r][i] != -1 && tab[r][i] != 1) return false;
        ++i;
        }
    }
    return true;    
        
    }
    
}

							

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

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

#define null 0
#define y1 yy1
const int size = 510;
//size must be bigger than n and m.
//nС��mʱЧ�ʸ�
int maxmatch( int n, int m, bool w[][size], int *p)
{

    int p_n[size];
    int p_m[size];
    bool sign[size];
    int q[size],from[size],s,t;
    int i,j,link,now,h;
    memset( p_n, -1, sizeof(int)*n );
    memset( p_m, -1, sizeof(int)*m );
    for(i=0;i<n;i++)
    if(p_n[i]==-1)
    {
        memset( sign, 0, sizeof(bool)*m );
                s=1;link=-1;
        from[0]=-1;
        q[0]=size-1;
        p_m[size-1]=i;
        for(t=0;t<s;t++)
        {
           now=q[t];
           for(j=0;j<m;j++)
           {
               if( w[p_m[now]][j] != null && sign[j]==0 )
               {
                    sign[j]=1;
                    q[s]=j;
                    from[s++]=t;

                    if(p_m[j]==-1)
                    {
                        link=s-1;
                        break;
                    }
               }
           }
           if(j<m)break;
        }
        if(t<s)
        {
             while(from[link]!=-1)
             {
                    h=from[link];
                    p_m[q[link]]=p_m[q[h]];
                    p_n[p_m[q[h]]]=q[link];
                    link=h;
             }
        }

        //���걸ƥ��
        //else return 0;
    }
    int an;
    for(i=0,an=0;i<n;i++)
    {
        if(p)p[i]=p_n[i];
        if(p_n[i]>=0)an++;
    }
    return an;
}
bool e[size][size];
int begin[size], end[size];
int x1[size], y1[size], x2[size], y2[size], n;
inline int dis( int x1, int y1, int x2, int y2 )
{
    return abs( x1 - x2 ) + abs( y1 - y2 );
}
int main()
{
    int cas, n, i, j, a, b;    
    scanf( "%d", &cas );
    while( cas-- )
    {
        memset( e, 0, sizeof e );
        scanf( "%d", &n );
        for( i=0; i<n; i++ )
        {
            scanf( "%d:%d %d %d %d %d", &a, &b, x1+i, y1+i, x2+i, y2+i );
            begin[i] = a*60 + b;
            end[i] = begin[i] + dis( x1[i], y1[i], x2[i], y2[i] );
        }
        for( i=0; i<n; i++ )
        for( j=i+1; j<n; j++ )
            if( end[i] + dis( x2[i], y2[i], x1[j], y1[j] ) < begin[j] )
                e[i][j] = true;
        printf( "%dn", n - maxmatch( n, n, e, 0 ) );
    }
    return 0;
}
							

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

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

struct node
{
    int id;
    int num;
    int cost;
    int sigma_c;
    node *father;
    vector <node *> child;
    bool colored;

}t[1000];

struct cmp
{
    bool operator()( node *a, node *b )const
    {
        return a->sigma_c*b->num > b->sigma_c*a->num || ( a->sigma_c*b->num == b->sigma_c*a->num && a->id < b->id );
    }
};

multiset < node*, cmp > s;

int n, r;

bool init()
{
    int i, a, b;
    node nd;

    s.clear();

    scanf( "%d%d", &n, &r );
    if( n == 0 && r == 0 ) return false;
    
    r--;

    for( i=0; i<n; i++ )
    {
        scanf( "%d", &t[i].cost );
        
        t[i].id = i;
        t[i].num = 1;
        t[i].sigma_c = t[i].cost;
        t[i].colored = false;
        t[i].father = 0;
        t[i].child.clear();

        if( i != r ) s.insert( &t[i] );
    
    }

    for( i=0; i<n-1; i++ )
    {
        scanf( "%d%d", &a, &b );
        a--, b--;

        t[a].child.push_back( &t[b] );
        t[b].father = &t[a];
    }
    
    t[r].colored = true;

    return true;
}

void doit()
{
    int k, i;
    int ans;
    node *p, *f;
    multiset < node*, cmp >::iterator iter;

    k = 1, ans = t[r].cost;

    while( !s.empty() )
    {
        iter = s.begin();
        p = *iter;
        s.erase( iter );

        if( p->father->colored )
        {
            ans += k * p->sigma_c + p->cost ;
            p->colored = true;
            k += p->num;
            continue;
        }
        
        iter = s.find( p->father );
        f = *iter;
        s.erase( iter );

        f->cost += p->cost + p->sigma_c * f->num ; 
        f->num += p->num;
        f->sigma_c += p->sigma_c;
        
        for( i=0; i<p->child.size(); i++ )
            p->child[i]->father = f;
        
        f->child.insert( f->child.end(), p->child.begin(), p->child.end() );

        p->child.clear();

        s.insert( f );
    }

    printf( "%dn", ans );
}

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



							

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

import java.util.Scanner;

public class Main {
 private static Query[] query = new Query[1002];

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

  int i = 0;
  while (sc.hasNext()) {
   String s = sc.nextLine();
   if (s.equals("#")) {
    int k = sc.nextInt();
    slove(k, i);
    break;
   }
   String[] str = s.split(" ");
   Query q = new Query();
   q.d = Integer.parseInt(str[1].trim());
   q.w = Integer.parseInt(str[2].trim());
   q.p = q.w;
   insertHeap(q, i);
   i++;
  }
 }

 public static void slove(int k, int n) {
  // System.out.println("start.........");
 
  while (k > 0) {
   System.out.println(query[0].d);
   query[0].w += query[0].p;
   // System.out.println(query[0].w);
   keapHeap(n);
   --k;
  }

 }

 public static void keapHeap(int n) {

  Query q = query[0];
  // System.out.println(q.w + ";" + q.d);
  int i = 0;
  int j = (i << 1) + 1;
  while (j <= n - 1) {
   if (j < n - 1 && query[j].w > query[j + 1].w)
    j++;
   else if (j < n - 1 && query[j].w == query[j + 1].w
     && query[j].d > query[j + 1].d) {
    j++;
   }
   if (query[j].w < q.w) {
    query[i] = query[j];
    i = j;
   } else if (query[j].w > q.w)
    break;
   else if (query[j].w == q.w && query[j].d < q.d) {
    query[i] = query[j];
    i = j;
   } else
    break;
   j = (i << 1) + 1;
  }
  query[i] = q;
 }

 public static void insertHeap(Query q, int n) {
  // System.out.println("n = " + n);
  if (n == 0) {
   query[0] = q;
  } else {

   int i = n;
   int j = (i - 1) >> 1;

   while (j >= 0) {
    if (query[j].w > q.w) {
     query[i] = query[j];
     i = j;
    } else if (query[j].w == q.w && query[j].d > q.d) {
     query[i] = query[j];
     i = j;
    } else
     break;
    j = (i - 1) >> 1;
   }
   query[i] = q;
  }
 }

 static class Query {
  private int w;
  private int p;
  private int d;
 }
}


							

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define INF 30000
#define NMAX 201
int a[NMAX][NMAX];
int map[NMAX][NMAX][4];
int yp[4]={1,0,-1,0},xp[4]={0,1,0,-1};
int M,N;
int x,y,d,t;
void init()
{
    for(int i=0;i<=200;i++)
    {
        map[0][i][2]=-1;
        map[200][i][0]=-1;
        map[i][0][3]=-1;
        map[i][200][1]=-1;
    }
}
typedef struct 
{
    int y,x;
}DATA;
DATA que[NMAX*NMAX*100];
long front,end;
int enque(int y,int x)
{
    que[end].y=y;
    que[end].x=x;
    end++;
    return 1;
}
void HeapAdjust(int s,int m);
int deque(int &y,int &x)
{
    HeapAdjust(1,end-1);
    if(front==end)
    {
        y=0;
        x=0;
        return 0;
    }
    y=que[front].y;
    x=que[front].x;
    end--;
    DATA t;
    t=que[end];
    que[end]=que[front];
    que[front]=t;
    
    return 1;
}
void HeapAdjust(int s,int m)
{
    DATA rc;
    rc.x=que[s].x;
    rc.y=que[s].y;
    for(int j=2*s;j<=m;j*=2)
    {
        if(j<m&&a[que[j].y][que[j].x]>a[que[j+1].y][que[j+1].x])
            ++j;
        if(a[rc.y][rc.x]<=a[que[j].y][que[j].x])
            break;
        que[s]=que[j];
        s=j;
    }
    que[s].x=rc.x;
    que[s].y=rc.y;
}

void set(int v)
{
    int i;
    if(d==0)
    {
        for(i=x;i<x+t;i++)
        {
            map[y][i][2]=v;
            map[y-1][i][0]=v;
        }
    }
    else
    {
        for(i=y;i<y+t;i++)
        {
            map[i][x][3]=v;
            map[i][x-1][1]=v;
        }
    }
}
void solve()
{
    front=end=0;
    enque(0,0);
    a[0][0]=0;
    int cy,cx,p;
    while(deque(cy,cx))
    {
        for(p=0;p<4;p++)
        {
            if(map[cy][cx][p]!=-1)
            {
                if(a[cy+yp[p]][cx+xp[p]]>map[cy][cx][p]+a[cy][cx]||a[cy+yp[p]][cx+xp[p]]==-1)
                {
                    a[cy+yp[p]][cx+xp[p]]=map[cy][cx][p]+a[cy][cx];
                    enque(cy+yp[p],cx+xp[p]);
                }
            }
        }
        
    }

}    
int main()
{

#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int i;
    float ex,ey;
    scanf("%d%d",&M,&N);
    while(M!=-1)
    {
        memset(map,0,sizeof(map));
        memset(a,0xff,sizeof(a));
        init();
        for(i=0;i<M;i++)
        {    
            scanf("%d%d%d%d",&x,&y,&d,&t);
            set(-1);
        }
        for(i=0;i<N;i++)
        {    
            scanf("%d%d%d",&x,&y,&d);
            t=1;
            set(1);
        }
        scanf("%f%f",&ex,&ey);
        if(ex>=200||ey>=200)
        {
            printf("0n");
        }
        else
        {
            solve();
            if(a[(int)ey][(int)ex]!=-1)
                printf("%dn",a[(int)ey][(int)ex]);
            else
                printf("-1n");
        }
        scanf("%d%d",&M,&N);
    }
        
#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
							

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

/* @author: */
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    int n, s, t1, t2, t;
    while( sc.hasNext() )
    {
       n=sc.nextInt();
    if( n == 0 ) break;
    s = 0;
    for(int i=(int)Math.sqrt( n/4 ); i*i<=n; i++ )
    {
         t1=n-i*i;
      for(int j=(int)Math.sqrt( t1/3 ); j<=i && j*j<=t1; j++ )
      {
        t2=t1-j*j;
        for(int k=(int)Math.sqrt(t2/2) ; k<=j && k*k<=t2; k++ )
        {
        t = (int)Math.sqrt( t2 - k*k );
        if( t <= k && t*t == t2 - k*k )
           s++;
        }
      }
       }
    System.out.printf( "%dn", s );
    }
   }
}
							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = 0;   
        String str;   
        char[][] array;   
        while(true)   
        {   
            num = Integer.valueOf(cin.nextLine()).intValue();   
            if(num == 0)   
                break;   
            else  
            {   
                str = cin.nextLine();   
                array = convert(str, num);   
                System.out.println(getRawStr(array));   
            }   
        }   
    }   
       
    private static char[][] convert(String str, int col)   
    {          
        int toRight = 1;   
           
        int row = 0;   
        if(str.length()%col == 0)   
            row = str.length()/col;   
        else  
            row = str.length()/col + 1;   
           
        char[][] array = new char[col][row];   
           
        int index = 0;   
        for(int i = 0; i < row; i++)   
        {   
            if(toRight % 2 == 1)   
                for(int j = 0; j < col; j++)   
                    array[j][i] = str.charAt(index++);   
            else  
                for(int j = col-1; j >= 0; j--)   
                    array[j][i] = str.charAt(index++);   
               
            toRight++;   
        }   
           
        return array;   
    }   
       
    private static String getRawStr(char[][] array)   
    {   
        StringBuffer sb = new StringBuffer();   
        for(int i = 0; i < array.length; i++)   
            for(int j = 0; j < array[0].length; j++)   
                sb.append(array[i][j]);   
        return sb.toString();   
    }   
}  

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 
    int c[][]=new int[11][53],p[]=new int[11],r[]=new int[2],d[]=new int[11],count[]=new int[11];
    int casen,i,j,k,pn,top,discard,noanswer;
    casen=sc.nextInt();
    for(k=1;k<=casen;k++)
    {
      pn=sc.nextInt();
      for(i=0;i< pn;i++){count[i]=c[i][0]=0;p[i]=1;}
      c[0][0]=52;top=0;noanswer=0;r[0]=r[1]=0;
      for(i=1;i<=52;i++)
        c[0][i]=sc.nextInt();
      while(top< pn&&c[top][0]!=0)
      {
        if(noanswer!=0)break;
        discard=0;
        for(i=0;i< pn;i++)
        {
           if(discard!=0){
                 
            for(j=c[i][0];j>=p[i];j--)c[i][j+1]=c[i][j];
            c[i][0]++;
            c[i][p[i]]=discard;
            p[i]++;if(p[i]>c[i][0])p[i]=1;
        }    
        discard=0;
       if(c[i][0]!=0){                    
           count[i]++;if(count[i]>13)count[i]=1;
       if(c[i][p[i]]==count[i])
       {
       discard=count[i];if(top==i)r[1]=0;
       for(j=p[i];j< c[i][0];j++)c[i][j]=c[i][j+1];
       c[i][0]--;p[i]--;
       if(c[i][0]==0)d[i]=count[i];
       if(top==i&&c[i][0]==0)top++;
       }    
          else if(top==i&&r[1]==0){r[0]=p[i];r[1]=count[i];} 
          else if(top==i&&r[0]==p[i]&&r[1]==count[i])
             {noanswer=1;break;}  
          p[i]++;if(p[i]>c[i][0])p[i]=1;
      }    
     }    
   }    
   System.out.printf("Case %d:",k);
   if(noanswer!=0) System.out.printf(" unwinnablen");
   else {
         for(i=0;i< pn;i++) System.out.printf(" %d",d[i]);
         System.out.printf("n");
        }    
    }      
  }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
   String s=in.readLine();
   if(s.equals("0")) break;
   int l=s.length();
   int[] arr=new int[l];
   int count=0;
   for(int i=0;i< l-1;i++)
   {
    if(s.charAt(i+1)!='0')
    arr[count++]=s.charAt(i)-'0';
    else {
        arr[count++]=(s.charAt(i)-'0')*10;
    i++;
     }
    }
   if(s.charAt(l-1)!='0') arr[count++]=s.charAt(l-1)-'0';
   int[] arr2=new int[count+1];
   arr2[count-1]=arr2[count]=1;
   for(int i=count-2;i>=0;i--)
    {
    if((arr[i]*10+arr[i+1]>26)||arr[i+1]>9) arr2[i]=arr2[i+1];
    else{
        arr2[i]=arr2[i+1]+arr2[i+2];
    }
     }
   System.out.println(arr2[0]);
  }
 }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
 static int[] p;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
    int a=Integer.parseInt(in.readLine());
    if(a==0)break;
    double[][] dd=new double[a][4];
    for(int i=0;i< a;i++)
    {
      String[] ss=in.readLine().split(" ");
      for(int j=0;j< 4;j++)
        dd[i][j]=Double.parseDouble(ss[j]);
    }
    p=new int[a];
    for(int i=0;i< a;i++)
        p[i]=i;
    rir[] yy=new rir[7000];
    int len=0;
    for(int i=0;i< a;i++)
     for(int j=i+1;j< a;j++)
     {
      if(i==j) continue;
        double dis=(dd[i][0]-dd[j][0])*(dd[i][0]-dd[j][0])+
        (dd[i][1]-dd[j][1])*(dd[i][1]-dd[j][1])+
        (dd[i][2]-dd[j][2])*(dd[i][2]-dd[j][2]);
       dis=Math.sqrt(dis);
       dis-=dd[i][3];
       dis-=dd[j][3];
       if(dis< 0) dis=0;
         yy[len]=new rir(i,j,dis);
       len++;
    }
    Arrays.sort(yy,0,a*(a-1)/2);
    //for(int i=0;i< a*(a-1)/2;i++)
    //System.out.println(yy[i].juli+" "+yy[i].x+" "+yy[i].y);
    double sum=0;
    for(int i=0;i< len;i++)
    {
      if(un(yy[i].x,yy[i].y))
      {
       sum+=yy[i].juli;
      }
    }
    System.out.printf("%.3fn",sum);
            
  }
 }

  static int root(int x)
  {
   int b=x;
   while(p[b]!=b)
    b=p[b];
   return p[x]=b;
  }

  static boolean un(int a,int b)
  {
   int aa=root(a);
   int bb=root(b);
   if(aa==bb)return false;
   if(aa>bb)
    p[aa]=bb;
    else p[bb]=aa;
    return true;
  }
}

class rir implements Comparable< rir>
{
 int x;
 int y;
 double juli;
 public rir(int xx,int yy,double j)
 {
    x=xx;y=yy;juli=j;
 }
 @Override
 public int compareTo(rir o) {
    if(juli-o.juli< 0)return -1;
    if(juli==o.juli)return 0;
    else return 1;
 }
}
							

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

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

public class Main {

/**
 * @param args
 */
 static int max(int a,int b)
 {
   if(a>b) return a;
    return b;
 }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int k,n,m,a,b;
    int i,j;
        
    int DP[][] = new int[110][110];
        
    Scanner cin = new Scanner(System.in);
        
    while(cin.hasNext())
     {
    k = cin.nextInt();
    if(k==0) break;
    
    n = cin.nextInt();
    m = cin.nextInt();
    for(i=0;i< 110;++i) for(j=0;j< 110;++j)
        DP[i][j]=0;
    for(i=0;i< k;++i)
    {
        a = cin.nextInt();
        b = cin.nextInt();
        DP[a][b]=1;
    }
            
    a = cin.nextInt();
    b = cin.nextInt();
            
    for(i=1;i<=n;++i) for(j=1;j<=m;++j)
    {
        DP[i][j]=DP[i-1][j]+DP[i][j-1]-DP[i-1][j-1]+DP[i][j];
    }
            
    k = 0;
    for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(i>=a&&j>=b)
    {
        k = max(k,DP[i][j]-DP[i-a][j]-DP[i][j-b]+DP[i-a][j-b]);
    }
    System.out.println(k);
   }
        
 }
}

							

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

//* @author ������<hongxp11@163.com>
import java.awt.Label;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
   while (true) {

    int n = in.nextInt();
    int q = in.nextInt();
    if ((n | q) == 0)
          break;
      Map< Integer, Integer> map = new HashMap< Integer, Integer>();
      for (int i = 0; i < n; i++) {
       int m = in.nextInt();
       for (int j = 0; j < m; j++) {
       int temp = in.nextInt();
        if (map.get(temp) == null)
            map.put(temp, 1);
        else
            map.put(temp, map.get(temp) + 1);
        }
      }
    Set< Integer> key = map.keySet();
    int max = 0;
    int keyValue = 0;
    for (Integer i : key) {
        if (map.get(i) > max) {
            max = map.get(i);
            keyValue = i;
        }
        if (map.get(i) == max) {
            if (i <= keyValue)
                      keyValue = i;
        }
    }
    if (max < q)
        System.out.println(0);
    else
            System.out.println(keyValue);
    }
  }
}

							

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

import java.util.Scanner;   
  
/**  
 * POJ2027 easy  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int a = scan.nextInt();   
                int b = scan.nextInt();   
                if (a >= b) {   
                    System.out.println("MMM BRAINS");   
                } else {   
                        System.out.println("NO BRAINS");   
                }   
            }   
        }   
    }   
}