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

#include<iostream>
using namespace std;
int d=0,m=0;

inline void data(long g)
{cout<<g/10000<<"-";
g%=10000;if(g/1000==0)cout<<'0';
cout<<g/100<<"-";
g%=100;if(g/10==0)cout<<'0';
cout<<g<<' ';

}
inline void demerit()
{cout<<d<<" demerit point(s)."<<endl;}
inline void merit()
{cout<<m<<" merit point(s)."<<endl;}
inline void none()
{cout<<"No merit or demerit points."<<endl;}


int main()
{int k,key=0;
long g,a;
cin>>g;data(g);none();
while(m<5||key<1)
    {if(!key)cin>>a;if(cin.fail()){key=1;a=999999999;}
          do{
            g+=10000;
            if(a>=g&&d){data(g);if(d/2<d-2)d=d/2;else d=d-2;if(d<=0){d=0;none();}else demerit();}
            else {g+=10000;
                    if(a>=g&&m>=0){data(g);m++;merit();}
            }
    
            }while(a>g&&m<5);    

    if(!key){g=a;cin>>k;d+=k;data(g);
          if(d>2*m){d-=2*m;m=0;demerit();}
          else if(d<2*m){m=(m*2-d)/2;d=0;if(m)merit();else none();}
          else {m=0;d=0;none();}
            }
          
}
return 1;
}    
							

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

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


public class Main {
 public static void main(String[] args)
  {
  Scanner in = new Scanner(System.in);
   while(true)
    {
    String first = in.next();
    String second = in.next();
    //System.out.println(first.length()+" "+second.length());
    if(first.equals("0") && second.equals("0"))
    {
        break;
    }
    int carry = 0;
    int result = 0;
    int n = first.length();
    int k = 0;
    if(first.length() > second.length())
    {
        n = first.length();
        k = first.length() - second.length();
        for(int i = 0; i < k; i++)
            second = '0'+second;
    }
    else if(first.length() < second.length())
    {
        n = second.length();
        k = second.length() - first.length();
        for(int i = 0; i < k; i++)
            first = '0'+first;
    }
        
            
    //System.out.println("first:"+first+"second:"+second+"n:"+n+"k"+k);
    for(int i = n-1; i>=0; i--)
    {
        int m = (first.charAt(i)-'0')+(second.charAt(i) -'0')+carry;
        if(m>9)
        {
            result++;
            carry = 1;
        }
        else
            carry =0;
    }

            
    //�����
    if( result == 0)
    {
        System.out.println("No carry operation.");
    }
    else if(result == 1)
    {
        System.out.println("1 carry operation.");
    }
    else
    {
        System.out.println(result + " carry operations.");
    }    
  }
 }
}

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  static double INF=99999999.0;

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
  
  double p[][]=new double[101][101];
  double ax[]=new double[101];
  double ay[]=new double[101];
  double dis[]=new double[101];
  boolean used[]=new boolean[101];
    int n,i,j;
      n=sc.nextInt();
    for(i=0;i< n;i++){
          ax[i]=sc.nextDouble();
          ay[i]=sc.nextDouble();
        }
    for(i=0;i< n;i++)
        for(j=0;j< n;j++) p[i][j]=INF;
    for(i=0;i< n;i++)
     for(j=i+1;j< n;j++)
     {
      double v=(ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]);
      v=Math.sqrt(v);
      if(v< p[i][j])p[i][j]=p[j][i]=v;
     }
    for(i=0;i< n;i++)
        dis[i]=p[0][i];
       Arrays.fill(used,false);
    dis[0]=0;
    used[0]=true;
    double ans=0;
    for(i=0;i< n-1;i++)
    {
      double min=INF;
      int tag=-1;
      for(j=1;j< n;j++)
      {
        if(!used[j]&&dis[j]< min)
        {
        min=dis[j];
        tag=j;
         }
        }
        used[tag]=true;
        ans+=min;
        for(j=1;j< n;j++)
        {
        if(!used[j]&&dis[j]>p[tag][j])
            dis[j]=p[tag][j];
        }
     }
    System.out.printf("%3.2fn",ans);
    }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] p,b,c;
 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==0) break;
   p=new int[a+2];
   b=new int[a+1];
   c=new int[a+1];
   for(int i=1;i<=a;i++)
    p[i]=Integer.parseInt(ss[i]);
   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++)
     {
    long h=(long)p[i]*(b[i]+c[i]-1);
    max=Math.max(h, max);
     }
    System.out.println(max);
  }
 }
}
							

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

#include<iostream>
#include"string.h"
using namespace std;
int width[210],n;
int ans[210][210];
char fold[210];
bool init()
{
    int i,j;
    cin>>fold;
    if(cin.fail())return 0;
    n=strlen(fold);    
    for(i=0;i<n;i++)
    {
        for(j=1;i+j<n&&i-j>=0&&fold[i+j]+fold[i-j]=='A'+'V';j++)
            ;
        width[i]=j;
    }
    return 1;
}
inline int get_ans(int a,int b)
{
    return (a>b)?0:ans[a][b];
}
void doit()
{
    int i,j,k,t,s1,s2,l;    
    for(i=0;i<n;i++)
    ans[i][i]=1;
    for(l=1;l<n;l++)
    for(i=0;i+l<n;i++)
    {
        j=i+l;
        ans[i][j]=9999;
        for(k=i;k<=j;k++)
        if( ( j-k<k-i ? j-k:k-i ) < width[k] )
        {
            s1 = get_ans(i,k-1);
            s2 = get_ans(k+1,j);
            t= 1+( s1 > s2 ? s1:s2 );            
            if(t<ans[i][j])ans[i][j]=t;
        }
    }
}
int main()
{
    while(init())
    {
        doit();
        cout<<ans[0][n-1]<<endl;
    }
    return 0;
}    
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(in.hasNext())
  {
   String s=in.next();
   System.out.println("300 420 moveto");
   System.out.println("310 420 lineto");
   int b=0;
   int x=310;
   int y=420;
   for(int i=0;i< s.length();i++)
    {
    char c=s.charAt(i);
    if(b==0)
    {
       if(c=='A'){
         y-=10;
         b=1;
       }
       else {
        y+=10;
        b=3;
       }
         }
    else if(b==1)
     {
       if(c=='A'){
         x-=10;
         b=2;
       }
       else {
        x+=10;
        b=0;
       }
    }
    else if(b==2)
     {
       if(c=='A'){
         y+=10;
         b=3;
       }
       else {
        y-=10;
        b=1;
       }
    }
    else if(b==3)
     {
       if(c=='A'){
         x+=10;
         b=0;
       }
       else {
         x-=10;
         b=2;
       }
    }
    System.out.println(x+" "+y+" lineto");
     }
     System.out.println("stroke");
     System.out.println("showpage");
    }
 }
}
							

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

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

public class Main{
 static Scanner cin;

 static double ci = 2.09, cw = 4.19;
 static double em = 335; 

 public static void main(String args[]){
    cin = new Scanner(System.in);
    while(run())
            ;
 }

 static boolean run(){
  double mw = cin.nextDouble();
  double mi = cin.nextDouble();
  double tw = cin.nextDouble();
  double ti = cin.nextDouble();

  if((mw+mi)==0)
    return false;

  DecimalFormat df = new DecimalFormat("#0.0");
        
  double Energy = waterEnergy(mw, tw)+iceEnergy(mi, ti);
  double averE = Energy/(mw+mi);

  double iceThreshold = ci*30;
  double waterThreshold = iceThreshold+em;

  if(averE <= iceThreshold){
    double temp = -30+averE/ci;
    System.out.println(df.format(mw+mi)+" g of ice and 0.0 g of water at "+df.format(temp)+" C");
  }
  else if(averE < waterThreshold){
   double fmw = (mw+mi)*(averE-iceThreshold)/em;
   double fmi = mw+mi-fmw;
   System.out.println(df.format(fmi)+" g of ice and "+df.format(fmw)+" g of water at 0.0 C");
  }
  else{
   double temp = (averE-waterThreshold)/cw;
   System.out.println("0.0 g of ice and "+df.format(mw+mi)+" g of water at "+df.format(temp)+" C");
  }

  return true;
        
}

static double waterEnergy(double mw, double tw){
  double waterThreshold = ci*30+em;
  return mw*(waterThreshold+tw*cw);
 }

static double iceEnergy(double mi, double ti){
    return mi*(ti+30)*ci;
 }
}

							

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

