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

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

public class Main{
    
    public static void main(String rgs[]) throws Exception
    {
        boolean[] prime=new boolean[1299710];
        Arrays.fill(prime,true);
        prime[1] = false;
        prime[0] = false;
        for(int i=2; i<=10000; ++i){
            if(prime[i])
                for (int j=i; i*j< 1299710; ++j)
                    prime[i*j] = false;
        }
        int n, left, right;
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        n = cin.nextInt();
        while(n!=0){
            if(prime[n])
                System.out.println(0);
            else{
                right = left = n;
                while(!prime[--left]);
                while(!prime[++right]);
                System.out.println(right - left);                
            }
            n = cin.nextInt();
        }
    }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
class Main
{
 static int n,k,m;
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    while(true)
    {
        String[] ss=in.readLine().split(" ");
     n=Integer.parseInt(ss[0]);
     k=Integer.parseInt(ss[1]);
     m=Integer.parseInt(ss[2]);
     if(n==0) break;
     System.out.println((f(n-1)+m)%n+1);
    }
   }

 static int f(int num)
 {
    if(num==1) return 0;
    else return (k+f(num-1))%num;
 }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Queue{
    int pre;
    int cnt_posi;
    int cnt_num;
    int cnt_sum;
    void set(int pre_t,int cnt_num_t,int cnt_sum_t,int cnt_posi_t){
        this.pre = pre_t;
        this.cnt_num = cnt_num_t;
        this.cnt_sum = cnt_sum_t;
        this.cnt_posi = cnt_posi_t;
    }
}
class node{
    int who;
    int value;
}
public class Main {
    static final int N = 4000000+10,P=256;
    
    static int n,p;
    static Queue myque[] = new Queue[N];

    static HashMap map[] = new HashMap[P];
    static int ans[] = new int[P],num[][] = new int[P][6];
    
    static void start_que(){
        int i,j;
        for(i=0;i< N;++i)
            myque[i] = new Queue();
        for(i=0;i< P;++i)
            map[i] = new HashMap();
    }
    
public static void main(String []args) throws Exception{
        
  int i,j,cs=1;
  String str = new String();
  Scanner cin = new Scanner(System.in);
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  start_que();
  while(cin.hasNext()){
    str = cin.next();
    if(str.equalsIgnoreCase("0=0"))
        break;
    for(i=0;i< str.length();++i){
        if(str.charAt(i)=='=')
            break;
    }
    n = i;
    p = Integer.valueOf(str.substring(i+1, str.length()));

    System.out.print(cs+". ");
    ++cs;
    solve(str,cs);
   }
 }

 public static void init_num(String str){
  int i,j;
  for(i=0;i< n;++i){
    num[i][0] = 0;
    for(j=1;j< 6 && i+j<=n;++j){
        num[i][j] = num[i][j-1]*10+str.charAt(i+j-1)-'0';
        //System.out.println(num[i][j]);
    }
   }
   for(i=0;i<=n;++i)
    map[i].clear();
  
   }


  static void get_ans(int cnt){
    String str="";
    int i,j,top=0;
    while(cnt>0){
        ans[top++] = myque[cnt].cnt_num;
        cnt = myque[cnt].pre;
    }
    str += String.valueOf(ans[top-1]);
    for(i=top-2;i>=0;--i){
        str+="+";
        str+=String.valueOf(ans[i]);
    }
    str+="="+String.valueOf(p);
    System.out.println(str);
  }

  public static void solve(String str,int cs){
   init_num(str);

   int i,j,k,left=0,right=0;
        
   myque[right].set(-1, 0, 0, 0);
   ++right;
        
   while(left< right){
    //System.out.println(left+" "+right);
    for(i=1;i< 6 && num[myque[left].cnt_posi][1]>0 && myque[left].cnt_posi+i<=n;++i){
    if(num[myque[left].cnt_posi][i]+myque[left].cnt_sum<=p){
                    
      myque[right].set(left, num[myque[left].cnt_posi][i], 
           num[myque[left].cnt_posi][i]+myque[left].cnt_sum, myque[left].cnt_posi+i);
      if(myque[right].cnt_posi==n && myque[right].cnt_sum==p){
        get_ans(right);
        return ;
        }
        if(!has_in_hash(myque[right].cnt_posi,myque[right].cnt_sum,cs))continue;
            ++right;
        }
        
    }
    ++left;
    }
    System.out.println("IMPOSSIBLE");
  }

  public static boolean has_in_hash(int posi,int sum,int cs){

        if(map[posi].containsKey(sum))
            return false;
        map[posi].put(sum, 1);
        return true;
    }
    
}

							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss;
  String s;
  int count=0;
  while(true)
  {
    count++;
    node[] arr=new node[1001];
    node[] pp=new node[1001];
    int i=0,j,zNum,maxNum,x,y,p,max=-1, a=0;
    while(true)
    {
         s=in.readLine();
      if(s.charAt(0)=='-'&&s.charAt(1)=='-') break;
      ss=s.split(" ");
      x=Integer.parseInt(ss[0]);
      y=Integer.parseInt(ss[1]);
      arr[a]=new node(x,y);
      pp[a]=new node(); 
      a++;
     }
     if(a==0) break;
     for(i=0;i< a-1;i++)
     {
       int k=0;
       zNum=maxNum=-1;
       for(j=i+1;j< a;j++)
       {
        x=arr[i].x-arr[j].x;
        y=arr[i].y-arr[j].y;
        if(y==0) zNum++;
        else if(x==0) maxNum++;
        else
        {
             p=gcd(Math.abs(x),Math.abs(y));
          pp[k].x=x/p;
          pp[k].y=y/p;
          if(pp[k].x< 0)
          {
           pp[k].x*=-1;
           pp[k].y*=-1;
          }
          k++;
        }
         }
         max=Math.max(max,Math.max(zNum, maxNum));
         int cnt=0;
         Arrays.sort(pp, 0, k);
         for(j=0;j< k-1;j++)
         {
        if(pp[j].x==pp[j+1].x&&pp[j].y==pp[j+1].y) cnt++;
        else{
            if(cnt>max) max=cnt;
            cnt=0;
        }
         }
         max=Math.max(max, cnt);
      }
     System.out.println(count+". "+(max+2));
     }
  }

  static int gcd(int a,int b)
  {
   if(b==0) return a;
   else return gcd(b,a%b);
  }
}

class node implements Comparable< node>{
    public int x,y;
    public node(){}
    public node(int a,int b)
    {
        x=a;
        y=b;
    }
    public int compareTo(node o) {
        if(x==o.x) return y-o.y;
        return x-o.x;
    }
}
							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
     public static void main(String args[]) throws IOException{
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        int[] prims=new int[1000001];
        int[] ferms=new int[1000001];
        for(int i=3;i< 1000000;i+=2) 
          prims[i]=1;
        prims[2]=1;
        int index=1;
        while((index+=2)< 1000000) 
           if(prims[index]==1)
             for(int i=2*index;i< 1000000;i+=index) prims[i]=0;
        ferms[2]=1;
        for(int i=3;i< 1000000;i+=2){
            if(prims[i]==1&&i%4==1) ferms[i]=1;
            prims[i]+=prims[i-1];
            prims[i+1]=prims[i];
            ferms[i]+=ferms[i-1];
            ferms[i+1]=ferms[i];
         }
        int limi=0,lims=0,in,su;
        while(true){
            tokens=new StringTokenizer(stdin.readLine());
            limi=Integer.parseInt(tokens.nextToken());
            lims=Integer.parseInt(tokens.nextToken());
            if(limi==-1&&lims==-1) break;
            in=limi;
            su=lims;
            if(limi<=0) limi=1;
            if(lims<=0) lims=1;
            System.out.println(in+" "+su+" "+(prims[lims]-prims[limi-1])+" "+(ferms[lims]-ferms[limi-1]));
        }
      }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   String s=in.nextLine();
   StringBuffer sb=new StringBuffer("");
   int l=s.length();
   boolean bb=false;
   for(int i=0;i< l;i++)
   {
    char c=s.charAt(i);
    if(i< l-1&&c=='d'&&s.charAt(i+1)=='d'){
        sb.append('p');
        i++;
    }
    else if(i< l-1&&c=='e'&&s.charAt(i+1)=='i'&&(i==0||s.charAt(i-1)!='c')){
        sb.append("ie");
        i++;
    }            
    else if(i< l-3&&c=='p'&&s.charAt(i+1)=='i'&&s.charAt(i+2)=='n'&&s.charAt(i+3)=='k'){
        sb.append("floyd");
        i+=3;
    }    
    else if(i< l-2&&c=='E'&&s.charAt(i+1)=='O'&&s.charAt(i+2)=='F'){
        bb=true;
        break;
    }
    else if(c>='a'&&c<='z'||c==' ') sb.append(c);
    }
    System.out.println(sb);
    if(bb) break;
   }
 }
}
							

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

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 num = 1;

       int flg, tt, last;

       while (true) {

           char[] c = read.readLine().toCharArray();

           if (c.length == 1 && c[0] == '0') {

              break;

           }

           last = c[c.length - 1];

           flg = 0;

           for (int j = c.length - 2; j >= 0; j--) {

              tt = c[j] - last;

              if (flg + tt < 0) {

                  c[j] = (char) ('0' + flg + tt + 10);

                  flg = -1;

              } else {

                  c[j] = (char) ('0' + flg + tt);

                  flg = 0;

              }

              last = c[j];

           }

           if (c[0] != '0') {

              System.out.println(num + ". " + String.valueOf(c));

           } else {

              System.out.println(num + ". IMPOSSIBLE");

           }

           num++;

       }

    }

}

							

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

import java.util.Scanner;


