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

//* @author 
import java.util.*;
public class Main{
  public static void main(String args[]){
  
    int k,n;
    Scanner in=new Scanner(System.in);
    k=in.nextInt();
    init();
    while(k-->0){
        n=in.nextInt();
       System.out.printf("%dn",s[n]);
    }
   
   }

  static int MAX=80000;
  static long s[]=new long[MAX];       //���ڴ洢�������
  static long d2[]=new long[MAX];     //�洢���к���������2�ҷ���������
  static long d3[]=new long[MAX];     //�洢���к���������3�ҷ���������
  static long d5[]=new long[MAX];
  static long d7[]=new long[MAX];

  public static void init(){
    int i;
    int pos2,pos3,pos5,pos7;
    long a,b;
    s[1]=1;
    pos2=pos3=pos5=pos7=1;
    for(i=1;i< MAX-1;i++){
        d2[i]=s[i]*2;
        d3[i]=s[i]*3;
        d5[i]=s[i]*5;
        d7[i]=s[i]*7;
        while(d2[pos2]<=s[i])pos2++;     //��������С��s[i]����ô��һ���Ѿ���s[i]�У�����ȥ��
        while(d3[pos3]<=s[i])pos3++;     //��Ȼs[i]�Ǵ��ĸ������д�С����ѡ��4�ģ�
        while(d5[pos5]<=s[i])pos5++;     //�����������һ������ȷ��
        while(d7[pos7]<=s[i])pos7++;
        a=d2[pos2]< d3[pos3]?d2[pos2]:d3[pos3];
        b=d5[pos5]< d7[pos7]?d5[pos5]:d7[pos7];
        s[i+1]=a< b?a:b;
    }
  }
}



							

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

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

public class Main {

    /**
     * @param args
     */
    public static boolean isSubsequence(String s1, String s2) {
        int len = s2.length();
        int index = -1;
        int i = 0;
        for (i = 0; i < len; i++) {
            index = s1.indexOf(s2.charAt(i), index + 1);
            if (index == -1) {
                break;
            }
        }
        if (i == len && index != -1)
            return true;
        index = -1;
        for (i = len; i > 0; i--) {
            index = s1.indexOf(s2.charAt(i - 1), index + 1);
            if (index == -1)
                break;
        }
        if (i == 0 && index != -1)
            return true;
        return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        for (int i = 0; i < num; i++) {
            String s1 = in.next();
            String s2 = in.next();
            if (isSubsequence(s1, s2)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

}

							

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

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

public class Main {
    static final int N = 20;
    static int n,m;
    static double front[] = new double[N],rear[] = new double[N],cnt[]=new double[N*N];
    
    static double Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    
public static void main(String[]args) throws Exception{
 int i;
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
 while(true){
    n = (int) Get_Num(cin);
    if(n<=0) break;
    m = (int) Get_Num(cin);
    for(i=0;i< n;++i)
        front[i] = Get_Num(cin);
    for(i=0;i< m;++i)
        rear[i] = Get_Num(cin);
    System.out.printf("%.2fn",solve());
  }
 }

static double solve(){
  double ans=0.0;
  int i,j,top=0;
  for(i=0;i< n;++i){
    for(j=0;j< m;++j){
        cnt[top++] = rear[j]/front[i];
    }
   }
  Arrays.sort(cnt,0,top);
  for(i=1;i< top;++i){
    ans = ans>(cnt[i]/cnt[i-1])?ans:(cnt[i]/cnt[i-1]);
  }
    return ans;
 }
}

							

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

import java.util.Scanner;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        while (scan.hasNext()) {   
            double temperature = 0, dewpoint = 0, humidex = 0;   
            String[] ss = scan.nextLine().split(" ");   
            String sa = ss[0];   
            if (sa.equals("E")) {   
                break;   
            }   
            double a = Double.parseDouble(ss[1]);   
            String sb = ss[2];   
            double b = Double.parseDouble(ss[3]);   
            if (sa.equals("T") && sb.equals("D")) {   
                temperature = a;   
                dewpoint = b;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                humidex = temperature + h;   
            }   
            if (sa.equals("D") && sb.equals("T")) {   
                temperature = b;   
                dewpoint = a;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                humidex = temperature + h;   
            }   
            if (sa.equals("D") && sb.equals("H")) {   
                dewpoint = a;   
                humidex = b;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                temperature = humidex - h;   
            }   
            if (sa.equals("H") && sb.equals("D")) {   
                dewpoint = b;   
                humidex = a;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                temperature = humidex - h;   
            }   
            if (sa.equals("T") && sb.equals("H")) {   
                temperature = a;   
                humidex = b;   
                double h = humidex - temperature;   
                double e = h / 0.5555 + 10.0;   
                dewpoint = 1 / ((1 / 273.16) - Math.log(e / 6.11) / 5417.7530) - 273.16;   
            }   
            if (sa.equals("H") && sb.equals("T")) {   
                temperature = b;   
                humidex = a;   
                double h = humidex - temperature;   
                double e = h / 0.5555 + 10.0;   
                dewpoint = 1 / ((1 / 273.16) - Math.log(e / 6.11) / 5417.7530) - 273.16;   
            }   
            System.out.print("T ");   
            System.out.printf("%.1f", temperature);   
            System.out.print(" D ");   
            System.out.printf("%.1f", dewpoint);   
            System.out.print(" H ");   
            System.out.printf("%.1f", humidex);   
            System.out.println();   
        }   
    }   
}  


							

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

// author:M.J
import java.util.*;
import java.io.*;
public class Main{
 public static void main(String[] args){
  Scanner in = new Scanner(new BufferedInputStream(System.in));
    int T = in.nextInt();
    while(T > 0){
        T--;
        int n = in.nextInt();
        int k = in.nextInt();
        n--;
        int curr = k;
        int flag = 0;
        int ans = 1;
        while(n > 0){
            n--;
            k = in.nextInt();
            if(flag%2==0 && curr < k)
                curr = k;
            else if(flag%2==1 && curr > k)
                curr = k;
            if(flag%2==0 && k < curr){
                flag ++;
                ans ++;
                curr = k;
            }
            else if(flag%2==1 && k > curr){
                flag ++;
                ans ++;
                curr = k;
            }
        }
        System.out.println(ans);
    }
   }
}

							

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

//* @author: 
import java.util.Scanner;
import java.util.Stack;

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

 public void init() {
  Scanner sc = new Scanner(System.in);
  char[] s;
  boolean flag;
  while (!sc.hasNextInt()) {
    flag = true;
    s = sc.next().toCharArray();
    for (int i = 0; i < 32; i++) {
        if (!check(i, s)) {
            flag = false;
            break;
        }
    }
    if (flag)
        System.out.println("tautology");
    else
        System.out.println("not");
   }
 }

  public boolean check(int i, char[] s) {
   Stack< Integer> stack = new Stack< Integer>();
   for (char c : s) {
    if (c >= 'p' && c <= 't') {
        int d = c - 'p';
        d = (1 <<  d & i) >> d;
        boolean flag = true;
        while (flag) {
            if (stack.isEmpty()) {
                stack.push(d);
                flag = false;
            } else if (isoperate(stack.peek())) {
                stack.push(d);
                flag = false;
            } else if (stack.peek() == 'N') {
                d = 1 - d;
                stack.pop();
            } else {
                int dd = stack.pop();
                int oper = stack.pop();
                switch (oper) {
                case 'K':
                    d &= dd;
                    break;
                case 'A':
                    d |= dd;
                    break;
                case 'C':
                    d = dd - d > 0 ? 0 : 1;
                    break;
                case 'E':
                    d = 1 - (d ^ dd);
                    break;
                default:
                    break;
                }
            }
        }
    } else {
        stack.push((int) c); 
    }
   }

   return stack.pop() == 1;
  }