#include"stdio.h"
#include"memory.h"
#include"list"
using namespace std;
long sign[5010];
long st[5010],s;
long ok[5010];
long v;
list<int> out[5000],in[5000];
void find(int a)
{list<int>::iterator iter;
    
    sign[a]=1;
    
    for(iter=out[a].begin();iter!=out[a].end();iter++)
    {
        if(sign[*iter]==0)find(*iter);
    }
    st[s++]=a;
}
int sink;
void find_too(int a)
{list<int>::iterator iter;
    sign[a]=sink;    
    for(iter=in[a].begin();iter!=in[a].end();iter++)
    {    
        if(sign[*iter]!=0&&sign[*iter]!=sink)ok[sign[*iter]]=1;                       
        if(sign[*iter]==0)find_too(*iter);        
    }    
}
int main()
{long e,i,a,b;
    while(1)
    {
        scanf("%ld",&v);
        if(v==0)break;
        scanf("%ld",&e);        
        for(i=0;i<v;i++)
        {
            out[i].clear();
            in[i].clear();
        }
        //mset(edge,0,sizeof(char)*5000*5000);
        for(i=0;i<e;i++)
        {
            scanf("%ld %ld",&a,&b);
            if(a!=b){
                out[a-1].push_back(b-1);
                in[b-1].push_back(a-1);
            }
        }
        s=0;
         memset(sign,0,sizeof(long)*5010);
         for(i=0;i<v;i++)
             if(!sign[i])find(i);
         memset(sign,0,sizeof(long)*5010);
         memset(ok,0,sizeof(long)*5010);         
         sink=1;
         for(i=v-1;i>=0;i--)
         {     
             if(sign[st[i]]==0)
             {find_too(st[i]);
                sink++;
             }
         }
         int key;
         for(i=0,key=0;i<v;i++)
         {     if(ok[sign[i]]==0){if(key)printf(" ");
                                
                                else key=1;
                            
                            printf("%ld",i+1);
                 
                            }
         }
         printf("n");        
    }
    return 0;
}



							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
  {
   ArrayList< Integer> a=new ArrayList< Integer>();
   for(int i=2;i< 35000;i++)
     a.add(i);
   int count=0;
   while(count< a.size())
    {
     for(int i=count+a.get(count);i< a.size();i+=a.get(count))
         a.set(i, 0);
     for(int i=0;i< a.size();i++)
         if(a.get(i)==0){
             a.remove(i);
         }
     count++;
    }     
    Scanner in=new Scanner(System.in);
    while(true)
    {
    int w=in.nextInt();
    if(w==0) break;
    System.out.println(a.get(w-1));
    }
 }
}
							

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

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


public class Main {
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  while(in.hasNext())
  {
    int input = in.nextInt();
    int result = 1;
    int begin = 1;
    while(true)
    {
    if(begin % input ==0)
        {
            System.out.println(result);
            break;
        }
    begin = begin%input;
    begin = begin*10 + 1;
    result ++;
    }
   }
 }
}

							

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


/**
 * Accepted.
 * 
 * @author Administrator
 *
 */
public class Main {

    private static Set< Long> set = new HashSet< Long>();

    private static Map< Long, List< String>> map = new HashMap< Long, List< String>>();

    private static Set< Long> sumSet = new HashSet< Long>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (true) {
            int n = cin.nextInt();

            if (n == 0) {
                break;
            }

            set.clear();
            sumSet.clear();

            map = new HashMap< Long, List< String>>();

            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = cin.nextInt();

                set.add(new Long(a[i]));
            }

            Arrays.sort(a);

            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (a[i] != a[j]) {
                        long temp = a[i];
                        temp += a[j];
                        sumSet.add(temp);
                    }
                }
            }


            for (int i = n - 1; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {

                    if (a[i] == a[j]) {
                        continue;
                    }

                    long v = a[i];
                    v -= a[j];

                    if (!sumSet.contains(v)) {
                        // System.out.println("v=" + v);
                        continue;
                    }

                    List<String> list = map.get(v);

                    if (list == null) {
                        list = new ArrayList<String>();
                        list.add("" + a[i] + " " + a[j]);
                    } else {

                        list.add("" + a[i] + " " + a[j]);
                    }

                    map.put(v, list);
                }
            }
            int ans = 0;
            boolean find = false;

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

                    long sum = a[i];
                    sum += a[j];
                    List< String> list = map.get(sum);
                    // System.out.println("list=" + list);

                    if (list != null) {
                        for (String s : list) {

                            String[] ss = s.split("[ ]+");

                            int d = Integer.parseInt(ss[0]);
                            int c = Integer.parseInt(ss[1]);

                            if (d != a[i] && d != a[j] && c != a[i] && c != a[j]) {
                                find = true;
                                ans = Math.max(ans, d);
                            }
                        }
                    }
                }
            }

            if (find) {
                System.out.println(ans);
            } else {
                System.out.println("no solution");
            }
        }
    }
}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;
import java.math.*;
public class Main {

    /**
     * @param args
     */
    static double min(double a,double b)
    {
        if(a>b) return b;
        return a;
    }
    static double max(double a,double b)
    {
        if(a>b) return a;
        return b;
    }
    public static double Number3(double pDouble)
    {
        String pattern = "##0.###";
        DecimalFormat df = new DecimalFormat(pattern);
        String result = String.valueOf(df.format(pDouble));
        System.out.println(result);
        pDouble = Double.parseDouble(result);
        return pDouble;
    }
    
  public static void main(String[] args)throws Exception {
   // TODO Auto-generated method stub
   double x1,y1,r1,x2,y2,r2,disten,ans;
        
   Scanner cin = new Scanner(System.in);
   while(cin.hasNext()){
    x1 = cin.nextDouble();
    y1 = cin.nextDouble();
    r1 = cin.nextDouble();
        
    x2 = cin.nextDouble();
    y2 = cin.nextDouble();
    r2 = cin.nextDouble();
        
    disten = Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
            
    if(disten>=r1+r2){
        ans = 0.0;
    }
    else if(disten+min(r1,r2)<=max(r1,r2)){
        ans = Math.acos(-1) * min(r1,r2) * min(r1,r2);
    }
    else
    {
    double ans1,ans2;
 ans1 = Math.acos((min(r1,r2)*min(r1,r2)+disten*disten-max(r1,r2)*max(r1,r2))/2.0/min(r1,r2)/disten);
 ans2 = Math.acos((max(r1,r2)*max(r1,r2)+disten*disten-min(r1,r2)*min(r1,r2))/2.0/max(r1,r2)/disten);
        ans = (r1+r2+disten)/2.0;
    ans = Math.sqrt(ans*(ans-r1)*(ans-r2)*(ans-disten));
    ans = max(r1,r2)*max(r1,r2)*ans2 + min(r1,r2)*min(r1,r2)*ans1 - 2.0*ans;
    }
    //    ans = Math.floor(ans*1000+0.5)/1000;
            
    DecimalFormat df = new DecimalFormat("##0.000");
    System.out.println(df.format(ans));
   }
}

}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  TreeSet< Long> t=new TreeSet< Long>();
  Scanner in=new Scanner(System.in);
  long a=in.nextInt();
  long b=in.nextInt();
  long c=in.nextInt();
  int d=in.nextInt();
  long[] arr=new long[d+1];
  arr[0]=1;
  int x1=0,x2=0,x3=0;
  for(int i=1;i<=d;i++)
  {
       long y1=arr[x1]*a;
    long y2=arr[x2]*b;
    long y3=arr[x3]*c;
    long min=Math.min(y1, y2);
    min=Math.min(min, y3);
    arr[i]=min;
    if(min==y1) x1++;
    if(min==y2) x2++;
    if(min==y3) x3++;
   }
   System.out.println(arr[d]);
        
  }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
 static BigInteger digit100=new BigInteger("1");
 static int t,a,b;
 static void start(){
    for(int i=0;i< 100;++i)
        digit100 = digit100.multiply(BigInteger.valueOf(10));
 }

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

  BigInteger num1,num2,temp,ans;
  start();
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  Scanner cin = new Scanner(System.in);
        
  while(cin.hasNext()){
    t = cin.nextInt();
    a = cin.nextInt();
    b = cin.nextInt();
    if((t==1||b==0||a< b)){
        output(BigInteger.valueOf(-1));
    }
    else if(a==0){
        output(BigInteger.valueOf(0));
    }
    else if(a==b){
        output(BigInteger.valueOf(1));
    }
    else if(a%b!=0||(a-b)*java.lang.Math.log10((double)t)>120){
        output(BigInteger.valueOf(-1));
    }
    else{
        temp = BigInteger.valueOf(t);
        num1 = temp.pow(a);
        num2 = temp.pow(b);
        num1 = num1.subtract(BigInteger.ONE);
        num2 = num2.subtract(BigInteger.ONE);
        ans = num1.divide(num2);
        if(ans.toString().length()< 100){
            output(ans);
        }else{
            output(BigInteger.valueOf(-1));
        }
    }
   }
 }

 static void output(BigInteger who){
  if(who.equals(BigInteger.valueOf(-1))){
   System.out.println("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) is not an integer with less than 100 digits.");
  }
  else{
   System.out.println("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) "+who);
  }
 }
}

							

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

//* @author  mekarlos@gmail.com
import java.util.Hashtable;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String[] s={"`1234567890-=","QWERTYUIOP[]","ASDFGHJKL;'","ZXCVBNM,./"};
        Scanner scan=new Scanner(System.in);
        s[1]+=(char)(92);
        String cad="",out="";
        Hashtable< String,String> table=new Hashtable< String,String>();
        for(int i=0;i< 4;i++){
            for(int j=1;j< s[i].length();j++){
                table.put(s[i].charAt(j)+"", s[i].charAt(j-1)+"");
            }
        }
        table.put(" ", " ");
        while(scan.hasNext()){
            cad=scan.nextLine();
            out="";
            for(int i=0;i< cad.length();i++){
                out+=table.get(cad.charAt(i)+"");
            }
            System.out.println(out);
        }
    }
}
							

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