public class Main {
 public static void main(String[] args)
 {
    Scanner in = new Scanner(System.in);
    float[] input = new float[6];
    while(true)
    {
        input[0] = in.nextFloat();
        float max = input[0];
        float min = input[0];
        float sum = input[0];
        for(int i = 1; i < 6; i++)
        {
            input[i] = in.nextFloat();
            if(max < input[i])
                max = input[i];
            if(min > input[i])
                min = input[i];
            sum = sum + input[i];
        }
        if(sum == 0.0)
            break;
        else
        {
            sum -= min;
            sum -= max;
        }
        float result = sum/4;
        int res = (int)sum/4;
        if(res*4 == sum)
            System.out.println(res);
        else
            System.out.println(result);    
    }
  }
}
							

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

//* @author: 
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    int nn,n,m,ans;
     nn=sc.nextInt();
     while((nn--)!=0) {
      n=sc.nextInt();
      m=sc.nextInt();
      int a[][]=new int[n+1][m+1];
       ans=0;
    for (int i=1;i<=n;i++) {
      for (int j=1;j<=m;j++) 
           a[i][j]=sc.nextInt();
        int tp=0,now=1,t1,t2;
        for (int j=1;j<=m;j++) if (a[i][j]!=-1) tp++;
         while ((tp--)!=0) {
          int pos=1,tmp=1000000;
         for (int j=1;j<=m;j++) if (a[i][j]!=-1&&a[i][j]< tmp) {pos=j;tmp=a[i][j];}
          ans+=(i-1)*20;
        t1=now-pos;
        t2=pos-now;
        if (t1< 1) t1+=m;
        if (t2< 1) t2+=m;
        if (t1>t2) t1=t2;
        ans+=t1*5;now=pos;
        a[i][pos]=-1;
    }
     }
     System.out.printf("%dn",ans);
    }
  }
}
							

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

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

public class Main {
 public static Scanner in=new Scanner(System.in).useLocale(Locale.US);


 public void run() {
  boolean[] singles=new boolean[26];
  Map< String,String>[][] words=new Map[26][26];
  for(int i=0;i< 26;++i) for(int j=0;j< 26;++j) words[i][j]=new HashMap< String,String>();
  Set< String>[][] doublewords=new Set[26][26];
  for(int i=0;i< 26;++i) 
    for(int j=0;j< 26;++j)
      doublewords[i][j]=new HashSet< String>();
  String s=in.next();
  int n=in.nextInt();
  for(int i=0;i< n;++i) {
    String word=in.next();
    if(word.length()==1) {
         singles[word.charAt(0)-'a']=true;
    } else {
      int a=word.charAt(0)-'a',b=word.charAt(word.length()-1)-'a';
      char[] letters=word.substring(1,1+word.length()-2).toCharArray();
      Arrays.sort(letters);
      if(words[a][b].containsKey(new String(letters))) 
       doublewords[a][b].add(new String(letters));
      else words[a][b].put(new String(letters),word);
    }
    }
   String[] prev=new String[s.length()+1];
   int[] ways=new int[s.length()+1]; ways[0]=1;
   for(int i=0;i< s.length();++i) if(ways[i]>0) {
    if(singles[s.charAt(i)-'a']) { 
        ways[i+1]=Math.min(2,ways[i+1]+ways[i]);
        prev[i+1]=""+s.charAt(i);
      }
    for(int len=2;i+len<=s.length() && len<=100;++len) {
      int a=s.charAt(i)-'a',b=s.charAt(i+len-1)-'a';
      char[] letters=s.substring(i+1,i+1+len-2).toCharArray();
      Arrays.sort(letters);
      String word=new String(letters);
      if(doublewords[a][b].contains(word)) 
           ways[i+len]=Math.min(2,ways[i+len]+2*ways[i]);
      else if(words[a][b].containsKey(word)) { 
           ways[i+len]=Math.min(2,ways[i+len]+ways[i]); 
           prev[i+len]=words[a][b].get(word); 
         }
    }
     }
     if(ways[s.length()]==0) System.out.println("impossible");
     else if(ways[s.length()]==2) System.out.println("ambiguous");
     else {
    List< String> ret=new ArrayList< String>();
    for(int i=s.length();i!=0;i-=prev[i].length()) ret.add(prev[i]);
    Collections.reverse(ret);
    for(int i=0;i< ret.size();++i) {
      if(i!=0) System.out.print(" ");
        System.out.print(ret.get(i));
    }
    System.out.println();
   }
    
 }
    
 public static void main(String[] args) {
   int n=in.nextInt(); 
   for(int i=0;i< n;++i)
    new Main().run();
 }
}

							

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            int n;
            try {
                n=in.nextInt();
            }
            catch(Exception e) {return;}
            String []s=new String [n];
            for (int i=0;i< n;i++) s[i]=in.next();
            int m=s[0].length();
            String tp=new String();
            for (int i=m-1;i>=0;i--) for (int j=n-1;j>=0;j--)
                tp=tp.concat(String.valueOf(s[j].charAt(i)));
            int lastone=0;
            for (int i=tp.length()-1;i>=0;i--)
                if (tp.charAt(i)!='_') {lastone=i;break;}
            for (int i=0;i< tp.length();i++) {
                if (tp.charAt(i)=='_') System.out.print(' ');
                else if (tp.charAt(i)=='\') System.out.println();
                else System.out.print(tp.charAt(i));
                if (i==lastone) break;
            }
            System.out.println();
            System.out.println();
        }
    }
}


							

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

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

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int n,c;
    int m[][]=new int[1003][1003];
    int f[]=new int[1003];
    while(sc.hasNext()){
          c=sc.nextInt();
          n=sc.nextInt();
          for(int i=0;i< m.length;i++)
             Arrays.fill( m[i],0);
          for(int i=1;i<=n;i++){
               for(int j=i;j<=n;j++)
                 m[i][j]=sc.nextInt();
                    
          }
          for(int i=1;i<=n;i++){
               f[i]=c+m[1][i];        
          }
          for(int i=2;i<=n;i++){
               for(int j=i;j<=n;j++){
                    if(f[j]>f[i-1]+c+m[i][j])
                         f[j]=f[i-1]+c+m[i][j];        
               }        
          }
          System.out.printf("%dn",f[n]);                  
    }
    }
}


							

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
class SEG implements Comparable<SEG>
{
    double b,e;
    SEG(double x,double y) {
        b=x;e=y;
    }
    public int compareTo(SEG other) {
        if (b< other.b) return -1;
        else if (b==other.b) {
            if (e< other.e) return -1;
            else if (e==other.e) return 0;
        }
        return 1;
    }
}
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            double l,d;
            int n;
            try {
                l=in.nextDouble();
            }
            catch (Exception e) {return;}
            d=in.nextDouble();
            n=in.nextInt();
            int ans=1;
            double d2=d*d,r,x,y;
            SEG []s=new SEG[n];
            for (int i=0;i< n;i++) {
                x=in.nextDouble();
                y=in.nextDouble();
                r=Math.sqrt(d2 - y*y);
                s[i]=new SEG(x-r,x+r);
            }
            Arrays.sort(s);
            double cr=s[0].e;
            for(int i=1;i< n;i++) {
                if (s[i].b>cr) {
                    cr=s[i].e;
                    ans++;
                }
                else if (cr>s[i].e) cr=s[i].e;
            }
            System.out.println(ans);
        }
    }
}


							

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
class node{
    int x,y,z;
    node(String s) {
        int t=0,cnt=0;
        for (int i=0;i<=s.length();i++) {
            if (i!=s.length()&&s.charAt(i)>='0'&&s.charAt(i)<='9') {
                t=t*10+s.charAt(i)-'0';
            }
            else {
                if (cnt==0) x=t;
                else if (cnt==1) y=t;
                else if (cnt==2) z=t;
                cnt++;
                t=0;
            }
        }
    }
}
public class Main {
    static void doit(Vector a) {
        int n=a.size();
        node tt=null;
        long beg=2147483647,end=0,ans=0;
        long total=0;
        for (int i=0;i< n;i++) {
            tt=(node)a.get(i);
            total+=(tt.y-tt.x)/tt.z+1;
            if (beg>tt.x) beg=tt.x;
            if (end< tt.y) end=tt.y;
        }
        if (total%2==0) {
            System.out.println("no corruption");
            return;
        }
        while (beg<=end) {
            long mid=(beg+end)/2;
            total=0;
            for (int i=0;i< n;i++) {
                tt=(node)a.get(i);
                long left,right,x=tt.x,y=tt.y,z=tt.z;
                if (x>beg) left=x;
                else {
                    if (beg%z==x%z) left=beg;
                    else if (beg%z>x%z) left=beg-beg%z+x%z+z;
                    else left=beg-beg%z+x%z;
                }
                if (y< mid) right=y;
                else right=mid;
                if (right>=left) total+=(right-left)/z+1;
            }
            if (total%2==1) {
                end=mid;
                if (beg==end) {
                    ans=beg;
                    break;
                }
            }
            else {
                beg=mid+1;
            }
        }
        System.out.print(ans);
        int ans2=0;
        for (int i=0;i< n;i++) {
            tt=(node)a.get(i);
            if (ans>=tt.x&&ans<=tt.y&&ans%tt.z==tt.x%tt.z) ans2++;
        }
        System.out.print(' ');
        System.out.println(ans2);
    }
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            Vector a=new Vector(0);
            while (true) {
                String s;
                try {s=in.nextLine();}
                catch (Exception e) {
                    if (a.size()!=0) doit(a);
                    return;
                }
                if (s.length()==0) {
                    if (a.size()!=0) {
                        doit(a);
                        break;
                    }
                }
                else a.add(new node(s));
            }
        }
    }
}


							

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

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        new Main().run();
    }
    
    int[] f;
    int[] dp;
    
    int Root(int x) {
        if(f[x] == x) 
            return x;
        return f[x] = Root(f[x]);
    }
    
    private class Node implements Comparable {
        int p, d;

        public Node() {
            super();
        }

        public Node(int p, int d) {
            super();
            this.p = p;
            this.d = d;
        }

        public int compareTo(Object arg0) {
            return -(p-((Node)arg0).p);
        }
    }

    private void run() throws FileNotFoundException {
         Scanner cin = new Scanner(System.in);
 
        while(cin.hasNextInt()) {
            int n = cin.nextInt();
            int l = cin.nextInt();
 
            Node p[] = new Node[n];
            int max = 0;
            for(int i = 0; i < n; ++i) {
                p[i] = new Node(cin.nextInt(), cin.nextInt());
                p[i].d++;
                p[i].d *= l;
                max = Math.max(max, p[i].d);
            }
            max++;
            Arrays.sort(p);

            f = new int[max];
            for(int i = 0; i < max; ++i) f[i] = i;
            
            int sum = 0;
            for(int i = 0; i < n; ++i) {
                int x = p[i].d;
 
                int r = Root(x);
                if(r != 0) {
                    f[r] = r-1;
                    sum += p[i].p;
 
                }
            }
            System.out.println(sum);
            
        }
        
    }

}

							

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

