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

#include<iostream>
using namespace std;
int prime[200],t[200],n;

void doprime()
{int i,j;
    n=1;
    prime[0]=2;
    for(i=3;i<1000;i++)
    {for(j=0;j<n;j++)if(i%prime[j]==0)break;

    if(j==n)prime[n++]=i;
    }
}

void fjie(int a[200],int s)
{int i;
for(i=0;i<200;i++)a[i]=0;

for(i=0;i<n&&s>1;i++)
while(s%prime[i]==0){a[i]++;s/=prime[i];}
}

int fn[101][200],fd[101][200],k,m,fdp[101][200],fnp[101][200]; 
int now[200];

void init()
{int i,s,j,h;
cin>>s;
fjie(now,s);
cin>>k;

for(i=0;i<k;i++)
{cin>>s;fjie(fn[i],s);
 h=0;
 for(j=0;j<n;j++)if(fn[i][j])fnp[i][h++]=j;

 fnp[i][h]=-1;


cin>>s;fjie(fd[i],s);
h=0;
 for(j=0;j<n;j++)if(fd[i][j])fdp[i][h++]=j;

 fdp[i][h]=-1;
}

}
//long ci=0;
void doit()
{int key=0;int i,j,temp;
for(j=0;j<n;j++){if(j&&now[j])key++;}
if(!key){m--;cout<<now[0];if(m)cout<<" ";}

while(m--)
{for(i=0;i<k;i++)
{for(j=0;fdp[i][j]>=0;j++){if(now[fdp[i][j]]<fd[i][fdp[i][j]])break;}
    
     if(fdp[i][j]<0)break;
    }
for(j=0;fdp[i][j]>=0;j++){temp=now[fdp[i][j]];now[fdp[i][j]]=now[fdp[i][j]]-fd[i][fdp[i][j]];
                        if(fdp[i][j]&&temp&&!now[fdp[i][j]])key--;}
for(j=0;fnp[i][j]>=0;j++){temp=now[fnp[i][j]];now[fnp[i][j]]=now[fnp[i][j]]+fn[i][fnp[i][j]];
                        if(fnp[i][j]&&!temp&&now[fnp[i][j]])key++;}


//ci++;
if(!key){cout<<now[0];if(m)cout<<" ";}
else m++;
}

cout<<endl;
//cout<<ci<<endl;
}

int main()
{doprime();
    while(1)
{cin>>m;
if(!m)break;
init();
doit();
}
return 0;
}
							

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

//* @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 i,j,n,cotinue;
boolean is_first;
String str;

Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
    str = cin.nextLine();
    n = str.length();
    
    cotinue = 1;
    is_first = false;
    
    for(i=0;i< n;)
    {
        if(i+1< n&&str.charAt(i)==str.charAt(i+1))
        {
            while(i+1< n&&str.charAt(i)==str.charAt(i+1)&&cotinue<9)
            {
                cotinue++;
                i++;
            }
            System.out.print(cotinue);
            System.out.print(str.charAt(i));
            i++;
            is_first = false;
            cotinue = 1;
        }
        else{
            cotinue = 1;
            if(!is_first)
                System.out.print("1");
            if(str.charAt(i)=='1')
                System.out.print("11");
            else
                System.out.print(str.charAt(i));
            if(i==n-1||(i< n-2&&str.charAt(i+1)==str.charAt(i+2)))
                    System.out.print("1");
            i++;
            is_first = true;
        }
    }
    System.out.println("");
 }
}

}

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    while(true)
    {
        String s=in.readLine();
     if(s.equals("00e0")) break;
     int a=(int)(((s.charAt(0)-'0')*10+s.charAt(1)-'0')*Math.pow(10, s.charAt(3)-'0'));
     s=Integer.toBinaryString(a);
     s=s.substring(1)+s.charAt(0);
     a=Integer.parseInt(s, 2);
     System.out.println(a);
    }
  }
}
							

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

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

 static StringBuffer res = new StringBuffer();
 public static void main(String[] args){
  Scanner in = new Scanner(System.in);
  int maxn=1100000;
  int a[]=new int[11];
  boolean f[]=new boolean[maxn];
  int n;
  a[0]=1;
  for(int i=1;i<=10;i++) a[i]=i*a[i-1];
  Arrays.fill(f,false);
  f[0]=true;
  for(int i=0;i< 11;i++)
   for(int j=maxn;j>=a[i];j--)
    if(f[j-a[i]]) f[j]=true;
  while(in.hasNext()){
     n=in.nextInt();
     if(n< 0) break;
     if(n==0) System.out.printf("NOn");
     else System.out.printf("%sn",f[n]?"YES":"NO");
   }
  }    
}
							

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

#include<iostream>
using namespace std;


struct point
{double x,y;};
struct line
{point a,b;};

point a[1010],b[1010];
 int n,d[1010];


inline double 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 double dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
///////////////
void init()
{int i;
d[0]=-1;
a[0].x=0;b[0].x=0;
a[0].y=1;b[0].y=0;

for(i=1;i<=n;i++)
{cin>>a[i].x>>b[i].x>>d[i];a[i].y=1;b[i].y=0;}

}
/////////////////////////////////////
int jiao(line l1,line l2)
{double s1=cheng(l1.a,l1.b,l2.a),
    s2=cheng(l1.a,l1.b,l2.b),s3,s4;
    if(s1*s2>0)return 0;
    s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);
    if(s3*s4>0)return 0;
    if(s1*s2<0&&s3*s4<0)return 1;
            
    if(  dcheng(l1.a,l2.a,l2.b)<=0
       ||dcheng(l1.b,l2.a,l2.b)<=0
       ||dcheng(l2.a,l1.a,l1.b)<=0
       ||dcheng(l2.b,l1.a,l1.b)<=0)return 2;
    return 0;
    
}
/////////////////////////////////////////////////////////////////
int in(point *p,int n,point judge)
{int c,j,k;point up,low,temp;    
          c=0;
          j=0;
          while(p[j].y==judge.y)j++;
          for(;j<n;j=k)
          {    k=j+1;
         
        while(p[k%n].y==judge.y&&p[k%n].x>judge.x)k++;
                up=p[j];
           low=p[k%n];
        if(up.y<low.y){temp=up;up=low;low=temp;}
        
        if(up.y<judge.y||low.y>judge.y)continue;
        if(cheng(low,up,judge)<=0&&k==j+1)continue;
        c++;
        }
        if(c%2)return 1;
        return 0;
}
/////////////////////////////
//�ԳƵ�

point duicheng(point o,line l)
{double dx=l.b.x-l.a.x,
        dy=l.b.y-l.a.y,
        s1=-l.a.x*dy+l.a.y*dx,
        s2=-o.x*dx-o.y*dy;
point an;
an.y=-(s2*dy-s1*dx)/(dy*dy+dx*dx);
if(dy)an.x=dx*(an.y-l.a.y)/dy+l.a.x;
else an.x=o.x;

an.x=an.x*2-o.x;
an.y=an.y*2-o.y;
return an;
}

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

int duit()
{int i,j;
line l,l1;point c,p[4];
for(i=1;i<n;i++)
{l.a=a[i];l.b=b[i];
for(j=0;j<i;j++){a[j]=duicheng(a[j],l);b[j]=duicheng(b[j],l);}

if(d[i]!=d[i+1])continue;
l.a=a[i+1];l.b=b[i+1];

for(j=0;j<=i;j++)
{l1.a=a[j];l1.b=b[j];
if(jiao(l,l1)==1)break;}
if(j<=i){return i+1;}

for(j=0;j<i;j++){l1.a=a[j];l1.b=a[j+1];if(jiao(l,l1)==1)break;}
if(j<i){return i+1;}

for(j=0;j<i;j++){l1.a=b[j];l1.b=b[j+1];if(jiao(l,l1)==1)break;}
if(j<i){return i+1;}

c.x=(l.a.x+l.b.x)/2;
c.y=(l.a.y+l.b.y)/2;

for(j=1;j<=i;j++)
{p[0]=a[j-1];p[1]=b[j-1];p[2]=b[j];p[3]=a[j];
if(in(p,4,c))return i+1;
}

}
return 0;
}

int main()
{int s;
while(1)
{cin>>n;
if(!n)break;
init();
if((s=duit())==0)cout<<"YES"<<endl;
else cout<<"NO "<<s<<endl;
}
return 0;
}
							

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

#include<iostream>
using namespace std;
int edge[32][32],sign[32];
int e[][2]={{0,1},{0,2},{0,3},{0,4},{0,5},
        {11,6},{11,7},{11,8},{11,9},{11,10},
        {1,2},{2,3},{3,4},{4,5},{5,1},
        {6,7},{7,8},{8,9},{9,10},{10,6},
        {1,6},{1,7},
        {2,7},{2,8},
        {3,8},{3,9},
        {4,9},{4,10},
        {5,10},{5,6},
        };
void find(int a)
{int i;
for(i=0;i<32;i++)
    if(edge[a][i]&&sign[i]==0){sign[i]=1;find(i);}
}


int main()
{int i,j,a,b,k,h,n,yes,no,past;
for(i=0;i<32;i++)
for(j=0;j<32;j++)edge[i][j]=0;

for(i=0;i<30;i++)
{a=e[i][0];b=e[i][1];edge[a][b]=edge[b][a]=1;}

h=12;
for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
for(k=j+1;k<12;k++)
if(edge[i][j]&&edge[i][k]&&edge[j][k])
    {edge[h][i]=edge[i][h]=1;
     edge[h][j]=edge[j][h]=1;
         edge[h][k]=edge[k][h]=1;     
    h++;
    }

for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
if(edge[i][j])
    {for(k=12;k<32;k++)
     for(h=k+1;h<32;h++)
     if(edge[i][k]&&edge[i][h]&&edge[j][k]&&edge[j][h])
     {edge[k][h]=edge[h][k]=1;}
    }

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

for(i=0;i<12;i++)
for(j=0;j<12;j++)edge[i][j]=0;
/*
for(i=0;i<32;i++)
{for(j=0;j<32;j++)
cout<<edge[i][j]<<' ';cout<<endl;}
*/

sign[12]=1;sign[13]=-1;
yes=12;no=13;past=-1;
cin>>n;

while(n--)
{cin>>a;
for(h=0;h<32;h++)if(edge[yes][h]&&edge[no][h]&&h!=past)break;
//cout<<h<<endl;        
if(a==1){sign[h]=-1;past=no;no=h;}
else {sign[h]=1;past=yes;yes=h;}
}

for(i=0;i<32;i++)
if(sign[i]==1)find(i);

int gs=0,bs=0,ws=0;
for(i=0;i<32;i++){
    if(sign[i]==1)gs++;
    else {if(i<12)bs++;
        else ws++;
        }
    }
cout<<bs<<' '<<ws<<' '<<gs<<endl;
return 0;
}
							

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

#include<iostream>
#include"memory.h"
#include"algorithm"
using namespace std;
long x[260000],y[260000];
long ordx[260000],ordy[260000];
inline long abs(long a)
{return a>0?a:-a;}

int cmpx(long a,long b)
{return x[a]<x[b]||(x[a]==x[b]&&y[a]<y[b]);}
int cmpy(long a,long b)
{return y[a]<y[b]||(y[a]==y[b]&&x[a]<x[b]);}

