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

import java.util.Scanner;

public class Main

{

 static final int Inf=9999999;

 public static void main(String[] args)

 {

    Scanner in=new Scanner(System.in);

    int cnt=0;

    while(true)

    {

        cnt++;

        int n=in.nextInt();

        int m=in.nextInt();

        if(n==0&&m==0)break;

        int[][] p=new int[n][n];

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

            for(int j=0;j< n;j++)

                p[i][j]=Inf;

        for(int i=0;i < m;i++)

        {

            int x=in.nextInt()-1;

            int y=in.nextInt()-1;

            int len=in.nextInt();

            p[x][y]=p[y][x]=len;

        }

        boolean[] bb=new boolean[n];

        bb[0]=true;

        int[] time=new int[n];

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

            time[i]=p[0][i];

        time[0]=0;

        for(int i=0;i< n-1;i++)

        {

            int min=Inf,tag=0;

            for(int j=0;j< n;j++)

            {

                if(!bb[j]&&time[j]< min)

                {

                    min=time[j];

                    tag=j;

                }

            }

            bb[tag]=true;

            for(int j=0;j< n;j++)

                if(!bb[j]&&p[tag][j]< Inf&&time[tag]+p[tag][j]< time[j])

                    time[j]=time[tag]+p[tag][j];

        }

        double maxtime=-Inf;

        int pos=-1;

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

        {

            if(time[i]>maxtime)

            {

                maxtime=time[i];

                pos=i;

            }

        }

        double max=-Inf,t;

        int pos1=-1,pos2=-1;

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

        {

            for(int j=i+1;j< n;j++)

            {

                t=(time[i]+time[j]+p[i][j])/2.0;

                if(p[i][j]< Inf&&t>max)

                {

                    max=t;

                    pos1=i;pos2=j;

                }

            }

        }

        System.out.println("System #"+cnt);

        System.out.print("The last domino falls after ");

        if(maxtime>=max)

            System.out.printf("%.1f seconds, at key domino %d.nn",maxtime,pos+1);

        else System.out.printf("%.1f seconds, between key dominoes %d and %d.nn",max,pos1+1,pos2+1);

    }

 }

}
							

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

#include<iostream>
#include"math.h"
#include<algorithm>
#include<vector>
using namespace std;
struct point
{long x,y;};
typedef point vect;

struct
{point p;
int bright;
}star[1001];

int sn,vn;
double v_sin,v_cos,bi;
vect vec[1001];
double len;
point pt[1001];

inline double jl(point &a,point &b)
{return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

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

void jiao(vect &a,vect &b)
{double t=sqrt(double(a.x*a.x+a.y*a.y)*(b.x*b.x+b.y*b.y));
v_sin=cheng(a,b)/t;//sqrt(a.x*a.x+a.y*a.y)/sqrt(b.x*b.x+b.y*b.y);
v_cos=(a.x*b.x+a.y*b.y)/t;//sqrt(a.x*a.x+a.y*a.y)/sqrt(b.x*b.x+b.y*b.y);
}

void sacal(vect &a,vect &b)
{bi=sqrt(double(b.x*b.x+b.y*b.y)/(a.x*a.x+a.y*a.y));}

inline double newx(double x,double y)
{return v_cos*x-v_sin*y;}
inline double newy(double x,double y)
{return v_sin*x+v_cos*y;}

int find(point &p)
{int i;
    for(i=0;i<sn;i++)if(star[i].p.x==p.x&&star[i].p.y==p.y)return i;
    return -1;
}
vector<int> answer;
long bright;long num;long self;


void judge(int s1,int s2)
{point a=star[s1].p,b=star[s2].p;
point p=b;
double x=0,y=0;int temp[1001];long br=star[s1].bright+star[s2].bright,at,bt;
vect v={b.x-a.x,b.y-a.y};
jiao(vec[1],v);
sacal(vec[1],v);

int i,s;
for(i=2;i<vn;i++)
    {x=bi*newx(vec[i].x,vec[i].y);y=bi*newy(vec[i].x,vec[i].y);
    at=long(x*1.00001);bt=long(y*1.00001);
    
    if(fabs(x-at)>0.000001)break;
    if(fabs(y-bt)>0.000001)break;

           
     p.x+=at;p.y+=bt;

    if((s=find(p))>=0){temp[i]=s;br+=star[s].bright;}
    else break;
    }
if(i<vn)return;
num++;
if(br>=bright){bright=br;answer[0]=s1;answer[1]=s2;
        for(i=2;i<vn;i++)answer[i]=temp[i];}
}    


void doit()
{bright=-9999999;num=0;
 for(int i=0;i<sn;i++)
 for(int j=0;j<sn;j++)
 if(i!=j) judge(i,j);
} 

int cmp(int i,int j)
{return star[i].p.x<star[j].p.x||
    (star[i].p.x==star[j].p.x&&star[i].p.y<star[j].p.y);}




int findself(point &p)
{int i;
    for(i=0;i<vn;i++)if(pt[i].x==p.x&&pt[i].y==p.y)return i;
    return -1;
}

void judgeself(int s1,int s2)
{point a=pt[s1],b=pt[s2];
point p=b;
double x,y;
vect v={b.x-a.x,b.y-a.y};
jiao(vec[1],v);
sacal(vec[1],v);

int i;
for(i=2;i<vn;i++)
    {x=bi*newx(vec[i].x,vec[i].y);
    if(fabs(x-floor(x))>0.0001)break;
     y=bi*newy(vec[i].x,vec[i].y);
     if(fabs(y-floor(y))>0.0001)break;

           
     p.x+=long(x*1.00001);p.y+=long(y*1.00001);

     if(findself(p)>=0){}
    else break;
    }
if(i<vn)return;
self++;

}    







int main()
{int i,j,a,b,c_n=0,t;
int x,y;char name[1000];
    while(1)
    {cin>>sn;if(sn==0)break;
    cout<<"Map #"<<++c_n<<endl;
    
    for(i=0;i<sn;i++)
    cin>>star[i].p.x>>star[i].p.y>>star[i].bright;
     
        
    
    cin>>t;
    while(t--)
    {cin>>vn;answer.resize(vn);
    
    cin>>name>>x>>y;
         
    pt[0].x=x;pt[0].y=y;
    vec[0].x=0;vec[0].y=0;    
    for(j=1;j<vn;j++)
    {cin>>a>>b;pt[j].x=a;pt[j].y=b;
    vec[j].x=a-x;vec[j].y=b-y;x=a;y=b;}

    if(vn==1)num=sn;        
    else {doit();self=0;
    
        for(i=0;i<vn;i++)
        for(j=0;j<vn;j++)
            if(i!=j)judgeself(i,j);
            num/=self;}
        

    cout<<endl<<name<<" occurs "<<num<<" time(s) in the map."<<endl;
    if(num){cout<<"Brightest occurrence:";
        if(vn==1){int q=0;
            for(j=1;j<sn;j++)
                if(star[j].bright>star[q].bright||
                (star[j].bright==star[q].bright&&cmp(j,q)))
                    q=j;
            cout<<" ("<<star[q].p.x<<","<<star[q].p.y<<")"<<endl;
            }    
        else {sort(answer.begin(),answer.end(),cmp);
            for(j=0;j<vn;j++)
            cout<<" ("<<star[answer[j]].p.x<<","
            <<star[answer[j]].p.y<<")";
        cout<<endl;}
        }
    }
    cout<<"-----"<<endl;
    }
    return 0;
}



							

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

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

#define NMAX 33
#define INF 1000000001
int xp[4]={0,1,0,-1},yp[4]={1,0,-1,0};
int dx[4]={0,0,-1,-1},dy[4]={0,-1,-1,0};
int stx,sty;
int map[NMAX][NMAX];
char in[NMAX*NMAX];

int set(char t)
{
    switch(t)
    {
    case 'N':return 0;
    case 'E':return 1;
    case 'S':return 2;
    case 'W':return 3;
    }
    return -1;
}
void solve()
{
    int i=0;
    int cx=stx,cy=sty;
    int direct;
    while(in[i]!='.')
    {
        direct=set(in[i]);
        map[cy+dy[direct]][cx+dx[direct]]=1;
        cx+=xp[direct];
        cy+=yp[direct];
        i++;
    }
    int j;
    for(i=31;i>=0;i--)
    {
        for(j=0;j<32;j++)
            if(map[i][j]==1)
                printf("X");
            else
                printf(".");
        printf("n");
    }
    printf("n");
}
int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t,i;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        printf("Bitmap #%dn",i);
        memset(map,0,sizeof(map));
        scanf("%d%d",&stx,&sty);
        
        scanf("%s",in);
        solve();
    }
#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}
							

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

import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
 public static void main(String[] args){
  Scanner cin=new Scanner(System.in);
  BigDecimal temp,sum,ans,num;
  String str;
  int i,len;
  while(cin.hasNext()){
   str=cin.next(); 
   len=str.length();
   temp=BigDecimal.valueOf(8.0);
   sum=BigDecimal.ONE;
   ans=BigDecimal.ZERO;
   for(i=2;i< len;i++)
   {
    int val=str.charAt(i)-'0';
    num=BigDecimal.valueOf(val);
    sum=sum.multiply(temp);
    ans=ans.add(num.divide(sum));
  }
  System.out.printf("%s [8] = ",str);
  System.out.println(ans+" [10]");
  }
 }
}

							

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

 import java.util.*;
import java.io.*;
/*
 *����������ŵ7��䡣��һ������ͼ��Ϊÿ����������ɫ��Ҫ���������ڵĶ�����ɫ��ͬ��
 * �����ٵ���ɫ���Ƕ���?
 *������������ɫ���?ֱ��ö����ɫ��+DFS������DFS�DZ�fö��ÿ�����ɫ���Ա��ҵ�һ����н⡣ 
 */
public class Main{
    
    public static int[][] g=new int[26][26];
    
    public static int solve(int n){
        int i,j,cnum;
        boolean tag=true;
        // �ޱ�ͼֻ��1ɫ����
        for(i=0;i< n && tag;i++){
            for(j=i+1;j< n && tag;j++){
                if(g[i][j]==1) 
                    tag=false;
            }
           }
        if(tag) 
            return 1;
        
        for(cnum=2;cnum<=4;cnum++)    // ö�ٴ�+dfs
        {
            int[] x=new int[n];
            Arrays.fill(x,-1);
            if(DFS(x,0,cnum,n)) 
                return cnum;
        }
        return -1;
    }
    
    //DFS�ĸ��Ӷ�����ɫ��^������(4^26�����п����Լ�֦����˺ܶ��֧) 
    public static boolean DFS(int[] x,int vnum, int cnum,int n){
        if(vnum == n) return true;    // v�Ķ��㶼��ɫ�����н�
        for(int i=0;i< cnum;i++){    // ���ij���û����ɫ�������һ��
            x[vnum] = i;
            if(check(vnum,x,i,n))         
                if(DFS(x,vnum+1,cnum,n)) // �Ϸ���ö����һ���
                    return true;
        }
        return false;
    }

    // �ж����ڵĶ����Ƿ���Ϳ��������ɫ
    public static boolean check(int vnum,int[] x,int t,int n){
        boolean find=true;
        for(int i=0;i< n && find;i++){
            if(g[vnum][i]==1 && x[i]==t)
                find=false;
        }
        return find;
    }
    
    public static void main(String rgs[]) throws Exception
    {  
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int i,j,n=cin.nextInt();
        while(n!=0){            
            for(i=0;i< n;i++)
                Arrays.fill(g[i],0);        
            for(i=0;i< n;i++){
                String s = cin.next();
                for(j=2;j< s.length();j++)
                    g[i][s.charAt(j)-'A']=1;
            }
            int count=solve(n);
            if(count==1)
                System.out.println(count+" channel needed.");
            else
                System.out.println(count+" channels needed.");
            n=cin.nextInt();
        }
    }
}

							

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

import java.util.Scanner;

public class Main {

/**
* @param args
*/

public static void main(String[] args) {
 Scanner s = new Scanner(System.in);
 String sentence = null;
 int count;
 char ch;
 while ((sentence = s.nextLine()) != null) {
   count = 0;// ��ǰ������
   for (int i = sentence.length() - 1; i >= 0; i--) {
    ch = sentence.charAt(i);
    if (ch >= 'p' && ch <= 'z') {
      count++;
    } else if (ch == 'C' || ch == 'D' || ch == 'E' || ch == 'I') {
      count--;
   if (count < 1)
     break;
   } else if (ch == 'N') {
     if (count < 1)
       break;
     } else {
       count = -1;
       break;
     }
   }
   if (count == 1) {
     System.out.println("YES");
   } else {
     System.out.println("NO");
   }
  }
 }
}

							

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

