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

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int num = in.nextInt();
            if (num == 0)
                break;
            String customers = in.next();
            int leftCustomer = 0;
            Set<Character> customerSet = new HashSet<Character>();
            for (int i = 0; i < customers.length(); i++) {
                int size = customerSet.size();
                if (size >= num) {
                    if (customerSet.contains(customers.charAt(i))) {
                        customerSet.remove(customers.charAt(i));
                        continue;
                    }
                    leftCustomer++;
                    int index = customers.indexOf(customers.charAt(i), i + 1);
                    if (index != -1)
                        customers = customers.substring(0, index)
                                + customers.substring(index + 1);
                } else {
                    if (customerSet.contains(customers.charAt(i))) {
                        customerSet.remove(customers.charAt(i));
                    } else
                        customerSet.add(customers.charAt(i));
                }
            }
            if (leftCustomer == 0)
                System.out.println("All customers tanned successfully.");
            else
                System.out.println(leftCustomer + " customer(s) walked away.");
        }
    }
}
            
                
							

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

//* @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)
  {
   int a=in.nextInt();
    if(a==0)break;
    int[] arr=new int[a];
    int t=0;
    for(int i=0;i< a;i++)
    {
    arr[i]=in.nextInt();
    t+=arr[i];
     }
    if(t%2==1)System.out.println("No equal partitioning.");    
    else
    {
    t=t/2;
    for(int i=0;i< a;i++)
    {
      t-=arr[i];
      if(t==0){
       System.out.println("Sam stops at position "+(i+1)+" and Ella stops at position "+(i+2)+".");
        break;
       }
      else if(t< 0)
      {
       System.out.println("No equal partitioning.");
        break;
       }
    }
     }
    }
  }
}
							

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

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

public class Main{
 public static void main(String[] args) throws Exception{
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n,flag;
        String line,r;
        char c;
        int[] idx;
        while (true){
            n=scanner.nextInt();
            if (n==0){
                break;
            }
            line=scanner.next();
            r="";
            for (int i=0;i< 26 ;i++ ){
                c=(char) ('a'+i);
                idx=new int[n];
                flag=0;
                while (line.indexOf(c)!=-1){
                    idx[flag]=line.indexOf(c);
                    flag++;
                    line=line.replaceFirst(""+c,"#");
                }
                if (flag>=3){
                    if (isD(idx,flag)){
                        r=r+c;
                    }
                }
            }
            if (r.equals("")){
                System.out.println("LOOOOOOOOSER!");
            }
            else{
                System.out.println(r);
            }
        }
    }

