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

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

public class Main
{
    public static BufferedInputStream bis;
    public static StringBuilder str;
    public static char[][] rules;
    public static StringBuilder[] words;
    public static int k;
    public static void main(String[] args) throws Exception
    {
        bis = new BufferedInputStream(System.in);
        
    rules = new char[8][4];
    Map< String,Boolean> exist = new HashMap< String,Boolean>();
    words = new StringBuilder[40000];
    StringBuilder start,result, previous, key;
        str = new StringBuilder();
        start = new StringBuilder();
    result = new StringBuilder();
    previous = new StringBuilder();
        key = new StringBuilder();
        for(int i = 0; i < 40000; i++)
        {
            words[i] = new StringBuilder();
        }
    while(true)
    {
        int n = (int)readLong();
            if(n == -1)
            {
                break;
            }
            k = 0;
            start.delete(0,start.length());
        start.append(readString());
            readRules();
        long s = readLong();
            result.delete(0,result.length());
        result.append(start);
        exist.clear();

            words[k].delete(0,words[k].length());
            words[k].append(lowest(result));
            k++;
        for(int j=0;j< s;j++)
        {
                previous.delete(0,previous.length());
        previous.append(result);
        result.delete(0,result.length());
            for(int i=0;i< n;i++)
            {
                int i1 = (i-2+n)%n;
            int i2 = i;
            int i3 = (i+1)%n;
                    key.delete(0,key.length());
            key.append(previous.charAt(i1));
            key.append(previous.charAt(i2));
            key.append(previous.charAt(i3));
            result.append(getKey(key));
            }
        String lw = lowest(result);
                
        if(exist.get(lw) == null)
        {
            exist.put(lw,true);
            words[k].delete(0,words[k].length());
                    words[k].append(lw);
                    k++;
        }else
        {
            int index = find(lw);
            int p = j + 1 - index;
            long resultIndex = ((s - j) % p - 1 + p)%p  + index;
                    result.delete(0,result.length());
                    result.append(words[(int)resultIndex]);
            break;
        }
        }

        System.out.println(lowest(result));
    }
    }
    
    public static int find(String lw)
    {
        int index = 0;
        for(int i = 0; i < k; i++)
        {
            boolean reached = true;
            for(int j = 0; j < lw.length(); j++)
            {
                if(lw.charAt(j) != words[i].charAt(j))
                {
                    reached = false;
                    break;
                }
            }
            if(reached)
            {
                index = i;
                break;
            }
        }
        return index;
    }
    
    public static char getKey(StringBuilder sb)
    {
        char result = '';
        for(int i = 0; i < 8; i++)
        {
            boolean reached = true;
            for(int j = 0; j < 3; j++)
            {
                if(rules[i][j] != sb.charAt(j))
                {
                    reached = false;
                    break;
                }
            }
            if(reached)
            {
                result = rules[i][3];
                break;
            }
        }
        return result;
    }
    
    public static void readRules() throws Exception
    {
        for(int i = 0; i < 8; i++)
    {
            for(int j = 0; j < 4; j++)
            {
                while(true)
                {
                    int bt = bis.read();
                    if(Character.isLetter(bt))
                    {
                        rules[i][j] = (char)bt;
                        break;
                    }
                }
            }
    }
    }
    
    static String lowest(StringBuilder sb)
    {
        String p = sb.toString();
    String min = p;
    int n = p.length();
    for(int i=0;i< n;i++)
    {
        String next = p.substring(n-1,n) + p.substring(0,n-1);
        if(next.compareTo(min) < 0)
        {
            min = next;
        }
        p = next;
    }
    return min;
    }
    
    public static long readLong() throws Exception
    {
        long num = 0;
        while(true)
        {
            int bt = bis.read();
            if(bt == -1)
            {
                return -1;
            }
            if(Character.isDigit(bt))
            {
                num = num*10 + bt - '0';
                break;
            }
        }
        
        while(true)
        {
            int bt = bis.read();
            if(!Character.isDigit(bt))
            {
                break;
            }
            num = num*10 + bt - '0';
        }
        return num;
    }
    
    public static StringBuilder readString() throws Exception
    {
        str.delete(0,str.length());
        while(true)
        {
            int bt = bis.read();
            if(Character.isLetter(bt))
            {
                str.append((char)bt);
                break;
            }
        }
        
        while(true)
        {
            int bt = bis.read();
            if(!Character.isLetter(bt))
            {
                break;
            }
            str.append((char)bt);
        }
        
        return str;
    }
}

							

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

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

public class Main {

    /**
     * @param args
     */
    static int pp;
    static int[] p = new int[30000];
    static int[] w = new int[30000];
    static boolean[] q = new boolean[35000];

    static void init() {
        int i;
        for (i = 2; i * i < 35000; i++) {
            if (q[i])
                continue;
            p[pp++] = i;
            for (int j = i * i; j < 35000; j += i)
                q[j] = true;
        }
        for (; i < 32768; i++)
            if (!q[i])
                p[pp++] = i;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        Scanner in = new Scanner(System.in);
        String s;
        while (true) {
            s = in.nextLine();
            if (s.equals("0"))
                break;
            StringTokenizer aa = new StringTokenizer(s);
            BigInteger k = BigInteger.ONE;
            int a1, a2;
            while (aa.hasMoreTokens()) {
                a1 = Integer.parseInt(aa.nextToken());
                a2 = Integer.parseInt(aa.nextToken());
                for (int i = 0; i < a2; i++)
                    k = k.multiply(BigInteger.valueOf(a1));
            }
            k=k.subtract(BigInteger.ONE);
            for (int i = pp - 1; i >= 0; --i) {
                w[i] = 0;
                while (k.mod(BigInteger.valueOf(p[i])).equals(BigInteger.ZERO)) {
                    w[i]++;
                    k = k.divide(BigInteger.valueOf(p[i]));
                }
                if (w[i] > 0)
                    if (k.equals(BigInteger.ONE)) {
                        System.out.println(p[i] + " " + w[i]);
                        break;
                    } else
                        System.out.print(p[i] + " " + w[i] + " ");
            }
        }
    }

}


							

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

import java.util.*;
public class Main {
 
 public static void main(String[] args){

    Scanner sc = new Scanner(System.in);
    int in[]=new int[1001];   
    int out[]=new int[1001];   
    int stack[]=new int[1001];   

    int n;   
    int i,j;   
    for(i=0;i< 1001;i++)   
        in[i]=i+1;   
    while(sc.hasNext())   
    {   
         n=sc.nextInt();
         if(n==0) break;  
        while(true)   
        {   
            out[0]=sc.nextInt();
            if(out[0]==0)   
                break;   
            for(i=1;i< n;i++)   
                out[i]=sc.nextInt();   
            i=j=0;   
            int top=-1;   
            while(i< n)   
            {   
                top++;   
                stack[top]=in[i];   
                i++;   
                while(stack[top]==out[j])   
                {   
                    top--;   
                    j++;   
                    if(top==-1)break;   
                }   
            }   
            if(top==-1)   
                System.out.printf("Yesn");   
            else  
                System.out.printf("Non");   
        }   
        System.out.printf("n");   
    }   
   }
} 


							

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

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

public class Main
{
    public static final int max = 30;
    public static void main(String[] args)
    {
        int[] weights = new int[max];
    int p = 2;
    for(int i = 0; i < max; i++)
    {
        weights[i] = p - 1;
        p *= 2;
        //System.out.println(weights[i]);
    }
    
    Scanner sc = new Scanner(System.in);
    int tc = sc.nextInt();
    for(int i = 0; i < tc; i++)
    {
        int[] digits = new int[max];
        int num = sc.nextInt();
        int out = num;
        for(int j = max - 1; j >= 0; j--)
        {
            if(num == 0)
        {
            break;
        }

            if(num < weights[j])
        {
            continue;
        }else if(num == 2 * weights[j])
        {
            digits[j] = 2;
            num -= 2*weights[j];
        }else
        {
            digits[j] = 1;
            num -= weights[j];
        }
        }
        boolean bg = true;
        System.out.print(out + " [");
        for(int j = 0; j < max; j++)
        {
            if(digits[j] != 0)
        {
            if(!bg)
            {
                System.out.print(",");
            }else
            {
                bg = false;
            }
            if(digits[j] == 1)
            {
                System.out.print(j);
            }else
            {
                System.out.print(j + "," +j);
            }
        }
        }
        System.out.println("]");
    }
    }
}

							

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

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            if (n == -1) {   
                break;   
            }   
            BigDecimal nn = new BigDecimal(n);   
            BigDecimal sum = BigDecimal.ONE;   
            for (BigDecimal i = BigDecimal.ONE; i.compareTo(nn) == -1; i = i.add(BigDecimal.ONE)) {   
                sum = sum.multiply(i);   
            }   
            System.out.println("N=" + n + ":");   
            System.out.println(sum.multiply(new BigDecimal(2)));   
        }   
    }   
}  


							

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

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

public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    int a[]=new int[200],b[]=new int[200];
    int n,m,k;
    while(sc.hasNext()) {
        String s=sc.nextLine();
        Scanner scan=new Scanner(s);
        scan.useDelimiter(",");
        n=scan.nextInt();
        if(n==-1) break;
        m=scan.nextInt();

        k=scan.nextInt();
        for (int i=1;i<=n;i++) {
            if (i<=m) a[i]=-1;
            else a[i]=1;
        }
        for (int j=1;j<=k;j++) {
            a[n+1]=a[1];
            for (int i=1;i<=n;i++) b[i]=a[i]*a[i+1];
            for (int i=1;i<=n;i++) a[i]=b[i];
        }
        int ans=0;
        for (int i=1;i<=n;i++) if (a[i]==-1) ans++;
        System.out.printf("%d,%d,%d: %dn",n,m,k,ans);
    }
  }
}
							

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

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

