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

import java.util.Scanner;

public class Main{

public static void main(String[] args) {
   Scanner s = new Scanner(System.in);
   while(true) {
    int n = s.nextInt();
    if(n == 0)
     System.exit(-1);
    double min = 1000000000;
    while(n > 0) {
     int v = s.nextInt();
     int t = s.nextInt();
     if(t < 0) {
      n--;
      continue;
     }
     double time = 4.5 / v * 3600 + t;
     if(time < min)
      min = time;
     n--;
    }
    System.out.println((int)Math.ceil(min));
   }
}

}


							

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

#include <iostream>
#include <string.h>
using namespace std;

int a[1030][1030];
int main()
{
    int test,d,n,i,max,j,temp,x,y,now;
    cin>>test;
    while(test--)
    {
        cin>>d;
        cin>>n;
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)
        {
            cin>>x>>y;
            cin>>a[x][y];
        }
        max=-1;
        for(i=1;i<1025;i++)
        {
            a[i][0]+=a[i-1][0];
            a[0][i]+=a[0][i-1];
        }
        temp=2*d+1;
        for(i=1;i<1025;i++)
            for(j=1;j<1025;j++) {
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
                if(i>=temp&&j>=temp) {
                    now=a[i][j]-a[i-temp][j]-a[i][j-temp]+a[i-temp][j-temp];
                    if(now>max) {
                        max=now;
                        x=i-d;
                        y=j-d;
                    }
                }
            }
        cout<<x<<" "<<y<<" "<<max<<endl;
    }
    return 0;
}
							

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

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
public class Main {   
  
    private static int[][] directions = new int[][]{   
        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};   
  
    static void BreadthFirstSearch(int startX, int startY,   
            chessNode[][] chessPanel, int size) {   
        chessNode currentNode = null, nextNode = null;   
        LinkedList<chessNode> queue = new LinkedList();   
        currentNode = chessPanel[startY][startY] =   
                new chessNode(startX, startY, true, 0, false);   
        queue.addLast(currentNode);
        while (!queue.isEmpty()) {   
            currentNode = queue.removeFirst();
            if (currentNode.isTarget()) {  
                break;   
            }   
            for (int i = 0; i < 8; i++) {   
                int x = currentNode.getX() + directions[i][0];   
                int y = currentNode.getY() + directions[i][1];   
                int step = currentNode.getStep();   
                if (x >= 0 && x < size && y >= 0 && y < size) {   
                    if (chessPanel[x][y] == null) {   
                        chessPanel[x][y] = new chessNode(x, y, false, 0, false);   
                    }   
                    nextNode = chessPanel[x][y];   
                    if (!nextNode.isVisited()) {   
                        nextNode.setVisited(true);
                        nextNode.setStep(step + 1);   
                        queue.addLast(nextNode);   
                    }   
                }   
            }   
        }   
    }   
  
    public static void main(String[] args) {   
        int n = 0;   
        int size = 0;   
        int startX = 0, startY = 0, endX = 0, endY = 0;   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        n = scanner.nextInt();   
        for (int i = 0; i < n; i++) {   
            size = scanner.nextInt();   
            startX = scanner.nextInt();   
            startY = scanner.nextInt();
            endX = scanner.nextInt();
            endY = scanner.nextInt();
            chessNode[][] chessPanel = new chessNode[size][size];   
            chessPanel[endX][endY] = new chessNode(endX, endY, false, 0, true);   
            BreadthFirstSearch(startX, startY, chessPanel, size);   
            System.out.println(chessPanel[endX][endY].getStep());   
        }   
    }   
}   
  
class chessNode {   
  
    private int x;   
    private int y;   
    private boolean visited;
    private int step;
  
    public int getX() {   
        return x;   
    }   
  
    public chessNode(int x, int y, boolean visited, int step, boolean target) {   
        this.x = x;   
        this.y = y;   
        this.visited = visited;   
        this.step = step;   
        this.target = target;   
    }   
  
    public void setX(int x) {   
        this.x = x;   
    }   
  
    public int getY() {   
        return y;   
    }   
  
    public void setY(int y) {   
        this.y = y;   
    }   
    private boolean target;   
  
    public boolean isVisited() {   
        return visited;   
    }   
  
    public void setVisited(boolean visited) {   
        this.visited = visited;   
    }   
  
    public int getStep() {   
        return step;   
    }   
  
    public void setStep(int step) {   
        this.step = step;   
    }   
  
    public boolean isTarget() {   
        return target;   
    }   
  
    public void setTarget(boolean target) {   
        this.target = target;   
    }   
}  


							

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
   int n=scanner.nextInt();
    BigInteger[][] a;
    BigInteger[] b;
    BigInteger aa,aa1,aa2,aa3;
    for (int i=0;i< n ;i++ ){
         a=new BigInteger[3][3];
     b=new BigInteger[3];
     for (int j=0;j< 3 ;j++ ){
       for (int k=0;k< 3 ;k++ ){
        a[j][k]=scanner.nextBigInteger();
       }
      b[j]=scanner.nextBigInteger();
    }
    aa=a[0][0].multiply(a[1][1].multiply(a[2][2]).add(a[1][2].multiply(a[2][1]).negate())).
          add((a[0][1].multiply(a[1][0].multiply(a[2][2]).
          add(a[1][2].multiply(a[2][0]).negate()))).negate()).
          add(a[0][2].multiply(a[1][0].multiply(a[2][1]).
          add(a[1][1].multiply(a[2][0]).negate())));

       aa1=b[0].multiply(a[1][1].multiply(a[2][2]).add(a[1][2].multiply(a[2][1]).negate())).
         add((a[0][1].multiply(b[1].multiply(a[2][2]).
         add(a[1][2].multiply(b[2]).negate()))).negate()).
         add(a[0][2].multiply(b[1].multiply(a[2][1]).
         add(a[1][1].multiply(b[2]).negate())));

      aa2=a[0][0].multiply(b[1].multiply(a[2][2]).add(a[1][2].multiply(b[2]).negate())).
         add((b[0].multiply(a[1][0].multiply(a[2][2]).
         add(a[1][2].multiply(a[2][0]).negate()))).negate()).
         add(a[0][2].multiply(a[1][0].multiply(b[2]).
         add(b[1].multiply(a[2][0]).negate())));

      aa3=a[0][0].multiply(a[1][1].multiply(b[2]).add(b[1].multiply(a[2][1]).negate())).
         add((a[0][1].multiply(a[1][0].multiply(b[2]).
         add(b[1].multiply(a[2][0]).negate()))).negate()).
         add(b[0].multiply(a[1][0].multiply(a[2][1]).
         add(a[1][1].multiply(a[2][0]).negate())));

    System.out.println(aa1+" "+aa2+" "+aa3+" "+aa);
    if (aa.equals(BigInteger.ZERO)){
        System.out.println("No unique solution");
    }
       else{
    DecimalFormat df=new DecimalFormat("0.000");
    BigDecimal x1=new BigDecimal(aa1.toString());
    BigDecimal x2=new BigDecimal(aa2.toString());
    BigDecimal x3=new BigDecimal(aa3.toString());
    BigDecimal x=new BigDecimal(aa.toString());
    BigDecimal xx1=x1.divide(x,6,BigDecimal.ROUND_HALF_UP);
    BigDecimal xx2=x2.divide(x,6,BigDecimal.ROUND_HALF_UP);
    BigDecimal xx3=x3.divide(x,6,BigDecimal.ROUND_HALF_UP);
   System.out.println("Unique solution: "+df.format(xx1)+" "+df.format(xx2)+" "+df.format(xx3));
    }
    System.out.println();
  }
}
}


							

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

//* @author: ccQ.SuperSupper
import java.util.*;
import java.io.*;
class node{
    int init_have;
    int sum_have;
    int nodes;
    Vector son = new Vector();
}
public class Main {
    
 static int N = 10000+100;
 public static void main(String []args) throws Exception{
        
  int n,i,j,ans,cnt,sons,root;
  node Tree[] = new node[N];
  for(i=0;i< N;++i) Tree[i] = new node();
        
   //Scanner cin = new Scanner(new FileInputStream("input.txt"));//System.in);
   Scanner cin = new Scanner(System.in);
        
   while(cin.hasNext()){
    n = cin.nextInt();
    if(n==0) break;
    for(i=0;i<=n;++i){
        Tree[i].sum_have = -1;
        Tree[i].son.clear();
        Tree[i].nodes = 0;
    }
    for(i=0;i< n;++i){
        cnt = cin.nextInt();
        Tree[cnt].init_have = cin.nextInt();
        sons = cin.nextInt();
        for(j=0;j< sons;++j){
            ans = cin.nextInt();
            Tree[cnt].son.add(ans);
            Tree[ans].sum_have = -2;
        }
    }
    root = 1;
    for(i=1;i<=n;++i) if(Tree[i].sum_have==-1)
        root = i;
    System.out.println(dfs(Tree,root));
   }
 }

public static int dfs(node Tree[],int root){
    
  int i,j,k,ans=0;
  Tree[root].sum_have = Tree[root].init_have;
  Tree[root].nodes = 1;
  for(i=0;i< Tree[root].son.size();++i){
    k = (Integer)Tree[root].son.get(i);
    if(Tree[k].sum_have< 0){
        ans+=dfs(Tree,k);
        Tree[root].sum_have+=Tree[k].sum_have;
        Tree[root].nodes+=Tree[k].nodes;
        ans+=abs(Tree[k].sum_have-Tree[k].nodes);
    }
   }
   return ans;
 }
    public static int abs(int a){
        return a<0?-a:a;
    }
}

							

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

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

public class Main {
 public static void main(String[]args){
  BigInteger dat[]=new BigInteger[100];
  dat[0]=BigInteger.ONE;
  BigInteger tr=new BigInteger("3");
  for(int i=1;i< 100;i++){
    dat[i]=dat[i-1].multiply(tr);
  }
  long N;
  int t;
  boolean first;
  Scanner cin=new Scanner(System.in);
  while(cin.hasNext()){
    N=cin.nextLong();
    if(N==0) break;
    N--;
    t=0;
    first=true;
    System.out.print("{");
    while(N>0){
    if(N%2==1){
      if(first){
       first=false;
       System.out.print(" "+dat[t]);
      }
      else System.out.print(", "+dat[t]);
    }
    t++;
    N/=2;
     }
     System.out.println(" }");
   }
  }
}
							

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

/* @author: */
import java.util.Scanner;
public class Main{
  static final  double PI=3.1415926;
  static final  double eps=1e-6;