    public static boolean isD(int[] idx,int flag){
        int a,b,c;
        int aa,bb,cc;
        int[] iidx=new int[3];
        boolean f,ff1,ff2;
        for (int i=0;i< flag-2 ;i++ ){
            for (int j=i+1;j< flag-1 ;j++ ){
                for (int k=j+1;k< flag ;k++ ){
                    a=getP(idx[i])-1;
                    b=getP(idx[j])-1;
                    c=getP(idx[k])-1;
                    aa=getL(idx[i]);
                    bb=getL(idx[j]);
                    cc=getL(idx[k]);
   if (3*(a-b)*(a-b)+(aa-bb)*(aa-bb)==3*(a-c)*(a-c)+(aa-cc)*(aa-cc)&&
      3*(c-b)*(c-b)+(cc-bb)*(cc-bb)==3*(a-c)*(a-c)+(aa-cc)*(aa-cc)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static int getP(int n){
        int flag=1;
        while (true){
            if (n<=(flag)*(flag+1)/2-1){
                return flag;
            }
            flag++;
        }
    }

    public static int getL(int n){
        int p=getP(n);
        int a=n-p*(p-1)/2;
        if (p%2==0){
            return 2*a-p+1;
        }
        else{
            return 2*(a-p/2);
        }
    }
}


							

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

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

public class Main{
 static Scanner cin;
 static int Case = 0;
 static int[][] result;
 public static void main(String args[]){
  cin = new Scanner(System.in);
    
  result = new int[100][100];
  int i,j;
  for(i = 0;i < 100;i++)
   for(j = 0;j < 100;j++)
     if(i == 1)
    result[i][j] = 1;
     else if(j == 0)
    result[i][j] = i;
     else
    result[i][j] = 0;
        
        
     while(true){
    if(!work(cin.nextInt(),cin.nextInt()))
      break;
     }
        
    return;
  }
    
  static boolean work(int m,int n){
   if((m == 0)&&(n == 0))
     return false;
        
   Case++;
   System.out.println("Case "+Case+": "+compute(m,n));
   return true;
  }
    
 static int compute(int m,int n){
    if(result[m][n] != 0)
    return result[m][n];
        
    result[m][n] = compute(m-1,n-1)+compute(m-1,n)+1;
    return result[m][n];
        
  }
}
							

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

/* @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(){
   int n = cin.nextInt();
   if(n==0)
        return false;

   Tree tree = new Tree(n, cin.next(), cin.next());
   System.out.println(tree.compute());
   return true;
 }
}


class Tree{
  static String preMap, postMap;
  static int M;

  static int[][] C;

  int preStart, postStart, length;

  public Tree(int M, String preMap, String postMap){
    this.M = M;
    this.preMap = preMap;
    this.postMap = postMap;

    C = new int[100][100];
    initialC();
        
    preStart = 0;
    postStart  = 0;
    length   = preMap.length();
   }

  public Tree(int preStart, int postStart, int length){
    this.preStart = preStart;
    this.postStart  = postStart;
    this.length = length;
  }

 ArrayList< Tree> subTree(){
    ArrayList< Tree> nodes = new ArrayList< Tree>();

    int start = preStart+1;
    int pEnd = postStart-1;
    int pstart, subLength;

    while(start< (preStart+length)){
         pstart = pEnd+1;
      pEnd  = postMap.indexOf(preMap.charAt(start));
        subLength = pEnd-pstart+1;

      nodes.add(new Tree(start, pstart, subLength));

      start = start+subLength;
    }

    return nodes;
   }

  int compute(){
    ArrayList< Tree> nodes = subTree();
    int count = C(M, nodes.size());
    for(Tree t:nodes)
         count *= t.compute();
    return count;
   }

  void initialC(){
    int i,j;
    for(i=0;i< 100;i++)
         for(j=0;j< 100;j++)
        C[i][j] = -1;

    for(i=0;i< 100;i++){
      C[1][i] = (i>1? 0:1);
      C[i][0] = 1;
    }
   }

int C(int n, int m){
  if(C[n][m] == -1)
    return C(n-1, m)+C(n-1, m-1);
  else
    return C[n][m];
  }
}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
interface Pass{
    int N = 100+10;
    void SetInit(int n,int k);
    void AddData(int left,int right);
    void InitData();
    int GetAns();
}
class Interval implements Comparable{
    int left,right;
    void set(int left,int right){
        this.left = left;
        this.right = right;
    }
    public int compareTo(Object obj){
        Interval temp = (Interval)obj;
        if(this.right>temp.right) return 1;
        return -1;
    }
}
class Muraille implements Pass{
    
    int n,k,cnt;
    int Graph[] = new int[N];
    int select[] = new int[N];
    Interval wall[] = new Interval[N];
    Muraille(){
        for(int i=0;i< N;++i) wall[i] = new Interval();
    }
    public void SetInit(int n,int k){
        cnt = 0;
        this.n = n;
        this.k = k;
        Arrays.fill(Graph, 0);
    }
    public void AddData(int left,int right){
        wall[cnt].set(left, right);
        for(int i=left;i<=right;++i){
            ++Graph[i];
        }
        ++cnt;
    }
    public void InitData(){
        Arrays.sort(wall,0,n);
    }
    void delete(int who){
        for(int i=wall[who].left;i<=wall[who].right;++i){
            --Graph[i];
        }
        wall[who].right = -1;
    }
    void delete(int left,int num){
        for(int i=n-1;i>=0 && num>0;--i) if(wall[i].left<=left && wall[i].right!=-1){
            --num;
            delete(i);
        }
    }
    public int GetAns(){
        int ans=0;
        for(int i=0;i< N;++i){
            if(Graph[i]>k){
                ans+=Graph[i]-k;
                delete(i,Graph[i]-k);
            }
        }
        return ans;
    }
    
}
public class Main {
 public static void main(String[]args)throws Exception{
    int Test,n,k;
    Muraille muraille = new Muraille();
    StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    Test = GetNum(cin);
    while(Test--!=0){
        n = GetNum(cin);
     k = GetNum(cin);
     muraille.SetInit(n,k);
     for(int i=0;i< n;++i){
        int left = GetNum(cin);
        GetNum(cin);
        int right = GetNum(cin);
        GetNum(cin);
        if(left>right) muraille.AddData(right, left);
        else muraille.AddData(left, right);
    }
    
    muraille.InitData();
    System.out.println(muraille.GetAns());
  }
 }
    static int GetNum(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
}

							

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



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

 public class Main {

     class Point {
         int x;
         int y;

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

     public static void main(String[] args) throws NumberFormatException,
             IOException {
         Main main = new Main();
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int n = Integer.parseInt(read.readLine());
         Point[] p;
         Point[] ch;
         int x, y;
         String[] s;
         int len;
         int t;
         boolean b;
         for (int i = 0; i < n; i++) {
             int m = Integer.parseInt(read.readLine());
             p = new Point[m];
             for (int j = 0; j < m; j++) {
                 s = read.readLine().split(" ");
                 x = Integer.parseInt(s[0]);
                 y = Integer.parseInt(s[1]);
                 p[j] = main.new Point(x, y);
             }
             if (m <= 5) {
                 System.out.println("NO");
             } else {
                 ch = new Point[m];
                 len = 0;
                 len = Graham_scan(p, ch, m);
                 b = false;
                 t = 0;
                 for (int j = 0; j < len - 2; j++) {
                     if (!AtOneLine(ch[j], ch[j + 1], ch[j + 2])) {
                         b = true;
                         break;
                     }
                 }
                 if (b) {
                     for (int j = 0; j < len - 1; j++) {
                         for (int k = 0; k < m; k++) {
                             if (AtOneLine(ch[j], ch[j + 1], p[k])) {
                                 t++;
                             }
                         }
                         if (t < 3) {
                             b = false;
                             break;
                         }
                         t = 0;
                     }
                 }
                 if (b) {
                     System.out.println("YES");
                 } else {
                     System.out.println("NO");
                 }
             }
         }
     }

     public static boolean AtOneLine(Point p1, Point p2, Point p3) {
         return ((p1.x - p2.x) * (p1.y - p3.y) == (p1.x - p3.x) * (p1.y - p2.y));
     }

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

     }

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

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

							

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

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

class Main {
 public static void main(String[] args) throws Exception {
    new Main().run();
 }

 private int n;    

 private void run() throws Exception {
  Scanner cin = new Scanner(System.in);
  int ntc = cin.nextInt(),i,j,k;
  while(ntc-- != 0) {
    n = cin.nextInt();
    StringBuffer[] s = new StringBuffer[n];
    for(i = 0; i < n; ++i) {
        s[i] = new StringBuffer(cin.next());
    }
    int max = 0;
    for(i = 0; i < s[0].length(); ++i) {
      for(j = i+1; j <= s[0].length(); ++j) {
        if(check(s,i,j)) {
          max = Math.max(max,j-i);
        }
     }
    }
    System.out.println(max);
   }
}
    
boolean check(StringBuffer s[], int x, int y) {
  int i;
  String pattern1 = s[0].toString().substring(x, y);
  String pattern2 = "";
  for(i = pattern1.length()-1; i >= 0; --i) {
    pattern2 += pattern1.charAt(i);
  }
  for(i = 0; i < n; ++i) {
    if(s[i].toString().indexOf(pattern1) == -1
        && s[i].toString().indexOf(pattern2) == -1) {
        return false;
    }
  }
  return true;
 }
}
							

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

import java.util.Scanner; 

public class Main { 

    int times; 
    int[][] puzzle; 
    static final int length = 6; 
    static final int width = 5; 
    int[][] arr; 
    int temp; 
    int req; 

    public Main() { 
        Scanner scan = new Scanner(System.in); 
        times = scan.nextInt(); 
        for (int t = 0; t < times; t++) { 
            puzzle = new int[width][length]; 
            arr = new int[width][length]; 
            for (int i = 0; i < width; i++) { 
                for (int j = 0; j < length; j++) { 
                    puzzle[i][j] = scan.nextInt(); 
                } 
            } 
            force(); 
            System.out.println("PUZZLE #" + (t + 1)); 
            for (int i = 0; i < width; i++) { 
                for (int j = 0; j < length; j++) { 
                    System.out.print(arr[i][j] + " "); 
                } 
                System.out.println(); 
            } 
        } 
    } 

    //��ٵ�һ����ݣ��Ƶ���������... 
    //�ж����һ���Ƿ���Ҫ�� 
    //6����Ҫ������2^6=64�� 
    public void force() { 
        boolean result = false; 
        do { 
            result = search(); 
            if (result) { 
                return; 
            } 
        } while (plus(arr[0], 0)); 
    } 

    public boolean search() { 
        for (int i = 1; i < width; i++) { 
            for (int j = 0; j < length; j++) { 
                req = puzzle[i - 1][j]; 
                temp = 0; 
                if (j - 1 >= 0) { 
                    temp += arr[i - 1][j - 1]; 
                } 
                if (j + 1 < length) { 
                    temp += arr[i - 1][j + 1]; 
                } 
                if (i - 2 >= 0) { 
                    temp += arr[i - 2][j]; 
                } 
                temp += arr[i - 1][j]; 
                if (req != (temp % 2)) { 
                    arr[i][j] = 1; 
                } else { 
                    arr[i][j] = 0; 
                } 
            } 
        } 
        for (int i = 0; i < length; i++) { 
            req = puzzle[width - 1][i]; 
            temp = 0; 
            if (i - 1 >= 0) { 
                temp += arr[width - 1][i - 1]; 
            } 
            temp += arr[width - 2][i]; 
            temp += arr[width - 1][i]; 
            if (i + 1 < length) { 
                temp += arr[width - 1][i + 1]; 
            } 
            if (req != (temp % 2)) { 
                return false; 
            } 
        } 
        return true; 
    } 

    public boolean plus(int[] a, int b) { 
        if (b == length) { 
            return false; 
        } else if (a[b] == 0) { 
            a[b]++; 
            return true; 
        } else { 
            a[b] = 0; 
            return plus(a, ++b); 
        } 
    } 

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

} 

							

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

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

public class Main {
    static final int N = 500;
    static long DP[][] = new long[N][N];
    static void init(){
        int i,j;
        for(i=0;i< N;++i) for(j=0;j< N;++j) DP[i][j] = 0;
        for(i=1;i< N;++i){
            for(j=i;j>=0;--j)
                DP[i][j]=1;
        }
        for(i=0;i< N;++i) DP[0][i]=1;
        for(i=2;i< N;++i){
            for(j=i/2;j>=1;--j)
                DP[i][j] = DP[i-2*j][j]+DP[i][j+1];
        }
    }
  public static void main(String[]args) throws Exception{
    int n;
    init();
    //Scanner cin = new Scanner(new FileInputStream("input.txt"));
    Scanner cin = new Scanner(System.in);
    while(cin.hasNext()){
        n = cin.nextInt();
        if(n==0) break;
        System.out.println(n+" "+solve(n));
    }
  }
  static long solve(int n){
    return DP[n][1];
  }
}

							

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

import java.util.*;
import java.math.*;
public class Main {
    static int c2i(char c){
        if(c>='0'&&c<='9')
            return c-'0';
        if(c>='A'&&c<='Z')
            return c-'A'+10;
        return c-'a'+36;
    }
    static char i2c(int c){
        if(c< 10)
            return (char)(48+c);
        if(c>=10&&c< 36)
            return (char)('A'+c-10);
        return (char)('a'+c-36);
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        for(int k=0;k< t;k++){
            int a1=in.nextInt();
            int a2=in.nextInt();
            String s=in.next();
            System.out.println(a1+" "+s);
            System.out.print(a2+" ");
            BigInteger a=BigInteger.ZERO;
            for(int i=0;i< s.length();i++)
                a=a.multiply(BigInteger.valueOf(a1)).add(BigInteger.valueOf(c2i(s.charAt(i))));
            s="";
            while(!a.equals(BigInteger.ZERO)){
                s=i2c(a.mod(BigInteger.valueOf(a2)).intValue())+s;
                a=a.divide(BigInteger.valueOf(a2));
            }
            if(s.equals(""))
                s="0";
            System.out.println(s);
            System.out.println();
        }
    }

}
							

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

 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;
         String r;
         int time;
         char[] last;
         StringBuilder temp;
         char[] buff;
         int pos;
         boolean[] used;
         game: while (!(s = read.readLine()).equals("LINGO")) {
             if (s.equals("") || s == null) {
                 continue;
             }
             System.out.println();
             r = s;
             last = new char[] { '.', '.', '.', '.', '.' };
             last[0] = r.charAt(0);
             System.out.println(last);
             time = 1;
             turn: while (!(s = read.readLine()).equals("")) {
                 // check valid
                 if (s.length() != 5) {
                     System.out.println(last);
                     time++;
                     continue turn;
                 }
                 for (int i = 0; i < 5; i++) {
                     if (!Character.isUpperCase(s.charAt(i))) {
                         System.out.println(last);
                         time++;
                         continue turn;
                     }
                 }
                 // is right
                 if (s.equals(r)) {
                     System.out.println(r);
                     over(read);
                     continue game;
                 }
                 if (time == 6) {
                     System.out.println(r.toLowerCase());
                     over(read);
                     continue game;
                 }
                 // check
                 buff = new char[] { '.', '.', '.', '.', '.' };
                 temp = new StringBuilder(r);
                 used = new boolean[5];
                 for (int i = 0; i < 5; i++) {
                     if (r.charAt(i) == s.charAt(i)) {
                         buff[i] = s.charAt(i);
                         temp.setCharAt(i, ' ');
                         used[i] = true;
                     }
                 }
                 for (int i = 0; i < 5; i++) {
                     if (used[i]) {
                         continue;
                     }
                     if ((pos = temp.indexOf(s.charAt(i) + "")) != -1) {
                         buff[i] = Character.toLowerCase(s.charAt(i));
                         temp.setCharAt(pos, ' ');
                         used[i] = true;
                     }
                 }
                 System.out.println(buff);
                 last = buff;
                 time++;
             }
             if (time < 7) {
                 System.out.println(r.toLowerCase());
             }
         }
     }

     public static void over(BufferedReader read) throws IOException {
         while (!read.readLine().equals("")) {
         }
     }
} 

							

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

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

/** 
*poj1218 
* @author NC 
*/ 
public class Main { 

    public static void main(String[] args) { 
        Scanner scan = new Scanner(new BufferedInputStream(System.in)); 
        if (scan.hasNext()) { 
            int t = scan.nextInt(); 
            for (int i = 0; i < t; i++) { 
                int n = scan.nextInt(); 
                boolean[] cells = new boolean[n + 1]; 
                for (int j = 1; j < cells.length; j++) { 
                    cells[j] = false; 
                } 
                for (int j = 2; j <= n; j++) { 
                    for (int k = j; k <= n; k = k + j) { 
                        if (cells[k]) { 
                            cells[k] = false; 
                        } else { 
                            cells[k] = true; 
                        } 
                    } 
                } 
                int count = 0; 
                for (int k = 1; k <= n; k++) { 
                    if (!cells[k]) { 
                        count++; 
                    } 
                } 
                System.out.println(count); 
            } 
        } 
    } 
} 


							

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

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

public class Main{
    static Scanner cin;
    static MyList list;
    public static void main(String args[]){
        cin = new Scanner(System.in);
        int n = cin.nextInt();
        list = new MyList();
        for(int i = 0;i < n;i++)
            list.add(new Stack(new Integer(i)));
        
        
        while(true)
            if(run() == false)
                break;
        
        show();

        return;
    }
    
    static boolean run(){
        String command = cin.next();
        
        if(command.equals("quit"))
            return false;
        
        Integer a = new Integer(cin.nextInt());
        String scommand = cin.next();
        Integer b = new Integer(cin.nextInt());
        
        if(command.equals("move"))
            return move(a,b,scommand);
        else
            return pile(a,b,scommand);
    }
    
 static boolean move(Integer a,Integer b,String command){
    Stack A = list.contains(a);
    Stack B = list.contains(b);
    if(A == B)
        return true;
    
    if(command.equals("over")){
        B.add(a);
        A.removeSingle(a);
    }
    else{
        Iterator< Integer> iterator = B.getLast(b).iterator();
        while(iterator.hasNext())
            list.get(iterator.next()).selfadd();
        B.removeLast(b).add(a);
        A.removeSingle(a);
    }


        
    return true;    
   }
    
 static boolean pile(Integer a,Integer b,String command){
    Stack A = list.contains(a);
    Stack B = list.contains(b);
    if(A == B)
        return true;
        
    if(command.equals("over")){
        B.add(a).add(A.getLast(a));
        A.removeLast(a).removeSingle(a);
    }
    else{
        Iterator<Integer> iterator = B.getLast(b).iterator();
        while(iterator.hasNext())
            list.get(iterator.next()).selfadd();
        B.removeLast(b).add(a).add(A.getLast(a));
        A.removeLast(a).removeSingle(a);
    }
    return true;        
   }

    static void show(){
        for(Stack stack:list)
            stack.show();
    }
}


class Stack{
    ArrayList< Integer> contents;
    Integer n;
    public Stack(Integer n){
        this.n = n;
        contents = new ArrayList< Integer>();
        contents.add(n);
        return;
    }
    
    boolean contains(Integer value){
        for(Integer p:contents)
            if(p.equals(value))
                return true;
        return false;
    }
    
    Stack add(List< Integer> others){
        contents.addAll(others);
        return this;
    }
    void selfadd(){
        contents.add(n);
    }
    Stack add(Integer n){
        contents.add(n);
        return this;
    }
    
    Stack removeLast(Integer value){
        int num = contents.indexOf(value);
        int size = contents.size();
        for(int i = num+1;i < size;i++)
            contents.remove(num+1);
        return this;
    }
    Stack removeSingle(Integer value){
        contents.remove(value);
        return this;
    }
    
    List< Integer> getLast(Integer value){
        int num = contents.indexOf(value);
        return contents.subList(num+1,contents.size());
    }
    
    void show(){

        System.out.print(n+":");
        for(Integer p:contents)
            System.out.print(" "+p);
        System.out.println();
    }
    
    
}


class MyList extends ArrayList< Stack>{
    Stack contains(Integer value){
        for(Stack stack:this)
            if(stack.contains(value)){
                return stack;
            }
        return null;
    }
}
							

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

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

 public class Main {

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int t;
         int s;
         int[] len;
         String str;
         int start;
         int end;
         int max;
         len = new int[10000];
         for (int i = 1; i < 10000; i++) {
             s = 1;
             t = i;
             while (t != 1) {
                 if (t < 10000 && len[t] != 0) {
                     s += len[t] - 1;
                     break;
                 }
                 if (t % 2 == 1) {
                     t = 3 * t + 1;
                 } else {
                     t = t / 2;
                 }
                 s++;
             }
             len[i] = s;
         }
         while ((str = read.readLine()) != null && !str.equals("")) {
             start = Integer.parseInt(str.split(" ")[0]);
             end = Integer.parseInt(str.split(" ")[1]);
             max = 0;
             for (int i = Math.min(start, end); i <= Math.max(start, end); i++) {
                 if (len[i] > max) {
                     max = len[i];
                 }
             }
             System.out.printf("%d %d %dn", start, end, max);
         }
     } 
}

							

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

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

public class Main {
    public static void main(String[] args)
    {
        BigInteger a[]=new BigInteger[105];
        int i,k;
        BigInteger temp;
        a[1]=new BigInteger("1");
        for(i=2;i<=100;i++)
        {
            temp=new BigInteger("1");
            for(k=1;k< i;k++)
            {
                temp=temp.add(a[k]);
            }
            a[i]=temp.add(a[i-1]);
        }
        Scanner stdin=new Scanner(System.in);
        while(stdin.hasNext())
        {
            int n=stdin.nextInt();
            System.out.println(a[n]);
        }
    }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Intervals{
    int left,right,ci;
}
public class Main {
 static final int N = 50000+10;
 static int DP[] = new int[N],n,left,right;
 static Intervals Inter[] = new Intervals[N];
    
 static void start(){
    for(int i=0;i< N;++i)
        Inter[i] = new Intervals();
 }
 static int Get_Num(StreamTokenizer cin) throws Exception{
    if(cin.nextToken()==StreamTokenizer.TT_EOF)
        return -1;
    return (int) cin.nval;
 }

 static int solve(){
  int i,j;
  boolean flag=true;
  for(i=left;i<=right;++i)
     DP[i] = -N;
  DP[left] = 0;
  for(i=left;i<=right && flag;++i){
    flag = false;
   for(j=0;j< n;++j)if(DP[Inter[j].left]>-N && DP[Inter[j].left]+Inter[j].ci>DP[Inter[j].right]){
        DP[Inter[j].right]= DP[Inter[j].left]+Inter[j].ci ;
        flag = true;
    }
   for(j=left;j< right;++j) if(DP[j]>-N && DP[j]>DP[j+1]){
    DP[j+1] = DP[j];
    flag = true;
   }
   for(j=right;j>left;--j) if(DP[j]>-N && DP[j]-1>DP[j-1]){
    DP[j-1] = DP[j]-1;
    flag = true;
   }
  }
    return DP[right];
 }

 public static void main(String[]args) throws Exception{
  int i,j;
  start();
  StreamTokenizer cin =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
  while((n = Get_Num(cin))>0){
    left = N ; right = 0;
    for(i=0;i< n;++i){
          Inter[i].left = Get_Num(cin);
      Inter[i].right = Get_Num(cin)+1;
      Inter[i].ci = Get_Num(cin);
      left = Min(left,Inter[i].left);
      right = Max(right,Inter[i].right);
    }
    System.out.println(solve());
   }
        
 }

  static int Max(int a,int b){
    return a>b?a:b;
  }

  static int Min(int a,int b){
    return a< b?a:b;
  }
}

							

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

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

char str[20000000+10] ;
int sub, radix, ans, index[256] ;
bool hash[20000000+10] ;

// 转化为nc进制 
void Change()
{
    int i, cnt(0) ;
    for( i=0; ; ++i ){
        if( 0 == index[ str[i] ] )
            index[ str[i] ] = cnt++ ;
        if( cnt == radix )
            break ;
    }
}

void KR()
{
    __int64 i, sum(0), p, up ;
    p = (__int64)pow( (double)radix, sub-1.0 ) ;
    //printf("  pow, %dn", p ) ;
    for( i=0; i<sub; ++i ){
        sum *= radix ;
        sum += index[ str[i] ] ;
    }
    hash[sum] = true ;
    ans = 1 ;
    up = strlen( str )-sub ;
    for( i=0; i<=up; ++i ){
        if( false == hash[sum] ){
            hash[sum] = true ;
            ++ans ;
        }
        // 用KR的思想来计算，比较节省时间。 
        sum = radix*( sum- index[ str[i] ]*p ) + index[ str[i+sub] ] ;
    }
}

int main()
{
    scanf("%d%d%s", &sub, &radix, str ) ;
    Change() ;
    KR() ;
    printf("%dn", ans ) ;
    return 0 ;
}
							

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

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

  static int x[];
  static int y[];
  static int c[];
  static int ans=0;

static int search(int i,int parent)
{
    int ret=0,t;
    for(int j=0;j< n;j++)
    {
        if(parent!=j&&Math.abs(x[i]-x[j])+Math.abs(y[i]-y[j])==1)
        {
            t=search(j,i);
            if(t>0)ret+=t;
        }
    }
    if(ret+c[i]>ans)ans=ret+c[i];
    return ret+c[i];
}

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
   n=sc.nextInt();
   x=new int[n];
   y=new int[n];
   c=new int[n];
    for(int i=0;i< n;i++){
      x[i]=sc.nextInt();
      y[i]=sc.nextInt();
      c[i]=sc.nextInt();
    }
       
    search(0,-1);
    System.out.println(ans);
   }
}

							

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

/* @author: */
import java.util.Scanner;
public class Main {
static int end,min;   
static int M,S;
static int dfs(int v,int m,int lastr,int lasth)   
{   
    if(m==0)   
    {   
        //������Ϊ0ʱ��ʣ�����Ϊ0,˵��˴�����ɹ�,Ӧ����   
        if(v>0||v< 0)   
            return 0;   
        else  
        {   
            //Ϊ0,����Ŀ���н�,�жϵ�ǰ�������Ƿ���Ѿ��õ�����С���С,��С���û�.   
            end=1;   
            if(min< S)   
                S=min;   
            return 0;   
        }   
    }   
    int i,t=0,j,k,temp;   
    //����m���������   
    for(i=1;i<=m;i++)   
        t+=i*i*i;   
    //��ǰ������С���С,����   
    if(v< t)   
        return 0;   
    t-=m*m*m;   
    int maxr,maxh;   
    //���㵱ǰ��ײ����ܹ��ﵽ�����뾶.   
    maxr=(int)Math.sqrt((v-t)*1.0/m)< lastr?(int)Math.sqrt((v-t)*1.0/m):lastr;   
    for(i=maxr;i>=m;i--)   
    {   
        //����ȷ���뾶��������ܹ��ﵽ�����߶�   
        maxh=(v-t)/(i*i)< lasth?(v-t)/(i*i):lasth;   
        //����   
        for(j=maxh;j>=m;j--)   
        {   
            temp=0;   
            //��ݵ�ǰ��ײ�ȷ��m�㵰���ܴﵽ��������.   
            for(k=0;k<=m-1;k++)   
                temp+=(i-k)*(i-k)*(j-k);   
            //���������,�϶�����ʣ��,����   
            if(v>temp)   
                break;   
            int tempv=v-i*i*j;   
            //��һ��ʱҪ�����ϱ�������   
            if(m==M)   
            {   
                if(i*i< S)   
                min=i*i;   
                else  
                {   
                    tempv=v;   
                    continue;   
                }   
            }   
            //���ϲ����,��ÿһ�㶼����   
            min+=2*i*j;   
            //��ǰ�õ�������Ѿ�������֪����С������,����ľͲ�����������,ֱ�ӷ���   
            if(min>S)   
            {   
                tempv=v;   
                min-=2*i*j;   
                continue;   
            }   
            dfs(tempv,m-1,i-1,j-1);   
            //���ݺ�Ҫ�ָ����   
            min-=2*i*j;   
        }   
    }   
    return 0;   
}   

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
 ///��������,�����Լ����֦�Ż�   
//S��ʾ��С���   
int N;   
//end��ʼΪ0,�н����Ϊ1.min��4��ʾÿ�γɹ�����ʱ�����������   
//v��ʾ��ǰʣ������,m��ʾʣ�൰��IJ���,lastr��ʾ�Ѿ�ȷ������һ�㵰��İ뾶,lasthͬ��   
    
    while(sc.hasNext())   
    {  
       N=sc.nextInt();
       M=sc.nextInt();
 
        int t=0;   
        end=0;   
        S=100000;   
        dfs(N,M,1000,1000);   
        if(end==0)   
            S=0;   
        System.out.printf("%dn",S);   
    }   
   }
}  

							

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

/* @author: */
import java.util.*;
public class Main {
static long gcd(long a,long b)//����a,b�����Լ��
{
        if(b==0)
           return a;
        else
           return gcd(b,a%b);
}

public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
    
    int m,n;
    long d,tmp;
        n=sc.nextInt();
        m=sc.nextInt();
       char ss[][]=new char[n][];
       long dp[][]=new long[n+1][];

        for(int i=0;i< n;i++){
           ss[i]=new char[i+1];
          for(int j=0;j< i+1;j++)  
           ss[i][j]=sc.next().charAt(0);
         
       }
        for(int i=0;i<=n;i++)
         dp[i]=new long[i+1];

        dp[0][0]=1l<< n;
        for(int i=1;i<=n;i++){
         for(int j=0;j< i;j++)
         {
            if(ss[i-1][j]=='*')
            {
                tmp=dp[i-1][j]>>1;
                dp[i][j]+=tmp;
                dp[i][j+1]+=tmp;
            }
            else                                                                        
                dp[i+1][j+1]+=dp[i-1][j];
         }
     
        }
        
         d=gcd(dp[n][m],dp[0][0]);
         System.out.printf("%d/%dn",dp[n][m]/d,dp[0][0]/d);

            
   }
}
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int mins=Integer.MIN_VALUE;
 static int maxs=Integer.MAX_VALUE;

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

static int max(int a,int b)
{
    return a>=b?a:b;   
}

 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
    int n,i; 
    while(sc.hasNext())
    {
       n=sc.nextInt();
       if(n==0)
         break;
       int startx=mins;
       int starty=mins;
       int startz=mins;
       int stopx=maxs;
       int stopy=maxs;
       int stopz=maxs;
       int x,y,z,len,h=0; 
       for(i=0;i< n;i++)
       {
          x=sc.nextInt();
          y=sc.nextInt();
          z=sc.nextInt();
          len=sc.nextInt();
           if(h==1)
             continue;   
           startx=max(startx,x);
           starty=max(starty,y);
           startz=max(startz,z);
           x=x+len;
           y=y+len;
           z=z+len;
           stopx=min(stopx,x);
           stopy=min(stopy,y);
           stopz=min(stopz,z);
           if(startx>=stopx || starty>=stopy || startz>=stopz)
              h=1;               
       }
       if(h==0)
       {
           System.out.println((stopx-startx)*(stopy-starty)*(stopz-startz));        
       }   
       else
         System.out.println("0");  
    }
   }
}


							

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