public class Main{
 static Scanner cin;
 static long[] f,g;
    
 public static void main(String args[]){
  cin = new Scanner(System.in);
  f = new long[17];
  g = new long[17];
        
  g[1]=4;
  g[2]=14;
  for(int i=3;i< 17;i++)
    g[i]=3*g[i-1]+2*g[i-2];
        
  for(int i=2;i< 17;i++)
    f[i] = (1<< (2*i))-(1<< i)-g[i]+2;
            
  while(run()==true)
            ;
 }
    
 static boolean run(){
   int n = cin.nextInt();
   if(n==-1)
    return false;
   if(n==16){
     System.out.println(16+": 3553389280");
     return true;
    }
            
   System.out.println(n+": "+f[n]);
   return true;
    
  }
}
							

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

//* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot;
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    while(true)
    {
        String num = sc.next();
        if(num.equals("-1"))
        {
            break;
        }
        System.out.println("N="+num+":");
        if(num.length()!=4||(num.charAt(0)==num.charAt(1)&&
            num.charAt(1)==num.charAt(2)&& num.charAt(2)==num.charAt(3)))
        {
        System.out.println("No!!");
        }else
        {
            int count = 0;
            while(true)
        {
            char[] chs = new char[num.length()];
            for(int i = 0;i < num.length(); i++)
            {
                chs[i] = num.charAt(i);
            }
            Arrays.sort(chs);
            int small = Integer.parseInt(new String(chs));
            for(int i=0;i< chs.length/2;i++)
            {
                char temp = chs[i];
            chs[i] = chs[chs.length-1-i];
            chs[chs.length-1-i] = temp;
            }
            int big = Integer.parseInt(new String(chs));
            int diff = big - small;
            num = Integer.toString(diff);
            count++;
            System.out.println(big+"-"+small+"="+diff);
            if(diff==6174 || diff == 0)
            {
                System.out.println("Ok!! " + count  + " times");
            break;
            }
        }
        }
    }
    }
}

							

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

//* @author: 
import java.util.*;
public class Main {
  
 static int value[][]=new int[50][50];
 static int ans,n;

static void calc()
{
 int i, j, temp, k, s;
 for( k=0; k< n-2; k++ )
 {
   s = 10000000;
   for( i = k+1; i < n; i++ )
    for( j = i+1; j < n; j++ )
    {
    if( (temp = (value[i][k]+value[j][k]-value[i][j])/2 ) < s )
    s = temp;
     }

   for( i = k+1; i < n; i++ ){
    value[i][k] -= s;
       value[k][i] -= s;
   }
  ans += s;
  }
  ans += value[n-2][n-1];
}

 public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int i, j;
    
    while( in.hasNext())
    {
    n=in.nextInt();

    if( n == 0 ) break;
    for( i=0; i< n; i++ )
    {
         for( j=i+1; j< n; j++ )
      {
         value[i][j]=in.nextInt();
         value[j][i] = value[i][j];
       }

       value[i][i] = 0;
      }
     ans = 0;
    calc();
    System.out.printf( "%dn",ans );
    }
  }
}
        

							

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;
import java.util.Vector;
public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        Vector< Long> v=new Vector< Long>();
        v.add(new Long(1));
        int i=0,j=0,k=0;
        while(v.size()< 1500){
            v.add(Math.min(Math.min(v.get(i)*2, v.get(j)*3), v.get(k)*5));
           if(v.get(v.size()-1).equals(v.get(v.size()-2))){v.remove(v.size()-1);}
            if(v.get(i)*2==v.get(v.size()-1))i++;
            else if(v.get(j)*3==v.get(v.size()-1))j++;
            else k++;
        }
       int n=1;      
       while((n=scan.nextInt())!=0){
            System.out.println(v.get(n-1));
        }        
    }
}
							

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

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

 public static void main(String[] args){

    Scanner in = new Scanner(System.in);
    
   int ans[]=new int[300];
   int a[]=new int[100],d[]=new int[100],t[]=new int[100];

   int cas, i, j, n, temp;
   boolean key;
   cas=in.nextInt();

   while(( cas-- )!=0)
   {
    n=in.nextInt();
    for( i=0; i< n; i++ ){
      t[i]=in.nextInt();
      a[i]=in.nextInt();
      d[i]=in.nextInt();
    }
        
   for( i=0; i<=250; i++ )
     ans[i] = 0;

  for( i=249; i>=0; i-- )
  {
    key = true;ans[i] = 99999999;
    for( j=0; j< n; j++ )
    {
         if( a[j] <= i && i+t[j] <= d[j] && ( temp = ans[i+t[j]] + t[j] ) < ans[i] ){
        ans[i] = temp;
              key = false;
         }
    }
    if( key ) ans[i] = ans[i+1];
        
   }
   System.out.printf( "%dn", ans[0] );
  }
 }
}

							

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

//* @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)
 {
    String s1=in.next();
    String s2=in.next();
    String s3=in.next();
    int max=0;
    for(int i=0;i< s1.length();i++)
    {
        char c=s1.charAt(i);
        int u=c-48;
        if(max< u)max=u;
    }
    for(int i=0;i< s2.length();i++)
    {
        char c=s2.charAt(i);
        int u=c-48;
        if(max< u)max=u;
    }
    for(int i=0;i< s3.length();i++)
    {
        char c=s3.charAt(i);
        int u=c-48;
        if(max< u)max=u;
    }
    boolean b=true;
    for(int o=max+1;o< 17;o++)
    {
        int w1=Integer.parseInt(s1, o);
        int w2=Integer.parseInt(s2, o);
        int w3=Integer.parseInt(s3, o);
        if(w1*w2==w3)
        {
            System.out.println(o);
            b=false;
            break;
        }
    }
    if(b)System.out.println(0);
  }
 }
}
							

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

import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
    int MAX = 10001;
    Vector< Integer> tree[] = new Vector[MAX + 1];; // 树结构
    byte[] flag = new byte[MAX]; // 入度标志，用于寻找根节点
    int parent[] = new int[MAX];;
    int rank[] = new int[MAX];;
    int ancestor[] = new int[MAX];
    int visited[] = new int[MAX];
    StringBuilder sb = new StringBuilder();
    byte ret;
    {
        for (int i = 1; i < MAX; i++)
            tree[i] = new Vector< Integer>();
    }

    public static void main(String[] args) {
        Main poj = new Main();
        java.util.Scanner s = new java.util.Scanner(System.in);
        int test = s.nextInt();
        int i = 0;
        while (++i <= test) {
            int length = s.nextInt();
            poj.initial(length);
            int a;
            int b;
            for (int j = 1; j < length; j++) {
                a = s.nextInt();
                b = s.nextInt();
                poj.flag[b] = -1;
                poj.tree[a].add(b);
            }
            int root;
            for (root = 1; root <= length; root++)
                if (poj.flag[root] != -1)
                    break;
            a = s.nextInt();
            b = s.nextInt();
            poj.LCA(root, a, b);
        }
        System.out.print(poj.sb.toString());
    }

    void initial(int n) {
        ret = 1;

        for (int i = 1; i <= n; i++) {
            flag[i] = 0;
            parent[i] = i;
            rank[i] = 0;
            ancestor[i] = 0;
            visited[i] = 0;
            tree[i].clear();

        }
    }

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

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

    void LCA(int u, int x, int y) {
        ancestor[u] = u;
        for (int i = 0; i < tree[u].size(); i++) {
            LCA(tree[u].get(i), x, y);
            if (ret == 0)
                return;
            union(u, tree[u].get(i));
            ancestor[find(u)] = u;
        }
        visited[u] = 1;

        if (u == x && visited[y] == 1 && ret == 1) {

            sb.append(ancestor[find(y)]);
            sb.append('n');
            ret = 0;
            return;
        }
        if (u == y && visited[x] == 1 && ret == 1) {
            {

                sb.append(ancestor[find(x)]);
                sb.append('n');
                ret = 0;
                return;
            }
        }
    }
}

							

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

import java.io.PrintWriter;  

 import java.util.Arrays;  
 import java.util.Scanner;  
 /**  
  *  
  * @author 小e  
  *  
  * 2010-6-12 下午01:48:35  
  */ 
 public class Main {  
  static class Range implements Comparable<Range>{  
   double left,right;  
   public Range(double left,double right){  
    this.left = left;  

   this.right = right;  
   }  
   @Override 

   public int compareTo(Range range) {  
    if(range.left == left){  
     return ((Double)right).compareTo((Double)(range.right));  
    }else{  
    return ((Double)left).compareTo((Double)(range.left));  
    }  
   }  

   @Override 
   public String toString() {  
    return "(" + left + "," + right + ")";  
   }  
  }  

     
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);    
   
   PrintWriter out = new PrintWriter(System.out);  
   int n ,d,x,y,num;  
   double dx;  
   Range[] ranges;  
   int index = 0;  
   while(true){  
    num = 0;  
    n = scn.nextInt();  
    d = scn.nextInt();  
    if(n == 0){  
     break;  
    }  
    ranges = new Range[n];  
    for(int i = 0; i < n; i++){  
     x = scn.nextInt();  
     y = scn.nextInt();  
     if(y > d){  
      num = -1;  
     }  
     dx = Math.sqrt(d*d - y*y);  
     ranges[i] = new Range(x - dx, x + dx);  
    }  
    Arrays.sort(ranges);//排序  
    if(num != -1){  
     num = calute(ranges);  
    }  
    out.format("Case %d: %dn",++index,num);  
   }  
   out.flush();  
      
  }  
    
  private static int calute(Range[] ranges) {  
   int num = 1;  
   int n = ranges.length;  
   Range preRange = ranges[0],range;  
   for(int i = 1; i < n; i++){  
    range = ranges[i];  
    //求区间交集  
    if(range.left >= preRange.left && range.left <= preRange.right){  
     preRange.left = range.left;  
     if(range.right < preRange.right){  
      preRange.right = range.right;  
     }  
    }else{  
     num++;  
     preRange = range;  
    }  
   }  
   return num;  
  }  
}

							

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