//* @author: 82638882@163.com
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
    static final int Inf=9999999;
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int a=in.nextInt();
        int[][] p=new int[a][a];
        for(int i=0;i< a;i++)
            for(int j=0;j< a;j++)
                p[i][j]=in.nextInt();
        int loc =in.nextInt()-1;
        boolean[] bb=new boolean[a];
        bb[loc]=true;
        int[] time=new int[a];
        int[] path=new int[a];
        for(int i=0;i< a;i++)
        {
            if(p[i][loc]!=-1)
            {
                time[i]=p[i][loc];
                path[i]=loc;
            }
            else
            {
                time[i]=Inf;
                path[i]=-1;
            }
        }
        for(int i=0;i< a-1;i++)
        {
            int min=Inf,tag=loc;
            for(int j=0;j< a;j++)
            {
                if(!bb[j]&&time[j]< min)
                {
                    min=time[j];
                    tag=j;
                }
            }
            bb[tag]=true;
            for(int j=0;j< a;j++)
                if(!bb[j]&&p[j][tag]!=-1&&time[tag]+p[j][tag]< time[j])
                {
                    time[j]=time[tag]+p[j][tag];
                    path[j]=tag;
                }
        }
        he[] arr=new he[a];
        int len=0;
        while(in.hasNextInt())
        {
            int u=in.nextInt();
            arr[len++]=new he(time[u-1],u-1);
        }
        System.out.println("Org    Dest    Time    Path");
        Arrays.sort(arr,0,len);
        for(int i=0;i< len;i++)
        {
         System.out.print((arr[i].loc+1)+"    "+(loc+1)+"    "+arr[i].time+"    "+(arr[i].loc+1));
         if(arr[i].loc==loc){
                System.out.println();
                continue;
            }
            int u=path[arr[i].loc];
            while(true)
            {
                System.out.print("    "+(u+1));
                if(u==loc)break;
                u=path[u];
            }
            System.out.println();
        }
    }
}
class he implements Comparable<he>
{
    int time,loc;
    public he(int t,int l)
    {
        time=t;
        loc=l;
    }
    @Override
    public int compareTo(he arg0) {
        // TODO Auto-generated method stub
        return time-arg0.time;
    }
}
    

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
   int map[][]=new int[22][22];
   int d[]=new int[16];
   char code[]={'.','!','X','#'};

   int sum(int i,int j){
    return map[i][j]+map[i-1][j]+map[i+1][j]+map[i][j-1]+map[i][j+1];
   }

  public void doIt(){
   Scanner sc=new Scanner(System.in);
   int n=sc.nextInt();

   for(int i=0;i< 16;i++)
    d[i]=sc.nextInt();

  for(int i=1;i<=20;i++)
   for(int j=1;j<=20;j++)
     map[i][j]=sc.nextInt();

   while((n--)!=0){
     int tem[][]=new int[22][22];
     for(int i=1;i<=20;i++)
    for(int j=1;j<=20;j++){
       tem[i][j]=map[i][j]+d[sum(i,j)];
       if(tem[i][j]>3)
         tem[i][j]=3;
       if(tem[i][j]< 0)
         tem[i][j]=0;
    }
    for(int i=1;i<=20;i++)
    for(int j=1;j<=20;j++){
        map[i][j]=tem[i][j];
    }
   }
  for(int i=1;i<=20;i++){
    for(int j=1;j<=20;j++){
    System.out.printf("%c",code[map[i][j]]);
    }
    System.out.println();
   }

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



							

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.HashMap;
import java.util.Map;

public class Main{

 private static String convertString(String s) {

  StringBuilder sb = new StringBuilder();

  for (int i = 0; i < s.length(); i++) {
   if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
    sb.append(s.charAt(i));
   } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
    sb.append(s.charAt(i));
   }
  }

  return sb.toString();
 }

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

  String pre = "";

  String line = "";

  Map< String, Integer> document = new HashMap< String, Integer>();

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

   pre = line;

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

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

   for (int i = 0; i < s.length; i++) {
    String str = convertString(s[i]);

    if (str.length() > 0) {
     Integer number = document.get(str);

     if (number == null) {
      document.put(str, 1);
     } else {
      document.put(str, number + 1);
     }
    }
   }

  }

  // System.out.println(document);

  while (true) {

   double sum = 0;

   Map< String, Integer> search = new HashMap< String, Integer>();

   while (true) {

    pre = line;
    line = stdin.readLine().trim().toLowerCase();

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

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

    for (int i = 0; i < temp.length; i++) {
     String str = convertString(temp[i]);

     if (str.length() > 0) {
      Integer number = search.get(str);

      if (number == null) {
       search.put(str, 1);
      } else {
       search.put(str, number + 1);
      }
     }
    }
   }

   for (Map.Entry< String, Integer> entry : search.entrySet()) {
    if (document.keySet().contains(entry.getKey())) {

     sum += Math.sqrt(entry.getValue() * document.get(entry.getKey()));
    }
   }

   if ("----------".equals(line) && "----------".equals(pre)) {
    break;
   }

   System.out.println(new BigDecimal(sum).setScale(2, RoundingMode.HALF_UP));

   // double sum =0;

  }

 }

}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {    
   int a=in.nextInt();
   if(a==0)break;
    int[] arrx=new int[a];
    int[] arry=new int[a];
    for(int i=0;i< a;i++)
    {
        arrx[i]=in.nextInt();
        arry[i]=in.nextInt();
    }
    int max=0;
    for(int i=0;i< a-2;i++)
    {
        for(int j=i+1;j< a-1;j++)
        {
            int c=0;
            for(int u=j+1;u< a;u++)
            {
    if((arrx[i]-arrx[u])*(arry[i]-arry[j])==(arrx[i]-arrx[j])*(arry[i]-arry[u]))c++;
            }
            if(c>max)max=c;
        }
    }
    System.out.println(max+2);
    }
  }
}
							

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

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

public class Main { 

    class Point { 
        int x; 
        int y; 

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

    public static void main(String[] args) throws IOException { 
        Main main = new Main(); 
        BufferedReader read = new BufferedReader(new InputStreamReader( 
                System.in)); 
        String[] s; 
        s = read.readLine().split(" "); 
        int n = Integer.parseInt(s[0]); 
        int l = Integer.parseInt(s[1]); 
        int x, y; 
        Point[] p = new Point[n]; 
        for (int i = 0; i < n; i++) { 
            s = read.readLine().split(" "); 
            x = Integer.parseInt(s[0]); 
            y = Integer.parseInt(s[1]); 
            p[i] = main.new Point(x, y); 
        } 
        Point[] ch = new Point[n]; 
        int len = 0; 
        if (n >= 3) { 
            len = Graham_scan(p, ch, n); 
        } 
        double sum = 0; 
        for (int i = 0; i < len - 1; i++) { 
            sum += distance(ch[i], ch[i + 1]); 
        } 
        if (len > 1) { 
            sum += distance(ch[len - 1], ch[0]); 
        } 
        sum += 2 * l * Math.PI; 
        System.out.println(Math.round(sum)); 

    } 

    public static double multiply(Point p1, Point p2, Point p0) { 
        return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y)); 
    } 

    public static double distance(Point p1, Point p2) { 
        return (Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) 
                * (p1.y - p2.y))); 
    } 

    public static int Graham_scan(Point[] PointSet, Point[] ch, int n) { 
        int i, j, k = 0, top = 2; 
        Point tmp; 
        for (i = 1; i < n; i++) 
            if ((PointSet[i].y < PointSet[k].y) 
                    || ((PointSet[i].y == PointSet[k].y) && (PointSet[i].x < PointSet[k].x))) 
                k = i; 
        tmp = PointSet[0]; 
        PointSet[0] = PointSet[k]; 
        PointSet[k] = tmp; 
        for (i = 1; i < n - 1; i++) { 
            k = i; 
            for (j = i + 1; j < n; j++) 
                if ((multiply(PointSet[j], PointSet[k], PointSet[0]) > 0) 
                        || ((multiply(PointSet[j], PointSet[k], PointSet[0]) == 0) && (distance( 
                                PointSet[0], PointSet[j]) < distance( 
                                PointSet[0], PointSet[k])))) 
                    k = j; 
            tmp = PointSet[i]; 
            PointSet[i] = PointSet[k]; 
            PointSet[k] = tmp; 
        } 
        ch[0] = PointSet[0]; 
        ch[1] = PointSet[1]; 
        ch[2] = PointSet[2]; 
        for (i = 3; i < n; i++) { 
            while (top > 0 && multiply(PointSet[i], ch[top], ch[top - 1]) >= 0) 
                top--; 
            ch[++top] = PointSet[i]; 
        } 
        return top + 1; 
    } 
} 

							

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

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

using namespace std;

vector<int> unknow[100];
vector< pair<int,int> > s;

int sign[100];
bool e[100][100];
int flag[110][110];

int a, b, an, bn;

bool search( int k, int key )
{
    int i;

    sign[k] = key;

    if( key == a ) an++;
    else bn++;

    for( i=0; i<unknow[k].size(); i++ )
        if( sign[ unknow[k][i] ] == 0 )
        {
            if( !search( unknow[k][i], a+b-key ) ) 
                return false;
        }
        else if( sign[ unknow[k][i] ] == key ) 
            return false;

    return true;
}


int main()
{
    int n, i, j, k, x, y;

    scanf( "%d", &n );

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

    for( i=0; i<n; i++ )
    {
        unknow[i].clear();
        while( 1 )
        {
            scanf( "%d", &j );
            if( j == 0 ) break;
            j--;
            e[i][j] = true;
        }
    }

    for( i=0; i<n; i++ )
    for( j=0; j<n; j++ )
        if( !e[i][j] || !e[j][i] ) unknow[i].push_back( j );
    

    memset( sign, 0, sizeof(sign) );
    memset( flag, 0, sizeof(flag) );

    a = 1, b = 2;

    s.clear();
    for( i=0; i<n; i++ )
        if( sign[i] == 0 )
        {
            
            an = bn = 0;
            if( !search( i, a ) ) break;

            s.push_back( pair<int,int>( an, bn ) );
            a += 2, b += 2;
        }

    if( i < n )
    {
        printf( "No solutionn" );
        return 0;
    }

    flag[0][0] = true;

    for( k=0; k<s.size(); k++ )
    for( i=n-1; i>=0; i-- )
    for( j=n-1; j>=0; j-- )
        if( flag[i][j] != 0 )
        {
            if( ( x = s[k].first+i ) < n && ( y = s[k].second+j ) < n && !flag[x][y] )
                flag[x][y] = k+1;
            if( ( x = s[k].first+j ) < n && ( y = s[k].second+i ) < n && !flag[y][x] )
                flag[y][x] = -(k+1);
        }

    x = 0; y = n;
    for( i=1; i<n; i++ )
        if( flag[i][n-i] != 0 && abs( i*2-n ) < y )
            x = i, y = abs( i*2-n );

    y = n-x;

    vector< int > s1,s2;

    while( x || y )
    {
        k = abs( flag[x][y] ) - 1;
        a = k*2+1; b = k*2+2;

        if( flag[x][y] < 0 ) swap( a, b );

        for( i=0; i<n; i++ )
            if( sign[i] == a )
                s1.push_back( i+1 );
            else if( sign[i] == b )
                s2.push_back( i+1 );

        a = s[k].first, b = s[k].second;
        if( flag[x][y] < 0 ) swap( a, b );

        x -= a, y-=b;
    }

    printf( "%d", s1.size() );
    for( i=0; i<s1.size(); i++ )
        printf( " %d", s1[i] );
    printf( "n" );

    printf( "%d", s2.size() );
    for( i=0; i<s2.size(); i++ )
        printf( " %d", s2[i] );
    printf( "n" );

    return 0;
}




							

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

//* @author: 82638882@163.com
import java.io.*;
class Main
{
    static int cnt;
    static char[][] map;
    static int[][] bool;
    public static void main(String[] args) throws IOException
    {
        InputStreamReader is=new InputStreamReader(System.in);
        BufferedReader in=new BufferedReader(is);
        while(true)
        {
            cnt=0;
            String[] ss=in.readLine().split(" ");
            int row=Integer.parseInt(ss[0]);
            int col=Integer.parseInt(ss[1]);
            int x=Integer.parseInt(ss[2]);
            int y=Integer.parseInt(ss[3]);
            if(row==0&&col==0)break;
            map=new char[row+2][col+2];
            bool=new int[row+2][col+2];
            for(int i=1;i<=row;i++)
            {
                for(int j=1;j<=col;j++)
                    map[i][j]=(char)in.read();
                in.readLine();
            }
            f(x,y);
            System.out.println(cnt);
        }
    }
    static void f(int x,int y)
    {
        if(bool[x][y]==1)return;
        bool[x][y]=1;
        if (map[x-1][y]!='X')cnt++;
        if (map[x+1][y]!='X')cnt++;
        if (map[x][y-1]!='X')cnt++;
        if (map[x][y+1]!='X')cnt++;
        for(int i=x-1;i< x+2;i++)
            for(int j=y-1;j< y+2;j++)
                if(map[i][j]=='X')f(i,j);    
    }
}

							

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

#include "stdio.h"


char map[80][10][80];
int n;

int main( ) {
    int n, r, c, i, j, k, l, test = 0;
    while( scanf( "%d%d%d", &n, &r, &c ) == 3 ) {

        if( n == 0 )
            break;

        for( i=0; i<r; i++ ) {
            for( k=0; k<n; k++ )
                scanf( "%s", map[k][i] );
        }

        for( k=0; k<n; k++ ) {
            for( i=0; i<r*c; i++ ) {
                if( map[k][i/c][i%c] != '.' ) {
                    for( l=0; l<n; l++ )
                        if( l!=k && map[l][i/c][i%c] != '.' )
                            break;
                    if( l == n )
                        break;
                }
            }
            if( i < r*c )
                map[k][i/c][i%c] = '#';
            else {
                for( i=0; i<r*c; i++ ) {
                    if( map[k][i/c][i%c] != '.' ) {
                        for( j=i+1; j<r*c; j++ ) {
                            if( map[k][j/c][j%c] != '.' ) {
                                for( l=0; l<n; l++ )
                                    if( l!=k && map[l][i/c][i%c] != '.' && map[l][j/c][j%c] != '.' )
                                        break;
                                if( l == n )
                                    goto loop;
                            } //if
                        } //for
                    } //if
                }//for
loop:
                if( i < r*c )
                    map[k][i/c][i%c] = '#', map[k][j/c][j%c] = '#';
                else
                    break;
            }
        }

        printf( "Test %dn", ++test );
        if( k < n ) 
            printf( "impossiblen" );
        else for( i=0; i<r; i++ ) {
            for( k=0; k<n; k++ )
                printf( "%s%s", k?" ":"", map[k][i] );
            printf( "n" );
        }
    }
    return 0;
}
							

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

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<ctype.h>

struct window

{

    char c;

    int hig, wid;