//* @author: 
import java.util.*;
public class Main {
  static int s[][][][]=new int[31][11][11][11];

static int get( int d, int l1, int l2, int l3 )
{
    int t, j, k, i, h;
    
    if( l1 == 0 && l2 == 0 && l3 == 0 && d >= 0 )
        return 1;
    
     if( d <= 0 )
        return 0;
        
    if( ( t = s[d][l1][l2][l3] ) >= 0 )
        return t;
        
    t = 0;
    
    if( d == 1 )
    {
        if( l1!=0 ) t += get( d, l1-1, l2, l3 );
        if( l2!=0 ) t += get( d, l1, l2-1, l3 );
        if( l3!=0 ) t += get( d, l1, l2, l3-1 );
         
         t %= 11380;
          s[d][l1][l2][l3] =  t;
        return t ;
    }    
    
     for( i=0; i<=l1-1; i++ )
    for( j=0; j<=l2; j++ )
     for( k=0; k<=l3; k++ )
      {
           t += ( get( d-1, i, j, k ) * get( d, l1-1-i, l2-j, l3-k ) );
        if( t > ( 1 << 30 ) ) t %= 11380;
    }    
      
    for( j=0; j<=l2-1; j++ )
    for( k=0; k<=l3; k++ )
    {
         t += ( get( d-1, 0, j, k ) * get( d, l1, l2-1-j, l3-k ) );
          if( t > ( 1 << 30 ) ) t %= 11380;
       }       
    
    for( k=0; k<=l3-1; k++ )
    {
         t += ( get( d-1, 0, 0, k ) * get( d, l1, l2, l3-1-k ) );
          if( t > ( 1 << 30 ) ) t %= 11380;
       }       

    t %= 11380;
    s[d][l1][l2][l3] = t;
    
    return t;
}