import java.util.*;   
import java.text.*;   
  
class FRecord   
{   
    String from;   
    String to;   
    int miles;   
    String type;   
       
    public FRecord(String a, String b, int c, String d)   
    {   
        this.from = a;   
        this.to = b;   
        this.miles = c;   
        this.type = d;   
    }   
       
}   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
        ArrayList record = new ArrayList();   
           
        while(true)   
        {   
            String tmp = cin.nextLine();   
               
            if(tmp.equals("#"))   
                break;   
            else if(tmp.equals("0"))   
            {   
                int total = getSummary(record);   
                record.clear();   
                System.out.println(total);   
            }   
            else  
            {   
                String[] str = tmp.split(" ");   
                FRecord fr = new FRecord(str[0], str[1],    
                        Integer.valueOf(str[2]).intValue(), str[3]);   
                record.add(fr);   
            }   
        }   
    }   
       
    private static int getSummary(ArrayList record)   
    {   
        int result = 0;   
           
        Iterator iter = record.iterator();   
        while(iter.hasNext())   
        {   
            FRecord fr = (FRecord)iter.next();   
            if(fr.type.equals("F"))   
            {   
                result += fr.miles * 2;   
                DecimalFormat df = new DecimalFormat("#");   
                result = Integer.valueOf(df.format(result)).intValue();   
            }   
            else if(fr.type.equals("B"))   
            {   
                result += fr.miles;   
                result += (fr.miles + 1)/2;   
                DecimalFormat df = new DecimalFormat("#");   
                result = Integer.valueOf(df.format(result)).intValue();   
            }   
                   
            else  
            {   
                if(fr.miles > 500)   
                {   
                    result += fr.miles;   
                    DecimalFormat df = new DecimalFormat("#");   
                    result = Integer.valueOf(df.format(result)).intValue();   
                }   
                       
                else  
                {   
                    result += 500;   
                    DecimalFormat df = new DecimalFormat("#");   
                    result = Integer.valueOf(df.format(result)).intValue();   
                }   
                       
            }   
        }   
           
        return result;   
    }   
  
}  

							

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

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define size 101
int g[size][size];      //ƥ��ͼ
int visited[size];      //x�����ʱ�־
int m,n;               //n:x������Ŀ��m:y����Ŀ
int My[size], Mx[size]; //ƥ����
int Q[size], prev[size];
int BFS_MaxMatch(void)
{
    int res = 0, i, u, v;
    int head, tail;
    bool flag;
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    memset(visited, -1, sizeof(visited));
    for(i = 0; i < n; i++)
    {
        if(Mx[i] == -1)
        {
            head = tail = 0;
            Q[tail++] = i;
            prev[i] = -1;
            flag = false;
            while(head < tail && !flag)
            {
                u = Q[head++];
                for(v = 0; v < m && !flag; v++)
                {
                    if (g[u][v] && visited[v] != i)
                    {
                        visited[v] = i;
                        Q[tail++] = My[v];
                        if(My[v] >= 0)
                        {
                            prev[My[v]] = u;
                        }
                        else
                        {
                            flag = 1;
                            int d = u, e = v;
                            while (d != -1)
                            {
                                int t = Mx[d];
                                Mx[d] = e;
                                My[e] = d;
                                d = prev[d];
                                e = t;
                            }
                        }
                    }
                }
            }
            if(Mx[i] != -1)    res++;
        }
    }
    return res;
}
int N,M,K;
int main()
{
    while((cin>>n && n != 0) && cin>>m>>K)
    {
        memset(g,0,sizeof(g));
        int task,m1,m2;
        for(int i = 0;i < K;i++)
        {
            scanf("%d%d%d",&task,&m1,&m2);
            if(m1 * m2 != 0)
                g[m1][m2] = 1;
        }
        cout<<BFS_MaxMatch()<<endl;
    }
    return 0;
}
/*
��С���㸲�ǣ��������ƥ�䣬������
Machine Schedule
Time Limit: 1000MS        Memory Limit: 10000K
Total Submissions: 4443        Accepted: 1845
Description

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ..., mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, ... , mode_m-1. At the beginning they are both work at mode_0.

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.

Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.
Output

The output should be one integer per line, which means the minimal times of restarting machine.
Sample Input

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output

3
Source

Beijing 2002
*/

							

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

#include<iostream>
#include<algorithm>
using namespace std;
const int mMax = 22;
const int nMax = 52;
 
struct data{
    int num;
    bool my;
    bool small;
}card[mMax * nMax];
 
int main(){
    int m , n, i, j, t = 1;
    while(cin >> m >> n && m != 0){
        for(i = 1; i <= m * n; i ++){
            card[i].num = i;
            card[i].my = false;
            card[i].small = false;
        }
        for(i = 1; i <= n; i ++){
            int number;
            cin >> number;
            card[number].my = true;
        }
        getchar();
        getchar();

        int ans = n;
        for(i = m * n; i >= 2 && ans > 0; i --)
            if(!card[i].my)
                for(j = i - 1; j >= 1; j --)
                    if(card[j].my && !card[j].small){
                        card[j].small = true;
                        ans --;
                        break;
                    }
        cout << "Case " << t++ << ": " << ans << endl;
    }
    return 0;
}
							

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

#include <iostream>
using namespace std;
int map[10][10];
int vis[10];
int n,k,ans;
void dfs(int col,int cnt)
{
int i;
if(cnt==k)
{
   ans++ ;
   return ;
}
if(n-col<k-cnt-1) return ;
for(i=1;i<=n;i++)
{
   if(!vis[i]&&map[col][i])
   {
    vis[i]=1;
    dfs(col+1,cnt+1);
    vis[i]=0;
   }
}
dfs(col+1,cnt);
}
int main()
{
int i,j;
char ch;
while(scanf("%d %d",&n,&k)!=EOF)
{
   if(n==-1&&k==-1) break;
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
     cin>>ch;
     if(ch=='.')      map[i][j]=0;
     else if(ch=='#') map[i][j]=1;
    }
   ans=0;
   memset(vis,0,sizeof(vis));
   dfs(1,0);
   printf("%dn",ans);
}
return 0;
}
							

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

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

public class Main{
 public static void main(String args[]){
   int[] array = new int[10];
   array[0]=6;
   array[1]=35;
        
   for(int i=2;i< 10;i++)
    array[i] = 6*array[i-1]-array[i-2];
            
   for(int i=0;i< 10;i++){
    //System.out.println("  "+array[i]+"   "+(Math.sqrt(8*array[i]*array[i]+1)-1)/2);
   }
        
   System.out.println("         "+6+"         "+8);
   System.out.println("        "+35+"        "+49);
   System.out.println("       "+204+"       "+288);
   System.out.println("      "+1189+"      "+1681);
   System.out.println("      "+6930+"      "+9800);
   System.out.println("     "+40391+"     "+57121);
   System.out.println("    "+235416+"    "+332928);
   System.out.println("   "+1372105+"   "+1940449);
   System.out.println("   "+7997214+"  "+11309768);
   System.out.println("  "+46611179+"  "+65918161);
  }
}
							

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

//* @author: 
import java.util.*;
public class Main {
  static final double l = Math.sqrt(3)/2;

  static int calc( double x, double y )
{
  int a[]=new int[2], s, i;
  double h;
  if( x < 1 )
    return 0;
  a[0] = (int)x;
  a[1] = (int)(x-0.5);
  for( i=0, h=1, s=0; h<=y; h+=l, i++ )
    s += a[i%2];
  return s;
}

 public static void main(String[] args){

   Scanner in = new Scanner(System.in);
   int s1, s2, t;    
   double x, y;
   while(in.hasNext())
   {
       x=in.nextDouble();
       y=in.nextDouble();
       s1 = (int)x * (int)y;
    s2 = calc( x, y );
    if( ( t = calc( y, x ) ) > s2 )
      s2 = t;
    if( s1 >= s2 )
         System.out.printf( "%d gridn", s1 );
    else
       System.out.printf( "%d skewn", s2 );
    }
  }
}


							

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

import java.util.*;

public class Main {

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   List< String> s1 = new ArrayList< String>();
   List< String> s2 = new ArrayList< String>();
   int indexS1 = 0;
   int indexS2 = 0;
   s1.add(cin.nextLine());
   while(s1.get(indexS1).charAt(0) != 'X') {
    indexS1++;
    s1.add(cin.nextLine());
   }
   s1.remove(indexS1);
   Collections.sort(s1);
  
   s2.add(cin.nextLine());
   while(s2.get(indexS2).charAt(0) != 'X') {
    indexS2++;
    s2.add(cin.nextLine());
   }
   s2.remove(indexS2);
  
   for(int i=0; i< s2.size(); i++) {
    boolean out = false;
    for(int j=0; j< s1.size(); j++) {
     if(isSame(s2.get(i), s1.get(j))) {
      System.out.println(s1.get(j));
      out = true;
     }
    }
    if(!out) {
     System.out.println("NOT A VALID WORD");
    }
     System.out.println("******");
   }
  
}

private static boolean isSame(String n1, String n2) {
   if(n1.length() != n2.length())
    return false;
   char[] first = n1.toCharArray();
   char[] secound = n2.toCharArray();
   Arrays.sort(first);
   Arrays.sort(secound);
   for(int i=0; i< first.length; i++) {
    if(first[i] != secound[i])
     return false;
   }
   return true;
}

}


							

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

#include <iostream>
#include <cstring>
using namespace std;