    int rc, lc;

    bool al;

} wi[70];

char str[70];

int stack[70];

int top;

char res[70][70];

void change(int len, bool worh, int w)

{

    int rl, ll, rn, ln;

    if(isalpha(wi[w].c))

    {

        if(worh)//change wid

            wi[w].wid=len;

        else

            wi[w].hig=len;

        return ;

    }

    if(worh)

    {

        wi[w].wid=len;           //do not forget

        if(wi[w].c=='-')

        {

            change(len, worh, wi[w].lc);

            change(len, worh, wi[w].rc);

        }

        else

        {

            ll=wi[wi[w].lc].wid;

            rl=wi[wi[w].rc].wid;

            if((len*ll)%(rl+ll)==0)

                ln=len*ll/(rl+ll);

            else

                ln=len*ll/(rl+ll)+1;

            rn=len-ln;

            change(ln, worh, wi[w].lc);

            change(rn, worh, wi[w].rc);

        }

    }

    else

    {

        wi[w].hig=len;            //do not forget!

        if(wi[w].c=='|')

        {

            change(len, worh, wi[w].lc);

            change(len, worh, wi[w].rc);

        }

        else

        {

            ll=wi[wi[w].lc].hig;

            rl=wi[wi[w].rc].hig;

            if((len*ll)%(rl+ll)==0)

                ln=len*ll/(rl+ll);

            else

                ln=len*ll/(rl+ll)+1;

            rn=len-ln;

            change(ln, worh, wi[w].lc);

            change(rn, worh, wi[w].rc);

        }

    }

    return;

}

void together(int a, int b, int d)

{

    if(wi[a].c=='-')

    {

        if(wi[b].wid!=wi[d].wid)

        {

            if(wi[b].wid>wi[d].wid)

                change(wi[b].wid, true, d);

            else

                change(wi[d].wid, true, b);

        }

        wi[a].wid=wi[b].wid;

        wi[a].hig=wi[b].hig+wi[d].hig;

    }

    else

    {

        if(wi[b].hig!=wi[d].hig)

        {

            if(wi[b].hig>wi[d].hig)

                change(wi[b].hig, false, d);

            else

                change(wi[d].hig, false, b);

        }

        wi[a].wid=wi[b].wid+wi[d].wid;

        wi[a].hig=wi[b].hig;

    }

    wi[a].al=true;

    wi[a].lc=b;

    wi[a].rc=d;

}

void construct(int sx, int sy, struct window *r)

{

    int i;

    if(isalpha(r->c))

    {

        res[sx][sy]=r->c;

        res[sx][sy+r->wid]=res[sx+r->hig][sy+r->wid]=res[sx+r->hig][sy]='*';

        for(i=sy+1; i<sy+r->wid; i++)

        {

            if(res[sx][i]!='*')

                res[sx][i]='-';

            if(res[sx+r->hig][i]!='*')

                res[sx+r->hig][i]='-';

        }

        for(i=sx+1; i<sx+r->hig; i++)

        {

            if(res[i][sy]!='*')

                res[i][sy]='|';

            if(res[i][sy+r->wid]!='*')

                res[i][sy+r->wid]='|';

        }

    }

    else if(r->c=='-')

    {

        construct(sx, sy, &wi[r->lc]);

        construct(sx+wi[r->lc].hig, sy, &wi[r->rc]);

    }

    else

    {

        construct(sx, sy, &wi[r->lc]);

        construct(sx, sy+wi[r->lc].wid, &wi[r->rc]);

    }

}

int main()

{

    int ca, t, i, j;

    char ch;

    scanf("%d", &ca);

    getchar();

    for(t=1; t<=ca; t++)

    {

        scanf("%s", str);

        top=0;

        for(i=0; i<70; i++)

        {

            wi[i].hig=wi[i].wid=0;

            wi[i].lc=wi[i].rc=-1;

        }

        for(i=0; str[i]!=''; i++)

        {

            wi[i].c=str[i];

            if(str[i]=='|'||str[i]=='-')

            {

                stack[top++]=i;

                wi[i].al=false;

            }

            else

            {

                wi[i].hig=wi[i].wid=2;

                wi[i].al=true;

                stack[top++]=i;

                if(top>=3 && wi[stack[top-3]].al==false && wi[stack[top-2]].al==true)

                {

                    while(top>=3 && wi[stack[top-3]].al==false && wi[stack[top-2]].al==true)

                    {

                        together(stack[top-3], stack[top-2], stack[top-1]);

                        top=top-2;

                    }

                }

            }

        }

        for(i=0; i<70; i++)

            for(j=0; j<70; j++)

                res[i][j]=' ';

        construct(0, 0, &wi[stack[0]]);

        printf("%dn", t);

        for(i=0; i<=wi[stack[0]].hig; i++)

        {

            for(j=0; j<=wi[stack[0]].wid; j++)

                printf("%c", res[i][j]);

            printf("n");

        }

    }

    return 0;

}
							

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