//* @author:
import java.util.*;
public class Main {
 
static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   while( sc.hasNext())
   {
     double s=1,answer;
     int k=sc.nextInt();
     int n=sc.nextInt();
     double ans[][]=new double[n][k+1];
     for( int i=0; i< n; i++ )
    s *= (k+1);

     for(int  j=0; j<=k; j++ )
    ans[0][j] = 1/s;

     for(int  i=1; i< n; i++ )
    for(int j=0; j<=k; j++ )
    {
       ans[i][j] = ans[i-1][j];
       if( j!=0) ans[i][j] += ans[i-1][j-1];
       if( j< k ) ans[i][j] += ans[i-1][j+1];
    }
        
     answer = 0;
     for( int j=0; j<=k; j++ )
    answer += ans[n-1][j];
     System.out.printf( "%.5fn", answer*100 );
    }

   }
}


							

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

/* @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 cnt[]=new int[101];
 int temp[]=new int[101];
 boolean arr[]=new boolean[101];
 int n,p,i,j;
  n=sc.nextInt();
  p=sc.nextInt();
  Arrays.fill(cnt,0);
  Arrays.fill(arr,false);
  for(i=0;i< n;i++)
  {
    int max=0,min=999999;
    for(j=0;j< p;j++)
    {
          temp[j]=sc.nextInt();
          if(max< temp[j])max=temp[j];
       if(min>temp[j])min=temp[j];
    }
    for(j=0;j< p;j++)
    {
      if(temp[j]==min) cnt[j]++;
      if(temp[j]==max) arr[j]=true;
    }
   }
   boolean bb=false;
   for(i=0;i< p;i++)
   {
    if(arr[i]||n/2>=cnt[i]) continue;
    if(bb) System.out.printf(" ");
    System.out.printf("%d",i+1);
    bb=true;
   }
   if(!bb) System.out.println("0");
 }
}
							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            int[] data = new int[n];   
            int[] count = new int[n];   
            for (int i = 0; i < n; i++) {   
                int a = scan.nextInt();   
                data[i] = a;   
                count[i] = 1;   
                int max = count[i];   
                int flag = 0;   
                for (int j = i - 1; j >= 0; j--) {   
                    if (data[i] > data[j]) {   
                        if (count[j] > max) {   
                            max = count[j];   
                        }  
                        flag = 1;   
                    }   
                }   
                if (flag == 1) {   
                    count[i] = max + 1;   
                }   
            }   
            int max = count[0];   
            for (int i = 1; i < n; i++) {   
                if (count[i] > max) {   
                    max = count[i];   
                }   
            }   
            System.out.println(max);   
        }   
    }   
}  


							

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

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

 int c[][]=new int[22][22];
  int result=0;
  int n;
 boolean sign[]=new boolean[22];
 int v[]=new int[22];

 int find(int k,int a,int r){
     int temp=0;
     if(a+r<=result) return result;
     if(k==n+1){
          if(a>result) result=a;
          return result;         
     }      
     sign[k]=false;
     for(int i=1;i< k;i++) if(sign[i]) temp+=c[k][i]; find(k+1,a+temp,r-v[k]);
     sign[k]=true; temp=0;
     for(int i=1;i< k;i++) if(!sign[i]) temp+=c[i][k]; find(k+1,a+temp,r-v[k]);
     return result;
}

 int init(){
     Scanner sc=new Scanner(System.in);  
     int sum=0;
      n=sc.nextInt();
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
              c[i][j]=sc.nextInt();
              v[i]+=c[i][j];
         }
         sum+=v[i];
     }
    return sum;
 }

public static void main(String args[]){
   Main m=new Main();
     int sum=m.init();
    
     System.out.printf("%dn", m.find(1,0,sum));
   }
}


							

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

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

public class Main 
{
    public static int N = 10000;
    public static Node head;
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        Set< Integer> endpoints = new TreeSet< Integer>();
        Segment[] segments = new Segment[N];
        int t = sc.nextInt();
        while(t-- > 0)
        {
            int n = sc.nextInt();
            LinkedList< Node> nodes = new LinkedList< Node>();
            for(int i = 0; i < n; i++)
            {
                int s = sc.nextInt();
                int e = sc.nextInt();
                segments[i] = new Segment(s,e);
                endpoints.add(s);
                endpoints.add(e);
            }
            for(Integer endpoint : endpoints)
            {
                nodes.addLast(new Node(endpoint,endpoint,endpoint,endpoint));
            }
            head = buildSegmentTree(nodes);
            int result = 0;
            for(int i = n-1; i >= 0; i--)
            {
                Segment seg = segments[i];
                int left = seg.start;
                int right = seg.end;
                if(updateSegmentTree(left,right,head))
                {
                    result++;
                }
            }
            System.out.println(result);
        }
    }
    
    public static boolean updateSegmentTree(int left, int right, Node current)
    {
        boolean result;
        if(current.isCovered)
        {
            result = false;
        }else
        {
            if(left == current.left && right == current.right)
            {
                current.isCovered = true;
                result = true;
            }else
            {
                int leftEnd = current.leftEnd;
                int rightStart = current.rightStart;
                if(right <= leftEnd)
                {
                    result = updateSegmentTree(left,right,current.leftChild);
                }else if(left >= rightStart)
                {
                    result = updateSegmentTree(left,right,current.rightChild);
                }else
                {
                    boolean r1 = updateSegmentTree(left,leftEnd,current.leftChild);
                    boolean r2 = updateSegmentTree(rightStart,right,current.rightChild);
                    result = (r1 || r2);
                }
                current.isCovered = (current.leftChild.isCovered && current.rightChild.isCovered);
            }
        }
        return result;
    }
    
    public static Node buildSegmentTree(LinkedList< Node> current)
    {
        LinkedList< Node> next = new LinkedList< Node>();
        while(current.size() >= 2)
        {
            Node leftChild = current.removeFirst();
            Node rightChild = current.removeFirst();
            Node parent = new Node(leftChild.left,rightChild.right,leftChild.right,rightChild.left);
            parent.leftChild = leftChild;
            parent.rightChild = rightChild;
            next.add(parent);
        }
        if(current.size() > 0)
        {
            next.add(current.removeFirst());
        }
        if(next.size() >= 2)
        {
            return buildSegmentTree(next);
        }else // it's the root left
        {
            return next.removeFirst();
        }
    }
}

class Node
{
    int left;
    int right;
    int leftEnd;
    int rightStart;
    int mid;
    Node parent;
    Node leftChild;
    Node rightChild;
    boolean isCovered;
    
    Node(int left, int right, int leftEnd, int rightStart)
    {
        this.left = left;
        this.right = right;
        this.leftEnd = leftEnd;
        this.rightStart = rightStart;
        this.parent = null;
        this.leftChild = null;
        this.rightChild = null;
        this.isCovered = false;
    }
    
}

class Segment
{
    int start;
    int end;
    
    Segment(int s, int e)
    {
        this.start = s;
        this.end = e;
    }
}
							

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

#include "stdio.h"
#include "algorithm"
using namespace std;

struct point
{
    int x,y;
}p[10000];

inline bool cmp( point a, point b )
{
    return a.x < b.x || ( a.x == b.x && a.y < b.y );
}

int n;

int main()
{
    int cas,i,xx,yy;
    
    scanf( "%d", &cas );

    while( cas-- )
    {
        scanf( "%d", &n );
        
        for( i=0; i<n; i++ )
        {
            scanf( "%d %d", &p[i].x, &p[i].y );
        }

        sort( p, p+n, cmp );
        
        xx = p[0].x + p[n-1].x;
        yy = p[0].y + p[n-1].y;

        for( i=1; i<=n/2; i++ )
        {
            if( p[i].x + p[n-1-i].x != xx || p[i].y + p[n-1-i].y != yy )
                break;
        }

        if( i <= n/2 )printf( "non" );
        else printf( "yesn" );
    }

    return 0;
}


							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
public class Main {   
  
    public static void main(String[] args) {   
        final int MAXSIZE = 50001;   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        int caseI = 1;
        int max = 0;   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            int m = scan.nextInt();   
            if (n == 0 && m == 0) {   
                break;   
            }   
            DisjointSet dj = new DisjointSet(MAXSIZE);   
            int count = 0;   
            for (int i = 0; i < m; i++) {   
                int a = scan.nextInt();   
                int b = scan.nextInt();   
                int ra = dj.find(a);   
                int rb = dj.find(b);   
                if (ra != rb) {   
                    dj.union(ra, rb);   
                    count++;   
                }   
            }   
            max = n - count;   
            String result = "Case " + caseI + ": " + max;   
            System.out.println(result);   
            caseI++;   
        }   
    }   
}   
  
class DisjointSet {   
  
    protected int n;   
    protected int[] parent;   
    protected int[] rank;   
  
    public DisjointSet(int n) {   
        this.n = n;   
        init(n);   
    }   
  
    protected void init(int n) {   
        this.parent = new int[this.n + 1];   
        this.rank = new int[this.n + 1];   
        for (int i = 1; i <= n; i++) {   
            parent[i] = i;   
            rank[i] = 1;   
        }   
    }   
  
    protected int find(int x) {  
        if (parent[x] != x) {   
            parent[x] = find(parent[x]);   
        }   
        return parent[x];   
    }   
  
    protected void union(int ra, int rb) {   
        if (rank[ra] > rank[rb]) {   
            parent[rb] = ra;   
        } else if (rank[ra] < rank[rb]) {   
            parent[ra] = rb;   
        } else {   
            rank[rb]++;   
            parent[ra] = rb;   
        }   
    }   
}  


							

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

#include "iostream"
using namespace std;
int ans[230][11];
int get( int a, int b )
{
    int i;    
    if( b == 1 ) return 1;
    if( ans[a][b] < 0 )
    {
        ans[a][b] = 0;
        for( i=0; i*b<=a; i++ )
            ans[a][b] += get( a-i*b, b-1 );
    }
    return ans[a][b];
}
int main()
{
    int cas,n,m,k,s,i,j,t;
    for( i=0; i<=220; i++ )
    for( j=0; j<=10; j++ )
    ans[i][j] = -1;
    cin>>cas;
    while( cas-- )
    {
        cin>>m>>n>>k;
        m -= n;s=0;t=1;
        while( n > 1 )
        {
            
            for(i=0 ; s + get( m-i*n, n-1 ) < k; i++ )
            {
                s += get( m-i*n, n-1 );
            }            
            printf( "%dn", i+t );
            t += i;
            m -= i*n;
            n--;        }
        printf( "%dn", m+t );
    }
    return 0;
}
            


							

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

    import java.util.*;  
      
    public class Main {  
      
        public static void main(String[] args) {  
            Scanner cin = new Scanner(System.in);  
            while(cin.hasNext())  
            {  
                String tmp = cin.nextLine();  
               if(tmp.equals("0 0 0 0"))  
                   break;  
               String[] tmp1 = tmp.split(" ");  
               int N = Integer.valueOf(tmp1[0]);  
               int M = Integer.valueOf(tmp1[1]);  
               int P = Integer.valueOf(tmp1[2]);  
               int C = Integer.valueOf(tmp1[3]);  
                 
               int totalPaid = M + C;  
              int totalTrue = totalPaid - P;  
                 
               int earn = totalTrue - N - C;  
                
              System.out.println(earn*-1);  
                 
           }  
    
       }  
     
   }  

							

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

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef int type;
const type MAX_FEE = 1e8;
const int size = 210;
const int MAX = 1e8;
struct edge
{
    int c,f;
    type w;
    int from,to;
    int rev_i;
};
vector<edge> e[size];
type dis[size], fee, sum, rest;
bool sign[size];
edge *from[size];
int n, s, t;
int maxflow, add;
void clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i].clear();
    rest = 0;
}
bool dijstra( )
{
    int i, j, k, to, v;
    for( i=0; i<n; i++ )
        dis[i] = 999999;
    memset( sign, 0, sizeof(bool)*n );
    memset( from, 0, sizeof(edge * )*n );
    dis[ s ] = 0;
    for( i=0; i<n; i++ )
    {
        k = -1;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[j] < 999999 && ( k < 0 || dis[k] > dis[j] ) )
                k = j;
        if( k == -1 )
            break;
        sign[ k ] = true;
        for( j=0; j<e[k].size(); j++ )
        if( e[k][j].f != e[k][j].c )
        {    
            to = e[k][j].to;
            if( !sign[to] && e[k][j].f != e[k][j].c && dis[ to ] > ( v = dis[ k ] + e[k][j].w ) )
            {
                if( e[k][j].w < 0 )
                    while( printf( "ft" ) );

                dis[ to ] = v;
                from[ to ] = &e[k][j];
            }
        }
    }
    return sign[t] == true;
}
void increse( edge *ep, int d )
{
    ep->f += d;
    e[ep->to][ep->rev_i].f -= d;
}
void modify( )
{
    int i, j, temp;
    add = MAX; sum = 0;
    for( i=t; i!=s; i = from[i]->from )
    {
        sum += from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }
    sum += rest;
    rest += dis[t];
    
    for( i=t; i!=s; i = from[i]->from )
        increse( from[i], add );

    for( i=0; i<n; i++ )
    for( j=0; j<e[i].size(); j++ )
        e[i][j].w = dis[i] - dis[ e[i][j].to ] + e[i][j].w;

    return;
}
void insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, from, to, e[to].size() }, eg2 = { 0, 0, -w, to, from, e[from].size() };
    e[from].push_back( eg1 );
    e[to].push_back( eg2 );
}
type min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;    
    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }    
    if( flow )
        *flow = maxflow;

    return fee;
}
int shop[50][50];
int t_s[50], t_n[50];
int need[50][50];
int main()
{
    int n, m, k, i, j, l, f, ans;
    bool key;
    while( 1 )
    {
        scanf( "%d %d %d", &n, &m, &k );
        if( n == 0 ) break;
        for( i=0; i<k; i++ )
            t_s[i] = t_n[i] = 0;
        for( i=0; i<n; i++ )
        for( j=0; j<k; j++ )
        {
            scanf( "%d", &need[i][j] );
            t_n[j] += need[i][j];
        }
        for( i=0; i<m; i++ )
        for( j=0; j<k; j++ )
        {
            scanf( "%d", &shop[i][j] );
            t_s[j] += shop[i][j];
        }        
        for( i=0; i<k; i++ )
            if( t_s[i] < t_n[i] )
                break;
        if( i < k ) key = false;
        else key = true;
        ans = 0;
        for( l=0; l<k; l++ )
        {
            clear();
            if( key )
            {
                for( i=0; i<m; i++ )
                if( shop[i][l] )insert_edge( 0, i+2, shop[i][l], 0 );
        
                for( i=0; i<n; i++ )
                if( need[i][l] )insert_edge( i+2+m, 1, need[i][l], 0 );
            }
            for( i=0; i<n; i++ )
            for( j=0; j<m; j++ )
            {
                scanf( "%d", &f );
                if( key )
                    insert_edge( j+2, i+2+m, 10000, f );
            }
            if( key )
                ans += min_fee_max_flow( n+m+2, 0, 1, 0 );
        }
        if( key )
            printf( "%dn", ans );
        else
            printf( "-1n" );
    }
    return 0;
}



							

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

import java.io.*;
import java.util.*;
import java.math.*;

/**
 *
 * @author gongshaoqing
 */