char ci[1000];
char pl[1000];

int main()
{
    int k,temp,t1;
    int i;
    int len;
    while(cin>>k && k)
    {
        getchar();
        gets(ci);//输入密文

        len=strlen(ci);

        for(i=0;i<len;i++)
        {
            if(ci[i]=='.')//这两点要特判
                temp=27;
            else if(ci[i]=='_')
                temp=0;
            else
                temp=ci[i]-'_'-1;
            
            t1=(temp+i)%28;
            //密文跟明文相对应
            if(t1==0)
            {
                pl[(k*i)%len]='_';
            }
            else if(t1==27)
            {
                pl[(k*i)%len]='.';
            }
            else
            {
                pl[(k*i)%len]='a'+t1-1;
            }
        }
        pl[i]='';//
        puts(pl);
    }
    return 0;
}
							

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

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

/*����,ÿ���Wall��λ����}�����,��rook����,���Թ�����Ӽ��ռ���,���ݵõ����Էŵ����rook��
 *���ռ���Ϊһ�ö�����,������nΪ16,ʱ�临�Ӷ�ΪO(2^n)<=65536,�����㷨����
 *�����Լ�������rook����ֱ��ˮƽ�����Ҵ�λ�ò�Ϊǽ..
 */

class cin
{
static int leave=0;
static StringTokenizer st;
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static int nextInt() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   int a=Integer.parseInt(st.nextToken());
   leave--;
   return a;
}
static String nextLine() throws IOException
{
   return in.readLine();
}
}
class Chess
{
char board[][];
int best,n,now,max;

void set(char b[][],int num)
{
   board=b;
   n=num;
   best=0;
   now=0;
   max=n*n;
}

boolean place(int x,int y)   //Լ����
{
   int i;
   if(board[x][y]=='X')return false;
   i=x-1;
   while(i>=0) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i--;
   }
   i=x+1;
   while(i< n) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i++;
   }
   i=y-1;
   while(i>=0) //������rook
   {
    if(board[x][i]=='r')return false;
    if(board[x][i]=='X')break;
    i--;
   }
   i=y+1;
   while(i< n) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i++;
   }
   return true;
}

void backTrack(int t) //����
{
   if(t==max)
   {
    if(now>best)best=now;
   }
   else 
   {
    if(max-t+1< best-now)return;
    int i=t/n,j=t%n;
    if(place(i,j))
    {
     now++;
     board[i][j]='r';
     backTrack(t+1);
     board[i][j]='.';
     now--;
    }
    backTrack(t+1);
   }
}
int outSum()
{
   backTrack(0);
   return best;
}
}

public class Main {
    public static void main(String args[]) throws IOException
    {
    char board[][]=new char[4][4];
    String temp;
    Chess data=new Chess();
    int n,i,j;
    while(true)
    {
       n=cin.nextInt();
       if(n==0)break;
       for(i=0;i< n;i++)
       {
        temp=cin.nextLine();
        for(j=0;j< n;j++)
         board[i][j]=temp.charAt(j);
       }
       data.set(board,n);
       System.out.println(data.outSum());
    }
    }
}
							

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

#include<iostream>
using namespace std;
int main()
{int p[27][3],n,cas,line;
int i,j,k,h,jie;char a;
cas=1;

while(1)
{cin>>n;
if(cin.fail())break;
if(n==0)break;

for(i=0;i<n;i++){cin>>a;p[i][0]=a;cin>>p[i][1];cin>>p[i][2];}
line=0;jie=0;
cout<<"Point set "<<cas<<":";
for(i=0;i<n;i++)
{for(j=0;j<n;j++)if(p[i][2]==p[j][2]&&p[i][1]<p[j][1])
    {for(k=0;k<n;k++)if(p[k][1]==p[j][1]&&p[k][2]<p[j][2])
        {for(h=0;h<n;h++)if(p[h][1]==p[i][1]&&p[h][2]==p[k][2])
                {if(line==0)cout<<endl;
                    cout<<' '<<(char)p[i][0]<<(char)p[j][0]<<(char)p[k][0]<<(char)p[h][0];
                    line++;if(line%10==0){cout<<endl;}}
}}}
if(line==0)cout<<" No rectangles"<<endl;
else if(line%10!=0)cout<<endl;
cas++;
}
return 0;
}
							

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

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

    Scanner in = new Scanner(System.in);
    
    int n,max;
    int i;
    while(in.hasNext()){
        n=in.nextInt();
        if(n==0) break;
        max=n/4+1;
        System.out.printf("Printing order for %d pages:n",n);
        if(n%4==1){
            int k=3;
            if(n==1)  System.out.printf("Sheet 1, front: Blank, 1n");
            else{
                System.out.printf("Sheet 1, front: Blank, 1n");
                System.out.printf("Sheet 1, back : 2, Blankn");
            }
            if(max>1){
                System.out.printf("Sheet 2, front: Blank, %dn",k++);
                System.out.printf("Sheet 2, back : %d, %dn",k++,n--);
                for(i=3;i<=max;i++){
                    System.out.printf("Sheet %d, front: %d, %dn",i,n--,k++);
                    System.out.printf("Sheet %d, back : %d, %dn",i,k++,n--);
                }
            }
        }
        else if(n%4==2){
           int k=3;
            System.out.printf("Sheet 1, front: Blank, 1n");
            System.out.printf("Sheet 1, back : 2, Blankn");
            for(i=2;i<=max;i++){
                System.out.printf("Sheet %d, front: %d, %dn",i,n--,k++);
                System.out.printf("Sheet %d, back : %d, %dn",i,k++,n--);
            }
        }
        else if(n%4==3){
            int k=3;
            System.out.printf("Sheet 1, front: Blank, 1n");
            System.out.printf("Sheet 1, back : 2, %dn",n--);
            for(i=2;i<=max;i++){
                System.out.printf("Sheet %d, front: %d, %dn",i,n--,k++);
                System.out.printf("Sheet %d, back : %d, %dn",i,k++,n--);
            }
        }
        else {
            max--;
            int k=1;
            for(i=1;i<=max;i++){
                System.out.printf("Sheet %d, front: %d, %dn",i,n--,k++);
                System.out.printf("Sheet %d, back : %d, %dn",i,k++,n--);
            }
        }
    }
   }
}
							

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

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

/**
 * 
 * Accepted. BigInteger is used here.
 * 
 * 
 */
public class Main {

    /**
     * Check if the given string is in numberic format.
     * 
     * @param a
     * @return
     */
    private static boolean isNumber(String a) {
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) >= '0' && a.charAt(i) <= '9') {
                // ignore
            } else {
                return false;
            }
        }

        return true;
    }

    /**
     * Format the given number.  such as 1234 to 1,234
     * 
     * @param a
     * @return
     */
    private static String format(String a) {
        StringBuffer sb = new StringBuffer();
        for (int j = a.length() - 1; j >= 0; j--) {
            if ((j != a.length() - 1) && ((a.length() - 1 - j) % 3 == 0)) {
                sb.append(",");
            }

            sb.append(a.charAt(j));
        }

        return sb.reverse().toString();
    }

    /**
     * Translate the words to number.
     * 
     * @param a
     * @return
     */
    private static String transalteToNumber(String a) {
        BigInteger m = new BigInteger("26");
        BigInteger ret = BigInteger.ZERO;

        BigInteger b = BigInteger.ONE;

        for (int i = a.length() - 1; i >= 0; i--) {
            BigInteger temp = new BigInteger("" + (a.charAt(i) - 'a' + 1));
            temp = temp.multiply(b);
            b = b.multiply(m);
            ret = ret.add(temp);
        }

        return ret.toString();
    }

    /**
     * Translate number to words.
     * 
     * @param a
     * @return
     */
    private static String translateString(String a) {
        BigInteger b = new BigInteger(a);
        BigInteger m = new BigInteger("26");
        StringBuffer sb = new StringBuffer();
        while (b.compareTo(BigInteger.ZERO) > 0) {

            BigInteger k = b.mod(m);
           if (k.intValue() <= 0) {
                sb.append("z");
                b = b.subtract(m);
            } else {
                sb.append((char) (k.intValue() - 1 + 'a'));

                b = b.subtract(k);
            }
            b = b.divide(m);
        }

        return sb.reverse().toString();
    }

    /**
     * Delete the leading zero.
     * 
     * @param a
     * @return
     */
    private static String deleteLeadingZero(String a) {
        int i = 0;
        while (a.charAt(i) == '0') {
            i++;
        }

        StringBuilder sb = new StringBuilder();
        while (i < a.length()) {
            sb.append(a.charAt(i));
            i++;
        }

        return sb.toString();
    }

    /**
     * Format and print the result string.
     * 
     * @param s
     */
    private static void print(String s) {
        int max = 22;
        String[] temp = s.split("[ ]+");

        System.out.print(temp[0]);

        for (int j = temp[0].length(); j < max; j++) {
            System.out.print(" ");
        }

        System.out.println(temp[1]);
    }

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        Scanner cin = new Scanner(System.in);
        while (true) {
            String line = cin.nextLine();
            line = deleteLeadingZero(line.trim());
            if (line.equals("*")) {
                break;
            }

            String word = "";
            String number = "";
            if (isNumber(line)) {
                word = translateString(line);
                number = format(line);
                print(word + " " + number);
            } else {
                word = line;
                number = format(transalteToNumber(line));
                print(word + " " + number);
            }
        }
    }

}



							

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

//* @author: 
import java.util.*;
public class Main {
  