//* @author: 
import java.util.*;
import java.io.FileReader;
import java.math.*;
public class Main {
    public static void main(String[] args)  throws Exception{
        int n=0;
        int [] dx=new int[1000];
        Scanner in=new Scanner(System.in);
        int fir=1;
        while (true) {
            String s;
            try {
                while (true) {
                    s=in.nextLine();
                    if (s.length()!=0) break;
                }
            }
            catch(Exception e) {
                break;
            }
            if (fir==1) fir=0;
            else System.out.println();
            int ll=s.length();
            n=0;
            for (int i=0;i< ll;i++) if (s.charAt(i)>0x20) {
                dx[s.charAt(i)]=n++;
            }
            while (true) {
                try{
                    s=in.nextLine();
                }
                catch(Exception e2) {
                    return;
                }
                int l=s.length();
                if (l==0) break;
                int max=0;
                for (int i=0;i< l;i++) 
                 if (s.charAt(i)>0x20&&max< dx[s.charAt(i)]) max=dx[s.charAt(i)];
                BigInteger ans=BigInteger.ZERO;
                for (int dig=max+1;dig<=n;dig++) {
                    BigInteger tmp=BigInteger.ZERO;
                    for (int i=0;i< l;i++) if (s.charAt(i)>0x20) {
                        tmp=tmp.multiply(BigInteger.valueOf(dig));
                        tmp=tmp.add(BigInteger.valueOf(dx[s.charAt(i)]));
                    }
                    ans=ans.add(tmp);
                }
                System.out.println(ans);
            }
        }
    }
}


							

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

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

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        BinaryMinimumHeap minHeap = new BinaryMinimumHeap();
        BinaryMaximumHeap maxHeap = new BinaryMaximumHeap();
        
        while(true)
        {
            int request = sc.nextInt();
            if(request == 0)
            {
                break;
            }else if(request == 1)
            {
                int k = sc.nextInt();
                int p = sc.nextInt();
                Client client = new Client(k,p);
                minHeap.offer(client);
                maxHeap.offer(client);
            }else if(request == 2)
            {
                if(maxHeap.size() == 0)
                {
                    System.out.println(0);
                }else
                {
                    Client client = maxHeap.poll();
                    minHeap.remove(client);
                    System.out.println(client);
                }
            }else if(request == 3)
            {
                if(minHeap.size() == 0)
                {
                    System.out.println(0);
                }else
                {
                    Client client = minHeap.poll();
                    maxHeap.remove(client);
                    System.out.println(client);
                }
            }else
            {
                throw new RuntimeException("No such type of request");
            }
        }
    }
    
}

class Client implements Comparable< Client>
{
    int id;
    int priority;
    int posInMinimumHeap;
    int posInMaximumHeap;
    
    Client(int id, int priority)
    {
        this.id = id;
        this.priority = priority;
        this.posInMaximumHeap = 0;
        this.posInMinimumHeap = 0;
    }
    
    public int compareTo(Client client)
    {
        if(this.priority < client.priority)
        {
            return - 1;
        }else if(this.priority == client.priority)
        {
            return 0;
        }else
        {
            return 1;
        }
    }
    
    public String toString()
    {
        return Integer.toString(id);
    }
}

class BinaryMinimumHeap
{
    
    public static final int capacity = 1000001;
    int count;
    Client[] clients;
    public BinaryMinimumHeap()
    {
        clients = new Client[capacity];
        count = 0;
    }
    
    public void offer(Client client)
    {
        if(count == capacity - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && clients[i/2].compareTo(client) == 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMinimumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMinimumHeap = i;
    }
    
    public Client poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        Client result = clients[1];
        result.posInMinimumHeap = 0;
        Client last = clients[count];
        count--;
        int i = 1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child+1 <= count && clients[child].compareTo(clients[child+1]) == 1)
            {
                child += 1;
            }
            if(last.compareTo(clients[child]) == -1)
            {
                break;
            }
            clients[i] = clients[child];
            clients[i].posInMinimumHeap = i;
            i = child;
        }
        clients[i] = last;
        clients[i].posInMinimumHeap = i;
        
        return result;
    }
    
    public void remove(Client client)
    {
        int i = client.posInMinimumHeap;
        while(i > 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMinimumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMinimumHeap = i;
        poll();
    }
    
    public int size()
    {
        return count;
    }
    
    public int capacity()
    {
        return capacity - 1;
    }
}

class BinaryMaximumHeap
{
    
    public static final int capacity = 1000001;
    int count;
    Client[] clients;
    public BinaryMaximumHeap()
    {
        clients = new Client[capacity];
        count = 0;
    }
    
    public void offer(Client client)
    {
        if(count == capacity - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && clients[i/2].compareTo(client) == -1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMaximumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMaximumHeap = i;
    }
    
    public Client poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        Client result = clients[1];
        result.posInMaximumHeap = 0;
        Client last = clients[count];
        count--;
        int i = 1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child+1 <= count && clients[child].compareTo(clients[child+1]) == -1)
            {
                child += 1;
            }
            if(last.compareTo(clients[child]) == 1)
            {
                break;
            }
            clients[i] = clients[child];
            clients[i].posInMaximumHeap = i;
            i = child;
        }
        clients[i] = last;
        clients[i].posInMaximumHeap = i;
        
        return result;
    }
    
    public void remove(Client client)
    {
        int i = client.posInMaximumHeap;
        while(i > 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMaximumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMaximumHeap = i;
        poll();
    }
    
    public int size()
    {
        return count;
    }
    
    public int capacity()
    {
        return capacity - 1;
    }
}

							

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

//* @author: 
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args)  throws Exception{
        int nn;
        Scanner in=new Scanner(System.in);
        nn=in.nextInt();
        while ((nn--)!=0) {
            int n=in.nextInt();
            long ans=0,max=0;
            for (int i=1;i<=n;i++) {
                long j=in.nextLong();
                if (j>max) max=j;
                ans=ans^j;
            }
            if ((ans!=0)&&(max>1)||(ans==0)&&(max<=1)) System.out.println("John");
            else System.out.println("Brother");
        }
    }
}

							

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

//* @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);
    BallSeq head, tail;
    BinaryHeap pq = new BinaryHeap();
    String s = sc.next();
    char previousChar = s.charAt(0);
        Ball ball = new Ball(0+1);
    BallSeq seq = new BallSeq(previousChar,0+1);
        head=seq;
        tail = seq;
    seq.firstBall = ball;
        seq.lastBall = ball;
    seq.number++;
    for(int i = 1; i < s.length(); i++)
    {
        char currentChar = s.charAt(i);
        if(currentChar==previousChar)
        {
        ball = new Ball(i+1);
                seq.lastBall.nextBall = ball;
                //ball.previousBall = seq.lastBall;
                seq.lastBall = ball;
                seq.number++;
        }else
        {
        previousChar = currentChar;
                pq.offer(seq);
        seq = new BallSeq(previousChar,i+1);
                tail.nextBallSeq = seq;
                seq.previousBallSeq = tail;
                tail = seq;
        ball = new Ball(i+1);
                seq.firstBall = ball;
                seq.lastBall = ball;
        seq.number++;
        }
    }
        pq.offer(seq);
    while(true)
    {
        int size = pq.size();
        if(size==0)
        {
            break;
        }
        seq = pq.poll();
        if(seq.number==1)
        {
            break;
        }
        System.out.print(seq.color);
            ball = seq.firstBall;
        for(int i = 0; i < seq.number; i++)
        {
            System.out.print(" "+ball.position);
                ball = ball.nextBall;
        }
        System.out.println();
        if(seq == head)
            {
                head = seq.nextBallSeq;
                if(head != null)
                {
                    head.previousBallSeq = null;
                }
            }else if(seq == tail)
            {
                tail = seq.previousBallSeq;
                if(tail !=null )
                {
                    tail.nextBallSeq = null;
                }
            }else
            {
                BallSeq p = seq.previousBallSeq;
                BallSeq n = seq.nextBallSeq;
                if(p.color == n.color)
                {
                    pq.remove(p);
                    pq.remove(n);
                    p.number += n.number;
                    p.lastBall.nextBall = n.firstBall;
                    //n.firstBall.previousBall = p.lastBall;
                    p.lastBall = n.lastBall;
                    p.nextBallSeq = n.nextBallSeq;
                    if(n != tail)
                    {
                        n.nextBallSeq.previousBallSeq = p;
                    }else
                    {
                        tail =p;
                    }
                    pq.offer(p);
                }else
                {
                    p.nextBallSeq = n;
                    n.previousBallSeq = p;
                }
            }
    }
    }   
}