 public static void main(String[] args){

    Scanner in = new Scanner(System.in);
    int d, l1, l2, l3, i, j, k, l;
      l1=in.nextInt();
      l2=in.nextInt();
      l3=in.nextInt();
      d=in.nextInt();
    
     for( l=0; l<=d; l++ )
     for( i=0; i<=l1; i++ )
     for( j=0; j<=l2; j++ )
     for( k=0; k<=l3; k++ )
         s[l][i][j][k] = -1;
    System.out.printf( "%dn", ( get( d, l1, l2, l3 ) - get( d-1, l1, l2, l3 ) + 11380 ) % 11380 );
    
    }
 }    

							

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

//* @author:
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Scanner;
public class Main
{
 static int[]k=new int[6];
 static int[]p=new int[6];
 static int n,m,mark;
 static int total;
 static Hashtable< Long,Integer>hash=new Hashtable< Long,Integer>();
 public static void main(String[] args)
 {
    int i,j;
    Scanner cin=new Scanner(System.in);
    while(cin.hasNext())
    {
        hash.clear();
     total=0;
     n=cin.nextInt();
     m=cin.nextInt();
     for(i=0;i< n;i++)
     {
       k[i]=cin.nextInt();
       p[i]=cin.nextInt();
      }
    mark=n/2;
    dfs(0,0);
    dfs2(mark,0);
    System.out.println(total);
      }        
   }

  static void dfs(int pos,long sum)
  {
   if(pos==mark)
   {
    sum*=-1;
    if(hash.containsKey(sum))
    {
       hash.put(sum,hash.get(sum)+1);
    }
    else
      hash.put(sum,1);
    return;
    }
    int i,j;
    long tmp;
    for(i=1;i<=m;i++)
    {
    tmp=(long)k[pos];
    for(j=0;j< p[pos];j++)
    {
       tmp*=i;
    }
    dfs(pos+1,sum+tmp);
     }
  }

 static void dfs2(int pos,long sum)
 {
   if(pos>=n)
   {
    if(hash.containsKey(sum))
    {
        total+=hash.get(sum);
    }
    return;
    }
   int i,j;
   long tmp;
   for(i=1;i<=m;i++)
   {
    tmp=(long)k[pos];
    for(j=0;j< p[pos];j++)
    {
         tmp*=i;
    }
    dfs2(pos+1,sum+tmp);
    }
        
  }
}
							

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

//* @author: 
/*��Ŀ������һ��n*m�ķ����з����ڱ�Ҫ�����ڣ���û���ڱ�������ܷŶ���
 *��ʼ��Ϊû���뵽�õķ�������������һ�Σ�tle...
 *֪���й���״̬ѹ����㷨���ɲ�̫�����һֱ����û����쿴��һ��״̬ѹ��ģ��㷨
 *������д����4���������ڣ�c..
 *״̬ѹ����λ4��ʾ״̬������λ�����ʡʱ�䣨���Ǻ�����ᣩ
 *ö��״̬������״̬ת�ƴӶ�õ����Ž⣬��Ϊ״̬ѹ��DP...
 */

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

class cin
{
 static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 static StringTokenizer st;
 static int leave=0;
 static int nextInt()throws IOException
 {
  return Integer.parseInt(next());
 }
 static String next() throws IOException
 {
  while(leave==0)
  {
   st=new StringTokenizer(in.readLine());
   leave=st.countTokens();
  }
  leave--;
  return st.nextToken();
 }
 static boolean hasNext() throws IOException
 {
  while(leave==0)
  {
   String temp=in.readLine();
   if(temp==null)return false;
   st=new StringTokenizer(temp);
   leave=st.countTokens();
  }
  return true;
 }
}

class Dp
{
 int s[],r[][],c[][],f[][][],n,m;
 int x[],top=0;
 String board[];
 static int v[]={1,2,4,8,16,32,64,128,256,512};
 Dp(String b[],int n,int m)
 {
  board=b;
  this.n=n;
  this.m=m;
  s=new int[61];
  x=new int[m];
 }
 
 void dfs(int t)//����s[]
 {
  int i;
  if(t>=m)
  {
   s[top]=0;
   for(i=0;i< m;i++)
   {
    s[top]+=v[i]*x[i];
   }
   top++;
  }
  else
  {
   if(place(t))
   {
    x[t]=1;
    dfs(t+1);
   }
   x[t]=0;
   dfs(t+1);
  }
 }
 
 boolean place(int t)
 {
  if(t-2>=0&&x[t-2]==1||t-1>=0&&x[t-1]==1)return false;
  return true;
 }
 
 int getC(int x)//x�к�1�ĸ���
 {
  int sum=0;
  while(x>0)
  {
   sum+=(x%2);
   x>>=1;
  }
  return sum;
 }
 
 void init() //��ʼ����״̬
 {
  dfs(0);
  int i,j,temp;
  r=new int[n][top];
  c=new int[n][top];
  for(i=0;i< n;i++)
  {
   temp=0;
   for(j=0;j< m;j++)
   {
    if(board[i].charAt(j)=='P')temp+=v[j];
   }
   for(j=0;j< top;j++)
   {
    r[i][j]=temp&s[j];
    c[i][j]=getC(r[i][j]);
//    System.out.println(r[i][j]+" "+c[i][j]);
   }
  }
  f=new int[n][top][top];
 }
 
 int findMax()//�������Ž�
 {
  int i,j,k,max,h;
  for(i=0;i< top;i++)
  {
   for(j=0;j< top;j++)
   {
       f[0][i][j]=c[0][i];
   }
  }
  if(n>1)
  {
   for(i=0;i< top;i++)
   {
    
    for(j=0;j< top;j++)
    {
     max=0;
     for(k=0;k< top;k++)
     {
      if((r[1][i]&r[0][j])==0&&max< f[0][j][k])
      {
       max=f[0][j][k];
      }
     }
     f[1][i][j]=max+c[1][i];
    }
   }
  }
  for(k=2;k< n;k++)
  {
   for(h=0;h< top;h++)
   {
    for(i=0;i< top;i++)
    {
     max=0;
     for(j=0;j< top;j++)
     {
      if((r[k][h]&r[k-1][i])==0&&(r[k-1][i]&r[k-2][j])==0&&(r[k][h]&r[k-2][j])==0&&max< f[k-1][i][j])
      {
       max=f[k-1][i][j];
      }
     }
     f[k][h][i]=max+c[k][h];
    }
    
   }
  }
  max=0;
  for(i=0;i< top;i++)
  {
   for(j=0;j< top;j++)
   {
    if(max< f[n-1][i][j])
     max=f[n-1][i][j];
   }
  }
  return max;
 }
 
 void out()
 {
  init();
  System.out.println(findMax());
 }
}

public class Main {
    public static void main(String args[]) throws IOException
    {
     int n,m,i;
     String str[];
     Dp data;
     n=cin.nextInt();
     m=cin.nextInt();
     str=new String[n];
     for(i=0;i< n;i++)
     {
      str[i]=cin.next();
     }
     data=new Dp(str,n,m);
     data.out();
    }
}
							

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

//* @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)));
  long a=scanner.nextInt();
  long m=1;
  for (long i=a;i>=1 ;i-- ){
   if ((a*a+1)%i==0){
    m=i;
    break;
   }
  }
  System.out.println(2*a+m+(a*a+1)/m);
 }
}


							

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

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Main poj = new Main();

        BufferedReader read = new BufferedReader(new InputStreamReader(
                System.in));
        String[] tm = read.readLine().split(" ");

        int N = new Integer(tm[0]);
        int K = new Integer(tm[1]);
        poj.initial(N);
        int i = 0;
        int count = 0;
        if (K == 0)
            System.out.println(count);
        while (++i <= K) {
            String[] tmp = read.readLine().split(" ");
            int kind = new Integer(tmp[0]);
            int animalA = new Integer(tmp[1]);
            int animalB = new Integer(tmp[2]);

            if (animalA > N || animalB > N) {
                count++;
                continue;
            }
            if (animalA == animalB) {
                if (kind == 2)
                    count++;
                continue;
            }
            int fa = poj.find(animalA);
            int fb = poj.find(animalB);

            if (fa == fb) {
                if (kind == 1) {
                    if (poj.mod[animalA] != poj.mod[animalB])
                        count++;
                } else {
                    if ((poj.mod[animalA] + 1) % 3 != poj.mod[animalB] % 3)
                        count++;
                }
            } else
                poj.union(animalA, animalB, kind);
        }
        read.close();
        System.out.println(count);
    }

    int[] parent;
    int[] mod;

    void union(int x, int y, int kind) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            if (mod[x] < mod[y]) {
                parent[fx] = fy;
                if (kind == 2)
                    mod[fx] = (mod[y] - mod[x] - 1 + 3) % 3;
                else
                    mod[fx] = (mod[y] - mod[x]) % 3;
            } else {
                parent[fy] = fx;
                if (kind == 2)
                    mod[fy] = (mod[x] - mod[y] + 1) % 3;
                else
                    mod[fy] = (mod[x] - mod[y]) % 3;
            }
        }

    }

    int find(int x) {
        if (x == parent[x])
            return parent[x];
        else {
            int t = parent[x];
            parent[x] = find(parent[x]);
            mod[x] = (mod[x] + mod[t]) % 3;
        }
        return parent[x];
    }

    void initial(int n) {
        parent = new int[n + 1];
        mod = new int[n + 1];
        for (int i = 1; i < n + 1; i++)
            parent[i] = i;
    }
}
							

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

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