public class Main {
private static  int  NULL=0;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int i, j, t;
        int m;
        BigInteger N, b[][], c,ans,temp;
        b = new BigInteger[102][102];
        b[1][1]=BigInteger.ONE;
        b[2][1]=BigInteger.ONE;
        b[2][2]=BigInteger.valueOf(2);
        for (i = 3; i <= 100; i++) {
            b[i][1]=BigInteger.ONE;
            for (j = 2; j <= i; j++) {
                if((i-1)< j)b[i-1][j]=BigInteger.ZERO;
                b[i][j]=b[i-1][j-1].add(b[i-1][j]);
                b[i][j]=b[i][j].multiply(BigInteger.valueOf(j));

            }
        }
        /*for(i=1;i<=100;i++)
        {   for(j=1;j<=i;j++)
                System.out.print(b[i][j]+" ");
            System.out.println();
        }*/
        t=cin.nextInt();
        while(cin.hasNext())
        {
            if(t==0)break;
            t--;
            N=cin.nextBigInteger();
            m=cin.nextInt();
            temp=N.add(BigInteger.ONE);

            ans=BigInteger.ZERO;
            for(i=1;i<=m;i++)
            {
                c=temp.multiply(N);
                temp=c.divide(BigInteger.valueOf(i+1));
                c=temp.multiply(b[m][i]);
                ans=ans.add(c);
                N=N.subtract(BigInteger.ONE);
                if(N.compareTo(BigInteger.ZERO)==0) break;
            }
            System.out.println(ans);
        }
        // TODO code application logic here
    }
}


							

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

//* @author:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
 int sum = 0;
 int time[] = new int[500000];
 int parent[] = new int[500000];
 int rank[] = new int[500000];
 trieT root;

 void ini() {
  root = new trieT();
  for (int i = 0; i < 500000; i++)
    parent[i] = i;
 }