/* @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 n,m,times=1,map[]=new int[7];
  char bits[]=new char[129],s[]=new char[20];
  while(true){
    n=sc.nextInt();
    if(n==0)
    break;
    for(int i=0;i< n;i++){
    s=sc.next().toCharArray();
    map[s[1]-'1']=(char)i;
    }
    bits=sc.next().toCharArray();
    m=sc.nextInt();
    System.out.printf("S-Tree #%d:n",times++);
    while((m--)!=0){
    char tem[]=new char[20];
    int res=0;
    s=sc.next().toCharArray();;
    for(int i=0;i< n;i++)
      tem[map[i]]=(char)(s[i]-'0');
    for(int i=0;i< n;i++){
      res<<=1;
      if(tem[i]!=0)
        res++;
    }
    System.out.printf("%c",bits[res]);
     }
     System.out.println();
     System.out.println();
   }
  }
}
							

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

#include <iostream>
#include <memory>
#define MAX_N 75
#define MAX_T 150
using namespace std;

bool visited[MAX_N + 5][MAX_N + 5][2];
char input[MAX_N + 5][MAX_N + 5];
int w, h, cyNum, lCy = INT_MIN;
int startH, startW, startP;

bool inRange(int curH, int curW)
{
    return (curH >= 1 && curH <= h && curW >= 1 && curW <= w);
}

void dfs(int preH, int preW, int preP, int curH, int curW, char type, int which, int length)
{
    //cout<<curH<<" "<<curW<<" "<<which<<endl;
   
    visited[curH][curW][which] = true;
    if(type == '\')
    {
        if(which == 0)
        {
            if(inRange(curH, curW - 1))
            {
                //visited[curH][curW - 1][1] = true;
                if(input[curH][curW - 1] == '\')
                {
                    if(!visited[curH][curW - 1][1])
                        dfs(curH, curW, which, curH, curW - 1, '\', 1, length + 1);
                    if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH][curW - 1] == '/')
                {
                    if(!visited[curH][curW - 1][1])
                        dfs(curH, curW, which, curH, curW - 1, '/', 1, length + 1);
                    if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
            if(inRange(curH + 1, curW))
            {
                if(input[curH + 1][curW] == '\')
                {
                    if(!visited[curH + 1][curW][1])
                        dfs(curH, curW, which, curH + 1, curW, '\', 1, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 1) &&curH + 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH + 1][curW] == '/')
                {
                    if(!visited[curH + 1][curW][0])
                        dfs(curH, curW, which, curH + 1, curW, '/', 0, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 0) && curH + 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
        else if(which == 1)
        {
            if(inRange(curH, curW + 1))
            {
                //visited[curH][curW + 1][0] = true;
                if(input[curH][curW + 1] == '\' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '\', 0, length + 1);
                else if(input[curH][curW + 1] == '/' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '/', 0, length + 1);
                if(!(curH == preH && curW + 1 == preW && preP == 0) && curH == startH && curW + 1 == startW && startP == 0)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH - 1, curW))
            {
                if(input[curH - 1][curW] == '\')
                {
                    if(!visited[curH - 1][curW][0])
                        dfs(curH, curW, which, curH - 1, curW, '\', 0, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 0) && curH - 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH - 1][curW] == '/')
                {
                    if(!visited[curH - 1][curW][1])
                        dfs(curH, curW, which, curH - 1, curW, '/', 1, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 1) && curH - 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
    }
    else if(type == '/')
    {
        if(which == 0)
        {
            if(inRange(curH, curW - 1))
            {
                if(input[curH][curW - 1] == '\' && !visited[curH][curW - 1][1])
                    dfs(curH, curW, which, curH, curW - 1, '\', 1, length + 1);
                else if(input[curH][curW - 1] == '/' && !visited[curH][curW - 1][1])
                    dfs(curH, curW, which, curH, curW - 1, '/', 1, length + 1);
                if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH - 1, curW))
            {
                if(input[curH - 1][curW] == '\')
                {
                    if(!visited[curH - 1][curW][0])
                        dfs(curH, curW, which, curH - 1, curW, '\', 0, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 0) && curH - 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH - 1][curW] == '/')
                {
                    if(!visited[curH - 1][curW][1])
                        dfs(curH, curW, which, curH - 1, curW, '/', 1, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 1) && curH - 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
        else if(which == 1)
        {
            if(inRange(curH, curW + 1))
            {
                if(input[curH][curW + 1] == '\' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '\', 0, length + 1);
                else if(input[curH][curW + 1] == '/' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '/', 0, length + 1);
                if(!(curH == preH && curW + 1 == preW && preP == 0) && curH == startH && curW + 1 == startW && startP == 0)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH + 1, curW))
            {
                if(input[curH + 1][curW] == '\')
                {
                    if(!visited[curH + 1][curW][1])
                        dfs(curH, curW, which, curH + 1, curW, '\', 1, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 1) && curH + 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH + 1][curW] == '/')
                {
                    if(!visited[curH + 1][curW][0])
                        dfs(curH, curW, which, curH + 1, curW, '/', 0, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 0) && curH + 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
    }
}

int main()
{
    int i, j, seq = 0;
    while(cin>>w>>h && !(w == 0 && h == 0))
    {
        seq++;
        getchar();
        for(i = 1; i <= h; i++)
        {
            for(j = 1; j <= w; j++)
                input[i][j] = getchar();
            getchar();
        }
        memset(visited, 0, sizeof(visited));
        cyNum = 0;
        lCy = INT_MIN;
        for(i = 1; i <= h; i++)
        {
            for(j = 1; j <= w; j++)
            {
                for(int k = 0; k < 2; k++)
                {
                    if(i == 1 && j == 3 && k == 1)
                    {
                        int a = 2;
                    }
                    startH = i, startW = j, startP = k;
                    if(!visited[i][j][k])
                        dfs(-1, -1, -1, i, j, input[i][j], k, 1);
                }
            }
        }
        cout<<"Maze #"<<seq<<":"<<endl;
        if(cyNum != 0)
            cout<<cyNum<<" Cycles; the longest has length "<<lCy<<"."<<endl;
        else
            cout<<"There are no cycles."<<endl;
        cout<<endl;
    }
    return 0;
}
							

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

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

 public class Main {

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int s;
         String[] ss;
         String str;
         String[] num = new String[] { "1111110", "0000110", "1011011",
                 "1001111", "0100111", "1101101", "1111101", "1000110",
                 "1111111", "1101111" };
         char temp;
         StringBuilder buff;
         while (true) {
             ss = read.readLine().split(" ");
             s = Integer.parseInt(ss[0]);
             if (s == 0) {
                 break;
             }
             str = ss[1];
             for (int i = 0; i < 5; i++) {
                 buff = new StringBuilder();
                 if (i == 0 || i == 2 || i == 4) {
                     for (int j = 0; j < str.length(); j++) {
                         buff.append(' ');
                         if (i == 0) {
                             temp = num[str.charAt(j) - '0'].charAt(0);
                         } else if (i == 2) {
                             temp = num[str.charAt(j) - '0'].charAt(6);
                         } else {
                             temp = num[str.charAt(j) - '0'].charAt(3);
                         }
                         if (temp == '1') {
                             for (int k = 0; k < s; k++) {
                                 buff.append('-');
                             }
                         } else {
                             for (int k = 0; k < s; k++) {
                                 buff.append(' ');
                             }
                         }
                         buff.append(' ');
                         buff.append(' ');
                     }
                 } else {
                     for (int j = 0; j < str.length(); j++) {
                         if (i == 1) {
                             temp = num[str.charAt(j) - '0'].charAt(1);
                             if (temp == '1') {
                                 buff.append('|');
                             } else {
                                 buff.append(' ');
                             }
                             for (int k = 0; k < s; k++) {
                                 buff.append(' ');
                             }
                             temp = num[str.charAt(j) - '0'].charAt(5);
                             if (temp == '1') {
                                 buff.append('|');
                             } else {
                                 buff.append(' ');
                             }
                         } else {
                             temp = num[str.charAt(j) - '0'].charAt(2);
                             if (temp == '1') {
                                 buff.append('|');
                             } else {
                                 buff.append(' ');
                             }
                             for (int k = 0; k < s; k++) {
                                 buff.append(' ');
                             }
                             temp = num[str.charAt(j) - '0'].charAt(4);
                             if (temp == '1') {
                                 buff.append('|');
                             } else {
                                 buff.append(' ');
                             }
                         }
                         buff.append(' ');
                     }
                 }
                 if (i == 0 || i == 2 || i == 4) {
                     System.out.println(buff);
                 } else {
                     for (int k = 0; k < s; k++) {
                         System.out.println(buff);
                     }
                 }
             }
             System.out.println();
         }
     } 
}

							

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

#include <iostream>
#include <queue>
using namespace std;
 
const int MAXN = 80;
char cmap[MAXN][MAXN];
bool used[MAXN][MAXN];
short turn[MAXN][MAXN];        // [i,j]'s turn        direction
int vis[MAXN][MAXN];        // the number 
int w, h, res;
bool isSucceed;
struct node
{
    int x, y;
    int cnt;
};
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};                // the direction
 
bool isOk(int x, int y)                // boundary
{
    if (x < 0 || x > h || y < 0 || y > w)
        return false;
    return true;
}
 
void bfs(node beg, node end)        // bfs
{
    int i, j;
    queue <node> q;
    node p, t;
 
    for (i = 0; i <= h; ++i)        // init
    {
        for (j = 0; j <= w; ++j)
        {
            vis[i][j] = INT_MAX;
            used[i][j] = false;
        }
    }        // for
 
    used[beg.x][beg.y] = true;
    turn[beg.x][beg.y] = -1;
    vis[beg.x][beg.y] = 0;
 
    for (i = 0; i < 4; ++i)
    {
        p.x = beg.x + dir[i][0];
        p.y = beg.y + dir[i][1];
        p.cnt = 1;
 
        vis[p.x][p.y] = p.cnt;
        used[p.x][p.y] = true;
        turn[p.x][p.y] = i;
 
        q.push(p);
    }
 
    while (!q.empty())
    {
        p = q.front();
        q.pop();
 
        if (end.x == p.x && end.y == p.y)
        {
            res = vis[p.x][p.y];
            isSucceed = true;
            return;
        }
        if (cmap[p.x][p.y] == 'X')
            continue;
 
        for (i = 0; i < 4; ++i)
        {
            t.x = p.x + dir[i][0];
            t.y = p.y + dir[i][1];
 
            if (isOk(t.x, t.y) && !used[t.x][t.y])
            {
                if (turn[p.x][p.y] == i)        // same direction
                    t.cnt = vis[p.x][p.y];
                else t.cnt = vis[p.x][p.y] + 1;        // different direction
 
                if (t.cnt < vis[t.x][t.y])
                {
                    vis[t.x][t.y] = t.cnt;
                    used[t.x][t.y] = true;
                    turn[t.x][t.y] = i;
                    q.push(t);
                }
            }
        }        // for
    }        // while
    return;
}
 
int main()
{
    char ch;
    int i, j, iCount = 0, t;
    node beg, end;
 
    while (scanf("%d%d", &w, &h) != EOF && (w + h))
    {
        w++;        h++;
        memset(cmap, ' ', sizeof(cmap));
        for (i = 1; i < h; ++i)
        {
            getchar();
            for (j = 1; j < w; ++j)
            {
                scanf("%c", &cmap[i][j]);
            }
        }
        printf("Board #%d:n", ++iCount);
        t = 0;
        while (scanf("%d%d%d%d", &beg.y, &beg.x, &end.y, &end.x) != EOF)        // beg and end 
        {
            if (beg.x == 0 && beg.y == 0 && end.x == 0 && end.y == 0)
                break;
            res = 0;
            isSucceed = false;
            bfs(beg, end);
            if (isSucceed)
                printf("Pair %d: %d segments.n", ++t, res);
            else printf("Pair %d: impossible.n", ++t);
        }
        printf("n");
    }
    return 0;
}
							

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

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define NIL        (unsigned)-1
#define MAX        12
typedef vector <int> VI;
typedef unsigned int UI;

int cas, N, F;
int equ, tmp_num[MAX], UFS[MAX];
VI num, prio, pos, opr, v0, v1;
string expr;
stringstream ss;
char opr_sign[3] =
{ '+', '-', '*' };
int (*opr_f[3])(int a, int b);

int inline add(int a, int b)
{
    return a+b;
}
int inline sub(int a, int b)
{
    return a-b;
}
int inline mul(int a, int b)
{
    return a*b;
}
class Disjoint
{
public:
    int parent[12];
    Disjoint()
    {
        for (int i = 0; i < 12; parent[ i ] = i, i++)
            ;
    }
    int Find(int x)
    {
        if (parent[x] == x)
            return x;
        else
            parent[x] = Find(parent[x]);
        return parent[x];
    }
    void inline Union(int a, int b)
    {
        parent[Find(b)] = Find(a);
    }
};
int inline cast(string s)
{
    int tmp;
    ss.clear();
    ss << s;
    ss >> tmp;
    return tmp;
}
string fix(string s)
{
    int eq, sign;
    eq = s.find('=', 0);
    if (s[eq+1] != ' ')
        s.insert(s.begin()+eq+1, ' ');
    if (s[eq-1] != ' ')
        s.insert(s.begin()+eq, ' ');
    while ((sign = s.find(")(", 0)) != -1)
        s.insert(s.begin()+sign+1, ' ');
    while ((sign = s.find("( ", 0)) != -1)
        s.erase(sign+1, 1);
    while ((sign = s.find(" )", 0)) != -1)
        s.erase(sign, 1);
    s.insert(s.begin()+s.length(), ' ');
    for (UI i = s.find('=', 0); i < s.length(); i++)
    {
        if (s[ i ] == '(')
            if (s[i-1] != ' ' && s[i-1] != '(')
                s.insert(s.begin()+i, ' ');
        if (s[ i ] == ')')
            if (s[i+1] != ' ' && s[i+1] != ')')
                s.insert(s.begin()+i+1, ' '), i++;
    }
    s.erase(s.length()-1);
    for (UI i = 1; i < s.length(); i++)
        if (s[i-1] == ' ' && s[ i ] == ' ')
            s.erase(i, 1), i--;
    return s;
}
int expression(string s)
{
    string tmp;
    int blank, lastblank, p, pp;
    int lp, rp;
    Disjoint ufs;
    num.clear();
    prio.clear();
    pos.clear();
    opr.clear();
    v0.clear();
    v1.clear();
    lp = rp = 0;

    s = fix(s);
    blank = s.find(' ', 0);
    tmp = s.substr(0, blank);
    equ = cast(tmp);
    blank = s.find(' ', blank+1);
    expr = s = s.substr(blank+1, s.length()-blank-1);

    blank = -1;
    do
    {
        lastblank = s.find(' ', blank+1);
        tmp = s.substr(blank+1, (lastblank == -1 ? s.length() : lastblank)
                -blank);
        blank = lastblank;
        pos.push_back(blank);
        while (tmp.find('(', 0) != NIL)
            tmp.erase(0, 1);
        while (tmp.find(')', 0) != NIL)
            tmp.erase(tmp.length()-1, 1);
        num.push_back(cast(tmp));
    } while (blank != -1);

    for (UI i = 0, p = 0; i < s.length(); i++)
    {
        if (s[ i ] == '(')
            p++, lp++;
        else if (s[ i ] == ')')
            p--, rp++;
        else if (s[ i ] == ' ')
            prio.push_back(p);
    }

    while (p != -1)
    {
        p = -1, pp = 0;
        for (UI i = 0; i < prio.size(); i++)
            if (prio[ i ]> p)
                p = prio[ i ], pp = i;
        if (p == -1)
            break;
        for (UI i = pp; i < prio.size(); i++)
            if (prio[ i ] == p)
                v0.push_back(i), prio[ i ] = -1;
            else
                break;
    }
    for (UI i = 0; i < v0.size(); i++)
    {
        v1.push_back(ufs.Find(v0[ i ]));
        v1.push_back(ufs.Find(v0[ i ]+1));
        ufs.Union(v0[ i ], v0[ i ]+1);
    }
    for (UI i = 0; i < prio.size(); i++)
        opr.push_back(0);

    if (lp != rp)
        return 0;

    return num.size();
}

int check()
{
    int a, b;
    for (int i = 0; i < N; i++)
        tmp_num[ i ] = num[ i ];
    for (int i = 0; i < N - 1; i++)
    {
        a = v1[i*2], b = v1[i*2+1];
        tmp_num[a] = (*opr_f[opr[v0[ i ]]])(tmp_num[a], tmp_num[b]);
    }
    return tmp_num[0];
}
void print(string s)
{
    cout << equ <<'=';
    for (int i = 0; i < N - 1; i++)
        s[pos[ i ]] = opr_sign[opr[ i ]];
    cout << s << endl;
}
void dfs(int k)
{
    if (F)
        return;
    if (k == N - 1)
    {
        if (check() == equ)
            print(expr), F = 1;
        return;
    }
    for (int i = 0; i < 3; i++)
    {
        opr[k] = i;
        dfs(k+1);
    }
}

int main()
{
    opr_f[0] = add;
    opr_f[1] = sub;
    opr_f[2] = mul;
    cas = 1;
    while (getline(cin, expr) && expr != "0")
    {
        N = expression(expr);
        printf("Equation #%d:n", cas++);
        if (N == 1)
        {
            if (equ == num[0])
                print(expr);
            else
                cout << "Impossible" << endl;
        }
        else
        {
            F = 0;
            dfs(0);
            if (!F)
                cout << "Impossible" << endl;
        }
        cout << endl;
    }
    return 0;
}
							

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

#include<iostream>
#include"memory.h"
using namespace std;
char map[60][60][60];


long answer;

int n,m,h;

void find()
{int i,j,k,key;
answer=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{key=1;
 for(k=0;k<h;k++)if(map[k][i][j]==1&&key){answer++;key=0;}
         else if(map[k][i][j]==2)key=1;
 key=1;
 for(k=h-1;k>=0;k--)if(map[k][i][j]==1&&key){answer++;key=0;}
                else if(map[k][i][j]==2)key=1;
         
}

for(i=0;i<h;i++)
for(j=0;j<m;j++)
{key=1;
    
for(k=0;k<n;k++)if(map[i][j][k]==1&&key){answer++;key=0;}
        else if(map[i][j][k]==2)key=1;
key=1;        
for(k=n-1;k>=0;k--)if(map[i][j][k]==1&&key){answer++;key=0;}
                else if(map[i][j][k]==2)key=1;
        
}


for(i=0;i<h;i++)
for(j=0;j<n;j++)
{
key=1;    
 for(k=0;k<m;k++)if(map[i][k][j]==1&&key){answer++;key=0;}
         else if(map[i][k][j]==2)key=1;
key=1;
 for(k=m-1;k>=0;k--)if(map[i][k][j]==1&&key){answer++;key=0;}
                 else if(map[i][k][j]==2)key=1;
    
}

}  

void color(int a,int b,int c)
{map[a][b][c]=2;
if(a>0&&map[a-1][b][c]==0)color(a-1,b,c);
if(a<h-1&&map[a+1][b][c]==0)color(a+1,b,c);

if(b>0&&map[a][b-1][c]==0)color(a,b-1,c);
if(b<m-1&&map[a][b+1][c]==0)color(a,b+1,c);

if(c>0&&map[a][b][c-1]==0)color(a,b,c-1);
if(c<n-1&&map[a][b][c+1]==0)color(a,b,c+1);
}



void findface()
{int i,j,k;
for(i=0,j=0;j<m;j++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(i=h-1,j=0;j<m;j++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(j=0,i=0;i<h;i++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(j=m-1,i=0;i<h;i++)
for(k=0;k<n;k++)
if(map[i][j][k]==0)color(i,j,k);

for(k=0,i=0;i<h;i++)
for(j=0;j<m;j++)
if(map[i][j][k]==0)color(i,j,k);

for(k=n-1,i=0;i<h;i++)
for(j=0;j<m;j++)
if(map[i][j][k]==0)color(i,j,k);
}

int main()
{int l,i,s;
    while(1)
    {cin>>n>>m>>h>>l;
        if(n==0&&m==0&&h==0&&l==0)break;
        memset(map,0,60*60*60*sizeof(char));
        for(i=0;i<l;i++)
        {cin>>s;
            map[s/(n*m)][s%(n*m)/n][s%n]=1;
        }
    findface();
    find();
    cout<<"The number of faces needing shielding is "<<answer<<"."<<endl;
    }
return 0;
}    
            
							

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

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

public class Main {
    static final int N = 20+10;
    static int sum[] = new int[N],catana[] = new int[N];
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws Exception{
        int n;
        init();
        Scanner cin = new Scanner(System.in);
        while(true){
            n = cin.nextInt();
            if(n==0) break;
            solve(n);
            out.println();
            out.flush();
        }
    }
    static void solve(int n){
        int i,j,t;
        if(n==0) return ;
        if(n==1) {out.print("X");return;}
        for(j=1;;++j){
            if(sum[j]>=n) break;
        }
        n = n-sum[j-1];
        for(i=0;i< j;++i){
            t = catana[i]*catana[j-i-1];
            if(n>t) n = n-t;
            else break;
        }
        if(i!=0){
            out.print("(");
            solve(sum[i-1]+1+(n-1)/catana[j-i-1]);
            out.print(")");
        }
        out.print("X");
        if(i!=j-1){
            out.print("(");
            solve(sum[j-2-i]+1+(n-1)%catana[j-i-1]);
            out.print(")");
        }
    }
    static void init(){
        int i,j;
        catana[0] = catana[1] = 1;
        for(i=2;i< N;++i){
            catana[i] = 0;
            for(j=0;j< i;++j){
                catana[i] += catana[j]*catana[i-j-1];
            }
        }
        sum[0] = 0;
        sum[1] = 1;
        for(i=2;i< N;++i)
            sum[i] = sum[i-1]+catana[i];
    }
}

							

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

#include<iostream>
using namespace std;

const char space=' ';
char word[10001],l;
int len[10002],m,n;
int jie[10002];
int chen[10002];
long bad[10002];

void init()
{int h=0,j=1,t=0;
    
    while(cin.get())
    {if(cin.peek()==10)break;
    
    while(cin.peek()!=10)
    {if(cin.peek()==32){cin.get();if(t){len[j++]=t;t=0;}}
        else {cin.get(word[h++]);
            t++;}
    }
    if(t){len[j++]=t;t=0;}
    }
len[0]=0;
m=j-1;    
l=h;
//for(i=0;i<l;i++)cout<<word[i];
//cout<<endl;
//for(i=1;i<=m;i++)cout<<len[i]<<endl;
}

long point(long n,long p)
{long j=p/n,s=0;
while(p%n)
{s+=(j+1)*(j+1);
p-=j+1;n--;    
}
return s+(p/n)*(p/n)*n;
}


void doit()
{long s,p,j,i;
 jie[0]=0;bad[0]=0;
 jie[1]=1;bad[1]=500;
 chen[0]=0;chen[1]=1;    
 for(i=2;i<=m;i++)
 {bad[i]=500+bad[i-1];jie[i]=i;chen[i]=chen[i-1]+1; 
  s=len[i]+1+len[i-1];
 
  for(j=i-1;s<=n&&j>0;j--)
     {p=point(i-j,n-s)+bad[j-1];
     if(p<bad[i]||(p==bad[i]&&chen[j-1]<chen[jie[i]-1])){bad[i]=p;jie[i]=j;chen[i]=chen[j-1]+1;}
     
    if(j>1)s+=len[j-1]+1;
     }
 }
}
void print()
{int stack[10001],i,j,s,h;

for(i=m;i>0;i=jie[i]-1)
{s=0;
 for(j=i;j>=jie[i];j--)
 s+=len[j];s=n-s;

 for(j=jie[i];j<i;j++)
    {stack[j]=s/(i-j);s-=s/(i-j);}
 stack[i]=-1;
}
stack[0]=-1;
h=0;
for(i=1;i<=m;i++)
{for(j=0;j<len[i];j++)cout<<word[h++];
//if(stack[i]==-1&&stack[i-1]==-1){for(j=0;j<n-len[i];j++)cout<<space;cout<<endl;}
 if(stack[i]==-1)cout<<endl;
else for(j=0;j<stack[i];j++)cout<<space;
}
}

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

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

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

public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int[] yue=getYue(m);
        for (int i=0;i< yue.length ;i++ ){
            if (yue[i]==0){
                break;
            }
            m=m/yue[i];
        }
        BigInteger ok=(new BigInteger(""+m)).pow(n);
        BigInteger tmp=BigInteger.ONE;
        for (int i=0;i< yue.length ;i++ ){
            if (yue[i]==0){
                break;
            }
             tmp=tmp.multiply(((new BigInteger(""+yue[i])).pow(n)).subtract(BigInteger.ONE));
        }
        ok=ok.multiply(tmp);
        System.out.println(ok.toString());
    }

    public static int[] getYue(int n){
        int l=0;
        int[] yue=new int[16];
        if (n%2==0){
            yue[l]=2;
            l++;
        }
        for (int i=3;i<=n/2 ;i=i+2 ){
            if (n%i==0&&isZh(i)){
                yue[l]=i;
                l++;
            }
        }
        if (isZh(n)){
            yue[l]=n;
        }
        return yue;
    }

    public static boolean isZh(int n){
        for (int i=2;i<=(int)Math.pow(n,0.5) ;i++ ){
            if (n%i==0){
                return false;
            }
        }
        return true;
    }
}


							

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

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

public class Main {
 public static void main(String[] args){
 Scanner stdin=new Scanner(System.in);
 int n=stdin.nextInt();
 int[] a=new int[n],b=new int[n];
 for(int i=0;i< n;i++)a[i]=stdin.nextInt();
  b[0]=a[n-1];
  for(int i=1;i< n;i++){
    b[i]=b[i-1]^a[n-1-i];
  }
  BigInteger ans=new BigInteger("0"),two=new BigInteger("2");
 for(int i=0;i< n;i++){
   ans=ans.multiply(two);
   if(b[i]==1)
    ans=ans.add(BigInteger.ONE);
 }
  System.out.println(ans);
  }
}
							

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

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

public class Main{
  public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   int n;
   n = in.nextInt();
  Interval intervals[] = new Interval[n];
  for(int i = 0; i < n; i++){
    int x = in.nextInt();
    int y = in.nextInt();
    intervals[i] = new Interval(x, y);
   }
   qsort(intervals, 0, n-1);
   //Arrays.sort(intervals);
   //System.out.println(Arrays.toString(intervals));
   int st = intervals[0].s;
   int ed = intervals[0].e;
  for(int i = 0; i < n; i++){
    if(st >= intervals[i].s && st <= intervals[i].e){
         st = intervals[i].s;
    }
    if(ed >= intervals[i].s && ed <= intervals[i].e){
      ed = intervals[i].e;
    }
    else if(ed < intervals[i].s){
      System.out.println(st + " " + ed);
      st = intervals[i].s;
      ed = intervals[i].e;
    }
   }
   System.out.println(st + " " + ed);
 }

 public static void qsort(Interval arr[], int l0, int h0){
   int l = l0;
   int h = h0;
  Interval mid = arr[(l+h)/2];
        
  while(l<=h){
    while(l< h0 && arr[l].compareTo(mid) < 0)
    l++;
    while(h>l0 && arr[h].compareTo(mid) > 0)
    --h;
    if(l <= h){
    Interval temp = new Interval(arr[l].s, arr[l].e);
    arr[l].s = arr[h].s;
    arr[l].e = arr[h].e;
    arr[h].s = temp.s;
    arr[h].e = temp.e;
    l++;
    h--;
     }
    }
   if(l < h0)
    qsort(arr, l, h0);
        
   if(h > l0)
    qsort(arr, l0, h);
  }
}

class Interval implements Comparable<Interval>{
  int s;
  int e;
  public Interval(int s, int e){
    this.s = s;
    this.e = e;
  }

  public int compareTo(Interval rhs){
    if(s == rhs.s){
    return e - rhs.e;
    }
    else{
    return s - rhs.s;
     }
   }

   public String toString(){
    return s + " " + e;
  }
}
							

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

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

#define null 0
const int size=1000;
bool w[size][size];

void maxmatch(int n,int m,int *p)
{
    int p_n[size];
    int p_m[size];
    bool sign[size];
    int q[size],from[size],s,t;

    int i,j,link,now,h;
    

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

    for(i=0;i<n;i++)
    if(p_n[i]==-1)
    {
    
        for(j=0;j<m;j++)sign[j]=0;
                
        s=0;
        
        for(j=0;j<m;j++)
            if(w[i][j]!=null)
            {
                q[s]=j;
                from[s++]=-1;
                sign[j]=1;
            }

        for(t=0;t<s;t++)
        {
            now=q[t];
            if(p_m[now]==-1)
            {
                link=t;
                break;
            }
            else
            {
                for(j=0;j<m;j++)
                if(w[p_m[now]][j]!=null&&sign[j]==0)
                {
                    sign[j]=1;
                    q[s]=j;
                    from[s++]=t;
                }
            }
        }

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

    }

    for(i=0;i<n;i++)p[i]=p_n[i];
    
    return ;
}

int main()
{
    bool map[501][501];
    char name[501][30],w1[30],w2[30];
    char device[501][30];
    int n,m,e,i,j,a,b,k,an[510],tn;

    cin>>n;
    tn=n;

    for(i=0;i<n;i++)
        cin>>name[i];

    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>w1>>device[i];
        for(a=0;a<n;a++)
        if(strcmp(device[i],name[a])==0)break;

        if(a==n)strcpy(name[n++],device[i]);
    }

    cin>>e;

    for(i=0;i<501;i++)
    for(j=0;j<501;j++)
        if(i!=j)map[i][j]=0;
        else map[i][j]=1;


    for(i=0;i<e;i++)
    {
        cin>>w1;
        cin>>w2;

        for(a=0;a<n;a++)
        if(strcmp(w1,name[a])==0)break;
        
        if(a==n)strcpy(name[n++],w1);

        for(b=0;b<n;b++)
        if(strcmp(w2,name[b])==0)break;
        
        if(b==n)strcpy(name[n++],w2);

        //if(a<n&&b<n)
        map[a][b]=1;
    }
    

    
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        map[i][j]|=map[i][k]&&map[k][j];
    
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        w[i][j]=0;
        
    for(i=0;i<m;i++)
    {
        for(a=0;a<n;a++)
        if(strcmp(device[i],name[a])==0)break;

        for(j=0;j<tn;j++)w[i][j]=map[a][j];
    }

    maxmatch(m,tn,an);
    int answer;

    for(i=0,answer=0;i<m;i++)
        if(an[i]<0)answer++;
    
        cout<<answer<<endl;

    return 0;
}

    
							

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

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

 public class Main {

     public static void main(String[] args) throws NumberFormatException,
             IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int t = Integer.parseInt(read.readLine());
         int s;
         int[][] m;
         String[] str;
         int[] rooms = new int[200];
         int len;
         int start;
         int max;
         for (int i = 0; i < t; i++) {
             Arrays.fill(rooms, 0);
             s = Integer.parseInt(read.readLine());
             m = new int[s][2];
             for (int j = 0; j < s; j++) {
                 str = read.readLine().split(" ");
                 m[j][0] = Integer.parseInt(str[0]);
                 m[j][1] = Integer.parseInt(str[1]);
             }
             for (int j = 0; j < s; j++) {
                 if (m[j][0] % 2 == 1) {
                     m[j][0] = m[j][0] + 1;
                 }
                 if (m[j][1] % 2 == 1) {
                     m[j][1] = m[j][1] + 1;
                 }
                 len = Math.abs(m[j][0] - m[j][1]) / 2 + 1;
                 start = Math.min(m[j][0], m[j][1]) / 2 - 1;
                 for (int k = 0; k < len; k++) {
                     rooms[start + k]++;
                 }
             }
             max = rooms[0];
             for (int j = 1; j < 200; j++) {
                 if (rooms[j] > max) {
                     max = rooms[j];
                 }
             }
             System.out.println(max * 10);
         }
     } 
}

							

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

//* @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();
        while((a--)!=0)
        {
            in.nextInt();
            boolean bb=false;
            int m=in.nextInt();
            int d=in.nextInt();
            if((m+d)%2==0)bb=true;
            else if(m==9&&d==30)bb=true;
            else if(m==11&&d==30)bb=true;
            if(bb)System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

							

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

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

public class Main{
 public static int[][] chart;
 public static void main(String[] args){
  init();
  Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  int p=in.nextInt();
  for (int k=0;k< p ;k++ ){
   int m=in.nextInt();
   String a=in.next();
   int n=in.nextInt();
   String b=in.next();
   int[][] c=new int[m+1][n+1];
   for (int i=0;i<=m ;i++ ){
    for (int j=0;j<=n ;j++ ){
     if (i==0&&j==0){
      c[i][j]=0;
     }
     else if(i==0){
      c[i][j]=c[i][j-1]+getValue(b.charAt(j-1),'-');
     }
     else if (j==0){
      c[i][j]=c[i-1][j]+getValue(a.charAt(i-1),'-');
     }
     else{
      int x=getValue(a.charAt(i-1),'-');
      int y=getValue(b.charAt(j-1),'-');
      int z=getValue(a.charAt(i-1),b.charAt(j-1));
      c[i][j]=max(c[i-1][j]+x,c[i][j-1]+y,c[i-1][j-1]+z);
     }
    }
  }
   System.out.println(c[m][n]);
  }
}

    public static void init(){
        chart=new int[5][5];
        chart[0][0]=5;
        chart[0][1]=-1;
        chart[0][2]=-2;
        chart[0][3]=-1;
        chart[0][4]=-3;
        chart[1][0]=-1;
        chart[1][1]=5;
        chart[1][2]=-3;
        chart[1][3]=-2;
        chart[1][4]=-4;
        chart[2][0]=-2;
        chart[2][1]=-3;
        chart[2][2]=5;
        chart[2][3]=-2;
        chart[2][4]=-2;
        chart[3][0]=-1;
        chart[3][1]=-2;
        chart[3][2]=-2;
        chart[3][3]=5;
        chart[3][4]=-1;
        chart[4][0]=-3;
        chart[4][1]=-4;
        chart[4][2]=-2;
        chart[4][3]=-1;
    }

    public static int getValue(char a,char b){
        int ai=getIndex(a);
        int bi=getIndex(b);
        return chart[ai][bi];
    }

    public static int getIndex(char a){
        switch (a){
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            case '-':
                return 4;
            default :
                return -1;
        }
    }

    public static int max(int a,int b,int c){
        int m=0;
        if (a>=b){
            if (a>=c){
                m=a;
            }
            else{
                m=c;
            }
        }
        else{
            if (b>=c){
                m=b;
            }
            else{
                m=c;
            }
        }
        return m;
    }
}


							

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

import java.io.*;
 public class Main {
  public static int gcd(int a,int b){
   while(a%b!=0){
     int temp=a;
     a=b;
     b=temp%b;
   }
    return b;
}

public static void main(String[] args) throws IOException{
  StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   while(in.nextToken()!=StreamTokenizer.TT_EOF){
    int a,b;
    double last=100000;
    a=(int)in.nval;    
    in.nextToken();    
    b=(int)in.nval;    
    int devide=gcd(a,b);
     if(devide!=1) {
      a/=devide;
      b/=devide;
     }    
   for(int i=1;i< b;i++) {
     double up=(double)a/((double)b/(double)i);
     int tup1=(int)up;
     int tup2=tup1+1;
     int upf;
    if(Math.abs((double)tup1/i-(double)a/b)< Math.abs((double)tup2/i-(double)a/b))    
       upf=tup1;
    else upf=tup2;    
    if(Math.abs((double)upf/i-(double)a/b)< last){    
     last=Math.abs((double)upf/i-(double)a/b);    
     System.out.println(upf+"/"+i);    
     }
   }    
    System.out.println(a+"/"+b);
    System.out.println();    
    }

   }
}

							

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

#include<iostream>
using namespace std;

int t[100],n;


int go(int i,long s,long a,long b)
{if(s==1)return 1;
if(i==n)return 0;
if(a%t[i]==0)if(go(i+1,s/t[i],a/t[i],b))return 1;
if(b%t[i]==0)if(go(i+1,s/t[i],a,b/t[i]))return 1;
if(go(i+1,s,a,b))return 1;
return 0;
}





int main()
{int i;long a,b,s;
while(1)
{cin>>a;if(cin.fail())break;
 cin>>b;
 if(a<b){a=a+b;b=a-b;a=a-b;}
  s=a*b;n=0;
 for(i=100;i>1;i--)
  if(s%i==0&&(a%i==0||b%i==0))t[n++]=i;       
  
  if(!go(0,b,b,1)){cout<<a<<endl;continue;}
  if(!go(0,a,a,1)){cout<<b<<endl;continue;}
   if(go(0,s,a,b)==1)cout<<a<<endl;
 else cout<<b<<endl;

}


return 1;
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
    static int[][] arr;
    static boolean[] bb=new boolean[10000000];
    static Queue< my> qu=new LinkedList< my>();
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        arr=new int[5][5];
        String s;
        for(int i=1;i< 4;i++)
        {
            for(int j=1;j< 4;j++)
            {
                s=in.next();
                if(s.equals("x"))arr[i][j]=0;
                else arr[i][j]=Integer.parseInt(s);
            }
        }
        int u=getNum();
        bfs(u);
        
    }
    static void bfs(int t)
    {
            qu.add(new my("",t));
        while(!qu.isEmpty())
        {
            my h=qu.poll();
            int u=h.u;
            String s=h.s;
            if(u==123456780)
            {
                System.out.println(s);
                return;
            }
            if(bb[u%9999991])continue;
            bb[u%9999991]=true;
            int i=-1,j=-1,p=u;
            for(int u1=3;u1>0;u1--)
            {
                for(int u2=3;u2>0;u2--)
                {
                    arr[u1][u2]=p%10;
                    if(arr[u1][u2]==0)
                    {
                        i=u1;
                        j=u2;
                    }
                    p/=10;
                }
            }
            change(i,j,i-1,j);
            int y=getNum();
            qu.add(new my(s+"u",y));
            change(i-1,j,i,j);
            
            change(i,j,i+1,j);
            y=getNum();
            qu.add(new my(s+"d",y));
            change(i+1,j,i,j);
            
            change(i,j,i,j+1);
            y=getNum();
            qu.add(new my(s+"r",y));
            change(i,j+1,i,j);
            
            change(i,j,i,j-1);
            y=getNum();
            qu.add(new my(s+"l",y));
            change(i,j-1,i,j);
        }
        System.out.println("unsolvable");
    }
    static int getNum()
    {
        int t=0;
        for(int i=1;i< 4;i++)
            for(int j=1;j< 4;j++)
            {
                t*=10;
                t+=arr[i][j];
            }
        return t;
    }
    static void change(int x1,int y1,int x2,int y2)
    {
        arr[x1][y1]=arr[x2][y2];
        arr[x2][y2]=0;
    }
}
class my
{
    String s="";
    int u;
    public my(String t,int a)
    {
        u=a;
        s=t;
    }
}

							

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

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


//#define DEBUG
//#define PRINT_TREE 


#ifdef DEBUG
#include <time.h>
#endif

using namespace std;

const char NONE = 30;
const char WORD = 50;

struct node
{
    node(){ p=0; m=''; for(int i=0;i<27;i++)id[i]=NONE; }
        
    char id[27];
    int *p;
    char m;
}mem[150000];

node a_word,root;
int use_node=0;

int new_node()
{
    return use_node++;
}

void insert( node *pnd, char c )
{

    int *q = new int[ pnd->m + 1];
    
    copy( pnd->p, (pnd->p)+(pnd->m), q );
        
    q[pnd->m] = new_node();
        
    pnd->id[c-'A'] = pnd->m;
    pnd->m++;

    delete pnd->p;
    pnd->p = q;

    return ;
}

inline void set_word( node *pnd )
{
    pnd->id[27] = WORD;
}

inline node *get_child( node *pnd,char c)
{
    int s;
    if( (s=pnd->id[c-'A']) == NONE )return 0;
    else return &mem[ pnd->p[s] ];
}

inline bool is_word( node *pnd)
{
    return pnd->id[27] == WORD;
}

void creat(node *p,char *word)
{
    if( *word == '')
    {
        set_word( p );
    }
    else
    {
        node *q=get_child(p,*word);
    
        if( !q )
        {
            insert(p,*word);
            q=get_child(p,*word);
        }
    
        creat( q,word+1 );
    }
}

char *word[2000];
int n;


bool cmp( char *a, char *b )
{
    return *a > *b || ( *a == *b ) && strcmp(a,b) < 0;
}


char s[100];

void print( node *p, int k )
{
    if( !p ) return;
    
    if( is_word(p) )
    {
        s[k] ='';
        printf(":%sn",s);
    }
    
    char a;
    for( a='A'; a<='Z'; a++ )
    {
        s[k]=a;
        print(get_child( p, a ), k+1 );
    }
}

char table[26];
char ans[26];
bool used[26];
int answer;



void init()
{
    char w[100], l, c;

    n=0;

    while( ( c = getchar() )=='n' )
        ;
    ungetc( c, stdin );

    while(1)
    {
        if(scanf( "%s", w )!=1)break;
        
        if( w[0] == '' ) break;
        
        l = strlen( w );

        word[n] = new char[l+2];
        word[n][0] = l;
        strcpy( word[n]+1, w );
         
        n++;
        while( ( c = getchar() )==' ' )
            ;
        if( c=='n')
        {
            c=getchar();
            if(c=='n')break;
            else ungetc(c,stdin);
        }
        else
        {
            ungetc(c,stdin);
        }
        if(n>1500)
        {
            n=n;
        }
    }
    
    sort(word, word+n, cmp);
    n=std::unique_copy(word, word+n,word )-word;

    int i;
    for( i=0;i<26;i++)
    {
        table[i]='*';
        used[i] = false;
    }
    answer=0;

#ifdef DEBUG
    printf("%d wordsn",n);
#endif
}

char *d_word[50010];




void creat_dictionary()
{
    int i ,l, m;
    char w[100];
    scanf( "%d", &m );

    for( i=0; i<m; i++ )
    {
        scanf( "%s", w );
    
        l = strlen( w );
        d_word[i] = new    char[l+2];
        
        d_word[i][0] = l;
        strcpy( d_word[i]+1, w );

        creat( &root, w );
    }

}

inline int certain(char *s)
{
    int i,j;
    for(i=1,j=0; s[i]; i++)
        if(table[s[i]-'A']!='*')
            j++;
    return j;
}

int cmp2(char *a,char *b)
{
    return certain(a)>certain(b);
}


bool find( int wn, int cn, node *p )
{

    if( wn>=n ) 
    {
        answer++;
        copy(table,table+26,ans);

        return answer>1;
    }
    
    if( !p )return false;

    if( cn == word[wn][0] )
    {
        if( is_word(p) )
        {
            sort( word+wn+1,word+n,cmp2 );

            if( find( wn+1, 0, &root ) ) return true;
        }
    }
    else
    {
        char c = word[wn][cn+1], d;
        
        if( table[c-'A'] == '*' )
        {
            for( d='A'; d<='Z'; d++ )
            if(!used[d-'A'])
            {
                table[c-'A'] = d;
                
                used[d-'A'] = true;
                if( find( wn, cn+1, get_child(p,d) ) ) return true;
                used[d-'A'] = false;
            }
            table[c-'A'] = '*';
        }
        else    if( find( wn, cn+1, get_child(p, table[c-'A']) ) ) return true;
    }

    return false;
}        

int main()
{
    int cas;
#ifdef DEBUG
    freopen("E.in","r",stdin);
    long t=clock();
#endif

    creat_dictionary();


#ifdef PRINT_TREE    
    print(&root,0);
#endif

#ifdef DEBUG
    printf( "%dmsn", clock()-t );
#endif
    
    scanf("%d",&cas);
    
    while( cas-- )
    {
        init();
        if( find( 0, 0, &root ) )
            printf( "#More than one solution#n" );
        else
        {
            if( answer == 0 )
                printf( "#No solution#n" );
            else 
            {
                char out[26];
                int i;

                for( i=0; i<26; i++ )
                    out[i]='*';
                
                for(i=0; i<26; i++ )
                if(ans[i-'A']!='*')
                {
                    out[ans[i]-'A']=i+'A';
                }

                for( i=0; i<26; i++ )
                    printf( "%c", out[i] );
                printf( "n" );
            }
        }
    }

    return 0;
}



							

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

 import java.util.Scanner;

 public class Main {

     int t;
     int len;
     int[] p;
     int[] w;
     String[] s;
     int index;
     int temp;
     int pos;

     public Main() {
         Scanner scan = new Scanner(System.in);
         t = scan.nextInt();
         for (int i = 0; i < t; i++) {
             len = scan.nextInt();
             p = new int[len];
             w = new int[len];
             s = new String[len * 2];
             for (int j = 0; j < len; j++) {
                 p[j] = scan.nextInt();
             }
             pos = 0;
             temp = 0;
             index = 0;
             for (int k = 0; k < len; k++) {
                 for (; pos < p[k]; pos++) {
                     s[index++] = "(";
                 }
                 s[index++] = ")";
             }
             search();
             for (int m = 0; m < len; m++) {
                 System.out.print(w[m] + " ");
             }
             System.out.println();
         }
     }

     public void search() {
         pos = 0;
         int k = 0;
         for (int i = 0; i < len; i++) {
             for (; k < 2 * len; k++) {
                 if (s[k].equals(")")) {
                     pos = k;
                     k++;
                     break;
                 }
             }
             temp = 0;
             index = 1;
             for (int j = pos - 1;; j--) {
                 if (s[j].equals("(")) {
                     temp++;
                     index--;
                 } else {
                     index++;
                 }
                 if (index == 0) {
                     w[i] = temp;
                     break;
                 }
             }
         }
     }

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

							

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

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
int main()
{
     int ax,bx,temp;
     int k,wantedax;
     while(scanf("%d%d",&ax,&bx)!=EOF) /*题中没有输入结标志时，必须这样写，否则会WA*/
     {
            if(ax>bx)
                swap(ax,bx);
            k = bx - ax;
            wantedax = (floor)( k*(1.0+sqrt(5.0))/2.0 );
            if(ax==wantedax)
                printf("%dn",0);
            else
                printf("%dn",1);
    }
    return 0;
}
							

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 35
int N;
using namespace std;
typedef struct Point
{
    double x,y;
    Point() {}
    Point(double tx,double ty):x(tx),y(ty) {}
}Vector;