  public static void main(String args[])
{    
  Scanner sc=new Scanner(System.in);
  double L,n,C,M,y1,low,high,mid;
  while(true)
  {
     L=sc.nextDouble();
     n=sc.nextDouble();
     C=sc.nextDouble();
     if(L==-1&&n==-1&&C==-1)break;
     if(L<=eps||n<=eps||C<=eps)
    {
      System.out.println("0.000");
      continue;
    }
     M=(1+n*C)*L;
     low=0;
     high=PI;
     while(true)
     {
    mid=(low+high)/2;
    y1=M-L*mid/Math.sin(mid);
    if(Math.abs(y1)<=eps)break;
    else if(y1>0)low=mid;
    else high=mid;
     }
     System.out.printf("%.3fn",L*Math.tan(mid/2)/2);
    }
  }
}

							

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

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

int e2[2010], ee2[2010], n;
vector<int> e1[2010];
vector<int> ee1[2010];

vector<int> ans[2010];

void input( ) {
    int i, k, m;
    scanf( "%d", &n );
    
    for( i=0; i<n; i++ ) {
        scanf( "%d", &m );
        e1[i].resize( m );
        while( m-- ) {
            scanf( "%d", &k );
            e1[i][m] = k-1;
            ee1[k-1].push_back( i );
        }
    }
    
    for( i=0; i<n; i++ ) {
        scanf( "%d", &e2[i] );
        e2[i]--;
        ee2[e2[i]] = i;
    }

}

vector<int> st;
int st2[2010], sn2;

bool sign[2010];
int flag1[2010], flag2[2010], counter;

void search( int k ) {
    int s = ee2[k];
    sign[k] = true;
    for( int i=0; i<e1[s].size(); i++ )
        if( !sign[e1[s][i]] )
            search( e1[s][i] );
    st.push_back( k );
}

void dfs1( ) {
    for( int i=0; i<n; i++ )
        if( !sign[i] )
            search( i );
}


void find( int k ) {
    int t;
    flag1[k] = counter;
    for( int i=0; i<ee1[k].size(); i++ ) {
        t = ee1[k][i];
        if( !flag2[t] ) {
            st2[sn2++] = t;
            flag2[t] = counter;
            if( !flag1[ e2[t] ] )
                find( e2[t] );
        }
    }
}

void dfs2( ) {
    int t;
    for( int i=n-1; i>=0; i-- ) {
        if( !flag1[st[i]] ) {

            sn2 = 0;
            counter = i+1;
            find( st[i] );
            
            while( sn2-- ) {
                t = st2[sn2];
                for( int j=0; j<e1[t].size(); j++ )
                    if( flag1[e1[t][j]] == counter )
                        ans[t].push_back( e1[t][j] );
                sort( ans[t].begin(), ans[t].end() );
            }
        }
    }
}

void output( ) {
    for( int i=0; i<n; i++ ) {
        printf( "%d", ans[i].size() );
        for( int j=0; j<ans[i].size(); j++ )
            printf( " %d", ans[i].operator [](j)+1 );
        printf( "n" );
    }

}

int main( ) {
    input( );
    dfs1();
    dfs2();
    output( );
    return 0;
}


							

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

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

using namespace std;

const int size = 1000;

struct point
{
    double x, y, z;
    int k;
}p[size];

inline double dis( point &a, point &b )
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z);
}

double dist[size][size];
typedef pair< double, int > type;
type s[size*size];
int n, m;

void init( )
{
    int i, j;
    scanf( "%d", &n );
    
    for( i=0; i<n; i++ )
        scanf( "%lf %lf %lf %d", &p[i].x, &p[i].y, &p[i].z, &p[i].k );

    m = 0;
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ )
    {
        s[m].first = dis( p[i], p[j] );
        s[m].second = i*n+j;
        m++;
    }

    sort( s, s+m );
}

int N[size];

void doit( )
{
    int ans = 0, j, i, t, a, b;
    double len = 0;

    for( i=0; i<n; i++ )
        N[i] = 1;

    t = 0;
    s[m].first = 1e100;
    for( i=0; i<m; i=j )
    {
        for( j=i; s[j].first < s[i].first + 1e-6 ; j++ )
        {
            a = s[j].second / n;
            b = s[j].second % n;
            if( p[a].k == p[b].k )
            {
                N[a]++, N[b]++;
                if( N[a] == 0 )
                    t--;
                if( N[b] == 0 )
                    t--;
            }
            else
            {
                N[a]--, N[b]--;
                if( N[a] == -1 )
                    t++;
                if( N[b] == -1 )
                    t++;
            }
        }

        if( t > ans )
        {
            ans = t;
            len = s[i].first;
        }
    }

    printf( "%dn%.4lfn", ans, sqrt(len) );
}

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


							

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

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

public class Main {
 public static void main(String[] args) throws Exception {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  String line;
  StringBuffer sb = new StringBuffer();
  while ((line = in.readLine()) != null) {
    for (int i = 0; i < line.length(); i++) {
         char ch = line.charAt(i);
      if (ch != ' ' && ch != 9)
        sb.append(ch);
    }
   }
  in.close();

  int indent = 1;
  boolean needws = true;
  System.out.println("{");
  for (int i = 1; i < sb.length(); i++) {
        char ch = sb.charAt(i);
    if (needws && ch != '}') {
        printws(indent);
        needws = false;
    }
      switch (ch) {
        case '{':
           System.out.println(" {");
           indent++;
           needws = true;
        break;
    case '}':
       needws = false;
       indent--;
       printws(indent);
      System.out.print("}");
      break;
      case ';':
      System.out.println(";");
      needws = true;
      break;
      case ',':
      System.out.print(", ");
      break;
      default:
      System.out.print(ch);
     }
  }
}

private static void printws(int indent) {
 for (int i = indent; --i >= 0;)
    System.out.print("    ");
 }
}

							

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

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

public class Main {
    public static void main(String[] args) {
       BigInteger sum,m,D[] = new BigInteger[2];
       int i,b[] = new int[340];
       Scanner cin = new Scanner(System.in);
       m = cin.nextBigInteger();
       sum = cin.nextBigInteger();
       int k = 0;
       while(sum.compareTo(BigInteger.ZERO) != 0)
       {
           D = sum.divideAndRemainder(m);
           sum = D[0];
           if(D[1].compareTo(BigInteger.ZERO) == 0)
           {
               sum = sum.subtract(BigInteger.ONE);
               b[++k] = m.intValue();
           }
           else
               b[++k] = D[1].intValue();
       }
       for(i = k;i >= 1;i --)
          System.out.print(b[i]);
       System.out.println();
    }
}

							

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

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

public class Main {

    public static void main(String[] args) throws Exception{

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        int totalnum;
        int count = 0;
        //while((totalnum=Integer.parseInt(in.readLine()))!=-100){
        while(true)    {
            int num;
            ArrayList < Integer> array = new ArrayList< Integer>();
            
            totalnum=Integer.parseInt(in.readLine());
            
            if(totalnum==-1)
                break;
            array.add(totalnum);
            while((num=Integer.parseInt(in.readLine()))!=-1){
                array.add(num);
            }
            
            int length = array.size();
            
            int [] num_array = new int[length];
            int [] max_array = new int[length];
            
            for(int i=0;i< length;i++){
                num_array[i] = array.get(i);
                max_array[i] = 1;
            }
            
            int max_value = 1;
            for(int i=1;i< length;i++){
                for(int j=0;j< i;j++){
                    if(num_array[i]<=num_array[j]&&max_array[i]<=max_array[j])
                        max_array[i]++;
                }
                max_value = (max_array[i]>max_value)?max_array[i]:max_value;
            }
            
            if(count!=0)
                System.out.println();
            System.out.println("Test #"+(++count)+":");
            System.out.println("  maximum possible interceptions: "+max_value);
        }
        
        
    }

}


							

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

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 101
#define INF 10000
int anset[NMAX],alen,min;
int m[10020];
int t[NMAX];
int N,S,len;
void solve()
{
    int i,j;
    m[0]=0;
    i=1;
    while(1)
    {
        m[i]=INF;
        
        for(j=0;j<len;j++)
        {
            if(t[j]>i)
                break;
            if(m[i]>m[i-t[j]]+1)
            {
                m[i]=m[i-t[j]]+1;
            }
            
        }
        if(m[i]>S)
            break;
        i++;
    }
    i--;
    if(min<i)
    {
        min=i;
        alen=len;
        memcpy(anset,t,sizeof(t));
    }
    else if(min==i)
    {
        if(alen>len)
        {
            alen=len;
            memcpy(anset,t,sizeof(t));
        }
        else if(alen==len)
        {
            if(anset[alen-1]>t[len-1])
                memcpy(anset,t,sizeof(t));
        }
    }
}    
void output()
{
    int i;
    printf("max coverage = %d :",min);
    for(i=0;i<alen;i++)
        printf(" %d",anset[i]);
    printf("n");
}
int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int i;
    scanf("%d",&S);
    while(S)
    {
        scanf("%d",&N);
        min=-1;
        while(N--)
        {
            scanf("%d",&len);
            for(i=0;i<len;i++)
            {
                scanf("%d",&t[i]);
            }
            solve();
        
        }
        output();
        scanf("%d",&S);
    }
#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}
							

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

/* @author: */
import java.util.Scanner;
public class Main {
  private int n;
  private int a[];

  public Main(int n,int[] a){
   this.n=n;
   this.a=a;
 }
  public boolean doIt(){
   for(int j=1;j< n/2;j++)
   {
    for(int i=j;i< n-j;i++)
    {
         if((a[i-j]-a[i])*(a[i+j]-a[i])< 0)
      {
        return true;
      }
    }
   }
   return false;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext())
    {    
         int n=0;
         String s=sc.next();
         if(s.endsWith(":"))
          n=Integer.parseInt(s.substring(0,s.length()-1));
         if(n==0) break;
           int a[]=new int[n];
      for(int i=0;i< n;i++){
        int tempno=sc.nextInt();
        a[tempno]=i;
      }
         Main m=new Main(n,a);
      if(!m.doIt())
        System.out.printf("yesn");
      else
        System.out.printf("non");
     }
   }
}
							

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

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

#define YES     { printf( "samen" );         continue; }
#define NO        { printf( "differentn" );    continue; }
#define PT(a)     (printf("an"));

struct node
{
    vector< node* > next;
    char c;

}mem[500];

char w[1000];
int u;

node* new_node()
{
    mem[u++].next.clear();
    return &mem[u-1];
} 

int creat( int a, node *p )
{
    node *q;
    p->c = w[a];
    a++;
    if( w[a] == '(' )
    {
        a++;
        while( 1 )//w[a] != '' )
        {
            if( w[a] == ',' ) a++;
        
            q = new_node();
            p -> next.push_back( q );
            q -> next.push_back( p );
            a = creat( a, q );

            if( w[a] == ')' )
            {
                a++;
                return a;
            }
        }
    }
    return a;
}

    
bool judge( node *p1, node *f1, node *p2, node *f2 )
{
    int d1 = p1->next.size(), d2 = p2->next.size(), i, j, k;

    if( d1 != d2 || p1->c != p2->c ) return false;    

    for( i = 0; i < d1; i++ )
        if( p1->next[i] == f1 ) break;

    for( j = 0; j < d2; j++ )
        if( p2->next[j] == f2 ) break;

    for( k = 1; k < d1; k++ )
        if( ! judge( p1->next[(i+k)%d1], p1, p2->next[(j+k)%d2], p2 ) )
            return false;

    return true;
}

