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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
   {
    String s=in.nextLine();
    if(s.equals("."))break;
    s=s.substring(0,s.length()-1);
    String[] arr=s.split(", ");
    int l=arr.length;
    int[] kk=new int[l];
    ArrayList< Integer> arrI=new ArrayList< Integer>();
    TreeMap< String,String> arrS=new TreeMap< String,String>();
    for(int i=0;i< l;i++)
    {
      if(isNum(arr[i])){
        arrI.add(Integer.parseInt(arr[i]));
        kk[i]=1;
       }
       else arrS.put(arr[i].toLowerCase(), arr[i]);
    }
    Collections.sort(arrI);
    int w=0,q=0;
    for(int i=0;i< l;i++)
    {
     if(kk[i]==1) System.out.print(arrI.get(w++));
     else {
      System.out.print(arrS.get(arrS.firstKey()));
      arrS.remove(arrS.firstKey());
     }
      if(i!=l-1) System.out.print(", ");
    }
    System.out.println(".");
   }
 }

 public static boolean isNum(String str)
 {
  char w=str.charAt(0);
  if(w!='-'&&(w>57||w<48)) return false;
  for(int i=1;i< str.length();i++)
  {
    char c=str.charAt(i);
    if(c>57||c< 48) return false;
  }
  return true;
 }
}
							

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

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

public class Main {
 public static void main(String[] args) {
   Scanner in = new Scanner(System.in);
    while (true) {
    String number = in.next();
    if (number.equals("0")) {
        break;
    }
    int len = number.length();
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum += number.charAt(i) - '0';
    }
    int result = sum % 9 == 0 ? 9 : sum % 9;
    System.out.println(result);
     }
  }
}

							

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

//* @author: 82638882@163.com
public class Main
{
 public static void main(String[] args)    {

    int i, n, j;
    double e = 0;
 
    System.out.printf("n en- -----------n");
    for (n = 0; n <= 9; ++n)
    {
        i = 1;
        for (j = 1; j <= n; ++j)
            i *= j;
        e += 1.0 / i;
        System.out.printf("%d %10.9fn", n, e);
    }

  }
}
							

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

#include <stdio.h>
#include <memory.h>
bool e[1000][1000];
int low[1000];
int visit[1000];
int vs,n;

void print( int a, int b)
{
    printf( "%d %dn", a+1, b+1 );
}

void search( int s, int f )
{
    int i;
        
    visit[s] = vs++;
    low[s] = visit[s];

    for( i=0; i<n; i++ )
    if( e[s][i] && i != f )
    {
        if( visit[i] == 0 )
        {
            search( i, s );
    
            if( low[i] > visit[s] )
            {
                print(s,i);
                print(i,s);
            
                e[s][i] = e[i][s] = false;
            }
        }

        if( low[i] < low[s] ) low[s] = low[i];
    }
    
}

bool connect[1000];

void find_path( int s )
{
    int i;

    if( connect[s] ) return ;
    
    connect[s] = true;

    for( i=0; i<n; i++ )
    if( e[s][i] )
    {
        e[i][s] = e[s][i] = false;
        print( s, i );

        find_path( i ) ;
    }

    return ;
}

bool init()
{
    int i, j, m;

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

    if( n == 0 && m == 0 ) return false;

    memset( e, 0, sizeof(e) );
    memset( visit, 0, sizeof(visit) );
    memset( low, 0, sizeof(low) );
    memset( connect, 0, sizeof(connect) );

    vs=1;

    while( m-- )
    {
        scanf( "%d %d", &i, &j );

        if( i == j ) print( i, i );
        else e[i-1][j-1] = e[j-1][i-1] = true;
    }

    return true;
}

void doit()
{
    int i, j;

    search( 0, -1 );

    for( i=0; i<n; i++ )
    if( !connect[i] )
    {
        find_path( i ) ;
    }

    return ;
}


int main()
{
    int i=1;
    
    while( init() )
    {
        printf( "%dnn", i++ );
        doit();
        printf( "#n" );
    }

    return 0;
}
							

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

//* @author: 82638882@163.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
 static int[] cost;
 static node[] edge,redge;
 static int n;
 static boolean[] used;
 public static void main(String[] args) throws NumberFormatException, IOException
  {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int h=Integer.parseInt(in.readLine());
   while((h--)!=0)
   {
    String[] ss=in.readLine().split(" ");
    n=Integer.parseInt(ss[0]);
    edge=new node[n];
    redge=new node[n];
    cost=new int[n];
    used=new boolean[n];
    for(int i=0;i< n;i++)
    {
        edge[i]=new node(-1,-1);
        redge[i]=new node(-1,-1);
    }
    int m=Integer.parseInt(ss[1]);
    for(int i=0;i< m;i++)
    {
        ss=in.readLine().split(" ");
        int x=Integer.parseInt(ss[0]);
        int y=Integer.parseInt(ss[1]);
        int w=Integer.parseInt(ss[2]);
        insert(x,y,w);
    }
    long w=0;
    w+=spfa(0);
    w+=spfa(1);
    System.out.println(w);
   }
  }

  static void insert(int x,int y,int w)
  {
    x--;y--;
    node temp=new node(y,w);
    temp.next=edge[x].next;
    edge[x].next=temp;
    temp=new node(x,w);
    temp.next=redge[y].next;
    redge[y].next=temp;    
   }

  static long spfa(int d)
  {
   node temp;
   for(int i=0;i< n;i++)
    cost[i]=2000000000;
   Queue< Integer> qu=new LinkedList< Integer>();
   qu.add(0);
   cost[0]=0;
   while(!qu.isEmpty())
   {
    int u=qu.poll();
    used[u]=false;
    if(d==0)temp=edge[u].next;
    else temp=redge[u].next;
    while(temp!=null)
    {
        if(cost[temp.v]>cost[u]+temp.w)
        {
          cost[temp.v]=cost[u]+temp.w;
          if(!used[temp.v])
          {
            qu.add(temp.v);
            used[temp.v]=true;
          }
        }
        
        temp=temp.next;
    }
   }
  long ans=0;
  for(int i=0;i< n;i++)
    ans+=cost[i];
  return ans;
 }
    
}

class node
{
    int v,w;
    node next=null;
    public node(int vv,int ww)
    {
        v=vv;w=ww;
    }
}
							

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

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

public static int minP(String s)
{
   int i = 0, j = 1, k = 0;
   int l = s.length();
   while (true)
   {
    if (i + k >= l || j + k >= l) break;
    if (s.charAt(i + k) == s.charAt(j + k))
    {
        k++;
        continue;
     }
     else
     {
      if (s.charAt(j + k) > s.charAt(i + k)) j += k + 1;
      else
          i += k + 1;
      k = 0;
      if (i == j) j++;
     }
   }
         return Math.min(i, j);
}

public static void main (String args[])
{
    Scanner sc=new Scanner(System.in);
    String s;
    int t, pos;
    t=sc.nextInt();

   while ((t--)!=0)
   {
     s=sc.next();
     s += s;
     pos = minP(s);
     System.out.printf("%dn", pos + 1);

   }
 }
}
							

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

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

public class Main {
 static final int N = 500+10;
 static int n,m;
 static boolean flag[] = new boolean[N];
 static long sum[] = new long[N],num[] = new long[N];
 public static void main(String[]args) throws Exception{
  int t,i;
  long best;
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  t = (int)Get_Num(cin);
  while(t--!=0){
    n = (int) Get_Num(cin);
    m = (int) Get_Num(cin);
    for(i=0;i< n;++i){
        num[i] = (long) Get_Num(cin);
        if(i==0) sum[i] = num[i];
        else sum[i] = num[i]+sum[i-1];
    }
    best = binary_search();
    make_ans(best);
  }
 }

 static void make_ans(long best){
  int i,j,k=0,last=n-1;
  Arrays.fill(flag, false);
  for(i=n-1;i>0;--i){
    if(sum[last]-sum[i-1]>best){
        flag[i] = true;
        last = i;
        ++k;
    }
  }
  for(i=0;i< n && k< m-1;++i){
    if(flag[i]==false){
        flag[i] = true;
        ++k;
    }
  }
        
  PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  for(i=0;i< n;++i){
    if(i!=0) out.print(" ");
    out.print(num[i]);
    if(flag[i])
        out.print(" /");
  }
  out.println();
  out.flush();
        
  }
 static long binary_search(){
  long Min = num[0],Max = sum[n-1],Mid;
  while(Min+1< Max){
    Mid = (Min+Max)/2;
    if(can(Mid)) Max = Mid;
    else Min = Mid;
  }
  if(can(Min)) return Min;
   return Max;
 }