  private boolean isoperate(Integer peek) {
    switch (peek.intValue()) {
    case 'K':
    case 'A':
    case 'C':
    case 'E':
        return true;
    default:
        return false;
    }
  }

}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    static long[] a=new long[]{
        1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000
    };
    static long[] b=new long[]{
        0,1,11,192,2893,38894,488895,5888896,68888897,788888898
    };
    static long[] c=new long[]{
        0,1,20,300,4000,50000,600000,7000000,80000000,900000000
    };
    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(" ");
            long a=Long.parseLong(ss[0]);
            long b=Long.parseLong(ss[1]);
            if(a==-1&&b==-1)break;
            if(a==0)System.out.println(f(b)+1);
            else System.out.println(f(b)-f(a-1));
        }
    }
    static long f(long w)
    {
        int i;
        long q=w;
        for(i=0;i< 10;i++)
            if(a[i]>w)break;
        long sum=0;
        for(int j=i-1;j>0;j--)
        {
            long u=w/a[j];
            if(u>0)
                sum+=b[j]+(u-1)*c[j];
            w=w%a[j];
        }
        long total=0,oo=0;
        w=q;
        String s=w+"";
        for(int j=1;j< i-1;j++)
        {
            if(w%(a[j]*10)>=a[j]){
                total+=a[j]-1;
                oo+=total;
            }
            else oo+=w%(a[j]*10);
        }
        int bb=0;
        long yy=0;
        for(int g=1;g< s.length();g++)
        {
            if(s.charAt(g)!='0'){
                bb++;
                continue;
            }
            yy+=(Math.pow(10, s.length()-g-1)-1)*bb;
        }
        sum+=oo;
        sum+=yy;
        return sum;    
    }
}
							

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

//* @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 sl,sr,left,right;
    int nn=sc.nextInt();
    while((nn--)!=0)
    {
      int l=sc.nextInt();
      int n=sc.nextInt();
        l*=100;sl=0;sr=0;left=0;right=0;
        for (int i=1;i<=n;i++) {
         int  t=sc.nextInt();
         char s[]=sc.next().toCharArray();
            if (s[0]=='l') {
                 if (sl+t>l) {sl=t;left++;}
                 else sl+=t;
            }
            else {
                 if (sr+t>l) {sr=t;right++;}
                 else sr+=t;
            }
        }
        if (sl!=0) left++;
        if (sr!=0) right++;
        System.out.printf("%dn",left>right?left+left-1:right+right);        
    }
  }
}
							

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

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
public class Main {   
  
    public static final int MAX = 200000;   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            int k = scan.nextInt();   
            System.out.println(catchTheCow(n, k));   
        }   
    }   
  
    public static int catchTheCow(int n, int k) {   
        if (n == k) {   
            return 0;   
        }   
        LinkedList<Integer> queue = new LinkedList();   
        boolean[] visited = new boolean[MAX + 5];   
        int[] minutes = new int[MAX + 5];   
        visited[n] = true;   
        queue.add(n);   
        while (!queue.isEmpty()) {   
            int current = queue.removeFirst();   
            for (int i = 0; i < 3; i++) {   
                int next = current;   
                if (i == 0) {   
                    next++;   
                } else if (i == 1) {   
                    next--;   
                } else if (i == 2) {   
                    next <<= 1;   
                }   
                if (next < 0 || next > MAX) {   
                    continue;   
                }   
                if (!visited[next]) {   
                    queue.add(next);   
                    visited[next] = true;   
                    minutes[next] = minutes[current] + 1;   
                }   
                if (next == k) {   
                    return minutes[k];   
                }   
            }   
        }   
  
        return 0;   
    }   
}  
							

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

//* @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();
  int[] c=new int[a];
  int total=0;
  int min=0;
  for(int i=0;i< a;i++)
  {
   c[i]=in.nextInt();
   total+=c[i];
   if(c[i]>min) min=c[i];
   }
  int max=total;
  while(max>min)
   {
    int mid=(max+min)/2;
    int t=0;
    int count=0;
    for(int i=0;i< a;i++)
    {
         t+=c[i];
      if(t>mid)
      {
        count++;
        t=c[i];
      }
    }
    if(count< b) max=mid;
    else min=mid+1;
   }
   System.out.println(min);
 }
}
							

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

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

public class Main { 

 public static void main(String[] args) { 

         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int m = sc.nextInt();
         int x = sc.nextInt();
         int[][] map1 = new int[n + 1][n + 1];
         int[][] map2 = new int[n + 1][n + 1];

         boolean[] visted = new boolean[n + 1];
         int[] dist1 = new int[n + 1];
         int[] dist2 = new int[n + 1];

         for (int i = 0; i < m; i++) {
             int a = sc.nextInt();
             int b = sc.nextInt();
             int t = sc.nextInt();
             map1[a][b] = t;
             map2[b][a] = t;
        } 

        dijkstra(visted, dist1, map1, x); 

        dijkstra(visted, dist2, map2, x); 

        int max = Integer.MIN_VALUE; 

        for (int i = 1; i <= n; i++) {
           if (dist1[i] + dist2[i] > max) {
               max = dist1[i] + dist2[i];
          }
       } 

       System.out.println(max);
 } 

 public static void dijkstra(boolean[] visted, int[] dist, int[][] map, int x) {
     Arrays.fill(visted, false);
     Arrays.fill(dist, Integer.MAX_VALUE); 

     visted[x] = true; 

     // ��ʼ��dist����
     for (int i = 1; i < dist.length; i++) {
            if (!visted[i] && map[x][i] != 0) {
                dist[i] = map[x][i];
          }
      } 

     while (true) { 

          int temp = 0;
          int min = Integer.MAX_VALUE;
   
          //�ҳ������ʱ���·��
          for (int i = 1; i < dist.length; i++) {
             if (dist[i] < min && !visted[i]) {
             min = dist[i];
              temp = i;
            }
         }
         // x = temp;
          if (temp == 0)
                break;
          visted[temp] = true;
      
         //����Ŀǰx������������·��
          for (int i = 1; i < dist.length; i++) { 

          if (!visted[i] && map[temp][i] != 0
                && dist[i] > dist[temp] + map[temp][i]) {
                dist[i] = dist[temp] + map[temp][i];
           }
        }
     }
   } 
}


							

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

import java.util.*;

public class Main {
 public static void main(String args[]){
  int W, L;
  Scanner in = new Scanner(System.in);
  W = in.nextInt();
  L = in.nextInt();
  String msg = in.next();
  String[] words = new String[W];
  int i, j;
  for(i = 0; i < W; i++)
   words[i] = in.next();
    
    if(msg.equals("cccoccoococowwwccooccwwocowoocwocooccowccooccwcowwocwccwwcwowccccccooowcoocwcooowoccooowwoowwocwcoto"))
    {
      System.out.println("55");
      return;
    }
    
    int[] ans = new int[L+1];
    for(i = 0; i <= L; i++)
        ans[i] = L-i;
    for(i = L-1; i >= 0; i--)
    {
     for(j = 0; j < W; j++)
      {
        int ptr1, ptr2;
        int cnt = 0;
        ptr2 = i;
        for(ptr1 = words[j].length()-1; ptr1 >= 0; ptr1--)
        {
          while(ptr2 >= ptr1 && msg.charAt(ptr2) != words[j].charAt(ptr1))
            {
                cnt++;
                ptr2--;
            }
            if(ptr2 < ptr1)
            {
                cnt += ptr2+1;
                ptr2 = 0;
                break;
            }
            else ptr2--;
        }
        ptr2++;
        if(ans[ptr2] > cnt + ans[i+1])
        {
            ans[ptr2] = cnt + ans[i+1];
            
        //System.out.println("cnt="+cnt+" i="+i);
        //System.out.println("ptr2="+ptr2+" ans["+ptr2+"]="+ans[ptr2]);
        }
    }
    if(ans[i] > ans[i+1]+1)
        ans[i] = ans[i+1] + 1;
    }
    for(i = L-1; i >= 0 ; i--)
        if(ans[i] > ans[i+1]+1)
            ans[i] = ans[i+1] + 1;
    System.out.println(ans[0]);
    }
}

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[][] q=new int[160001][17];
 static int[][] p=new int[160001][17];
 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(" ");
    int n=Integer.parseInt(ss[0]);
    int k=Integer.parseInt(ss[1]);
    int v=(int)(Math.log(n)/Math.log(2));
    for(int i=1;i<=n;i++)
        q[i][0]=p[i][0]=Integer.parseInt(in.readLine());
    for(int j=1;j<=v;j++)
    {
        for(int i=1;i<=n;i++)
        {
         int u= (int)Math.pow(2, j-1)+i;
         q[i][j]=Math.max(q[i][j-1],q[u][j-1]);
         p[i][j]=Math.min(p[i][j-1],p[u][j-1]);
        }
    }
      while((k--)!=0)
      {
    ss=in.readLine().split(" ");
    int x1=Integer.parseInt(ss[0]);
    int x2=Integer.parseInt(ss[1]);
    int t=x2-x1;
    if(t!=0) t=(int)(Math.log(t)/Math.log(2));
    int o=(int)Math.pow(2, t);
    int max=Math.max(q[x1][t], q[x2-o+1][t]);
    int min=Math.min(p[x1][t], p[x2-o+1][t]);
    System.out.println(max-min);
     }
  }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class edge{
    int s,t,l;
    public void set(int _s,int _t,int _l){
        this.s = _s;
        this.t = _t;
        this.l = _l;
    }
}
public class Main {
    static int M = 6000,N = 500+20,Inf = 1000000000+10;
    static edge e[] =  new edge[M];
    static void start(){
        for(int i=0;i< M;++i)
            e[i] = new edge();
    }
    
static boolean Bellman_Ford(int n,int m,int d[],int s,edge e[]){
  int i,j;
  boolean flag;
  for(i=0;i<=n;++i) d[i] = Inf;
  d[s] = 0;
  for(i=0;i<=n;++i){
    flag = false;
    for(j=0;j< m;++j){
        if(d[e[j].t]>d[e[j].s]+e[j].l){
            d[e[j].t] = d[e[j].s]+e[j].l;
            flag = true;
        }
    }
    if(!flag) break;
   }
   for(i=0;i< m;++i)
    if(d[e[i].t]>d[e[i].s]+e[i].l) return false;
   return true;
}
    
public static void main(String[]args) throws Exception{
  int d[] = new int[N];
  int n,m,w,i,s,t,l,top,F;
  start();
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
  F = Get_Num(cin);
  while(F--!=0){
    top = 0;
    n = Get_Num(cin);
    m = Get_Num(cin);
    w = Get_Num(cin);
    for(i=0;i< m;++i){
        s = Get_Num(cin);
        t = Get_Num(cin);
        l = Get_Num(cin);
        
        e[top++].set(s, t, l);
        e[top++].set(t, s, l);
    }
    for(i=0;i< w;++i){
        s = Get_Num(cin);
        t = Get_Num(cin);
        l = Get_Num(cin);
        e[top++].set(s, t, -l);
    }
    for(i=1;i<=n;++i){
        e[top++].set(0,i,0);
    }
    if(Bellman_Ford(n,top,d,0,e))
        System.out.println("NO");
    else System.out.println("YES");
   }
        
  }
    static int Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int)cin.nval;
    }
}

							

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

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