int main()
{char c;long xn,yn,n,i,bb,eb,lb,b,e,l;
cin>>n;    
xn=0;yn=0;ordx[0]=0;ordy[0]=0;x[0]=0;y[0]=0;

for(i=1;i<=n;i++)
{cin>>c;
    switch(c)
    {case'N':yn--;break;
     case'S':yn++;break;
     case'W':xn--;break;
     case'E':xn++;break;
     default:break;
    }
 x[i]=xn;y[i]=yn;ordx[i]=i;ordy[i]=i;
}

sort(&ordx[0],&ordx[n+1],cmpx);
sort(&ordy[0],&ordy[n+1],cmpy);
lb=99999999;

for(i=1;i<=n;i++)
if(x[ordx[i]]==x[ordx[i-1]])
    {b=ordx[i]<ordx[i-1]?ordx[i]:ordx[i-1];
     e=ordx[i]>ordx[i-1]?ordx[i]:ordx[i-1];
     l=y[ordx[i]]-y[ordx[i-1]];
     if((e-b)!=l)
     {if(l<lb){lb=l;bb=b;eb=e;}
      else if(l==lb){if(b<bb){bb=b;eb=e;}
              else if(b==bb){if(e>eb)eb=e;}
              }
            }
    }
for(i=1;i<=n;i++)
if(y[ordy[i]]==y[ordy[i-1]])
    {b=ordy[i]<ordy[i-1]?ordy[i]:ordy[i-1];
     e=ordy[i]>ordy[i-1]?ordy[i]:ordy[i-1];
     l=x[ordy[i]]-x[ordy[i-1]];
     if((e-b)!=l)
      {if(l<lb){lb=l;bb=b;eb=e;}
       else if(l==lb){if(b<bb){bb=b;eb=e;}
                      else if(b==bb){if(e>eb)eb=e;}
                      }
       }
     }

cout<<lb<<' '<<bb<<' '<<eb<<' ';
if(x[bb]==x[eb])
{if(y[eb]>y[bb])cout<<'S';
     else cout<<'N';
}
if(y[bb]==y[eb])
{if(x[eb]>x[bb])cout<<'E';
         else cout<<'W';
}
cout<<endl;
return 0;
}








							

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

#include<iostream>
#include"string.h"
#include"stdio.h"
using namespace std;
char name[62][10],w[10];
long ci[62][9],ti[62][9];
int main()
{long i,n,j,m,t,c;char q,a;
    for(i=0;i<62;i++)
    for(j=0;j<9;j++){ti[i][j]=-1;ci[i][j]=0;}
cin>>n;
m=0;
while(n--)
{cin>>t>>w>>q>>a;
for(i=0;i<m;i++)if(strcmp(name[i],w)==0)break;
if(i==m){m++;strcpy(name[m-1],w);}

j=q-'A';
if(ti[i][j]==-1){ci[i][j]++;if(a=='A')ti[i][j]=t;}
}

int ac;
for(j=0;j<9;j++)
{c=0;t=0;ac=0;
for(i=0;i<62;i++)
if(ti[i][j]!=-1){ac++;c+=ci[i][j];t+=ti[i][j];}
printf("%c %ld",j+'A',ac);
if(ac)printf(" %.2f %.2f",(float)c/ac,(float)t/ac);
printf("n");
}
return 0;
}
							

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

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
 
public class Main {   
    static boolean[] isVisited = new boolean[65536]; 
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int[][] chessBoard = new int[4][4];   
            for (int i = 0; i < 4; i++) {   
                String ss = scan.nextLine().trim();   
                char[] cs = ss.toCharArray();   
                for (int j = 0; j < 4; j++) {   
                    if (cs[j] == 'b') {   
                        chessBoard[i][j] = 1;//black 1   
                    } else if (cs[j] == 'w') {   
                        chessBoard[i][j] = 0;//white 0   
                    }   
                }   
            }   
            int result = bfs(chessBoard);   
            if (result == -1) {   
                System.out.println("Impossible");   
            } else {   
                System.out.println(result);   
            }   
        }   
    }   
    static int bfs(int[][] chessBoard) {   
        LinkedList<Node> queue = new LinkedList();   
        int id = chessBoardToId(chessBoard);   
        Node node = new Node(id,0);
        if (isWhite(id) || isBlack(id)) {   
            return 0;   
        }   
        isVisited[id] = true;   
        queue.addLast(node);   
        while (!queue.isEmpty()) {   
            node = queue.removeFirst();   
            for (int i = 0; i < 16; i++) {   
                //16 childNode   
                Node nextNode = nextNode(node, i);   
                nextNode.addDepth(); 
                int idid = nextNode.getChessBoardId();   
                if (!isVisited[idid]) {
                    isVisited[idid] = true;   
                    queue.addLast(nextNode);   
                }   
                if (isWhite(idid) || isBlack(idid)) {   
                    int d = nextNode.getDepth();   
                    return d;   
                }   
            }   
        }   
        return -1;   
    }   
  
    static int chessBoardToId(int[][] chessBoard) {   
        int id = 0;   
        for (int i = 0; i < chessBoard.length; i++) {   
            for (int j = 0; j < chessBoard[i].length; j++) {   
                if (chessBoard[i][j] == 1) {   
                    id++;   
                }   
                id <<= 1;
            }   
        }   
        id >>= 1;
        return id;   
    }   
  
    static Node nextNode(Node node, int i) {   
        int id = node.getChessBoardId();   
        int depth = node.getDepth();   
        id ^= (1 << (15 - i));
        if (i >= 4) {   
            id ^= (1 << (15 - i + 4));   
        }   
        if (i <= 11) {
            id ^= (1 << (15 - i - 4));   
        }   
        if (i % 4 > 0) {
            id ^= (1 << (15 - i + 1));   
        }   
        if ((i + 1) % 4 > 0) {
            id ^= (1 << (15 - i - 1));   
        }   
        node = new Node(id,depth);   
        return node;   
    }   
  
    static boolean isWhite(int chessBoardId) {   
        if (chessBoardId == 0) {   
            return true;   
        }   
        return false;   
    }   
  
    static boolean isBlack(int chessBoardId) {   
        if (chessBoardId == 0xFFFF) {
            return true;   
        }   
        return false;   
    }   
}   
  
class Node {   
  
    private int chessBoardId;   
    private int depth;   
  
    public Node(int chessBoardId,int depth) {   
        this.chessBoardId = chessBoardId;   
        this.depth = depth;   
    }   
  
    public int getChessBoardId() {   
        return chessBoardId;   
    }   
  
    public void setChessBoardId(int chessBoardId) {   
        this.chessBoardId = chessBoardId;   
    }   
  
    public int getDepth() {   
        return depth;   
    }   
  
    public void addDepth() {   
        this.depth++;   
    }   
}  


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
    String[] ss;
    int b=Integer.parseInt(in.readLine());
    int[] ax=new int[b];
    int[] ay=new int[b];
    int[][] p=new int[b][b];
    for(int i=0;i< b;i++)
    {
        ss=in.readLine().split(" ");
        ax[i]=Integer.parseInt(ss[0]);
        ay[i]=Integer.parseInt(ss[1]);
    }
    for(int i=0;i< b;i++)
    {
        for(int j=i+1;j< b;j++)
        {
            int juli=(ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]);
            p[i][j]=p[j][i]=juli;
        }
    }
    int a=Integer.parseInt(in.readLine());
    for(int i=0;i< a;i++)
    {
        ss=in.readLine().split(" ");
        int u1=Integer.parseInt(ss[0])-1;
        int u2=Integer.parseInt(ss[1])-1;
        p[u1][u2]=p[u2][u1]=0;
    }
    int[] low=new int[b];
    low[0]=-1;
    int[] near=new int[b];
    for(int i=1;i< b;i++)
        low[i]=p[0][i];
    for(int i=1;i< b;i++)
    {
        int min=9999999,tag=0;
        for(int j=0;j< b;j++)
        {
            if(low[j]!=-1&&low[j]< min)
            {
                min=low[j];
                tag=j;
            }
        }
        if(min!=0) System.out.println((near[tag]+1)+" "+(tag+1));
        low[tag]=-1;
        for(int j=0;j< b;j++)
        {
            if(p[tag][j]< low[j])
            {
                low[j]=p[tag][j];
                near[j]=tag;
            }
        }
    }
 }
}
    

							

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

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

public class Main {
    
    static int M = 100+10;
    static int N = 2;
    public static void main(String []args) throws Exception{
        
        int n,m,i,j,k,cnt;
        int DP[][] = new int[N][M];
        
        Scanner cin = new Scanner(System.in);
        
        n = cin.nextInt();
        m = cin.nextInt();
        
        for(i=0;i< m;++i) for(j=0;j< 2;++j) DP[j][i] = 0;
        DP[0][0] = 1;
        cnt = 0;
        for(i=1;i<=n;++i){
            cnt = i%2;
            for(j=0;j<=m;++j) DP[cnt][j]=0;
            k = cin.nextInt();
            if(k< 0){
                k = -k;
                k %=m;
                k = -k;
            }
            else k%=m;
            for(j=0;j< m;++j) if(DP[1-cnt][j]>0){
                DP[cnt][(j+k+m)%m] = DP[cnt][(j-k+m)%m] = 1;;
            }
        }
        
        if(DP[cnt][0]>0) System.out.println("Divisible");
        else System.out.println("Not divisible");
        
    }
}

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  public static void main(String args[])
{
   int N, M;
   Scanner sc=new Scanner(System.in);
   while(sc.hasNext())
   {
      N=sc.nextInt();//Ӳ�ҵ�����
      M=sc.nextInt();//
      if(N==0&&M==0) break;
      int a[]=new int[100];//a[i]��ʾ��i��Ӳ�ҵ���ֵ
      int c[]=new int [100];//c[i]��ʾ��i��Ӳ�ҵĸ���

      for (int i=0; i< N; i++) a[i]=sc.nextInt();
      for (int i=0; i< N; i++) c[i]=sc.nextInt();

      int nRes=0;
      boolean s[]=new boolean[100001];
      s[0]=true;

      for (int i=0; i< N; i++)
      {
          int u[]=new int[100001];
          for (int j=a[i]; j<=M; j++)
          {
             if (!s[j] && s[j-a[i]] && u[j-a[i]]< c[i])
              {
                   s[j]=true;
                   u[j]=u[j-a[i]]+1;
                   nRes++;
              }
          }
      }
      System.out.printf("%dn", nRes);
   }
  } 
}
							

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

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

long  use[14];
long  lchild[10010][14];
long  rchild[10010][14];
long  sum[510010][14];
long  depth[10010][14];

long  value[10010],dist[10010];
long  m,n,k,kind,answer;

long findit(long key,long s1,long deep)
{ 
    long &lc=lchild[s1][deep],&rc=rchild[s1][deep],sumnow=sum[s1][deep];
    long now=depth[s1][deep];

    if(now==key)
    {
        if(rc>=0)return sumnow-sum[rc][deep+1];
        else return sumnow;
    }

    else if(key<now)
    {
        if(lc>=0)return findit(key,lc,deep+1);
        return 0;
    }
    else 
    {
        if(rc>=0)return sumnow-sum[rc][deep+1]+findit(key,rc,deep+1);
        return sumnow;
    }
}

void merge(long s1,long s2,long deep)
{ 
    long &lc=lchild[s1][deep],&rc=rchild[s1][deep];
    long &lc2=lchild[s2][deep],&rc2=rchild[s2][deep];

    sum[s1][deep]+=sum[s2][deep];
            
    if(lc<0)lc=lc2;
    else 
    {
        if(lc2>=0)merge(lc,lc2,deep+1);
    }
    
    if(rc<0)rc=rc2;
    else 
    {
        if(rc2>=0)merge(rc,rc2,deep+1);
    }
}

void great(long key)
{
    long down=0,up=kind-1,deep=0,c,*p=0;
    while(1)
    {
        c=(down+up)/2;
        depth[use[deep]][deep]=value[c];
        sum[use[deep]][deep]=1;
        if(p)*p=use[deep];
        use[deep]++;
                
        if(value[c]==key)break;
        else if(key<value[c]){up=c-1;p=&lchild[use[deep]-1][deep];}
        else {down=c+1;p=&rchild[use[deep]-1][deep];}
        deep++;
    }
}