class BallSeq implements Comparable< BallSeq>
{
    public char color;
    public int number;
    public int start;
    public int position;
    Ball firstBall;
    Ball lastBall;
    BallSeq previousBallSeq;
    BallSeq nextBallSeq;
    public BallSeq(char color, int start)
    {
        this.color = color;
    this.start = start;
    this.number = 0;
        position = 0;
        firstBall = null;
        lastBall = null;
        previousBallSeq = null;
        nextBallSeq = null;
    }
    public int compareTo(BallSeq bs)
    {
        if(this.number == bs.number)
    {
        if(this.start == bs.start)
        {
            return 0;
        }else if(this.start < bs.start)
        {
            return -1;
        }else
        {
            return 1;
        }
    }else if(this.number < bs.number)
    {
        return 1;
    }else
    {
        return -1;
    }
    }
}

class Ball
{
    //Ball previousBall;
    Ball nextBall;
    int position;//position in the sequence
    public Ball(int position)
    {
        this.position = position;
        //previousBall = null;
        nextBall = null;
    }
}
class BinaryHeap
{
    public static final int max = 1000000;
    int count;
    BallSeq[] segments;
    public BinaryHeap()
    {
        count = 0;
        segments = new BallSeq[max];
    }
    public void offer(BallSeq seq)
    {
        if(count == max - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && segments[i/2].compareTo(seq) == 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
    }
    public void remove(BallSeq seq)
    {
        int i = seq.position;
        while(i > 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
        poll();
    }
    public BallSeq poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        BallSeq result = segments[1];
        BallSeq last = segments[count];
        count--;
        int i =1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child + 1 <= count && segments[child].compareTo(segments[child+1]) == 1)
            {
                child += 1;
            }
            if(last.compareTo(segments[child]) == -1)
            {
                break;
            }
            segments[i] = segments[child];
            segments[i].position = i;
            i = child;
        }
        segments[i] = last;
        segments[i].position = i;
        return result;
    }
    public int size()
    {
        return count;
    }
    public int capacity()
    {
        return max;
    }
}
							

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

//* @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(sc.hasNext())
    {
        long a = sc.nextLong();
        long b = sc.nextLong();
        double c = sc.nextDouble();
        double d = sc.nextDouble();
        int steps = 0;
        if(a > b)
        {
            long temp = a;
        a = b;
        b = temp;
        }
        while(true)
        {
            if(c > d)
        {
            double temp = c;
            c = d;
            d = temp;
        }

        if(a >= c && b >=d)
        {
            break;
        }else if(b < d)
        {
            d = d/2;
            steps++;
        }else
        {
            c = c/2;
            steps++;
        }
        }
        System.out.println(steps);
    }
    }
}

							

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

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

public class Main {

    /**
     * @param args the command line arguments
     */
    static BigInteger []a=new BigInteger[10005];
    public static void main(String[] args) {
       // TODO code application logic here
        int n;
        a[0]=BigInteger.ONE;
        a[1]=BigInteger.ONE;
        for(int i=2;i<=10000;i++) a[i]=a[i-1].add(a[i-2]);
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            n=cin.nextInt();
            BigInteger ans=a[n-1].pow(4);
            ans=ans.add(a[n].pow(2).multiply(a[n-2].pow(2)));
            ans=ans.add(BigInteger.valueOf(6).multiply(a[n].multiply(a[n-2].multiply(a[n-1].pow(2)))));
            ans=ans.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(2));
            String s=ans.toString();
            StringBuffer sbf=new StringBuffer();
            int p=0;
            for(int i=s.length()-1;i>=0;i--){
                p++;
            sbf.append(s.charAt(i));
                if(p==3&&i>0){
                    sbf.append(",");
                    p=0;
                }
            }
            sbf.reverse();
            System.out.println(sbf.toString());
        }

    }

}


							

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

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

public class Main 
{
 public static void main(String []args)
 {
  SegmentTree segmentTree=new SegmentTree();
 }
};
class SegmentTree
{
 public SegmentTree()
 {
  tot=0;
  int n,m,left,right,value;
  String str;
  Scanner input=new Scanner(System.in);
  n=input.nextInt();
  m=input.nextInt();
  for(int i=1;i<=n;i++)
   a[i]=input.nextInt();
  creatTree(1,1,n);
  for(int i=0;i< m;i++)
  {
   str=input.next();
   if(str.charAt(0)=='Q')
   {
    left=input.nextInt();
    right=input.nextInt();
    System.out.println(query(1,left,right,0));
   }
   else
   {
    left=input.nextInt();
    right=input.nextInt();
    value=input.nextInt();
    insert(1,left,right,value);
   }
  }
 }
 public long creatTree(int now,int left,int right)
 {
  if(now>tot)
   tot=now;
  _left[now]=left;
  _right[now]=right;
  long lSum=0,rSum=0;
  if(left< right)
  {
   lSum=creatTree(2*now,left,(left+right)/2);
   rSum=creatTree(2*now+1,(left+right)/2+1,right); 
   _sum[now]=lSum+rSum;
  }
  else
   _sum[now]=a[left];
  return _sum[now];
 }
 public void insert(int now,int left,int right,int value)
 {
  if(now>tot)
   return ;
  if(left<=_left[now]&&right>=_right[now])
  {
   _d[now]+=value;
   return ;
  }
  long lSum=0,rSum=0;
  if(left<=(_left[now]+_right[now])/2)
   insert(2*now,left,right,value);
  if(right>(_left[now]+_right[now])/2)
   insert(2*now+1,left,right,value);
  if(2*now<=tot)
   lSum=_sum[2*now]+_d[2*now]*(_right[2*now]-_left[2*now]+1);
  if(2*now+1<=tot)
   rSum=_sum[2*now+1]+_d[2*now+1]*(_right[2*now+1]-_left[2*now+1]+1);
  _sum[now]=lSum+rSum;
 }
 public long query(int now,int left,int right,long d)
 {
  if(now>tot)
   return 0;
  if(left<=_left[now]&&right>=_right[now])
   return _sum[now]+(_d[now]+d)*(_right[now]-_left[now]+1);
  long lSum=0,rSum=0;
  if(left<=(_left[now]+_right[now])/2)
   lSum=query(2*now,left,right,d+_d[now]);
  if(right>(_left[now]+_right[now])/2)
   rSum=query(2*now+1,left,right,d+_d[now]);
  return lSum+rSum;
 }
 public static final int N=100005;
 public int tot;
 public int[] a=new int[N];
 public int[] _left=new int [3*N];
 public int[] _right=new int [3*N];
 public long[] _sum=new long [3*N];
 public long[] _d=new long [3*N];
} 
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] next;
 static String s1,s2;
 static int l1,l2,cnt;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  while((a--)!=0)
  {
    s1=in.readLine();
    s2=in.readLine();
    l1=s1.length();
    l2=s2.length();
    cnt=0;
    next=new int[l1];
    next();
    kmp();
    System.out.println(cnt);
   }
 }

 static void kmp()
 {
  int i=0,j=0;
  while(i< l2&&j< l1)
  {
    if(j==-1||s2.charAt(i)==s1.charAt(j))
    {
    i++;
    j++;
    }
    else j=next[j];
    if(j==l1)
    {
    cnt++;
    i=i-1;
    j=next[j-1];
    }
   }
 }

  static void next() 
  {
   int i = 0;
   next[0] = -1;
   int j = -1;
   while(i < l1 - 1) 
   {
    if(j == -1 || s1.charAt(i) == s1.charAt(j))
    {
        ++i;
        ++j;
        next[i] = j;
    }
    else
        j = next[j];
    }
  }

}

							

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;

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

    public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);
        int n;
        int[] m,o;
        while (scan.hasNext()){
            n=scan.nextInt();
            if (n==0) {
                break;
            }
            m=new int[n];
            o=new  int[n];

            for (int i = 0; i < m.length; i++) {
                m[i]=scan.nextInt();
            }
            int k;
            for (int i = 1; 1<< i <= m.length; i++) {
                o=java.util.Arrays.copyOf(m, n);
                k=1<< i;
                for (int j = 0; j < k/2; j++) {

                    //System.out.println("2*k+1 = " + (k-1+j));
                        m[2*j]=(o[j]+o[k/2+j])/2;
                        m[2*j+1]=(o[j]-o[k/2+j])/2;
                }
                // System.out.println("");

                
            }
           for (int K = 0; K < m.length; K++) {
                    System.out.print(m[K]+" ");
           }
            System.out.println("");
        }
        System.out.println("");
    }
}
							

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
        String rawStr = null;   
           
           
        char repeatChar = 'n';   
        int repeat = 0;   
        char temp = 'n';   
        int newLineFlag = 0;   
           
        for(int i = 0; i < num; i++)   
        {   
            newLineFlag = 0;   
            StringBuffer sb = new StringBuffer();   
            boolean oneLetter = false;   
            rawStr = cin.nextLine();   
               
            for(int j = 0; j < rawStr.length(); j++)   
            {   
                temp = rawStr.charAt(j);   
                if(newLineFlag == 0)   
                {   
                    repeatChar = temp;   
                    repeat = 1;   
                    newLineFlag = 1;   
                    if(j == rawStr.length()-1)   
                        oneLetter = true;   
                    continue;   
                }   
                   
                if(temp == repeatChar)   
                {   
                    repeat++;   
                }else  
                {   
                    sb.append(repeat);   
                    sb.append(repeatChar);   
                    repeatChar = temp;   
                    repeat = 1;   
                }      
                   
                if(j == rawStr.length()-1)   
                {   
                    sb.append(repeat);   
                    sb.append(repeatChar);   
                }   
            }   
               
            if(oneLetter == true)   
            {   
                System.out.println("1" + temp);   
            }else  
            {   
                System.out.println(sb.toString());     
            }   
               
        }   
  
    }   
  
}  

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
  
 int n,i,j,k1,k2,p[][]=new int[101][101];
 n=sc.nextInt();
    
 int len=n*n;
 for(i=0;i< len;i++)
   for(j=0;j< len;j++)
    p[i][j]=sc.nextInt();
 boolean bb[]=new boolean[101],is=true;
  //memset(bb,0,sizeof(bb));
 for(i=0;i< len;i++)
 {
    Arrays.fill(bb,false);
    for(j=0;j< len;j++)
    {
         if(p[i][j]==0)continue;
      if(bb[p[i][j]])break;
      bb[p[i][j]]=true;
    }
    if(j< len)break;
   }
  if(i< len)is=false;
  for(j=0;j< len;j++)
  {
    Arrays.fill(bb,false);
    for(i=0;i< len;i++)
    {
         if(p[i][j]==0)continue;
      if(bb[p[i][j]])break;
      bb[p[i][j]]=true;
    }
    if(i< len)break;
   }
   if(j< len)is=false;
   for(i=0;i< len;i+=n)
    {
    for(j=0;j< len;j+=n)
    {
       Arrays.fill(bb,false);
       for(k1=i;k1< i+n;k1++)
       {
        for(k2=j;k2< j+n;k2++)
        {
             if(p[k1][k2]==0)continue;
          if(bb[p[k1][k2]])break;
          bb[p[k1][k2]]=true;
        }
        if(k2!=j+n)break;
        }
       if(k1!=i+n)is=false;
       if(is==false)break;
    }
    if(is==false)break;
     }
     if(is) System.out.println("CORRECT");
     else System.out.println("INCORRECT");    
   }
}
							

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

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