 static boolean can(long cnt){
    int i,must=0;
    long temp=0;
    for(i=0;i< n;++i){
        if(num[i]>cnt) return false;
        if(temp+num[i]>cnt){
            ++must;
            temp = num[i];
        }
        else temp+=num[i];
    }
    if(temp>0) must++;
    if(must<=m) return true;
    return false;
   }
    static double Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return cin.nval;
    }
}

							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
        String[] str = new String[2];   
        String rawA, rawB;   
           
        int a, b, sum = 0;   
           
        for(int i = 0; i < num; i++)   
        {   
            str = cin.nextLine().split(" ");   
            rawA = str[0];   
            rawB = str[1];   
                   
            a = Integer.valueOf(reverse(rawA)).intValue();   
            b = Integer.valueOf(reverse(rawB)).intValue();   
               
//          System.out.println(a + " " + b);   
            sum = a + b;   
            System.out.println(reverse(""+sum));   
        }   
           
    }   
       
    public static String reverse(String str)   
    {   
        int index = str.length() - 1;   
        while(str.charAt(index) == '0')   
            index--;   
  
        String trimStr = str.substring(0,index+1);   
        StringBuffer sb = new StringBuffer();   
           
        for(int i = trimStr.length()-1; i >=0; i--)   
            sb.append(trimStr.charAt(i));   
           
        return sb.toString();   
    }   
  
}  

							

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

import java.util.*;   
import java.math.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        BigDecimal bd1 = BigDecimal.valueOf(0);   
        BigDecimal bd2 = BigDecimal.valueOf(0);   
        String str;   
           
        while(cin.hasNext())   
        {   
            str = cin.nextLine();   
            if(str.equals("0"))   
                break;   
            else  
            {   
                bd2 = new BigDecimal(str);   
                bd1 = bd1.add(bd2);   
            }   
        }   
           
        System.out.println(bd1.toPlainString());   
           
  
    }   
  
}  


							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        while(in.hasNext())
        {
        String s=in.next();
        boolean bb=true;
        for(int i=0;i< s.length()-1;i++)
        {
          if(s.charAt(i)-s.charAt(i+1)>=0)
          {
            System.out.println(0);
            bb=false;
            break;
           }
        }
        if(!bb)continue;
        int l=s.length();
        long ans=0;
        for(int i=1;i< l;i++)
            ans+=find(26,i);
        int k=0;
        for(int i=0;i< l;i++)
        {
          k=0;
          if(i!=0)k=s.charAt(i-1)-'a'+1;
          int y=s.charAt(i)-'a'+1;
          for(int j=y-1;j>k;j--)
          {
            ans+=find(26-j,l-i-1);
          }
        }
        System.out.println(ans+1);
        }
    }
    public static long find(int u,long a)
    {
        if(u< a) return 0;
        if(a==0) return 1;
        long l=1;
        for(int i=u;i>u-a;i--)
            l*=i;
        for(int i=1;i<=a;i++)
            l/=i;
        return l;
    }
}
							

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

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

public class Main {
 static final int N = 100000;
 static String str[] = new String[N];
 static int n;
 static void start(){
    for(int i=0;i< n;++i) str[i] = new String();
  }

public static void main(String[]args) throws Exception{
    int i;
    Scanner cin = new Scanner(System.in);
    while(true){
        n = cin.nextInt();
        if(n<=0) break;
        cin.nextLine();
        for(i=0;i< n;++i){
            str[i] = cin.nextLine();
            //System.out.println(str[i]);
        }
        System.out.println(solve());
    }
  }

 public static int solve(){
  int i,j,max_length=0,length=str[0].length(),ans=0,cnt;
  for(i=0;i< n;++i){
    ans = 0;
    for(j=0;j< length;++j){
        if(str[i].charAt(j)=='X')
            ++ans;
    }
    max_length = ans>max_length?ans:max_length;
}
ans = 0;
for(i=0;i< n;++i){
    cnt = 0;
    for(j=0;j< length;++j){
        if(str[i].charAt(j)=='X')
            ++cnt;
    }
    ans+=max_length-cnt;
 }
 return ans;
 }
}

							

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

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

public class Main {

    public static int factor(int a, int b) {
    if (b == 0)
        return a;
    else
      return factor(b, a % b);

    }

public static void main(String[] args) {
  // TODO Auto-generated method stub
 Scanner in = new Scanner(System.in);
  while (true) {
    int n = in.nextInt();
    if (n == 0)
        break;
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
        array[i] = in.nextInt();
    }
    int total = (n - 1) * n / 2;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (factor(array[i], array[j]) == 1)
                count++;
        }
    }
    if (count == 0)
        System.out.println("No estimate for this data set.");
    else {
        double pi = Math.sqrt(6.0 * total / count);
        DecimalFormat output = new DecimalFormat("#.######");
        System.out.println(output.format(pi));
    }
   }
 }

}

							

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

#include<stdio.h>
int main()
{
    char c;
    int q=1;
    while((c=getchar())!=EOF)
    {
        if(c == '"')
        {
            printf(q ? "``":"''");
            q=!q;
        }
        else
            printf("%c",c);
    }
    return 0;
}
							

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

#include <iostream>
#define MAX 200000000
using namespace std;
long r[300],sum[300][40],one[300][300];
long from[300][40],to[300][40],at[300][40];
long printDetail(long i, long j)//递归输出
{
    if(j<=0||i<=0) return 1;
    long num=printDetail(from[i][j]-1,j-1);
    cout<<"Depot "<<num<<" at restaurant "<<at[i][j]<<" serves ";;
    if(from[i][j]==to[i][j]) cout<<"restaurant "<<from[i][j]<<endl;
    else cout<<"restaurants "<<from[i][j]<<" to "<<to[i][j]<<endl;
    return num+1;
}
int main()
{
    long n,K,i,j,k,middle,min,get,c=1;
    while(cin>>n>>K&&(n||K))
    {
        for(i=1;i<=n;i++) cin>>r[i];
        memset(one,0,sizeof(one));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                middle=(i+j)/2;
                for(k=i;k<middle;k++)
                   one[i][j]+=r[middle]-r[k];
                for(k=middle+1;k<=j;k++)
                    one[i][j]+=r[k]-r[middle];
            }
        }
        for(i=1;i<=n;i++) sum[i][0]=MAX;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i&&j<=K;j++)
            {
                sum[i][j]=MAX;
                for(k=j-1;k<=i-1;k++)
                {
                    get=sum[k][j-1]+one[k+1][i];
                    if(get<sum[i][j])
                    {
                        sum[i][j]=get;
                        from[i][j]=k+1;
                        to[i][j]=i;
                        at[i][j]=(k+1+i)/2;
                    }//记录动态规划路径
                }
            }
        }
        cout<<"Chain "<<c++<<endl;
        printDetail(n,K);
        cout<<"Total distance sum = "<<sum[n][K]<<endl<<endl;
    }
    return 0;
}
							

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

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

public class Main {
 public static void main(String[] args){
  int n, m, c;
  int i, j = 1, k;
  Scanner scanner = new Scanner(System.in);
  boolean blowFuse = false;
  int sumOfPower = 0;
  while(true){
    n = scanner.nextInt();
    m = scanner.nextInt();
    c = scanner.nextInt();
    if(n == 0 && m == 0 && c == 0){
         break;
    }
    sumOfPower = 0;
    int max = 0;
    blowFuse = false;
    Device[] devices = new Device[n + 1];
    for(i = 1; i <= n; i++){
      int num = scanner.nextInt();
      devices[i] = new Device(i, num, false);
    }
    for(i = 1; i <= m; i++){
      k = scanner.nextInt();
      if(devices[k].state && sumOfPower > 0){
        sumOfPower -= devices[k].pow;
       devices[k].state = false;
    }
    else if(!devices[k].state){
       sumOfPower += devices[k].pow;
       devices[k].state = true;
       if(sumOfPower > max){
        max = sumOfPower;
       }
       if(sumOfPower > c){
        blowFuse = true;
       }
    }
    }
    System.out.println("Sequence " + (j++));
    if(blowFuse){
    System.out.println("Fuse was blown.");
    }
    else{
    System.out.println("Fuse was not blown.nMaximal power consumption was "+ max +" amperes.");
    }
    System.out.println();
  }
        
}
  
  static class Device{
    int num;
    int pow;
   boolean state; // true : power on , false : power in
   public Device(int num, int pow, boolean state){
   this.num = num;
   this.pow = pow;
   this.state = state;
   }