int main()
{
    bool key;
    int cas, i, j, h;


    scanf( "%d", &cas );

    while( cas-- )
    {

        u=0;

        scanf( "%s", w );
        mem[u].next.clear();
        u++;
        creat( 0, &mem[u-1] );
        
        h = u;

        scanf( "%s", w );
        mem[u].next.clear();
        u++;
        creat( 0, &mem[u-1] );
        
        if( u == 2 ) 
        {
            if( mem[0].c == mem[1].c )    YES
            else NO
        }

        if( h*2 != u )
            NO

        for( i=0; i < h; i++ )
        if( mem[i].next.size() == 1 )
            break;

        if( i < h )
        {
            for( key=1, j=h; j < u && key ; j++ )
            if( mem[j].next.size() == 1 && mem[j].c == mem[i].c )
            {
                if( judge( mem[i].next[0], &mem[i], mem[j].next[0], &mem[j] ) )
                {
                    key = 0;
                }
            }

            if( !key ) YES
        }
        
        NO
    }
    return 0;
}



							

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

import java.util.*;   
import java.text.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
        List list = new ArrayList();   
           
        for(int i = 0; i < num; i++)   
            list.add(Double.valueOf(cin.nextLine()));   
           
        Collections.sort(list);   
           
        double result, temp = 0;   
        double a, b = 0;   
           
        if(list.size() == 1)   
            result = Double.valueOf((Double)list.get(0)).doubleValue();   
        else  
        {   
            int index = list.size() - 1;   
            a = Double.valueOf((Double)list.get(index)).doubleValue();   
            b = Double.valueOf((Double)list.get(index-1)).doubleValue();   
               
            result = 2 * Math.sqrt(a * b);   
               
            for(int i = index - 2; i>=0; i--)   
            {   
                a = Double.valueOf((Double)list.get(i)).doubleValue();   
                result = 2 * Math.sqrt(a * result);   
            }   
        }   
           
        DecimalFormat df = new DecimalFormat("#.000");   
        System.out.println(df.format(result));   
    }   
  
}  


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Edge implements Comparable{
    int u,v,disten;
    Edge(){};
    void set(int u,int v,int disten){
        this.u = u;
        this.v = v;
        this.disten = disten;
    }
    public int compareTo(Object obj){
        Edge temp = (Edge)obj;
        if(this.disten>temp.disten) return 1;
        return -1;
    }
}
class Set{
    int father[],num[];
    void init(int n){
        num = new int[n+10];
        father = new int[n+10];
        Arrays.fill(num, 1);
        Arrays.fill(father, -1);
    }
    int Ufind(int who){
        int temp,cnt = who;
        while(father[who]!=-1){
            who = father[who];
        }
        while(cnt!=who){
            temp = father[cnt];
            father[cnt] = who;
            cnt = temp;
        }
        return who;
    }
    void Uset(int u,int v){
        if(u==v) return ;
        if(num[u]>num[v]){
            father[v] = u;
            num[u]+=num[v];
        }else{
            father[u] = v;
            num[v]+=num[u];
        }
    }
}
class Kruscal{
    final int N = 15000+100;
    int n,m,cnt,max,ans;
    Edge edge[] = new Edge[N];
    Kruscal(){
        for(int i=0;i< N;++i) edge[i] = new Edge();
    }
    void init(int n,int m){
        cnt = 0;
        this.n = n;
        this.m = m;
        max = ans = 0;
    }
    void addEdge(int u,int v,int disten){
        edge[cnt++].set(u, v, disten);
    }
    void calc(PrintWriter out){
        Set set = new Set();
        set.init(n);
        Arrays.sort(edge,0,m);
        for(int i=0;i< m;++i){
            if(set.Ufind(edge[i].u) == set.Ufind(edge[i].v)){
                edge[i].disten = -1;
            }else{
                max = Max(max,edge[i].disten);
                ++ans;
                set.Uset(set.Ufind(edge[i].u), set.Ufind(edge[i].v));
            }
        }
        
        out.println(max);
        out.println(ans);
        for(int i=0;i< m;++i)if(edge[i].disten>=0){
            out.println(edge[i].u+" "+edge[i].v);
        }
    }
    int Max(int a,int b){
        return a>b?a:b;
    }
}
public class Main {
 public static void main(String[]args)throws Exception{
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    Kruscal kruscal = new Kruscal();
    int n,m,u,v,disten;
    n = GetNum(cin);
    m = GetNum(cin);
    kruscal.init(n, m);
    for(int i=0;i< m;++i){
        u = GetNum(cin);
        v = GetNum(cin);
        disten = GetNum(cin);
        if(u>v) kruscal.addEdge(v, u, disten);
        else kruscal.addEdge(u, v, disten);
    }
    kruscal.calc(out);
    out.flush();
 }
    static int GetNum(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
}

							

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

//* @author 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

//���·��bellman_ford
public class Main {
 Scanner cin = new Scanner(System.in);

 int n;
 int m;
 int s;
 double v;
 Edge[] rate;
 Edge[] commission;
 double[] value;
 public static final double EPS = 1E-8;

 public void inPut() throws FileNotFoundException {
 // File f = new File("D:\ACM\POJ����\1860\test.txt");
 // cin = new Scanner(f);

  n = cin.nextInt();
  m = cin.nextInt();
  s = cin.nextInt() - 1;
  v = cin.nextDouble();
  int a;
  int b;
  double rab;
  double cab;
  double rba;
  double cba;
  rate = new Edge[m * 2];
  commission = new Edge[m * 2];
  value = new double[n];

  for (int i = 0; i < 2 * m; i++) {
   a = cin.nextInt() - 1;
   b = cin.nextInt() - 1;
   rab = cin.nextDouble();
   cab = cin.nextDouble();
   rba = cin.nextDouble();
   cba = cin.nextDouble();

   rate[i] = new Edge();
   rate[i].s = a;
   rate[i].e = b;
   rate[i].v = rab;
   commission[i] = new Edge();
   commission[i].s = a;
   commission[i].e = b;
   commission[i].v = cab;

   i++;
   rate[i] = new Edge();
   rate[i].s = b;
   rate[i].e = a;
   rate[i].v = rba;
   commission[i] = new Edge();
   commission[i].s = b;
   commission[i].e = a;
   commission[i].v = cba;
  }

  solve();
 }

 private void solve() {
  if (bellmanFord(s, rate, commission)) {
   System.out.println("YES");
  } else {
   System.out.println("NO");
  }
 }

 private boolean bellmanFord(int s, Edge[] rate, Edge[] commission) {
  Arrays.fill(value, 0);
  value[s] = v;
  boolean released;

  while (value[s] <= v + EPS) {
   released = false;
   for (int i = 0; i < m * 2; i++) {
    if (value[rate[i].e] + EPS < (value[rate[i].s] - commission[i].v)
      * rate[i].v) {
     value[rate[i].e] = (value[rate[i].s] - commission[i].v)
       * rate[i].v;
     released = true;
//     System.out.println(Arrays.toString(value));
    }
   }

   if (!released) {
//    System.out.println(true);
    return value[s] > v + EPS;
   }
  }
//  System.out.println(value[s]);
  return true;
 }

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

 class Edge {
  int s;
  int e;
  double v;
 }
}
							

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

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

using namespace std;

struct pairs {
    int first, second;
}p[20100];

bool cmp( const pairs& a, const pairs& b ) {
    return a.first<b.first || a.first==b.first&&a.second<b.second;
}

int main( ) {
    int n, i, sx, sy;

    while( true ) {
        scanf( "%d", &n );

        if( n == 0 )
            break;

        sx = sy = 0;
        for( i=0; i<n; i++ ) {
            scanf( "%d%d", &p[i].first, &p[i].second );
            sx += p[i].first;
            sy += p[i].second;
        }
        
        if( ( (n%1) && (sx%n||sy%n) ) || 2*sx%n || 2*sy%n ) {
            printf( "This is a dangerous situation!n" );
            continue;
        }
        
        stable_sort( p, p+n, cmp );
        
        sx = 2*sx/n; sy = 2*sy/n;
        
        for( i=0; i<=n/2; i++ )
            if( p[i].first+p[n-1-i].first != sx 
                || p[i].second+p[n-1-i].second != sy )
                break;
            
        if( i > n/2 )
            printf( "V.I.P. should stay at (%.1f,%.1f).n", sx*0.5, sy*0.5 );
        else
            printf( "This is a dangerous situation!n" );
    }

    return 0;
}



							

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

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

    /**
     * @param args
     */
    static int max(int a,int b)
    {
        if(a>b) return a;
        return b;
    }
    static int min(int a,int b)
    {
        if(a>b) return b;
        return a;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int t,n,m,ans1,ans2,i,k;
        
        Scanner cin = new Scanner(System.in);
        
        t = cin.nextInt();
        while(t>0)
        {
            --t;
            
            n = cin.nextInt();
            m = cin.nextInt();
            
            ans1 = 0;ans2 = 0;
            
            for(i=0;i< m;++i)
            {
                k = cin.nextInt();
                ans1 = max(ans1,min(k,n-k));
                ans2 = max(ans2,max(k,n-k));
            }
            System.out.println(ans1+" "+ans2);
        }

    }

}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  String s=in.next();
  boolean bb=false;
  for(int i=0;i< s.length()-1;i++)
  {
    if(s.charAt(i)-s.charAt(i+1)>=0)
    {
        System.out.println(0);
        bb=true;
        break;
    }    
    }
   if(bb) System.exit(0);
   int l=s.length();
   long ans=0;
   for(int i=1;i< l;i++)
    ans+=find(26,i);
   int k=0;
   for(int i=0;i< l;i++)
   {
    k=0;
    if(i!=0) k=s.charAt(i-1)-'a'+1;
    int y=s.charAt(i)-'a'+1;
    for(int j=y-1;j>k;j--)
    {
        ans+=find(26-j,l-i-1);
    }
    }
   System.out.println(ans+1);
 }

 public static long find(int u,long a)
 {
    if(u< a) return 0;
    if(a==0) return 1;
    long l=1;
    for(int i=u;i>u-a;i--)
        l*=i;
    for(int i=1;i<=a;i++)
        l/=i;
    return l;
  }
}
							

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

import java.util.*; 
public class Main {
  
      static long modPow(long a,long n)
      {
          long MOD=9901;
          if (n==1) return a%MOD;
         long tmp=modPow(a,n>>1);
         tmp=tmp*tmp%MOD;
         if ((n&1)==1) tmp=tmp*a%MOD;
         return tmp;
     }