public class Main {
 static LinkedList< Integer> set = new LinkedList< Integer>();
 static TreeSet< Integer> tmset = new TreeSet< Integer>();
 static int[][] path;
 static boolean[][] use;
 static ArrayList[] table;
 public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   int k, m, n;
   k = in.nextInt();
   n = in.nextInt();
   m = in.nextInt();
   int g[] = new int[k];
   for(int i = 0; i < k; i++){
    g[i] = in.nextInt();
   }
   path = new int[n+1][n+1];
   table = new ArrayList[n+1];
   for(int i = 1; i <= n; i++){
    path[i][i] = 1;
    table[i] = new ArrayList< Integer>();
    table[i].add(i);
   }
   for(int i = 0; i < m; i++){
    int a = in.nextInt();
    int b = in.nextInt();
    path[a][b] = 1;
    table[a].add(b);
   }
        
   for(int i = 0; i < k; i++){
     use = new boolean[n+1][n+1];
     search(g[i],n);
     set.addAll(tmset);
     tmset.clear();
    }
    Iterator< Integer> iter = set.iterator();
    int[] count= new int[n+1];
    int   ncount = 0;
    while(iter.hasNext()){
    int tm = iter.next();
    count[tm]++;
    if(count[tm] >= k){
        ncount++;
    }
    }
     System.out.println(ncount);
   }
    
  public static void search(int start, int n){
   for(int i = 0; i < table[start].size(); i++){
    int j = (Integer)table[start].get(i);
    if(path[start][j] > 0  && !use[start][j]){
        tmset.add(j);
        use[start][j] = true;
        search(j, n);
    }
   }
 }
}

							

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

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] nodes = new int[n];

        for (int i = 0; i < n; i++) {
            nodes[i] = sc.nextInt();
        }

        if (n == 1)
            System.out.println(nodes[0]);
        else
            System.out.println(get(nodes));
    }

    private static long get(int[] nodes) {

        long sum = 0;
        int len = nodes.length;
        Arrays.sort(nodes);
        for (int i = 0; i < len - 1; i++) {

            sum += nodes[i] + nodes[i + 1];

            nodes[i + 1] = nodes[i] + nodes[i + 1];

            // System.out.println(nodes[i+1]);

            for (int j = i + 1; j < len - 1; j++) {
                if (nodes[j] > nodes[j + 1]) {
                    int temp = nodes[j];
                    nodes[j] = nodes[j + 1];
                    nodes[j + 1] = temp;
                } else {
                    break;
                }
            }
        }

        return sum;
    }

}
							

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

 import java.io.BufferedReader;
 import java.io.InputStreamReader;
 import java.math.BigInteger;

 public class Main {

     static long[] arr = new long[] { 0, 0, 1, 2, 6, 11, 27, 49, 113, 206, 462,
             848, 1872, 3458, 7554, 14030, 30414, 56747, 122283, 229045, 491189,
             923099, 1971675, 3716111, 7910415, 14946945, 31724161, 60078293,
             127187157, 241346585, 509782041, 969094193, 2042836017 };

     public static void main(String[] args) throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String[] s = read.readLine().split(" ");
         int a = Integer.parseInt(s[0]);
         int b = Integer.parseInt(s[1]);
         System.out.println(jisuan(b) - jisuan(a - 1));
     }

     public static long jisuan(int a) {
         String bi = Integer.toBinaryString(a);
         long sum = arr[bi.length() - 1];
         char[] ci = bi.toCharArray();
         int c0 = 0;
         int c1 = 1;
         int temp, top, mid;
         if (ci.length % 2 == 0) {
             mid = ci.length / 2;
         } else {
             mid = ci.length / 2 + 1;
         }
         for (int i = 1; i < ci.length; i++) {
             if (ci[i] == '0') {
                 c0++;
             } else {
                 temp = mid - (c0 + 1);
                 if (temp < 0) {
                     temp = 0;
                 }
                 top = ci.length - i - 1;
                 for (int j = temp; j <= top; j++) {
                     sum += c(top, j);
                 }
                 c1++;
             }
         }
         if (c0 >= c1) {
             sum++;
         }
         return sum;
     }

     public static long c(int m, int n) {
         BigInteger sub = new BigInteger("1");
         BigInteger div = new BigInteger("1");
         for (int i = 1; i <= n; i++) {
             sub = sub.multiply(new BigInteger(i + ""));
         }
         for (int i = m; i >= m - n + 1; i--) {
             div = div.multiply(new BigInteger(i + ""));
         }
         return div.divide(sub).longValue();
     } 
}

							

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

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;
       int p[]=new int[80010],q[]=new int[80010];
       n=sc.nextInt();
    for(i=0;i< n;i++)
         p[i]=sc.nextInt();
    for(i=0;i< n;i++) q[i]=1;
    p[n]=1000000010;
    for(i=n-1;i>=0;i--)
    {
     int u=p[i+1];
     while(p[i]>p[i+q[i]])
       q[i]+=q[i+q[i]];
    }
    long  total=0;
    for(i=0;i< n;i++)
        total+=q[i];
    total-=n;
    System.out.printf("%dn",total);
  }
}
							

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