int WallY0[MAX]; //��ַ����ݸ���
int WallY100[MAX];
int WallX0[MAX];
int WallX100[MAX];
struct Line
{
    Point A,B;

    Line()  {}
    Line(Point &tA,Point &tB):A(tA),B(tB)
    {
        if (A.x > B.x)
        {
            Point t = A;
            A = B;
            B = t;
        }
    }
};

Line T[MAX];
Point S;

double muli(Vector A,Vector B)
{
    return A.x * B.y - A.y * B.x;
}

Vector GetVector(Point A,Point B)
{
    Vector t;
    t.x = B.x - A.x;
    t.y = B.y - A.y;
    return t;
}

bool IsCross(Line L1,Line L2)
{
    Vector A = GetVector(L1.A,L1.B);
    Vector A1 = GetVector(L1.A,L2.A);
    Vector A2 = GetVector(L1.A,L2.B);

    Vector B = GetVector(L2.A,L2.B);
    Vector B1 = GetVector(L2.A,L1.A);
    Vector B2 = GetVector(L2.A,L1.B);

    double Ans_A1 = muli(A,A1);
    double Ans_A2 = muli(A,A2);
    if ((Ans_A1 > 0 && Ans_A2 > 0) || (Ans_A1 < 0 && Ans_A2 < 0))
        return false;
    if (Ans_A1 == 0 && Ans_A2 == 0)
    {
        Line t1 = L1.A.x < L2.A.x ? L1 : L2;
        Line t2 = L1.A.x < L2.A.x ? L2 : L1;
        if (t2.A.x > t1.B.x)
            return false;
    }

    double Ans_B1 = muli(B,B1);
    double Ans_B2 = muli(B,B2);
    if ((Ans_B1 > 0 && Ans_B2 > 0) || (Ans_B1 < 0 && Ans_B2 < 0))
        return false;
    if (Ans_B1 == 0 && Ans_B2 == 0)
    {
        Line t1 = L1.A.x < L2.A.x ? L1 : L2;
        Line t2 = L1.A.x < L2.A.x ? L2 : L1;
        if (t2.A.x > t1.B.x)
            return false;
    }
    return true;
}

