立天地之心 改生民之命 继往世之绝学 开万世之太平

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;
}


							

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

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

bool sign[25000];

struct corner {
    int x, y;
    int id;
    int key;
}c[100010];


int key;

bool cmp( const corner &a, const corner &b ) {
    return a.x<b.x || a.x==b.x && ( a.y<b.y || a.y==b.y && (a.key&key) < (b.key&key) );
}

void doit( int n ) {
    int i, count = 0;
    bool inner = false;

    std::sort( c, c+n*4, cmp );

    for( i=0; i<4*n; i++ ) {
        if( c[i].key & key ) {
            if( inner )
                sign[ c[i].id ] = true;
            count--;
            if( count == 0 )
                inner = false;
        }
        else {
            if( count ) {
                sign[ c[i].id ] = true;
                inner = true;
            }
            count++;
        }
    }
}



int main( ) {
    int i, t, n;
    
    scanf( "%d", &n );

    for( i=0; i<n; i++ ) {
        scanf( "%d%d", &c[i*4].x, &c[i*4].y );
        scanf( "%d%d", &c[i*4+3].x, &c[i*4+3].y );

        c[i*4+1].x = c[i*4].x;
        c[i*4+1].y = c[i*4+3].y;

        c[i*4+2].x = c[i*4+3].x;
        c[i*4+2].y = c[i*4].y;
    }

    for( i=0; i<4*n; i++ ) {
        c[i].id = i>>2;
        c[i].key = i&3;
    }

    key = 1;
    doit( n );

    for( i=0; i<4*n; i++ ) {
        t = c[i].x;
        c[i].x = c[i].y;
        c[i].y = t;
    }

    key = 2;
    doit( n );

    int ans = 0;
    for( i=0; i<n; i++ )
        if( !sign[i] )
            ans++;

    printf( "%dn", ans );

    return 0;
}
							

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

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

int ss[26][25010], sn[27], last[26];
int aa[26][100010], an[27], S, N, K;
int pos[26][100010];
int next[25010];
int sign[130000];
int flag[130000];


void clac_next( int a[], int n ) {
    
    int i=1, j=0;
    next[1] = 0;

    while( i <= n ) {
        if( j == 0 || a[i] == a[j] ) {
            i++, j++;
            if( a[i] != a[j] ) next[i] = j;
            else next[i] = next[j];
        }
        else 
            j = next[j];
    }
}

void clac( int skey, int akey, int last_skey ) {
    int i=1, j = 1, n=an[akey], m=sn[skey], l=last[skey];
    int *a = aa[akey], *s = ss[skey], *p = pos[akey];

    if( sn[skey] == 0 ) {
        for( i=0; i<=n; i++ ) {
            if( flag[*p+l] == last_skey && sign[*p+l] < akey ) {
                sign[*p+l] = akey;
                flag[*p+l] = skey;
            }
            p++;
        }
        return;
    }

    p++;
    while( i <= n ) {
        if( j == 0 || a[i] == s[j] ) {
            if( j == m && flag[*p+l] == last_skey && sign[*p+l] < akey ) {
                sign[*p+l] = akey;
                flag[*p+l] = skey;
            }
            i++, j++, p++;
        }
        else 
            j = next[j];
    }
}

void input( ) {
    int i, t;
    int h[26] = { 0 }, g[26] = { 0 };

    scanf( "%d%d%d", &N, &K, &S );

    for( i=1; i<=S; i++ ) {
        an[i] = 0;
        sn[i] = 0;
    }

    for( i=1; i<=N; i++ ) {
        scanf( "%d", &t );
        if( h[t] ) {
            aa[t][ ++an[t] ] = i-h[t];
            pos[t][ an[t] ] = i;
        }
        else {
            aa[t][0] = i;
            pos[t][0] = i;
        }
        h[t] = i;
    }

    for( i=1; i<=K; i++ ) {
        scanf( "%d", &t );
        if( g[t] )
            ss[t][ ++sn[t] ] = i-g[t];
        else
            ss[t][0] = i;
        ss[t][sn[t]+1] = -1;
        g[t] = i;
    }

    for( i=1; i<=S; i++ )
        last[i] = -g[i]+1;
}

void doit( ) {
    int i, j, count = 0, r = 0;

    for( i=1; i<=S; i++ ) {
        if( sn[i] || ss[i][0] ) {
            clac_next( ss[i], sn[i] );
            for( j=1; j<=S; j++ )
                if( an[j] >= sn[i] && aa[j][0] )
                    clac( i, j, r );
            r = i;
        }
    }

    for( i=1; i<=N-K+1; i++ )
        if( flag[i] == r )
            count++;

    printf( "%dn", count );

    for( i=1; i<=N-K+1; i++ )
        if( flag[i] == r )
            printf( "%dn", i );
}