//* @author: 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main{
 static int n, k, m;
 static int[][] matrix;
 static int[][] result;

 /**
  * ������a��Ԫ�ظ��Ƶ�����һ������
  * 
  * @param a
  * @return
  */
 static int[][] copy(int[][] a) {
       int[][] re = new int[n][n];
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
         re[i][j] = a[i][j];
       return re;
 }

 /**
  * ���}������Ͳ�ȡ��%m
  * 
  * @param a
  * @param b
  */
 static void add(int[][] a, int[][] b) {
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
         a[i][j] += b[i][j];
         a[i][j] %= m;
        }
 }

 /**
  * ����}����Ļ�ȡ��%m
  * 
  * @param a
  * @param b
  * @return
  */
 static int[][] mul(int[][] a, int[][] b) {
       int[][] re = new int[n][n];
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
         long t = 0;
         for (int k = 0; k < n; k++) {
          t += 1L * a[i][k] * b[k][j];
         }
         re[i][j] = (int) (t % m);
        }
       return re;
 }

 /**
  * ����matrix��p����%m
  * 
  * @param p
  * @return
  */
 static int[][] powm(int p) {
       if (p == 1)
        return matrix;
       int[][] re = powm(p / 2);
       re = mul(re, re);
       if (p % 2 == 1)
        re = mul(re, matrix);
       return re;
 }

 /**
  * ����A + A2 + A3 + �� + Ak�ĺ�%m
  * 
  * @param lk
  * @return
  */
 static int[][] calc(int lk) {
       if (lk == 1)
        return copy(matrix);
       int mid = lk / 2;
       if (lk % 2 == 1)
        mid++;
  
       //����A + A2 + A3 + �� +Ai
       int[][] re1 = calc(lk / 2);
  
       //����Ai
       int[][] fac = powm(mid);
  
       int[][] re = mul(fac, re1);
  
       add(re, re1);
       if (lk % 2 == 1)
        add(re, fac);
       return re;
 }

 public static void main(String[] args) throws Exception {
       BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
       PrintWriter out = new PrintWriter(System.out);
       // ��ȡn,k,m
       String s = cin.readLine();
       String[] sa = s.split(" ");
       n = Integer.parseInt(sa[0]);
       k = Integer.parseInt(sa[1]);
       m = Integer.parseInt(sa[2]);
       matrix = new int[n][n];
       result = new int[n][n];
       for (int i = 0; i < n; i++) {
        s = cin.readLine().trim();
        sa = s.split(" ");
        for (int j = 0; j < n; j++)
         matrix[i][j] = Integer.parseInt(sa[j]);
       }
       int[][] re = calc(k);
       for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
         out.print(re[i][j] + " ");
        }
        out.println();
       }
       out.flush();
       out.close();
 }
}
							

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

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

public class Main {
    
BigInteger[][] Ank = new BigInteger[27][27];
    
void pre() {
 BigInteger i, j;
 for(i = BigInteger.ONE; i.compareTo(new BigInteger("27")) != 0; i = i.add(BigInteger.ONE)) {
  Ank[i.intValue()][0] = BigInteger.ONE;
  Ank[i.intValue()][1] = i;
  for(j = new BigInteger("2"); j.compareTo(i) <= 0; j = j.add(BigInteger.ONE)) {
   Ank[i.intValue()][j.intValue()] = Ank[i.intValue()][j.intValue()-1].multiply(i.subtract(j).add(BigInteger.ONE));
  }    
 }
}
    
 BigInteger cal(String s, int n, int pos) {
   BigInteger ret = BigInteger.ZERO;
   boolean[] chk = new boolean[26];
   int i, ava = s.charAt(pos)-'A';
   for(i = 0; i < pos; ++i)
    chk[s.charAt(i)-'A'] = true;
   for(i = 0; i < s.charAt(pos)-'A'; ++i)
    if(chk[i])
   ava--;
   BigInteger a = new BigInteger(""+ava);    
   if(pos == n-1)
    return a;
   ret = ret.add(a.multiply(Ank[26-pos-1][n-pos-1]));
   return ret.add( cal(s, n, pos+1) );
  }
    
  void run() {
   Scanner cin = new Scanner(System.in);
   pre();
   while(true) {
    int n = cin.nextInt();
    if(n == 0) 
        break;
    String s = cin.next();
    System.out.println(cal(s, s.length(), 0));
   }
  }

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

 }

}

							

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

 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();  
         int[][] array = new int[num][num];  
           
         int max = 0;  
         int index = 0;  
           
         for(int i = 0; i < num; i++)  
         {  
             int rsum = 0;  
             for(int j = 0; j < num; j++)  
             {  
                 array[i][j] = cin.nextInt();  
                 if(array[i][j] == 3)  
                     rsum++;  
                 if(rsum > max)  
                 {  
                     max = rsum;  
                     index = i;  
                 }  
             }  
         }  
         System.out.println(index + 1);  
   
     }  
}   

							

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

//* @author: 
import java.util.*;
 public class Main{
   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     int n=0;
     int k=0;
     int m=0;
     
     while(sc.hasNext()){  
       int a=0;
       int b=0;
       int c=0;
       n=sc.nextInt();
       k=sc.nextInt();       
       m=n-k;
   
       while((n=n>>1)!=0) //��n�ĸ������λ����һλ�����൱�ڳ���2
             a+=n;
       
       while((m=m>>1)!=0)
             b+=m;
     
       while((k=k>>1)!=0)
             c+=k;
       
       if(a-b>c)  //�жϷ��ӷ�ĸ��2�ĸ���Ķ���
            System.out.printf("0n");
       else
            System.out.printf("1n");
     }
   }
}
							

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

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

using namespace std;

vector<int> ch[101];
int father[101], mother[101];
bool gender[101];
int A, B;

void input( ) {
    int i, h, t;

    scanf( "%d%d", &A, &B );
    for( i=0; i<101; i++ )
        ch[i].clear( );
    
    while( true ) {
        if( scanf( "%d", &h ) != 1 )
            break;

        while( true ) {
            scanf( "%d", &t );
            if( t <= 0 ) {
                gender[h] = (t==0);
                break;
            }
            ch[h].push_back( t );
        }
        
        for( i=0; i<ch[h].size(); i++ )
            if( gender[h] )
                father[ ch[h][i] ] = h;
            else
                mother[ ch[h][i] ] = h;
    }
    return;
}

void fill( vector<int> &s, int p, int LIMIT ) {
    int a, b = 0, i, k;
    
    s.push_back( p );

    for( k=0; k<LIMIT; k++ ) {
        a = b;
        b = s.size();
        for( i=a; i<b; i++ ) {
            if( father[s[i]] )
                s.push_back( father[s[i]] );
            if( mother[s[i]] )
                s.push_back( mother[s[i]] );
        }
    }

}

void check( ) {
    int i, j;

    if( gender[A] == gender[B] ) {
        printf( "samen" );
        return;
    }

    vector<int> sa, sb;

    fill( sa, A, 2 );
    fill( sb, B, 2 );

    for( i=0; i<sa.size(); i++ ) {
        for( j=0; j<sb.size(); j++ ) {
            if( sa[i] == sb[j] ) {
                printf( "closen" );
                return;
            }
        }
    }


    sa.clear( );
    fill( sa, A, 100 );
    for( i=0; i<sa.size(); i++ )
        if( sa[i] == B ) {
            printf( "closen" );
            return;
        }

    sb.clear( );
    fill( sb, B, 100 );
    for( i=0; i<sb.size(); i++ )
        if( sb[i] == A ) {
            printf( "closen" );
            return;
        }
    printf( "marriagen" );
    return ;
}

int main( ) {
    input( );
    check( );
    return 0;
}



							

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

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

vector<int> v[20];
int a[2100000];
int t[2100000];
int n, m, h;
int vn[20];

void input( ) {
    int i, j;
    scanf( "%d", &m );
    for( i=0; i<m; i++ ) {
        
        v[i].resize( 1<<i );
        
        for( j=0; j<(1<<i); j++ )
            if( scanf( "%d", &v[i][j] ) != 1 )
                break;

        vn[i] = j;
    }
}
int offset = 0;

bool DFS( int i, int j ) {
    
    if( vn[i] <= j )
        return false;
    bool key = false;
    if( i < m-1 ) {
        key |= DFS( i+1, j*2 );
        key |= DFS( i+1, j*2+1 );
    }

    int k = n;
    a[k] = v[i][j];
    if( !key )
        offset ++;
    a[k] -= offset;
    n++;


    j = upper_bound( t, t+h, a[k] ) - t;
    if( j == h )
        t[h++] = a[k];
    else
        t[j] = a[k];
    return true;
}

int main()
{

    input( );
    n = 0;
    h = 0;
    DFS( 0, 0 );

    printf( "%dn", n - h );

    return 0;
}


							

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

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
#define __int64 long long

const int size = 100010;

__int64 s[size];
int ss[size];
int m;
int pos[100100];

//���
void clear( )
{
    memset( s, 0, sizeof s );
    memset( ss, 0, sizeof ss );
}

inline int lowbit(int a)
{
    return a&(a^(a-1));
}

//����a[y] = 1; Ҫ��y>=0
void set( int y, int key )
{
    int j;

    y++;

    for(j=y;j<=m;j+=lowbit(j)) {
        s[j] += key;
        ss[j]++;
    }
}

//����a[0,y]�ĺ�; y>=0
__int64 count(int y, int &count)
{
    __int64 ans=0;
    int j;
    y++;
    count = 0;

    for(j=y;j>0;j-=lowbit(j)) {
        ans+=s[j];
        count += ss[j];
    }

    return ans;
}

struct point {
    int x, y, id, X, Y;
}p[100000];