 public static void main(String[] args){
  Scanner in = new Scanner(System.in);
  long N,i,j,t,ans;
  int flag=0;

  N=in.nextLong();
  while(N>0)
  {
    flag=0;
    for(j=N-1;j>1;j--)
    {
    
    i=0;
    t=N;
    while(t%j==1)
    {
      t-=(t/j+1);
      i++;
    }
    if(t%j==0&&i==j)
    {
      flag=1;
      ans=j;
      System.out.printf("%d coconuts, %d people and 1 monkeyn",N,ans);
         break;
     }
      }
    if(flag==0)
      System.out.printf("%d coconuts, no solutionn",N);
    N=in.nextLong();
     }
   }
}

							

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

#include<iostream>
using namespace std;
short ins[50000];
bool bb[50000];
int main()
{
    int a,b,c=1;
    int i;
    memset(bb,0,sizeof(bb));
    memset(ins,0,sizeof(ins));
    int iMax=-1;
    int zero;
    bool flag;// ones;

    while(scanf("%d%d",&a,&b))
    {
        if(a==-1 && b==-1)
            break;
        if(a==0 && b==0)
        {
            zero=0;
            flag = false;
            
            for(i=1;i<=iMax;++i)
            {
                if(bb[i])
                {
                    if(ins[i]==0)
                        
                        zero+=1;
                    else
                    {
                        if(ins[i]>1)
                        {
                            printf("Case %d is not a tree.n",c);
                            c++;
                            flag=true;
                            break;
                        }
                    }
                    if(zero > 1)//度为0的点大于1个

                    {
                        printf("Case %d is not a tree.n",c);
                        c++;
                        flag=true;
                        break;
                    }
                }
            }
            if(flag == false )
            {
                if(zero ==0 && iMax!=-1)
                    printf("Case %d is not a tree.n",c);
                else
                    printf("Case %d is a tree.n",c);
                c++;
            }
            memset(bb,0,sizeof(bb));
            memset(ins,0,sizeof(ins));
            iMax=-1;
        }
        else
        {
            bb[a]=true;
            bb[b]=true;
            ins[b]+=1;
            if(iMax<a)
                iMax=a;
            if(iMax<b)
                iMax=b;
        }
    }
    return 0;
}
							

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

#include"stdio.h"
bool left[13][13];
bool right[13][13];
bool up[13][13];
bool down[13][13];
int n,m,x1,x2,y1,y2;

bool init()
{
    int i,j,s;
    
    scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2);

    if(n==0&&m==0&&x1==0&&x2==0&&y1==0&&y2==0)
        return 0;

    x1--,x2--,y1--,y2--;    
    
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        scanf("%d",&s);
        right[i][j] = left[i][j+1]= (s&1);
        down[i][j] = up[i+1][j]= (s&2);
    }

    for(i=0;i<n;i++)
        left[i][0]=true,right[i][m-1]=true;
    for(j=0;j<m;j++)
        up[0][j]=true,down[n-1][j]=true;

    return 1;
}

int sign[13][13];
bool (*pt[])[13]={left,up,right,down};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};


bool search(int x,int y,int step)
{
    int i;

    sign[x][y]=step;
    
    if(x==x2&&y==y2)return 1;
    
    for(i=0;i<4;i++)
        if( !pt[i][x][y] && sign[x+dx[i]][y+dy[i]]==0 )
        {
            if(search(x+dx[i],y+dy[i],step+1))
                return 1;    
        }
    
    sign[x][y] = -1;
    
    return 0;
}

void doit()
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        sign[i][j]=0;
    search(x1,y1,1);
}

void printmap()
{
    int i,j;
    static  int times=1;
    
    printf("Maze %dnn",times++);    
           
    printf("+");
     
    for(j=0;j<m;j++)
    {
        printf("---+");
    }
    
    for(i=0;i<n;i++)
    {
        printf("n|");
        for(j=0;j<m;j++)
        {
            if(sign[i][j]>0)printf("%3d",sign[i][j]);
            else if(sign[i][j]==-1)printf("???");
            else printf("   ");
            
            if(right[i][j])printf("|");
            else printf(" ");
        }

        printf("n+");
        for(j=0;j<m;j++)
        {
        
            if(down[i][j])printf("---");
            else printf("   ");
            printf("+");
        }
    }
    printf("nnn");
}

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

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

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


public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(true)
        {
            int n = in.nextInt();
            int m = in.nextInt();
            int m1 = m;
            BigInteger sum1 = new BigInteger("1");
            BigInteger sum2 = new BigInteger("1");
            BigDecimal a;
            if(n == 0 && m == 0)
                break;
            if(m > n/2)
            {
                m = n - m;
            }
            for(int i = 0; i< m; i++)
            {
                sum1 = sum1.multiply(new BigInteger(String.valueOf(n-i))); 
            }
            for(int i = 0; i< m; i++)
            {
                sum2 = sum2.multiply(new BigInteger(String.valueOf(i+1)));
            }
            System.out.println(n + " things taken " + m1 +" at a time is " 
                    + sum1.divide(sum2) +" exactly.");
        }
    }

}

							

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

/* @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);
   while(run()==true)
        ;
 }

static boolean run(){
  String marker = cin.next();
  if(marker.compareTo("ENDOFINPUT")==0)
    return false;

  int n = cin.nextInt();
  Sequence seq = new Sequence(cin.next());
  System.out.println(seq.mutatedSequence());
  cin.next();
  return true;
 }

}

class Sequence{
 char[] content;
 public Sequence(String s){
   content = s.toCharArray();
 }

 public Sequence(char[] content){
   this.content = content;
 }

 private int mutate(int start){
  int count;

  if(start>=content.length)
   return 0;
  char c = content[start];
  if(isLetter(c)){
    count = mutate(start+1);
    content[start] = (char)(count%10+'0');
    count++;
    return count;
   }
  else if(c == '0')
    return 0;
  else if(isNumber(c)){
    content[start] = (char)(c-1);
    if((start+c-'0')< content.length)
    count = mutate(start+c-'0');
    else
    count = mutate(start+1);
    count++;
    return count;
  }
            
  return -1;
}

 private boolean isLetter(char c){
   if((c<='Z')&&(c>='A'))
     return true;
   return false;
  }

 private boolean isNumber(char c){
   if((c<='9')&&(c>='0'))
     return true;
   return false;
 }


 String mutatedSequence(){
   mutate(0);
   return new String(content);
 }
}

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
    
public static void main(String[] args)
{
  Scanner in=new Scanner(System.in);
  while(true)
  {
    String s=in.next();
    if(s.equals("ENDOFINPUT"))break;
    int loc=in.nextInt();
    int n=in.nextInt();
    in.nextLine();
    int[] door=new int[n];
    int doors=0;
    for(int i=0;i< n;i++)
    {
        s=in.nextLine();
        if(s.equals("")) continue;
        String[] ss=s.split(" ");
        for(int j=0;j< ss.length;j++)
        {
            int u=Integer.parseInt(ss[j]);
            door[i]++;
            door[u]++;
            doors++;
        }
    }
    s=in.nextLine();
    int odd=0,even=0;
    for(int i=0;i< n;i++)
    {
        if(door[i]%2==0) even++;
        else odd++;
    }
    if(odd==0&&loc==0) System.out.println("YES "+doors);
    else if(odd==2&&loc!=0&&door[loc]%2==1&&door[0]%2==1)
        System.out.println("YES "+doors);
    else System.out.println("NO");
  }
 }
}

							

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    String s1;
    int r,g,w;
    while (true){
        s1=scanner.next();
        if (s1.equals("ENDOFINPUT")){
            break;
        }
        r=scanner.nextInt();
        g=scanner.nextInt();
        w=scanner.nextInt()%360;
        if (w>180){
            w=360-w;
        }
        int m1=g*5;
        int m2=(int)Math.ceil(Math.PI*4*r*w/360);
        if (m1< m2){
            System.out.println("NO "+m1);
        }
        else{
            System.out.println("YES "+(m1-m2)/5);
        }
        scanner.next();
    }
  }
}


							

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

 import java.io.BufferedInputStream;
 import java.util.Scanner;

 public class Main {

     String cipher;
     char[] message;
     char c;

     public Main() {
         Scanner scan = new Scanner(new BufferedInputStream(System.in));
         while (!(cipher = scan.nextLine()).equals("ENDOFINPUT")) {
             while (!(cipher = scan.nextLine()).equals("END")) {
                 message = cipher.toCharArray();
                 for (int i = 0; i < message.length; i++) {
                     c = message[i];
                     if (65 <= c && c <= 90) {
                         c = (char) (65 + (c - 65 - 5 + 26) % 26);
                         message[i] = c;
                     }
                 }
                 System.out.println(String.valueOf(message));
             }
         }
     }

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

							

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

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

public class Main
{
    public static Node[] nodes;
    
    public static void main(String[] args) 
    {
      Scanner sc = new Scanner(new BufferedInputStream(System.in));
      while(true)
      {
            int n = sc.nextInt();
            if(n == 0)
            {
                break;
            }
            boolean consistent = true;
            nodes = new Node[n+1];
            for(int i = 1; i <= n; i++)//make set;
            {
                nodes[i] = new Node(i);
            }
            for(int i = 1; i <=n; i++)
            {
                sc.next();
                int j = sc.nextInt();
                sc.next();
                String falsehood = sc.next();
                falsehood = falsehood.substring(0,falsehood.length()-1);
                if(consistent)
                {
                    boolean unionOk = unionOne(i,j,Boolean.parseBoolean(falsehood));
                    if(!unionOk)
                    {
                        consistent = false;
                    }
                }
            }
            if(consistent)
            {
                int result = 0;
                for(int i = 1; i <= n; i++)
                {
                    if(nodes[i].parent == -1)
                    {
                        if(nodes[i].numOfTrue >= nodes[i].numOfFalse)
                        {
                            result += nodes[i].numOfTrue;
                        }else
                        {
                            result += nodes[i].numOfFalse;
                        }
                    }
                }
                System.out.println(result);
            }else
            {
                System.out.println("Inconsistent");
            }
        }
    }
    
    public static boolean unionOne(int i, int j, boolean falsehood)
    {
        int t1 = find(i);
        int t2 = find(j);
        boolean unionOk = true;
        if(t1 == t2)
        {
            if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
            {
                unionOk = false;
            }
        }else
        {
            if(nodes[t2].num <= nodes[t1].num)
            {
                nodes[t2].parent = t1;
                /*for(int k : nodes[t2].nodes)
                {
                    nodes[k].parent = t1;
                }*/
                nodes[t1].num += nodes[t2].num;
                if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
                {
                    for(int k : nodes[t2].nodes)
                    {
                        nodes[k].falsehood = !nodes[k].falsehood;
                    }
                    nodes[t1].numOfTrue += nodes[t2].numOfFalse;
                    nodes[t1].numOfFalse += nodes[t2].numOfTrue;
                }else
                {
                    nodes[t1].numOfTrue += nodes[t2].numOfTrue;
                    nodes[t1].numOfFalse += nodes[t2].numOfFalse;
                }
                
                nodes[t1].nodes.addAll(nodes[t2].nodes);
            }else
            {
                nodes[t1].parent = t2;
                /*for(int k : nodes[t1].nodes)
                {
                    nodes[k].parent = t2;
                }*/
                nodes[t2].num += nodes[t1].num;
                if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
                {
                    for(int k : nodes[t1].nodes)
                    {
                        nodes[k].falsehood = !nodes[k].falsehood;
                    }
                    nodes[t2].numOfTrue += nodes[t1].numOfFalse;
                    nodes[t2].numOfFalse += nodes[t1].numOfTrue;
                }else
                {
                    nodes[t2].numOfTrue += nodes[t1].numOfTrue;
                    nodes[t2].numOfFalse += nodes[t1].numOfFalse;
                }
                nodes[t2].nodes.addAll(nodes[t1].nodes);
            }
        }
        return unionOk;
    }
    
    public static int find(int x)
    {
        Node r = nodes[x];
        while(r.parent != -1)
        {
            r = nodes[r.parent];
        }
        while(nodes[x].position != r.position)
        {
            int q = nodes[x].parent;
            nodes[x].parent = r.position;
            x = q;
        }
        return r.position;
    }
    
}