     static long myPow(long a,long n)
    {
        if (n==0) return 1;
        long ans=modPow(a,(n>>1)+1);
        ans=(ans+1)%9901;
        if ((n&1)==1)
            ans=ans*myPow(a,n>>1)%9901;
        else
        {
            ans=ans*myPow(a,(n-1)>>1)%9901;
            ans=ans+modPow(a,n>>1);
        }
        return ans%9901;
    }

    public static void main(String[] args) {
         Scanner cin=new Scanner(System.in);
        long a=cin.nextLong();
        long b=cin.nextLong();
        long ans=1;
        for (long i=2;i*i<=a;i++)
        if (a%i==0)
         {
            long pow=0;
            while (a%i==0)
            {
                a/=i;
                pow++;
            }
            pow*=b;
            ans=ans*myPow(i,pow)%9901;
        }
        if (a!=1)
            ans=ans*myPow(a,b)%9901;
        System.out.println((ans+9901)%9901);
   }
 }
  

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int sun=in.nextInt();
  int sum=0;
  int i;
  for(i=1;i< 9999;i++)
  {
    sum+=i;
    if (sum>=sun)break;
  }
  if((sum-sun)%2==0) System.out.println(i);
  else if((sum-sun)%2==1&&i%2==1) System.out.println(i+2);
  else if((sum-sun)%2==1&&i%2==0) System.out.println(i+1);
 }
}
							

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

//* @author: 
import java.util.*;
public   class Main{    
   
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);

       int a1=sc.nextInt();
       int a2=sc.nextInt();
       int a3=sc.nextInt();
       int a4=sc.nextInt();
       int a5=sc.nextInt();
      System.out.println( hashQuestions(a1,a2, a3,a4,a5));
  }
   
 
   /**  
    * @param a1  
    * @param a2  
    * @param a3  
    * @param a4  
    * @param a5  
    */  
   public static  int  hashQuestions(int a1, int a2, int a3, int a4, int a5){   
       
    char hash[] = new char[25000010];   //hash�洢   
       
    int bigsqure[] = new int[100];           //��b�����ֵ�   
    int pos = 0;   
    int m = 0;            
    for (int x = -50; x <= 50; x++) {   
        if(x == 0) continue;         //Ϊ��ɾ���0 ��Ȼ����4200���   
        bigsqure[m++] = x*x*x;       //�����b��ֵ����4���Ժ���á�   
    }   
       
    //������ֵ   
    for (int i = 0; i < 100; i++) {   
        for (int j = 0; j < 100; j++) {   
            pos = -(bigsqure[i]*a1 + bigsqure[j]*a2);      
                
            hash[pos+12500000]++;          //���ֵΪ1��!   
               
            //��������֮�� ��hash������������� ��������߽���Ԫ��  ֵ��Ϊ1�ˡ�   
        }   
    }   
       
    int answer = 0;   
    //���ұ�ֵ   
    for (int i = 0; i < 100; i++) {   
        for (int j = 0; j < 100; j++) {   
            for (int k = 0; k < 100; k++) {   
                pos = bigsqure[i]*a3 + bigsqure[j]*a4 + bigsqure[k]*a5;   
                if(pos > 12500000 || pos < -12500000)    
                    continue;   
                answer += hash[pos+12500000];   
                   
                //�����ӵĵ��?�ǣ�����ұߵ�ֵû�к�����ص� ��ô���ֵ��0��   
                //����ص��ˣ�����ߵ�ʱ�� �Ѿ�������Ϊ1�ˣ���ô �����е��ص��ġ�1���ۼ���4   
                //���ǽ��   
            }   
        }   
    }   
        
  return answer;
 }  
}
							

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

//PKU_1837_Balance_DP(û˼·)
#include <iostream>
#include <cstring>
using namespace std;
int C,G;
int Pos[22];
int Weight[22];
int Value[22][7505];//������ȫΪ��25���������һͷ�����ʮ��Ϊ25*10*15(�۳�) = 3750
//Ȼ���״̬ƽ��ȫΪ��Ϊ7500��״̬��ȡ7505
int main()
{
    while(cin>>C>>G)
    {
        for(int i = 1;i <= C;i++)
            cin>>Pos[i];
        for(int i = 1;i <= G;i++)
            cin>>Weight[i];

        memset(Value,0,sizeof(Value));

        for(int i = 1;i <= C;i++)
            Value[1][Pos[i]*Weight[1] + 3750] = 1; //��ʼ����ֻ��һ�����룬�ҵ�����λ������ȡ����״̬��

        for(int i = 2;i <= G;i++) //�ӵڶ������뵽��G��
        {
            for(int j = 1;j <= C;j++) //�4γ���ÿһ��λ��
            { 
                for(int k = 1;k < 7505;k++) //�������е�״̬���������д���
                {
                    if(Value[i - 1][k])
                        Value[i][k + Pos[j] * Weight[i]] += Value[i - 1][k];
                }
            }
        }

        cout<<Value[G][3750]<<endl;
    }
    return 0;
}

/*
Balance
Time Limit: 1000MS  Memory Limit: 30000K
Total Submissions: 1998  Accepted: 1052

Description

Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance.
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.

Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.

Input

The input has the following structure:
? the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
? the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: '-' for the left arm and '+' for the right arm);
? on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.

Output

The output contains the number M representing the number of possibilities to poise the balance.
Sample Input

2 4
-2 3
3 4 5 8

Sample Output

2

*/

							

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

//* @author: 
import java.util.Scanner;
public class Main{
   private int n;
   private double a[];
   int b[],c[],sum[];
   
   public Main(int n,double a[]){
    this.n=n;
    this.a=a;
    b=new int[n+1];
    c=new int[n+1];
    sum=new int[n+1];
  }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      double a[]=new double[n+1];
      for(int i=1;i<=n;i++){
        a[i]=sc.nextDouble();//�±��1��ʼ
   
       }
      Main ma=new Main(n,a);
     // ma.showB();
      //ma.showC();
      System.out.println(ma.doIt());
      
  }

   private void showB(){
     for(int i=1;i<=n;i++){
        System.out.println(b[i]+"  ");
     }
    }

   private void showC(){
     for(int i=1;i<=n;i++){
        System.out.println(c[i]+"  ");
     }
   }
  
   private void lis(){//a[]��ǰi��Ԫ���У�����������еij���Ϊb[i]
    b[1] = 1;
    for (int i=2;i<=n;i++)
    {
        int max = 0;
        for (int j=1;j< i;j++)
        {
            if (a[j]< a[i] && b[j]>max)
            {
                 max = b[j];
            }
        }
        b[i] = max + 1;
    } 
  // showB();
}

private void flis()//a[]�ĴӺ���ǰ��n-i+1Ԫ���У�����������еij���Ϊc[i]
{
     c[n] = 1;
    for (int i=n-1;i>=1;i--)
    {
        int max = 0;
        
        for (int j=n;j>i;j--)
        {
            if (a[j]< a[i] && c[j]>max)
            {
                max = c[j];
            }
        }
        c[i] = max + 1;
    }
}

 

  private int doIt(){
    lis();
    flis();
    int min=n;
   for(int i=1;i<=n;i++){
      for (int j = i + 1; j <= n; j++) {//��ߵ������}��,���a[i]���������Լ��ȸߵ���
            if (a[i] == a[j]){
              if(c[i]<=c[j])
                c[i]=c[j]+1;
            }
        }

      sum[i]=n-(b[i]+c[i]-1);
      if(sum[i]< min){
           min=sum[i];
      }
   }
  return min;
 }

}

							

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

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

public class Main{
    public static int x,y,z,p,h;
    public static void main(String[] args){
     Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n=scanner.nextInt();
        int m,s;
        String f;
        for (int i=0;i< n ;i++ ){
            m=scanner.nextInt();
            x=y=z=p=0;
            h=2;
            for (int j=0;j< m ;j++ ){
                f=scanner.next();
                s=scanner.nextInt();
                if (f.equals("forward")){
                    forward(s);
                }
                else if (f.equals("back")){
                    turnLeft();
                    turnLeft();
                    forward(s);
                }
                else if (f.equals("left")){
                    turnLeft();
                    forward(s);
                }
                else if (f.equals("right")){
                    turnLeft();
                    turnLeft();
                    turnLeft();
                    forward(s);
                }
                else if (f.equals("up")){
                    turnUp();
                    forward(s);
                }
                else if (f.equals("down")){
                    turnUp();
                    turnUp();
                    turnUp();
                    forward(s);
                }
            }
            System.out.println(x+" "+y+" "+z+" "+p);
        }
    }

    public static void turnLeft(){
        if (h==0){
            if (p==2){
                p=1;
            }
            else if (p==1){
                p=5;
            }
            else if (p==5){
                p=4;
            }
            else if (p==4){
                p=2;
            }
        }
        else if (h==3){
            if (p==2){
                p=4;
            }
            else if (p==1){
                p=2;
            }
            else if (p==5){
                p=1;
            }
            else if (p==4){
                p=5;
            }
        }
        else if (h==2){
            if (p==0){
                p=4;
            }
            else if (p==4){
                p=3;
            }
            else if (p==3){
                p=1;
            }
            else if (p==1){
                p=0;
            }
        }
        else if (h==5){
            if (p==0){
                p=1;
            }
            else if (p==4){
                p=0;
            }
            else if (p==3){
                p=4;
            }
            else if (p==1){
                p=3;
            }
        }
        else if (h==1){
            if (p==3){
                p=5;
            }
            else if (p==5){
                p=0;
            }
            else if (p==0){
                p=2;
            }
            else if (p==2){
                p=3;
            }
        }
        else if (h==4){
            if (p==3){
                p=2;
            }
            else if (p==5){
                p=3;
            }
            else if (p==0){
                p=5;
            }
            else if (p==2){
                p=0;
            }
        }
    }

    public static void turnUp(){
        int t=h;
        turnLeft();
        turnLeft();
        h=p;
        p=t;
    }

    public static void forward(int s){
        switch (p){
            case 0:
                x=x+s;
            break;
            case 1:
                y=y+s;
            break;
            case 2:
                z=z+s;
            break;
            case 3:
                x=x-s;
            break;
            case 4:
                y=y-s;
            break;
            case 5:
                z=z-s;
            break;
        
        }
    }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  while((a--)!=0)
  {
    String[] ss=in.readLine().split(" ");
    int l=Integer.parseInt(ss[0]);
    int cnt=Integer.parseInt(ss[1]);
    int[] arr=new int[l];
    ss=in.readLine().split(" ");
    for(int i=0;i< l;i++)
        arr[i]=Integer.parseInt(ss[i]);
    while((cnt--)!=0)
    {
      boolean bb=false;
      for(int y=l-1;y>=0;y--)
      {
        for(int i=l-1;i>y;i--)
        {
            if(arr[i]>arr[y])
            {
              int u=arr[i];
              arr[i]=arr[y];
              arr[y]=u;
              Arrays.sort(arr,y+1,l);
              bb=true;
              break;
            }
         }
        if(bb)break;
        }
        if(!bb)
        for(int i=0;i< l;i++)arr[i]=i+1;
    }
    for(int i=0;i< l-1;i++)
        System.out.print(arr[i]+" ");
    System.out.println(arr[l-1]);
    }
   }
}
							

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

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