public static void main(String[] args) throws IOException {
  BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
  Main p = new Main();
  p.ini();
  int a = 0;
  int b = 0;
  int qtime = 0;

  String tmp = re.readLine();
  while (tmp!=null) {

    a = p.insert(tmp.split(" ")[0].toCharArray(), p.root);
    b = p.insert(tmp.split(" ")[1].toCharArray(), p.root);
    p.time[a]++;
    p.time[b]++;
    tmp = re.readLine();
    if (a != b)
        p.union(a, b);
    }
    
  for (int i = 0; i < p.sum; i++)
    if (p.time[i] % 2 != 0)
        qtime++;
  int k = p.find(0);
  for (int i = 1; i < p.sum; i++)
    if (k != p.find(i)) {
         System.out.println("Impossible");
      return;
    }
  if (qtime <= 2)
    System.out.println("Possible");
  else
    System.out.println("Impossible");

 }


 int find(int x) {
   if (parent[x] != x) {
    parent[x] = find(parent[x]);
   }
  return parent[x];
 }

 void union(int a, int b) {
   int fa = find(a);
   int fb = find(b);
   if (fa == fb)
    return;
   if (rank[fa] > rank[fb])
    parent[fb] = fa;
   else if (rank[fa] < rank[fb])
    parent[fa] = fb;
   else {
    parent[fa] = fb;
    rank[fb]++;
   }
  }

  int insert(char[] key, trieT trie) {
   for (int i = 0; i < key.length; i++) {
    int index = key[i] - 'a';
    if (trie.child[index] == null) {
         trie.child[index] = new trieT();
    }
    trie = trie.child[index];
    }
    if (trie.count == -1)
    trie.count = sum++;
    return trie.count;
  }
}
class trieT {
    int count = -1;
    trieT child[] = new trieT[26];

    public trieT() {
         for (int i = 0; i < 26; i++)
        child[i] = null;

    }

}
							

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

#include <stdio.h>