static int dis[][][][]=new int[8][8][8][8];
static int x[]=new int[64],y[]=new int[64], n;

static void floyd()
{
    int i1, i2, i3, j1, j2, j3, t;
    
    for( i1=0; i1< 8; i1++ )
    for( j1=0; j1< 8; j1++ )
    for( i2=0; i2< 8; i2++ )
    for( j2=0; j2< 8; j2++ )
    for( i3=0; i3< 8; i3++ )
    for( j3=0; j3< 8; j3++ )
        if( ( t = dis[i2][j2][i1][j1] + dis[i1][j1][i3][j3] ) < dis[i2][j2][i3][j3] )
            dis[i2][j2][i3][j3] = t;
}


static void init()
{
    char w[]=new char[200];
    int i,i1,i2,j1,j2;
    Scanner in = new Scanner(System.in);
     w=in.next().toCharArray();
    
    for( i=0; i< w.length-1; i+= 2 ){
        x[i/2] = w[i] - 'A';
         y[i/2] = w[i+1] - '1';
       }
    
     n = i / 2;
        
    for( i1=0; i1< 8; i1++ )
    for( j1=0; j1< 8; j1++ )
    for( i2=0; i2< 8; i2++ )
    for( j2=0; j2< 8; j2++ )
     if( ( Math.abs( i1 - i2 ) == 2 && Math.abs( j1 - j2 ) == 1  ) || ( Math.abs( i1 - i2 ) == 1 && Math.abs( j1 - j2 ) == 2 ) )
             dis[i1][j1][i2][j2] = 1;
           else if( i1 == i2 && j1 == j2 ) dis[i1][j1][i2][j2] = 0;
        else dis[i1][j1][i2][j2] = 999; 
    
     floyd();
}

static void doit()
{
    int i1, i2, j1, j2, k, ans, t, temp, h;    
    
    ans = 99999;
    for( i1=0; i1< 8; i1++ )
    for( j1=0; j1< 8; j1++ )
    {
        temp = 0;
        for( k=1; k< n; k++ )
            temp += dis[x[k]][y[k]][i1][j1];
        
        for( k=1; k< n; k++ )
        {
          t = temp - dis[x[k]][y[k]][i1][j1];
            
          for( i2=0; i2< 8; i2++ )
           for( j2=0; j2< 8; j2++ )
           {
            h = t + dis[x[k]][y[k]][i2][j2] + dis[i2][j2][i1][j1] + 
           ( Math.abs( x[0]-i2 ) > Math.abs( y[0]-j2 ) ? Math.abs( x[0]-i2 ) : Math.abs( y[0]-j2 ) );
                
           if( h < ans ) ans = h;
          }
             
          }
       }
    
    System.out.printf( "%dn", ans );
}

 public static void main(String[] args){

    init();
    doit();
 }               
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
 static final int N = 1000+10;
 static int top,ans;
 static String opt = new String();
 static String str[] =new String[N];
 static int score[]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
    
 public static void main(String[]args)throws Exception{
    
  top = ans = 0;
    
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
  opt = next_string(cin);
    
  while(true){
    str[top] = next_string(cin);
    if(str[top].equals(".")) break;
    if(can_save(opt,str[top])) {
            
          ans = Max(ans,get_score(str[top]));
      ++top;
    }
   }
  for(int i=0;i< top;++i){
    for(int j=i+1;j< top;++j){
        str[top+1] = add(str[i],str[j]);
        if(can_save(opt,str[top+1])){
            ans = Max(ans,get_score(str[top+1]));
        }
    }
  }
  System.out.println(ans);
        
 }
    static String add(String obj1,String obj2){
        char temp[] = new char[20];
        String cnt = obj1+obj2;
        temp = cnt.toCharArray();
        Arrays.sort(temp,0,cnt.length());
        
        return String.valueOf(temp);
        
    }
    static int get_score(String op1){
        int i,cnt=0,n=op1.length();
        for(i=0;i< n;++i){
            cnt+=score[(int)(op1.charAt(i)-'a')];
        }
        return cnt;
    }
    static int Max(int a,int b){
        return a>b?a:b;
    }
    static boolean can_save(String op1,String op2){
        
        int i=0,j=0,n =op1.length(),m=op2.length();
        while(i< n && j< m){
            if(op1.charAt(i)==op2.charAt(j)){
                ++i;++j;
            }else{
                ++i;
            }
        }
        if(j< m) return false;
        
        return true;
    }
    static String next_string(StreamTokenizer cin) throws Exception{
        char temp[] = new char[10];
        String cnt = new String();
        cin.nextToken();
        cnt = cin.sval;
        if(cnt==null) return ".";
        temp = cnt.toCharArray();
        Arrays.sort(temp,0,cnt.length());

        return String.valueOf(temp);
        

    }
}

							

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

/* @author: */
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  int arr[]=new int[9];
  int ans[]=new int[9];
  int i=0;
  for(i=0;i< 9;i++)
    arr[i]=sc.nextInt();
  int a1,a2,a3,a4,a5,a6,a7,a8,a9,cnt;
  int u[]=new int[9];
  int min=100;
  for(a1=0;a1< 4;a1++)
   for(a2=0;a2< 4;a2++)
    for(a3=0;a3< 4;a3++)
     for(a4=0;a4< 4;a4++)
      for(a5=0;a5< 4;a5++)
    for(a6=0;a6< 4;a6++)
     for(a7=0;a7< 4;a7++)
      for(a8=0;a8< 4;a8++)
       for(a9=0;a9< 4;a9++)
          {
         cnt=a1+a2+a3+a4+a5+a6+a7+a8+a9;

            u[0]=arr[0]+a1+a2+a4;
            u[1]=arr[1]+a1+a2+a3+a5;
         u[2]=arr[2]+a2+a3+a6;
            u[3]=arr[3]+a1+a4+a5+a7;
            u[4]=arr[4]+a1+a3+a5+a7+a9;
            u[5]=arr[5]+a3+a5+a6+a9;
            u[6]=arr[6]+a4+a7+a8;
            u[7]=arr[7]+a5+a7+a8+a9;
            u[8]=arr[8]+a6+a8+a9;
            for(i=0;i<9;i++)
        if(u[i]%4!=0)break;
          if(i==9&&cnt< min)
          {
           ans[0]=a1;
           ans[1]=a2;
           ans[2]=a3;
           ans[3]=a4;
           ans[4]=a5;
           ans[5]=a6;
           ans[6]=a7;
           ans[7]=a8;
           ans[8]=a9;
           min=cnt;
          }
       }
         boolean bb=false;
      for(i=0;i< 9;i++)
      {
       if(ans[i]==0) continue;
        for(int j=0;j< ans[i];j++)
        {
         if(bb) System.out.printf(" ");
         bb=true;
         System.out.printf("%d",i+1);
       }
    }
    }
}
							

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

//* @author: 
import java.util.*;
public class Main {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int sum=in.nextInt();
  int lefttop=in.nextInt();
  cnt=new int[11][11][11][11][11];
  for (int i = 0; i < cnt.length; i++) {
   for (int j = 0; j < cnt.length; j++) {
    for (int k = 0; k < cnt.length; k++) {
    for (int l = 0; l < cnt.length; l++) {
      Arrays.fill(cnt[i][j][k][l], 0);
    }
    }
   }
  }
  for (int i = 10000; i < 100000; i++) {
    if(isPrime(i)&&dsum(i)==sum)
    {
    int[]x=new int[]{i/10000,i%10000/1000,i%1000/100,i%100/10,i%10};
    for (int j = 0; j < 1<< 5; j++) {
      int[]y=new int[]{10,10,10,10,10};
      for (int k = 0; k < 5; k++) {
       int mark=1<< k;
       mark&=j;
       if(mark==0)
       {
        y[k]=x[k];
        }
      }
    cnt[y[0]][y[1]][y[2]][y[3]][y[4]]++;
       }
      }
    }
    sq=new int[5][5];
    for (int[] is : sq) {
     Arrays.fill(is, 10);
    }
    sq[0][0]=lefttop;
    list=new int[][]{{2,2},{0,4},{1,1},{1,3},{3,1},{3,3},{4,0},{4,4},
      {0,1},{0,2},{0,3},{1,0},{1,2},{1,4},{2,0},{2,1},{2,3},{2,4},{3,0},{3,2},{3,4},{4,1},{4,2},{4,3}};
    res=new ArrayList< Res>();
    dfs(0,24);
    Collections.sort(res);
    for (int i = 0; i < res.size(); i++) {
    for (int j = 0; j < 5; j++) {
       System.out.println(res.get(i).r[j]);
    }
    System.out.println();
     }
    }
    
  static class Res implements Comparable< Res>
  {
    int r[];
        
    @Override
    public int compareTo(Res o) {
    if(r[0]==o.r[0])
       {
       if(r[1]==o.r[1])
       {
         if(r[2]==o.r[2])
         {
        if(r[3]==o.r[3])
         {
          return r[4]-o.r[4];
          }
        else return r[3]-o.r[3];
          }
          else return r[2]-o.r[2];
        }
        else return r[1]-o.r[1];
       }
     else return r[0]-o.r[0];
     }

 public Res(int[] r) {
    super();
    this.r = r;
  }
}
    
 static int[][]sq;
 static int[][]list;
 static int[][][][][]cnt;
 static ArrayList< Res> res;
    
 static void dfs(int i,int n)
 {
   if(i==n)
    {
    int[]r=new int[]{0,0,0,0,0};
    for (int j = 0; j < 5; j++) {
      for (int k = 0,l=10000; k < 5; k++,l/=10) {
        r[j]+=sq[j][k]*l;
      }
    }
    res.add(new Res(r));
     }
    else
    {
    int x=list[i][0],y=list[i][1];
    if(sq[x][y]!=10)dfs(i+1,n);
    else
    {
      for (int j = 0; j < 10; j++,sq[x][y]=10) {
       sq[x][y]=j;
       if(cnt[sq[x][0]][sq[x][1]][sq[x][2]][sq[x][3]][sq[x][4]]==0)continue;
       if(cnt[sq[0][y]][sq[1][y]][sq[2][y]][sq[3][y]][sq[4][y]]==0)continue;
       if(x==y&&cnt[sq[0][0]][sq[1][1]][sq[2][2]][sq[3][3]][sq[4][4]]==0)continue;
       if(x+y==4&&cnt[sq[4][0]][sq[3][1]][sq[2][2]][sq[1][3]][sq[0][4]]==0)continue;
        dfs(i+1,n);
       }
      }
     }
    }
    
  static int dsum(int i)
   {
    return i/10000+i%10000/1000+i%1000/100+i%100/10+i%10;
   }

   static boolean isPrime(int number)
    {
        if (number < 2) return false;
        if (number == 2) return true;
        if (number % 2 == 0) return false;
        for (int i = 3; i * i <= number; i += 2)
            if (number % i == 0) return false;
        return true;
    }
}

							

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

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int mat[55][55];
int num;

bool vist[55][55];