public class Main {
    static BigInteger[] base = new BigInteger[128];
    static void init(){
        base[0] = BigInteger.ONE;
        for (int i=1; i< 128; i++){
            base[i] = base[i-1].multiply(BigInteger.valueOf(2));
        }
    }
    public static void main(String args[]){
        init();
        Scanner cin = new Scanner(System.in);
        int m,n = cin.nextInt();
        int[] a = new int[128];
        int[] b = new int[128];
        while ((n--)!=0){
            m = cin.nextInt();
            for (int i=0; i< m; i++){
                a[i] = cin.nextInt();
                if (i!=0){
                    a[i] = a[i]^a[i-1];
                }
            }
            for (int i=0; i< m; i++){
                b[i] = cin.nextInt();
                if (i!=0){
                    b[i] = b[i]^b[i-1];
                }
            }
            BigInteger start = BigInteger.ZERO;
            BigInteger end = BigInteger.ZERO;
            for (int i=0; i< m; i++){
                if (a[m-i-1]!=0) start = start.add(base[i]);
                if (b[m-i-1]!=0) end = end.add(base[i]);
            }
            System.out.println(end.max(start).subtract(end.min(start)));
        }
    }
}
							

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

//* @author: 
/*��˹��Ԫ,Ȼ������Ԫ��ľ���õ���,����ì�ܵ������޽�

   �����ĸ���Ϊ2^k   kΪ����ȫΪ0������
 */



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

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

class Gaus 
{
    int a[][],num;
    static int M=2;
    Gaus(int m[][],int n)
    {
    a=m;
    num=n;
    }
    
    int mod(int a) //��M����
    {
    return (a%M+M)%M;
    }
    
    void swap(int x,int y) //����a[x],a[y]
    {
    int temp[];
    temp=a[x];
    a[x]=a[y];
    a[y]=temp;
    }
    
    void change() //����任
    {
    int i,j,k,max;
    for(i=0;i< num-1;i++)
    {
       max=i;
       for(j=i+1;j< num;j++)
       {
        if(a[j][i]>a[max][i])
         max=j;
       }
       if(a[max][i]==0)continue;
       swap(i,max);
       for(j=i+1;j< num;j++)
       {
        if(a[j][i]==0)continue;
        for(k=i+1;k<=num;k++)
        {
         a[j][k]=mod(a[j][k]*a[i][i]-a[i][k]*a[j][i]);
        }
        a[j][i]=0;
       }
    }
    }
    
    int noUse()//����ȫΪ0������,���в���b���з���-1
    {
    int count=0,i,j;
    boolean zero;
    for(i=num-1;i>=0;i--)
    {
       zero=true;
       for(j=0;j< num;j++)
       {
        if(a[i][j]!=0)
        {
         zero=false;
         break;
        }
       }
       if(zero)
       {
        if(a[i][num]!=0)return -1;
        count++;
       }
    }
    return count;
    }
}

public class Main {
static int value[];
static void init()
{
   value=new int[29];
   value[0]=1;
   for(int i=1;i< 29;i++)
   {
    value[i]=2*value[i-1];
   }
}
    public static void main(String args[]) throws IOException
    {
    init();
    int a[][]=new int[28][29],t1,t2,t,n,i;
    int s1[]=new int[28];
    Gaus data;
    t=cin.nextInt();
    while((t--)>0)
    {
       n=cin.nextInt();
       for(i=0;i< n;i++)s1[i]=cin.nextInt();
       for(i=0;i< n;i++)
       {
        t1=cin.nextInt();
        Arrays.fill(a[i],0);
        a[i][i]=1;
        if(t1==s1[i])a[i][n]=0;
        else a[i][n]=1;
       }
       while(true)
       {
        t1=cin.nextInt();
        t2=cin.nextInt();
        if(t1==0&&t2==0)break;
        a[t2-1][t1-1]=1;
       }
       data=new Gaus(a,n);
       data.change();
       t1=data.noUse();
       if(t1< 0)System.out.println("Oh,it's impossible~!!");
       else System.out.println(value[t1]);
    }
    
    }
}

							

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
int ans[1025][161], s[1025];
int v[161], n, m;
const int MAX = ( (unsigned int)1<<31-1 );
void clac( ) {
    int i, j, k, t, h, best;    
    memset( ans, 0x7F, sizeof ans );    
    ans[1][1] = v[1];
    s[1] = v[1];
    for( i=2; i<=n; i++ ) {
        for( j=2; j<=i&&j<=m; j++ ) {
            best = ans[i-1][j-1]+v[j];
            h = i/j;
            if( h > i-j+1 )
                h = i-j+1;
            for( k=2; k<=h; k++ )
                if( ( t = ans[i-k][j-1] + s[k] + v[j]*k*k ) < best )
                    best = t;
            ans[i][j] = best;
        }
        best = MAX;
        for( j=2; j<=i&&j<=n; j++ )
            if( ans[i][j] < best )
                best = ans[i][j];
        s[i] = best;
        ans[i][1] = s[i] + v[1]*i*i;
    }

}
int main( ){
    int t, i;
    scanf( "%d", &t );
    while( t-- ) {
        scanf( "%d %d", &n, &m );
        for( i=1; i<=m; i++ )
            scanf( "%d", &v[i] );
        std::sort( v+1, v+m+1 );
        clac( );
        printf( "%dn", s[n] );
    }
    return 0;
}
							

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

//* @author: ccQ.SuperSupper
import java.util.*;    //Monkeys' Pride

class node implements Comparable {
    int x,y;
    public int compareTo(Object o) {
        node oo=(node)o;
        if(this.x!=((node)o).x)
            return this.x>((node)o).x?1:0;
        return this.y>((node)o).y?1:0;
    }
}
public class Main{

 static int N = 500000+100;

 public static void main(String []args) throws Exception{
    int i,y,n,ans;
    node mokey[] = new node[N];
    for(i=0;i< N;++i)
         mokey[i] = new node();
    Scanner cin = new Scanner(System.in);

    while(cin.hasNext()){
        n = cin.nextInt();
        if(n==0) break;
        for(i=0;i< n;++i){
            mokey[i].x = cin.nextInt();
            mokey[i].y = cin.nextInt();
        }
        Arrays.sort(mokey,0,n);
        ans = 1; y = mokey[n-1].y;

        for(i=n-2;i>=0;--i){
            if(y< mokey[i].y){
                ++ans;
                y = mokey[i].y;
            }
        }
        System.out.println(ans);
    }
 }
}

							

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

#include"stdio.h"
#include<iostream>
#include"memory.h"
using namespace std;
int x[20],y[20],m;
int s[2000],len;
void cheng(int a)
{int i,t;
for(i=0,t=0;i<len;i++)
{s[i]*=a;s[i]+=t;
t=s[i]/10;
s[i]%=10;
}
while(t)
{s[len++]=t%10;
t/=10;
}

}
int p[]={2,3,5,7,11,13,17,19,23,29,31 ,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
     101,     103   ,  107,     109  ,   113,
     127 ,    131  ,   137 ,    139 ,    149 ,    151 ,    157    , 163 ,    167     ,173,
     179  ,   181 ,    191  ,   193,     197  ,   199,     211   ,  223  ,   227    , 229,
     233   ,  239,     241   }  ,z[300];

void init()
{int i,j;
cin>>m;
for(i=0;i<m;i++)cin>>y[i];
for(i=0;i<y[0];i++)
{for(j=0;j<m&&y[j]>i;j++);
x[i]=j;
}

}
inline int find(int i,int j)
{return (y[i]+x[j]-i-1-j-1+1);
}

void doit()
{int d=0,k;
int i,j,n=sizeof(p)/sizeof(int);
for(i=0;i<m;i++)d+=y[i];
for(i=0;i<n;i++)z[i]=0;
for(i=0;d>=0;i++,d--)
{k=d;
for(j=0;j<n&&k>1;j++)
if(k%p[j]==0){z[j]++;k/=p[j];j--;}
}
int l;
len=1;s[0]=1;
for(i=0;i<m;i++)
for(j=0;j<y[i];j++)
{k=find(i,j);
for(l=0;l<n&&k>1;l++)
if(k%p[l]==0){z[l]--;k/=p[l];l--;}
}
//_int64 s=1;
for(i=0;i<n;i++)
{
    while(z[i])
    {cheng(p[i]);z[i]--;}
}
for(i=len-1;i>=0;i--)
printf("%d",s[i]);
printf("n");
}
int main()
{init();
doit();
return 0;
}
							

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

#include"stdio.h"
#include"memory.h"

const int L=2048*16;
short left[L],right[L],max[L];char stop[L];
#define bigger(a,b) (((a)>(b))?(a):(b))
//inline short bigger(short a,short b)
//{return a>b?a:b;}
short a,b,key;
void insert(short root,short begin,short end)
{
    if(begin>end||b<begin||end<a)return;
    short l1,l2,*l=&left[root],*r=&right[root]; 
    if(a<=begin&&end<=b)
    {
        stop[root]=1;
        if(key==1)
        {
            (*l)=(*r)=max[root]=0;
        }
        
        else 
        {
            (*l)=(*r)=max[root]=end-begin+1;
        }
        return;
    }

    l1=(begin+end)/2-begin+1;
    l2=end-(begin+end)/2;

    short ji=root*2+1,ou=root*2+2;
    if(stop[root])
    {
        stop[root]=0;stop[ji]=1;stop[ou]=1;

        if(max[root]>0)
        {
            left[ji]=right[ji]=max[ji]=l1;
            left[ou]=right[ou]=max[ou]=l2;
        }
        else
        {
            left[ji]=right[ji]=max[ji]=0;
             left[ou]=right[ou]=max[ou]=0;
        }
    }
    insert(ji,begin,(begin+end)/2);
    insert(ou,(begin+end)/2+1,end);
    if(left[ji]==l1)(*l)=left[ji]+left[ou];
    else (*l)=left[ji];
    if(right[ou]==l2)(*r)=right[ou]+right[ji];
    else (*r)=right[ou];
    max[root]=bigger(bigger(max[ji],max[ou]),left[ou]+right[ji]);

}
int main()
{short n,ppp;
long p;
scanf("%d%d",&n,&p);
memset(stop,0,L*sizeof(char));
stop[0]=1;max[0]=left[0]=right[0]=n;
while(p--)
{scanf("%d",&ppp);
if(ppp==3)printf("%dn",max[0]);
else {scanf("%d%d",&a,&b);b+=a-1;a--;b--;key=ppp;insert(0,0,n-1);}
}
return 0;
}
							

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