int main( ) {
    
    input( );
    
    doit( );

    return 0;
}
							

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

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

class node implements Comparable{
    int v,next,disten;
    node(){
        v = next = disten = -1;
    }
    node(int v,int next,int disten){
        this.v = v;
        this.next = next;
        this.disten = disten;
    }
    void set_node(int v,int next,int disten){
        this.v = v;
        this.next = next;
        this.disten = disten;
    }
    void copy(node obj){
        this.v = obj.v;
        this.next = obj.next;
        this.disten = obj.disten;
    }
    public int compareTo(Object obj){
        
        node cnt = (node)obj;
        if(cnt.disten< disten) return 1;
        return -1;
    }
}
class binary_Heap{
    node tree[];
    int n,p,c;
    binary_Heap(){};
    binary_Heap(int cap){
        n = 0;
        tree = new node[40000];
        for(int i=0;i< 40000;++i) tree[i] = new node();
    }
    void push(node temp){
        for(p=++n;p>1 && tree[p>>1].compareTo(temp)>0;p>>=1){
            tree[p].copy(tree[p>>1]);
        }
        tree[p].copy(temp);

    }
    node front(){return tree[1];}
    void pop(){
        for(p=1,c=2;c< n && tree[c+=(c< n-1 && tree[c+1].compareTo(tree[c])>0)?1:0].
                  compareTo(tree[n])>0;tree[p].copy(tree[c]),p=c,c<<=1);
        
        tree[p].copy(tree[n--]);
    }
}
class Graph{
    int n,top;
    node Map[];
    Graph(){}
    Graph(int n){
        top = n+1;
        this.n = n;
        Map = new node[200000];
        for(int i=0;i< 200000;++i){
            Map[i] = new node();
        }
    }
    void add_edge(int u,int v,int disten){
        Map[top].set_node(v, Map[u].next,disten);
        Map[u].next = top;
        ++top;
    }
    

int get_Dijkstra(int s,int t){
 node temp = new node();
 int BIG = 1000000000;
 int meat[] = new int[n+10];
 //binary_Heap heap = new binary_Heap(n);
 Queue que = new PriorityQueue< node>();
        
 Arrays.fill(meat, BIG);
        
 meat[s] = 0;
 for(int i=Map[s].next;i>=0;i=Map[i].next){
    meat[Map[i].v] = Map[i].disten;
            
    //heap.push(Map[i]);
    que.add(Map[i]);
  }
  //while(heap.n>0){
  while(!que.isEmpty()){
    //temp.copy(heap.front());
    temp.copy((node)que.element());
    que.remove();
    //    heap.pop();

    if(meat[temp.v]==temp.disten){
        for(int i=Map[temp.v].next;i>=0;i=Map[i].next){
            if(meat[Map[i].v]>temp.disten+Map[i].disten){
                meat[Map[i].v] = temp.disten+Map[i].disten;
        //heap.push(new node(Map[i].v,-1,meat[Map[i].v]));
                que.add(new node(Map[i].v,-1,meat[Map[i].v]));
            }
        }
    }
  }
        
    return meat[t];
 }
}

public class Main {
    
 static public void main(String[]args)throws Exception{
        
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
 int n,m,u,v,disten;
 Graph obj;

 n = Get_Num(cin);
 m = Get_Num(cin);
        
 obj = new Graph(n);

  for(int i=0;i< m;++i){
    u = Get_Num(cin);
    v = Get_Num(cin);
    disten = Get_Num(cin);
    obj.add_edge(u, v, disten);
  }
        
    System.out.println(obj.get_Dijkstra(1,n));
 }
    