  public boolean equals(Device rhs){
    return(this.num == rhs.num);
 }
}
}


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int c=0;
  while(true)
  {
    int a=in.nextInt();
    if(a==0)break;
    c++;
    int[] arr=new int[a];
    int total=0;
    for(int i=0;i< a;i++)
    {
        arr[i]=in.nextInt();
        total+=arr[i];
    }
    total/=a;
    int ans=0;
    for(int i=0;i< a;i++)
    {
        if(arr[i]>total)
            ans+=arr[i]-total;
    }
    System.out.println("Set #"+c);
    System.out.println("The minimum number of moves is "+ans+".");
    System.out.println();
   }
 }
}
							

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

#include<stdio.h>

#define debug 0
#define NMAX 20
#define DMAX 30
#define INF 1000000000
#define KMAX 1001
long d[KMAX][NMAX];
int main()
{

#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

    int T=1,N,K,i,j,k;
    long c[NMAX+1][NMAX+1][DMAX+1];
    int t[NMAX+1][NMAX+1];
    scanf("%d%d",&N,&K);
    while(N&&K)
    {
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
            {
                if(i!=j)
                {
                    scanf("%d",&t[i][j]);
                    for(k=1;k<=t[i][j];k++)
                    {
    
                        scanf("%ld",&c[i][j][k]);
                        
                    }
                }
                else
                {
                    t[i][j]=0;
                }
            }
        k=K;
        for(i=1;i<N;i++)
        {
            if(c[i][N][(k-1)%t[i][N]+1]==0)
                d[k][i]=INF;
            else
                d[k][i]=c[i][N][(k-1)%t[i][N]+1];
        }
        d[k][N]=INF;
        for(k=K-1;k>=1;k--)
        {
            for(i=1;i<=N;i++)
            {
                d[k][i]=INF;
                for(j=1;j<=N;j++)
                {
                    if(i!=j&&c[i][j][(k-1)%t[i][j]+1]&&d[k][i]>c[i][j][(k-1)%t[i][j]+1]+d[k+1][j])
                    {
                        d[k][i]=c[i][j][(k-1)%t[i][j]+1]+d[k+1][j];
                    }
                }
            }
        }
        printf("Scenario #%dn",T);

        if(d[1][1]!=INF)
            printf("The best flight costs %ld.nn",d[1][1]);
        else
            printf("No flight possible.nn");

        scanf("%d%d",&N,&K);
        T++;
    }

#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}
							

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

#include<iostream>
using namespace std;
int xmin,ymin,xmax,ymax,n;
int main()
{int i,xn,yn,xp,yp,dx,dy,c_n=0;
while(1)
{cin>>n;
if(!n)break;
xmin=-32000;ymax=32000;
xmax=-xmin;ymin=-ymax;
cin>>xp>>yp;
dx=xp;dy=yp;
for(i=0;i<n;i++)
{if(i<n-1)cin>>xn>>yn;else {xn=dx;yn=dy;}
if(yn==yp){if(xn>xp){if(yp<ymax)ymax=yn;}
            else if(yp>ymin)ymin=yn;
            }
else {if(yn>yp){if(xn>xmin)xmin=xn;}
            else if(xn<xmax)xmax=xn;
            }
xp=xn;yp=yn;
}
cout<<"Floor #"<<++c_n<<endl;
if(xmin<=xmax&&ymin<=ymax)cout<<"Surveillance is possible."<<endl<<endl;
else cout<<"Surveillance is impossible."<<endl<<endl;
}
return 0;
}
							

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define sq2 0.70710678118654752440084436210485
#define INF 30000
#define NMAX 52
int p[10]={0};
int as[10]={0};
double xd[8]={0,sq2,1,sq2,0,-sq2,-1,-sq2};
double yd[8]={1,sq2,0,-sq2,-1,-sq2,0,sq2};
double cx,cy;
void findpos(char *s)
{
    s[strlen(s)-1]=0;
    int len;
    char direct[4];
    sscanf(s,"%d%s",&len,direct);
    int d;
    
    if(!strcmp("NE",direct))
        d=1;
    else if(!strcmp("E",direct))
        d=2;
    else if(!strcmp("SE",direct))
        d=3;
    else if(!strcmp("SW",direct))
        d=5;
    else if(!strcmp("W",direct))
        d=6;
    else if(!strcmp("NW",direct))
        d=7;
    else if(!strcmp("N",direct))
        d=0;
    else if(!strcmp("S",direct))
        d=4;
    cx+=xd[d]*len;
    cy+=yd[d]*len;


        
}
int input(char *s)
{
    int i=0;
    do
    {
        
        scanf("%c",&s[i]);
        if(s[i]==',')
        {
            s[i+1]='';
            return 1;
        }
        else if(s[i]=='.')
        {
            s[i+1]='';
            return 2;
        }
        else if(s[i]=='D')
        {
            return 3;
        }
        i++;

    }
    while(1);
}

int main()
{

#if _DEBUG    
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif
char s[10];

    int flag=0;
    int times=1;
    double dis;
    
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    cx=0;
    cy=0;
    while(flag!=3)
    {
        flag=input(s);
        if(flag==1)
        {
            findpos(s);
        }
        if(flag==2)
        {
            findpos(s);
            dis=sqrt(cx*cx+cy*cy);
            printf("Map #%dn",times);
            printf("The treasure is located at (%.3f,%.3f).n",cx,cy);
            printf("The distance to the treasure is %.3f.nn",dis);
            cx=0;
            cy=0;
            times++;
        }
            
    }
    
    

        
#if _DEBUG
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
							

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

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

class Main
{
  public static Scanner cin=new Scanner(new BufferedInputStream(System.in));
  public static int [] coef=new int[11];
  public static String temp;
  public static void work(int con,int expo)
  {
    while (true)
    {
    temp=cin.next();
    switch (temp.charAt(0))
    {
      case 'O':
       coef[expo]+=con*Integer.parseInt(cin.next());
       break;
     case 'L':
      temp=cin.next();
      if (temp.charAt(0)=='n')
       work(con,expo+1);
      else
       work(con*Integer.parseInt(temp),expo);
      break;
    case 'E':
      return;
     }
    }
  }

  public static void output()
  {
    int i,j=0,now=0;
    for (i=0;i<=10;i++)
     if (coef[i]!=0)
    j++;
     if (j==0)
     {
    System.out.print(0);
    return;
      }
     else
    for (i=10;i>=0;i--)
      if (coef[i]!=0)
       if (i==0)
        System.out.print(coef[i]);
       else
       {
         if (coef[i]==1)
        System.out.print("n");
         else
        System.out.print(coef[i]+"*n");
         if (i>1)
        System.out.print("^"+i);
         if (now< j-1)
        System.out.print("+");
         now++;
       }
    }
    
  public static void main(String [] args)
  {
    int n=Integer.parseInt(cin.nextLine()),i;
    for (i=1;i<=n;i++)
    {
        Arrays.fill(coef,0);
     temp=cin.next();
     work(1,0);
     System.out.println("Program #"+i);
     System.out.print("Runtime = ");
     output();
     System.out.println();
     System.out.println();
    }
   }
}
							

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

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define MAXNO 102
int tr[MAXNO][2*MAXNO-1]={0};
int maxtr[MAXNO][2*MAXNO-1]={0};
int curmax=0;
int min(int a,int b)
{
    if(a>b)
        return b;
    else
        return a;
}
int sum(int a1,int an,int n)
{
    return (a1+an)*n/2;
}
int ln(int n)
{
    return 2*n-1;
}
int mingrid(int l,int r,int d)
{
    if(d)
        return min(l,r)+1;
    else
        return 1;
    
}
int main()
{
    int N,i,j,l,r,d,di,k=1;
    int nsum,nline;
    char s[(1+MAXNO)*MAXNO/2];
    cin>>N;
    while(N)
    {
        curmax=0;
        nsum=sum(1,N,N);
        nline=ln(N);
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=nline;j++)
            {
                tr[i][j]=0;
                maxtr[i][j]=0;
            }
        }
        
        for(i=1;i<=N;i++)
        {
            cin>>s;
            for(j=1;j<=ln(N-i+1);j++)
            {
                if(s[j-1]=='-')
                    tr[i][j+i-1]=1;
            }
        }

        for(i=1;i<=nline;i++)
        {
            maxtr[1][i]=tr[1][i];
            if(curmax<maxtr[1][i])
                curmax=maxtr[1][i];
        }
        if(N>1)
        {
            maxtr[N][N]=tr[N][N];
            for(i=2;i<=N;i++)
            {
                for(j=i;j<=nline-i+1;j++)
                {
                    if((j+!(i%2))%2)
                    {
                        l=maxtr[i-1][j-1];
                        r=maxtr[i-1][j+1];
                        d=tr[i-1][j];
                        if(tr[i][j])
                            maxtr[i][j]=mingrid(l,r,d);
                        if(curmax<maxtr[i][j])
                            curmax=maxtr[i][j];
                    }
                }
                di=N-i+1;
                for(j=di;j<=nline-di+1;j++)
                {
                    if((j+!(di%2))%2==0)
                    {
                        l=maxtr[di+1][j-1];
                        r=maxtr[di+1][j+1];
                        d=tr[di+1][j];
                        if(tr[di][j])
                            maxtr[di][j]=mingrid(l,r,d);
                        if(curmax<maxtr[di][j])
                            curmax=maxtr[di][j];
                    }
                }
            }
        }
        cout<<"Triangle #"<<k<<endl;
        cout<<"The largest triangle area is "<<curmax*curmax<<'.'<<endl;
        cout<<endl;
        cin>>N;
        k++;
        
    }
    
    return 0;
}
							

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

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

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=0,k=0;
        boolean band;
        int M[][]=new int[5000][4];
        while(scan.hasNext()){
            n=scan.nextInt();
            for(int i=0;i< n;i++){
                for(int j=0;j< 4;j++){
                    M[i][j]=scan.nextInt();
                }
            }
            k=0;
            for(int i=0;i< n;i++){
                band=false;
                for(int j=0;j< n;j++){
                    if(j!=i&&M[j][0]<=M[i][0]&&M[j][1]>=M[i][1]&&M[j][2]<=M[i][2]&&M[j][3]>=M[i][3]){
                        band=true;
                        break;
                    }
                }
                if(band)k++;
            }
            System.out.println(k);
        }
    }
}
							

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