void DFS(int x,int y)
{
     num++;
     vist[x][y]=true;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的西方
     {
         if(!vist[x][y-1])
            DFS(x,y-1);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的北方
     {
         if(!vist[x-1][y])
             DFS(x-1,y);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的东方
     {
         if(!vist[x][y+1])
             DFS(x,y+1);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的南方
     {
         if(!vist[x+1][y])
             DFS(x+1,y);
     }
}

int main()
{
    int i,j,r,c,room,area;
    while(scanf("%d%d",&r,&c)!=EOF)
    {
        for(i=0;i<r;i++)
         for(j=0;j<c;j++)
           scanf("%d",&mat[i][j]);
        room=area=0;
        memset(vist,0,sizeof(vist));
        for(i=0;i<r;i++)
         for(j=0;j<c;j++)
          if(!vist[i][j])
          {
              room++;
              num=0;
              DFS(i,j);
              if(area<num)
                 area=num;
          }
        printf("%dn",room);
        printf("%dn",area);
    }
    system("pause");
    return 0;
}

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int num[]=new int[302];
 static int s[][]=new int[302][302];

 static void cost(int n){
     int i,j,k;
     for(i=1;i< n;i++){
         for(k=i+1; k <= n; k ++){
            int mid=(i+k)/2;
            for(j=i;j< mid;j++) s[i][k]+=num[mid]-num[j];
            for(j=mid+1;j<=k;j++) s[i][k]+=num[j]-num[mid];
         }
      }
 }

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
     int f[][]=new int[302][32];
     int n,k;

     int i,j,m;
     for(i=0;i< s.length;i++)
          Arrays.fill(s[i],0);
     for(i=0;i< f.length;i++)
          Arrays.fill(f[i],1000000);
     n=sc.nextInt();
     m=sc.nextInt();
    
     for(i=1;i<=n;i++)
        num[i]=sc.nextInt();
     cost(n);
     for(i=1;i<=n;i++) f[i][1]=s[1][i];
     for(k=2;k<=m;k++){
         for(i=1;i<=n;i++){
            for(j=1;j< i;j++)
                 if(f[j][k-1]+s[j+1][i]< f[i][k]) f[i][k]=f[j][k-1]+s[j+1][i];        
         }                  
     }
     System.out.printf("%dn",f[n][m]);
    }
}
							

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


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

public class Main {

 public static void main(String[] args) throws Exception{
    BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
    int total = Integer.parseInt(in.readLine());
    String string = in.readLine();
        System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString()));
}

//����}��string��lcs�ij���
public static int LCS(String str1,String str2){
    short length1 = (short)str1.length();
    short length2 = (short)str2.length();
    short[][]result = new short [length1+1][length2+1];
    for(int i=0;i< length1;i++){
        result[i][0] = 0;
    }
    for(int i=0;i< length2;i++){
        result[0][i] = 0;
    }
    for(int i=1;i<=length1;i++){
      for(int j=1;j<=length2;j++){
        if(str1.charAt(i-1)==str2.charAt(j-1))
         result[i][j] = (short)(result[i-1][j-1]+1);
        else
         result[i][j] = result[i-1][j]>result[i][j-1]?result[i-1][j]:result[i][j-1];
        }
    }
    return result[length1][length2];
 }
    

}


							

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

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;

int n, begin, end;
int b[300], p[300], sum[300];
int r[300];

typedef pair<int,int> p_i;

bool s[300][30000];

vector< p_i > e[300];
struct cmp {
    bool operator()( const p_i &a, const p_i &b ) const {
        return a.second > b.second;
    }
};

priority_queue< p_i, vector<p_i>, cmp > q;

void input( ) {
    int i, v, m, y, x;
    char c[2];
    scanf( "%d%d", &begin, &end );
    begin--, end--;

    scanf( "%d%d", &n, &m );
    for( i=0; i<n; i++ ) {
        scanf( "%1s%d%d%d", c, r+i, b+i, p+i );
        if( c[0] == 'P' )
            r[i] = b[i]+p[i]-r[i];
        else
            r[i] = b[i]-r[i];
        sum[i] = b[i]+p[i];
    }

    for( i=0; i<m; i++ ) {
        scanf( "%d%d%d", &x, &y, &v );
        e[x-1].push_back( p_i( y-1, v ) );
        e[y-1].push_back( p_i( x-1, v ) );
    }
}

int main( ) {
    int i, x, t, y, tt;

    input();

    q.push( p_i( begin, 0 ) );

    while( !q.empty() ) {
        x = q.top().first;
        t = q.top().second;
        
        if( x == end )
            break;
        
        if( t > n*200 ) {
            t = 0;
            break;
        }

        q.pop();

        if( !s[x][t+1] ) {
            q.push( p_i( x, t+1 ) );
            s[x][t+1] = true;
        }


        for( i=0; i<e[x].size(); i++ ) {
            y = e[x][i].first;
            if( !s[y][tt=t+e[x][i].second] && ((t+r[x])%sum[x]>=b[x]) == ((t+r[y])%sum[y]>=b[y]) ) {
                s[y][tt] = true;
                q.push( p_i( y, tt ) );
            }
        }
    }

    if( q.empty() )
        printf( "0n" );
    else
        printf( "%dn", t );

    return 0;
}


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    static boolean[][] p;
    static int sz;
    static String[] ss;
    public static void main(String[] args) throws IOException
    {
        InputStreamReader is=new InputStreamReader(System.in);
        BufferedReader in=new BufferedReader(is);
        String[] ss=in.readLine().split(" ");
        int a=Integer.parseInt(ss[0]);
        int b=Integer.parseInt(ss[1]);
        int[][] p=new int[a][b];
        int[][] c=new int[a][b];
        for(int i=0;i< a;i++)
        {
            ss=in.readLine().split(" ");
            for(int j=0;j< b;j++)
                p[i][j]=Integer.parseInt(ss[j]);
        }
        for(int j=0;j< b;j++)
            c[0][j]=p[0][j];
        for(int i=1;i< a;i++)
        {
            for(int j=i;j< b;j++)
            {
                int max= -9999999;
                for(int k=0;k< j;k++)
                    if(max< c[i-1][k])max=c[i-1][k];
                c[i][j]=p[i][j]+max;
            }
        }
        int max=-99999;
        for(int i=a;i< b;i++)
            if(c[a-1][i]>max)max=c[a-1][i];
        System.out.println(max);
    }
}
							

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

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

 static  int[][] dp;
 static int[] offspring;
 static int[] vert;
 static int[] parent;
 static int[] leaf;
 static int n,k;
public static void main(String[] args)
{
 Scanner cin=new Scanner(System.in);
 n=cin.nextInt();
 leaf=new int[n+1];
 offspring=new int[n+1];
 vert=new int[n+1];
 parent=new int[n+1];
 dp=new int[n+1][n+1];
 boolean[] flag=new boolean[n+1];
 int[] left=new int[n+1];
 int[] right=new int[n+1];
 for(int i=0;i<=n;i++)
 for(int j=0;j<=n;j++)
 {
   if(j==0)
    dp[i][j]=0;
   else
    dp[i][j]=-99999999;
 }
 k=cin.nextInt();
 for(int i=0;i< n-k;i++)
 {
   int c=cin.nextInt();
   if(c==0)
    continue;
   int temp=i+1;
   int m=cin.nextInt();
   vert[m]=cin.nextInt();
   left[temp]=m;
   parent[m]=temp;
   offspring[temp]+=1;
   temp=m;
   for(int j=1;j< c;j++)
   {
    m=cin.nextInt();
    right[temp]=m;
    parent[m]=temp;
    offspring[temp]+=2;
    vert[m]=cin.nextInt();
    temp=m;
   }
 }
 for(int i=0;i< k;i++)
 {
   int m=i+n-k+1;
   while(m!=0)
   {
     leaf[m]++;
     m=parent[m];
    }
  }
  for(int i=0;i < k;i++)
   {
    dp[i+n-k+1][1]=cin.nextInt()-vert[i+n-k+1];
    if(offspring[i+n-k+1]==0)
      flag[i+n-k+1]=true;
   }
   while(!flag[1])
   {
    for(int i=1;i<=n;i++)
    {
     if(!flag[i])
     {
      int l=left[i];
      int r=right[i];
      if(l==0&&flag[r]) 
      {
       for(int o=leaf[i];o>=0;o--)
       for(int p=leaf[r];p>=0;p--)
       {
        if(o+p<=leaf[i]&&dp[r][p]+dp[i][o]>dp[i][o+p])
          dp[i][o+p]=dp[r][p]+dp[i][o];
       }
       int o=0;
       while(o<=leaf[r])
        {
         if(dp[r][o]>dp[i][o])
           dp[i][o]=dp[r][o];
         o++;
        }
      flag[i]=true;
     }
    if(r==0&&flag[l]) 
    {
     for(int o=leaf[i];o>=0;o--)
      for(int p=leaf[l];p>=0;p--)
       {
         if(o+p<=leaf[i]&&dp[l][p]+dp[i][o]-vert[i]>dp[i][o+p])
           dp[i][o+p]=dp[l][p]+dp[i][o]-vert[i];
       }
     int o=0;
     while(o<=leaf[l])
     {
       if(dp[l][o]-vert[i]>dp[i][o])
            dp[i][o]=dp[l][o]-vert[i];
       o++;
     }
     flag[i]=true;
   }
   if(flag[r]&&flag[l]) 
   {
     for(int o=leaf[r];o>=0;o--)
      for(int p=leaf[l];p>=0;p--)   
      {
       if(p!=0)
       {
        if(o+p<=leaf[i]&&dp[l][p]+dp[r][o]-vert[i]>dp[i][o+p])
          dp[i][o+p]=dp[l][p]+dp[r][o]-vert[i];
       }
       if(p==0)
       {
         if(dp[r][o]>dp[i][o])
           dp[i][o]=dp[r][o];
        }

     }
    flag[i]=true;
   }
  }
 }
}
   int i;
   for(i=k;i>=1;i--)
    {
       if(dp[1][i]>=0)
         break;
        }
      System.out.println(i);
    }
}
							

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    private static String[] a = null;
    private static int max = -1;
    private static int n = 0;
    private static int m = 0;

    private static void dfs(int x, int y, char[] c, int current) {
        boolean find = false;
        for (int i = 0; i < current; i++) {
            if (c[i] == a[x].charAt(y)) {
                find = true;
                break;
            }
        }

        if (find) {
            max = Math.max(max, current);
            return;
        }

        c[current] = a[x].charAt(y);

        if (x - 1 >= 0) {
            dfs(x - 1, y, c, current + 1);
        }

        if (x + 1 < n) {
            dfs(x + 1, y, c, current + 1);
        }

        if (y - 1 >= 0) {
            dfs(x, y - 1, c, current + 1);
        }

        if (y + 1 < m) {
            dfs(x, y + 1, c, current + 1);
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String line = stdin.readLine();
        String[] temp = line.split("[ ]+");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        a = new String[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = stdin.readLine();
        }

        char[] c = new char[30];
        dfs(0, 0, c, 0);
        System.out.println(max);
    }

}


							

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