class Node
{
    int position;
    boolean falsehood;
    int parent;
    int num;
    int numOfTrue;
    int numOfFalse;
    LinkedList<Integer> nodes;
    
    public Node(int position)
    {
        this.position = position;
        this.falsehood = true;
        this.parent = -1;
        this.num = 1;
        this.numOfTrue = 1;
        this.numOfFalse = 0;
        this.nodes = new LinkedList< Integer>();
        this.nodes.add(position);
    }
}

							

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

#include<iostream>
using namespace std;
 
int main(){
    int init_hei, work_num;
    while(cin >> init_hei >> work_num && init_hei != 0){
        int n = 0, v1, v2, x;
        bool flag = false;
        while(!flag){   //  模拟解方程(n+1)^x = init_hei, n^x = work_num。
            n ++;
            x = 0;
            v1 = v2 = 1;
            while(1){
                if(v1 > init_hei || v2 > work_num)
                    break;
                if(v1 == init_hei && v2 == work_num){
                    flag = true;
                    break;
                }
                v1 *= n + 1;
                v2 *= n;
                x ++;
            }
        }

        int nowork_num, hei, num, height_sum;
        if(n == 1)  nowork_num = 0;   //  切记比为1的情况应单独考虑。
        else  nowork_num = (work_num - 1) / (n - 1);
        hei = 1;
        num = work_num;
        height_sum = 0;
        for(int i = 0; i <= x; i ++){  //  逐项乘积相加。
            height_sum += num * hei;
            hei *= n + 1;
            num /= n;
        }
        cout << nowork_num << ' ' << height_sum << endl;
    }
    return 0;
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Edge implements Comparable{
    int start,end;
    int cost;
    public int compareTo(Object temp){
        Edge cnt = (Edge) temp;
        if(cnt.cost< this.cost) return 1;
        return -1;
    }
}
class Set{
    final int N = 100;
    int father[] = new int[N],num[] = new int[N];
    void init(){
        for(int i=0;i< N;++i){
            father[i] = -1;
            num[i] = 0;
        }
    }
    int find(int who){
        int u,v = who;
        while(this.father[who]!=-1){
            who = this.father[who];
        }
        while(v!=who){
            u = this.father[v];
            this.father[v] = who;
            v = u;
        }
        return who;
    }
    void set(int a,int b){
        a = this.find(a);
        b = this.find(b);
        if(a==b)
            return ;
        if(this.num[a]>this.num[b]){
            this.father[b] = a;
            this.num[a]+=this.num[b];
        }else{
            this.father[a] = b;
            this.num[b]+=this.num[a];
        }
    }
}
public class Main {
    static final int N = 100000;
    static int n,m;
    static Set set = new Set();
    static Edge edge[] = new Edge[N];
    static void start(){
        for(int i=0;i< N;++i)
            edge[i] = new Edge();
    }
    static int solve(){
        int ans=0;
        int i;
        Arrays.sort(edge,0,m);
        for(i=0;i< m;++i){
            if(set.find(edge[i].start)!=set.find(edge[i].end))
                ans+=edge[i].cost;
            set.set(edge[i].start, edge[i].end);
        }
        return ans;
    }
public static void main(String[]args) throws Exception{
 int i,j;
 start();
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 while(true){
    n = Get_Num(cin);
    if(n==0) break;
    m = Get_Num(cin);
    set.init();
    for(i=0;i< m;++i){
        edge[i].start = Get_Num(cin);
        edge[i].end = Get_Num(cin);
        edge[i].cost = Get_Num(cin);
    }
    System.out.println(solve());
  }
}
    static int Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int)cin.nval;
    }
}

							

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

import java.io.PrintWriter; 
import java.io.PrintWriter; 
import java.util.Collections; 
import java.util.PriorityQueue;
import java.util.Scanner; 

public class Main { 
  Scanner cin = new Scanner(System.in);
  PrintWriter out=new PrintWriter(System.out,true);
  
  public void solve() {
   int maxCost,removeLen; 
   String op; 
   while(cin.hasNext()) {
    maxCost=cin.nextInt();
    removeLen=cin.nextInt(); 
    int [] list=new int[removeLen];
    for(int i=0; i< removeLen; i++) 
     list[i]=cin.nextInt();
 
  PriorityQueue< Integer> minQ=new PriorityQueue< Integer>();
  PriorityQueue< Integer> maxQ=new PriorityQueue< Integer>(1000,Collections.reverseOrder());
  int state=1,cost,step=1,flagRemove=0,temp; op=cin.next();
  while(!op.equals("e")) {
   if(op.equals("a")) {
    cost=cin.nextInt();
    maxQ.add(cost);
    minQ.add(cost);
   } else if(op.equals("r")) {
     if(maxQ.isEmpty()) //empty 
       out.println("-1");
    else //not empty 
    { 
     if(state==1){
      temp=minQ.poll(); 
      maxQ.remove(temp);  
     } else {
      temp=maxQ.poll();
       minQ.remove(temp);   
    } 
  if(flagRemove< removeLen&&step==list[flagRemove]) //show 
 { 
   out.println(temp); 
   flagRemove++; 
  } 
 } step++; 
} else // op==p 
{ 
 state=cin.nextInt();
 } 
op=cin.next();
 } 
out.println("");
 } 
out.close();
 }
 
public static void main(String[] args) {
    Main m = new Main(); 
    m.solve();
  }
 } 

							

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

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
    cin = new Scanner(System.in);
    int num = cin.nextInt();
    for(int i=0;i< num;i++)
      run();
  }

static void run(){
    int p = cin.nextInt();
    //BigInteger n = new BigInteger(new Integer(p));
    BigInteger one = new BigInteger("1");
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    BigInteger six = new BigInteger("24");


    if(p<=3)
      System.out.println(0);
    else if(p%2==1)
      System.out.println(p*(p-3)/2);
    else
         System.out.println(p*(p-4)/2+1);
  }

}

							

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

import java.util.Scanner;

public class Main {

    static int[] value = new int[100];
    static int[] dp = new int[100001];

    public static void main(String[] args) {
        Scanner s;
        try {
            // s = new Scanner(new InputStreamReader(new FileInputStream(
            // "c:\1.txt")));
            s = new Scanner(System.in);
            while (s.hasNextInt()) {

                int total = s.nextInt();
                int kind = s.nextInt();

                int count = 0;

                for (int i = 0; i < kind; i++) {
                    int a = s.nextInt();
                    int b = s.nextInt();
                    int k = 1;
                    while (a - k >= 0) {
                        a -= k;
                        value[count++] = k * b;
                        k *= 2;
                    }
                    if (a > 0)
                        value[count++] = a * b;

                }
                if (total == 0 || kind == 0 || count == 0) {
                    System.out.println(0);
                    continue;
                }
                for (int i = 1; i <= total; i++)
                    dp[i] = 0;
                dp[0] = 1;
                for (int i = 0; i < count; i++)
                    for (int j = total; j >= value[i]; j--)
                        if (dp[j] == 0)
                            dp[j] = dp[j - value[i]];
                for (int i = total; i >= 0; i--)
                    if (dp[i] > 0) {
                        System.out.println(i);
                        break;
                    }

            }

        } catch (Exception e) {
            System.exit(0);
        }

    }

}
							

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