import java.util.*;

/**
 *
 * @author yeming
 */
public class Main {

    static int n;
    static LinkedList< Integer>[] matrix;
    static int[] result;
    static boolean[] state;
    static int ans;
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()) {
            init(sc);
            for(int i = 0; i < n; i++) {
                Arrays.fill(state, false);
                if (find(i)) {
                    ans++;
                }
            }
            System.out.println(n-ans/2);
        }
    }

    private static boolean find(int i) {
        for(int t : matrix[i]) {
            if(!state[t]) {
                state[t] = true;
                if(result[t] == -1
                        || find(result[t])) {
                    result[t] = i;
                    return true;
                }
            }
        }
        return false;
    }

    private static void init(Scanner sc) {
        ans = 0;
        n = sc.nextInt();
        matrix = (LinkedList< Integer>[])new LinkedList[n];
        for(int i = 0; i < n; i++) {
            sc.next();//id, the same as i
            String str = sc.next();
            String numStr = str.substring(1, str.length()-1);
            int num = Integer.parseInt(numStr);
            matrix[i] = new LinkedList< Integer>();
            for (int j = 0; j < num; j++) {
                int id = sc.nextInt();
                matrix[i].add(id);
            }
        }
        state = new boolean[n];
        Arrays.fill(state, false);
        result = new int[n];
        Arrays.fill(result, -1);
    }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 static int[] p,q;
 static int m,n;
 static Queue< mye> qu;
 public static void main(String[] args) throws IOException
 {
  Scanner in=new Scanner(System.in);
  qu=new LinkedList< mye>();
  while(in.hasNext())
  {
    qu.clear();
    n=in.nextInt();
    m=in.nextInt();
    p=new int[m];
    for(int i=0;i< m;i++)
        p[i]=in.nextInt();
    Arrays.sort(p);
    if(n==0)
        System.out.println(0);
    else {
        q=new int[n];
    bsf(q,p);
    if(q[0]==0)System.out.print(0);
    System.out.println();
    }        
    }
 }

  static void f(mye e)
  {
   if(e.pre!=null)
   {
    f(e.pre);
   }
   if(e.pre!=null)System.out.print(e.curN);
  }


  static void bsf(int[] q,int[] p)
  {
   qu.add(new mye(0,0,null));
   while(!qu.isEmpty())
   {
    mye uu=qu.poll();
    int num=uu.dig*10;
    for(int i=0;i< m;i++)
    {
      int k=num+p[i];
      if(k==0) continue;
      k%=n;
      if(q[k]==0)
      {
       q[k]++;
       if(k==0)
       {
        mye tt=new mye(k,p[i],uu);
        f(tt);
        return;
       }
       qu.add(new mye(k,p[i],uu));
     }
    }
    }        
 }
}
class mye
{
    int dig=0;
    int curN;
    mye pre;
    public mye(int d,int c,mye e)
    {
        dig=d;
        curN=c;
        pre=e;
    }
}
							

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

#include <stdio.h>
#include <memory.h>
#define min(a,b) ((a)<(b)?(a):(b))
int e[2000][20];
int en[2000];
int ans[2000][2], n;

void calc( int k, int f ) {
    int i;
    ans[k][0] = 0, ans[k][1] = 1;
    for( i=0; i<en[k]; i++ ) {
        if( e[k][i] != f ) {
            calc( e[k][i], k );
            ans[k][0] += ans[ e[k][i] ][1];
            ans[k][1] += min( ans[ e[k][i] ][0], ans[ e[k][i] ][1] );
        }
    }
}

int main( ) {
    int i, k, m, l, j;
    while( scanf( "%d", &n ) == 1 ) {

        memset( en, 0, sizeof en );

        for( j=0; j<n; j++ ) {
            scanf( "%d:(%d)", &k, &m );
            for( i=0; i<m; i++ ) {
                scanf( "%d", &l );
                e[k][ en[k]++ ] = l;
                e[l][ en[l]++ ] = k;
            }
        }

        calc( 0, -1 );
        printf( "%dn", min( ans[0][0], ans[0][1] ) );
    }
    return 0;
}
							

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

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str1 = in.next();
            String str2 = in.next();
            int[][] DP = new int[str1.length()+1][str2.length()+1];
            int i;
            for(i=0;i<=str1.length();i++)
                DP[i][0] = 0;
            for(i=0;i<=str2.length();i++)
                DP[0][i] = 0;
            for(i=1;i<=str1.length();i++){
                for(int j=1;j<=str2.length();j++){
                    if(str1.charAt(i-1) == str2.charAt(j-1))
                        DP[i][j]=DP[i-1][j-1]+1;
                    else
                        DP[i][j]=Math.max(DP[i-1][j], DP[i][j-1]);
                }
            }
            System.out.println(DP[str1.length()][str2.length()]);
        }        
    }
}


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
    Scanner in=new Scanner(System.in);
    int a=in.nextInt();
    while((a--)!=0)
    {
        int b=in.nextInt();
        int ans=0;
        int c=b/2;
        if(b%2==0) ans=c*(c-1);
        else ans=c*c;
        System.out.println(ans);
    }
  }
}
							

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

 
							

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



#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0
int main(void) {
    int iCase;
    if(DEBUG)
    freopen("in","r",stdin);
    scanf("%d",&iCase);
    int number;
     for ( number = 1; number <=iCase; ++number) {
      int N,M;
      scanf("%d%d",&M,&N);
      printf("Scenario #%d:n",number);
      printf("%d.",M*N);
      if(M%2&&N%2)printf("41");
      else printf("00");
      printf("nn");
    }
   return 0;
}

							

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

#include<iostream>
using namespace std;

const long big=1024*1024*1024;
long b;
long n,m;
char a[16][34]={
". . . . . . . . . . . . . . . 1",
". . . . . . . . . . . . . 1 1 .",
". . . . . . . . . . . 1 1 1 . .",
". . . . . . . . . 1 1 . 1 . . .",
". . . . . . . 1 1 1 . 1 . . . .",
". . . . . 1 1 . 1 1 1 . . . . .",
". . . 1 1 1 . . 1 1 . . . . . .",
". 1 1 . 1 . . . 1 . . . . . . .",
"1 1 . 1 . . . 1 . . . . . . . .",
"1 1 1 . . 1 1 . . . . . . . . .",
"1 1 . 1 1 1 . . . . . . . . . .",
"1 1 1 . 1 . . . . . . . . . . .",
"1 1 . 1 . . . . . . . . . . . .",
"1 1 1 . . . . . . . . . . . . .",
"1 1 . . . . . . . . . . . . . .",
"1 . . . . . . . . . . . . . . ."};


int find()
{if(m>n)return 0;
b=big;
while(1)
{
if(m<=16&&n<=m/2+8){if(a[16-n][(m-1)*2]=='1')return 1;else return 0;}

while(b/2>=m&&n<=m/2+b/4)b/=2;

if(m>b/2){m-=b/2;n-=b/4;continue;}
if(n>=b/4+m){n-=b/4;continue;}
return 0;
}
return 0;
}