////////////////////////////////////////////////////////
struct edge
{
    long from,to;
    long distance;
}e[10020*2];

long begin[10020],end[10020];


int cmp(edge a,edge b)
{
    return a.from<b.from||(a.from==b.from&&a.to<b.to);
}

long stack[10010],st,ii[10010];
bool init()
{
    scanf("%ld %ld",&n,&k);
    if(n==0&&k==0)return 0;

    m=n-1;
    long i,j;

    for(i=0;i<2*m;i+=2)
    {
        scanf("%ld %ld %ld",&e[i].from,&e[i].to,&e[i].distance);

        e[i].from--;
        e[i].to--;

        e[i+1].from=e[i].to;
        e[i+1].to=e[i].from;
        e[i+1].distance=e[i].distance;
    }

    sort(&e[0],&e[m*2],cmp);
    
    begin[0]=0;
    for(i=1;i<m*2;i++)
    {
        if(e[i].from!=e[i-1].from)
        {
            end[e[i-1].from]=i;
            begin[e[i].from]=i;
        }
    }
    end[n-1]=2*m;
    //scanf("%ld",&k);
    
    for(i=0;i<14;i++)
    {
        use[i]=0;
        for(j=0;j<n;j++)
        {
            rchild[j][i]=lchild[j][i]=-1;
            sum[j][i]=0;
        }
    }
    long now,*father=value;
    st=1;stack[0]=0;ii[0]=-1;dist[0]=0;

    while(st)
    {
        now=stack[--st];
        ii[st]++;
        if(ii[st]<end[now]&&e[ii[st]].to==father[now])
            ii[st]++;
        
        if(ii[st]<end[now])
        {
            stack[st+1]=e[ii[st]].to;
            father[stack[st+1]]=now;
            ii[st+1]=begin[stack[st+1]]-1;
            dist[stack[st+1]]=dist[now]+e[ii[st]].distance;
            st+=2;
        }
    }
    
    copy(&dist[0],&dist[n],&value[0]);
    sort(&value[0],&value[n]);
    
    for(i=1,kind=1;i<n;i++)
    if(value[i]!=value[i-1])value[kind++]=value[i];    

    answer=0;
    return 1;
}

void count(long t,long s,int deep,long l)
{
    long a,lc=lchild[s][deep],rc=rchild[s][deep];
    a=sum[s][deep];
    
    if(lc>=0)
    {
        a-=sum[lc][deep+1];
        count(t,lc,deep+1,l);
    }
        
    if(rc>=0)
    {
        a-=sum[rc][deep+1];
        count(t,rc,deep+1,l);
    }
    
    if(a>0)
    {
        answer+=a*findit(k+l-depth[s][deep],t,0);
    }
    
    return;

}


void doit()
{
    long now,child;long tree[40010];long father[40010];
    
    st=1;stack[0]=0;ii[0]=-1;tree[0]=0;
    great(dist[0]);father[0]=0;
    while(st)
    {
        now=stack[--st];
        ii[st]++;
        
        if(ii[st]<end[now]&&e[ii[st]].to==father[now])
                ii[st]++;
        if(ii[st]<end[now])
        {
            child=e[ii[st]].to;
            father[child]=now;
            tree[child]=use[0];
            great(dist[child]);
            
            
            stack[st+1]=child;
            ii[st+1]=begin[child]-1;
            st+=2;
        }
        else if(st)
        {
            if(sum[tree[now]][0]<sum[tree[stack[st-1]]][0])
            {
                count(tree[stack[st-1]],tree[now],0,dist[stack[st-1]]*2);
                merge(tree[stack[st-1]],tree[now],0);
            }
            else
            {
                count(tree[now],tree[stack[st-1]],0,dist[stack[st-1]]*2);
                merge(tree[now],tree[stack[st-1]],0);
                tree[stack[st-1]]=tree[now];
            }
        }
    }
    printf("%ldn",answer);
    return ;
}

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

    return 0;
}





							

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

/* @author: */
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
 Scanner sc=new Scanner(System.in);
 int a[]=new int[11];
 boolean flag=false;
 while(sc.hasNext())
 {
  flag=true;
  int n=sc.nextInt();
  if(n==0)
    break;
  for(int i=1;i<=n;i++)
   a[i]=sc.nextInt();
   if(n%2==1)
    {
      System.out.printf("1n");
      continue;
    }//������������Ȼ�ǵ�һ����Ӯ
    for(int i=1;i< n&&flag;i++)
     {
      for(int j=i+1;j<=n&&flag;j++)
        if(a[i]!=0&&a[i]==a[j]){
         a[i]=0;
         a[j]=0;
         break;
        }
     
        if(a[i]!=0) flag=false;
     }//�����ż�����ж��Ƿ��˫�ɶ�
    if(!flag)
      System.out.printf("1n");
    else System.out.printf("0n");
 }
}
}
							

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

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

public class Main
{
   BigInteger[] ans = new BigInteger[52];
   public Main()
   {
      DP();
      solve();
   }
   //求组合数
   BigInteger combinationNum(int n, int m)
   {
      BigInteger ret = new BigInteger("1");
      int i;
      for (i = 0; i < m; ++i)
      {
         ret = ret.multiply(new BigInteger(n - i + ""));
         ret = ret.divide(new BigInteger(i + 1 + ""));
      }
      return ret;
   }

    void DP()
   {
      ans[1] = new BigInteger("1");
      ans[2] = new BigInteger("1");
      int i, j;
      BigInteger tmp = new BigInteger("0");
      BigInteger com = new BigInteger("0");
      for (i = 3; i <= 50; ++i)
      {
         ans[i] = new BigInteger("0");
         for (j = 1; j < i; ++j)
         {
            com = combinationNum(i - 2, j - 1);
            tmp = ans[j].multiply(ans[i - j]);
            tmp = tmp.multiply(com);
            tmp = tmp.multiply(new BigInteger(((long)1 << j) - 1 + ""));
            ans[i] = ans[i].add(tmp);
         }
      }
      //for (i = 1; i <= 50; ++i)
      //   System.out.println(i + ": " + ans[i]);
   }
    void solve()
    {
       int n;
       Scanner cin = new Scanner(System.in);
       while (true)
       {
          n = cin.nextInt();
          if (n == 0)
             return;
          System.out.println(ans[n]);
       }
    }

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


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class word{
    String str,num;
    public void change(){
        
    }
}
public class Main {
    static final int N = 100+10,M = 50000+10;
    static Map mymap = new HashMap();
    static int DP[] = new int[N],pre[] = new int[N],n,m;
    static String str[] = new String[M],num,temp,Ans[] = new String[N];
    
    public static void main(String[]args)throws Exception{
        int i;
        Scanner cin = new Scanner(System.in);
        //Scanner cin = new Scanner(new FileInputStream("input.txt"));
        
        while(cin.hasNext()){
            num = cin.next();
            n = cin.nextInt();
            m = num.length();
            mymap.clear();
            for(i=0;i< n;++i){
                str[i] = cin.next();
                temp = change(str[i]);
                mymap.put(temp, i);
            }
            solve();
        }
    }
    static void solve(){
        int i,j,k;
        String tmp;
        for(i=0;i<=m;++i){
            DP[i] = -1;
            pre[i] = -1;
        }
        DP[0] = 0;
        for(i=1;i<=m;++i){
            for(j=0;j< i;++j){
                tmp = num.substring(j, i);
                if(mymap.containsKey(tmp)){
                    k = (Integer)mymap.get(tmp);
                    if(DP[j]>-1 && (DP[i]==-1 || DP[i]>DP[j]+1)){
                        DP[i] = DP[j]+1;
                        pre[i] = k;
                    }
                }
            }
        }
        if(DP[m]==-1) System.out.println("No solution.");
        else{
            k = 0; j = m;
            while(j>0){
                Ans[k++] = str[pre[j]];
                j -=str[pre[j]].length();
            }
            for(i=k-1;i>=0;--i){
                if(i!=k-1) System.out.print(" ");
                System.out.print(Ans[i]);
            }
        }
    }
    static String change(String world){
        String ans="";
        int i,len = world.length();
        for(i=0;i< len;++i){
            ans+=change(world.charAt(i));
        }
        return ans;
    }
    static char change(char c){
        if(c=='i' || c=='j') return '1';
        if(c>='a' && c<='c') return '2';
        if(c>='d' && c<='f') return '3';
        if(c>='g' && c<='h') return '4';
        if(c=='k' || c=='l') return '5';
        if(c=='m' || c=='n') return '6';
        if(c=='p' || c=='r' || c=='s') return '7';
        if(c=='t' || c=='u' || c=='v') return '8';
        if(c=='w' || c=='x' || c=='y') return '9';
        if(c=='o' || c=='q' || c=='z') return '0';
        return '0';
    }
}

							

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

//* @author:
import java.util.*;
//���ظ�������
public class Main {
    static Scanner in = new Scanner(System.in);
    static boolean nextPermutation(char[] s) {
        int i;
        for(i=s.length-1; i>0; --i)
            if(s[i-1]< s[i]) break;
        if(i==0) return false;
        --i;
        int k=i+1;
        for(int j=i+2; j< s.length; ++j)
            if(s[i]< s[j]) k = j;
        {
            char x=s[i];
            s[i] = s[k];
            s[k] = x;
        }
        for(int j=i+1; j<=(s.length+i)/2; ++j) {
            char x=s[j];
            k=s.length+i-j;
            s[j] = s[k];
            s[k] = x;
        }
        return true;
    }
    public static void main(String[] args) {
        char[] s = in.next().toCharArray();
        Arrays.sort(s);
        do {
            System.out.println(s);
        } while(nextPermutation(s));
    }
}

							

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

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

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    while(true)
    {
        long x = sc.nextLong();
        long xx = Math.abs(x);
        if(x == 0)
        {
            break;
        }
            int result = 0;
        for(int i = 32; i >= 1; i--)
        {
            if(i%2 == 0 && x < 0)
        {
            continue;
        }
            double m = Math.pow(xx,1.0/i);
        int n1 = (int)Math.floor(m);
        int n2 = (int)Math.ceil(m);
        //System.out.println(i+ " " + m + " " + n1 + " " + n2);
            if(Math.pow(n1,i) == xx || Math.pow(n2,i) == xx)
        {
            result = i;
            break;
        }
        }
        System.out.println(result);
    }
    }
}

							

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

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

struct event{
    int t, x;
}p[100000];

bool cmp( event &a, event &b ) {
    return a.x+a.t < b.x+b.t;
}
int n, m;

void input( ) {
    int i;
    scanf( "%d%d", &n, &m);
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].t, &p[i].x );

}

bool check( int lt ) {
    int i, lx, j;
    lx = -100000000;
    for( i=0, j=0; i<n&&j<=m; i++ ) {
        if( abs( p[i].x - lx ) > p[i].t - lt ) {
            lx = p[i].x + ( p[i].t - lt );
            j++;
        }
    }
    return j<=m;
}

int main( ) {
    int i, s, a, b, j, c;
    scanf( "%d", &s );
    for( i=1; i<=s; i++ ) {
        input( );
        a = 1000000;
        b = -10000000;

        for( j=0; j<n; j++ )
            if( a > p[j].t ) a = p[j].t;

        std::sort( p, p+n, cmp );
        a++;
        while( a > b+1 ) {
            c = (a+b)/2;
            if( check( c ) )
                b = c;
            else
                a = c;
        }

        printf( "Case %d: %dn", i, b );
    }
    return 0;
}
							

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