public class Main {
    
 int n;

 BigInteger[] x = new BigInteger[115];
 BigInteger[] y = new BigInteger[115];
    
 public class Line {
    BigInteger a, b, c;
 }
    
    
 void run() {
   Scanner cin = new Scanner(System.in);
   BigInteger Zero = BigInteger.ZERO;
   n = cin.nextInt();
   int i;
   for(i = 0; i < n; ++i) {
    x[i] = cin.nextBigInteger();
    y[i] = cin.nextBigInteger();
   }
        
   int m = cin.nextInt(), ok = 0;
   for(i = 0; i < m; ++i) {
    int a, b, c, d;
    a = cin.nextInt();
    b = cin.nextInt();
    c = cin.nextInt();
    d = cin.nextInt();
    --a; --b; --c; --d;
    Line l1 = new Line(), l2 = new Line();
    l1.a = y[b].subtract(y[a]);
    l1.b = x[a].subtract(x[b]);
    l1.c = (l1.a.multiply(x[a])).add(l1.b.multiply(y[a]));
            
    l2.a = y[d].subtract(y[c]);
    l2.b = x[c].subtract(x[d]);
    l2.c = (l2.a.multiply(x[c])).add(l2.b.multiply(y[c]));
            
    BigInteger det = (l1.a.multiply(l2.b)).subtract((l2.a.multiply(l1.b)));
    BigInteger sx = (l2.b.multiply(l1.c)).subtract((l1.b.multiply(l2.c)));
    BigInteger sy = (l1.a.multiply(l2.c)).subtract((l2.a.multiply(l1.c)));
    int j;
    for(j = 0; j < n; ++j) {
        x[j] = x[j].multiply(det);
        y[j] = y[j].multiply(det);
    }
    if(sx.compareTo(Zero) == 0 && sy.compareTo(Zero) == 0) {
        if(ok == 0)
            ok = i+1;
    }
    x[n] = sx;
    y[n] = sy;
    n++;
    }
    System.out.println(ok);
   }

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

    }

}

							

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

import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 int n,L,v;
 n=sc.nextInt();
 L=sc.nextInt();
 int m=0;
 while((n--)!=0)
 {
     v=sc.nextInt();
     if(v%L==0)continue;
     int u=L-v%L;
     if(u>m)m=u;
  }
  System.out.printf("%d",m);
 }
}
							

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

//* @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);
    int n = sc.nextInt();
    Call[] calls = new Call[n];
    for(int i = 0; i < n; i++)
    {
        int q = sc.nextInt();
        int a = sc.nextInt();
        int x = sc.nextInt();

        calls[i] = new Call(q,a,x);
    }
    Arrays.sort(calls);

    int preQ = 0;
    int num = 0;
    int amount = 0;
    for(int i = 0; i < n; i++)
    {
        if(calls[i].q != preQ)
        {
            preQ = calls[i].q;
        num = 0;
        }
        if(calls[i].a == 1)
        {
        if(calls[i].x == 1)
        {
            amount += 40;
        }else
        {
            amount += 20;
        }
        amount += 10 * num;
        num++;

        }else
        {
        amount += 10;
        }
    }
    System.out.println(amount);
    }
}

class Call implements Comparable< Call>
{
    int q;
    int a;
    int x;

    Call(int q, int a, int x)
    {
        this.q = q;
    this.a = a;
    this.x = x;
    }

    public int compareTo(Call other)
    {
        if(this.q < other.q)
    {
        return -1;
    }else if(this.q == other.q)
    {
        return 0;
    }else
    {
        return 1;
    }
    }
}

							

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

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

public class Main{
 private static final String[] status = new String[] { "", "FILL(1)",
    "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" };
 private static boolean[][] visted = new boolean[101][101];
 private static int a;
 private static int b;
 private static int c;

 public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    for (int i = 0; i < 101; ++i) {
        for (int j = 0; j < 101; ++j)
            visted[i][j] = false;
    }
    a = sc.nextInt();
    b = sc.nextInt();
    c = sc.nextInt();
    bfs();
  }

  static void bfs() {
    boolean is = false;
    LinkedList< Node> queue = new LinkedList< Node>();
    Node p = new Node();
    p.aa = 0;
    p.bb = 0;
    visted[p.aa][p.bb] = true;
    queue.addLast(p);
    // visted[p.aa][p.bb] = true;
    // p = new Node();
    // p.aa = 0;
    // p.bb = b;
    // p.status.add(2);
    // visted[p.aa][p.bb] = true;
    // queue.addLast(p);
    while (!queue.isEmpty()) {
     Node front = queue.getFirst();
     queue.remove();
     int r = -1;
     for (int i = 1; i <= 6; ++i) {
      int aa = front.aa;
      int bb = front.bb;
      int flag = i;
      switch (flag) {
       case 1:
        aa = a;
        break;
       case 2:
        bb = b;
        break;
       case 3:
        aa = 0;
        break;
       case 4:
        bb = 0;
        break;
       case 5:
        r = b - bb;
        bb = bb + (r <= aa ? r : aa);
        aa = (r <= aa ? (aa - r) : 0);
        break;
       case 6:
        r = a - aa;
        aa = aa + (r <= bb ? r : bb);
        bb = (r <= bb ? (bb - r) : 0);
        break;
       default:
        break;
       }
       if (aa == c || bb == c) {
        int size = front.status.size();
        System.out.println(size + 1);
        for (int j = 0; j < size; ++j)
             System.out.println(status[front.status.get(j)]);
        System.out.println(status[flag]);
        is = true;
        return;
        }
        if (!visted[aa][bb]) {
         Node tmp = new Node();
         tmp.aa = aa;
         tmp.bb = bb;
         int size = front.status.size();
         for (int j = 0; j < size; ++j)
            tmp.status.add(front.status.get(j));
         tmp.status.add(flag);
         visted[aa][bb] = true;
         queue.addLast(tmp);
         }
     }
    }
    if (!is)
      System.out.println("impossible");
 }

 private static class Node {
    private int aa;
    private int bb;
    private ArrayList< Integer> status = new ArrayList< Integer>();
 }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
   Scanner in=new Scanner(System.in);
   int[] b2=new int[]{6,2,4,8};
   int[] b3=new int[]{1,3,9,7};
   int[] b7=new int[]{1,7,9,3};
   int[] b9=new int[]{1,9,1,9};
   int n=in.nextInt();
   int m=in.nextInt();
   int w=n-m;
   int e,a2=0,a3=0,a5=0,a7=0,a9=0;
   e=n;while((e=e/2)!=0) a2+=e;
   e=m;while((e=e/2)!=0) a2-=e;
   e=w;while((e=e/2)!=0) a2-=e;
   e=n;while((e=e/5)!=0) a5+=e;
   e=m;while((e=e/5)!=0) a5-=e;
   e=w;while((e=e/5)!=0) a5-=e;
   a3=f(n,3)-f(m,3)-f(w,3);
   a7=f(n,7)-f(m,7)-f(w,7);
   a9=f(n,9)-f(m,9)-f(w,9);
   int ans=1;
   if(a5>a2) System.out.println(5);
   else{
    a2-=a5;
    if(a2!=0){
         a2=a2%4;
      ans*=b2[a2];
      ans=ans%10;
    }
    ans*=b3[(a3%4+4)%4];
    ans=ans%10;
    ans*=b7[(a7%4+4)%4];
    ans=ans%10;
    ans*=b9[(a9%4+4)%4];
    ans=ans%10;
    System.out.println(ans);
    }
  }

  public static int f(int n,int a)
  {
    if(n==0) return 0;
    else return f(n/2,a)+g(n,a);
   }

  public static int g(int n,int a)
  {
    if(n==0)return 0;
    else if(n%10< a)return n/10+g(n/5,a);
    else return n/10+1+g(n/5,a);
  }
}
							

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

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