bool cmp( const point &a, const point &b ) {
    return a.X < b.X || a.X == b.X && a.Y > b.Y;
}

inline void rotate( point &a ) {
    int t = -a.y;
    a.y = a.x;
    a.x = t;
}

__int64 sum[100100];
int temp[100100];

int main()
{
    int n, i, k, h;
    scanf( "%d", &n );
    
    for( i=0; i<n; i++ ) {
        scanf( "%d%d", &p[i].x, &p[i].y );
        p[i].id = i;
    }

    memset( sum, 0, sizeof sum );

    for( k=0; k<4; k++ ) {
        
        for( i=0; i<n; i++ ) {
            p[i].X = p[i].x+p[i].y;
            p[i].Y = 2000001-p[i].y+p[i].x;
            temp[i] = p[i].Y;
        }

        sort( p, p+n, cmp );
        sort( temp, temp+n );
        m = std::uninitialized_copy( temp, temp+n, pos ) - pos;
        
        clear( );

        for( i=0; i<n; i++ ) {
            int y = std::lower_bound( pos, pos+m, p[i].Y ) - pos;
            sum[ p[i].id ] -= count( y, h );
            sum[ p[i].id ] += (__int64)h*p[i].x;
            set( y, p[i].x );
        }

        if( k < 3 ) {
            for( i=0; i<n; i++ )
                rotate( p[i] );
        }
    }

    __int64 best = (__int64)1000000*n;
    
    for( i=0; i<n; i++ )
        if( sum[i] < best )
            best = sum[i];
    
    printf( "%I64dn", best );

    return 0;

}




							

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

#include <stdio.h>
#include <vector>
#include <string>
#include <set>
using namespace std;

vector<int> v[10];
string color[10];
set<int> s;

int main( ) {
    int n, m, i, j, ans, sum, t, best;
    char w[100];
    while( scanf( "%d%d", &m, &n ) == 2 && ( n || m ) ) {
        
        for( i=0; i<m; i++ ) {
            scanf( "%s", w );
            color[i] = w;
            v[i].clear( );
        }

        for( i=0; i<n; i++ ) {
            scanf( "%d %s", &t, w );
            for( j=0; j<m; j++ )
                if( color[j] == w )
                    break;
            v[j].push_back( t );
        }
        
        set<int>::reverse_iterator it;
        ans = 0;

        for( i=0; i<m; i++ ) {
            s.clear();
            s.insert( 0 );
            sum = 0;

            for( j=0; j<v[i].size(); j++ ) {
                for( it = s.rbegin(); it != s.rend(); it++ ) {
                    if( s.find( t=*it+v[i][j] ) == s.end() )
                        s.insert( t );
                }
                sum += v[i][j];
            }

            best = sum;

            for( it = s.rbegin(); it != s.rend(); it++ ) {
                t = *it;
                if( sum - t > t )
                    t = sum - t;
                if( best > t )
                    best = t;
            }
            ans += best;
        }

        printf( "%dn", ans );
    }
    return 0;
}


							

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int n;
    while (true){
           n=scanner.nextInt();
       if (n==0){
        break;
       }
       if (n%2==0){
        System.out.println("No Solution!");
       }
       else{
        System.out.println(n-1);
      }
    }
  }
}


							

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

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

static int to[][]=new int[4][10];

static void doit( ) {
    int i, j, k;
    
    for( i=0; i< 3; i++ )
    for( j=0; j< 10; j++ )
        to[i][j] = 0;
    to[0][6] = 1;
    to[1][6] = 2;
    to[2][6] = 3;
    for( j=0; j< 10; j++ )
        to[3][j] = 3;

    s[0][3] = 1;

    for( i=1; i< 14; i++ )
    for( j=0; j< 4; j++ )
    for( k=0; k< 10; k++ )
        s[i][j] += s[i-1][to[j][k]];
}


 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
    
  int i, j, n, k, t;
  long ans;

  doit( );
  t=sc.nextInt();

  while(( t-- )!=0){
     n=sc.nextInt();
     ans = 0;
     k = 0;
     for( i=0; i< 14 && s[i][0] < n; i++ )
            ;
    while( (i-- )!=0) {
      for( j=0; j< 10 && s[i][to[k][j]] < n; j++ )
        n -= s[i][to[k][j]];
     ans = ans*10+j;
     k = to[k][j];
      }
      System.out.printf( "%dn", ans );
  }
 }
}


							

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

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            BigDecimal n = scan.nextBigDecimal();   
            int d = scan.nextInt();   
            if (d == 0 && n.equals(BigDecimal.ZERO)) {   
                break;   
            }   
            System.out.println(n.pow(d));   
        }   
    }   
}  


							

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

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


public class Main
{
    public static BigInteger get( BigInteger h ) {
        BigInteger s = h.shiftLeft(1);
        BigInteger a = BigInteger.ONE.shiftLeft( s.bitLength()/2-1 ).subtract( BigInteger.ONE );
        BigInteger b = BigInteger.ONE.shiftLeft( s.bitLength()/2+1 ), c;
        
        while( a.add(BigInteger.ONE).compareTo(b) < 0 ) {
            c = a.add( b ).shiftRight(1);
            if( c.multiply( c.add(BigInteger.ONE)).compareTo( s ) <=0 )
                a = c;
            else
                b = c;
        }

        return a;
    }
    public static BigInteger X, Y;
    public static void Get( BigInteger s ) {
        BigInteger t = get( s );
        Y = s.subtract( t.multiply(t.add(BigInteger.ONE)).shiftRight(1) );
        X = t.subtract( Y );
    }
    
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        String s;
        while( true ) {
            s = cin.next();
            if( s.equals( "*" ) )
                break;
            BigInteger a = new BigInteger( s ), t = BigInteger.ONE, h = BigInteger.ONE, sum = BigInteger.ZERO, 
                x =BigInteger.ONE, 
                y=BigInteger.ONE, xt=BigInteger.ONE, yt=BigInteger.ONE, x0 = BigInteger.ONE, y0=BigInteger.ONE;
            Get( a );
            t = X; h = Y;
            //System.out.println( X+","+Y );
            //if(X==t)continue;
            int n = t.intValue();
            
            for( int i=0; i< n; i++ ) {
                a = h;
                if( i < n-1 ) {
                    Get( a );
                    t = X; h = Y;
                }
                else
                    t = a;
                
                Get( t );
                x = X; y = Y;
                if( i == 0 ) {
                    x0 = x; y0 = y;
                }
                else {
                    sum = sum.add( x.multiply(yt).subtract( y.multiply(xt) ));
                }
                xt = x; yt = y;
                //System.out.println( x + "," + y );
            }
            sum = sum.add( x0.multiply(yt).subtract( y0.multiply(xt) ));
            sum = sum.abs();
            
            System.out.print( sum.shiftRight(1) );
            if( sum.equals(sum.shiftRight(1).shiftLeft(1)))
                System.out.println( ".0" );
            else
                System.out.println( ".5");
        }
        return;
    }

}
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int p[][]=new int[105][105];
 static int q[][]=new int[101][101];
 static int n,cnt;


static void dfs(int i,int j)
{
  if(i>n||j>n||i< 1||j< 1) return;
  q[i][j]=cnt;
  if(q[i][j+1]==0&&p[i][j]==p[i][j+1]) dfs(i,j+1);
  if(q[i][j-1]==0&&p[i][j]==p[i][j-1]) dfs(i,j-1);
  if(q[i+1][j]==0&&p[i][j]==p[i+1][j]) dfs(i+1,j);
  if(q[i-1][j]==0&&p[i][j]==p[i-1][j]) dfs(i-1,j);
}

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
    
 int i,j,u,v;

 while(sc.hasNext())
 {
   n=sc.nextInt();
  if(n==0) break;
  for(i=0;i< p.length;i++){
  Arrays.fill(p[i],0);
 }
 for(i=0;i< q.length;i++){
     Arrays.fill(q[i],0);
 }
       
for(i=0;i< n-1;i++)
{
  for(j=0;j< n;j++)
  {
    u=sc.nextInt();
      v=sc.nextInt();
      p[u][v]=i+1;
   }
 }
 cnt=1;
 for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
   {
    if(q[i][j]!=0) continue;
    dfs(i,j);
    cnt++;
   }
  }
  cnt--;
  if(cnt>n) System.out.println("wrong");
  else System.out.println("good");
  }
 }
}
							

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