int main()
{int t;
cin>>t;
while(t--)
{cin>>n>>m;
cout<<find()<<endl;
}


return 0;
}
							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) throws IOException {
        BigInteger a;
        BigInteger b;
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        long c=0,d=0;
        long n=0;
        while((n=Long.parseLong(stdin.readLine()))!=0){
        //for(n=1;n<=200;n++)   {
        b=new BigInteger(1+"");
        d=1;
            while(true){
                c=Long.parseLong(Long.toBinaryString(d));
                //a=new BigInteger(b.toString(2));
                //if(a.mod(new BigInteger(n+"")).toString().equals("0"))break;
                if(c%n==0) break;
                //b=b.add(new BigInteger("1"));
                d++;
            }
            System.out.println(Long.toBinaryString(d));
        }
    }
}
							

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

import java.util.*;

public class Main {

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

 int n = cin.nextInt();
 while(n > 0) {
  int test = cin.nextInt();
  if(test <= 3)
   System.out.println(1);
  else {
   double result = 0.5*Math.log10(2*test*Math.PI)+
   test*Math.log10(test/Math.E)+1;;
   System.out.println((int)(result));
  }
  n--;
 }
}

}

							

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

//* @author: 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
    static int n,m,match[]=new int[201];
    static boolean mat[][]=new boolean[201][201],v[]=new boolean[201];
    static boolean findmatch(int pre)
    {
        int i;
        for(i=0;i< m;i++)
        {
            if(mat[pre][i]&&!v[i])
            {
                v[i]=true;
                int buf=match[i];
                match[i]=pre;
                if(buf==-1||findmatch(buf))return true;
                match[i]=buf;
            }
        }
        return false;
    }
    static int bmatch()
    {
        int ret=0,i;
        for(i=0;i< n;i++)
        {
            Arrays.fill(v, false);
            if(findmatch(i))ret++;
        }
        return ret;
    }
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int t=cin.nextInt(),k,a,b;
        while(t-->0)
        {
            m=n=cin.nextInt();
            int i,j;
            for(i=0;i< n;i++) for(j=0;j< n;j++)mat[i][j]=false;
            k=cin.nextInt();
            while(k-->0)
            {
                a=cin.nextInt();
                b=cin.nextInt();
                a--;
                b--;
                mat[a][b]=true;
            }
            Arrays.fill(match, -1);
            System.out.println(n-bmatch());
        }
    }
}


							

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

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
   cin = new Scanner(System.in);
        
   int m = cin.nextInt();
   for(int i=0;i< m;i++)
     run();
  }
    
 static void run(){
   int n = cin.nextInt();
   int k = cin.nextInt();
        
   Graph graph = new Graph(n);
   for(int i=0;i< k;i++)
    graph.addEdge(cin.nextInt(), cin.nextInt());
        
   graph.Coloring(0);
   System.out.println(graph.maxBlack);
   graph.record.print();
  }
}

class Graph{
 int n;
 Node[] nodes;
    
 int maxBlack=-1;
 Record record;
    
 public Graph(int n){
   this.n = n;
        
   nodes = new Node[n];
  for(int i=0;i< n;i++)
    nodes[i] = new Node();
        
  record = new Record();
 }
    
 void addEdge(int m, int n){
   nodes[m-1].add(nodes[n-1]);
   nodes[n-1].add(nodes[m-1]);
 }
    
 void Coloring(int colored){
   if(colored< n){
     int position=0;
    while(nodes[position].color != 0)
     position = (position+1)%n;
     Node node = nodes[position];
            
     node.color = 'b';
     if(node.check() == true)
    Coloring(colored+1);
            
     node.color = 'w';
     Coloring(colored+1);
            
     node.color = 0;
     return;    
   }    
    
   int tmp = countBlack();
   if(tmp > maxBlack){
    maxBlack = tmp;
    record.clear();
            
    for(int i=0;i< n;i++)
         if(nodes[i].color == 'b')
        record.add(new Integer(i+1));
    }
            
}
        
    
int countBlack(){
  int count=0;
  for(int i=0;i< n;i++)
    if(nodes[i].color == 'b')
    count++;
  return count;
 }
}

class Node{
 char color=0;
 LinkedList< Node> linkList;
    
 void setColor(char c){
   color = c;
}

void add(Node another){
  if(linkList==null)
    linkList = new LinkedList< Node>();
        
  linkList.add(another);
 }
    

 boolean isEdgeColored(){
  for(Node n:linkList)
    if(n.color == 0)
      return false;
  return true;
 }
    
 boolean check(){
  if(color=='w')
    return true;
            
   for(Node n:linkList)
    if(n.color=='b')
    return false;
   return true;
 }
}

class Record extends ArrayList< Integer>{
  void print(){
   for(Integer p:this)
    System.out.print(p+" ");
   System.out.println();
 }
    
}
							

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

#include<iostream>
#include"math.h"
using namespace std;
#define MSIZE 1000
const double pi=3.14159265358979324;
const double eps=1e-15;
struct point
{double x,y;};

    
struct typearc
{double a,b;};

struct typecir
{point ct;
double r;
typearc arc[360];
int n;
};

int cmp(double a,double b)
{if(fabs(a-b)<eps)return 0;
if(a>b)return 1;
return -1;
}

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

inline int div(typearc &arc1,typearc &arc2)
{if(cmp(arc1.a,arc2.b)>=0||cmp(arc1.b,arc2.a)<=0)return 0;
 if(cmp(arc1.a,arc2.a)>=0&&cmp(arc1.b,arc2.b)<=0)return -1;
 if(cmp(arc1.a,arc2.a)<0&&cmp(arc1.b,arc2.b)>0)return 3;
 if(cmp(arc1.a,arc2.a)>=0)return 1;
 return 2;
}


int div_arc(typecir &c,typearc &arc)
{int i,j,result,key=0,num=c.n;typearc t;
for(i=0;i<num;i++)
    {result=div(c.arc[i],arc);
//    cout<<"result"<<result<<endl;
//    cout<<arc.a<<' '<<arc.b<<' '<<c.arc[i].a<<' '<<c.arc[i].b<<endl;
    if(result==0)continue;
    key=1;
    t=c.arc[i];
    for(j=i;j<c.n-1;j++)c.arc[j]=c.arc[j+1];
    i--;num--;
    switch(result)
        {case -1:c.n--;break;
         case 3:c.arc[c.n-1].a=t.a;
            c.arc[c.n-1].b=arc.a;
            c.arc[c.n].a=arc.b;
            c.arc[c.n].b=t.b;
            c.n++;break;
         case 1:c.arc[c.n-1].a=arc.b;
            c.arc[c.n-1].b=t.b;
            break;
         case 2:c.arc[c.n-1].a=t.a;
            c.arc[c.n-1].b=arc.a;
            break;
        }
    
    }    
return key;
}        

typearc jiao(typecir &a,typecir &b)
{typearc arc;
double da,d,l_ab,l,p;
l_ab=jl(a.ct,b.ct);
da=asin((b.ct.y-a.ct.y)/l_ab);    
if(cmp(a.ct.x,b.ct.x)>0)da=pi-da;
if(cmp(da,0)<0)da=2*pi+da;
//    cout<<da<<endl;

p=(a.r+b.r+l_ab)/2;
l=2*sqrt(p*(p-a.r)*(p-b.r)*(p-l_ab))/l_ab;
d=asin(l/a.r);

if(cmp(l_ab*l_ab+a.r*a.r,b.r*b.r)<0)d=pi-d;
arc.a=da-d;
arc.b=da+d;
return arc;
}

int c_c_type(typecir &a,typecir &b)
{double l=jl(a.ct,b.ct);
if(cmp(l,a.r+b.r)>=0)return 0;
if(cmp(l,fabs(a.r-b.r))<=0)return -1;
return 1;
}

int doit(typecir &c1,typecir &c2)
//judge cir2
{int i,key=0;typearc arc,arct;
switch(c_c_type(c1,c2))
{case 0:return 0;
 case -1:if(cmp(c2.r,c1.r)<=0)c2.n=0;
     if(cmp(c1.r,c2.r)<0)if(c1.n){c1.n=0;return 1;}    
     return 0;
 case 1:arc=jiao(c1,c2);     
    if(cmp(arc.b,2*pi)>0){arc.b-=2*pi;arc.a-=2*pi;}
    if(cmp(arc.a,0)<0){arct.a=arc.a+2*pi;arct.b=2*pi;arc.a=0;
            key|=div_arc(c1,arc);
                 key|=div_arc(c1,arct);    }
    else  key|=div_arc(c1,arc);
    arc=jiao(c2,c1);
     if(cmp(arc.b,2*pi)>0){arc.b-=2*pi;arc.a-=2*pi;}
         if(cmp(arc.a,0)<0){arct.a=arc.a+2*pi;arct.b=2*pi;arc.a=0;
                        div_arc(c2,arc);
                        div_arc(c2,arct);  }
         else  div_arc(c2,arc);
    return key;
}
return 0;
}