import java.io.*;
import java.util.*;
public class Main
{
   static int m,n;
   static boolean[] flag;
   static int[] occ;
   static int[][] adj;
   public static void main(String args[]) throws Exception
   {
     Scanner cin=new Scanner(System.in);
     while(cin.hasNext())
     {
          n=cin.nextInt();
          m=cin.nextInt();
          adj=new int[n+1][m+1];
       for(int i=0;i< n;i++)
       {
          int a=cin.nextInt();
          while(a--!=0)
           {
                 adj[i+1][cin.nextInt()]=1;
            }
       }
       int count=0;
         occ=new int[m+1];
          for(int i=1;i<=n;i++)
          {
        flag=new boolean[m+1];
        if(find(i))
        {
         count++;
        }
                            
       }
       System.out.println(count);
    }
  }
            
  public static boolean find(int i)
  {
   for(int j=1;j<=m;j++)
    {
      if(!flag[j]&&adj[i][j]==1)
      {
        flag[j]=true;
        if(occ[j]==0||find(occ[j]))
        {
         occ[j]=i;
         return true;
        }
       }
    }
    return false;
  }
}
							

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

//* @author: 
import java.util.*;
public class Main implements Comparator< Integer> { 
  static class Edge{  
   int e,c;
   Edge next;
   Edge rev;  
  public void dec(int f){
   c-=f;
   rev.c+=f;
  }
 }

 int n,m,src,tag;
 final Edge[] g=new Edge[200];
 final int[] h=new int[200];  final int[] ex=new int[200];
 final Scanner sc=new Scanner(System.in);
 final PriorityQueue< Integer> pq=new PriorityQueue< Integer>(200,this);

 boolean init(){ 
   if(!sc.hasNext()) return false;
   m=sc.nextInt();
   n=sc.nextInt();
   src=0;   tag=n-1;
  for(int i=0;i!=n;++i){
   g[i]=null;
   h[i]=0;
   ex[i]=0;
   }

  h[src]=n;
  for(int i=0;i!=m;++i){
   int a=sc.nextInt()-1,b=sc.nextInt()-1,c=sc.nextInt();
   Edge e0=addEdge(a, b, c),e1=addEdge(b,a,0);
   e0.rev=e1;e1.rev=e0;
  }    return true; 
 }

  private Edge addEdge(int s, int e, int c) {
   Edge n=new Edge();
   n.c=c;
   n.e=e;
   n.next=g[s];
   g[s]=n;
  return n;
  }

  int work(){
   for(Edge e=g[src];e!=null;e=e.next){
    ex[e.e]+=e.c;
    e.dec(e.c);
    if(e.e!=src&&e.e!=tag){
     pq.add(e.e);
   }
  }
  while(pq.size()>0){
   int v=pq.poll();
   int exv=ex[v],hv=h[v];
   for(Edge e=g[v]; exv>0&&e!=null; e=e.next){  
      if(e.c<=0 || hv !=h[e.e]+ 1 ) continue;
    int f=Math.min( exv , e.c);
    ex[e.e]+=f;
    exv-=f;
    e.dec(f);
    if(ex[e.e]==f&&e.e!=tag&&e.e!=src){
     pq.add(e.e);
    }
   }
   if(exv>0){
    for(Edge e=g[v];e!=null;e=e.next){
     if(e.c > 0 && hv>h[e.e]){
      hv=h[e.e];
     }
    }
    ++hv;
    pq.add(v);
   }
   ex[v]=exv;
   h[v]=hv;
  }
  return ex[tag];
 }

  void go(){     while(init()){
    System.out.println( work());
  }
  }

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

  public int compare(Integer o1, Integer o2) {
   return h[o2]-h[o1];
  }
}
							

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

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

public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n=scanner.nextInt();
        double[] x,y;
        double px,py;
        double k1,k2,b1,b2;
        System.out.println("INTERSECTING LINES OUTPUT");
        for (int i=0;i< n ;i++ ){
            x=new double[4];
            y=new double[4];
            for (int j=0;j< 4 ;j++ ){
                x[j]=scanner.nextDouble();
                y[j]=scanner.nextDouble();
            }
            if ((x[1]-x[0])*(y[3]-y[2])==(x[3]-x[2])*(y[1]-y[0])){
                if ((x[3]-x[0])*(y[2]-y[1])==(x[2]-x[1])*(y[3]-y[0])){
                    System.out.println("LINE");
                }
                else{
                    System.out.println("NONE");
                }
            }
            else{
                if (x[0]==x[1]){
                    px=x[0];
                    k2=(y[3]-y[2])/(x[3]-x[2]);
                    b2=y[3]-k2*x[3];
                    py=k2*px+b2;
                }
                else if (x[2]==x[3]){
                    px=x[2];
                    k1=(y[1]-y[0])/(x[1]-x[0]);
                    b1=y[1]-k1*x[1];
                    py=k1*px+b1;
                }
                else{
                    k1=(y[1]-y[0])/(x[1]-x[0]);
                    b1=y[1]-k1*x[1];
                    k2=(y[3]-y[2])/(x[3]-x[2]);
                    b2=y[3]-k2*x[3];
                    px=(b2-b1)/(k1-k2);
                    py=k1*px+b1;
                }
                px=(Math.round(px*100.0))/100.0;
                py=(Math.round(py*100.0))/100.0;
                System.out.println("POINT "+getO(px)+" "+getO(py));
            }
        }
        System.out.println("END OF OUTPUT");
    }

    public static String getO(double d){
        String ds=""+d;
        while (true){
            int index=0;
            boolean flag=false;
            for (int j=0;j< ds.length() ;j++ ){
                if (flag){
                    index++;
                }
                if (ds.charAt(j)=='.'){
                    flag=true;
                }
            }
            if (index==2){
                break;
            }
            else if (index==1){
                ds=ds+"0";
            }
        }
        return ds;
    }
}


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Point{
    int x,y;
}
public class Main {
    
    static final int N = 100+10;
    static int n;
    static Point Area[] = new Point[N];
    static void start(){
        for(int i=0;i< N;++i)
            Area[i] = new Point();
    }
public static void main(String []args) throws Exception{
        
    int t,cs=1,i,x,y;
    
    StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    start();
    t = Get_Num(cin);
    while(t--!=0){
        n = Get_Num(cin);
        Area[0].x = Area[0].y = 0;
        for(i=1;i<=n;++i){
            Area[i].x = Get_Num(cin)+Area[i-1].x;
            Area[i].y = Get_Num(cin)+Area[i-1].y;
        }
        solve(cs++);
    }
}
    static int Get_Num(StreamTokenizer cin) throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    static int GCD(int a,int b){
        if(b==0) return a;
        return GCD(b,a%b);
    }
    static int node_in_line(Point a,Point b){
        int x,y;
        x = abs(a.x-b.x);
        y = abs(a.y-b.y);
        return GCD(x,y);
    }
    static int abs(int a){
        if(a>=0) return a;
        return -a;
    }
    static int get_area(Point a,Point b,Point c){
        return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y);
    }
    static void solve(int cs){
        int I,E=0,area=0,i;
        for(i=0;i< n;++i){
            E+=node_in_line(Area[i],Area[(i+1)%n]);
        }
        for(i=2;i< n;++i){
            area += get_area(Area[0],Area[i-1],Area[i]);
        }
        area = abs(area);
        I = (area-E+2)/2;
        
        System.out.print("Scenario #"+cs+":n"+I+" "+E+" ");
        if(area%2==0) System.out.println(area/2+".0n");
        else System.out.println(area/2+".5n");
    }
}

							

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

#include<iostream>
#include"math.h"
using namespace std;
const double pi=3.14159265358979324;

struct point
{double x,y;};

struct cir
{point p;
double r;};

struct ray
{point p;
double dx,dy;};

struct line
{double a,b,c;};
//l: ax+by+c=0

inline double sq(double a)
{return a*a;}    

line ray_line(ray s)
{line l;double d;
if(s.dx==0){l.a=1;l.b=0;l.c=-s.p.x;return l;}    
d=s.dy/s.dx;
l.a=d;l.b=-1;l.c=s.p.y-d*s.p.x;
return l;
}

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 double jl(line &l,point &p)
{return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);}

double jl(cir &c,ray &s)
{line l=ray_line(s);return jl(l,c.p);}

int in_cir(cir &c,point &p)
{return fabs(c.r*c.r-sq(c.p.x-p.x)-sq(c.p.y-p.y))<0.00001;}

point jiao(ray &s,cir &c)
{point n;
double d=jl(c,s),
       l=jl(c.p,s.p),
       h=sqrt(sq(l)-sq(d)),
       f=sqrt(sq(c.r)-sq(d)),
       g=h-f,
       m=sqrt(sq(s.dx)+sq(s.dy));
    
       n.x=s.p.x+g/m*s.dx;
       n.y=s.p.y+g/m*s.dy;
       
       if(!in_cir(c,n)){n.x=s.p.x-g/m*s.dx;n.y=s.p.y-g/m*s.dy;}
return n;
}

ray ref(ray &s,cir &c,point &n)
{ray fs;point vec;double m;
        vec.x=n.x-c.p.x;
    vec.y=n.y-c.p.y;
    m=sqrt(sq(vec.x)+sq(vec.y));
    vec.x/=m;vec.y/=m;
    m=vec.x*(s.p.x-n.x)+vec.y*(s.p.y-n.y);
    vec.x*=2*m;vec.y*=2*m;
    fs.p=n;
    fs.dx=vec.x-(s.p.x-n.x);
    fs.dy=vec.y-(s.p.y-n.y);    
        return fs;   
 }      