#include<iostream>
#include"math.h"
using namespace std;

double r[1000];
double x[1000],t[1000];
char set[1000];
int n;

void init()
{int i;
cin>>n;
for(i=0;i<n;i++){set[i]=1;cin>>r[i];}
}

void doit()
{int i,j,k=0,s;

for(i=0;i<n;i++)
{x[i]=r[i];
k=-1;
for(j=0;j<i;j++)
    if(set[j])
    {t[j]=sqrt((r[i]+r[j])*(r[i]+r[j])-(r[i]-r[j])*(r[i]-r[j]))+x[j];
    if(t[j]>x[i]){x[i]=t[j];k=j;}
    }

for(j=k+1;j<i;j++)set[j]=0;

}
double right=0;
for(i=0;i<n;i++)if(x[i]+r[i]>right){right=x[i]+r[i];k=i;}
for(j=k+1;j<n;j++)set[j]=0;

for(i=0,s=0;i<n;i++)if(!set[i])s++;
cout<<s<<endl;
for(i=0;i<n;i++)if(!set[i])cout<<i+1<<endl;
}

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

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

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


char w[100000][7];
int len[100000];
int code[100000];

bool check( char *p, int n, char *w, int m ) {
    bool ans[7][21] = { false };
    char *a = p-1, *b = w-1;

    ans[0][0] = true;

    for( int i=1; i<=n; i++ ) {
        if( a[i] == '?' ) {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ans[i-1][j-1];
        }
        else if( a[i] == '*' ) {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ans[i-1][j] | ans[i][j-1] | ans[i-1][j-1];
        }
        else {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ( a[i]==b[j] && ans[i-1][j-1] );
        }
    }
    return ans[n][m];
}

int main( ) {
    int n, m, i, j, l;
    char str[100];
    
    scanf( "%d%d", &n, &m );
    for( i=0; i<n; i++ ) {
        scanf( "%s", w[i] );
        len[i] = strlen( w[i] );
        code[i] = 0;
        for( j=0; w[i][j]; j++ )
        if( w[i][j] != '?' && w[i][j] != '*' )
            code[i] |= 1<<(w[i][j]-'a');
    }
    
    bool key;
    for( i=0; i<m; i++ ) {
        scanf( "%s", str );
        l = strlen( str );
        key = false;
        int c = 0;
        for( j=0; str[j]; j++ )
            c |= 1<<(str[j]-'a');
            
        for( j=0; j<n; j++ ) {
            if( (c|code[j])==c && check( w[j], len[j], str, l ) ) {
                if( key )
                    printf( " " );
                printf( "%d", j );
                key = true;
            }
        }
        if( !key )
            printf( "Not match" );
        printf( "n" );
    }
    return 0;
}
							

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

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

struct point
{double x,y;};

const double pi=3.14159265359;

inline double cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline double dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}

double doit(point p1,point p2,point o,double r)
{point px,p[16];int set[16];int s=0;double t;
    
 p1.x-=o.x;
 p1.y-=o.y;
 p2.x-=o.x;
 p2.y-=o.y;
 o.x=0;
 o.y=0;
 
 if(fabs(p1.y)<=r){px.x=-sqrt(r*r-p1.y*p1.y);px.y=p1.y;
                   if(fabs(p1.x)<=fabs(px.x)||fabs(p2.x)<=fabs(px.x))
                   {
                   t=px.x;
                   set[s]=0;px.x=p1.x<px.x?px.x:p1.x;p[s++]=px;
                   px.x=-t;
                   set[s]=1;px.x=p2.x>px.x?px.x:p2.x;p[s++]=px;
                   }
                }
  if(fabs(p2.x)<=r){px.y=-sqrt(r*r-p2.x*p2.x);px.x=p2.x;
                   if(fabs(p1.y)<=fabs(px.y)||fabs(p2.y)<=fabs(px.y))
                   {
                   t=px.y;
                   set[s]=0;px.y=p1.y<px.y?px.y:p1.y;p[s++]=px;
                   px.y=-t;
                   set[s]=1;px.y=p2.y>px.y?px.y:p2.y;p[s++]=px;
                   }
                }
  if(fabs(p2.y)<=r){px.x=sqrt(r*r-p2.y*p2.y);px.y=p2.y;
                   if(fabs(p1.x)<=fabs(px.x)||fabs(p2.x)<=fabs(px.x))
                   {
                   t=px.x;
                   set[s]=0;px.x=p2.x>px.x?px.x:p2.x;p[s++]=px;
                   px.x=-t;
                   set[s]=1;px.x=p1.x<px.x?px.x:p1.x;p[s++]=px;
                   }
                }
  if(fabs(p1.x)<=r){px.y=sqrt(r*r-p1.x*p1.x);px.x=p1.x;
                   if(fabs(p1.y)<=fabs(px.y)||fabs(p2.y)<=fabs(px.y))
                   {
                   t=px.y;
                   set[s]=0;px.y=p2.y>px.y?px.y:p2.y;p[s++]=px;
                   px.y=-t;
                   set[s]=1;px.y=p1.y<px.y?px.y:p1.y;p[s++]=px;
                   }
                }
 double area=0;
 for(int i=0;i<s;i++)
 {p1=p[i];p2=p[(i+1)%s];
  if(set[(i+1)%s])area+=cheng(o,p1,p2)/2;
  else {if(cheng(o,p2,p1)<0)area+=acos(dcheng(o,p1,p2)/r/r)*r*r/2;
        else if(cheng(o,p2,p1)>0)area+=(2*pi-acos(dcheng(o,p1,p2)/r/r))*r*r/2;
        }
 }

  if(!s){if(p1.x<0&&p2.x>0&&p1.y<0&&p2.y>0)return pi*r*r;
            else return 0;
        }
  return area;
 }


int main()
{point p1,p2,p3,p4;
double r1,r2,r,da,db,l,area;
int t;
double x1,x2,y1,y2;char c1,c2;
cin>>t;

while(t--)
{cin>>c1;
cin>>p1.x>>p1.y;
if(c1=='R')cin>>p2.x>>p2.y;
else cin>>r1;

cin>>c2;
cin>>p3.x>>p3.y;
if(c2=='R')cin>>p4.x>>p4.y;
else cin>>r2;

if(c1=='R'&&c2=='R'){x1=p1.x>p3.x?p1.x:p3.x;x2=p2.x>p4.x?p4.x:p2.x;
                     y1=p1.y>p3.y?p1.y:p3.y;y2=p2.y>p4.y?p4.y:p2.y;
                    if(x2>x1&&y2>y1)printf("%.0fn",(x2-x1)*(y2-y1));
                     else printf("0n");
                    }
else if(c1=='C'&&c2=='C'){if(p1.x==p3.x&&p1.y==p3.y){r=r1<r2?r1:r2;printf("%.0fn",pi*r*r);continue;}
                     
                     l=sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y));
                     if(l>=r1+r2){printf("0n");continue;}
                     
                     da=acos((l*l+r1*r1-r2*r2)/2/l/r1);
                     db=acos((l*l+r2*r2-r1*r1)/2/l/r2);
                    
                     area=r1*r1*da+r2*r2*db-r1*l*sin(da);
                      printf("%.0fn",area);
                    }
                     
else            {if(c1=='C')printf("%.0fn",doit(p3,p4,p1,r1));
                    else printf("%.0fn",doit(p1,p2,p3,r2));
                }

}
return 0;
}
							

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

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

using namespace std;

char op[10];
int opn, ans;

void search( int h, const int *str, int len ) {
    int i, j, k;

    if( h >= ans )
        return;    

    if( len == 0 ) {
        ans = h;
        return;
    }

    if( h == opn )
        return;

    int w[20];
    
    for( i=0; i<len; i++ ) {
        if( (str[i]&255) == op[h] ) {
            memcpy( w, str, len*sizeof(int) );
            w[i] += (1<<8);
            if( (w[i]>>8) >= 3 ) {
                for( j=i-1, k=i+1; j>=0 && k<len && (w[j]&255)==(w[k]&255); j--, k++ ) {
                    w[j] += (w[k]>>8<<8);
                    if( (w[j]>>8) < 3 ) {
                        k++;
                        break;
                    }
                }
                while( k<len )
                    w[++j] = w[k++];
                search( h+1, w, j+1 );
            }
            else
                search( h+1, w, len );
        }
    }

}

int main( ) {
    int t, len, i;
    char w[21];
    int str[20], l;

    scanf( "%d", &t );

    while( t-- ) {
        scanf( "%d%d", &len, &opn );
        scanf( "%s", w );

        for( l=0, i=0; i<len; i++ ) {
            if( !i || w[i] != w[i-1] )
                str[l++] = (1<<8) | w[i];
            else
                str[l-1] += (1<<8);
        }
        ans = 6;
        
        scanf( "%s", op );
        sort( op, op+opn );

        do {
            search( 0, str, l );
        } while( next_permutation( op, op+opn ) );

        if( ans == 6 )
            printf( "losen" );
        else
            printf( "%dn", ans );
    }
    return 0;
}




							

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

/* @author: */
//��һ����N���ж���N�Ƿ�Ϊ������������������"Prime"�����������N����С������

import java.util.Random;
import java.util.Scanner;
//http://en.wikipedia.org/wiki/Pollard's_rho_algorithm
public class Main{
   static int MAX_COUNT = 6;
   static long allFactor[ ]=new long [65];
   static int nFactor;
   static Random rn=new Random();
    
 static long  fMultiModular(   long a,   long b,   long  n)
{
  long back = 0, temp = a % n;
  while ( b > 0 )
  {
     if ( (b & 0x1)==1 )
     {
        if ( (back = back + temp) > n )
          back -= n;
      }//modres=back
      if ( (temp <<= 1) > n )
     temp -= n;//temp=a^(xx)

    b >>= 1;
  }
  return back;
 }