public class Main {
    
 public static void main(String[] args) {
        
    int i,n,ans;
    int way[] = new int[60];
    Scanner cin = new Scanner(System.in);
    
    while(cin.hasNext())
    {
        n = cin.nextInt();
        for(i=0;i< n;++i)
            way[i] = cin.nextInt();
        Arrays.sort(way,0,n);
        ans = search(n,way);
        System.out.println(ans);
    }
   }

  public static int search(int n,int way[])
  {
    int  ans=0,i,j;
    if(n==1) return way[0];
    if(n==2) return way[1];
    if(n==3) return min(way[2]+way[0]+way[1],way[2]+way[1]+way[1]);
    return search(n-2,way)+min(way[n-1]+way[0]+way[1]+way[1],way[n-1]+way[n-2]+way[0]+way[0]);
   }
    public static int min(int a,int b)
    {
        if(a>b) return b;
        return a;
    }
    
}

							

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


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

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int k1=0,k2=0,a=0,kk=0;
        int[] a1=new int[101],a2=new int[101],ans=new int[101];
        for(int i=0;i< n;++i){
            a=in.nextInt();
            if(a>=0)
                a1[k1++]=a;
            else a2[k2++]=a;
        }
        Arrays.sort(a1,0,k1);
        Arrays.sort(a2,0,k2);
        if(k%2==1){
            k--;
            if(k1>0)
                ans[kk++]=a1[--k1];
            else{
                for(int i=k2-1;i>k2-1-k;--i)
                    System.out.print(a2[i]+" ");
                System.out.println(a2[k2-1-k]);
                return ;
            }
        }
        int j2=0;
        for(int i=0;i< k/2;++i){
            int t1=-1000000000;
            int t2=-1000000000;
            if(k1==1&&k2-j2==1){
                ans[kk++]=a1[--k1];
                ans[kk++]=a2[j2++];
            }else{
                if(k1>1)
                    t1=a1[k1-1]*a1[k1-2];
                if(k2-j2>1)
                    t2=a2[j2]*a2[j2+1];
                if(t1>t2){
                    ans[kk++]=a1[--k1];
                    ans[kk++]=a1[--k1];
                }else{
                    ans[kk++]=a2[j2++];
                    ans[kk++]=a2[j2++];
                }
            }
        }
        Arrays.sort(ans,0,kk);
        for(int i=kk-1;i>0;--i)
            System.out.print(ans[i]+" ");
        System.out.println(ans[0]);
    }

}


							

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

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;
int main()
{
    int A,a,B,b,P;
    while (cin>>A>>a>>B>>b>>P)
    {
        map<int,int> m;
        if (a == b)
        {
            if (!(A + B <= P))
                printf("Non");
            else
                printf("Yesn");
            continue;
        }
        m[a] = A;
        m[b] = B;
        if (A > P || B > P)
        {
            printf("Non");
            continue;
        }
        if (A + B <= P)
        {
            printf("Yesn");
            continue;
        }

        map<int,int>::iterator p = m.begin();
        p++;
        if ((*p).first < (*m.begin()).second)
        {
            printf("Non");
            continue;
        }
        printf("Yesn");


    }
    return 0;
}

/*
Halloween Holidays
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 1827  Accepted: 706 

Description

Planet Cucurbita is inhabited with intelligent pumpkins. These pumpkins are not only extremely clever, they also are fond of tourism. One of their main routes is the Earth during Halloween.

As you know, pumpkins cannot move by themselves (intelligent pumpkins are not an exception), so they make somebody else to transport them. In the case of Halloween this is done by humans. First, they make people to grow special biological docking stations, then prepare the stations (people cut special holes, fire candles etc �C you know the procedure), and after these preparations pumpkins come and have fun. People usually do not see anything and think that this is just a holiday and that this holiday is for humans, but remember �C if somebody is frightened at Halloween, he was frightened not by his not-very-friendly friends, but by alien pumpkins.

To use the biological docking station, a pumpkin must have a special transmitter. It��s main elements are two rings made of gold and for some unexplainable reasons these rings should be cut from one round plate. The sizes of these rings (inner and outer radii) are pumpkin-specific, so each alien should order a special set for himself.

Mr. Calabaza, an adolescent pumpkin, wants to make his first trip to the Earth. He found a discount plate, which was not redeemed by a previous customer, and it is necessary to check, whether this plate allows Mr. Calabaza to cut the rings he needs from it, or he should order a new larger plate.

Input

The input file contains five integer numbers A, a, B, b, P (0 < A, a, B, b, P �� 1 000 000, a < A and b < B), separated with spaces. Here, A and B are the outer radii of the rings, a and b are the inner radii of the corresponding rings, and P is the plate radius.

Output

Output a word ��Yes�� if the plate suits Mr. Calabaza, or a word ��No�� if he needs to order another one.

Sample Input

2 1 5 3 6
Sample Output

Yes

*/
							

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

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

class Binary
{
    int n,i;
    long ret;
    long a[],c[];
    void init(int x)
    {
        n = x;
        a = new long [x+10];
        c = new long [x+10];
        for(i=0;i< x+10;++i)
        {
            a[i]=c[i]=0;
        }
    }
    void update(int x,long v)
    {
        a[x]+=v;
        for(i=x;i<=n;i+=lowbit(i)) c[i]+=v;
    }
    int lowbit(int x)
    {
        return (x)&(-x);
    }
    long query(int x)
    {
        for(ret=0,i=x;i>0;i^=lowbit(i)) ret+=c[i];
        return ret;
    }
}
public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int n,i,j;
    int way[] = new int[50010];
    int num[] = new int[50010];
    int mapping[]= new int[50010];
    
    BigInteger ans,temp;
        
    Binary array[] = new Binary[5];
    
     Scanner cin = new Scanner(System.in);
     while(cin.hasNext())
     {
    n = cin.nextInt();
    for(i=0;i< n;++i)
    {
        way[i]=cin.nextInt();
        num[i]=way[i];
    }
    Arrays.sort(num,0,n);
    mapping[0]=2;
    for(i=1;i< n;++i)
    {
        if(num[i]==num[i-1]) mapping[i]=mapping[i-1];
        else mapping[i]=mapping[i-1]+1;
    }
        
    for(i=0;i< n;++i)
    {
        way[i]=mapping[binary_search(0,n-1,way[i],num)];
    }
    for(i=0;i< 5;++i)
    {
        array[i]=new Binary();
        array[i].init(50010);
    }
            
    ans = new BigInteger("0");
    for(i=0;i< n;++i)
    {
        for(j=4;j>0;--j)
        {
           array[j].update(way[i], array[j-1].query(way[i]-1));
        }
        array[1].update(way[i], 1);
                
        temp = BigInteger.valueOf(array[4].query(way[i]-1));
        ans = ans.add(temp);
    }
            
    System.out.println(ans);
            
    }
 }
    public static int binary_search(int left,int right,int value,int num[])
    {
        int mid;
        while(left+1< right)
        {
            mid=(left+right)/2;
            if(num[mid]>value) right = mid;
            else left = mid;
        }
        if(num[left]==value) return left;
        return right;
    }

}

							

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

//* @author: 82638882@163.com<br />
/*��Ŀ���⣺��n��ͬѧ���һ��Բ��һ��ʦ���ǹ��4η����1��2��4��7...��ͬѧ�����Ƿ�ÿ��ͬѧ���ܵõ�����һ���ǡ�
 *����д�����صij������1~100�������ѷ��֣�ֻ�е�n=2^k��kΪ����ʱ�����YES��
 */

import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
    Scanner in=new Scanner(System.in);
    
    while(in.hasNext())
    {
        int a=in.nextInt();
        while(a%2==0)
            a=a/2;
        if(a==1) System.out.println("YES");
        else System.out.println("NO");
    }
  }
}
							

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

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.text.DecimalFormat;

class Main
{
  public static boolean isvowel(char a)
  {
     if (a=='a' || a=='e' || a=='i' || a=='o' || a=='u' || a=='y')
      return true;
     else
      return false;
  }