typecir cir[100];

int main()
{int n,i,j,key,answer,k,h;
       
while(1)
       {answer=0;
    cin>>n;if(n==0)break;
    for(i=n-1;i>=0;i--)
    {cin>>cir[i].ct.x>>cir[i].ct.y>>cir[i].r;
    cir[i].ct.x*=MSIZE;cir[i].ct.y*=MSIZE;cir[i].r*=MSIZE; 
    cir[i].n=1;cir[i].arc[0].a=0;cir[i].arc[0].b=2*pi;
     }
    
    for(i=0;i<n;i++)
    {key=0;
    
    for(j=0;j<i;j++)
    key+=doit(cir[j],cir[i]);    
/*    
    for(k=0;k<=i;k++)
    {cout<<k+1<<" :";
    for(h=0;h<cir[k].n;h++)cout<<cir[k].arc[h].a/pi*180
        <<'&'<<cir[k].arc[h].b/pi*180<<' ';
    cout<<endl;
    }
*/                
//    cout<<key<<endl;    
/*
    k=0;
    for(j=0;j<cir[i].n;j++)
        if(cir[i].arc[j].b-cir[i].arc[j].a>=eps)break;
    if(j<cir[i].n)k=1;
*/        
    if(key||cir[i].n)answer++;
    }
    cout<<answer<<endl;
       }
return 0;
}
							

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

/* @author: */
import java.util.*;
 public class Main {  
 private int target;
 private char num[];
 private int max;
 private StringBuffer s;
 private StringBuffer result;
 boolean check;

public Main(int target,char num[]){
    this.target=target;
    this.num=num;
    max=0;
     s=new StringBuffer("");
     result=new StringBuffer("");
}

public boolean getCheck(){
    return check;
}

public int getMax(){
   return max;
}

public String getResult(){
   return result.toString();
}

private boolean isOk(){
  int sum=0;
 for(int i=0;i< num.length;i++){
    sum+=num[i]-'0';
  } 
   if(sum>target) return false;
   else return true;
}

void  dfs(int startIndex,int sumTotal){
  int i,t=0;
  if(startIndex==num.length)
  {
    if(sumTotal==max){
        check=false;
     }else if(sumTotal>max){
        check=true;
        max=sumTotal;
        result=s;
      }
   }
  for(i=1;i< num.length-startIndex+1;i++){
     t*=10;
    t+=num[startIndex+i-1]-'0';
    if(t+sumTotal>target)
     return;
    StringBuffer tt=new StringBuffer(s);
    s.append(Integer.toString(t)).append(" ");

    dfs(startIndex+i,sumTotal+t);
    s=tt;
  }
}

public static void main(String args[]){
 Scanner sc=new Scanner(System.in);
  while(sc.hasNext())
  {
  
   int target=sc.nextInt();
   char num[]=sc.next().toCharArray();
    if(target==0)
      break;
    Main m=new Main(target,num);
    if(!m.isOk())
       System.out.printf("errorn");
    else{
      m.dfs(0,0);
     if(!m.getCheck())
         System.out.printf("rejectedn");
     else{
       System.out.print(m.getMax()+" ");
       System.out.println(m.getResult());
     }

     }
      
  }
 }
}

							

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


import java.util.*;

/**
 *
 * @author leo
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static boolean prime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int m, a, b;
        m = scan.nextInt();
        a = scan.nextInt();
        b = scan.nextInt();
        while (true) {
            if (a == 0 && b == 0 && m == 0) {
                break;
            }
            boolean flag = false;
            while (m > 0) {
                int t = (int) Math.sqrt((double) (m * a / b));
                if (t * t != m) {
                    t++;
                }
                int tmp = (int) Math.sqrt((double) m);
                for (int i = t; i <= tmp; i++) {
                    if (m % i == 0 && prime(i) && prime(m / i)) {
                        flag = true;
                        System.out.println(i + " " + m / i);
                        break;
                    }
                }
                if (flag) {

                    break;
                }
                m--;

            }

            m = scan.nextInt();
            a = scan.nextInt();
            b = scan.nextInt();
        }
        // TODO code application logic here
    }
}

							

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n=scanner.nextInt();
        double dx1,dx2,dy1,dy2;
        double x1,x2,y1,y2;
        double k,b;
        double d1,d2,d3,d4;
        for (int i=0;i<n ;i++ ){
            x1=scanner.nextDouble();
            y1=scanner.nextDouble();
            x2=scanner.nextDouble();
            y2=scanner.nextDouble();
            dx1=scanner.nextDouble();
            dy1=scanner.nextDouble();
            dx2=scanner.nextDouble();
            dy2=scanner.nextDouble();
            if (dx1>dx2){
                double tx=dx1;
                dx1=dx2;
                dx2=tx;
            }
            if (dy1>dy2){
                double ty=dy1;
                dy1=dy2;
                dy2=ty;
            }
            if ((x1< dx1&&x2< dx1)||(x1>dx2&&x2>dx2)){
                System.out.println("F");
            }
            else if ((y1< dy1&&y2< dy1)||(y1>dy2&&y2>dy2)){
                System.out.println("F");
            }
            else{
                if (x1==x2){
                    System.out.println("T");
                }
                else{
            k=(y2-y1)/(x2-x1);
            b=y1-k*x1;
            d1=dy1-k*dx1-b;
            d2=dy2-k*dx2-b;
                 d3=dy1-k*dx2-b;
            d4=dy2-k*dx1-b;
            if ((d1>0&&d2>0&&d3>0&&d4>0)||(d1<0&&d2<0&&d3<0&&d4<0)){
                System.out.println("F");
            }
            else{
                System.out.println("T");
            }
        }
    }
     }
   }
}

							

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

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

public class Main {
  static double[][][] mesh=new double[32][32][2];
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new
                InputStreamReader(System.in));
   String s;
   String[] ss;
   int n,i,j;
   double max=0d,t;
   while((s=br.readLine())!=null&&!"0".equals(s)){
          n=parseInt(s);
          s=br.readLine();
          ss=s.split(" ",n);
          for(i=1;i<=n;i++){
              mesh[n+1][i][0] = Double.parseDouble(ss[i-1]);
          }
          s=br.readLine();
          ss=s.split(" ",n);
          for(i=1;i<=n;i++){
              mesh[0][i][0] = Double.parseDouble(ss[i-1]);
              mesh[0][i][1] = 1d;
          }
          s=br.readLine();
          ss=s.split(" ",n);
          for(i=0;i< n;i++){
              mesh[n-i][0][1] = Double.parseDouble(ss[i]);
          }
          s=br.readLine();
          ss=s.split(" ",n);
          for(i=0;i< n;i++){
            mesh[n-i][n+1][0] = 1d;
              mesh[n-i][n+1][1] = Double.parseDouble(ss[i]);
          }
          mesh[0][0][1]=
          mesh[0][n+1][0]=mesh[0][n+1][1]=
          mesh[n+1][n+1][0]=1d;
            
          for(i=1;i<=n;i++){
         for(j=1;j<=n;j++){
              setPoint(mesh[n+1][j][0],mesh[0][j][0],mesh[i][0][1],mesh[i][n+1][1],i,j);
         }
      }
          for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
          t=getSquare(mesh[i][j],mesh[i][j+1],mesh[i+1][j+1],mesh[i+1][j]);
          if(t>max)
            max=t;
        }
       }
       System.out.printf("%.6fn",max);
       max=0d;
       reset(n+2);
    }
   }

   static void print(int n) {
    for(int i=0;i< n;i++){
        for(int j=0;j< n;j++){
       System.out.print("["+mesh[i][j][0]+","+mesh[i][j][1]+"]");
      }
     System.out.println();
    }
    }

   static void setPoint(double a,double b,double c,double d,int x,int y){
    double t=1-(a-b)*(c-d);
    mesh[x][y][0]=(a-(a-b)*c)/t;
    mesh[x][y][1]=(c-a*(c-d))/t;
   }

   static double getSquare(double[] a,double[] b,double[] c,double[] d){
    double t=Math.abs((a[0]-b[0])*(c[1]-b[1])-(a[1]-b[1])*(c[0]-b[0]));
    t+=Math.abs((a[0]-d[0])*(c[1]-d[1])-(a[1]-d[1])*(c[0]-d[0]));
    return t/2;
   }

   static void reset(int limit){
    for(int i=0;i< limit;i++){
         for(int j=0;j< limit;j++){
       mesh[i][j][0]=mesh[i][j][1]=0d;
      }
    }
    }

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

							

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


import java.util.*;

/**
 *
 * @author leo
 */