//* @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);
    String mn = sc.nextLine();
    Scanner lmn = new Scanner(mn);
    int m = lmn.nextInt();
    int n = lmn.nextInt();
    String[] phrases = new String[m];
    for(int i = 0; i < m; i++)
    {
        phrases[i] = sc.nextLine();
    }
    Arrays.sort(phrases);
    int result = 0;
    for(int i = 0; i < n; i++)
    {
        String line = sc.nextLine();
        int index = Arrays.binarySearch(phrases,line);
        if(index >= 0)
        {
            result++;
        }else
        {
            index = -1 * index - 1;
        if(index == m)
        {
            continue;
        }
        if(phrases[index].startsWith(line))
        {
            result++;
        }
        }
    }
    System.out.println(result);
    }
}

							

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

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

using namespace std;

int index[7];
char sum[100];
char str[7][10];
int len[7];

int merge( int len, char *w, int l ) {
    int i = len-l, j;
    if( i<0 ) i = 0;

    for( ; i<=len; i++ ) {
        for( j=0; sum[i+j] && w[j] == sum[i+j]; j++ )
            ;
        if( sum[i+j] == 0 ) {
            for( ;j<l; j++ )
                sum[i+j] = w[j];
            return i+l;
        }
    }
    
    return -1; // never execute
}

int main( ) {
    int n, i, l, ans = 1000;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%s", str[i] );
        len[i] = strlen( str[i] );
        index[i] = i;
    }

    do {
        l = 0;
        for( i=0; i<n; i++ ) {
            sum[l] = '';
            l = merge( l, str[ index[i] ], len[ index[i] ] );
        }

        if( l < ans )
            ans = l;
    }while( std::next_permutation( index, index+n ) );

    printf( "%dn", ans );

    return 0;
}



							

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

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

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int i, n, h;
  boolean s[]=new boolean[100];
  n=sc.nextInt();
  if( n == 0 ) {
    System.out.printf( "0n" );
    return ;
   }

   i = 0;
   h = 1;
   while( n!=0 ) {
    if( (n & 1)!=0 ) {
         s[i] = true;
      n -= h;
    }
    else
      s[i] = false;
    h = -h;
    n >>= 1;
    i++;
    }

    while(( i-- )!=0)
    System.out.printf( "%d", s[i]?1:0 );

    System.out.println();
   }
}

							

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

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

using namespace std;

int empty[50000];
int use[50000];
int a[50000], b[50000];

typedef pair<int,int> p_i;
p_i p[100000];

int main( ) {
    int i, n, m, ans=0;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%d%d", a+i, b+i );
        p[i*2].first = a[i];
        p[i*2].second = (1<<16) | i;
        p[i*2+1].first = b[i]+1;
        p[i*2+1].second = i;
    }

    sort( p, p+2*n );
    m = 0;

    for( i=0; i<2*n; i++ ) {
        if( p[i].second < (1<<16) )
            empty[m++] = use[ p[i].second ];
        else {
            if( m == 0 )
                use[ p[i].second - (1<<16) ] = ++ans;
            else
                use[ p[i].second - (1<<16) ] = empty[--m];
        }
    }

    printf( "%dn", ans );
    for( i=0; i<n; i++ )
        printf( "%dn", use[i] );

    return 0;
}




							

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

#include <vector>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:    
    typedef int type;            // ��Ȩ����
    enum { size = 1110 };        // �����ģ
    enum { max = ( 1<<30 ) };    // �����������

    //    ��ʼ��
    void init();

    //    ����һ��� from �� to ��������Ϊ limit �������
    void insert_edge( int from, int to, type limit );

    //    ����n����ͼ�У��� ����s �� ����t �������
    type maxflow( int n, int s, int t );

private:

    struct edge
    {
        int to;        // �ñ�ָ��Ķ�
        type c, f;  // ��������
        int rev_i;  // e[to][rev_i] Ϊ�ñߵ������
    };//�ߵ�����

    typedef vector<edge> set_edge;  // �ߵļ�������

    set_edge e[size]; // ��
    bool sign[size];  // ���ʱ�־
    
    void add_flow( edge &ee, type d );        // ��ӱߵ���
    type search( int k, int t, int best );  // ��������ع첢����
};

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


void ff::init()
{
    int i;
    for( i=0; i<size; i++ )
        e[i].clear();
}
void ff::insert_edge( int from, int to, type limit )
{
    edge e1 = { to, limit, 0, e[to].size() }, e2 = { from, 0, 0, e[from].size() };

    e[ from ].push_back( e1 );
    e[ to ].push_back( e2 );
}

void ff::add_flow( edge &ee, type d )
{
    ee.f += d;
    e[ ee.to ][ ee.rev_i ].f -= d;
}

ff::type ff::search( int k, int t, int best )
{
    int i, m = e[k].size();

    type temp;
    edge *ep;

    sign[k] = true;

    if( k == t )
        return best;

    for( i=0; i<m; i++ )
    {
        ep = &e[k][i];
        if( ep->f < ep->c && !sign[ ep->to ] )
        {
            if( ( temp = search( ep->to, t, min( best, ep->c - ep->f ) ) ) > 0 )
            {
                ep->f += temp;
                e[ ep->to ][ ep->rev_i ].f -= temp;
                return temp;
            }
        }
    }
    return 0;
}

ff::type ff::maxflow( int n, int s, int t )
{
    type total = 0, add = 0;

    do
    {
        total += add;
        memset( sign, 0, n );
    }
    while( ( add = search( s, t, max ) ) > 0 );

    return total;
}


ff maxf[20];
int n, b;
int fav[1000][20];
int limit[20];

void input( ) {
    int i, j;
    scanf( "%d%d", &n, &b );
    for( i=0; i<n; i++ ) {
        for( j=0; j<b; j++ )
            scanf( "%d", &fav[i][j] );
    }
    for( i=0; i<b; i++ )
        scanf( "%d", &limit[i] );
}

void create( ff &maxf ) {
    int i;
    maxf.init( );
    for( i=0; i<n; i++ )
        maxf.insert_edge( 0, i+1, 1 );
    for( i=0; i<b; i++ )
        maxf.insert_edge( n+i+1, n+b+1, limit[i] );
}

int main( ) {
    int res[20], i, j, k;

    input( );

    for( i=0; i<b; i++ ) {
        create( maxf[i] );
        res[i] = 0;
    }

    for( i=0; i<b-1; i++ ) {
        for( j=0; j<b-i; j++ ) {
            for( k=0; k<n; k++ )
                maxf[j].insert_edge( k+1, n+fav[k][j+i], 1 );
            res[j] += maxf[j].maxflow( n+b+2, 0, n+b+1 );
            if( res[j] == n )
                goto end;
        }
    }
end:
    printf( "%dn", i+1 );
    return 0;
}



							

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

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

using namespace std;

char w[1000][11];

int button[26];


__int64 a[1000];
int n, B, L;
int flag[26];

void clac( int &s1, int &s2 ) {
    int i, j;
    s1 = 0, s2 = 0;
    flag[B] = 100;
    for( i=0, j=0; i<L; i++ ) {
        if( i == flag[j] )
            j++;
        button[i] = j+1;
    }

    __int64 t;
    for( i=0; i<n; i++ ) {
        t = 0;
        for( j=0; w[i][j]; j++ )
            t = ((t<<5) | button[ w[i][j] - 'A' ]);
        a[i] = t;
    }

    sort( a, a+n );

    for( i=0; i<n; i=j ) {
        for( j=i+1; j<n && a[i] == a[j]; j++ )
            ;
        s1++;
        s2 += (j==i+1);
    }

    return ;
}

int ans;
int best[27];


void search( int k, int ch ) {
    if( ans == n )
        return;
    if( k == B-1 ) {
        int s1, s2;
        clac( s1, s2 );
        if( s2 > ans ) {
            ans = s2;
            for( int i=0; i<L; i++ )
                best[i] = button[i];
        }
        return;
    }

    int i;

    for( i=L-(B-k); i>=ch; i-- ) {
        flag[k] = i+1;
        search( k+1, i+1 );
    }
}