  public static boolean isword(char a)
  {
    if (a==',' || a==''' || a=='"')
      return true;
    else
      return false;
   }

  public static boolean issen(char a)
  {
     if (a==':' || a==';' || a=='?' || a=='.' || a=='!')
     return true;
     else
     return false;
  }

  public static void main(String [] args) throws IOException
  {
    Scanner cin=new Scanner(new BufferedInputStream(System.in));
    DecimalFormat df=new DecimalFormat("0.00");
    String inp,temp;
    int word,wordnum=0,sentnum=0,sylnum=0,i,len;
    double score;
    boolean hasaddsyl,hasaddword,hasvow,sinquo,douquo;
    while (cin.hasNext())
    {
    inp=cin.next();
    temp=inp.toLowerCase();
    len=temp.length();
    word=0;
    hasaddsyl=false;
    hasaddword=false;
    hasvow=false;
    sinquo=false;
    douquo=false;
    for (i=0;i< len;i++)
    {
      if (temp.charAt(i)>='a' && temp.charAt(i)<='z')
       {
        word++;
        if ((word<=3) && ((i+1==len) || isword(temp.charAt(i+1)) || issen(temp.charAt(i+1))))
        {
              word=0;
           if (!hasvow)
            sylnum++;
        }
        else if (isvowel(temp.charAt(i)))
        {
           hasvow=true;
           if (!hasaddsyl)
           {
            sylnum++;
            hasaddsyl=true;
           }
           else if (!isvowel(temp.charAt(i-1)))
           {
            if (temp.charAt(i)=='e')
               {
              if (((i+1==len) || (temp.charAt(i+1)>'z') || 
               (temp.charAt(i+1)< 'a')) && (temp.charAt(i-1)=='l'))
             {
               sylnum++;
               continue;
             }
             if ((i+1==len) || ((temp.charAt(i+1)< 'a') || (temp.charAt(i+1)>'z')))
               continue;
             if ((i+1< len) && ((temp.charAt(i+1)=='s') || 
               (temp.charAt(i+1)=='d')) && ((i+2==len) || 
               (temp.charAt(i+2)>'z') || (temp.charAt(i+2)< 'a')))
               continue;
             else
               sylnum++;
            }
            else
              sylnum++;
           }
       }
    }
    else if (isword(temp.charAt(i)))
    {
        hasvow=false;
        if (temp.charAt(i)==''' && !sinquo)
        {
             sinquo=true;
          continue;
        }
        if (temp.charAt(i)=='"' && !douquo)
        {
           douquo=true;
           continue;
        }
        wordnum++;
        word=0;
        hasaddword=true;
        hasaddsyl=false;
    }
    else if (issen(temp.charAt(i)))
    {
       wordnum++;
       word=0;
       hasvow=false;
       if ((i+1< len) && temp.charAt(i)=='.' && temp.charAt(i+1)=='.')
        while ((i+1< len) && temp.charAt(i+1)=='.')
             i++;
       else
        sentnum++;
        hasaddword=true;
    }
    }
    if (!hasaddword)
        wordnum++;
  }
  score=206.835-1.015*((double)(wordnum)/(double)(sentnum))-84.6*((double)(sylnum)/(double)(wordnum));
  System.out.println(df.format(score));
 }
}
							

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

import java.io.*;
import java.util.*;
public class Main
{
  static  treex[] mytreex=new treex[210000];
  static int[] hash=new int[100005];
  static int[] left=new int[100005];
  static int[] right=new int[100005];
  static int[] data=new int[100005];
  static boolean build=false;
  static int k=0;
  
  public static void main(String args[]) throws Exception
  {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss;
    StringBuffer res=new StringBuffer();
    while(true)
    {
        build=false;
       ss=in.readLine().split(" ");
       int n=Integer.parseInt(ss[0]);
       if(n==0)
           break;
       int q=Integer.parseInt(ss[1]);
       ss=in.readLine().split(" ");
       k=1;
       for(int i=0;i< n;i++)
       {
           data[i]=Integer.parseInt(ss[i]);
           if(i>0&&data[i]!=data[i-1])
           {
               right[k]=i-1;
               left[k+1]=i;
              k++;
           }
           hash[i]=k;
         }
         right[k]=n-1;
         for(int i=0;i< q;i++)
         {
            ss=in.readLine().split(" ");
            int begin=Integer.parseInt(ss[0])-1;
            int end=Integer.parseInt(ss[1])-1;
            if(hash[begin]==hash[end])
            {
                  res.append(end-begin+1);
                  res.append("n");
                  continue;
            }
            if(hash[end]-hash[begin]==1)
            {
                int l=right[hash[begin]]-begin+1;
                int r=end-left[hash[end]]+1;
                int temp=l>r?l:r;
                res.append(temp);
                res.append("n");
                continue;
                        
            }
            if(!build)
            {
                  build=true;
                  buildtreex(1,k,1);
            }
            int n1=right[hash[begin]]-begin+1;
            int n2=end-left[hash[end]]+1;
            if(n1< n2)
                  n1=n2;
            n2=query(hash[begin]+1,hash[end]-1,1);
            res.append(n1>n2?n1:n2);
            res.append("n");    

        }
      }
      System.out.print(res.toString());
   }
            
  public static void buildtreex(int a,int b,int i)
  {
      if(mytreex[i]==null)
            mytreex[i]=new treex();
      mytreex[i].left=a;
      mytreex[i].right=b;
      if(a==b)
           mytreex[i].max=right[a]-left[a]+1;
      if(a!=b)
      {
           int mid=(a+b)/2;
           buildtreex(a,mid,i*2);
           buildtreex(mid+1,b,i*2+1);
           mytreex[i].max=mytreex[i*2].max>mytreex[i*2+1].max?mytreex[i*2].max:mytreex[i*2+1].max;
      }
   }
            
            
  public static int query(int a,int b,int i)
  {
     if(a==mytreex[i].left&&b==mytreex[i].right)
          return mytreex[i].max;
     int mid=(mytreex[i].left+mytreex[i].right)/2;
     if(b<=mid)
        return query(a,b,2*i);
     else if(a>=mid+1)
        return query(a,b,2*i+1);
     else
     {
       int l =query(a,mid,2*i);
       int r = query(mid+1,b,2*i+1);
       return l>r?l:r;
     }
  }
            
}

class treex
{
    int left;
    int right;
    int max;
}
							

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

//* @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();
    int b=in.nextInt();
    String[] s1=new String[a];
    String[] s2=new String[a];
    for(int i=0;i< a;i++)
    {
        s1[i]=in.next();
        s2[i]=in.next();
    }
    for(int i=0;i< b;i++)
    {
         String s=in.next();
      boolean bb=false;
      for(int j=0;j< a;j++)
      {
       if(s.equals(s1[j]))
       {
        System.out.println(s2[j]);
        bb=true;
        break;
        }
       }
      if(!bb){
        if(s.endsWith("y"))
        {
            if(s.endsWith("ay")||s.endsWith("ey")||s.endsWith("iy")||s.endsWith("oy")||s.endsWith("uy"))
            System.out.println(s+"s");
         else
            System.out.println(s.substring(0,s.length()-1)+"ies");
        }
        else if(s.endsWith("o")||s.endsWith("s")||s.endsWith("ch")||s.endsWith("sh")
                ||s.endsWith("x")) System.out.println(s+"es");
        else System.out.println(s+"s");
        }
      }
    }
}
							

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

/* @author: */
//����һ�ų�ΪH��Ϊw��ֽ��Ҫ����һ���������Բ����ʹ����Բ�İ뾶����
//���}�����һ����wΪ����Բ���ܳ���һ����H-2RΪ����Բ���ܳ���Ȼ��ȡ���ֵ�ͺ���

import java.util.Scanner;
import java.util.Arrays;
public class Main{
  static double pi=Math.PI;
  static double epx=1e-6;
  
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  double w,h,v1,v2,temp,r,d;   
    while(sc.hasNext()){
     w=sc.nextDouble();
     h=sc.nextDouble();
     if(w==0&&h==0) break;
        if(h>w){temp=h;h=w;w=temp;}   
        v1=h*h*(w-h/pi)/(4.0*pi);   
        d=w/(pi+1);   
        if(d>h+epx){/*�ж�d�Ƿ������*/  
           r=h/2.0;   
          v2=pi*r*r*h;   
        }   
        else v2=pi*w*w*h/(4.0*(pi+1)*(pi+1));   
        System.out.printf("%.3fn",Math.max(v1,v2));   
    }   
   }
  
}  

							

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

import java.util.Scanner;
import java.util.Arrays;
public class Main{
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
     int n,m,c;
     while(sc.hasNext()){
        n=sc.nextInt();
        if(n==0) break;
        m=sc.nextInt();
        c=sc.nextInt();
       int t=(m-7)*(n-7);
    int t1=(t+1)/2;
    if (c==0) System.out.printf("%dn",t-t1);
    else System.out.printf("%dn",t1);
    
  }
}
}
							

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

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


public class Main{

public static void main(String[] args) throws Exception{
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 String str ;
 while((str=in.readLine())!=null){
  StringTokenizer toke1 = new StringTokenizer(str);
  StringTokenizer toke2 = new StringTokenizer(in.readLine());
  int m = Integer.parseInt(toke1.nextToken());
  String str1 = toke1.nextToken();
  int n = Integer.parseInt(toke2.nextToken());
  String str2 = toke2.nextToken();
        
  int[][]array = new int[m+1][n+1];
        
  for(int i=0;i<=m;i++){
    array[i][0] = i;
  }
  for(int i=0;i<=n;i++){
    array[0][i] = i;
    }
        
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
     if(str1.charAt(i-1)==str2.charAt(j-1))
      array[i][j] = Math.min(Math.min(array[i-1][j-1], array[i-1][j]+1), array[i][j-1]+1);
     else
      array[i][j] = Math.min(Math.min(array[i-1][j-1]+1, array[i-1][j]+1), array[i][j-1]+1);
    }
    }
        
    System.out.println(array[m][n]);
    }
    }

}


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int a,cnt=1;
 static int[] rank,un;
 static boolean[][] map;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss=in.readLine().split(" ");
    a=Integer.parseInt(ss[0]);
    map=new boolean[a+1][a+1];
    rank=new int[a+1];
    un=new int[a+1];
    for(int i=1;i<=a;i++)
        un[i]=i;
    int b=Integer.parseInt(ss[1]);
    for(int i=0;i< b;i++)
    {
        ss=in.readLine().split(" ");
        int x=Integer.parseInt(ss[0]);
        int y=Integer.parseInt(ss[1]);
        map[x][y]=map[y][x]=true;
    }
    dsf(1,1,rank,un);
    int cnt=0;
    for(int i=1;i<=a;i++)
        rank[i]=0;
    for(int i=1;i<=a;i++)
    {
      int yy=root(i,un);
      for(int j=1;j<=a;j++)
      {
        if(!map[i][j])continue;
        int ww=root(j,un);
        if(ww!=yy)
        {
             rank[yy]++;
          if(rank[yy]>1)break;
        }
       }
    }
    for(int i=1;i<=a;i++)
    {
       if(rank[i]==1)cnt++;
    }
    System.out.println((cnt+1)/2);
 }


 static void dsf(int n,int pre,int[] rank,int[] un)
 {
    if(rank[n]!=0)
    {
      for(int i=1;i<=a;i++)
        if(rank[i]>rank[n]) union(i,n,un);
    }
    else
    {
      rank[n]=cnt++;
      for(int i=1;i<=a;i++)
      {
        if(map[i][n]&&i!=pre&&root(i,un)!=root(n,un))
          dsf(i,n,rank,un);
       }
       rank[n]=0;
    }
  }