#include <stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int P[300000];
int SEG=10000000;
int main()
{
    long n;
    long i;
    long j;
    double result,tempresult;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>P[i];

    }
    sort(P,P+n);
    for(i=0;i<n;i++)
    {
        P[i+n]=P[i]+SEG;
        P[i+2*n]=P[i+n]+SEG;
    }
    tempresult=0;
    int s;
    s=P[n]+SEG/2;
    for(i=n+1;P[i]<=s;++i)
    {
        tempresult+=(P[i]-P[n]); 
    }
    int ln=i;
    j=2*n-i;
    for(i=0;i<j;++i)
    {
        tempresult+=(P[n]-P[n-i-1]);
    }
    result=tempresult; 
    for(i=n+1;i<2*n;++i)
    {
        s=P[i]+SEG/2;
        for(j=ln;P[j]<=s;j++)
        {
            tempresult+=(P[j]-P[i]);
            tempresult-=(P[i-1]-P[j-n]);
        }
        tempresult+=((n-ln+2*i-j)*(P[i]-P[i-1]));
        ln=j;
        if(result>tempresult)
            result=tempresult;
    }
    printf("%.0fn",result);
    return 0;
}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
    
    static int get_base(char c){
        if(c>='0'&&c<='9')
            return c-'0'+0;
        if(c>='A' && c<='Z')
            return c-'A'+ 10;
        if(c>='a' && c<='z')
            return c-'a' + 36;
        return -1;
    }
    
public static void main(String[]args) throws Exception{
        
 int ans,i;
 String str;
 Scanner cin = new Scanner(System.in);
 //Scanner cin = new Scanner(new FileInputStream("input.txt"));
 while(cin.hasNext()){
    str = cin.next();
    for(ans=2;ans<=62;++ans){
        if(can(str,ans))
            break;
    }
    if(ans>62) System.out.println("such number is impossible!");
    else System.out.println(ans);
  }
}

 static boolean can(String str,int cnt){
  int i,sum=0;
  for(i=0;i< str.length();++i){
    if(get_base(str.charAt(i))>=cnt) return false;
    sum*=cnt;
    sum+=get_base(str.charAt(i));
    sum%=(cnt-1);
  }
  if(sum==0) return true;
  return false;
 }

 static int Max(int a,int b){
    return a>b?a:b;
 }
}

							

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

#include<iostream>
#include"stdio.h"
#include"vector"
#include <algorithm>
using namespace std;
struct rect
{double xt,yt,xb,yb;
};
struct point
{double x,y;};

double max(double a,double b)
{if(a>b)return a;
    else return b;
}
double min(double a,double b)
{if(a>b)return b;
            else return a;
}

/*
rect find(rect &a,rect &b)
{rect u;
u.xt=max(a.xt,b.xt);
u.xb=min(a.xb,b.xb);
u.yt=max(a.yt,b.yt);
u.yb=min(a.yb,b.yb);
return u;
}
*/



inline double mj(rect &a)
{return (a.xb-a.xt)*(a.yb-a.yt);}

rect r[100];
vector<double> x,y;


double s;
int n;
/*
inline int isfind(rect &a)
{return a.xt<a.xb&&a.yt<a.yb;}

void go(rect &a,int c,int key)
{rect b;
for(;c<n;c++)if(isfind(b=find(a,r[c])))
{s=s+mj(b)*key;go(b,c+1,key*-1);}    
}*/

inline int in_rect(rect &a,rect &b)
{return a.xt>=b.xt&&a.yt>=b.yt&&a.yb<=b.yb&&a.xb<=b.xb;}

int compare(double a,double b)
{return a<b;}


int main()
{double a,b,c,d;int i,j,c_n=0,ii,jj,k;rect rt;


while(1)
{cin>>n;if(n==0)break;
c_n++;
x.resize(2*n);y.resize(2*n);
for(i=0;i<n;i++)
{cin>>a>>b>>c>>d;
x[2*i]=a;x[2*i+1]=c;
y[2*i]=b;y[2*i+1]=d;
r[i].xt=min(a,c);
r[i].xb=max(a,c);
r[i].yt=min(b,d);
r[i].yb=max(b,d);

}
sort(x.begin(),x.end(),compare);
sort(y.begin(),y.end(),compare);
s=0;

for(i=1;i<2*n;i++)
{ii=i-1;
while(x[i]==x[ii]&&i<2*n)i++;
if(i>=2*n)break;
for(j=1;j<2*n;j++)
    {jj=j-1;
    while(y[j]==y[jj]&&j<2*n)j++;
    if(j>=2*n)break;
    rt.xt=x[ii];rt.xb=x[i];
    rt.yt=y[jj];rt.yb=y[j];
    for(k=0;k<n;k++)
    if(in_rect(rt,r[k]))break;
    
    if(k<n)s+=mj(rt);
    }
}


printf("Test case #%dnTotal explored area: %.2fnn",c_n,s);

}
return 0;
}



							

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

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

int get2(int n)//计算n!中质因子2的出现次数
{
    if(n==0)
        return 0;
    return n/2+get2(n/2);
}

int get5(int n)//计算n!中质因子5的出现次数
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}

//////////////////////////////////////////////////////////////////////////
int g(int n,int x)//计算f(1) to f(n) 中，奇数数列中末尾为x的数出现的次数
{
    if(n==0)
        return 0;
    return n/10+(n%10>=x)+g(n/5,x);
}

int getx(int n,int x)//计算f(1) to f(n)中，末尾为x的数的出现次数
{
    if(n==0)
        return 0;
    return getx(n/2,x)+g(n,x);
}
//////////////////////////////////////////////////////////////////////////

int table[4][4] =
{
        6,2,4,8,//2^n%10的循环节，注意如果2的个数为0时候，结果应该是1，要特殊处理。 
        1,3,9,7,//3
        1,7,9,3,//7
        1,9,1,9,//9    
};//3，7，9的循环节中第一位，刚好是1，故不需要考虑这些数字出现次数为0的情况。


int main()
{

    int n,m;
    int num2;
    int num3;
    int num5;
    int num7;
    int num9;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        num2=get2(n)-get2(n-m);
        num5=get5(n)-get5(n-m);
        num3=getx(n,3)-getx(n-m,3);
        num7=getx(n,7)-getx(n-m,7);
        num9=getx(n,9)-getx(n-m,9);
        int res=1;
        if(num5>num2)
        {
            printf("5n");
            continue;
        }
        else 
        {
            if(num2!=num5)
            {
                res*=table[0][(num2-num5)%4];
                res%=10;
            }//如果num2==num5,那么2^0次方mod 10应该为1 ，而不是table中的6,所以要特殊处理。
            
            res*=table[1][num3%4];
            res%=10;
            res*=table[2][num7%4];
            res%=10;
            res*=table[3][num9%4];
            res%=10;
        }
        printf("%dn",res);
    }
    return 0;
}

							

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

#include <list>
#include <vector>

using namespace std;



class pre_f
{

public:

    enum{ MAX = 1000000000 };        //���������
    enum{ size = 103 };                //ͼ�����ģ(*)

    // ����һ��� from �� to �� ��Ϊ c �ı�
    void insert_edge( int from, int to, int c );
    // ɾ�����б�
    void clear();
    //��ڵ���Ϊnodenum (0...nodenum-1 ) ������� begin ΪԴ, endΪ��                                
    int maxflow( int nodenum, int begin, int end );

private:
    /* needn't care */

    struct edge
    {
        int to;
        int f, c;
        int rev_i;
    };//�ߵĶ���

    int h[size];    //�߶�
    int r[size];    //����
    int cur[size];    //��ǰ���ǵı�ָ��

    vector<edge> e[size];    //�ڽӱ�
    list<int> l;        //����t��

    int n, s, t;        //������Դ�� ��

    void push( int a, edge &s );
    void lift( int a );
    void init();
    void dischange( int a );

};

/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//    ������


void pre_f::insert_edge( int from, int to, int c )
{
    edge e1 = { to, 0, c, e[to].size() }, e2 = { from, 0, 0, e[from].size() };
    
    e[from].push_back( e1 );
    e[to].push_back( e2 );

}

void pre_f::clear()
{
    int i;
    for( i=0; i<size; i++ )
        e[i].clear();
    
    l.clear();
}

void pre_f::push( int a, edge &s )
{
    int y = s.c - s.f, x = r[a]<y?r[a]:y;
    s.f += x;
    e[ s.to ][ s.rev_i ].f = - s.f;
    r[a] -= x;
    r[s.to] += x;
}

void pre_f::lift( int a )
{
    int i, t = size*10;

    for( i=0; i<e[a].size(); i++ )
        if( e[a][i].f < e[a][i].c && t > h[ e[a][i].to ] )
            t = h[ e[a][i].to ];
    h[a] = t + 1;
}

void pre_f::init()
{
    int i;
    for( i=0; i<n; i++ )
        h[i] = 0, r[i] = 0;
    
    h[s] = n;
    r[s] = MAX;

    for( i=0; i<e[s].size(); i++ )
        push( s, e[s][i] );

    l.clear();

    for( i=0; i<n; i++ )
    {
        cur[i] = 0;
        if( i != s && i != t )
            l.push_back( i );
    }

}

void pre_f::dischange( int a )
{
    int k;

    while( r[a] )
    {
        k = cur[a];
        if( k == e[a].size() )
        {
            lift( a );
            cur[a] = 0;
        }
        else if( e[a][k].c > e[a][k].f && h[a] == h[ e[a][k].to ] + 1 )
            push( a, e[a][k] );
        else cur[a]++;
    }
}

int pre_f::maxflow( int nodenum, int begin, int end )
{
    int h_old;
    list<int>::iterator it;

    n = nodenum, s = begin, t = end;

    init();

    for( it=l.begin(); it != l.end(); it++ )
    {
        h_old = h[ *it ];
        dischange( *it );
        if( h_old < h[ *it ] )
        {
            l.push_front( *it );
            l.erase( it );
            it = l.begin();
        }
    }

    return MAX - r[s];
}


/***********************************************************/

#include <stdio.h>

int pig[1000];
int pre[1000];

#include <memory.h>
pre_f mf;
bool sign[102][102];

int main()
{
    int n, m, i, j, k, h;
    scanf( "%d %d", &m, &n );

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

    for( i=0; i<m; i++ )
    {
        scanf( "%d", &pig[i] );
        pre[i] = -1;
    }
    
    for( i=2; i<n+2; i++ )
    {
        scanf( "%d", &h );
        k = 0;
        while( h-- )
        {
            scanf( "%d", &j );
            j--;
            if( pre[j] < 0 )
            {
                k += pig[j];                
            }
            else if( !sign[pre[j]][i] )
            {
                mf.insert_edge( pre[j], i, 2000000 );
                sign[pre[j]][i] = true;
            }

            pre[j] = i;
        }

        if( k )
            mf.insert_edge( 0, i, k );

        scanf( "%d", &k );
        mf.insert_edge( i, 1, k );
    }

    printf( "%d", mf.maxflow( n+2, 0, 1 ) );

    return 0;

}


							

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

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

int num[20000], n;
int ans_x[10000], ans_y[10000],sign_x[10000], sign_y[10000];
const int xsign[]={ 1, -1, -1, 1 },ysign[]={ 1, 1, -1, -1}, h[]={ 1, -1};

void creat(int end, int num[], int sign[], int ans[], int last_sign)
{
    if( end == 0 )
    {
        ans[0] = num[0]*last_sign;
        return ;
    }

    if( last_sign == sign[end-1])
    {
        ans[end]=num[0]*last_sign*h[end%2];
        creat(end-1,num+1,sign,ans,last_sign);
    }
    else
    {
        ans[end] = num[end]*last_sign;
        creat(end-1,num,sign,ans,-last_sign);
    }
    return ;
}