import java.io.BufferedInputStream;   
import java.util.Arrays;   
import java.util.Scanner;   
 
public class Main {   
  
    static int x[];   
    static int y[];   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            x = new int[n];   
            y = new int[n];   
            for (int i = 0; i < n; i++) {   
                x[i] = scan.nextInt();   
                y[i] = scan.nextInt();   
            }   
            Arrays.sort(x);   
            Arrays.sort(y);   
            for (int i = 0; i < n; i++) {   
                x[i] -= i;   
            }   
            Arrays.sort(x);   
            int midX = x[(n + 1) / 2 - 1];   
            int midY = y[(n + 1) / 2 - 1];   
            int num = 0;   
            for (int i = 0; i < n; i++) {   
                num += Math.abs(x[i] - midX) + Math.abs(y[i] - midY);   
            }   
            System.out.println(num);   
  
        }   
    }   
}  

							

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

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

int e[1000][1000], en[1000], col[1000];
int match[1000];

bool sign1[1000], sign2[1000];
int flag[1000];

bool search( int a )
{
    int i, j;

    sign1[a] = true;

    for( i=0; i<en[a]; i++ )
    {
        j = e[a][i];
        if( !sign2[j] )
        {
            sign2[j] = true;
            if( match[j] == -1 || ( !sign1[match[j]] && search( match[j] ) ) )
            {
                match[j] = a;
                flag[a] = j;
                return true;
            }
        }
    }

    return false;
}

int main( )
{
    int cas, i, c, r, a, b;

    scanf( "%d", &cas );

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

        for( i=0; i<r; i++ )
            en[i] = 0;

        for( i=0; i<c; i++ )
        {
            scanf( "%d %d", &a, &b );
            col[i] = a;
            a--, b--;
            e[a][en[a]++] = i;
            e[b][en[b]++] = i;
        }

        memset( flag, -1, sizeof flag );
        memset( match, -1, sizeof match );

        for( i=0; i<r; i++ )
        if( flag[i] == -1 )
        {
            memset( sign1, 0, sizeof sign1 );
            memset( sign2, 0, sizeof sign2 );
            if( !search( i ) )
                break;
        }
        
        if( i < r )
            printf( "NOn" );
        else
        {
            for( i=0; i<c; i++ )
            {
                if( match[i] != -1 )
                    printf( "%d", match[i]+1 );
                else 
                    printf( "%d", col[i] );

                if( i < c-1 )printf( " " );
                else printf( "n" );
            }
        }
    }

    return 0;
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    int a=Integer.parseInt(in.readLine());
    int ans=2,i;
    my[] arr=new my[a];
    String[] ss;
    for(i=0;i< a;i++)
    {
         ss=in.readLine().split(" ");
      int x=Integer.parseInt(ss[0]);
      int y=Integer.parseInt(ss[1]);
      arr[i]=new my(x,y);
     }
     Arrays.sort(arr);
     int x=arr[0].b,y=x-1;
     for(i=1;i< a;i++)
     {
      if(y>=arr[i].a){}
      else if(x>=arr[i].a)
      {
        y=x;
        x=arr[i].b;
        ans++;
       }
       else
       {
        x=arr[i].b;
        y=x-1;
        ans+=2;
        }
       }
    System.out.printf("%dn",ans);
  }
}
class my implements Comparable< my>
{
    public int a,b;
    public my(int x,int y)
    {
        a=x;
        b=y;
    }
    public int compareTo(my o) {
        return b-o.b;
    }
}
							

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

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


char *digit = "FEDCBA9876543210"; //0123456789ABCDEF";
int p[8][8];
bool sign[16];

int main()
{
    int i,j,n,k;
    char ans[9];


    for( k=0; k<8; k++ )
    {
        p[k][7-k] = 1;
        for( i=6-k; i>=0; i-- )
            p[k][i] = p[k][i+1]*(15-i);
    }
    

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

    scanf( "%d", &n );

    n -- ;
    for( k=0; n >= p[k][0]*15; k++ )
        n -= p[k][0]*15;

    int h;
    for( i=0; i<8-k; i++ )
    {
        h = n / p[k][i];
        for( j=0; j<16; j++ )
        if( !sign[j] )
        {
            if( !h )break;
            h--;
        }

        ans[i] = digit[j];
        sign[j] = 1;
        n %= p[k][i];
    }

    ans[i] = '';

    printf( "%sn", ans );

    return 0;
}
							

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

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

struct node
{
    int id;
    int order;
    node *l,*r,*f;
    int lv,rv,fv;
}tree[600];

node *leaf[600];

int n, k;
int e[600][3];
int v[600][3];
int d[600];

inline bool isleaf( node *s )
{
    return s->id < k;
}
        
int creat( node *r, node *f , int fv )
{
    int i, lo, ro;
    
    r -> f = f;
    r -> fv = fv;
    if( isleaf( r ) ) return r -> order;

    r -> lv = -1;

    for( i=0; i<3; i++ )
    {
        if( e[r->id][i] != f - tree )
        {
            if( r -> lv == -1 )
            {
                r->lv = v[r->id][i];
                r->l = tree+e[r->id][i];
                lo = creat( r->l, r, r->lv );
            }
            else
            {
                r->rv = v[r->id][i];
                r->r = tree+e[r->id][i];
                ro = creat( r->r, r, r->rv );
            }
        }
    }

    if( lo > ro )
    {
        std::swap( r->l, r->r );
        std::swap( r->lv, r->rv );
        r -> order = ro;
    }
    else r -> order = lo;
    
    return r -> order;
} 

void init()
{
    int i, j, a, b, va, h, t, g;
    
    scanf( "%d%d", &n, &k );

    for( i=0; i<n; i++ )
    d[i] = 0,tree[i].id = i;

    for( i=0; i< 3*n/2 ; i++ )
    {
        scanf( "%d%d%d", &a, &b, &va );
        a--,b--;
        e[a][ d[a] ] = b;
        v[a][ d[a] ] = va;
        d[a]++;
    
        e[b][ d[b] ] = a;
        v[b][ d[b] ] = va;
        d[b]++;
    }

    for( i=0; i<3; i++ )
    if( isleaf( tree+e[0][i] ) )
    {
        tree[0].l = tree+e[0][i];
        tree[0].lv = v[0][i];
        break;
    }

    h = e[0][i];

    for( j=1,t=0; h!=0; j++  )
    {
        tree[h].order = j;
        leaf[j] = tree+h;

        for( i=0; i<3; i++ )
        {
            if( e[h][i] == t )
            {
                tree[h].l = tree+e[h][i];
                tree[h].lv = v[h][i];
            }
            else if( isleaf( tree+e[h][i] ) )
            {
                tree[h].r = tree+e[h][i];
                tree[h].rv = v[h][i];
                g = e[h][i];
            }
        }

        t=h;
        h=g;
    }
    tree[0].r = tree+t;
    tree[0].rv = tree[t].rv;

    for( i=0; i<3; i++ )
    {
        if( e[0][i] != tree[0].l-tree && e[0][i] != tree[0].r-tree )
        {
            tree[0].f = e[0][i] + tree;
            tree[0].fv = v[0][i];
            break;
        }
    }

    creat(     tree[0].f , tree, tree[0].fv );

}

int *output, m;

int calc_a_r( node *a, node *b, node *r );
int calc_r_b( node *a, node *b, node *r );


int calc_a_b( node *a, node *b, node *r )
{
    int ans = 0;

    if( a == b )
    {
        output[m++] = r->id;
        return 0;
    }

    ans +=    calc_a_r( a, leaf[r->r->order-1], r->l );
    output[m++] = r->id;
    ans +=     calc_r_b( leaf[r->r->order], b, r->r ) + r->lv + r->rv;

    return ans;
}

int calc_a_r( node *a, node *b, node *r )
{
    int ans;    

    if( a == b )
    {
        output[m++] = r->id;
        return 0;
    }

    ans =    calc_a_b( a, leaf[r->r->order-1], r->l ) +
              calc_a_r( leaf[r->r->order], b, r->r ) +
              r->rv + leaf[r->r->order]->lv;
    output[m++] = r->id;

    return ans;
}

int calc_r_b( node *a, node *b, node *r )
{
    
    output[m++] = r->id;

    if( a == b ) return 0;

    return    calc_r_b( a, leaf[r->r->order-1], r->l ) +
              calc_a_b( leaf[r->r->order], b, r->r ) +
              r->lv + leaf[r->r->order]->lv;
}

int answer[3][500];

int main()
{
    int i, ans1, ans2, ans3;

    init();

    m = 0; output = answer[0];
    ans1 = calc_a_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].rv;
    
    m = 0; output = answer[1];
    ans2 = calc_a_r( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].fv;
    
    m = 0; output = answer[2];
    ans3 = calc_r_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].rv + tree[0].fv;

    if( ans1 <= ans2 && ans1 <= ans3 )
        output = answer[0];
    else if( ans2 <= ans1 && ans2 <= ans3 )
        output = answer[1];

    printf( "%d", 1 );
    for( i=0; i<n-1; i++ )
        printf( " %d", output[i]+1 );
    printf( "n" );

    return 0;
}
							

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

#include<iostream>
#include"memory.h"
using namespace std;
int n;

bool map[101][101];

void init()
{int i,j;bool k;
k=1;
for(i=1;i<=n;i++,k=!k)
map[i][1]=k;

for(i=1;i<=n;i++)
for(j=2;j<=n;j++)
map[i][j]=!map[i][j-1];
}

void doit()
{int i,j,step=2*n+1;bool k=true;

for(i=1;i<n;i++)
{cout<<step;
for(j=1;j<=n;j++)
if(map[i][j]==k)cout<<' '<<(i-1)*n+j;
cout<<endl;
step+=2;k=!k;
cout<<step;
for(j=1;j<=n;j++)
if(map[i][j]==k)cout<<' '<<(i-1)*n+j;
cout<<endl;
step+=2;k=!k;
}

if(n%2)
{for(i=1;i<n;i++,step+=2)
cout<<step<<' '<<(n-1)*n+i<<endl;}
else 
for(i=n;i>1;i--,step+=2)
cout<<step<<' '<<(n-1)*n+i<<endl;

}


int main()
{int t;
//cin>>t;
//while(t--)
{cin>>n;
init();
doit();
//cout<<endl;
}
return 0;
}
							

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

#include<iostream>
#include"memory.h"
#include"string.h"
using namespace std;
char word[1000][23];
int index[27];
int n,l,len[1000],set[1000];
void init()
{
    int i;
    for(i=0;i<26;i++)index[i]=n;

    for(i=0;i<n;i++)
    {
        cin>>word[i];
        len[i]=strlen(word[i]);
        if(index[word[i][0]-'a']==n)index[word[i][0]-'a']=i;
    }

    memset(set,1,1000*sizeof(int));
}

char best[100];int go;
char w[100];


void find(int a,int b)
{
    if(go&&strcmp(w,best)>0)return;

    if(b==a&&a)
    {
        if(a==l&&!go)
        {
            strcpy(best,w);go=1;
        }

        else if(a==l&&strcmp(w,best)<0)
            strcpy(best,w);
        return;
    }

    if(a>=l||b>l)return;
    int i,j;
    for(i=(a==0?0:index[w[a]-'a']);i<n&&(a==0||word[i][0]==w[a]);i++)
    if(set[i])
    {
        for(j=a;j<b&&j-a<len[i];j++)
        {
            if(word[i][j-a]!=w[j])break;
        }
        if(j>=b)
        {
            w[a]=0;
            strcat(w,word[i]);
            set[i]=0;                
            if(go&&strcmp(w,best)>0)
            {
                w[b+1]=0;set[i]=1;return;
            }
        
            find(b,a+len[i]);        
            w[b+1]=0;
            set[i]=1;

        }
        if(j-a>=len[i])
        {
            set[i]=0;    
            find(a+len[i],b);
            set[i]=1;
        }
    }
return;

}
int main()
{
    cin>>l>>n;
    init();
    w[0]=0;go=0;
    find(0,0);
    if(n>1&&go)cout<<best<<endl;
    else cout<<"NO SOLUTION"<<endl;
    return 0;
}
							

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