public class Main {

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

        Scanner scan = new Scanner(System.in);
        int total, left;
        while (true) {
            total = scan.nextInt();
            if (total == 0) {
                break;
            }
            left = total;
            int temp = 0;
            for (int i = 0;; i++) {
                temp = i * i * i;
                if (temp == total) {
                    left = 0;
                    break;
                }
                if (temp > total) {
                    break;
                }
                if (left > (total - temp)) {
                    left = total - temp;
                    if (left == 0) {
                        break;
                    }
                }
                int ttemp = 0;
                boolean flag = false;
                for (int j = 1;; j++) {
                    ttemp = j * (j + 1) * (j + 2) / 6 + temp;
                    if (ttemp == total) {
                        left = 0;
                        flag = true;
                        break;
                    }
                    if (ttemp > total) {
                        break;
                    }
                    if (left > (total - ttemp)) {
                        left = total - ttemp;
                        if (left == 0) {
                            flag = true;
                            break;
                        }
                    }

                }
                if (flag) {
                    break;
                }
            }
            System.out.println(total - left);
        }

        // TODO code application logic here
    }
}

							

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

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.ArrayList;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            ArrayList<BigDecimal> results = new ArrayList(18);   
            results.add(0, new BigDecimal(2));   
            for (int i = 1; i < 18; i++) {   
                BigDecimal last = results.get(i - 1);   
                BigDecimal temp = (last.add(BigDecimal.ONE.negate())).multiply(last).add(BigDecimal.ONE);   
                results.add(i, temp);   
            }   
            for (int i = 1; i <= n; i++) {   
                System.out.println(results.get(i - 1));   
            }   
        }   
    }   
}  


							

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

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

int K,L;
char key[]=new char[100];
char letter[]=new char[100];
int F[]=new int[100];
int p[]=new int[100];
int best;
int map[][][]=new int[100][100][100];
int father[][]=new int[100][100];
int q[]=new int[100];

int t,c;
int i,j,m,n;
int limitA,limitB;
char str[]=new char[100];
t=in.nextInt();
c=0;
while(c< t)
{
  c++;
  K=in.nextInt();
  L=in.nextInt();
  str=in.next().toCharArray();
  for(i=1;i<=K;i++) key[i]=str[i-1];
  str=in.next().toCharArray();

  for(i=1;i<=L;i++) letter[i]=str[i-1];
  for(i=1;i<=L;i++) F[i]=in.nextInt();
  for(i=1;i<=K;i++)
  {
    for(j=1;j<=L;j++)
    {
         for(m=1;m<=j;m++)
      {
       map[i][j][m]=-1;
       }
     }
    }
   limitA=L-K+1;
   map[1][1][1]=F[1];
   for(i=2;i<=L;i++)
   {
    for(j=2;j<=i && j<=K;j++)
    {
          limitB=i-j+1;
       for(m=1;m<=limitA && m<=limitB;m++)
       {
        if(map[j-1][i-1][m]>=0)
        {
            if(map[j][i][1]< 0 || map[j][i][1]>=map[j-1][i-1][m]+F[i])
         {
          map[j][i][1]=map[j-1][i-1][m]+F[i];
          father[j][i]=m;
          }
        }
        }
     }
     for(j=1;j<=i && j<=K;j++)
     {
      limitB=i-j+1;
      for(m=2;m<=limitA && m<=limitB;m++)
      {
        if(map[j][i-1][m-1]>=0)
        {
        map[j][i][m]=m*F[i]+map[j][i-1][m-1];
        }

       }
      }
     }
     best=1000000000;
     for(i=1;i<=L;i++)
     {
     if(map[K][L][i]>=0 && map[K][L][i]<=best)
     {
       j=K;m=L;n=i;
       while(m>=1)
       {
        q[j]=1;
        while(n>1)
        {
             n--;m--;
          q[j]++;
        }
        n=father[j][m];
        m--;
        j--;
        }
        best=map[K][L][i];
        for(j=1;j<=K;j++)p[j]=q[j];
       }
        }
      m=0;
     System.out.printf("Keypad #%d:n",c);
     for(i=1;i<=K;i++)
     {
       System.out.printf("%c: ",key[i]);
       n=p[i];
       while(n-->0)
       {
        m++;
        System.out.printf("%c",letter[m]);
        }
       System.out.printf("n");
    }
    System.out.printf("n");
    }
  }
}

							

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

#include <iostream>
 
using namespace std;
 
int calc(int z)
{
    int i, count = 0;
    for (i = 5; i <= z; i *= 5)
    {
        count += z / i;
    }
    return count;
}
 
int main()
{
    int n, z;
    cin >> n;
    while (n--)
    {
        cin >> z;
        cout << calc(z) << endl;
    }
    //system("pause");
    return 0;
}
							

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

#include<iostream>
#include"memory.h"
#include"algorithm"
using std::sort;
using namespace std;
int x[2010],y[2010];
int n,index_y[2010],index_x[2010],to_y[2010];
int tree[2048*2],cover[2048*2];

int cmp_x(int a,int b)
{return x[a]<x[b];}
int cmp_y(int a,int b)
{return y[a]<y[b];}

int init()
{int i;

for(i=0;;i++)
{cin>>x[2*i]>>y[2*i]>>x[2*i+1]>>y[2*i+1];
if(x[2*i]==-1)break;
index_x[2*i]=2*i;index_x[2*i+1]=2*i+1;
index_y[2*i]=2*i;index_y[2*i+1]=2*i+1;
}
n=i;
if(n==0)return 0;

sort(&index_x[0],&index_x[2*n],cmp_x);
sort(&index_y[0],&index_y[2*n],cmp_y);

for(i=0;i<2*n;i++){to_y[index_y[i]]=i;}

memset(tree,0,2048*sizeof(int));
memset(cover,0,2048*sizeof(int));

return 1;
}

int a,b,key;

void insert(int root,int begin,int end)
{if(begin==end||b<=begin||end<=a)return;
 
if(a<=begin&&end<=b){
        if(key==0){tree[root]++;cover[root]=y[index_y[end]]-y[index_y[begin]];}
        else {tree[root]--;
                if(tree[root]==0){if(root*2+1<2048*2)cover[root]=cover[root*2+1]+cover[root*2+2];
                                else cover[root]=0;}
            }
            return;}

insert(root*2+1,begin,(begin+end)/2);
insert(root*2+2,(begin+end)/2,end);

if(tree[root]==0)cover[root]=cover[root*2+1]+cover[root*2+2];

}

void doit()
{int i;
long s=0;

for(i=0;i<2*n;i++)
{key=index_x[i]%2;
if(i)s+=cover[0]*(x[index_x[i]]-x[index_x[i-1]]);
a=to_y[index_y[to_y[index_x[i]]]-key];
b=to_y[index_y[to_y[index_x[i]]]-key+1];
insert(0,0,n*2-1);
}

cout<<s<<endl;
}

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

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] arr=new int[26];
 static int[] cin=new int[26];
 static int[] cout=new int[26];
 static boolean[] used=new boolean[26];

public static void main(String[] args) throws NumberFormatException, IOException
{
 InputStreamReader is=new InputStreamReader(System.in);
 BufferedReader in=new BufferedReader(is);
 int y=Integer.parseInt(in.readLine());
 while((y--)!=0)
 {
    int n=Integer.parseInt(in.readLine());
    for(int i=0;i< 26;i++){
        arr[i]=i;
        cin[i]=0;
        cout[i]=0;
        used[i]=false;
    }
    for(int i=0;i< n;i++)
    {
        String s=in.readLine();
        int u=s.charAt(0)-'a';
        int v=s.charAt(s.length()-1)-'a';
        cin[u]++;
        cout[v]++;
        used[u]=true;
        used[v]=true;
        union(u,v);
    }
    boolean euler=true;
    int one=0,none=0;
    for(int i=0;i< 26;i++)
    {
        if(!used[i])continue;
        if(Math.abs(cin[i]-cout[i])>1){
            euler=false;
            break;
        }
        if(cin[i]-cout[i]==1)
        {
            one++;
            if(one>1)
            {
                euler=false;
                break;
            }
        }
        if(cout[i]-cin[i]==1)
        {
            none++;
            if(none>1)
            {
                euler=false;
                break;
            }
        }
    }
    if(one!=none)euler=false;
    int yy=-1;
    for(int i=0;i< 26;i++)
    {
        if(!used[i]) continue;
        if(yy==-1) yy=root(i);
        else if(yy!=root(i))
        {
            euler=false;
            break;
        }
    }
    if(!euler)System.out.println("The door cannot be opened.");
    else System.out.println("Ordering is possible.");
  }
 }

 static int root(int a)
 {
    int b=a;
    while(arr[b]!=b)
        b=arr[b];
    return arr[a]=b;
  }