 static long   GCD(long    a , long  b)
{
  int z = 0;
  while(b != 0 && a != 0)
  {
   while((a & 1) == 0 && (b & 1) == 0)
   {
    z++;
    a >>= 1;
    b >>= 1;
   }
  while((a & 1) == 0)
  {
    a >>= 1;
  }
  while((b & 1) == 0)
  {
    b >>= 1;
  }
 if(a > b)
 {
    a -= b;
 }
 else
 {
    b -= a;
 }
}//while
if(b == 0)
{
 return a << z;
}
 return b << z;
}


static long modular_exp( long  a, long b, long n)
{
    long d=1, dTemp=(a % n);
    while ( b > 0 )
    {
        if ( (b & 0x1)==1 )
            d = fMultiModular(d, dTemp, n);
        dTemp = fMultiModular(dTemp, dTemp, n);
        b >>= 1;
    }
    return d;
}

static boolean fWitNess(long  a, long  n, int t, long  u)
{
    long x, y = 0;
 x = modular_exp(a, u, n);
 while ( t-- >0)
 {
  y = fMultiModular(x, x, n);
  if ( y == 1 && x != 1 && x != n-1 )
   return true; //must not
  x = y;
 }
 return y != 1;
}


static boolean  miller_rabin(long n, int count) 
{
    if ( n == 1 )
        return false;
    if ( n == 2 )
    return true;
 
  long  a, u;    
    int t=0; 
    for (u = n-1; !((u & 0x1)==1); u>>=1)
  ++t;//2's power
    for (int i = 1; i <= count; ++i)
    {
        a = rand() % (n-1) + 1;
        if ( fWitNess(a, n, t, u) )
         return false;
    }
    return true;
}

static long  pollard_rho(long c, long num)
{
    int i=(1), k=(2);
   long x = rand() % num;
   long y = x, comDiv;
    do
    {
        ++i;
        if ( (x = fMultiModular(x, x, num) - c) < 0 )
   x += num;
        if ( x == y )
            break;
        comDiv = GCD((y-x+num)%num, num);
        if ( comDiv > 1 && comDiv < num )
            return comDiv;
        if ( i == k )
        {
            y = x;
            k <<= 1;
        }
    }while ( true );
    return num;
}

static void fFindFactor(long num)
{
    if ( miller_rabin(num, MAX_COUNT) == true )
    {
    allFactor[++nFactor] = num; 
 // printf("%I64d ",num);
        return;
    }
    long factor;
    do
    {
        factor = pollard_rho(rand()%(num-1) + 1, num);
    }while ( factor >= num );

    fFindFactor(factor);
    fFindFactor(num/factor);
}

 static long rand()
 {
     long temp=rn.nextLong();
     if(temp< 0)
         temp+=Long.MAX_VALUE;
     return 
    temp;
 }

 public static void main(String args[])
 {
    int t, i;
    Scanner cin = new Scanner(System.in);
    long test_num, min;
    t = cin.nextInt();
    while (t-- > 0) {
         test_num = cin.nextLong();
      //BigInteger testprime = new BigInteger(Long.toString(test_num));
      // if(testprime.isProbablePrime(20))
      if (miller_rabin(test_num, 20))                
        System.out.println("Prime");
      else {
           min = test_num;
        nFactor = 0;
        fFindFactor(test_num);
        for (i = 1; i <= nFactor; i++) {
        if (allFactor[i] < min)
          min = allFactor[i];
        }
        System.out.println(min);
     }
     }
  }
}
							

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

#include<iostream>
#include"algorithm"
using std::sort;
using namespace std;
int s[1001],N,K,M;
long d[10000];


int max()
{int i,k=M;
for(i=M+1;i<=N;i++)if(s[k]<=s[i])k=i;
return k;
}

void find()
{int i,j,k,h,down,up,x=N,y=N,best=0;
    
    for(i=N,j=0,h=0;i>=M;i--)
    {while(h<j&&d[h]%2000>i)
        {down=d[h]/2000;up=down+M-1<N?down+M-1:N;
        for(k=down;k<=up;k++)s[k]--;
        h++;
        }
    while(j<K&&i-d[j]%2000<M)
        {down=d[j]/2000;up=down+M-1<N?down+M-1:N;
        for(k=down;k<=up;k++)s[k]++;
        j++;
        }
    k=max();
    if(s[k]>best){best=s[k];y=k;x=i;}
    if(j>=K)break;
    }
    cout<<x-M<<' '<<y-M<<endl;
}
int cmp(long a,long b)
{return a%2000>b%2000;}

int main()
{int t,i;double a,b;
cin>>t;
while(t--)
{cin>>K>>N>>M;
for(i=0;i<K;i++){cin>>a>>b;d[i]=(long(a)+1)+2000*(long(b)+1);}

sort(&d[0],&d[K],cmp);
for(i=0;i<=N;i++)s[i]=0;
find();
}
return 0;
}


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
    public static long mod(long a,long b,long c)
    {
        long ret=1%c;
        while(b!=0)
        {
            if((b&0x1)!=0)
                ret=ret*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ret;
    }
    public static void main(String args[]) throws Exception {
    
        int idx=0;
        Scanner cin=new Scanner(System.in);
        long a,p;
        int t;
        t=cin.nextInt();
        while(t!=0)
        {
            --t;
            a=cin.nextLong();
            p=cin.nextLong();
            a%=p;
            if(a< 0)a+=p;
            ++idx;
            System.out.println("Scenario #"+idx+":");
            if(mod(a,(p-1)/2,p)==1)
                System.out.println("1");
            else
                System.out.println("-1");
            System.out.println();
        }
    }
}
							

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

//* @author 
import java.util.*;
public class Main {   
    
   static int count=0;
    /**  
     * @param args  
     */  
    public static void main(String[] args) {  
       Scanner in=new Scanner(System.in);
       String  t=in.nextLine();
       int tcase=Integer.parseInt(t);
  
       for(int j=1;j<=tcase;j++){
         count=0;
         String str = in.nextLine();
         String b[]=str.split("\s");
        
         int n=Integer.parseInt(b[0]);
         int a[]=new int[n];
         for(int i=0;i< n;i++)
           a[i]=Integer.parseInt(b[i+1]);
      
         sort(a);
         System.out.println("Scenario #"+j+":"); 
         System.out.println(count);
         System.out.println();
        }
     
    }   
       
       
    public static void sort(int arr[]) {
          
        int temp[] = new int[arr.length];   
        mergeSort(arr,temp,0,arr.length-1);
       
    }   
       
    private static void mergeSort(int arr[],int temp[],int m,int n) {   
        if (m == n) return;   
        int mid = (m+n)/2;   
        mergeSort(arr, temp, m, mid);   
        mergeSort(arr, temp, mid+1, n);   
        for (int i = m; i <= n; i++) {   
            temp[i] = arr[i];   
        }   
        int index1 = m;   
        int index2 = mid + 1;   
        int index = m;   
  
        while (index1 <= mid && index2 <= n) {   
            if (temp[index1] <= temp[index2]) {   
                arr[index++] = temp[index1++];   
            } else {   
                arr[index++] = temp[index2++];   
                count=count+mid-index1+1;
            }   
        }   
        while(index1 <= mid) {   
            arr[index++] = temp[index1++];   
        }   
        while(index2 <= n) {   
            arr[index++] = temp[index2++];   
        }   
           
    }   
  
}  

							

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

#include"stdio.h"
#include<iostream>
#include"memory.h"
#include"algorithm"

using namespace std;

int tree[1024*1024*2];
int stop[1024*1024*2];
long m[1024*1024*2];
long area;
int x1,y1,x2,y2,key;
long temp;
void search(int s,long mj);

void find(int xu,int yu,int xd,int yd,long s,long mj,int k)
{
 if(xu>=x2||xd<=x1||yu>=y2||yd<=y1){return;}
 
 if(key){tree[s]++;}
 if(!key){tree[s]--;}
 
 if(xu>=x1&&yu>=y1&&xd<=x2&&yd<=y2)
 {if(!key)stop[s]--;else tree[s]--;
    if(!k){temp=0;//search(s,mj);
           if(key)area+=mj-temp;
           else area-=mj-temp;
            }
  if(key){stop[s]++;tree[s]++;m[s]=mj;}
  else if(!stop[s]){if(mj==1)m[s]=0;else m[s]=m[s*4+1]+m[s*4+2]+m[s*4+3]+m[s*4+4];}
  return;}
//if(xd-xu<=1&&yd-yu<=1)return;
 if(stop[s])k=1;
 
 find(xu,yu,(xu+xd)/2,(yu+yd)/2,s*4+1,mj/4,k);
 find((xu+xd)/2,yu,xd,(yu+yd)/2,s*4+2,mj/4,k);
 find(xu,(yu+yd)/2,(xu+xd)/2,yd,s*4+3,mj/4,k);
 find((xu+xd)/2,(yu+yd)/2,xd,yd,s*4+4,mj/4,k);
 if(!stop[s])m[s]=m[s*4+1]+m[s*4+2]+m[s*4+3]+m[s*4+4];
}


int index[4000];
int x[4000],y[4000],xx[4000],yy[4000],z[4000],n;int sign[4000];
int xb,yb,zb,xe,ye,ze;

////////////////////////////////////////////
int cmp(int a,int b)
{return z[a]<z[b];}

void init()
{int i,x1,y1,z1,x2,y2,z2,h;
//cin>>xb>>yb>>zb>>xe>>ye>>ze;
scanf("%d%d%d%d%d%d",&xb,&yb,&zb,&xe,&ye,&ze);
n=0;
//cin>>h;
scanf("%d",&h);
for(i=0;i<h;i++)
{//cin>>x1>>y1>>z1>>x2>>y2>>z2;
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
if(x1<xb)x1=xb;
if(y1<yb)y1=yb;
if(z1<zb)z1=zb;

if(x2>xe)x2=xe;
if(y2>ye)y2=ye;
if(z2>ze)z2=ze;

if(x2>x1&&y2>y1&&z2>z1)
{x[n]=x1;y[n]=y1;xx[n]=x2;yy[n]=y2;z[n]=z1;sign[n]=1;index[n]=n;n++;
 x[n]=x1;y[n]=y1;xx[n]=x2;yy[n]=y2;z[n]=z2;sign[n]=0;index[n]=n;n++;
}

}

sort(&index[0],&index[n],cmp);
area=0;
memset(tree,0,1024*1024*2*sizeof(int));
memset(stop,0,1024*1024*2*sizeof(int));
memset(m,0,1024*1024*2*sizeof(long));
}
long v;
///////////////////////////
void doit()
{int i;v=0;

for(i=0;i<n;i++)
{x1=x[index[i]];x2=xx[index[i]];
 y1=y[index[i]];y2=yy[index[i]];
 key=sign[index[i]];
 find(0,0,1024,1024,0,1024*1024,0);
 area=m[0];
 //search(0,1024*1024);
 if(i<n-1)v+=area*(z[index[i+1]]-z[index[i]]);
}

}