#include<iostream>
#include"memory.h"
using namespace std;
int set[100][100];
int map[100][10000][2];
int path[100];
int n,l,k,q;
int cir[100];

void init()
{int i,m,a,b;
memset(path,0,100*sizeof(int));
memset(set,0,100*100*sizeof(int));

    cin>>n>>l>>k>>q;
    l--;k--;q--;

for(i=0;i<n;i++)cin>>cir[i];
cin>>m;
for(i=0;i<m;i++){cin>>a>>b;a--;b--;
                cin>>map[a][path[a]++][1];
                     map[a][path[a]-1][0]=b;}
}

int queue[10000][3],head,tail;

void find()
{int a,b,c,i,to;
head=0;tail=0;
queue[tail][0]=l;queue[tail][1]=k;
queue[tail][2]=0;
set[l][k]=set[k][l]=1;
tail++;
int key=0;
while(head!=tail&&!key)
{a=queue[head][0];
 b=queue[head][1];
 c=queue[head][2];
 head++;head%=10000;
 for(i=0;i<path[a];i++)
     if(map[a][i][0]!=b&&cir[b]==map[a][i][1]&&!set[b][map[a][i][0]])
     {if(map[a][i][0]==q){key=1;break;}
      to=map[a][i][0];
      
      set[b][to]=1;set[to][b]=1;
      queue[tail][0]=to;queue[tail][1]=b;
      queue[tail][2]=c+1;
      tail++;tail%=10000;
     }
 
 for(i=0;i<path[b]&&!key;i++)
     if(map[b][i][0]!=a&&cir[a]==map[b][i][1]&&!set[a][map[b][i][0]])
     {if(map[b][i][0]==q){key=1;break;}
      to=map[b][i][0];
     
      set[to][a]=1;set[a][to]=1;
      queue[tail][0]=to;queue[tail][1]=a;
      queue[tail][2]=c+1;
      tail++;tail%=10000;
     }
}
if(key){cout<<"YES"<<endl;cout<<c+1<<endl;}
else cout<<"NO"<<endl;

}

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

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main 
{
 static class com
 {
    BigInteger a,b;//a/b...
    com add(com C)
    {
        com ret=new com();
        BigInteger lcm;
        lcm=b.multiply(C.b).divide(b.gcd(C.b));
        ret.b=lcm;
        ret.a=a.multiply(lcm.divide(b)).add(C.a.multiply(lcm.divide(C.b)));
        lcm=ret.b.gcd(ret.a);
        ret.a=ret.a.divide(lcm);
        ret.b=ret.b.divide(lcm);
        return ret;
    }
    com sub(com C)
    {
        com ret=new com();
        BigInteger lcm;
        lcm=b.multiply(C.b).divide(b.gcd(C.b));
        ret.b=lcm;
        ret.a=a.multiply(lcm.divide(b)).subtract((C.a.multiply(lcm.divide(C.b))));
        lcm=ret.b.gcd(ret.a);
        ret.a=ret.a.divide(lcm);
        ret.b=ret.b.divide(lcm);
        return ret;
    }
    void show()
    {
        System.out.println(a+" / "+b);
    }
  }

 static BigInteger s[][]=new BigInteger[105][105],fac[]=new BigInteger[105],dp[][]=new BigInteger[105][105];
  static com B[]=new com[105];
  static com buf[] = new com[105];
  static void mkstri()
  {
   int i,j;
   com tmp = new com();
   for (i = 0; i < 105; ++i) B[i] = new com();
     for(i=1;i< 105;++i)
    {
        dp[i][0]=dp[i][i]=BigInteger.ONE;
        for(j=1;j< i;++j)
            dp[i][j]=dp[i-1][j-1].add(dp[i-1][j]);
    }
     for(i=1;i< 105;++i)
    s[i][i]=s[i][1]=BigInteger.ONE;
     for(i=2;i< 105;++i)
    for(j=2;j< i;++j)
        s[i][j]=s[i-1][j-1].add(s[i-1][j].multiply(BigInteger.valueOf(j)));
     fac[0]=BigInteger.ONE;
     for(i=1;i< 105;++i) 
       fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));
     B[0].a=B[0].b=BigInteger.ONE;
     for(i=1;i< 105;++i)
     {
    B[i].a=BigInteger.ZERO;
    B[i].b=BigInteger.ONE;
    for(j=1;j<=i;++j)
    {
        tmp.a=fac[j].multiply(s[i][j]);
        tmp.b=BigInteger.valueOf(j+1);
        if((i+j)%2==0)
            B[i]=B[i].add(tmp);
        else
            B[i]=B[i].sub(tmp);
    }
      }
    }
    
 public static void main(String args[]) throws Exception {
   Scanner cin=new Scanner(System.in);
   mkstri();
   BigInteger ans,tmp,G;
   int k,i;
   for(i=0;i< 105;++i)buf[i]=new com();
   while(cin.hasNext())
   {
    k=cin.nextInt();
    //k+1...
    ans=BigInteger.ONE;
    for(i=0;i<=k;++i)
    {
        buf[i].b=B[i].b.multiply(BigInteger.valueOf(k+1));
        buf[i].a=B[i].a.multiply(dp[k+1][i]);
        G=buf[i].a.gcd(buf[i].b);
        buf[i].a=buf[i].a.divide(G);
        buf[i].b=buf[i].b.divide(G);
        ans=ans.multiply(buf[i].b).divide(buf[i].b.gcd(ans));
    }
    System.out.print(ans);
    for(i=0;i<=k;++i)
    {
        G=ans.divide(buf[i].b);
        System.out.print(" "+buf[i].a.multiply(G));
    }
    System.out.println(" 0");
  }
 }
} 
							

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

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

public class Main 
{
    public static Map< Integer,Integer> mapOldToNew;
    public static Map< Integer,Integer> mapNewToOld;    
    public static int counter = 1;
    public static void main(String[] args) throws Exception
    {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        Map< Integer, StringBuilder> references = new HashMap< Integer,StringBuilder>(1000);
        mapOldToNew = new HashMap< Integer,Integer>(1000);
        mapNewToOld = new HashMap< Integer,Integer>(1000);
        boolean isInsidePara = false;
        boolean isRegPara = true;
        boolean isBegin = true;
        String num = "";
        String line = null;
        StringBuilder para = null;
        String id = "";
        while(true)
        {
            line = stdin.readLine();
            if(line == null)
            {
                break;
            }
            if(line.trim().length() == 0)
            {
                if(isInsidePara)
                {
                    isInsidePara = false;
                    if(isRegPara)
                    {
                        //regulars[numReg++] = para;
                    }else
                    {
                        int in = Integer.parseInt(id);
                        references.put(in,para);
                    }
                }
            }else
            {
                if(!isInsidePara)
                {
                    isInsidePara = true;
                    if(line.startsWith("["))
                    {
                        
                        para = new StringBuilder(240);
                        isRegPara = false;
                        id = "";
                        for(int i = 1; i < line.length(); i++)
                        {
                            char ch = line.charAt(i);
                            if(ch == ']')
                            {
                                break;
                            }
                            id += ch;
                        }
                        para.append(line);
                        para.append("n");
                    }else
                    {
                        isRegPara= true;
                        if(isBegin)
                        {
                            isBegin = false;
                        }else
                        {
                            System.out.write('n');
                        }
                        printRegLine(line);
                    }
                }else
                {
                    if(isRegPara)
                    {
                        printRegLine(line);
                    }else
                    {
                        para.append(line);
                        para.append("n");
                    }
                }
            }
        }
        
        if(isInsidePara)
        {
            if(isRegPara)
            {
                //regulars[numReg++] = para;
            }else
            {
                int in = Integer.parseInt(id);
                references.put(in,para);
            }
        }
        
        boolean insideRef = false;
        for(int j = 1; j < counter; j++)
        {
            StringBuilder sb = references.get(mapNewToOld.get(j));
            System.out.write('n');
            
            num = "";
            insideRef = false;
            for(int i = 0; i < sb.length(); i++)
            {
                char ch = sb.charAt(i);
                if(ch == '[')
                {
                    insideRef = true;
                    System.out.write(ch);
                }else if(ch == ']')
                {
                    insideRef = false;
                    int in = Integer.parseInt(num);
                    num = "";
                    System.out.print(mapOldToNew.get(in));
                    System.out.write(ch);
                }else if(insideRef)
                {
                    num += ch;
                }else
                {
                    System.out.write(ch);
                }
            }
        }
    }
    
    public static void printRegLine(String sb)
    {
            String num = "";
            boolean insideRef = false;
            for(int i = 0; i < sb.length(); i++)
            {
                char ch = sb.charAt(i);
                if(ch == '[')
                {
                    insideRef = true;
                    System.out.write(ch);
                }else if(ch == ']')
                {
                    insideRef = false;
                    int in = Integer.parseInt(num);
                    Integer value = mapOldToNew.get(in);
                    if(value == null)
                    {
                        mapOldToNew.put(in,counter);
                        mapNewToOld.put(counter,in);
                        counter++;
                    }
                    num = "";
                    System.out.print(mapOldToNew.get(in));
                    System.out.write(ch);
                }else if(insideRef)
                {
                    num += ch;
                }else
                {
                    System.out.write(ch);
                }
            }
            System.out.write('n');
    }
}

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 public static void  main(String args[] ){
  int arr[]=new int[10005];
  Scanner sc=new Scanner(System.in);

  int T=sc.nextInt();

  while((T--)!=0){
   int n=sc.nextInt();
   arr[0] = 0;
   for (int i = 1; i <= n;i++)
     arr[i]=sc.nextInt();
   Arrays.sort(arr,1,n + 1);
   int ans = 0;
   for (int i = n; i >= 1; i -= 2)
    ans ^= arr[i] - arr[i-1] - 1;
   if (ans==0) System.out.printf ("Bob will winn");
   else System.out.printf ("Georgia will winn");
  }
 }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] p,q;
 static int u;
 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());
    while((a--)!=0)
    {
     String[] ss=in.readLine().split(" ");
     int n=Integer.parseInt(ss[0]);
     int m=Integer.parseInt(ss[1]);
     p=new int[n+1];
     q=new int[n+1];
     for(int i=0;i<=n;i++)
        p[i]=i;
     for(int i=0;i< m;i++)
     {
        ss=in.readLine().split(" ");
        int x=Integer.parseInt(ss[1]);
        int y=Integer.parseInt(ss[2]);
        if(ss[0].equals("D"))
            union(x,y);
        else{
           if(root(x)!=root(y))
            System.out.println("Not sure yet.");
           else
           {
            if(get(x)==get(y))
              System.out.println("In the same gang.");
            else
              System.out.println("In different gangs.");
            }
        }
      }
    }
 }
    static int root(int a)
    {
        while(p[a]!=a)
            a=p[a];
        return a;
    }
  static void union(int x,int y)
  {
    int s1=get(x);
    int x1=u;
    int s2=get(y);
    int y1=u;
    if(x1==y1)return;
    if(x1< y1)
    {
        p[y1]=x1;
        if(s1==s2)
            q[y1]=q[x1]+1;
    }
    else
    {
        p[x1]=y1;
        if(s1==s2)
            q[x1]=q[y1]+1;
    }
    }
    
  static int get(int a)
 {
    int t=0;
    while(p[a]!=a)
    {
        t+=q[a];
        a=p[a];
    }
    u=a;
    return t%2;
  }
}
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static long ans[]={ 1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,
                     1594323,4782969,14348907,43046721,129140163,387420489,1162261467 };
 public static void  main(String args[]){
  int n;
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  int p[]=new int[25];
  while((n--)!=0){
    Arrays.fill(p,0);
    int  a;
    a=sc.nextInt();
    int len=0,i;
    while(a!=0)
    {
    int u=a%3;
    p[len++]=u;
    a/=3;
     }
    for(i=0;i< len;i++)
    {
    if(p[i]==2)
    {
      p[i]=-1;
      p[i+1]++;
    }
    if(p[i]==3)
    {
      p[i]=0;
      p[i+1]++;
    }
     }
     boolean bb=false;
     for(i=0;i<=len;i++)
     {
    if(p[i]==-1)
    {
      if(bb) System.out.printf(",");
      System.out.printf("%d",ans[i]);
      bb=true;
    }
      }
      if(!bb) System.out.printf("empty");
      System.out.printf(" ");
      bb=false;
      for(i=0;i<=len;i++)
       {
      if(p[i]==1)
      {
       if(bb) System.out.printf(",");
       System.out.printf("%d",ans[i]);
       bb=true;
       }
     }
     System.out.println();
    }
  }
}
							

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

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