cir c[30];
ray s;int n;
int main()
{int i,j,c_n=0,key;point nb,nt;int b;
    while(1)
    {cin>>n;
    if(n==0)break;
    for(i=0;i<n;i++)
        cin>>c[i].p.x>>c[i].p.y>>c[i].r;
    cin>>s.p.x>>s.p.y>>s.dx>>s.dy;
    cout<<"Scene "<<++c_n<<endl;
    
    for(i=0;i<=10;i++)
    {key=0;b=-1;
    for(j=0;j<n;j++)
    if(jl(c[j],s)<c[j].r&&!in_cir(c[j],s.p))
        {
        nt=jiao(s,c[j]);
        if((nt.x-s.p.x)*s.dx>=0&&(nt.y-s.p.y)*s.dy>=0)
            {if(key==0){nb=nt;b=j;}
            else if(jl(nt,s.p)<jl(nb,s.p)){nb=nt;b=j;}
            }
        }    
    if(b==-1){cout<<"inf"<<endl;break;}
    else if(i==10)cout<<"..."<<endl;
    else {s=ref(s,c[b],nb);
        cout<<b+1<<' ';}
    }
    cout<<endl;
    }
return 0;
}
    
    
    
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  static final int maxn=100;
  private int a[]=new int[maxn],p[]=new int[maxn],f[]=new int[maxn];

  private  int min(int a,int b){
    return a< b?a:b;
  }

  public int dp(int x){
    if(x< 0)return 0;
    if(f[x]!=-1)return f[x];
    if(x==0)return f[x]=(a[0]+10)*p[0];
    int c=(10+a[x])*p[x],res=c+dp(x-1);
    for(int i=x-1;i>=0;i--){
        c+=p[x]*a[i];
        res=min(c+dp(i-1),res);
    }
    return f[x]=res;
}
 public static void main(String args[]){
    
    Scanner sc=new Scanner(System.in);
  
    int times=sc.nextInt();
    while((times--)!=0){
        int n=sc.nextInt();
              Main m=new Main();
        for(int i=0;i< n;i++){
               m.a[i]=sc.nextInt();
               m.p[i]=sc.nextInt();
             }
             Arrays.fill(m.f,-1);
        System.out.printf("%dn",m.dp(n-1));
    }
  }
}


							

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



 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));
         String s = null;
         int n;
         int[][] a;
         int t;
         String[] ss;
         int index;
         while ((s = read.readLine()) != null) {
             if (s.equals("")) {
                 break;
             }
             n = Integer.parseInt(s);
             a = new int[n][n];
             t = n;
             while (t-- > 0) {
                 index = 0;
                 while (index != n) {
                     ss = read.readLine().split(" ");
                     for (int i = 0; i < ss.length; i++, index++) {
                         a[n - t - 1][index] = Integer.parseInt(ss[i]);
                     }
                 }
             }
             System.out.println(prim(a, n));
         }
     }

     public static int prim(int[][] a, int count) {
         int sum = 0;
         int i, j, k;
         int[] lowcost = new int[count];
         int[] closeset = new int[count];
         boolean[] used = new boolean[count];
         for (i = 0; i < count; i++) {
             lowcost[i] = a[0][i];
             closeset[i] = 0;
             used[i] = false;
         }
         used[0] = true;
         for (i = 1; i < count; i++) {
             j = 0;
             while (used[j]) {
                 j++;
             }
             for (k = 0; k < count; k++) {
                 if ((!used[k]) && (lowcost[k] < lowcost[j])) {
                     j = k;
                 }
             }
             sum += lowcost[j];
             used[j] = true;
             for (k = 0; k < count; k++) {
                 if (!used[k] && (a[j][k] < lowcost[k])) {
                     {
                         lowcost[k] = a[j][k];
                         closeset[k] = j;
                     }
                 }
             }
         }
         return sum;
     } 
}

							

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

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

 public class Main {

     class Compara implements Comparator<Character> {
         public int compare(Character o1, Character o2) {
             char a = Character.toLowerCase(o1);
             char b = Character.toLowerCase(o2);
             if (a == b) {
                 return o1 - o2;
             } else {
                 return a - b;
             }
         }
     }

     public Main() throws NumberFormatException, IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int t = Integer.parseInt(read.readLine());
         String s;
         Character[] c;
         char[] temp;
         char[] o;
         boolean[] used;
         for (int i = 0; i < t; i++) {
             s = read.readLine();
             o = s.toCharArray();
             c = new Character[o.length];
             for (int j = 0; j < o.length; j++) {
                 c[j] = new Character(o[j]);
             }
             Arrays.sort(c, new Compara());
             used = new boolean[c.length];
             temp = new char[c.length];
             findAll(c, temp, 0, used);
         }
     }

     public void findAll(Character[] c, char[] temp, int i, boolean[] used) {
         char flg = ' ';
         if (i == c.length) {
             System.out.println(temp);
             return;
         }
         for (int j = 0; j < c.length; j++) {
             if (!used[j]) {
                 if (flg == c[j]) {
                     continue;
                 }
                 flg = c[j];
                 temp[i] = c[j];
                 used[j] = true;
                 findAll(c, temp, i + 1, used);
                 used[j] = false;
             }
         }
     }

     public static void main(String[] args) throws NumberFormatException,
             IOException {
         new Main();
     }

 }

							

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

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main{

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   DecimalFormat df1 = new DecimalFormat("0.0000"); 
   int n = cin.nextInt();
   while(n-- > 0) {
    int x1 = cin.nextInt();
    int y1 = cin.nextInt();
    double t1 = cin.nextInt();
    int x2 = cin.nextInt();
    int y2 = cin.nextInt();
    double t2 = cin.nextInt();
    double x, y;
    t1=t1 / 360 * 2 * Math.PI;
    t2=t2 / 360 * 2 * Math.PI;
      y = (Math.cos(t2)*(Math.sin(t1)*y1-Math.cos(t1)*x1)-Math.cos(t1)*(Math.sin(t2)*y2-Math.cos(t2)*x2))/(Math.sin(t1-t2));
    x = (Math.sin(t2)*(Math.sin(t1)*y1-Math.cos(t1)*x1)-Math.sin(t1)*(Math.sin(t2)*y2-Math.cos(t2)*x2))/(Math.sin(t1-t2));
    System.out.println(df1.format(x)+" "+ df1.format(y));
   }
  
}

}


							

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

import java.io.BufferedInputStream;   
import java.util.Collections;   
import java.util.HashMap;   
import java.util.Iterator;   
import java.util.LinkedList;   
import java.util.Map.Entry;   
import java.util.Scanner;   
  
 
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        while (scanner.hasNext()) {   
            int n = scanner.nextInt();   
            if (n == 0) {   
                break;   
            }   
            String a;   
            LinkedList< Edge> graph = new LinkedList();   
            for (int i = 0; i < n - 1; i++) {   
                a = scanner.next("[A-Z]");   
                int m = scanner.nextInt();   
                int j = 0;   
                while (j < m) {   
                    String b = scanner.next("[A-Z]");   
                    int value = scanner.nextInt();   
                    graph.add(new Edge(a, b, value));   
                    j++;   
                }   
            }   
            LinkedList< Edge> l = Kruskal(graph);   
            Iterator< Edge> ite = l.iterator();   
            Integer sum = 0;   
            while (ite.hasNext()) {   
                Edge e = ite.next();   
                sum = sum + e.getValue();   
            }   
            System.out.println(sum);   
        }   
    }   
  
    static LinkedList< Edge> Kruskal(LinkedList graph) {   
        Collections.sort(graph);   
        LinkedList< Edge> g = new LinkedList();   
        HashMap< String, Integer> vertexes = new HashMap< String, Integer>();   
        Iterator< Edge> it = graph.iterator();   
        Integer tree = 0;   
        while (it.hasNext()) {   
            Edge e = it.next();   
            if (g.size() == 0) {   
                g.add(e);   
                vertexes.put(e.getVertex1(), tree);   
                vertexes.put(e.getVertex2(), tree);   
            } else {   
                if (!vertexes.containsKey(e.getVertex1()) && vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    vertexes.put(e.getVertex1(), vertexes.get(e.getVertex2()));   
  
                } else if (vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    vertexes.put(e.getVertex2(), vertexes.get(e.getVertex1()));   
                } else if (!vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    tree++;   
                    vertexes.put(e.getVertex1(), tree);   
                    vertexes.put(e.getVertex2(), tree);   
                } else if (vertexes.get(e.getVertex1()) != vertexes.get(e.getVertex2())) {   
                    g.add(e);   
                    vertexes = MergeTwoTrees(vertexes, e.getVertex1(), e.getVertex2());   
                }   
            }   
        }   
        return g;   
    }   
  
    static HashMap< String, Integer> MergeTwoTrees(HashMap< String, Integer> vertexes, String v1, String v2) {   
        HashMap< String, Integer> hm = new HashMap< String, Integer>();   
        Integer a = vertexes.get(v1);   
        Integer b = vertexes.get(v2);   
        Iterator it = vertexes.entrySet().iterator();   
        while (it.hasNext()) {   
            Entry entry = (Entry) it.next();   
            String key = (String) entry.getKey();   
            Integer value = (Integer) entry.getValue();   
            if (b == value) {   
                value = a;   
            }   
            hm.put(key, value);   
        }   
        return hm;   
    }   
}   
  
class Edge implements Comparable {   
  
    private String vertex1;   
    private String vertex2;   
    private Integer value;   
  
    public Edge(String vertex1, String vertex2, Integer value) {   
        this.vertex1 = vertex1;   
        this.vertex2 = vertex2;   
        this.value = value;   
    }   
  
    public int getValue() {   
        return value;   
    }   
  
    public void setValue(int value) {   
        this.value = value;   
    }   
  
    public String getVertex1() {   
        return vertex1;   
    }   
  
    public void setVertex1(String vertex1) {   
        this.vertex1 = vertex1;   
    }   
  
    public String getVertex2() {   
        return vertex2;   
    }   
  
    public void setVertex2(String vertex2) {   
        this.vertex2 = vertex2;   
    }   
  
    public int compareTo(Object o) {   
        Edge e = (Edge) o;   
        return this.value - e.getValue();   
    }   
}