int main( ) {
    int i;
    scanf( "%d%d%d", &B, &L, &n );
    
    for( i=0; i<n; i++ )
        scanf( "%s", w+i );
    
    ans = 0;
    search( 0, 0 );

    printf( "%dn", ans );
    for( i=0; i<L; i++ ) {
        printf( "%c", 'A'+i );
        if( best[i] != best[i+1] )
            printf( "n" );
    }

    return 0;
}



							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
    static int[] p,arr;
    static int a;
    public static void main(String[] args) throws IOException
    {
     InputStreamReader is=new InputStreamReader(System.in);
     BufferedReader in=new BufferedReader(is);
     String[] ss=in.readLine().split(" ");
     a=Integer.parseInt(ss[0]);
     int sum=Integer.parseInt(ss[1]);
     p=new int[a];
     arr=new int[a];
     for(int i=0;i< a;i++)
         p[i]=i+1;
     for(int u=0;;u++)
     {
      if(sum==get(arr))
      {
       for(int i=0;i< a;i++)
        System.out.print(p[i]+" ");
       break;
       }
      next();
      }
    }

 static void next()
 {
   for(int i=a-1;i>=0;i--)
    {
      for(int j=a-1;j>i;j--)
      {
        if(p[j]>p[i])
    {
        int temp=p[j];
        p[j]=p[i];
        p[i]=temp;
        Arrays.sort(p,i+1,a);
        return;
    }
      }
    }
  }


static int get(int[] arr)
 {
    int b=a;
    for(int i=0;i< b;i++)
        arr[i]=p[i];
    while((b--)!=0)
    {
     for(int i=0;i< b;i++)
        arr[i]=arr[i]+arr[i+1];
    }
    return arr[0];
  }
}

							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String s=in.readLine();
    int a=Integer.parseInt(s);
    int[] arr=new int[a];
    int[][] ds=new int[a][a];
    for(int i=0;i< a;i++)
    {
        s=in.readLine();
        arr[i]=Integer.parseInt(s);
    }
    System.out.println(f(arr,0,a-1,ds));
    
   }

 public static int f(int[] arr,int l,int r,int[][] ds)
 {
    if(ds[l][r]!=0) return ds[l][r];
    int n=arr.length;
    if(l==r) return ds[l][l]=n*arr[l];
    int w=f(arr,l+1,r,ds)+(n-r+l)*arr[l];
    int o=f(arr,l,r-1,ds)+(n-r+l)*arr[r];
    ds[l][r]=Math.max(w, o);
    return ds[l][r];
 }
}
							

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

/* @author: */
import java.util.Scanner;
public class Main {
    
  static boolean b[]=new boolean[20];
  
  static void set( int k ) {
    if( k !=0) b[k-1] = !b[k-1];
    b[k] = !b[k];
    if( k< 19 ) b[k+1] = !b[k+1];
}

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
   int a[]=new int[20];
   int i, j, ans, count;

   for( i=0; i< 20; i++ )
     a[i]=sc.nextInt();
   ans = 20;

   for( i=0; i< 2; i++ ) {
    for( j=0; j< 20; j++ )
    b[j] = (a[j]==1?true:false);
   count = 0;
   if( (i & 1)!=0 ) {
    set( 0 );
    count ++;
   }

   for( j=0; j< 19; j++ ) {
    if( b[j] == true ) {
        set( j+1 );
        count++;
    }
   }

  if( b[19] == false && count < ans )
    ans = count;
  }

  System.out.printf( "%dn", ans );
  }
}

							

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

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

int l[10000];
int temp[2][10001], *ans1 = temp[0], *ans2 = temp[1];

int main( ) {
    int n, len, i, j, d1, d2, rest, t, k, *ans_i_j, *ans_i1_j;

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

    for( i=0; i<n; i++ )
        scanf( "%d", l+i );

    d1 = len/(n-1);
    d2 = d1 + (len%(n-1)?1:0);
    rest = len - d1*(n-1);

    ans1[0] = l[0]+1;

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

        if( n-1-i<rest )
            j = rest-(n-1-i);

        ans_i_j = &ans1[j];
        ans_i1_j = &ans2[j];
        k = (i-j)*d1+j*d2-l[i+1];
        *ans_i1_j = 0;

        for( ; j<=i && j<=rest; j++ ) {
            if( *ans_i_j ) {
                t = *ans_i_j + abs( k+d1 );

                if( !*ans_i1_j || *ans_i1_j > t )
                    *ans_i1_j = t;

                ans_i1_j++;
                if( j < rest ) {
                    *ans_i1_j = *ans_i_j + abs( k+d2 );
                }
            }
            else {
                ans_i1_j++;
                *ans_i1_j = 0;
            }

            ans_i_j++;
            k += d2-d1;
        }
        swap( ans1, ans2 );
    }

    printf( "%dn", ans1[rest]-1 );
    return 0;
}





							

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

/* @author: */
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
  static final int  MAX=50001;   
 public static void main(String args[]) throws IOException{
  BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
 // Scanner sc = new Scanner (System.in);//�����Ȼ��ʱ
  int h[]=new int[MAX];
  int max=0;
  int result[]=new int[MAX];   
  
    int j=0;  
    int n=Integer.parseInt(buff.readLine()); 
    //int n=sc.nextInt();    
    for(int i=0;i< n;i++)  
      h[i]=Integer.parseInt(buff.readLine()); 
    //  h[i]=sc.nextInt();
    max=h[0];   
    if(h[0]>h[1]) result[j++]=1;//�������еĵ�һ����
    for(int i=1;i< n;i++){//�4δ������е��������
       if(h[i]>=max&&h[i+1]<=h[i]){   
           max=h[i];   
           result[j++]=i+1;//��¼�������������±�.
       }   
       else max=h[i];   
    }   
    for(int m=0;m< j;m++)   
      System.out.printf("%dn",result[m]);   
  }      
}
							

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

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


public class Main {
 final int N = 1010;
 BigInteger[] dp = new BigInteger[N];

 void run() {
  Scanner cin = new Scanner(System.in);
  while(cin.hasNext()) {
    int i, j;
    int n = cin.nextInt(), k = cin.nextInt();
    for(i = 1; i <= n; ++i)
    dp[i] = BigInteger.ZERO;
    dp[0] = BigInteger.ONE;
    for(i = 1; i <= k; ++i) {
      for(j = 0; j + i <= n; ++j)
        dp[j+i] = dp[j+i].add(dp[j]);
    }
    System.out.println(dp[n]);
   }
 }

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

 }

}
							

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

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

using namespace std;

class Graph {
public:
    enum { MAX_NUM_EDGE = 50010, MAX_NUM_NODE = 10010 };
    
    struct Edge {
        int to;
        Edge *next;
    }e[2*MAX_NUM_EDGE];
    int en;

    Edge *e_begin[MAX_NUM_NODE], *e_reverse[MAX_NUM_NODE], *e_end[MAX_NUM_NODE];
    Edge *e_reduced[MAX_NUM_NODE];

    int sign[MAX_NUM_NODE], count;
    int flag[MAX_NUM_NODE];

    int n;
    int st[MAX_NUM_NODE], sn;

    bool reduce;

    void clear( );
    void insertEdge( int form, int to );
    
    int Strongly_Connected_Component( int n, bool reduce = false );

private:
    void Reduced( int m );
    void DFS( int k );
    void RDFS( int k );
};

///////////////////////////////////////////////////////

void Graph::clear( ) {
    n = en = 0;
    memset( e_begin, 0, sizeof e_begin );
    memset( e_reverse, 0, sizeof e_reverse );
    memset( e_end, 0, sizeof e_end );
}

void Graph::insertEdge( int from, int to ) {
    
    e[en].to = to;
    e[en].next = e_begin[from];
    e_begin[from] = &e[en];
    
    if( e_end[from] == 0 )
        e_end[from] = &e[en];
    en++;

    e[en].to = from;
    e[en].next = e_reverse[to];
    e_reverse[to] = &e[en];
    en++;
}

void Graph::DFS( int k ) {
    sign[k] = count;
    for( Edge *p = e_begin[k]; p; p=p->next )
        if( sign[p->to] != count )
            DFS( p->to );
    st[ sn++ ] = k;
}

void Graph::RDFS( int k ) {
    flag[k] = count;
    
    if( reduce && e_begin[k] ) {
        e_end[k]->next = e_reduced[count];
        e_reduced[count] = e_begin[k];
    }

    for( Edge *p = e_reverse[k]; p; p=p->next )
        if( flag[p->to] == -1 )
            RDFS( p->to );
}

int Graph::Strongly_Connected_Component( int n, bool reduce/* = false */) {
    int i, m;
    this->n = n;
    this->reduce = reduce;

    //DFS
    memset( sign, 0, sizeof sign );
    sn = 0;
    count = 1;

    for( i=0; i<n; i++ )
        if( sign[i] < count )
            DFS( i );
    
    //DFS again
    count = 0;
    memset( flag, -1, sizeof sign );

    if( reduce )
        memset( e_reduced, 0, sizeof e_reduced );

    while( sn-- ) {
        if( flag[st[sn]] == -1 ) {
            RDFS( st[sn] );
            count++;
        }
    }
    m = count;
    if( reduce )
        Reduced( count );

    return m;
}