static void union(int a,int b,int[] un)
 {
    int x1=root(a,un);
    int y1=root(b,un);
    if(x1>y1)un[x1]=y1;
    else un[y1]=x1;
 }

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


							

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

//* @author: 
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Node
{
    int index;
    Node next;
}
public class Main
{
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    final int N=9997;

    int [][]snow=new int[100010][6];
    boolean check(int s1,int  s2)
    {
        boolean flag;
        int temp;
        
        for(int j=0;j< 6;j++)
        {
            flag=true;
            for(int step=0;step< 6;step++)
            {
                if(snow[s1][(j+step)%6]!=snow[s2][step])
                {    flag=false;    break;    }
            }
            if(flag) return true;
        }
        
        for(int j=0;j< 6;j++)
        {
            flag=true;
            for(int step=0;step< 6;step++)
            {
                temp=j-step;
                if(temp< 0) temp+=6; 
                if(snow[s1][temp]!=snow[s2][step])
                {    flag=false;    break;    }
            }
            if(flag) return true;
        }    
        return false;
    }
    boolean solve() throws IOException
    {
        int num,sum;
        String input;
        StringTokenizer st;
        num=Integer.parseInt(cin.readLine());
        
        Node[]vs=new Node[N];
        for(int i=1;i<=num;i++)
        {
            sum=0;
            input=cin.readLine();
            st=new StringTokenizer(input);
            for(int j=0;j< 6;j++)
            {
                snow[i][j]=Integer.parseInt(st.nextToken());
                sum+=snow[i][j];
            }
            if(vs[sum%N]==null)        //���t��
            {
                Node node=new Node();
                node.index=i;
                node.next=null;
                vs[sum%N]=node;
            }
            else
            {
                Node node=new Node();
                node.index=i;
                node.next=vs[sum%N];
                vs[sum%N]=node;
            }
        }
        for(int i=0;i< N;i++)
        {
            for(Node n1=vs[i]; n1!=null; n1=n1.next)
                for(Node n2=n1.next; n2!=null; n2=n2.next)
                    if(check( n1.index , n2.index ))    return true;
        }
        return false;
    }

    public static void main(String args []) throws IOException
    {
        Main test=new Main();
        if(test.solve())
            System.out.println("Twin snowflakes found.");
        else
            System.out.println("No two snowflakes are alike.");            
    }
}

 


							

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

//* @author ������<hongxp11@163.com>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
 * @param args
 * @throws IOException
 */
public static int count(String a, String b) {
 int len = a.length();
 int result = 1;
 for (int i = 0; i < len; i++) {
    if (Character.isDigit(a.charAt(i))) {
        if (a.charAt(i) > b.charAt(i)) {
            for (int j = i + 1; j < len; j++) {
                if (a.charAt(j) == '?')
                    result *= 10;
            }
            return result;
        }
        if (a.charAt(i) < b.charAt(i))
            return 0;
    } else {
        if (len == i + 1)
            return '9' - b.charAt(i);
        else {
            String new_a = a.substring(i + 1);
            String new_b = b.substring(i + 1);
            for (int j = i + 1; j < len; j++) {
                if (a.charAt(j) == '?')
                    result *= 10;
            }
            return ('9' - b.charAt(i)) * result + count(new_a, new_b);
        }
    }
  }
  return 0;
}

 public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
        String wild = br.readLine();
        if (wild.equals("#"))
            break;
        String num = br.readLine();
        System.out.println(count(wild, num));
    }
 }

}

							

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

import java.util.regex.*;import java.util.*;
public class Main { 
     public static void main(String[] args){ 
         String str; 
         int n; 
         Scanner cin = new Scanner(System.in);
          n=cin.nextInt();  
          str=cin.nextLine(); 
         Pattern pattern = Pattern.compile("(\s)*(\+|\-)?(\d)+(\.(\d)+)?((e|E)(\+|\-)?(\d)+)?");
         int i;
          for(i=0;i< n;++i){
              str=cin.nextLine(); 
             Matcher matcher = pattern.matcher(str); 
             if(matcher.matches()){ 
                 System.out.println("LEGAL"); 
             } 
             else{ 
                 System.out.println("ILLEGAL");
              } 
         } 
     }
}


							

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

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.Scanner;   
  
/**  
 *  
 * poj3331  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int a = scan.nextInt();   
                int b = scan.nextInt();   
                BigDecimal sum = BigDecimal.ONE;   
                while (a > 0) {   
                    BigDecimal aa = new BigDecimal(a);   
                    sum = sum.multiply(aa);   
                    a--;   
                }   
                char[] cs = sum.toString().toCharArray();   
                int count = 0;   
                String s = b+"";   
                for (int k = 0; k < cs.length; k++) {   
                    if ((cs[k]+"").equals(s)) {   
                        count++;   
                    }   
                }   
                System.out.println(count);   
            }   
        }   
    }   
}  


							

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

 import java.util.*;  
 import java.text.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         while(true)  
         {  
             int num = cin.nextInt();  
             if(num == 0)  
                 break;  
               
             int[] list = new int[num];  
             int max = 0;  
             int min = 1000;  
             int result = 0;  
             int tmp = 0;  
             for(int i = 0; i < num; i++)  
             {  
                 tmp = cin.nextInt();  
                 if(tmp > max)  
                     max = tmp;  
                 if(tmp < min)  
                     min = tmp;  
                 result += tmp;  
             }  
             result = (result - max - min)/(num-2);  
             DecimalFormat df = new DecimalFormat("");  
             System.out.println(df.format(result));  
         }  
   
     }  
}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
 public static void main(String args[]) throws Exception {
    Scanner cin=new Scanner(System.in);
    BigInteger s,M;
    int p,i;
    while(cin.hasNext())
    {
        p=cin.nextInt();
        s=BigInteger.valueOf(4);
        M=BigInteger.ONE;
        M=M.shiftLeft(p).subtract(BigInteger.ONE);
        for(i=0;i< p-2;++i)
        {
            s=s.multiply(s).subtract(BigInteger.valueOf(2));
            while(s.bitLength()>p)
            {
                s=s.shiftRight(p).add(s.and(M));
            }
        }
        if(s.compareTo(BigInteger.ZERO)==0||s.compareTo(M)==0)
        {
            System.out.println(0);
            continue;
        }
        String ans="";
        while(s.compareTo(BigInteger.ZERO)>0)
        {
            long buf=s.mod(BigInteger.valueOf(16)).longValue();
            ans+=Integer.toHexString((int)buf);
            s=s.divide(BigInteger.valueOf(16));
        }
        for(i=ans.length()-1;i>=0;--i)System.out.print(ans.charAt(i));
        System.out.println();
    }
  }
}
							

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

//* @author: 

import java.io.*;
import java.util.Arrays;
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
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return Integer.parseInt(st.nextToken());
}
static String nextString() 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 Node //���ڽӱ�
{
int now,v=1;
Node next;
Node(int y)
{
   now=y;
   next=null;
}
}

class TreeArray //��״����
{
    int value[],n;
    int now;
    Node tree[];
    int pis[][];
    TreeArray(int num,Node e[])
    {
    n=num;
    value=new int[n+1];
    tree=e;
    pis=new int[n+1][2];
    Arrays.fill(value,0);
    }
    
    int lowBit(int t)
    {
    return t&(t^(t-1));
    }
    
    void plus(int a,int i)
    {
    while(i<=n)
    {
       value[i]+=a;
        i+=lowBit(i);
    }
    }
    
    int getSum(int i)
    {
    int sum=0;
    while(i>0)
    {
       sum+=value[i];
       i=i-lowBit(i);
    }
    return sum;
    }
    void dfs(int t) //dfs��¼ʱ��
    {
    pis[t][0]=now;
    now++;
    Node p=tree[t].next;
    while(p!=null)
    {
       dfs(p.now);
       p=p.next;
    }
    pis[t][1]=now;
    
    }
    void init()
    {
    now=0;
    dfs(1);
    for(int i=1;i<=n;i++) //��ʼ����״����
    {
       plus(1,i); 
    }
    }
}

public class Main {
    public static void main(String args[]) throws IOException
    {
    int n,t1,t2,i;
    String s;
    n=cin.nextInt();
    Node lunch[]=new Node[n+1],temp;
    for(i=1;i<=n;i++)
    {
       lunch[i]=new Node(i);
    }
    for(i=0;i< n-1;i++)
    {
       t1=cin.nextInt();
       t2=cin.nextInt();
       temp=new Node(t2);
         temp.next=lunch[t1].next;
         lunch[t1].next=temp;
    }
    TreeArray data=new TreeArray(n,lunch);
    data.init();
    n=cin.nextInt();
    for(i=0;i< n;i++)
    {
       s=cin.nextString();
       t1=cin.nextInt();
       if(s.charAt(0)=='C')
       {
        if(data.tree[t1].v==1)
        {
         data.tree[t1].v=0;
         data.plus(-1,data.pis[t1][0]+1);
        }
        else
        {
         data.tree[t1].v=1;
         data.plus(1,data.pis[t1][0]+1);
        }
       }
       else 
       {
        t2=data.getSum(data.pis[t1][0]);
        int t3=data.getSum(data.pis[t1][1]);
        System.out.println(t3-t2);
       }
    }
    }
}