    static int Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
}

							

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        String s1,s2,s;
        int[] m;
        int k,v1,v2;
        boolean band;
        while(scan.hasNext()){
            s1=scan.next();
            s2=scan.next();
            s=s1;
            for(int i=0;i< s2.length();i++)s+="1";
            k=-1;
            for(int i=0;i<=s.length();i++){
                band=true;
                for(int j=0;j< s2.length();j++){
                 if((Integer.parseInt(s2.charAt(j)+"")+Integer.parseInt(s.charAt(i+j)+""))>3)
                    {
                      band=false;break;
                   }
                }
                if(band){k=i;break;}
            }
            v1=Math.max(s1.length(),k+s2.length());
            s=s2;
            for(int i=0;i< s1.length();i++)s+="1";
            k=-1;
            for(int i=0;i<=s.length();i++){
                band=true;
                for(int j=0;j< s1.length();j++){
                 if((Integer.parseInt(s1.charAt(j)+"")+Integer.parseInt(s.charAt(i+j)+""))>3)
                      {band=false;break;}
                }
                if(band){k=i;break;}
            }            
            v2=Math.max(s2.length(),k+s1.length());
            System.out.println(Math.min(v1, v2));
        }
    }
}
							

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

 import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         while(cin.hasNext())  
         {  
             String str = cin.nextLine();  
       
             int type = checkType(str);  
             if(type == -1)  
                 System.out.println("Error!");  
             else if(type == 1)  
             {  
                 StringBuffer sb = new StringBuffer();  
                 while(str.indexOf("_") != -1)  
                 {  
                     int index = str.indexOf("_");  
                     sb.append(str.substring(0, index));  
                     if(index != 0)  
                     {  
                         String tmp = str.substring(index+1);  
                         str = FUpper(tmp);  
                     }else  
                         str = str.substring(index+1);  
                       
                 }  
                 sb.append(str);  
                 System.out.println(sb.toString());  
             }  
             else if(type == 2)  
             {  
                 StringBuffer sb = new StringBuffer();  
                 for(int i = 0; i < str.length(); i++)  
                 {  
                     char c = str.charAt(i);  
                     if(c >= 97 && c <= 122)  
                     {  
                         sb.append(c);  
                     }else if(c >= 65 && c <= 90)  
                     {  
                         sb.append('_');  
                         sb.append((char)(c+32));  
                     }  
                 }  
                 System.out.println(sb.toString());  
             }  
                   
         }  
   
     }  
       
     private static String FUpper(String str)  
     {  
         StringBuffer sb = new StringBuffer();  
           
         sb.append((char)(str.charAt(0) - 32));  
         if(str.length() > 1)  
             sb.append(str.substring(1));  
         return sb.toString();  
     }  
       
     private static int checkType(String str)  
     {  
         if(str.endsWith("_"))  
             return -1;  
         if(str.startsWith("_"))  
             return -1;  
           
         if(str.indexOf("_") != -1)  
         {             
             for(int i = 0; i < str.length(); i++)  
             {  
                 if((str.charAt(i) + 0) >= 65 && (str.charAt(i) + 0) <= 90)  
                     return -1;  
                 if(str.charAt(i) == '_' && i != 0 && i != str.length()-1)  
                     if(str.charAt(i-1) == '_' || str.charAt(i+1) == '_')  
                         return -1;  
             }  
               
             return 1;  
         }  
       
         if(str.charAt(0) >= 65 && str.charAt(0) <= 90)  
             return -1;  
   
         return 2;  
     }  

}

							

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

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

 static int clac( int s, int p, int n ) {
    if( s < p )    return 0;
    return (s-n%s-1)*(n/s) + clac( s/p, p, n%s )*((n+s-1)/s);
}

 public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
  
   int n, p, s, k=0, t;
   while(sc.hasNext()) {
     p=sc.nextInt();
     n=sc.nextInt();
    if(p==00&&n==0) break;
    s = 1;
    while( s <= n/p )
    s *= p;
    t = clac( s, p, n );
    System.out.printf( "Case %d: %04dn", ++k, (n+1-t)%10000 );
   }
  }    
}


							

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

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

pair<int,int> p[100], q[100];

int n;

bool input( ) {
    int i;
    scanf( "%d", &n );
    if( n == 0 )
        return false;
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].first, &p[i].second );
    sort( p, p+n );
    return true;
}

int clac( pair<int,int> p[], int len, int a, int b ) {
    int i, j;
    int best = 0, curr, edge = 0, temp, inside, ans = 0;
    for( i=0; i<len; i=j ) {
        inside = 0;
        temp = edge;
        for( j=i; j<len && p[j].first == p[i].first; j++ )
            if( p[j].second != a && p[j].second != b )
                inside++;
            else
                edge ++;
        curr = edge + inside;
        if( curr - best > ans )
            ans = curr - best;
        if( temp - inside < best )
            best = temp - inside;
    }
    return ans;
}



int main( ) {
    int k=0, t, i, j, ans = 0, a, b, count=0, m;
    while( input() ) {
        ans = 1;
        for( i=0; i<n; i++ ) {
            for( j=i+1; j<n; j++ ) {
                a = p[i].second;
                b = p[j].second;
                if( a > b ) swap( a, b );

                m = 0;

                for( k=0; k<n; k++ )
                    if( p[k].second >= a && p[k].second <= b )
                        q[m++] = p[k];

                t = clac( q, m, a, b );
                if( t > ans )
                    ans = t;
            }
        }
        printf( "Case %d: %dn", ++count, ans );
    }
    return 0;
}




							

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

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