int dx[]={ 0, 0, 1,-1,   1, 1,-1,-1,  1, 1, 2, 2,-1,-1,-2,-2 };
int dy[]={-1, 1, 0, 0,   1,-1, 1,-1, -2, 2,-1, 1,-2, 2,-1, 1 };
char map[8][9];
#define true '.'
#define false 'x'
inline bool inmap( int x, int y )
{
    return 0<=x && x<8 && 0<=y && y<8;
}
void doit( char c, int x, int y )
{
    int i, j, xx, yy;
    map[x][y] = 'o';
    switch( c )
    {
    case 'k':case 'K':
        for( i=0; i<8; i++ )
        {
            if( inmap( xx=x+dx[i], yy=y+dy[i] ) )
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'q': case'Q':
        for( i=0; i<8; i++ )
        for( j=1; j<8; j++ )
        {
            if( !inmap( xx=x+dx[i]*j, yy=y+dy[i]*j ) || map[xx][yy] == 'o' )
                break;
            
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'r': case'R':
        for( i=0; i<4; i++ )
        for( j=1; j<8; j++ )
        {
            if( !inmap( xx=x+dx[i]*j, yy=y+dy[i]*j )  || map[xx][yy] == 'o' )
                break;
            
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'b': case'B':
        for( i=4; i<8; i++ )
        for( j=1; j<8; j++ )
        {
            if( !inmap( xx=x+dx[i]*j, yy=y+dy[i]*j )  || map[xx][yy] == 'o' )
                break;
            
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'n': case'N':
        for( i=8; i<16; i++ )
        {
            if( inmap( xx=x+dx[i], yy=y+dy[i] ) )
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'p':
        for( i=4; i<6; i++ )
        {
            if( inmap( xx=x+dx[i], yy=y+dy[i] ) )
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    case 'P':
        for( i=6; i<8; i++ )
        {
            if( inmap( xx=x+dx[i], yy=y+dy[i] ) )
            if( map[xx][yy] == true ) 
                map[xx][yy] = false;
        }
        break;
    default: while(1)printf("faintn");
    }
    return;
}
int main()
{
    int xt[64],yt[64],s;
    int i, j, x, y;
    char c,ct[64];
    while( 1 )
    {
        x=0, y=0;
        for( i=0; i<8; i++ )
        for( j=0; j<8; j++ )
                map[i][j] = true;
        s = 0;
        while( 1 )
        {
            if( scanf("%c",&c ) != 1 )return 0;

            if( c >= '0' && c <= '9' ) y += c-'0';
            else if( c == '/' ) x++,y=0;
            else if( c =='n' ) break;
            else 
            {
                xt[s] = x;
                yt[s] = y;
                ct[s] = c;
                map[x][y] = 'o';
                s++;
                y++;
            }
        }
        while( s-- )
            doit( ct[s], xt[s], yt[s] );
        int ans;
        ans = 0;
        for( i=0; i<8; i++ )
        for( j=0; j<8; j++ )
            if( map[i][j] == true ) ans ++;
        printf( "%dn", ans );

    }
    return 0;
}
							

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

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <algorithm>
using namespace std;
char word[2500][100];
char mem[2500][100];
int v[2500];
int e[2500][2500];
int d[2500];
int id[2500];
int ans[2500][10];
int from[2500][10];
int n;
bool cmp( int a, int b )
{
    return strcmp( word[a], word[b] ) > 0;
}
bool check( int a,int b )
{
    char *p = word[a], *q = word[b];
    while( *p && *q && *p != *q )
        p++,q++;
    return *p == '' || *q == '' ;
}
void init()
{
    int i, j, k;
    scanf( "%d", &n );
    for( i=0; i<n; i++ )
    {
        scanf( "%d", &v[i] );        
        gets( word[i] );
        strcpy( mem[i], word[i] );
        for(j=0, k=0; word[i][j]; j++ )
        {
            if( word[i][j] >= 'A' && word[i][j] <= 'Z' ) word[i][j] += 'a' - 'A';
            
            if( word[i][j] >= 'a' && word[i][j] <= 'z' ) word[i][ k++ ] = word[i][j];
        }
        word[i][k] = '';
        id[i] = i;
    }
    std::sort( id, id+n, cmp );
    for( i=0; i<n; i++ )
    {
        d[i] = 0;
        for( j=0; j<i; j++ )
        if( check( id[i], id[j] ) )
            e[i][ d[i]++ ] = j;
    }
    memset( ans, -1, sizeof(ans) );

}
int main()
{
    int i, j, k, h, value;
    init();
    for( i=0; i<n; i++ )
    {
        value = ans[i][0] = v[ id[i] ];
        
        for( j=0; j<d[i]; j++ )
        {
            k = e[i][j];
    
            for( h=0; h<9; h++ )
                if( ans[i][h+1] < 0 || ans[k][h] + value > ans[i][h+1] )
                {
                    ans[i][h+1] = ans[k][h] + value;
                    from[i][h+1] = k;
                }
        }
    }    
    value = -1;
    for( i=0; i<n; i++ )
    for( j=0; j<10; j++ )
    {
        if( ans[i][j] > value )
        {
            k = i;
            h = j;
            value = ans[i][j];
        }
    }
    printf( "%dn", h+1 );
    printf( "%dn", value );
    while( h>=0 )
    {
        for( i=0; mem[id[k]][i] == ' '; i++ );
        for( ;mem[id[k]][i]; i++ )
            printf( "%c", mem[id[k]][i] );        
        printf( "n" );
        k = from[k][h];
        h--;
    }
    return 0;
}
							

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

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


public class Main {
    public static void main(String[] args)
    {
    Scanner in = new Scanner(System.in);
    while(in.hasNext())
    {
        int n = in.nextInt();
        int k = in.nextInt();
        int temp = n;
        int add = 0;
        while(n>=k)
        {
            
            int diff = n/k;
            add = add + diff;
            n = diff  + n - (n/k)*k;
    
        }
        System.out.println(temp+add);
    }
  }
}

							

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

//* @author:
import java.util.*;
public class Main {
 
static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   double r, h, d1, a1, d2, a2, dg, l, s, a;

   while(sc.hasNext())
   {
      r=sc.nextDouble();
      h=sc.nextDouble();
      d1=sc.nextDouble();
      a1=sc.nextDouble();
      d2=sc.nextDouble();
      a2=sc.nextDouble();
      l = Math.sqrt( r*r + h*h );
      dg = 2*r*Math.PI / l;
      a = Math.abs(a1-a2);
      if( a > 180 ) a = 360 - a;
      a = a / 360 * dg;
      s = Math.sqrt( d1*d1 + d2*d2 - 2*d1*d2*Math.cos( a ) );
    System.out.printf( "%.2fn", s );
    }

   }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{    
 public static void main(String[] args) throws IOException
  {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(in.ready())
   {
    String[] ss=in.readLine().split(" ");
    double x=Double.parseDouble(ss[0]);
    double y=Double.parseDouble(ss[1]);
    double c=Double.parseDouble(ss[2]);
    double max=Math.min(x, y),min=0;
    for(int i=0;max-min>0.00001;i++)
    {
         double mid=(min+max)/2;
     double d1=Math.sqrt(x*x-mid*mid);
     double d2=Math.sqrt(y*y-mid*mid);
     if(c*(d1+d2)==(d1*d2)){
        min=max=mid;
            break;
     }
    else if(c*(d1+d2)>(d1*d2)) max=mid;
    else min=mid;
       }
       System.out.printf("%.3fn",(min+max)/2);
    }
  }
}
							

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

import java.util.*;
import java.math.*;
public class Main{
 static BigInteger[] ans;
 public static void main(String args[])
  {
   Scanner sc=new Scanner(System.in);
   ans=new BigInteger[251];
   ans[0]=BigInteger.valueOf(1);
   ans[1]=BigInteger.valueOf(1);
   ans[2]=BigInteger.valueOf(3);
   for(int i=3;i<=250;i++)
    ans[i]=ans[i-1].add(ans[i-2].multiply(BigInteger.valueOf(2)));
   while(sc.hasNextInt()){
    int n=sc.nextInt();
    System.out.println(ans[n]);
   }
  }
}


							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
    Scanner in=new Scanner(System.in);
    while(in.hasNext())
    {
    double m=in.nextDouble();
    while(m>18)
        m/=18;
    System.out.println(m>9?"Ollie wins.":"Stan wins.");
    }
  }
}

							

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

/* @author: */
import java.util.Scanner;
public class Main{
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
int n;
double xx1,xx2,xx3,yy1,yy2,yy3,x,y,mnx,mxx,mny,mxy;
  
    int t=1;
    while(sc.hasNext())
    {
           n=sc.nextInt();
           if(n==0) break;
           xx1=sc.nextDouble();
           yy1=sc.nextDouble();
           xx2=sc.nextDouble();
           yy2=sc.nextDouble();
           xx3=sc.nextDouble();
           yy3=sc.nextDouble();
        double A1=2*(xx1-xx2);
        double A2=2*(xx1-xx3);
        double B1=2*(yy1-yy2);
        double B2=2*(yy1-yy3);
        double C1=xx1*xx1+yy1*yy1-xx2*xx2-yy2*yy2;
        double C2=xx1*xx1+yy1*yy1-xx3*xx3-yy3*yy3;
        double J=A1*B2-A2*B1;
        x=(C1*B2-C2*B1)/J;
        y=(A1*C2-A2*C1)/J;
        mnx=mny=999999999;
        mxx=mxy=-999999999;
        double angle=2*3.14159265358979/n;
        double xx,yy;
        for(int i=0;i< n;i++)
        {
         xx=Math.cos(i*angle)*(xx1-x)-Math.sin(i*angle)*(yy1-y)+x;
         yy=Math.sin(i*angle)*(xx1-x)+Math.cos(i*angle)*(yy1-y)+y;
         if(xx< mnx)mnx=xx; 
         if(xx>mxx)mxx=xx;
         if(yy< mny)mny=yy;
         if(yy>mxy)mxy=yy;
        }
        mxx=mxx-mnx;
        mxy=mxy-mny;
        System.out.printf("Polygon %d: %.3fn",t,mxx*mxy);
        t++;
    }
  }
}
							

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

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

public class Main{
 double max = Double.MAX_VALUE;
 int fin[] = new int[205];
 double d[] = new double[205];
 double dis[][] = new double[205][205];
 pos p[] = new pos[205];

 void initial() {
  for (int i = 0; i < 205; i++)
    p[i] = new pos();
  Scanner s;
  int n = 2;
  try {
    s = new Scanner(System.in);
    p[0].x = s.nextInt();
    p[0].y = s.nextInt();
    p[1].x = s.nextInt();
    p[1].y = s.nextInt();

    int flag = 0;
    while (s.hasNext()) {
    p[n].x = s.nextInt();
    p[n].y = s.nextInt();
    if (p[n].x == -1 && p[n].y == -1) {
         flag = 0;
      continue;
    }
    if (flag == 1) {
      dis[n][n - 1] = dis[n - 1][n] = Math
       .sqrt((p[n].x - p[n - 1].x) * (p[n].x - p[n - 1].x)
       + (p[n].y - p[n - 1].y)
       * (p[n].y - p[n - 1].y)) / 40000;
    }
    n++;
    flag = 1;
     }
   } catch (Exception e1) {
   }

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
         if (i != j && dis[i][j] == 0)
        dis[i][j] = dis[j][i] = (Math.sqrt((p[j].x - p[i].x)
        * (p[j].x - p[i].x) + (p[j].y - p[i].y)
        * (p[j].y - p[i].y))) / 10000.0;

  fin[0] = 1;
  for (int i = 0; i < n; i++)
    d[i] = dis[0][i];
  int v = 0;
  for (int i = 1; i < n; i++) {
    double min = max;
       for (int j = 0; j < n; j++)
          if (fin[j] != 1)
            if (d[j] < min) {
           v = j;
           min = d[j];
         }
        fin[v] = 1;
        for (int w = 0; w < n; w++)
          if (fin[w] != 1 && (min + dis[v][w] < d[w]))
            d[w] = min + dis[v][w];

    }
    double ans = 60.0 * d[1];
    System.out.println(Math.round(ans));
 }

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

class pos {
    int x = 0;
    int y = 0;
}
							

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

//* @author 
import java.io.*; 
import java.util.*; 
import java.text.DecimalFormat; 

public class Main 
{ 
    static int hh; 
    static int mm; 
    static int ss; 
    static double sumDist; 
    static double speed; 
    public static void main(String[] args) throws Exception 
    { 
        readFile(); 
    } 

    static void readFile() throws Exception 
    { 
        BufferedReader br = new BufferedReader( 
            //new FileReader("in.in")); 
            new InputStreamReader(System.in)); 
        StringTokenizer st = null; 
        String stemp = null; 
        while((stemp=br.readLine())!=null) 
        { 
            st = new StringTokenizer(stemp," "); 
            if(st.countTokens()==2) 
            { 
                stemp = st.nextToken(); 
                double tempspeed = Double.valueOf(st.nextToken()) / 3600; 
                st = new StringTokenizer(stemp,":"); 
                process(Integer.valueOf(st.nextToken()), 
                    Integer.valueOf(st.nextToken()), 
                    Integer.valueOf(st.nextToken()),-1); 
                speed = tempspeed; 
            } 
            else 
            { 
                st = new StringTokenizer(st.nextToken(),":"); 
                process(Integer.valueOf(st.nextToken()), 
                    Integer.valueOf(st.nextToken()), 
                    Integer.valueOf(st.nextToken()),1); 
            } 
        } 
    } 
    static int fff = 0; 
     
    static void process(int h,int m,int s,int flag) 
    { 
        int sumSecond = 0; 
        sumSecond += (s-ss); 
        sumSecond += ((m-mm)*60); 
        sumSecond += ((h-hh)*3600); 
        sumDist += (sumSecond * speed); 
        if(flag==1) 
        { 
            if(fff!=0) 
                System.out.println(); 
            fff++; 
            display(h,m,s); 
            System.out.print(saveDigit(sumDist,2)); 
            System.out.print(" km"); 
        } 
        hh = h; 
        mm = m; 
        ss = s; 
    } 
     
    static String saveDigit(double d,int n) 
    { 
        StringBuffer sb = new StringBuffer("###."); 
        for(int i=0; i< n; i++) 
            sb.append("0"); 
        DecimalFormat df2  = new DecimalFormat(sb.toString()); 
        StringBuffer result = new StringBuffer(df2.format(d)); 
        if(result.indexOf(".")==0) 
            result.insert(0,"0"); 
        return result.toString(); 
    } 
     
    static void display(int h,int m,int s) 
    { 
        if(h< 10) 
            System.out.print("0"); 
        System.out.print(h+":"); 
        if(m< 10) 
            System.out.print("0"); 
        System.out.print(m+":"); 
        if(s< 10) 
            System.out.print("0"); 
        System.out.print(s+" "); 
    } 
}
							

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

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;


int n,c,g;
double d,r;
const double pi = 3.1415926535898;
const double eps = 1e-8;

double area(int a, int b, int c )
{
    double l1, l2;
    l1 = sin( pi*abs(a-b)/n ) * r;
    l2 = sin( pi*abs(b-c)/n ) * r;
    return l1 * l2 * sin( pi*abs(a-c)/n ) * 2;
}

int id[1000];

void init()
{
    int k;

    cin>>d>>n>>c>>g;
    r = d *100 / 2;

    id[0] = 0;
    for( k=1; k<c; k++ )
        id[k] = ( id[k-1] + g ) % n;
    
    sort( id, id+c );
    c = unique_copy( id, id+c, id ) - id;
}

int main()
{
    int i, j, k, cas, h;
    double s, s1, s2, t1, t2;
    
    cin>>cas;
    for( h=1; h<=cas; h++ )
    {
        init();

        s = 0;
        for( i=2, j=1, k=3; i < c-1; i++ )
        {
            if( k < i+1 ) k = i+1;

            s1 = area( 0, id[j], id[i] );
            s2 = area( id[i], id[k], 0 );

            while( j+1 < i && ( t1 = area( 0, id[j+1], id[i] ) ) - s1 > -eps )
            {
                s1 = t1;
                j++;
            }

            while( k+1 < c && ( t2 = area( 0 , id[i], id[k+1] ) ) - s2 > -eps )
            {
                s2 = t2;
                k++;
            }
            if( s1 + s2 - s > -eps ) s = s1 + s2;
        }
        printf( "Scenario #%d:n%.6lfnn", h, s/10000 );
    }

    return 0;
}



							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int cnt=0;
  while((a--)!=0)
  {
   int b=in.nextInt();
   int c=in.nextInt();
   cnt++;
   int d=0,e=0;
   while(true)
   {
    if(b>c)
    {
     d+=b/c;
     b=b%c;
     if(b==0) break;
    }
    else
    {
    e+=c/b;
    c=c%b;
    if(c==0) break;
     }
    }
    if(b==0) d--;
    if(c==0) e--;
    System.out.println("Scenario #"+cnt+":");
    System.out.println(d+" "+e);
    System.out.println();
   }
 }
}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int count=1;
  int[] arr=new int[]{9,3,7};
  while((a--)!=0)
  {
   String s=in.next();
   int total=0;
   int k=0;
   int p=0;
   int t=s.length();
   for(int i=t-1;i>-1;i--)
   {
    char c=s.charAt(i);
    if(c!='?')
    {
         int w=c-48;
     total+=w*arr[(t-1-i)%3];
    }
    if(c=='?')
    {
     k=arr[(t-1-i)%3];
     p=i;
    }
    }
    for(int i=0;i< 10;i++)
    {
    if((total+i*k)%10==0)
    {
     System.out.println("Scenario #"+count+":");
     System.out.println(s.substring(0,p)+i+s.substring(p+1));
     System.out.println();
     break;
    }
     }
    count++;
            
   }
 }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int cnt=0;
  while((a--)!=0)
  {
   cnt++;
   String[] ss=in.readLine().split(" ");
   int t=Integer.parseInt(ss[0]);
   int w=Integer.parseInt(ss[1]);
   int[] p=new int[w];
   ss=in.readLine().split(" ");
   for(int i=0;i< w;i++)
    p[i]=Integer.parseInt(ss[i]);
   Arrays.sort(p);
   int sum=0,i,j;
   for(i=0;i< w;i++)
   {
    if(t< p[i])break;
    t-=p[i];
   }
   for(j=0;j< i;j++)
     sum+=(i-j)*p[j];
   System.out.println("Scenario #"+cnt+":");
   System.out.println("Steve wins with "+i+" solved problems and a score of "+sum+".");
   System.out.println();
  }
 }
}
							

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

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