int main()
{int t,i;
//cin>>t;
scanf("%d",&t);
for(i=1;i<=t;i++)
{cout<<"Scenario #"<<i<<":"<<endl;
 init();
 doit();
 cout<<v<<endl<<endl;
}

return 0;
}



							

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
 public static void main(String[] args) throws NumberFormatException, IOException {
  BufferedReader re=new  BufferedReader(new InputStreamReader(System.in) );
  int T=Integer.parseInt(re.readLine());
  for(int i=1;i<=T;i++)
  {   int n=0,last=0;
    boolean[] use=new boolean[300010];
    Set strset=new TreeSet();
      for(int p=0;p< 3;p++)
      {
   String str=re.readLine().toLowerCase();
   str=str.replaceAll("[^a-zA-Z]+"," ").trim();//"[^a-zA-Z]+"ƥ�����ĸ�ַ�
   String[] sa=str.split(" ");
   for(int j=0;j< sa.length&&strset.size()<=3;j++,n++)
   {
    String te=sa[j];
    if(p==0||p==1&&use[n])
    {
     int next=n+te.length();
     use[next]=true;
     last=Math.max(last,next);
    }
    if(p==2&&use[n])
    {
     strset.add(te);
    }
   }
      }
      System.out.println("Scenario #"+i+":");
   if(last>=n)
    strset.add("-outside-");
   if(strset.size()>3)
    System.out.println("-too many-");
   else
   {
    Iterator it=strset.iterator();
    while(it.hasNext())
    
     System.out.println(it.next());
    
   }
   System.out.println();
      }
 
 }

}


							

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

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

public class Main{
 public static void main(String[] args){
    Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int n=scanner.nextInt();
    double r,t;
    for (int i=0;i< n ;i++ ){
        r=scanner.nextDouble();
        t=scanner.nextDouble();
        System.out.println("Scenario #"+(i+1)+":");
        DecimalFormat df=new DecimalFormat("0.000");
        System.out.println(df.format(r*(1.0-1.0/(1.0+Math.sin(Math.PI/t)))));
        System.out.println();
    }
 }
}


							

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

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


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cas, k;
    cas=sc.nextInt();
    for( k=1; k<=cas; k++ )
    {
       int s1[]=new int[60010], s2[]=new int[60010];
         int i, n, m, a, b, ans;

    n=sc.nextInt();
       m=sc.nextInt();
    
    for( i=0; i< n; i++ )
    {
          a=sc.nextInt();
          b=sc.nextInt();
       s1[a]++;
       s2[b]++;
    }

    for( i=1; i<=n+m; i++ ){
       s1[i] += s1[i-1];
          s2[i] += s2[i-1];
       }

    ans = 0;
    for( i=0; i< m; i++ )
    {
          a=sc.nextInt();
          b=sc.nextInt();
       if( s1[a] >= s2[b] )
        ans += s1[a] - s2[b-1];
       else
        ans += s2[b] - s1[a];
    }

    System.out.printf( "Scenario #%d:n", k );
    System.out.printf( "%dnn", ans );
   }

 }
}



							

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

import java.io.PrintWriter;  
 import java.util.Scanner;public class Main {  
    
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);  
   //Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));  
   PrintWriter out = new PrintWriter(System.out);  
   int[][] table;  
   String[] input;  
   int n = 0;  
   while(true){  
    n = scn.nextInt();  
    if(n == 0){  
     break;  
    }  
    input = new String[n];  
   table = new int[n][n];  
    for(int i = 0; i < n; i++){  
     input[i] = scn.next();  
    }  
    //��ʼ�����  
    for(int i = 0; i < n; i++){  
     for(int j = 0; j < n; j++){  
      int disc = (i == j)?0:getDisc(input[i], input[j]);  
      table[i][j] = disc == 0? Integer.MAX_VALUE: Math.abs(disc);  
     }  
    }  
    //out.format("The highest possible quality is 1/%d.n", prim(table,n));  
    out.println("The highest possible quality is 1/" + prim(table, n) + ".");  
    
   }  
   out.flush();  
  }  
  public static int prim(int[][] table,int n){  
   int[] lowcost = new int[n];  
   boolean[] s = new boolean[n];  
   int sum = 0;  
   s[0] = true;//�ӵ�һ��λ�ÿ�ʼ  
  for(int i = 1; i < n; i++){  
    lowcost[i] = table[0][i];  
    s[i] = false;  
   }  
   //�ҵ� j - s �е���СȨ��  
   for(int i = 1; i < n; i++){  
    int min = Integer.MAX_VALUE;  
    int j = 1;  
    for(int k = 1; k < n; k++){  
     if((lowcost[k] < min) && (!s[k])){  
      min = lowcost[k];  
      j = k;  
     }  
    }  
    s[j] = true;//���뵽j ���뵽 s ������4  
    //sum += min;  
    for(int k = 1; k < n; k++){  
     if(table[j][k] < lowcost[k] && (!s[k])){  
      lowcost[k] = table[j][k];  
     }  
    }  
   }  
   for(int i = 0; i < n; i++){  
    sum += lowcost[i];  
   }  
   return sum;  
  }  
  /**  
   * �����ǰ���м���Ԫ�ز�Ϊa  
   * @param next  
   * @return  
   */ 
  private static int getDisc(String str1,String str2) {  
  int num = 0;  
   for(int i = 0; i < 7; i++){  
    if(str1.charAt(i) != str2.charAt(i)){  
     num++;  
    }  
   }  
   return num;  
  }  
 } 


							

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

#include<iostream>
#include"memory.h"
using namespace std;

char set[10000];
int use[10000][4];
long total[10000];
int money[4]={1,5,10,25};

int limit[4],p;


void doit()
{int i,j,h,k;
memset(set,0,10000*sizeof(char));
memset(use,0,10000*4*sizeof(int));
set[0]=1;
total[0]=0;
for(i=0;i<4;i++)
for(j=0;j<=p-money[i];j++)
{h=j+money[i];
if(set[j]&&(!set[h]||total[h]<total[j]+1)&&use[j][i]<limit[i])
    {set[h]=1;
    for(k=0;k<4;k++)use[h][k]=use[j][k];
    use[h][i]=use[j][i]+1;
    total[h]=total[j]+1;
    }
}

return;
}

int main()
{int i;
    while(1)
{cin>>p;
for(i=0;i<4;i++)cin>>limit[i];
if(p==0)break;
doit();
if(set[p])cout<<"Throw in "<<use[p][0]<<" cents, "<<use[p][1]<<" nickels, "<<use[p][2]<<" dimes, and "<<use[p][3]<<" quarters."<<endl;
else cout<<"Charlie cannot buy coffee."<<endl;
}
return 0;
}
							

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

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

public class Main {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    Map< String, Integer> map = new HashMap< String, Integer>();
    map.put("N", 0);
    map.put("E", 1);
    map.put("S", 2);
    map.put("W", 3);
    String pos[] = {"N", "E", "S", "W"};
    while(true){
    String dealer = in.next();
    String table[] = new String[4];
    for(int i = 0; i < 4; i++){
        table[i] = "";
    }
    if(dealer.equals("#")){
        return;
    }
    String card = "";
    card += in.next();
    card += in.next();
    
    //System.out.println(card);
    int count = 0;
    int turn = (map.get(dealer) + 1) % 4;
    while(count < 104){
        table[turn] += (card.charAt(count) +""+ card.charAt(count+1));
        count += 2;
        turn = (turn + 1) % 4;
    }
    //System.out.println(card.length());
    //System.out.println(Arrays.toString(table));
    Card cards[][] = new Card[4][13];
    for(int t = 0; t < 4; t++){
        cards[t] = new Card[13];
        for(int i = 0, j = 0; i < 13; i++, j += 2){
            cards[t][i] = Card.read(table[t].charAt(j), table[t].charAt(j+1));
        }
        Arrays.sort(cards[t]);
    }
    System.out.println("South player:");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[2][i].code + " " + cards[2][i].code);
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("| " + cards[2][i].cc + " ");
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[2][i].code + " " + cards[2][i].code);
    }
    System.out.println("|");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    
    System.out.println("West player:");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[3][i].code + " " + cards[3][i].code);
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("| " + cards[3][i].cc + " ");
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[3][i].code + " " + cards[3][i].code);
    }
    System.out.println("|");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    
    System.out.println("North player:");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[0][i].code + " " + cards[0][i].code);
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("| " + cards[0][i].cc + " ");
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[0][i].code + " " + cards[0][i].code);
    }
    System.out.println("|");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    System.out.println("East player:");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[1][i].code + " " + cards[1][i].code);
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("| " + cards[1][i].cc + " ");
    }
    System.out.println("|");
    for(int i = 0; i < 13; i++){
        System.out.print("|" + cards[1][i].code + " " + cards[1][i].code);
    }
    System.out.println("|");
    System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
    System.out.println();
    }
   }
}

class Card implements Comparable<Card>{
  int color;
  int num;
  char code;
  char cc;
  public Card(int c, int n, char code, char cc){
    color = c;
    num = n;
    this.code = code;
    this.cc = cc;
}
public static Card read(char c, char n){
    int color = -1;
    int num = 0;
    if(c == 'C'){
        color = 0;
    }
    else if(c == 'D'){
        color = 1;
    }
    else if(c == 'S'){
        color = 2;
    }
    else if(c == 'H'){
        color = 3;
    }
    if(Character.isLetter(n)){
        if(n == 'A'){
            num = 14;
        }
        else if(n == 'T'){
            num = 10;
           }
        else if(n == 'J'){
            num = 11;
        }
        else if(n == 'Q'){
            num = 12;
        }
        else if(n == 'K'){
            num = 13;
        }
    }
    else{
        num = n - '0';
    }
    return new Card(color, num, n, c);
    }
    
    public int compareTo(Card rhs){
    if(this.color != rhs.color){
        return this.color - rhs.color;
    }
    else{
        return this.num - rhs.num;
    }
    }
    
    public String toString(){
    return num + " " + color + " " + code + " " ;
    }
}

							

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

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

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);

  int p[]=new int[202];
  int q[]=new int[202];
  int s[][]=new int[202][202];
  int ans[][]=new int[202][202];
  int sum[]=new int[202];
  int n , i, j, l, k, temp, r;
  while(sc.hasNext())
  {
    n=sc.nextInt();
    if( n == 0 ) break;
    for( i=1; i<=n; i++ )
    {
           p[i]=sc.nextInt();
           sum[i] = p[i];
    }

    sum[0] = 0;
    sum[n+1] = 0;
    p[n+1] = 0;
    for( i=0; i<=n; i++ )
    {
           q[i]=sc.nextInt();
           sum[i+1] += sum[i] + q[i];
    }
    
    for( i=1; i<=n; i++ )
    {
       ans[i][i] = p[i] + q[i-1] + q[i];
       ans[i][i-1] = 0;
       s[i][i] = i;
    }
    ans[n+1][n] = 0;

    for( l=1; l< n; l++ )
      for( i=1; i+l<=n; i++ )
      {
        j = i+l;
        ans[i][j] = 999999999;
        for( k = s[i][j-1]; k<=s[i+1][j]; k++ )
        {
        if( ( temp = ans[i][k-1] + ans[k+1][j] ) < ans[i][j] )
        {
           ans[i][j] = temp;
           s[i][j] = k;
        }
        }
          ans[i][j] += sum[j+1] - p[j+1] - sum[i-1];
    }
    System.out.printf( "%dn", ans[1][n] );
     }
   }    
}