public class Main {

    private static int sum;

    public static int getSumTime(int[] a, int n) {
        
        if (n < 3) {
             return a[n-1];
        } else if (n == 3) {
            return a[0] + a[1] + a[2];
        } else {
            int temp1 = a[n-1] + a[0] + a[n - 2] + a[0];
            int temp2 = a[1] + a[0] + a[n-1] + a[1];
            
            if (temp1 < temp2){
                return  temp1 + getSumTime(a, n - 2);
            }
            else if (temp2 < temp1){
                return  temp2 + getSumTime(a, n - 2); 
            }else{
                return  temp2 + getSumTime(a, n - 2); 
            }
        }
    }

    public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int t = sc.nextInt();
          for(int i = 0; i < t ; i++){
              int n = sc.nextInt();
              int[] a = new int[n];
              for(int j = 0; j < n ; j++){
                  a[j] = sc.nextInt();
              }
              Arrays.sort(a);
              System.out.println(Main.getSumTime(a, n));
          }     
    }

}
							

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

#include<iostream>
#include"string.h"
#include<vector>
#include<algorithm>
using namespace std;
int m[10][10];
int set[10];
int len[10];int n;
int order1[10][9],order2[10][9];
char word[10][22];
int h;
int cmp1(int a,int b)
{return m[h][a]>m[h][b];}

int cmp2(int a,int b)
{return m[a][h]>m[b][h];}

int link(int a,int b)
{int i,j;
for(i=0;i<=len[a];i++)
for(j=0;j<=len[b];j++)
{if(i+j>=len[a]||j==len[b])return j;
if(word[a][i+j]!=word[b][j])break;
}
return 0;
}

int best;

void find(int lennow,int head,int tail,int l)
{int i;
if(lennow>=best)return;
if(l==n&&best>lennow)
{best=lennow;return;}
for(i=0;i<n-1;i++)
{if(!set[order2[head][i]]){set[order2[head][i]]=1;

        find(lennow+len[order2[head][i]]-m[order2[head][i]][head],order2[head][i],tail,l+1);
        set[order2[head][i]]=0;
                    }
if(!set[order1[tail][i]]){set[order1[tail][i]]=1;
        find(lennow+len[order1[tail][i]]-m[tail][order1[tail][i]],head,order1[tail][i],l+1);
        set[order1[tail][i]]=0;
                }        
}

}

int main()
{int i,t,j,k,num;
cin>>t;
while(t--)
{cin>>n;
for(i=0;i<n;i++){cin>>word[i];len[i]=strlen(word[i]);set[i]=0;}

for(i=0;i<n;i++)
{k=0;
for(j=0;j<n;j++)
if(i!=j){m[i][j]=link(i,j);
         m[j][i]=link(j,i);
         order1[i][k]=j;
         order2[i][k++]=j;
         if(!set[j]&&(m[i][j]==len[i]||m[j][i]==len[i]))set[i]=1;
            if(!set[i]&&(m[i][j]==len[j]||m[j][i]==len[j]))set[j]=1;
        }
}
num=0;h=-1;
for(i=0;i<n;i++)if(set[i])num++;
else {h=i;sort(&order1[i][0],&order1[i][n-1],cmp1);
          sort(&order2[i][0],&order2[i][n-1],cmp2);
    }

best=9999;
if(h==-1){for(i=0;i<n;i++)if(best>len[i])best=len[i];}
else {set[h]=1;find(len[h],h,h,num+1);}

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



							

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

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin  = new Scanner(System.in);
  int M = cin.nextInt();
  for(int i=0;i< M;i++)
   run();
  }
    
  static void run(){
    int N = cin.nextInt();
    int[][] d = new int[N+1][N+1];
    for(int i=1;i< N;i++)
     for(int j=i+1;j<=N;j++)
    d[i][j] = cin.nextInt();
    
    int[][][] f = new int[N+1][N+1][N+1];
    for(int i=1;i<=N;i++)//��ʼ��
      for(int j=1;j<=N;j++)
        for(int k=1;k<=N;k++)
           f[i][j][k]=10000;
    f[1][1][1] = 0;
    for(int k=2;k<=N;k++)
      for(int i=1;i< k;i++)
    for(int j=1;j< k;j++){
      if(f[i][j][k-1]+d[i][k]< f[j][k-1][k]){
       f[j][k-1][k]=f[i][j][k-1]+d[i][k];
       f[k-1][j][k]=f[i][j][k-1]+d[i][k];
      }
      if(f[i][j][k-1]+d[j][k]< f[i][k-1][k]){
        f[i][k-1][k]=f[i][j][k-1]+d[j][k];
        f[k-1][i][k]=f[i][j][k-1]+d[j][k];
       }
      if(f[i][j][k-1]+d[k-1][k]< f[i][j][k]){
        f[i][j][k]=f[i][j][k-1]+d[k-1][k]; 
        f[j][i][k]=f[i][j][k-1]+d[k-1][k];
      }
    } 
        
    int opt=f[1][1][N];
    for(int i=1;i< N;i++)
      for(int j=1;j< N;j++)
        if(f[i][j][N]< opt)
          opt=f[i][j][N];
    System.out.println(opt);
  }
}
							

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

#include<iostream>
#include<vector>
#include"stdlib.h"
using namespace std; 
int child[201],need[201];

int ch[201][200];

//int cmp(int i,int j)
int cmp(const void * i,const void * j)

{
    if(need[*((int *)i)]<need[*((int *)j)]) return 1;

    else if(need[*((int *)i)]>need[*((int *)j)]) return -1;

    return 0;
}

void doit(int a)
{
    int i,max;

    for(i=0;i<child[a];i++)
        if(need[ch[a][i]]==-1)doit(ch[a][i]);

    if(i==0){need[a]=1;return;}

    qsort(&ch[a][0],child[a],sizeof(int),cmp);

    max=0;
    for(i=0;i<child[a];i++)
        if(i+need[ch[a][i]]>max)max=i+need[ch[a][i]];

    need[a]=max;
}

int main()
{
    int i,j,n,t,a,node;

    cin>>t;

    while(t--)
    {
        cin>>node;
        for(i=0;i<node;i++)
        {
            cin>>a>>n;

            for(j=0;j<n;j++)
                cin>>ch[a][j];

            child[a]=j;
        }

        for(i=0;i<=node;i++)need[i]=-1;

        doit(1);

        cout<<need[1]<<endl;
    }
return 0;
}




							

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

#include<iostream>
using namespace std;
char set[100][100];
int n_cl,n_rl;
struct line
{int x1,x2,y1,y2;};

line c[100],r[100];
inline int min(int a,int b)
{if(a<b)return a;
else return b;
}
inline int max(int a,int b)
{if(a>b)return a;
else return b;
}



int jiao(line rl,line cl)
{return rl.x1<=cl.x1&&cl.x1<=rl.x2&&cl.y1<=rl.y1&&rl.y1<=cl.y2;}

int cs[100];
int rs[100];

int main()
{int i,j,k,n,t,a,b,cc,d;
long s,m;
cin>>t;
while(t--)
{cin>>n;n_cl=0;n_rl=0;
for(i=0;i<n;i++)
{cin>>a>>b>>cc>>d;
if(a==cc){c[n_cl].y1=min(b,d);c[n_cl].y2=max(b,d);c[n_cl].x1=c[n_cl].x2=a;n_cl++;}
else {r[n_rl].x1=min(a,cc);r[n_rl].x2=max(a,cc);r[n_rl].y1=r[n_rl].y2=b;n_rl++;}
}




for(i=0;i<n_cl;i++)
for(j=0;j<n_rl;j++)
if(jiao(r[j],c[i]))set[i][j]=1;else set[i][j]=0;

s=0;
for(i=0;i<n_cl;i++)
for(j=i+1;j<n_cl;j++)
{m=0;
for(k=0;k<n_rl;k++)
if(set[i][k]&&set[j][k])m++;
s+=m*(m-1)/2;
}
cout<<s<<endl;
}
return 0;
}
							

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

#include<iostream>
using namespace std;
int links[101][101];
int f[101],s[101],n,m;
int answer;

void find()
{int i,j,t,k,h;
    links[0][0]=0;
    links[0][1]=0;
    links[1][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{t=links[i-1][j]>links[i][j-1]?links[i-1][j]:links[i][j-1];
 if(f[i]!=s[j])
 {
 for(k=i-1;k>=1;k--)
     if(f[k]==s[j])break;
 for(h=j-1;h>=1;h--)
     if(f[i]==s[h])break;
 if(k&&h&&links[k-1][h-1]+1>t)t=links[k-1][h-1]+1;
 }
 links[i][j]=t;
}
}


int main()
{int i,t;
    cin>>t;
    while(t--)
    {cin>>n>>m;
        for(i=1;i<=n;i++)cin>>f[i];
        for(i=1;i<=m;i++)cin>>s[i];
        find();
        cout<<links[n][m]*2<<endl;
    }
return 0;
}
							

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

#include<iostream>
#include"vector"
#include"algorithm"
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))

using namespace std;

struct point
{long x,y;};

struct type_dbx
{int n;
point d[50];    
};

type_dbx dbx[50];

vector <long> x,y;
long mx,my;
int n;

char sign[50*50*2];


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


int in(point p[50],int n,point judge)
{int c,k,j;point up,low,temp;
 c=0;
   j=0;
   while(p[j].y==judge.y)j++;
   for(;j<n;j=k)
  {k=j+1;
    while(p[k%n].y==judge.y&&p[k%n].x>judge.x)k++;
    up=p[j];
    low=p[k%n];

    if(up.y<low.y){temp=up;up=low;low=temp;}

    if(up.y<judge.y||low.y>judge.y)continue;

    if(cheng(low,up,judge)<=0&&k==j+1)continue;
    c++;
    }
   return c%2;
}
    

int com(long a,long b)
{return a>b;}