void PreProcess()
{
    WallX0[0] = 1;
    WallX0[1] = 0;
    WallX100[0] = 1;
    WallX100[1] = 0;
    WallY0[0] = 1;
    WallY0[1] = 0;
    WallY100[0] = 1;
    WallY100[1] = 0;
    for (int i = 0;i < N;i++)
    {
        if (T[i].A.x == 0)
            WallX0[++WallX0[0]] = T[i].A.y;
        if (T[i].B.x == 0)
            WallX0[++WallX0[0]] = T[i].B.y;
        if (T[i].A.x == 100)
            WallX100[++WallX100[0]] = T[i].A.y;
        if (T[i].B.x == 100)
            WallX100[++WallX100[0]] = T[i].B.y;
        if (T[i].A.y == 0)
            WallY0[++WallY0[0]] = T[i].A.x;
        if (T[i].B.y == 0)
            WallY0[++WallY0[0]] = T[i].B.x;
        if (T[i].A.y == 100)
            WallY100[++WallY100[0]] = T[i].A.x;
        if (T[i].B.y == 100)
            WallY100[++WallY100[0]] = T[i].B.x;
    }

    sort(WallX0 + 1,WallX0 + WallX0[0] + 1);
    sort(WallX100 + 1,WallX100 + WallX100[0] + 1);
    sort(WallY0 + 1,WallY0 + WallY0[0] + 1);
    sort(WallY100 + 1,WallY100 + WallY100[0] + 1);

    if(WallX0[WallX0[0]] != 100)
        WallX0[++WallX0[0]] = 100;
    if(WallX100[WallX100[0]] != 100)
        WallX100[++WallX100[0]] = 100;
    if(WallY0[WallY0[0]] != 100)
        WallY0[++WallY0[0]] = 100;
    if(WallY100[WallY100[0]] != 100)
        WallY100[++WallY100[0]] = 100;
    // for(int i = 1;i < WallY0[0];i++)
    //{
    //     cout<<WallY0[i]<<endl;
    //}
}