using namespace std;
double ans, total;
vector<int> e[100100];
int s[100100];

double dfs( int k, int f ) {
    double sum = 0, t;
    for( int i=0; i<e[k].size(); i++ ) {
        if( e[k][i] != f ) {
            t = dfs( e[k][i], k );
            sum += t;
            t = (t*2)-total;
            if( t < 0 ) t = -t;
            if( t < ans ) ans = t;
        }
    }
    sum += s[k];
    return sum;
}

int main( ) {
    int n, m, i, a, b, counter=1;
    while( scanf( "%d%d", &n, &m ) == 2 && n ) {
        total = 0;
        for( i=1; i<=n; i++ ) {
            e[i].clear( );
            scanf( "%d", &s[i] );
            total += s[i];
        }

        for( i=0; i<m; i++ ) {
            scanf( "%d%d", &a, &b );
            e[a].push_back( b );
            e[b].push_back( a );
        }

        ans = total;
        dfs( 1, -1 );

        printf( "Case %d: %.0lfn", counter++, ans );
    }
    return 0;
}




							

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

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

int has_one[1<<16];

int ans[1<<16];
int result[1<<16][24];

int a[16];

void clac_has_one( ) {
    int i;
    has_one[0] = 0;
    for( i=1; i<(1<<16); i++ )
        has_one[i] = has_one[ i&(i-1) ] + 1;
}

void clac_result( ) {
    int i, j, k;
    int index[4];

    for( i=0; i<(1<<16); i++ ) {
        if( has_one[i] == 4 ) {
            k = 0;
            for( j=0; j<16; j++ )
                if( i & (1<<j) )
                    index[k++] = j;
            j = 0;
            do{
                result[i][j] = a[index[0]]*4 + a[index[1]]*3 
                    + a[index[2]]*2 + a[index[3]];
                j++;
            }while( next_permutation( index, index+4 ) );

            sort( result[i], result[i]+j );
        }
    }
}

int c_8_4[100][4];
int m;

void clac_c84( ) {
    int i, j, k;
    m = 0;
    for( i=0; i<(1<<7); i++ ) {
        if( has_one[i] == 4 ) {
            k = 0;
            for( j=0; j<7; j++ )
                if( i & (1<<j) )
                    c_8_4[m][k++] = j;
            m++;
        }
    }
}



void clac_ans( ) {
    int i, j, k, a, b, *ra, *rb, *ka, *kb, t;
    char counter[11000] = { 0 };

    int id[8];

    for( i=0; i<(1<<16); i++ ) {
        if( has_one[i] == 8 && ( i<(1<<15) || ans[((1<<16)-1)^i] ) ) {

            k = 0;
            for( j=0; j<16; j++ )
                if( i & (1<<j) )
                    id[k++] = j;
            t = 0;

            for( j=0; j<35; j++ ) {
                a = (1<<id[c_8_4[j][0]]) | (1<<id[c_8_4[j][1]]) 
                    | (1<<id[c_8_4[j][2]]) | (1<<id[c_8_4[j][3]]);
                b = i ^ a;
                ra = result[a];
                rb = result[b];
                ka = result[a] + 23;
                kb = result[b] + 23;
                if( *ra > *kb || *rb > *ka )
                    continue;

                while( ra<=ka )
                    counter[ *ra++ ]++;
                while( rb<=kb )
                    t += counter[ *rb++ ];
                ra = result[a];
                while( ra<=ka )
                    counter[ *ra++ ] = 0;
            }
            
            ans[i] = t;
        }
        else
            ans[i] = 0;
    }
    return ;
}

long long clac( ) {
    long long sum = 0;
    int i;

    for( i=0; i<(1<<15); i++ ) {
        if( has_one[i] == 8 ) {
            sum += (long long)ans[i]*ans[((1<<16)-1)^i];
        }
    }
    return sum;
}

int main( ) {
    int i, count=1;
    clac_has_one( );
    clac_c84( );

    while( true ) {
        scanf( "%d", &a[0] );
        if( a[0] == 0 ) break;

        for( i=1; i<16; i++ )
            scanf( "%d", &a[i] );

        clac_result( );

        clac_ans( );

        printf( "Case %d: %lldn", count++, clac() );
    }
    return 0;
}