int main()
{int t,m,i,j,k,h,l;long s,xz[50*50+4],yz[50*50+4];
    point p;
    cin>>t;    
    while(t--)
    {cin>>mx>>my>>n;
    mx*=2;my*=2;
    m=2;
    xz[0]=0;yz[0]=0;
    xz[1]=mx;yz[1]=my;
    
    for(i=0;i<n;i++)
    {cin>>dbx[i].n;
    
    for(j=0;j<dbx[i].n;j++)
        {cin>>dbx[i].d[j].x>>dbx[i].d[j].y;
        dbx[i].d[j].y=my/2-dbx[i].d[j].y;
        dbx[i].d[j].x*=2;
        dbx[i].d[j].y*=2;                        
              xz[m]=dbx[i].d[j].x;yz[m]=dbx[i].d[j].y;m++;
        }
    }
    x.resize(m);
    y.resize(m);
    for(i=0;i<m;i++){x[i]=xz[i];y[i]=yz[i];}    
    sort(x.begin(),x.end(),com);
    sort(y.begin(),y.end(),com);    
    for(i=0;i<m+2;i++)sign[i]=0;    
    sign[1]=1;    
    s=0;
    for(i=0;i<m-1;i++)
    {
    for(j=1;j<=m-1;j++)    
    {h=i;k=j-1;
    for(l=0;l<n;l++)
       {p.x=x[k]-1;
        p.y=y[h]-1;
       if(in(dbx[l].d,dbx[l].n,p))break;
        }
    if(l<n){sign[j]=0;continue;}
                    
    if(sign[j]||sign[j-1])sign[j]=1;
            
    else {sign[j]=0;s+=(x[k]-x[k+1])*(y[h]-y[h+1]);}
//        cout<<x[k]<<' '<<x[k+1]<<' '<<y[h]<<' '<<y[h+1]<<endl;}
    
    }
    }
        cout<<s/4<<endl;
    }
return 0;
}


							

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

#include<iostream>
#include"math.h"
using namespace std;
long x[50],y[50];
inline long cheng(int a,int  b,int c)
{return (x[a]-x[b])*(y[a]-y[c])-(x[a]-x[c])*(y[a]-y[b]);}
                   
int main()
{int t,n,m,p[50],h,key,i,j,l;char s[50];long an,anb;
        cin>>t;
        for(;t>0;t--)
        {cin>>n;
                for(i=0;i<n;i++)
                        cin>>x[i]>>y[i];
        cin>>m;key=0;anb=0;
        for(l=0;l<m;l++)
        {cin>>h;
       for(i=0;i<h;i++){cin>>p[i];p[i]--;}
                  
        an=0;
        for(i=1;i<h-1;i++)
                {
                an+=cheng(p[0],p[i],p[i+1]);
                                                }
//      cout<<":::"<<an<<endl;
        if(abs(an)>anb){anb=abs(an);key=l+1; }
        }
                                                                                                                             
cout<<key<<endl;
        }
                
        return 1;
}
							

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

//* @author: 
import java.util.Scanner; 
import javax.script.ScriptEngine;   
import javax.script.ScriptEngineManager;   
import javax.script.ScriptException; 

public class Main{
    
    ScriptEngineManager factory = new ScriptEngineManager();   
    ScriptEngine engine = factory.getEngineByName("JavaScript");   
    Scanner cin=new Scanner(System.in);
    
    int[] num=new int[60];
    void init()
    {
        for(int i=1;i< 59;i++)
            num[i]=i+9997;
    }
    void solve() throws ScriptException
    {
        int numCase=cin.nextInt();
        String s1,s2;
        s1=cin.nextLine();
        for(int k=1;k<=numCase;k++)
        {
            s1=cin.nextLine();
            s2=cin.nextLine();
            for(int i=0;i< 52;i++)
            {
                s1=s1.replace(String.valueOf((char)(i+'a')), String.valueOf(num[i+1]));
                s2=s2.replace(String.valueOf((char)(i+'a')), String.valueOf(num[i+1]));    

       
            }
            Object o1= engine.eval(s1);
            Object o2= engine.eval(s2);
            if(o1.toString().endsWith(o2.toString()))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    public static void main(String[] args) throws ScriptException {   
         Main jason=new Main();
         jason.init();
         jason.solve();
    }   
}

							

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

#include<iostream>
#include"math.h"
#include"stdio.h"
using namespace std;
double x[60][2],y[60][2],xs,ys,xt,yt;

double best1[62][2],best2[62][2],len[62];
int color[60],cl,c[62];

inline double  jl(double a,double c,double b,double d)
{return sqrt((a-b)*(a-b)+(c-d)*(c-d));}

int main()
{int t,i,j,k,n;double ss,tt;
    cin>>t;
    for(;t>0;t--)
    {cin>>xs>>ys>>xt>>yt;
    cin>>cl;
    for(i=0;i<cl;i++)cin>>color[i];
    cin>>n;
    for(i=0;i<n;i++){cin>>x[i][0]>>y[i][0]>>x[i][1]>>y[i][1]>>c[i];
                len[i]=jl(x[i][0],y[i][0],x[i][1],y[i][1]);}

    for(i=0;i<n;i++)
        if(c[i]==color[0]){best1[i][0]=jl(xs,ys,x[i][0],y[i][0])+len[i];
                            best1[i][1]=jl(xs,ys,x[i][1],y[i][1])+len[i];}
        else best1[i][0]=best1[i][1]=999999999999;

    
    for(i=1;i<cl;i++)
    {for(j=0;j<n;j++){best2[j][0]=best1[j][0];best2[j][1]=best1[j][1];}
     for(j=0;j<n;j++)
     {best1[j][0]=9999999999;best1[j][1]=9999999999999;
        if(c[j]==color[i])
        
            for(k=0;k<n;k++)if(c[k]==color[i-1]){
                ss=best2[k][0]+jl(x[k][1],y[k][1],x[j][0],y[j][0]);
                tt=best2[k][1]+jl(x[k][0],y[k][0],x[j][0],y[j][0]);
                if(tt<ss)ss=tt;
                
                if(ss+len[j]<best1[j][0])best1[j][0]=ss+len[j];
                
                ss=best2[k][0]+jl(x[k][1],y[k][1],x[j][1],y[j][1]);
                tt=best2[k][1]+jl(x[k][0],y[k][0],x[j][1],y[j][1]);
                if(tt<ss)ss=tt;
                
                if(ss+len[j]<best1[j][1])best1[j][1]=ss+len[j];
                                                }

     }
    }
    double answer=2000000000;
    for(i=0;i<n;i++)
        if(c[i]==color[cl-1]){tt=best1[i][0]+jl(x[i][1],y[i][1],xt,yt);
                              ss=best1[i][1]+jl(x[i][0],y[i][0],xt,yt);    
                            if(tt<ss)ss=tt;
                            if(answer>ss)answer=ss;
                        }
    
    printf("%.3fn",answer);
    }
return 1;
}
    
							

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

#include<iostream>
using namespace std;
int h[50][8],n,m;
char obj[8][8];
int sign[50][50];
int alive[50];

int can(int i,int j)
{int k;
    for(k=0;k<n;k++)
    if(h[i][k]*h[j][k]>0)break;

    if(k==n)return 1;
    else return 0;
}

void merage(int a,int b)
{int i;
for(i=0;i<n;i++)h[a][i]+=h[b][i];

for(i=0;i<n*m;i++){sign[a][i]+=sign[b][i];sign[i][a]+=sign[i][b];}
alive[b]=-a;
}


int main()
{int t,i,j,k,l,a,b,d;char c;
cin>>t;
for(;t>0;t--)
{cin>>n>>m;
for(i=0;i<n;i++)cin>>obj[i];

for(i=0;i<n*m;i++){alive[i]=1;}

for(i=0;i<n*m;i++)
{for(j=0;j<n;j++)h[i][j]=0;
h[i][i/m]=i%m+1;
}

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


while(1)
{cin>>i>>j>>c>>k>>l;if(i==0)break;
i--;j--;k--;l--;
if(c=='R'){a=i*m+j;b=k*m+l;
    while(alive[a]<1)a=-alive[a];
     while(alive[b]<1)b=-alive[b];
     merage(a,b);
    }
if(c=='N'){a=i*m+j;b=k*m+l;
        while(alive[a]<1)a=-alive[a];
         while(alive[b]<1)b=-alive[b];
    sign[b][a]=sign[a][b]=1;
    }
}
/*

for(i=0;i<n*m;i++)
{cout<<alive[i]<<" : ";
    for(j=0;j<n;j++)if(h[i][j])cout<<obj[j][h[i][j]-1];
cout<<endl;
}

for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)cout<<sign[i][j];
cout<<endl;
}
*/
for(i=0;i<n*m;i++)
if(alive[i]>0)    
{ for(d=0;d<n;d++)
  if(d!=i)
  {k=-1;
    for(j=0;j<m;j++)    
    {l=d*m+j;while(alive[l]<1)l=-alive[l];
    if(l!=i&&!sign[i][l]&&alive[l]>0&&can(i,l)){if(k!=-1)break;else k=l;}
    }
    
   if(j==m&&k>=0){merage(i,k);d=n*m;i=-1;}
  }
}

//cout<<"**********"<<endl;
for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)
 if(alive[j]>0&&h[j][0]==i+1)break;
 if(j<n*m){for(k=0;k<n;k++)cout<<obj[k][h[j][k]-1];cout<<endl;}
}
cout<<endl;
/*for(i=0;i<n*m;i++)
{cout<<alive[i]<<" : ";
            for(j=0;j<n;j++)if(h[i][j])cout<<obj[j][h[i][j]-1];
        cout<<endl;
}
                                                                              
for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)cout<<sign[i][j];
    cout<<endl;
}

for(i=0;i<n*m;i++)
{for(k=0;k<n;k++)cout<<obj[k][h[i][k]-1];cout<<endl;}

cout<<"**********"<<endl;*/
} 

return 1;
}    
							

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

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

public class Main {

 static Scanner in = new Scanner(System.in);
 static char[][] board;//���ڱ����ʼ״̬
 static boolean[][] map;//ǽ�ڵ�״̬
 static int cnt;//Ϳ��Ĵ���
    
 static void click(int x, int y) {//Ϳ��x,y)���ĸ���
    ++cnt;
    map[x][y] = !map[x][y];
    if(x-1>=0) map[x-1][y] = !map[x-1][y];//����ĸ���
    if(y-1>=0) map[x][y-1] = !map[x][y-1];//��ߵĸ���
    if(x+1< map.length) map[x+1][y] = !map[x+1][y];//����ĸ���
    if(y+1< map[x].length) map[x][y+1] = !map[x][y+1];//�ұߵĸ���
  }
    

 static int check(int s) {
   cnt = 0;
  for(int i=0; i!=map.length; ++i)//��ʼ״̬
    for(int j=0; j!=map[i].length; ++j)
        map[i][j] = board[i][j]=='w';
  for(int i=0; i!=map[0].length; ++i)//ȷ����һ�еľ������
           if((s&(1<< i))!=0)
        click(0, i);
                
  for(int i=1; i!=map.length; ++i)//Ϳ�ڶ��������һ��
       for(int j=0;j!=map[i].length; ++j)
        if(map[i-1][j]) click(i, j);
                
  for(int j=0; j!=map[map.length-1].length; ++j)//������һ���Ƿ�ȫ�ǻ�ɫ
    if(map[map.length-1][j]) return Integer.MAX_VALUE;
        return cnt;
  }
    
    
 public static void main(String[] args) {
   int t = in.nextInt();//���Դ���
   while(t-->0) {
    int n = in.nextInt();//���ӵĹ�ģ
    board = new char[n][];
    for(int i=0; i!=n; ++i) {
        board[i] = in.next().toCharArray();
    }
    map = new boolean[n][n];
    int ans = Integer.MAX_VALUE;
    for(int i=0; i!=(1 << n); ++i) {//��һ����2^n�ֱ仯����ÿһ�ֱ仯����
        ans = Math.min(ans, check(i));
    }
    if(ans< Integer.MAX_VALUE) System.out.println(ans);
    else System.out.println("inf");
   }
 }

}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Edge{
    int u,v,disten;
    void set(int u,int v,int disten){
        this.u = u;
        this.v = v;
        this.disten = disten;
    }
}
interface MST{
    int N = 100+2,BIG = 1000000000;
    int getMST(int op);
}
class UniqueMST implements MST{
    int n,m;
    Edge edge[] = new Edge[N];
    int Graph[][] = new int[N][N];
    