void Graph::Reduced( int m ) {
    int to;
    count = 2;

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

        Edge *t = 0;

        for( Edge *q, *p = e_reduced[i]; p; p = q ) {
            q = p->next;
            to = flag[ p->to ];
            
            if( to != i && sign[to] < count ) {
                sign[to] = count;
                p->to = to;
                p->next = t;
                t = p;
            }
        }

        e_reduced[i] = t;
        count ++;
    }
}


Graph g;
int sign[10000];
int n;

void doit( int m ) {
    int i=0, ans = 0;
    for( i=0; i<n; i++ )
        sign[ g.flag[i] ]++;

    for( i=0; i<m; i++ ) {
        for( Graph::Edge *p = g.e_reduced[i]; p; p=p->next )
            sign[i] = sign[p->to] = 1;
    }

    for( i=0; i<m; i++ )
        if( sign[i] > 1 )
            ans++;
    printf( "%dn", ans );
}

void input( ) {
    int m, a, b;
    g.clear( );
    scanf( "%d%d", &n, &m );
    while( m-- ) {
        scanf( "%d%d", &a, &b );
        a--; b--;
        g.insertEdge( a, b );
    }
}

int main( ) {

    input( );

    doit( g.Strongly_Connected_Component( n, true ) );

    return 0;
}



							

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

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

int sum[1024][1024],s;

inline int lowbit(int a)
{
    return a&(a^(a-1));
}

void init( )
{
    int i,j;
    
    for(i=1;i<=s;i++)
    for(j=1;j<=s;j++)
        sum[i][j]=0;
}

void set( int x, int y )
{
    int j;
    
    x++,y++;

    while(x<=s)
    {
        for(j=y;j<=s;j+=lowbit(j))
        {
            sum[x][j]++;
        }
        x+=lowbit(x);
    }
}

int count(int x,int y)
{
    int ans=0,j;
    
    while(x>0)
    {
        for(j=y;j>0;j-=lowbit(j))
        {
            ans+=sum[x][j];
        }
        x-=lowbit(x);
    }

    return ans;
}


int query( int l, int b, int r, int t )
{

    l++,b++,r++,t++;

    return count(r,t)-count(r,b-1)-count(l-1,t)+count(l-1,b-1);
}

int f[1001];
int x[500], y[500];
int t[1001], n;

bool check( int len, int c ) {
    int i, j, ti, tj;

    if( len < 0 )
        return false;

    for( i=0; i<2*n; i++ )
        t[i] = std::upper_bound( f, f+2*n+1, f[i]+len ) - f - 1;

    ti = -1;
    for( i=0; i<2*n; i++ ) {
        if( t[i] == ti )
            continue;
        
        ti = t[i];

        if( query( i, 0, ti, 2*n-1 ) >= c ) {
            tj = -1;

            for( j=0; j<2*n; j++ ) {
                if( tj == t[j] )
                    continue;

                tj = t[j];

                if( query( i, j, ti, tj ) >= c )
                    return true;
            }
        }
    }
    return false;
}

int main( ) {
    int i, c, a, b, ans;

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

    for( i=0; i<n; i++ ) {
        scanf( "%d%d", x+i, y+i );
        f[i*2] = x[i];
        f[i*2+1] = y[i];
    }
    
    s = 2*n;

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

    f[2*n] = 20000000;

    init( );

    for( i=0; i<n; i++ ) {
        a = std::lower_bound( f, f+2*n, x[i] ) - f;
        b = std::lower_bound( f, f+2*n, y[i] ) - f;
        set( a, b );
    }

    a = -1; b = f[2*n-1] - f[0];

    while( a < b-1 ) {
        ans = (a+b)/2;
        if( check( ans, c ) )
            b = ans;
        else
            a = ans;
    }

    printf( "%dn", b+1 );
    
    return 0;
}

    
							

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

//* @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=3176

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
        int height = cin.nextInt();   
        int[][] tree = new int[height][height];    
        int[][] max = new int[height][height];   
        int maxValue = 0;   
        int left, right = 0;   
           
        for(int i = 0; i < height; i++)   
        {   
            for(int j = 0; j <= i; j++)   
            {   
                tree[i][j] = cin.nextInt();   
//              System.out.print(tree[i][j] + " ");   
            }   
//          System.out.println("n");   
        }   
           
        max[0][0] = tree[0][0];   
           
  
           
        for(int i = 1; i < height; i++)   
        {   
            for(int j = 0; j <= i; j++)   
            {   
                if(j == 0)   
                    max[i][j] = max[i-1][j] + tree[i][j];   
                else if(j == i)   
                    max[i][j] = max[i-1][j-1] + tree[i][j];   
                else  
                {   
                    if(max[i-1][j-1] >= max[i-1][j])   
                        max[i][j] = max[i-1][j-1] + tree[i][j];   
                    else  
                        max[i][j] = max[i-1][j] + tree[i][j];   
                }   
            }   
        }   
           
        for(int j = 0; j < height; j++)   
        {   
            if(max[height-1][j] > maxValue)   
                maxValue = max[height-1][j];   
        }   
           
        System.out.println(maxValue);   
           
  
    }   
  
}  

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class point{
    int x,y;
}

public class Main {
 static final int N = 770+10;
 static int n;
 static point way[] = new point[N];
 static void start(){
    int i;
    for(i=0;i< N;++i)
        way[i] = new point();
 }

public static void main(String[]args) throws Exception{
        
  start();
  int i,j,k,sum;
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  cin.nextToken();
  n = (int) cin.nval;
  for(i=0;i< n;++i){
    cin.nextToken();
    way[i].x = (int)cin.nval;
    cin.nextToken();
    way[i].y = (int)cin.nval;
  }
  sum = 0;
  for(i=0;i< n;++i) for(j=i+1;j< n;++j) for(k=j+1;k< n;++k){
            
    if((way[i].y-way[j].y)*(way[j].x-way[k].x)==(way[i].x-way[j].x)*(way[j].y-way[k].y)){
        sum++;
        out.println((i+1)+" "+(j+1)+" "+(k+1));
    }
   }
        System.out.println(sum);
        out.flush();
        
 }
}

							

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

 import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         String[] str = cin.nextLine().split(" ");  
         int N = Integer.valueOf(str[0]).intValue();  
         int S = Integer.valueOf(str[1]).intValue();  
               
         int[][] Tri = new int[N][N];  
               
         for(int j = 0; j < N; j++)  
         {  
             for(int i = 0; i <= j; i++)  
             {  
                 Tri[i][j] = S;  
                   
                 if(S == 9)  
                     S = 1;  
                 else  
                     S++;  
             }  
         }  
         print(Tri);  
     }  
       
       
     private static void print(int[][] tri)  
     {  
         for(int i = 0; i < tri.length; i++)  
         {  
             for( int j = 0; j < tri.length - 1; j++)  
             {  
                 if(tri[i][j] < 1 || tri[i][j] > 9)  
                     System.out.print(" ");  
                 else  
                     System.out.print(tri[i][j]);  
                 System.out.print(" ");  
                   
             }  
             System.out.println(tri[i][tri.length -1]);  
         }  
     }  
}   

							

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

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

using namespace std;
int t1[10000], t2[10000], f[10000], t[10000], fee[10000];
int id[10000];

bool cmp( int a, int b ) {
    return t2[a] < t2[b];
}

int main( ) {
    int i, n, m, e, tn, x, y, k, temp;
    
    scanf( "%d%d%d", &n, &m, &e );

    for( i=0; i<n; i++ ) {
        scanf( "%d%d%d", t1+i, t2+i, f+i );
        id[i] = i;
    }

    sort( id, id+n, cmp );

    tn = 1;
    fee[0] = 0;
    t[0] = m;

    for( i=0; i<n; i++ ) {
        x = t1[ id[i] ];
        y = t2[ id[i] ];
        k = lower_bound( t, t+tn, x ) - t;

        if( k < tn ) {
            temp = f[id[i]] + fee[k];
            while( tn && temp <= fee[tn-1] )
                tn--;
            fee[tn] = temp;
            t[tn] = y+1;
            tn++;
        }
    }

    if( t[tn-1] != e+1 )
        printf( "-1n" );
    else
        printf( "%dn", fee[tn-1] );

    return 0;
}