void Answer()
{
    PreProcess();
    int Count = 0x7FFFFFFF;
    int i = 1;
    while(WallX0[i] == 0) i++;
    for (;i <= WallX0[0];i++)
    {
        double mid = (WallX0[i] + WallX0[i - 1]) / 2.0;
        Line l;
        l.A = S;
        l.B = Point(0,mid);

        int c = 0;
        for (int j = 0;j < N;j++)
        {
            if (IsCross(T[j],l))
            {
                c++;
                //cout<<WallX0[i - 1]<<' '<<WallX0[i]<<" Cross "<<T[j].A.x<<' '<<T[j].A.y<<' '<<T[j].B.x<<' '<<T[j].B.y<<endl;
            }
        }
        if (c < Count)
        {
            Count = c;
            //cout<<0<<' '<<WallX0[i]<<endl;
        }
    }
    i = 1;
    while(WallX100[i] == 0) i++;
    for (;i <= WallX100[0];i++)
    {
        double mid = (WallX100[i] + WallX100[i - 1]) / 2.0;
        Line l;
        l.A = S;
        l.B = Point(100,mid);

        int c = 0;
        for (int j = 0;j < N;j++)
        {
            if (IsCross(T[j],l))
            {
                c++;
                //cout<<WallX100[i -1]<<' '<<WallX100[i]<<" Cross "<<T[j].A.x<<' '<<T[j].A.y<<' '<<T[j].B.x<<' '<<T[j].B.y<<endl;
            }
        }
        if (c < Count)
         {
             Count = c;
             //cout<<100<<' '<<WallX100[i]<<endl;
         }
    }

    i = 1;
    while(WallY0[i] == 0) i++;
    for (;i <= WallY0[0];i++)
    {
        double mid = (WallY0[i] + WallY0[i - 1]) / 2.0;
        Line l;
        l.A = S;
        l.B = Point(mid,0);

        int c = 0;
        for (int j = 0;j < N;j++)
        {
            if (IsCross(T[j],l))
            {
                c++;
                //cout<<WallY0[i - 1]<<' '<<WallY0[i]<<" Cross "<<T[j].A.x<<' '<<T[j].A.y<<' '<<T[j].B.x<<' '<<T[j].B.y<<endl;
            }
        }
        if (c < Count)
        {
            Count = c;
            //cout<<WallY0[i]<<' '<<0<<endl;
        }
    }

    i = 1;
    while(WallY100[i] == 0) i++;
    for (;i <= WallY100[0];i++)
    {
        double mid = (WallY100[i] + WallY100[i - 1]) / 2.0;
        Line l;
        l.A = S;
        l.B = Point(mid,100);

        int c = 0;
        for (int j = 0;j < N;j++)
        {
            if (IsCross(T[j],l))
            {
                c++;
                //cout<<WallY100[i-1]<<' '<<WallY100[i]<<" Cross "<<T[j].A.x<<' '<<T[j].A.y<<' '<<T[j].B.x<<' '<<T[j].B.y<<endl;
            }
        }
        if (c < Count)
        {
            Count = c;
            //cout<<WallY100[i]<<' '<<100<<endl;
        }
    }
    cout<<"Number of doors = "<<Count+1<<endl;
}

int main()
{
    while (cin>>N)
    {
        for (int i = 0;i < N;i++)
        {
            scanf("%lf%lf%lf%lf",&T[i].A.x,&T[i].A.y,&T[i].B.x,&T[i].B.y);
        }
        scanf("%lf%lf",&S.x,&S.y);
        Answer();
    }
    return 0;
}


/*
Archeologists from the Antiquities and Curios Museum (ACM) have flown to Egypt to examine the great pyramid of Key-Ops. Using state-of-the-art technology they are able to determine that the lower floor of the pyramid is constructed from a series of straightline walls, which intersect to form numerous enclosed chambers. Currently, no doors exist to allow access to any chamber. This state-of-the-art technology has also pinpointed the location of the treasure room. What these dedicated (and greedy) archeologists want to do is blast doors through the walls to get to the treasure room. However, to minimize the damage to the artwork in the intervening chambers (and stay under their government grant for dynamite) they want to blast through the minimum number of doors. For structural integrity purposes, doors should only be blasted at the midpoint of the wall of the room being entered. You are to write a program which determines this minimum number of doors. 
Input

The input will consist of one case. The first line will be an integer n (0 <= n <= 30) specifying number of interior walls, followed by n lines containing integer endpoints of each wall x1 y1 x2 y2 . The 4 enclosing walls of the pyramid have fixed endpoints at (0,0); (0,100); (100,100) and (100,0) and are not included in the list of walls. The interior walls always span from one exterior wall to another exterior wall and are arranged such that no more than two walls intersect at any point. You may assume that no two given walls coincide. After the listing of the interior walls there will be one final line containing the floating point coordinates of the treasure in the treasure room (guaranteed not to lie on a wall). 
Output

Print a single line listing the minimum number of doors which need to be created, in the format shown below. 
Sample Input

7 
20 0 37 100 
40 0 76 100 
85 0 0 75 
100 90 0 90 
0 71 100 61 
0 14 100 38 
100 47 47 100 
54.5 55.4 
Sample Output

Number of doors = 2
*/

							

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

import java.util.*;   
    
public class Main{   
    public static void main(String[] args){   
        int l[]=new int[10000];   
        int w[]=new int[10000];   
        int tt[]=new int[5000];   
        int k=0;   
        Scanner keyin=new Scanner(System.in);   
        int m=keyin.nextInt();   
        int mm=m;   
        int n=0;   
        for(;m>0;m--){   
            n=keyin.nextInt();   
            for(int j=0;j< n;j++){   
                l[j]=keyin.nextInt();   
                w[j]=keyin.nextInt();   
            }   
  
            int time=0,c=0;   
            for(int t=0;t<=n-2;t++){   
                for(int s=n-2;s>=t;s--){   
                    if(l[s]>l[s+1]){   
                        int temp=l[s];   
                        l[s]=l[s+1];   
                        l[s+1]=temp;   
                        temp=w[s];   
                        w[s]=w[s+1];   
                        w[s+1]=temp;   
                    }   
                }   
            }   
  
            for(int p=0;p< n;p++){   
                if(w[p]!=-1){   
                    time++;   
                    c=w[p];   
                    for(int q=p+1;q< n;q++){   
                        if(w[q]>=c){   
                            c=w[q];   
                            w[q]=-1;   
                        }   
                    }   
                }   
            }   
            tt[k++]=time;   
        }   
        for(int r=0;r< mm;r++)   
            System.out.println(tt[r]);   
    }   
}  

							

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

#include <iostream>
#include <cstdio>
using namespace std;
int N,K;
long long len[10001];
int main()
{
    while(cin>>N>>K)
    {
        double t;
        long long sum = 0;
        for(int i = 0;i < N;i++)
        {
            cin>>t;
            t *= 100;
            len[i] = (long long)t;
            sum += len[i];
        }

        long long head = 0;
        long long tail = sum;
        long long mid;
        while(head < tail)
        {
            mid = (head + tail) / 2;
            if(mid == head)
                break;
            int sum = 0;
            for(int i = 0;i < N;i++)
            {
                sum += len[i] / mid;
            }
            if(sum < K)
            {
                tail = mid;
            }
            else
            {
                head = mid;
            }
        }
        if(!mid)
            cout<<"0.00"<<endl;
        else
            printf("%.2fn",mid / 100.0);
    }
    return 0;
}
/*
Cable master
Time Limit: 1000MS        Memory Limit: 10000K
Total Submissions: 7737        Accepted: 1580
Description

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input

The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.
Output

Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).
Sample Input

4 11
8.02
7.43
4.57
5.39
Sample Output

2.00
Source

Northeastern Europe 2001
*/

							

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

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

 public static void main(String args[])
{
  int cas, i, n, j, s1, s2;
  int a[]=new int[30];
  Scanner sc=new Scanner(System.in);
  cas=sc.nextInt();
    
  while((cas--)!=0 )
  {
   n=sc.nextInt();
        
   for( i=0; i< n; i++ )
   {
      a[i]=sc.nextInt();
   }

   for( i=0; i< n; i++ )
    if( a[i] == 1 )
    {
    s1 = s2 = 0;
    for( j=1; j< n; j++ )
    if( a[(j+i)%n] == 1 )
    {
       if( j%2!=0 ) s1++;
       else s2++;
    }
    if( s1 == s2 || s1 == s2+1 )
    {
       System.out.printf( "YESn" );
       break;
    }
      }
        
     if( i >= n )
    System.out.printf( "NOn" );
   }
  }
}
							

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

//���ձ��˵�˼���õ�,֮ǰ���Ǻ��˽�dijkstra������������Щ��� 
//1,����ǰδ�������·�ķ��Ҫ��ľ�����̽���������·; 
//2,�������뵱ǰ����Ľ���й�j����δ���������·�Ľ����̾�����и��¡� 
//ͼ������һ������С�����ĵľ����㷨Prim�㷨��Dij��̼������ƣ�����̰��˼�롣 
//ֻ��һ���ǶԶ����ѡ������һ���ǶԱߵ�ѡ�� 

import java.util.*; 
public class Main 
{ public static int[][] e; 
   public static int[]  dis; 
   public static int[] used; 
   public static int[] level; 
   public static int n,m; 
   public static void main(String[] args){ 
    Scanner cin = new Scanner(System.in); 
    int  x,t; 
    e = new int[101][101]; 
    dis = new int[101]; 
    used =  new int[101]; 
    level = new int[101]; 
          m=cin.nextInt(); 
          n=cin.nextInt(); 
           for(int i=1;i<=n;i++) 
             {   e[0][i]=cin.nextInt(); 
                 level[i]=cin.nextInt(); 
                  x=cin.nextInt(); 
                for(int j=0;j< x;j++) 
                { t=cin.nextInt(); 
                  e[t][i]=cin.nextInt(); 
                } 
             } 
           solve(); 
} 

public static void solve() 
{ int max,result; 
  result=e[0][1]; 
  for(int i=1;i<=n;i++) 
     { max=level[i]; 
       for(int j=1;j<=n;j++) 
        if(level[j]>max || level[j]< max-m)//�ж����׵��˵ĵȼ��Ƿ�����Ŀ�������� 
         used[j]=1;//����� 
        else 
         used[j]=0; //��� 
       dijkstra(); 
       if(result>dis[1]) //�Ƚ�ÿ������ķ��� 
         result=dis[1]; 
} 
System.out.println(result); 
} 
public static void dijkstra() 
{ int min,temp,k; 
  for(int i=1;i<=n;i++) 
   dis[i]=e[0][i]; 
  for(int i=1;i<=n;i++) 
     { min=0x7FFFFFFF; 
       k=0; 
       for(int j=1;j<=n;j++)//�ҳ�����С�ı� 
         if(used[j]==0 && dis[j]< min) 
          {min=dis[j]; 
              k=j; 
          } 
       if(k==0) 
        break; 
       used[k]=1; 
       for(int j=1;j<=n;j++)//������ڵ��ֵ 
        if(used[j]==0 && e[k][j]>0 && min+e[k][j]< dis[j]) 
         dis[j]=min+e[k][j]; 
    } 
   } 
} 
 

							

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


import java.util.Scanner; 

public class Main { 

    static long x0, y0; 

    public static void main(String[] args) { 
        Scanner scan = new Scanner(System.in); 
        long x = scan.nextInt(); 
        long y = scan.nextInt(); 
        long m = scan.nextInt(); 
        long n = scan.nextInt(); 
        long L = scan.nextInt(); 
        x = x % L; 
        y = y % L; 
        if (x > y) { 
            long t = y; 
            y = x; 
            x = t; 
            t = n; 
            n = m; 
            m = t; 
        } 
        long a = Math.abs(m - n); 
        long b = -L; 
        long c; 
        if (m > n) { 
            c = y - x; 
        } else {         
            c = x - y + L; 
        } 

       

        long d = gcd(a , b); 
        if(c%d!=0){ 
            System.out.println("Impossible"); 
        }else{ 
            long add1 = x0*c/d ; 
            long add2 = Math.abs(b/d); 
            while( add1 <0 ){ 
                add1 += add2; 
            } 
            while(add1 - add2 >= 0){ 
               add1 -= add2; 
            } 
            System.out.println(add1); 
        } 
    } 

  
    public static long gcd(long a, long b) { 
        long t, d; 
        if (b == 0) { 
            x0 = 1; 
            y0 = 0; 
            return a; 
        } 
        d = gcd(b, a % b); 
        t = x0; 
        x0 = y0; 
        y0 = t - a / b * y0; 
        return d; 
    } 
  
  } 

							

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

//* @author:
import java.util.*;
public class Main{
  String result[][];
  char c[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P'};

  boolean used[];

  public Main(String result[][]){
   this.result=result;
  
  }

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

    while(true){
     String result[][]=new String[5][4];
    
    for(int i=0;i< 5;i++)
     for(int j=0;j< 4;j++){
        if(i>=3)
          result[i][j]="";
        else
          result[i][j]=sc.next();
     }
    
     Main m=new Main(result);
     
     int r=0;
     for(int x=3;x<=4;x++){
       if(!m.doIt(x)){ r+=1; break;}
     }
     if(r==0) m.show();
    }
  }
 