    UniqueMST(){
        for(int i=0;i< N;++i){
            edge[i] = new Edge();
        }
    }
    
String Unique(){
    int ans = -1;
    ans = getMST(0);
    for(int i=0;i< n-1;++i){
     Graph[edge[i].u][edge[i].v] = Graph[edge[i].v][edge[i].u] = BIG;
     int cnt = getMST(1);
     if(ans==cnt) return "Not Unique!";
     Graph[edge[i].u][edge[i].v] = Graph[edge[i].v][edge[i].u] = edge[i].disten;
    }
    return String.valueOf(ans);
}

public int getMST(int op){
    int ans = 0;
    int meat[][] = new int[2][N];
    boolean s[] = new boolean[N];
    Arrays.fill(s, false);
    s[1] = true;meat[1][1] = 0;meat[0][1] = 1;
    for(int i=2;i<=n;++i){
     meat[0][i] = 1;    //meat[0][i]��¼��ǰ��i��ǰ�����˭��
     meat[1][i] = Graph[1][i];    //meat[1][i]��¼��i����С���롣
    }
    
    for(int i=0;i< n-1;++i){
            
    int k=-1,Min = 0;
    for(int j=1;j<=n;++j) if(!s[j]){
        if(k==-1 || (k!=-1 && meat[1][j]< Min)){
            k = j;
            Min = meat[1][j];
        }
    }
    if(op==0){
        edge[i].set(meat[0][k], k, Min);
    }
    ans+=Min;
    s[k] = true;
    for(int j=1;j<=n;++j) if(!s[j]){
        if(Graph[k][j]< meat[1][j]){
            meat[0][j] = k;
            meat[1][j] = Graph[k][j];
        }
    }
    }
   return ans;
 }
 
void initGraph(){
    for(int i=0;i< N;++i){
        for(int j=0;j< N;++j) Graph[i][j] = BIG;
    }
 }
 void addEdge(Edge e){
    Graph[e.v][e.u] = Graph[e.u][e.v] = e.disten;
 }
}
public class Main {
    
 public static void main(String[]args)throws Exception{
  UniqueMST uniqueMst = new UniqueMST();
    
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
  int Case = GetNum(cin);
  Edge edge = new Edge();
  while(Case--!=0){
    uniqueMst.n = GetNum(cin);
    uniqueMst.m = GetNum(cin);
    uniqueMst.initGraph();
    for(int i=0;i< uniqueMst.m;++i){
        edge.set(GetNum(cin), GetNum(cin), GetNum(cin));
        uniqueMst.addEdge(edge);
    }
    System.out.println(uniqueMst.Unique());
   }
 }

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

							

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

//* @author 
/**
 * pku 1677 Girls' Day
 * Memory: 3524K  Time: 172MS 
 * Language: Java  Result: Accepted 
 * @Author    conanhjj
 */
import java.util.*;

public class Main {

 static Scanner in = new Scanner(System.in);

 static int g,w;
 static String[] girl;
 public static void main(String[] args){
    input();
    work();
 }

 static void work() {
  String line;
  for(int i=0;i< w;++i){
    do{
         line = in .nextLine();
       }while(line.length()==0);

    LinkedList<String> words = new LinkedList<String>(Arrays.asList(line.split("[\s|!]+")));
    if(words.size()>0 && words.peek().equals(""))
        words.removeFirst();
        //    System.out.println(words);

    boolean flag = false;
    boolean xixi = false;
    boolean[] mark = new boolean[g];
    for(int k=0;k< mark.length;++k) mark[k] =false;
    for(String word : words){
        word = word.toLowerCase();
        if(word.equals("beautiful") || word.equals("pretty") ||
                word.equals("lovely")){
            xixi = true;
          }

        for(int k=0;k< g;++k) {
            if(word.equals(girl[k]) && !mark[k]){
                mark[k] = true;
                flag = true;
            }
        }
    }

    if(!flag){
        System.out.print("All");
    } else {
        boolean first = true;
        for(int k=0;k< g;++k) {
            if(mark[k]){
                if(first){
                    System.out.print(girl[k]);
                    first = false;
                } else {
                    System.out.print(" " + girl[k]);
                }
            }
        }
    }

    System.out.print(": ");
    if(words.size() <= 9 ){
        System.out.println("oh");
    } else {
        if(xixi){
            System.out.println("xixi");
        } else {
            System.out.println("hehe");
        }
    }

  }
 }

 static void input(){
     g = in.nextInt();
    w = in.nextInt();

    girl = new String[g];
    for(int i=0;i< g;++i){
        girl[i] = in.next();
        //System.out.println(girl[i]);
    }
   }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int[] N=new int[]{    119,36,93,109,46,107,123,37,127,111};
  while((a--)!=0)
  {
   int[] Num1=new int[4];
   int[] Num2=new int[4];
   String line=in.readLine();
   ///////////////////��һ��///////////////////////////
   for(int i=0;i< 4;i++)
   {
    if(line.charAt(i*3+1)!=' ') Num1[i]|=1;
    if(line.charAt(i*3+14)!=' ') Num2[i]|=1;
    }
   //////////////////////��///////////////////////
   line=in.readLine();
   for(int i=0;i< 4;i++)
   {
    if(line.charAt(i*3)!=' ') Num1[i]|=2;
    if(line.charAt(i*3+13)!=' ') Num2[i]|=2;
    if(line.charAt(i*3+1)!=' ') Num1[i]|=8;
    if(line.charAt(i*3+14)!=' ') Num2[i]|=8;
    if(line.charAt(i*3+2)!=' ') Num1[i]|=4;
    if(line.charAt(i*3+15)!=' ') Num2[i]|=4;
    }
    
   /////////////////////////��/////////////////////////
   line=in.readLine();
   for(int i=0;i< 4;i++)
   {
    if(line.charAt(i*3)!=' ') Num1[i]|=16;
    if(line.charAt(i*3+13)!=' ') Num2[i]|=16;
    if(line.charAt(i*3+1)!=' ') Num1[i]|=64;
    if(line.charAt(i*3+14)!=' ') Num2[i]|=64;
    if(line.charAt(i*3+2)!=' ') Num1[i]|=32;
    if(line.charAt(i*3+15)!=' ') Num2[i]|=32;
    }

   /////////////////////////////////////////
  int cnt=0,clo1,clo2,tim1,tim2;
  int a1=0,a2=0,a3=0,a4=0;
  for(int i=0;i< 6;i++)
  {
    if((Num1[2]|N[i])!=N[i]) continue;
    for(int j=0;j< 10;j++)
    {
    if((Num1[3]|N[j])!=N[j]) continue;
    for(int m=0;m< 6;m++)
    {
      if((Num2[2]|N[m])!=N[m]) continue;
      for(int n=0;n< 10;n++)
      {
        if((Num2[3]|N[n])!=N[n]) continue;
         for(int u1=0;u1< 3;u1++)
         {
        if((Num1[0]|N[u1])!=N[u1]) continue;
        for(int u2=0;u2< 3;u2++)
        {
          if((Num2[0]|N[u2])!=N[u2]) continue;
          for(int d1=0;d1< 10;d1++)
          {
           if(u1==2&&d1>3)break;
           if((Num1[1]|N[d1])!=N[d1]) continue;
           for(int d2=0;d2< 10;d2++)
           {
            if(u2==2&&d2>3)break;
            if((Num2[1]|N[d2])!=N[d2]) continue;
            tim1=10*i+j;
            tim2=10*m+n;
            clo1=10*u1+d1;
            clo2=10*u2+d2;
            if((clo1==clo2&&tim1==tim2+15)||(clo1==clo2+1&&tim1+45==tim2)
            ||(clo1==0&&clo2==23&&tim1+45==tim2))
            {
            cnt++;
            a1=u1;
            a2=d1;
            a3=i;
            a4=j;
             }
                            
          }
          }
       }
       }
     }
   }
  }
 }
    if(cnt>1)System.out.println("Not Sure");
    else 
    System.out.println(a1+""+a2+""+a3+""+a4);
 }
}
}
							

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

/* @author:����acmilan_fan@yahoo.cn */
import java.io.*;
public class Main {
    static double A = Math.PI*2/3;
    public static void main(String[] args)throws Exception{
        
        BufferedReader br = new BufferedReader(new
                InputStreamReader(System.in));
        String s = br.readLine();
        String[] ss;
        int num = Integer.parseInt(s);
        int x1, y1, x2, y2, x3, y3;
        for(int i=0;i< num;i++){
            s = br.readLine();
            ss = s.split(" ",7);
            x1 = Integer.parseInt(ss[1]);
            y1 = Integer.parseInt(ss[2]);
            x2 = Integer.parseInt(ss[3]);
            y2 = Integer.parseInt(ss[4]);
            x3 = Integer.parseInt(ss[5]);
            y3 = Integer.parseInt(ss[6]);
            System.out.println(checkPos(x1, y1, x2, y2, x3, y3)?"Yes":"No");
        }
    }
    
    static boolean checkPos(int x1, int y1, int x2, int y2, int x3, int y3){
        //if one is in the center, this is impossible
        if(x1==0 && y1==0 || x2==0 && y2==0 || x3==0 && y3==0)
            return false;
        double angle = Math.atan2(x1, y1);
        double angle2 = Math.atan2(x2, y2);
        double angle3 = Math.atan2(x3, y3);
        //if two points are of the same angle
        if(angle==angle2 || angle2==angle3 || angle3==angle)
            return false;
        double d12 = get(angle, angle2);
        double d23 = get(angle2, angle3);
        double d31 = get(angle3, angle);
        //120 degrees each
        if(d12==d23 && d23==d31 && d31==d12)
            return true;
        //maximum distinction is less than 120 degrees
        if(checkVal(d12) && checkVal(d23) && checkVal(d31))
            return false;
        return true;
    }
    static double get(double a, double a2){
        double dis = Math.abs(a-a2);
        return dis>Math.PI ? 2*Math.PI-dis:dis;
    }
    static boolean checkVal(double d){
        return d<=A;
    }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss;
  int a=Integer.parseInt(in.readLine());
  HashSet< Integer> hs=new HashSet< Integer>();
  while((a--)!=0)
  {
    int b=Integer.parseInt(in.readLine());
    ss=in.readLine().split(" ");
    int[] arr=new int[b+1];
    for(int i=0;i< b;i++)
        arr[i+1]=Integer.parseInt(ss[i]);
    int c=0;
    for(int i=1;i<=b;i++)
    {
         int u=arr[i];
    if(!hs.contains(u))
    {
     while(!hs.contains(u))
      {
        hs.add(u);
        u=arr[u];
       }
       c++;
     }
       }
    System.out.println(b-c);
    hs.clear();
    }
  }        
}
							

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

import java.util.*;
public class Main{
 
 static double dp[][]=new double[51][51];
 static {
   dp[1][1]=1;
   for (int i=2;i<=50;i++)
     for(int j=1;j<=50;j++)
    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
  }


public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    while (sc.hasNext()) {
        int n=sc.nextInt();
        if(n==0) break;
     double ans=0;
     for (int i=1;i<=n;i++)
          ans+=dp[n][i];
     System.out.printf("%d %.0fn",n,ans);
    }
  }
}