static void union(int a,int b)
 {
    int x=root(a);
    int y=root(b);
    if(x==y)return;
    if(x>y)arr[x]=y;
    else arr[y]=x;
 }
}

							

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

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

double x,y,x1,y1,xb,yb;
double area,x_sum,y_sum,temp;

int main()
{
    int t,n,i;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>x1>>y1;
        
        xb=x1,yb=y1;

        area=x_sum=y_sum=0;
        for(i=1;i<=n;i++)
        {
            if(i<n)cin>>x>>y;
            else x=xb,y=yb;

            temp=x*y1-y*x1;
            x_sum+=temp*(x+x1);
            y_sum+=temp*(y+y1);
            area+=temp;
            x1=x,y1=y;
        }

        printf("%.2lf %.2lfn",(double)((long)(x_sum/area/3*100))/100,(double)(long)(y_sum/area/3*100)/100);
    }
    return 0;
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Coin{
    int price,weight;
}
public class Main {
 static final int N = 500+10,M = 10000+10;
 static int DP[] = new int[M],n,m;
 static Coin coin[] =new Coin[N];
 static void start(){
    for(int i=0;i< N;++i){
        coin[i] =new Coin();
    }
}

 public static void main(String[]args) throws Exception{
  int t,i,j;
  start();
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   t = Get_Num(cin);
   while(t--!=0){
    i = Get_Num(cin);
    j = Get_Num(cin);
    m = j-i;
    n = Get_Num(cin);
    for(i=0;i< n;++i){
        coin[i].price = Get_Num(cin);
        coin[i].weight = Get_Num(cin);
    }
    solve();
    if(DP[m]==-1) System.out.println("This is impossible.");
       else System.out.println("The minimum amount of money in the piggy-bank is "+DP[m]+".");
    }
  }

 static int Get_Num(StreamTokenizer cin)throws Exception{
    cin.nextToken();
    return (int) cin.nval;
}
static void solve(){
  int i,j;
  for(i=0;i<=m;++i) DP[i] = -1;
   DP[0] = 0;
   for(i=0;i< n;++i){
    for(j=0;j<=m;++j) if(DP[j]>-1 && j+coin[i].weight<=m){
      DP[j+coin[i].weight] = Min(DP[j+coin[i].weight],DP[j]+coin[i].price);
    }
   }
}

  static int Min(int a,int b){
   if(a==-1) return b;
   return a< b?a:b;
  }
}

							

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

#include"stdio.h"
#include"memory.h"


char map[1100][1100];
bool sign[1100][1100];
int max,bx,by,n,m;

void init_sign()
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        sign[i][j]=0;
}

void init()
{
    scanf("%d %d",&m,&n);
    for(int i=0;i<n;i++)
        scanf("%s",map[i]);
}
inline int inmap(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<m;
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

void search(int x,int y,int floor)
{
    int xx,yy;
    sign[x][y]=1;

    if(floor>max)
    {
        max=floor;
        bx=x,by=y;
    }

    for(int i=0;i<4;i++)
    {
        if(inmap(xx=x+dx[i],yy=y+dy[i])&&!sign[xx][yy]&&map[xx][yy]=='.')
            search(xx,yy,floor+1);
    }
}

void doit()
{
    int x,y;
    for(x=0;x<n;x++)
    for(y=0;y<m;y++)
        if(map[x][y]=='.')goto loop;

    max=0;
    return;
loop:
    max=-1;
    init_sign();
    search(x,y,0);

    max=-1;
    init_sign();
    search(bx,by,0);
    return;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        doit();
        printf("Maximum rope length is %d.n",max);
    }
    return 0;
}
							

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

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

using namespace std;

int x[200], y[200], xn, yn, n, m;

struct
{
    int x1, x2, y1, y2;
}ln[100];

char map[414][414];

bool init()
{
    int i, j, l, r, u, d, k;

    cin >> n;
    if( n == 0 ) return 0;

    xn = yn = 0;
    for( i=0; i<n; i++ )
    {
        cin >> ln[i].x1 >> ln[i].y1 >> ln[i].x2 >> ln[i].y2;

        x[ xn++ ] = ln[i].x1;    x[ xn++ ] = ln[i].x2;
        y[ yn++ ] = ln[i].y1;    y[ yn++ ] = ln[i].y2;
    }

    sort( x, x+xn );
    sort( y, y+yn );

    xn = std::unique_copy( x, x+xn, x ) - x;
    yn = std::unique_copy( y, y+yn, y ) - y;

    m = n * 4 + 4;

    for( i=0; i<m; i++ )
    for( j=0; j<m; j++ )
        map[i][j] = ' ';

    for( i=0; i<n; i++ )
    {
        l = 2 + ( std::lower_bound( x, x+xn, ln[i].x1 ) - x ) * 2;
        r = 2 + ( std::lower_bound( x, x+xn, ln[i].x2 ) - x ) * 2;
        u = 2 + ( std::lower_bound( y, y+yn, ln[i].y1 ) - y ) * 2;
        d = 2 + ( std::lower_bound( y, y+yn, ln[i].y2 ) - y ) * 2;

        if( l > r ) swap( l, r );
        if( u > d ) swap( u, d );

        for( j=l ; j <= r; j++ )
        for( k=u ; k <= d; k++ )
        {
            map[j][k] = '#';
        }
    }

    return 1;
}

int dx[]={ 0, 0, 1, -1 }, dy[]={ 1, -1, 0, 0 };

inline bool inmap( int x, int y )
{
    return 0 <= x && x < m && 0 <= y && y < m;
}

void fill( int x, int y, char wall, char past )
{
    int i, xx, yy;

    map[x][y] = past;
    for( i=0; i<4; i++ )
    if( inmap( xx=x+2*dx[i], yy=y+2*dy[i] ) && map[x+dx[i]][y+dy[i]] != wall && map[xx][yy] == ' ' )
        fill( xx, yy, wall, past );
}

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

    fill( 1, 1, '#', '*' );

    ans = 0;
    for( i=1; i<m; i+=2 )
    for( j=1; j<m; j+=2 )
    if( map[i][j] == ' ' )
    {
        fill( i, j, '*', 'o' );
        ans ++ ;
    }

    cout<< ans << endl;
}

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

    return 0;
}


							

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

#include<iostream>
#include"memory.h"
using namespace std;
int set[3][3][3][3];
int map[7][7][4];
int n,m;

int div(char c)
{switch(c)
{case 'O':return 0;
 case 'F':return 1;
 case 'I':return 2;
 default:return -1;
}
}


void init()
{int i,j,a[4];char c;
memset(set,0,81*sizeof(int));

for(i=0;i<n*m;i++)
{for(j=0;j<4;j++)
 {cin>>c;a[j]=div(c);}
  set[a[0]][a[1]][a[2]][a[3]]++;
}
for(i=0;i<=n;i++)map[i][0][1]=1;
for(i=0;i<=m;i++)map[0][i][2]=1;
}


int find(int a,int b)
{int u,l,d,r;
u=2-map[a-1][b][2];
l=2-map[a][b-1][1];

if(a==n){if(b==m)return set[u][1][1][l]==1;
    d=1;
    for(r=0;r<3;r+=2)
    if(set[u][r][d][l]){
        set[u][r][d][l]--;
            map[a][b][1]=r;
           if(find(a,b+1))return 1;
            set[u][r][d][l]++;
                }
    return 0;
    }
else {if(b==m){for(d=0;d<3;d+=2)
           if(set[u][1][d][l]){
               set[u][1][d][l]--;
                   map[a][b][2]=d;
                   if(find(a+1,1))return 1;
                      set[u][1][d][l]++;
                                }
        return 0;
        }
    for(r=0;r<3;r+=2)
    for(d=0;d<3;d+=2)
    if(set[u][r][d][l]){
        set[u][r][d][l]--;
            map[a][b][1]=r;
        map[a][b][2]=d;
        if(find(a,b+1))return 1;
        set[u][r][d][l]++;
                }
    return 0;
    }
}                                                                  
int main()
{while(1)
    {cin>>n>>m;
    if(n==0&&m==0)break;
        init();
    if(find(1,1))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }
return 0;
}