int e[100][100];
int n;
int p;
int a[10000];

int main()
{
    int cas, i, j, l, k, ans;
    
    scanf( "%d", &cas );
    
    for( l=1; l<=cas; l++ )
    {
        scanf( "%d", &p );
        scanf( "%d", &n );
        
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf( "%d", &e[i][j] );


        for(k=0;k<n;k++)
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(e[i][k]>=0 && e[k][j]>=0 
                && ( e[i][k] + e[k][j] < e[i][j] || e[i][j] < 0 ) )
                e[i][j] = e[i][k] + e[k][j];

        k = 0;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if( i != j  )
            a[k++] = e[i][j];

        std::sort( a, a+k );
        
        if( ( k*p ) % 100 == 0 )ans = ( k*p ) / 100-1;
        else ans = ( k*p ) / 100 ;
        
        printf( "Scenario #%d:n", l );
        printf( "%dnn", a[ans] );
    }

    return 0;
}
							

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

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

public class Main {

/**
 * @param args
 */
public static void main(String[] args)throws Exception {
    // TODO Auto-generated method stub
    int a,b,c,d,t,i;
    
    Scanner cin = new Scanner(System.in);
    
    t = cin.nextInt();
    for(i=1;i<=t;++i){
        a = cin.nextInt();
        b = cin.nextInt();
        c = cin.nextInt();
        d = cin.nextInt();
            
        System.out.print("Scenario #"+i);
        System.out.println(":");
        if((a+b+c+d)%2==1)
            System.out.println("1");
        else
            System.out.println("0");
        System.out.println("");
    }
  }

}

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static my[] p;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int cnt=0;
  while((a--)!=0)
  {
   cnt++;
   String[] ss=in.readLine().split(" ");
   int n=Integer.parseInt(ss[0]);
   p=new my[n+1];
   for(int i=0;i<=n;i++)
     p[i]=new my(i);
   int t=Integer.parseInt(ss[1]);
   boolean bb=true;
   while((t--)!=0)
   {
    ss=in.readLine().split(" ");
    if(bb)
    {
          int x1=Integer.parseInt(ss[0]);
      int x2=Integer.parseInt(ss[1]);
      int r1=root(x1),r2=root(x2);
      if(r1< r2){
        p[r2].root=r1;
        p[x2].d=(p[x1].d+1)%2;
      }
      else if(r1>r2){
        p[r1].root=r2;
        p[x1].d=(p[x2].d+1)%2;
      }
      else if(p[x2].d==p[x1].d)bb=false;
    }
     }
     System.out.println("Scenario #"+cnt+":");
     if(bb)System.out.println("No suspicious bugs found!");
     else System.out.println("Suspicious bugs found!");
     System.out.println();
  }
 }

 static int root(int a)
  {
    int u=a;
    while(p[a].root!=a)a=p[a].root;
    p[u].root=a;
    return a;
  }
    
}

 class my
 {
    int root;
    int d=0;
    public my(int r)
    {
        root=r;
    }
 }

							

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

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


int next[400];
bool ishead[400];

char w1[400][100],w2[400][100];

int main()
{
    int cas, i, n, j, k = 0;
    

    scanf( "%d", &cas );
    
    while( cas-- )
    {
        scanf( "%d", &n );
        n--;        

        for( i=0; i<n; i++ )
        scanf( "%s%s",w1[i],w2[i] );

        for( i=0; i<n; i++ )
        next[i] = -1, ishead[i] = true;

        for( i=0; i<n; i++ )
        for( j=0; j<n; j++ )
        if( i != j && strcmp( w2[i], w1[j] ) == 0 )
        {
            next[i] = j, ishead[j] = false;
            break;
        }

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

        printf( "Scenario #%d:n", ++k );

        printf( "%sn", w1[i] );
        for( ; i >= 0; i = next[i] )
        printf( "%sn", w2[i] );

        printf( "n" );
    } 

    return 0;
}
							

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

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


struct point
{
    int x,y;
};

struct line
{
    point a,b;
    int dx,dy;
}l[100001];

int n;
__int64 ans;


inline double crossproduct(point o, point a, point b)
{
    return (double)(a.x-o.x)*(b.y-o.y) - (double)(a.y-o.y)*(b.x-o.x);
}

void normal(line &l)
{
    if( l.a.x>l.b.x || ( (l.a.x==l.b.x) && l.a.y>l.b.y )  )
        swap( l.a, l.b );
}

void qiu( line &l)
{
    l.dx = l.b.x-l.a.x;
    l.dy = l.b.y-l.a.y;
}

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

bool cmp1( line l1, line l2 )
{
    double temp = (double)l1.dx*l2.dy-(double)l2.dx*l1.dy;
    if( temp >  0 )
        return 1;

    if( temp == 0 && crossproduct( l1.a,l2.b,l2.a ) > 0 )
        return 1;
    
    return 0;
}

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

bool cmp2( line l1, line l2 )
{
    if( l1.dx == 0 )
        return l1.a.y<l2.a.y||(l1.a.y==l2.a.y&&l1.b.y<l2.b.y);
    else
        return l1.a.x<l2.a.x||(l1.a.x==l2.a.x&&l1.b.x<l2.b.x);
}



//////////////////////////////////////////////////////////
inline int low_it(int a)
{
    return a&(a^(a-1));
}


int a[200010];
int m;

void set(int i)
{
    for(;i<=m;i+=low_it(i))
    {
        a[i]++;
    }
}

int count(int i)
{
    int ans=0;
    for(;i>0;i-=low_it(i))
    {
        ans+=a[i];
    }
    return ans;
}

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

int v[200100];

int find(int value )
{
    int a=1,b=m,c;
    
    while(a<=b)
    {
        c=(a+b)/2;
        if( v[c]-value == 0 )
            return c;
        else if(v[c]<value)a=c+1;
        else b=c-1;
    }

    while(1)
    {
        printf("asdf");
    }
    return -1;

}

void calc( int begin, int end )
{
    int i,k,temp,h;

//    for(i=begin;i<end;i++)
//        printf(":::%d  %d - %d %dn", l[i].a.x, l[i].a.y, l[i].b.x, l[i].b.y );
//    printf("n");

    for( i=begin; i<end; i++ )
    if( l[i].dx !=0  )
    {
        v[(i-begin)*2+1] = l[i].a.x;
        v[(i-begin)*2+2] = l[i].b.x;
    }
    else 
    {
        v[(i-begin)*2+1] = l[i].a.y;
        v[(i-begin)*2+2] = l[i].b.y;
    }

    sort( v+1, v+1+(end-begin)*2 );
    m = std::unique_copy( v+1, v+1+(end-begin)*2, v+1 ) - (v+1);


    memset( a,0,sizeof(int)*(m+5) );

//__int64 tm=ans;

    for( i=begin; i<end; i++ )
    {
        if( l[i].dx != 0 )
            k = find( l[i].a.x ), h = find( l[i].b.x ); 
        else k = find( l[i].a.y ), h = find( l[i].b.y );

        temp = i-begin-count(k);
        ans += temp;
        set(h);
    }
//printf(":%I64dn",ans-tm);
}