int main()
{
    int i, j, t;
    scanf( "%d", &n );
    for(i=0;i<2*n;i++)
        scanf("%d",&num[i]);
    
    for(i=0;i<n;i++)
    {
        scanf("%d",&t);
        sign_x[i]=xsign[t-1];
        sign_y[i]=ysign[t-1];
    }

    std::sort(num,num+2*n);

    creat(n-1,num,sign_x,ans_x,sign_x[n-1]);
    creat(n-1,num+n,sign_y,ans_y,sign_y[n-1]);

    for(i=0;i<n;i++)
    {
        if(ans_x[i]>0)printf("+");
        printf("%d ",ans_x[i]);
        if(ans_y[i]>0)printf("+");
        printf("%dn",ans_y[i]);
    }

    return 0;
}
							

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

#include"stdio.h"
int a[3001];
int next[3001];
int main()
{
    int n,i,j,k=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(!a[i])k++;
    }
 j=1; k++;
    for(i=1;i<=n;i++)
  if(a[i])
  { next[k]=i; k++; }
  else
  { next[j]=i; j++; }
    k=1;
    for(i=1;i<=n;i++)
    {
        k=next[k];
        printf("%d ",a[k]);
    }
 return 0;
}
							

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

/* @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(cin.next()))
                ;
}

static boolean run(String input){
    if(input.compareTo("#") == 0)
        return false;
    
    System.out.println(next(input));
    return true;
}

static String next(String s){
    char[] map = s.toCharArray();

    int count = map.length-1;

    while(count>0){
         if(map[count-1] < map[count])
        break;
      count--;
    }    

    if(count==0)
      return "No Successor";
        
    char node = map[count];
    int position = count;
    for(int i=count;i< map.length;i++)
      if((map[i]>map[count-1])&&(map[i]< node)){
            node = map[i];
            position = i;
      }

    map[position] = map[count-1];
    map[count-1]  = node;

    PriorityQueue< Char> heap = new PriorityQueue< Char>();
    for(int i=count;i< map.length;i++)
        heap.add(new Char(map[i]));

    for(int i=count;i< map.length;i++)
        map[i] = heap.poll().c;

    return new String(map);

  }

}

class Char implements Comparable{
 char c;

 public Char(char c){
    this.c = c;
 }
 public int compareTo(Object o){
    Char another = (Char)o;
    return this.c-another.c;
 }
}

							

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

import java.util.Scanner;  
public class Main {  
 public static int sum = 0;  
 public static boolean isPrime(int num) {  
  for (int i = 2; i <= Math.sqrt(num); i++) {  
   if (num % i == 0)  
    return false;  
  }  
  return true;  
 }  
 public static boolean isSmithNumbers(int num) {  
  String s = String.valueOf(num);  
  int tempSum = 0;  
  int k = num;  
  while (true) {  
   if (k / 10 > 0) {  
    tempSum += k % 10;  
    k /= 10;  
   } else {  
    tempSum += k;  
    break;  
   }  
  }  
  int n = (int)Math.sqrt(num);  
  for (int i = 2; i <= (int)Math.sqrt(num) ; ) {  
   if (num % i == 0) {  
    getSum(i);  
    num = num / i;  
   }else  
    i++;  
  }  
   getSum(num);  
  if (sum == tempSum)  
   return true;  
  return false;  
 }  
 public static void getSum(int i) {  
  while (true) {  
   if (i / 10 > 0) {  
    sum += i % 10;  
    i /= 10;  
   } else {  
    sum += i;  
    break;  
   }  
  }  
 }  
 public static void get(int n) {  
  while (true) {  
   sum = 0;  
   n++;  
   if (!isPrime(n)) {  
    if (isSmithNumbers(n)) {  
     System.out.println(n);  
     return;  
    }  
   }  
  }  
 }  
 public static void main(String[] args) {  
  Scanner sc = new Scanner(System.in);  
  int n = sc.nextInt();  
  while (n != 0) {  
   //long b = System.currentTimeMillis();  
   get(n);  
  // System.out.println(System.currentTimeMillis() - b);  
   n = sc.nextInt();  
  }  
 }  
}

							

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

//* @author:
import java.util.*;
public class Main
{
  //f[i][j]��λ��i��λ��j����Ҫ�������С�ַ���ans[i][j]��ʾi��j֮������(��ƥ���ַ�

 private char s[];
 private int len;

 private  int f[][];
 private String ans[][];

 public Main(char s[]){
     this.s=s;
     this.len=s.length;
     f=new int[len][len];
     ans=new String[len][len];
     for(int i=0;i< len;i++)
         Arrays.fill(ans[i],"");
     dp();
 }

public String[][] getAns(){
    return ans;
}

public String Answer(){
   return ans[0][len-1];
}
   
private void dp()
{
    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
        {  
            f[i][j] = Integer.MAX_VALUE;
        }
    for (int i = len - 1; i >= 0; i--)
        for (int j = i; j < len; j++)
            if (i == j)
            {
                f[i][j] = 1;
                if (s[i] == '(') ans[i][j] = "()";
                if (s[i] == ')') ans[i][j] = "()";
                if (s[i] == '[') ans[i][j] = "[]";
                if (s[i] == ']') ans[i][j] = "[]";
            }
            else  if (j > i)
            {
               
                    if (s[i] == '(' && s[j] == ')')
                    {
                        if (f[i + 1][j - 1] < f[i][j])
                        {
                            f[i][j] = f[i + 1][j - 1];
                            ans[i][j] = "(" + ans[i + 1][j - 1] + ")";
                        }
                    }
                    else if (s[i] == '[' && s[j] == ']')
                    {
                        if (f[i + 1][j - 1] < f[i][j])
                        {
                            f[i][j] = f[i + 1][j - 1];
                            ans[i][j] = "[" + ans[i + 1][j - 1] + "]";
                        }                            
                    }
                for (int k = i; k < j; k++)
                {
                    if (f[i][k] + f[k + 1][j] < f[i][j])
                    {
                        f[i][j] = f[i][k] + f[k + 1][j];
                        ans[i][j] = ans[i][k] + ans[k + 1][j];
                    }
                }
            }
}
   
    public static void main(String[] args)
    {
    Scanner sc = new Scanner(System.in);
          String ss=sc.nextLine();
          if(ss.length()==0){
             System.out.println();
          }
         ss.replaceAll(" ", "");
        char s[]=ss.toCharArray();

        Main m=new Main(s);
        System.out.println(m.Answer());
   }
}


							

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

/* @author: */

import java.io.*;
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int a,b,i,j,c[],f,d;
        c=new int[2000];
        for(;;)
        {
         a=cin.nextInt();
         b=cin.nextInt();
         if(a==0&b==0)break;
         c[0]=a;i=0;f=0;j=0;d=1;
         System.out.print(".");
         for(;;)
         {
          a=(a*10)%b;
          if(a!=0)
          {
           for(j=0;j< i;j++)
           {
            if(c[j]==c[i])break;
           }
           if(c[j]==c[i]&j!=i)break;
           System.out.printf("%d",c[i]*10/b);
           c[++i]=a;
           d++;
           if(d%50==0)System.out.println();
          }
          else
          {
           f=1;
           break;
          }
         }
         if(f==1)System.out.printf("%dnThis expansion terminates.n",c[i]*10/b);
         else
         {
          if(d%50!=0)System.out.printf("n");
          System.out.printf("The last %d digits repeat forever.n",i-j);
         }
        }
    }
}

							

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

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.lang.Integer;

class Node {
    int x, mask;

    int s;

    int f;

    int action;

    public Node(int x, int mask, int s, int f, int aa) {
        this.x = x;
        this.mask = mask;
        this.s = s;
        this.f = f;
        this.action = aa;
    }
}

public class Main {

    int r, d, s;

    boolean[][] adj;

    boolean[][] ctr;

    int[][] dp;

    void run() throws Exception {
        Scanner cin = new Scanner(System.in);
        int tc = 0;
        while (true) {

            r = cin.nextInt();
            d = cin.nextInt();
            s = cin.nextInt();

            if (r == 0 && d == 0 && s == 0)
                break;
            System.out.printf("Villa #%dn", ++tc);

            int i;
            adj = new boolean[r][r];
            ctr = new boolean[r][r];
            dp = new int[r][1 << r];

            for (i = 0; i < r; ++i) {
                Arrays.fill(dp[i], -1);
            }

            for (i = 0; i < d; ++i) {
                int x = cin.nextInt();
                int y = cin.nextInt();
                adj[x - 1][y - 1] = adj[y - 1][x - 1] = true;
            }

            for (i = 0; i < s; ++i) {
                int x = cin.nextInt();
                int y = cin.nextInt();
                ctr[x - 1][y - 1] = true;
            }

            List< Node> Q = new ArrayList< Node>();

            Q.add(new Node(0, 1, 0, -1, 0));
            Node now = new Node(0, 1, 0, -1, 0);
            dp[0][1] = 0;
            int lo = 0;
            while (lo < Q.size()) {
                now = Q.get(lo);
                int x = now.x, mask = now.mask, s = now.s;
                if (x == r - 1 && mask == (1 << (r - 1))) {
                    break;
                }

                for (i = 0; i < r; ++i)
                    if (adj[x][i] && (mask & (1 << i)) != 0) {
                        if (dp[i][mask] == -1) {
                            dp[i][mask] = s + 1;
                            Q.add(new Node(i, mask, s + 1, lo, 0));
                        }
                    }

                for (i = 0; i < r; ++i)
                    if (ctr[x][i]) {
                        if ((mask & (1 << i)) != 0 && i != x) {
                            if (dp[x][mask ^ (1 << i)] == -1) {
                                dp[x][mask ^ (1 << i)] = s + 1;
                                Q.add(new Node(x, mask ^ (1 << i), s + 1, lo, -i - 1));
                            }
                        } else {
                            if (dp[x][mask | (1 << i)] == -1) {
                                dp[x][mask | (1 << i)] = s + 1;
                                Q.add(new Node(x, mask | (1 << i), s + 1, lo, i + 1));
                            }
                        }
                    }
                lo++;
            }

            if (lo == Q.size()) {
                System.out.printf("The problem cannot be solved.n");
            } else {
                System.out.printf("The problem can be solved in %d steps:n", now.s);
                ArrayList<Integer> idxes = new ArrayList<Integer>();
                while (lo != -1) {
                    // System.out.println(lo);
                    idxes.add(lo);
                    lo = Q.get(lo).f;
                }
                for (i = idxes.size() - 2; i >= 0; --i) {
                    if (Q.get(idxes.get(i)).action == 0) {
                        System.out.printf("- Move to room %d.n", Q.get(idxes.get(i)).x + 1);
                    } else if (Q.get(idxes.get(i)).action > 0) {
                        System.out.printf("- Switch on light in room %d.n", Q.get(idxes.get(i)).action);
                    } else {
                        System.out.printf("- Switch off light in room %d.n", -Q.get(idxes.get(i)).action);
                    }
                }
            }
            System.out.println();

        }
    }

    public static void main(String[] args) throws Exception {
        new Main().run();

    }

    private String toBinary(int x) {
        String now = Integer.toBinaryString(x);
        for (int i = 0; i < r - now.length(); ++i) {
            now = "0" + now;
        }
        return now;
    }

}