  private void show(){
    for(int i=0;i< 5;i++){
     for(int j=0;j< 4;j++){
        System.out.print(result[i][j]+" ");
     }
     System.out.println();
    }
    System.out.println();
   }

   
   private boolean ch(String s1,String s2){
     int x=0;
     for(int i=0;i< s1.length();i++)
        for(int j=0;j< s2.length();j++){
          if(s1.charAt(i)==s2.charAt(j)) x++;
          if(x>=2) return true;
        }
     return false;
  }

   private boolean check(StringBuffer temp){
      String s=temp.toString();
       for(int i=0;i< 5;i++)
        for(int j=0;j< 4;j++){
          if(result[i][j]!=null&&ch(result[i][j],s))
              return false;
        }
       return true;
    }
          
    public boolean doIt(int x){
      used=new boolean[16];
      int sum=0;
      int y=0;
         
    for(int i=0;i< 16;i++)
     for(int j=i+1;j< 16;j++)
       for(int k=j+1;k< 16;k++)
         for(int l=k+1;l< 16;l++){
            if(!used[i]&&!used[j]&&!used[k]&&!used[l]){
                StringBuffer s=new StringBuffer("");
                s.append(c[i]).append(c[j]).append(c[k]).append(c[l]);
                if(check(s)){
                    used[i]=true;used[j]=true;used[k]=true;used[l]=true;
                    result[x][y]=s.toString();

                     y=y+1;
                     sum=sum+1;
                }
             }
           }
        if(sum< 4){
            System.out.println("It is not possible to complete this schedule.");
            System.out.println();
            return false;
         }
        return true;
    }
      
}
							

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

/* @author:����acmilan_fan@yahoo.cn */
import java.io.*;
public class Main {
  public static void main(String[] args) throws Exception{
//System.setIn(new FileInputStream(new File("E:\in.txt")));
//System.setOut(new PrintStream(new File("E:\out.txt")));
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String s;
  Node root=new Node("ROOT",null);
  Node curr=root;
  Node t,n;
  int count=1;
  tag:
  while(true){
    switch((s=br.readLine()).charAt(0)){
       case 'f':
         t=new Node(s,curr);
      if(curr.fleftmost==null)
          curr.fleftmost=t;
      else{
         if(t.compareTo(curr.fleftmost)< 0){
             t.frightsib=curr.fleftmost;
             curr.fleftmost=t;
         }else{
        n=curr.fleftmost;
        while(n.frightsib!=null&&t.compareTo(n.frightsib)>0){
           n=n.frightsib;
        }
        t.frightsib=n.frightsib;
        n.frightsib=t;
         }
     }
     break;
      case 'd':
      t=new Node(s,curr);
      if(curr.dleftmost==null)
        curr.dleftmost=curr.drightmost=t;
      else{
        curr.drightmost.drightsib=t;
        curr.drightmost=t;
       }
       curr=curr.drightmost;
       break;
    case ']':
       curr=curr.parent;
       break;
    case '*':
        print(root,count++);
        curr=root=new Node("ROOT",null);
        break;
    case '#':
        break tag;
     }
   }
  }

 static void print(Node root,int count) {
   System.out.println("DATA SET "+count+":");
   print0(root,0);
   System.out.println();
 }

static void print0(Node root, int d) {
   for(int i=0;i< d;i++){
    System.out.print("|     ");
    }
    System.out.println(root.content);
    Node t=root.dleftmost;
    while(t!=null){
        print0(t,d+1);
        t=t.drightsib;
    }
    t=root.fleftmost;
    while(t!=null){
        print0(t,d);
        t=t.frightsib;
    }
  }
}
class Node implements Comparable< Node>{
    String content;
    Node parent;
    Node fleftmost;
    Node frightsib;
    Node dleftmost;
    Node drightsib;
    Node drightmost;
    Node(String c,Node n){
        content=c;
        parent=n;
    }
    @Override
    public int compareTo(Node o) {
        return this.content.compareTo(o.content);
    }
}

							

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

//* @author 洪晓鹏<hongxp11@163.com>

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

/**
 * @param args
 */
 public static boolean isPrefix(String a, String b) {
    int len = a.length() > b.length() ? b.length() : a.length();
    if (a.substring(0, len).equals(b.substring(0, len)))
      return true;
    else
        return false;
 }

public static void main(String[] args) {
  ArrayList< String> array = new ArrayList< String>();
  Scanner in = new Scanner(System.in);
  int num = 1;
  boolean skip = false;
  while (in.hasNext()) {
    String temp = in.next();
    if (temp.equals("9")) {
     int len = array.size();
     for (int i = 0; i < len - 1; i++) {
      for (int j = i + 1; j < len; j++) {
        if (isPrefix(array.get(i), array.get(j))) {
         skip = true;
        }
       }
    }
    if (!skip) {
     System.out.println("Set " + num+ " is immediately decodable");
    } else {
     System.out.println("Set " + num+ " is not immediately decodable");
    }
        skip = false;
        num++;
        array.clear();
        continue;
    } else {
        array.add(temp);
    }
  }
 }

}




							

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

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

 public class Main {

     class Point implements Comparable {
         int row;
         int col;

         public Point(int x, int y) {
             this.row = x;
             this.col = y;
         }

         public int compareTo(Object o) {
             int result = 0;
             result = this.row - ((Point) o).row;
             if (result == 0) {
                 return this.col - ((Point) o).col;
             }
             return result;
         }
     }

     int width;
     int length;
     int num;
     Point[] points;
     int t_w;
     int t_l;
     int t_r;
     int t_c;
     int t_p;
     int max;
     int t_max;
     boolean[][] tian;

     public Main() {
         Scanner scan = new Scanner(System.in);
         width = scan.nextInt();
         length = scan.nextInt();
         tian = new boolean[width][length];
         num = scan.nextInt();
         points = new Point[num];
         for (int i = 0; i < num; i++) {
             t_r = scan.nextInt() - 1;
             t_c = scan.nextInt() - 1;
             points[i] = new Point(t_r, t_c);
             tian[t_r][t_c] = true;
         }
         Arrays.sort(points);
         search();
         if (max >= 3) {
             System.out.println(max);
         } else {
             System.out.println(0);
         }
     }

     public void search() {
         max = 0;
         for (int i = 0; i < num; i++) {
             for (int j = i + 1; j < num; j++) {
                 t_w = points[j].row - points[i].row;
                 t_l = points[j].col - points[i].col;
                 t_r = points[i].row - t_w;
                 t_c = points[i].col - t_l;
                 if (t_r >= 0 && t_r < width && t_c >= 0 && t_c < length) {
                     continue;
                 }
                 t_r = points[j].row;
                 t_c = points[j].col;
                 t_max = getLength(2);
                 if (max < t_max) {
                     max = t_max;
                 }

             }
         }
     }

     public int getLength(int sum) {
         t_r += t_w;
         t_c += t_l;
         while (t_r >= 0 && t_r < width && t_c >= 0 && t_c < length) {
             if (hasPoint(t_r, t_c)) {
                 sum++;
             } else {
                 return 0;
             }
             t_r += t_w;
             t_c += t_l;
         }
         return sum;
     }

     public boolean hasPoint(int row, int col) {
         if (tian[row][col]) {
             return true;
         } else {
             return false;
         }
     }

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

							

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

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

public class Main 
{ 
    static HashMap< String,String> codeMap = new HashMap< String,String>(); 
    static HashMap< String,String> ref = new HashMap< String,String>(); 

    public static void main(String[] args) throws Exception 
    { 
        initMap(); 
        readFile(); 
    } 
    static void readFile() throws Exception 
    { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int n = Integer.valueOf(br.readLine()); 
        int count = 0; 
        while(count< n) 
        { 
            process(br.readLine()); 
            count++; 
        } 
    } 
    static void initMap() 
    { 
        codeMap.put("A",".-"); 
        codeMap.put("B","-..."); 
        codeMap.put("C","-.-."); 
        codeMap.put("D","-.."); 
        codeMap.put("E","."); 
        codeMap.put("F","..-."); 
        codeMap.put("G","--."); 
        codeMap.put("H","...."); 
        codeMap.put("I",".."); 
        codeMap.put("J",".---"); 
        codeMap.put("K","-.-"); 
        codeMap.put("L",".-.."); 
        codeMap.put("M","--"); 
        codeMap.put("N","-."); 
        codeMap.put("O","---"); 
        codeMap.put("P",".--."); 
        codeMap.put("Q","--.-"); 
        codeMap.put("R",".-."); 
        codeMap.put("S","..."); 
        codeMap.put("T","-"); 
        codeMap.put("U","..-"); 
        codeMap.put("V","...-"); 
        codeMap.put("W",".--"); 
        codeMap.put("X","-..-"); 
        codeMap.put("Y","-.--"); 
        codeMap.put("Z","--.."); 
        codeMap.put("_","..--"); 
        codeMap.put(".","---."); 
        codeMap.put(",",".-.-"); 
        codeMap.put("?","----"); 

        ref.put(".-","A"); 
        ref.put("-...","B"); 
        ref.put("-.-.","C"); 
        ref.put("-..","D"); 
        ref.put(".","E"); 
        ref.put("..-.","F"); 
        ref.put("--.","G"); 
        ref.put("....","H"); 
        ref.put("..","I"); 
        ref.put(".---","J"); 
        ref.put("-.-","K"); 
        ref.put(".-..","L"); 
        ref.put("--","M"); 
        ref.put("-.","N"); 
        ref.put("---","O"); 
        ref.put(".--.","P"); 
        ref.put("--.-","Q"); 
        ref.put(".-.","R"); 
        ref.put("...","S"); 
        ref.put("-","T"); 
        ref.put("..-","U"); 
        ref.put("...-","V"); 
        ref.put(".--","W"); 
        ref.put("-..-","X"); 
        ref.put("-.--","Y"); 
        ref.put("--..","Z"); 
        ref.put("..--","_"); 
        ref.put("---.","."); 
        ref.put(".-.-",","); 
        ref.put("----","?"); 
    } 
    static void process(String str) 
    { 
        StringBuffer strCode = new StringBuffer(str); 
        StringBuffer lengthCode = new StringBuffer(); 
        StringBuffer currentCode = new StringBuffer(); 
        int index = 0; 
        while(index< strCode.length()) 
        { 
            String code = codeMap.get(strCode.charAt(index++)+""); 
            currentCode.append(code); 
            lengthCode.append(code.length()); 
        } 
        index = lengthCode.length()-1; 
        int start = 0; 
        int end = 0; 
        StringBuffer result = new StringBuffer(); 
        while(index>=0) 
        { 
            end = Integer.valueOf(lengthCode.charAt(index--)+"")+start; 
            String ttt = currentCode.substring(start,end); 
            result.append(ref.get(ttt)); 
            start = end; 
        } 
        if(flag!=0) 
            System.out.println(); 
        flag++; 
        System.out.print(flag+": " + result.toString()); 
    } 
    static int flag = 0; 
}
							

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

 import java.util.Scanner;

 public class Main {

     int[][] a;
     int l;
     int max = Integer.MIN_VALUE;
     int t;
     int t1;
     int t2[];

     public Main() {
         Scanner scan = new Scanner(System.in);
         l = scan.nextInt();
         a = new int[l][l];
         for (int i = 0; i < l; i++) {
             for (int j = 0; j < l; j++) {
                 a[i][j] = scan.nextInt();
             }
         }
         search();
         System.out.println(max);
     }

     public void search() {
         for (int i = 0; i < l; i++) {
             for (int j = 0; j < l; j++) {
                 t1 = 0;
                 t2 = new int[l];
                 for (int k = i; k < l; k++) {
                     t1 += a[k][j];
                     t = t1;
                     if (t > max) {
                         max = t;
                     }
                     for (int m = j + 1; m < l; m++) {
                         t2[m] += a[k][m];
                         t += t2[m];
                         if (t > max) {
                             max = t;
                         }
                     }
                 }
             }
         }
     }

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

							

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

import java.util.*;
import java.math.*;
public class Main {


 public static void main(String[] args) {
  Scanner cin  = new Scanner(System.in);
  BigInteger b,c,d;
  String str,str1,str2,str3;
  int i,len;
  while(cin.hasNext())
  {
   str = cin.next();
   b = new BigInteger(str);
   len=str.length()+1;
      char []kids = new char[len-1];
      for(i=0;i< len-1;i++)
       kids[i]='9';
      str3 = new String(kids);
   str1 = String.valueOf(len);
   c = new BigInteger(str1);
   d = b.multiply(c);
   str2 = d.toString();
   if(str2.compareTo(str3)==0)
         System.out.println(str+" "+"is cyclic");
   else
    
    System.out.println(str+" "+"is not cyclic");
    
  }
  

 }

}


							

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

#include <stdio.h>
struct Color{
    int R,G,B;
}map[16];
int main() {
    int i;
    for ( i = 0; i < 16; ++i)
      scanf("%d%d%d",&map[i].R,&map[i].G,&map[i].B);
struct  Color c;
  while(scanf("%d%d%d",&c.R,&c.G,&c.B)&&c.R>=0){
        int index=0,min=65535;
         for ( i = 0; i < 16; ++i) {
            int d=(c.R-map[i].R)*(c.R-map[i].R)+
                    (c.G-map[i].G)*(c.G-map[i].G)+
                    (c.B-map[i].B)*(c.B-map[i].B);
            if(min>d){
                min=d;
                index=i;
            }
        }
        printf("(%d,%d,%d) maps to (",c.R,c.G,c.B);
        printf("%d,%d,%d)n",map[index].R,map[index].G,map[index].B);
  }

    return 0;
}