void init()
{
    int i;

    scanf("%d",&n);

    for( i=0; i<n; i++)
    {

        scanf( "%d %d %d %d", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y );
        
        normal( l[i] );
        qiu( l[i] );

    }

}


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

    sort( l, l+n, cmp1 );

    for(j=0,i=1;i<n;i++)
    {
        while( i<n && (double)l[i].dx*l[i-1].dy-(double)l[i-1].dx*l[i].dy == 0 
            && crossproduct( l[i].a,l[i-1].b,l[i-1].a ) == 0 )
            i++;

        sort( l+j, l+i, cmp2 );
        
        if(i>j+1)
            calc( j, i );
        
        j=i;
    }

    printf( "%I64dn", ans );
}

int main()
{
    int cas,i=0;
//    freopen("sin","r",stdin);
    scanf( "%d", &cas );

    while( cas-- )
    {
        init();
        printf( "Scenario #%d:n", ++i );
        doit();
        printf("n");
    }

    return 0;
}





							

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

import java.io.PrintWriter;  
 import java.util.Scanner;  
 import java.util.Stack;  
 public class Main {  
  static class Point{  
   int x ,y;  
   public Point(int x ,int y){  
    this.x = x;  
    this.y = y;  
   }  
  }  

 static int[][] chessboard = new int[27][27];  
  static int num = 1;  
 static int[] DX = {-1,1,-2,2,-2,2,-1,1};  
  static int[] DY = {-2,-2,-1,-1,1,1,2,2};  

  public static void main(String[] args) {  
    Scanner scn = new Scanner(System.in);  
  
   PrintWriter out = new PrintWriter(System.out);  
   int n ,p,q;  
   n = scn.nextInt();  
   int index = 1;  
   while(n-- > 0){  
    p = scn.nextInt();  
    q = scn.nextInt();  
    out.format("Scenario #%d:n%snn", index++,calute(p,q));  
   }  
   out.flush();  
  }  
  static boolean find;//�ҵ���־  
  private static String calute(int p, int q) {  
   //Queue<Point> points = new LinkedList<Point>();  
   Stack<String> result = new Stack<String>();  
   num = 1;  
   find = false;  
   int[][] visited = new int[p][q];  
   result.add("A1");  
   visited[0][0] = 1;  
   bfs(p,q,new Point(0,0),result,visited);  
   if(!find){  
    return "impossible";  
   }  
   return getResult(result);  
  }  
  private static String getResult(Stack<String> result) {  
   StringBuffer sbf = new StringBuffer("");  
   for(String str : result){  
    sbf.append(str);  
   }  
   return sbf.toString();  
  }  
  private static void bfs(int p, int q, Point point, Stack<String> result, int[][] visited) {  
   int x = point.x, y = point.y, nx,ny;  
   if(num == (p*q)){  
    find = true;  
   }  
   for(int i = 0; i < 8 && !find; i++){  
    nx = x + DX[i];  
    ny = y + DY[i];  
       
    if((nx <0 || nx >= p) || (ny < 0 || ny >= q)){  
     continue;  
    }  
    //�ѷ��ʹ�  
    if(visited[nx][ny] == 1){  
     continue;  
    }  
    result.add((char)('A' + ny) + "" + (nx + 1));  
    visited[nx][ny] = 1;  
    num++;  
    bfs(p,q,new Point(nx,ny),result,visited);  
    if(find){  
     break;  
    }  
    visited[nx][ny] = 0;  
    num--;  
    result.pop();  
       
   }  
  }  
    
 } 


							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 *poj2487  
 * @author NC  
 */  
public class Main {   
  
    private static int partition(int[] array, int low, int high) {   
        int key = array[low];   
        while (low < high) {  
            while (low < high && array[high] >= key) {   
                high--;    
            }   
            array[low] = array[high];    
            while (low < high && array[low] <= key) {   
                low++; 
            }   
            array[high] = array[low];    
        }   
        array[low] = key; 
        return low;   
    }   
  
    private static void qSort(int[] array, int low, int high) {   
        int pivotloc;   
        if (low < high) {  
            pivotloc = partition(array, low, high); 
            qSort(array, low, pivotloc - 1);    
            qSort(array, pivotloc + 1, high); 
        }   
    }   
  
    private static void quickSort(int[] array) {   
        int n = array.length - 1;   
        qSort(array, 1, n);   
    }   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 1; i <= n; i++) {   
                int stamps = scan.nextInt();   
                int friends = scan.nextInt();   
                int[] fs = new int[friends + 1];   
                for (int j = 1; j <= friends; j++) {   
                    fs[j] = scan.nextInt();   
                }   
                quickSort(fs);   
                int count = 0;   
                int sum = 0;   
                for (int k = friends; k >= 1; k--) {   
                    if (sum < stamps) {   
                        sum = sum + fs[k];   
                        count++;   
                    } else {   
                        break;   
                    }   
                }   
                if (sum < stamps) {   
                    System.out.println("Scenario #" + i + ":");   
                    System.out.println("impossible");   
                    System.out.println();   
                } else {   
                    System.out.println("Scenario #" + i + ":");   
                    System.out.println(count);   
                    System.out.println();   
                }   
  
            }   
        }   
    }   
}  


							

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

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int value[100];
int gone[100][201],m,K,n;
int back[100][201];
list<int> e[100];
void merge_back(int bk1[], int bk2[], int bk[], int maxstep )
{
    int i,j;
    for( i=0; i<=maxstep; i++ )
    {
        bk[i] = bk2[i];
        for( j=2; j<=i; j++ )
        if( bk1[j-2] + bk2[i-j] > bk[i] )
            bk[i] = bk1[j-2] + bk2[i-j];
    }
    
    return ;    
}    
void merge_gone(int go1[], int bk1[], int go2[], int bk2[], int go[], int maxstep )
{
    int i,j;
    for( i=0; i<=maxstep; i++ )
    {
        go[i] = go2[i];

        for( j=1; j<=i; j++ )
        if( go1[j-1] + bk2[i-j] > go[i] )
            go[i] = go1[j-1] + bk2[i-j];
        
        for( j=2; j<=i; j++ )
        if( bk1[j-2] + go2[i-j] > go[i] )
            go[i] = bk1[j-2] + go2[i-j];
    }

    return ;
}
int back_temp[201],gone_temp[201];
void calculate(int root,int maxstep,int father)
{
    int i,j;    
    list<int>::iterator iter;
    if( root>100 || root<0 )
        int *p = new int[10000000];    
    for( i=0; i<=maxstep ; i++ )
    {
        gone[root][i] = back[root][i] = value[root];
    }
    if( maxstep == 0 ) return ;
    for( iter = e[root].begin(); iter != e[root].end() ; iter++ )
    if( *iter != father )
    {
        calculate( *iter, maxstep-1 , root );
        merge_back( back[*iter], back[root], back_temp, maxstep );
        merge_gone( gone[*iter], back[*iter], gone[root], back[root], gone_temp,maxstep );
                    
        copy( back_temp, back_temp+maxstep+1, back[root] );
        copy( gone_temp, gone_temp+maxstep+1, gone[root] );
    }

}
bool init()
{
    int i, a, b;
    cin>>n>>K;
    if( n>100 || K>200 )
        while(cout<<"faint");
    if( cin.fail() )return false;
    
    if( K > 2*n ) K = 2*n;    

    for( i=0; i<n; i++ )
    {
        cin >> value[i];
        e[i].clear();
    }    
    for( i=0; i<n-1; i++ )
    {
        cin >> a >> b;
        e[a-1].push_back( b-1 );
        e[b-1].push_back( a-1 );
    }    

    return true;
}
void doit()
{
    int answer = 0;    
    calculate( 0, K, -1);     
    cout << gone[0][K] << endl;
}
int main()
{
    while( init() )
    {
        doit();
    }
    return 0;
}



							

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

import java.util.Scanner;
public class Main{
        public static void main(String argvs[]){
                int matrix[][];
                int Max=65536;
                int m,n,t,i,j,k,max_len,count,num,min,point=0;
                int temp1[],temp2[],flag[];
                Scanner in=new Scanner(System.in);
                t=in.nextInt();
                for(i=0;i< t;i++){
                    n=in.nextInt();
                    matrix=new int[n][n];
                    flag=new int[n];
                    for(j=0;j< n;j++)
                        flag[j]=0;
                    flag[0]=1;
                    count=0;
                    num=0;
                    min=Max;
                    max_len=0;
                    temp1=new int[n*(n-1)/2];
                    temp2=new int[n*(n-1)/2];
                    for(j=0;j< n;j++)
                        for(k=0;k< n;k++)
                            matrix[j][k]=in.nextInt();
                    for(j=1;j< n;j++){
                        temp1[num]=matrix[0][j];
                        temp2[num]=j;
                        num++;
                    }
                    while(count!=n-1){
                       for(j=0;j< num;j++)
                           if(min>temp1[j]&&flag[temp2[j]]==0){
                               min=temp1[j];
                               point=j;
                           }
                       if(min>max_len) max_len=min;
                       flag[temp2[point]]=1;
                       for(j=0;j< n;j++)
                           if(j!=temp2[point]&&flag[j]==0){
                                temp1[num]=matrix[temp2[point]][j];
                                temp2[num]=j;
                                num++;
                           }
                       min=Max;
                       count++;
                    }
                    System.out.println(max_len);
                }
        }
}