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

#include "stdio.h"
#include "memory.h"
#include "string.h"
#include "stdlib.h"



const int CHAR_NUM = 27;
const int MAXSIZE = 500000;

struct suftree{
    suftree *ch[CHAR_NUM];
    char *l, *r;
    int len;
    suftree *s, *p;
}suft[MAXSIZE];

int use_node = 0;

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

suftree *new_node( ) {
    memset( suft+use_node, 0, sizeof(suft[0].ch) );
    suft[use_node].s = 0;
    return suft+(use_node++);
}
suftree *proot;

int get_index( char c ) {
    if( c == '$' )
        return CHAR_NUM-1;
    return c-'a';
}

//    ->t    :    ->pnew->t 
suftree *disjoin( suftree *t, char *c ) {
    suftree *pnew = new_node( );

    pnew->len = t->p->len + ( c-t->l );
    pnew->l = t->l;
    pnew->r = c;
    pnew->p = t->p;
    pnew->ch[ get_index( *c ) ] = t;

    t->p->ch[ get_index( *(t->l) ) ] = pnew;

    t->l = c;
    t->p = pnew;

    return pnew;
}

/*
     p ------> s
    /            
   t            sc
*/
void modify_s( suftree *t ) {
    suftree *s, *p, *sc, *pnew;
    int l1, l2;
    char *l, *r;
    
    if( t->s ) return;
    p = t->p;
    s = p->s;

    if( p == proot && t->r-t->l == 1 ) {
        t->s = proot;
        return;
    }

    l = t->l + ( p == proot );
    r = t->r;

    sc = s->ch[ get_index( *l ) ];
    l1 = ( r - l );
    while( l1 ) {
        l2 = ( sc->r - sc->l );
        if( l1 < l2 ) {
            pnew = disjoin( sc, sc->l+l1 );
            t->s = pnew;
            modify_s( pnew );
            return;
        }
        else {
            if( l1 == l2 ) break;
            l1 -= l2;
            sc = sc->ch[ get_index( l[l2] ) ];
            l += l2;
        }
    }

    t->s = sc;
}

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

void create( char *w, int n ) {
    int i, j;
    char *l, *r = w+n+1, *c;
    suftree *h, *t, *tc; 
    use_node = 0;
    proot = new_node( );

    proot->p = proot->s = proot;
    proot->l = proot->r = w;
    proot->len = 0;
    w[n] = '$';
    w[n+1] = '';
    h = proot;

    for( i=0; i<n; i++ ) {
        
        if( i ) {
            l = r - ( h->r - h->l );
            if( l-w < i ) l = w+i;
        }
        else l = w;
        t = h->p->s;        

        while( 1 ) {
            j = get_index( *l );
            tc = t->ch[ j ];

            if( tc == 0 ) {
                tc = new_node( );
                tc->l = l;
                tc->r = r;
                tc->p = t;
                tc->len = t->len + ( r-l );
                t->ch[ j ] = tc;
                modify_s( t );
                break;
            }
            else {
                for( c=tc->l; c<tc->r && *l == *c; c++, l++ )
                    ;
                if( c >= tc->r )
                    t = tc;
                else
                    t = disjoin( tc, c );
            }
        }
        h = tc;

    }//for

}
//////////////////////////////////////////////////////////////////////

char word1[100100], word2[100100];
int main( ) {
    int len1, len2, ans = 0, temp, i;
    char *l, *l1, *l2;
    suftree *t, *tc;

    ans = 0;    
    scanf( "%s", word1 );
    scanf( "%s", word2 );
    len1 = strlen( word1 );
    len2 = strlen( word2 );
    create( word1, len1 );

    t = proot;
    l = word2;
    do {
        tc=t->ch[ get_index(*l) ];
        if( tc ) {
            for( l1=tc->l, l2=l; l1<tc->r && *l1==*l2; l1++, l2++ )
                ;
            if( ( temp = tc->len - ( tc->r-l1 ) ) > ans )
                ans = temp;
            if( l1 == tc->r )
                t = tc, l = l2;
            else {    
                if( t == proot )
                    l++;
                t = t->s;
            }
        }
        else {
            if( t == proot )
                l++;
            t = t->s;
        }
    }while( l < word2+len2 );
    

    printf( "%dn", ans );

    return 0;
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(in.hasNext())
  {
    int a=in.nextInt();
    int b=in.nextInt();
    if(a==1)System.out.println(b);
    else{
     ArrayList< Integer> arr=new ArrayList< Integer>();
     for(int i=1;i< a;i++)
     {
      int m=a,n=i;
      while(m%n!=0)
       {
        int w=m;
        m=n;
        n=w%n;
       }
      if(n==1) arr.add(i);
      }
       int c=arr.size();
       int k=b/c;
       int u=b%c;
       if(u==0){
        u=c;
        k-=1;
       }
    System.out.println(a*k+arr.get(u-1));
    }
    }
  }
}
							

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

//* @author  mekarlos@gmail.com
import java.util.Hashtable;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Hashtable< Integer,Integer> table;
        Scanner scan=new Scanner(System.in);
        int M[]=new int[300];
        int n=scan.nextInt(),k=0,m=1;
        boolean band=false;
        for(int i=0;i< n;i++){
            k=scan.nextInt();
            band=true;
            table=new Hashtable< Integer, Integer>();
            for(int j=0;j< k;j++){
                M[j]=scan.nextInt();
            }
            m=k;
            while(true){
                band=true;
                for(int j=0;j< k;j++){
                    if(table.get((M[j]%m))==null){
                        table.put((M[j]%m), 0);
                    }
                    else {
                        band=false;
                        break;
                    }
                }
                if(band==true) break;
                table.clear();
                m++;
            }
            System.out.println(m);
        }
    }
}
							

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

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

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
  
    int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
    int g[][]=new int[52][52];
    int ca,i,j,k,n,r,x,y,dir;
    ca=sc.nextInt();
    while ((ca--)!=0)
    {
        n=sc.nextInt();
        r=sc.nextInt();
        for(i=0;i< g.length;i++)
          Arrays.fill(g[i],0);
        for (i=0;i< r;i++)
        {
            x=sc.nextInt();
            y=sc.nextInt();
            g[x][y]=1;
        }    
        for (i=0;i<=n+1;i++)
        g[0][i]=g[n+1][i]=g[i][0]=g[i][n+1]=-1;
        x=sc.nextInt();
        y=sc.nextInt();
        if (y==0) dir=0; else 
        if (x==0) dir=1; else
        if (y==n+1) dir=2; else dir=3;
        x+=dx[dir];
        y+=dy[dir];
        while (g[x][y]!=-1)
        {
            if (g[x][y]!=0) dir=(dir+1)%4;            
            x+=dx[dir];
            y+=dy[dir];
        }    
        System.out.printf("%d %dn",x,y);        
    }        
  }
}

							

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

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


struct product{
    char w[100];
    char name[110][100];
    int per[110];
    int most[110], least[110];
    int m;
}p[10];

int n;

void clac( product &a ) {
    int s = 0, r = 100, i, j, k, low[100], up[100], sum, sh, rh;

    for( i=a.m-1; i>=0; i-- ) {
        if( a.per[i] != -1 ) {
            s = a.per[i];        // be sure that per[i] >= s;
            a.most[i] = a.least[i] = a.per[i];
        }
        else if( s < 1 )
            s = 1;

        low[i] = s;
        r -= s;
    }

    s = 100;
    sum = 0;
    for( i=0; i<a.m; i++ ) {
        if( a.per[i] != -1 ) {
            s = a.per[i];        // be sure that per[i] <= s;
        }
        up[i] = s;
        sum += up[i] - low[i];
    }

    for( i=0; i<a.m; i++ ) 
    if( a.per[i] == -1 ){
        a.most[i] = low[i];
        a.least[i] = up[i];

        for( j=low[i]; j<=up[i]; j++ ) {
            sh = sum;
            rh = r;
            
            for( k=i; k<a.m && j < up[k]; k++ )
                sh -= up[k] - j;
            for( k=i; k>=0 && j > low[k]; k-- ) {
                sh -= j - low[k];
                rh -= j - low[k];
            }

            if( rh >= 0 && rh <= sh ) {
                if( a.least[i] > j )
                    a.least[i] = j;
                if( a.most[i] < j )
                    a.most[i] = j;
            }
        }//for
    }//if

}

int get_most( product &a, char *w ) {
    int i;
    for( i=0; i<a.m; i++ )
        if( strcmp( a.name[i], w ) == 0 )
            return a.most[i];
    return 0;
}

int get_least( product &a, char *w ) {
    int i;
    for( i=0; i<a.m; i++ )
        if( strcmp( a.name[i], w ) == 0 )
            return a.least[i];
    return 0;
}
void query_most( char *w ) {
    int i, l = -1, t;
    bool key = false;
    for( i=0; i<n; i++ ) {
        t = get_least( p[i], w );
        if( t > l )
            l = t;
    }

    for( i=0; i<n; i++ )
        if( get_most( p[i], w ) >= l ) {
            if( key ) printf( " " );
            printf( "%s", p[i].w );
            key = true;
        }
    printf( "n" );
}
        
void query_least( char *w ) {
    int i, l = 200, t;
    bool key = false;
    for( i=0; i<n; i++ ) {
        t = get_most( p[i], w );
        if( t < l )
            l = t;
    }

    for( i=0; i<n; i++ )
        if( get_least( p[i], w ) <= l ) {
            if( key ) printf( " " );
            printf( "%s", p[i].w );
            key = true;
        }
    printf( "n" );
}

bool input( ) {
    int i, j;
    char c;
    scanf( "%d", &n );
    if( n <= 0 )
        return false;

    for( i=0; i<n; i++ ) {
        scanf( "%s", p[i].w );
        scanf( "%d", &p[i].m );
        for( j=0; j<p[i].m; j++ ) {
            scanf( "%s", p[i].name[j] );
            c = getchar();
            if( c != 'n' )
                scanf( "%d%%", &p[i].per[j] );
            else
                p[i].per[j] = -1;
        }
    }

    for( i=0; i<n; i++ )
        clac( p[i] );
    return true;
}

int main( ) {
    int t;
    char w1[100], w2[100];
    while( input( ) ) {
        scanf( "%d", & t );
        while( t-- ) {
            scanf( "%s %s", w1, w2 );
            if( w1[0] == 'm' )
                query_most( w2 );
            else
                query_least( w2 );
        }
    }

    return 0;
}
							

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

#include "stdio.h"
#include "math.h"
#include "memory.h"
#include "algorithm"
using namespace std;
#define y1 sdgdsf
double clac( double h0, double h1, double x0, double x1 ) {
    return h0/(h0-h1)*( x1 - x0 ) + x0;
}
double sum[5048];
struct node {
    double x;
    int id;
}x[1024];
int a_to[1024], b_to[1024];
bool cmp( node a, node b ) {
    if( a.x == b.x )
        return a.id > b.id;
    return a.x < b.x;
}
int covers[2048];
void modify( int l, int r, int a, int b, int k, int key ) {
    int c = (l+r)/2, k1 = k*2+1, k2 = k*2+2;
    if( a >= r || b <= l || r-l<=0  )
        return;
    if( a<=l && r<=b ) {
        covers[ k ] += key;        
        if( covers[ k ] == 0 )
            sum[ k ] = sum[ k1 ] + sum[ k2 ];
        else
            sum[ k ] = x[r].x - x[l].x;
        return;
    }
    if( c - l > 0 )
        modify( l, c, a, b, k1, key );
    if( r - c > 0 )
        modify( c, r, a, b, k2, key );
    if( covers[ k ] == 0 )
            sum[ k ] = sum[ k1 ] + sum[ k2 ];
    return;
}
int n;
double x1[510], y1[510], x2[510], y2[510], h[510], lh;
double xl, xr, yu, yd, xx, yy;
struct rect {
    int id;
    double y;
    bool in;
}r[1100];
bool cmp_rect( rect a, rect b ) {
    return a.y < b.y;
}
inline void jia( double &c, double a, double b ) {
    if( c < a ) c = a;
    if( c > b ) c = b;
}
void input( ) {
    int i;
    scanf( "%d", &n );
    scanf( "%lf %lf %lf %lf", &xl, &yu, &xr, &yd );
    scanf( "%lf %lf %lf", &xx, &yy, &lh );

    for( i=0; i<n; i++ ) {
        scanf( "%lf %lf %lf %lf %lf", &x1[i], &y1[i], &x2[i], &y2[i], &h[i] );
        
        x1[i] = clac( lh, h[i], xx, x1[i] );
        jia( x1[i], xl, xr );

        x2[i] = clac( lh, h[i], xx, x2[i] );
        jia( x2[i], xl, xr );
        
        y1[i] = clac( lh, h[i], yy, y1[i] );
        jia( y1[i], yu, yd );

        y2[i] = clac( lh, h[i], yy, y2[i] );
        jia( y2[i], yu, yd );
        
        x[i*2].x = x1[i];
        x[i*2].id = i+1;
        x[i*2+1].x = x2[i];
        x[i*2+1].id = -(i+1);

        r[i*2].id = i;
        r[i*2].y = y1[i];
        r[i*2].in = true;

        r[i*2+1].id = i;
        r[i*2+1].y = y2[i];
        r[i*2+1].in = false;
    }
    sort( x, x+2*n, cmp );
    for( i=0; i<2*n; i++ ) {
        if( x[i].id >= 0 )
            a_to[ x[i].id-1 ] = i;
        else
            b_to[ -x[i].id-1 ] = i;
    }
    sort( r, r+2*n, cmp_rect );
    memset( covers, 0, sizeof covers );
    for( i=0; i<5048; i++ )
        sum[i] = 0;

}
double doit( ) {
    double ans = 0;
    int i, a, b;

    for( i=0; i<2*n; i++ ) {

        if( i )
            ans += sum[0] * ( r[i].y - r[i-1].y );
        a = a_to[ r[i].id ];
        b = b_to[ r[i].id ];

        modify( 0, n*2-1, a, b, 0, r[i].in?1:-1 );
    }
    return ans;
}
int main( ) {
    input( );
    printf( "%.4lfn", (xr-xl)*(yd-yu) - doit( ) );
    return 0;
}


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
 public static void main(String args[]) throws Exception {
    
    Scanner cin=new Scanner(System.in);
    BigInteger n;
    long b;
    while(cin.hasNext())
    {
        n=cin.nextBigInteger();
        b=cin.nextLong();
        if(n.compareTo(BigInteger.ZERO)<=0)
        {
            System.out.println("0");
            continue;
        }
        BigInteger ans;
        ans=n.multiply(n.add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
        ans=ans.multiply(BigInteger.valueOf(b));
        //how many [0..b-1]
        BigInteger cnt=n.divide(BigInteger.valueOf(b));
        ans=ans.add(BigInteger.valueOf(b*(b-1)/2).multiply(cnt));
        cnt=cnt.multiply(BigInteger.valueOf(b));
        while(cnt.compareTo(n)<=0)
        {
            BigInteger tmp=BigInteger.ZERO,tsum=cnt;
            while(tsum.compareTo(BigInteger.ZERO)>0)
            {
                tmp=tmp.add(tsum.mod(BigInteger.valueOf(b)));
                tsum=tsum.divide(BigInteger.valueOf(b));
            }
             tmp=(BigInteger.valueOf(b).subtract(tmp.mod(BigInteger.valueOf(b)))).mod(BigInteger.valueOf(b));
            cnt=cnt.add(BigInteger.ONE);
            ans=ans.add(tmp);
        }
        System.out.println(ans);
    }
  }
}
							

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

    import java.util.*;  
    import java.math.*;  
      
    public class Main {  
      
        public static void main(String[] args)   
        {  
            Scanner cin = new Scanner(System.in);  
            int num = Integer.valueOf(cin.nextLine()).intValue();  
             
           for(int i = 0; i < num; i++)  
           {  
               String[] str = cin.nextLine().split(" ");  
     
               BigDecimal a = new BigDecimal(str[0]);  
               BigDecimal b = new BigDecimal(str[1]);  
                 
               BigDecimal result = a.add(b);  
               System.out.println(result.toPlainString());  
          }  
     
       }  
     
   }  

							

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

/* @author: */
import java.util.Scanner;   
public class Main {   
   static int a[][]=new int[10001][2];
   static int b[][]=new int[10001][2];
   static int an,bn;

   static void sort(){
    int i,j,t1,t2;
    for(i=0;i< an;i++)
        for(j=0;j< an;j++)
        {
            if(a[i][0]< a[j][0])
            {
                t1=a[i][0];t2=a[i][1];
                a[i][0]=a[j][0];a[i][1]=a[j][1];
                a[j][0]=t1;a[j][1]=t2;   
            }    
        }    
    for(i=0;i< bn;i++)
        for(j=0;j< bn;j++)
        {
            if(b[i][1]>b[j][1])
            {
                t1=b[i][0];t2=b[i][1];
                b[i][0]=b[j][0];b[i][1]=b[j][1];
                b[j][0]=t1;b[j][1]=t2;   
            }    
        }   
    }    

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int i,j,cn,t1,t2,l1,l2,sum1,sum2;
    while(sc.hasNext()){
        cn=sc.nextInt();
        if(cn==0) break;
        an=0;bn=0;
        for(i=0;i< cn;i++)
        {
            t1=sc.nextInt();
            t2=sc.nextInt();
            if(t1<=t2)
            {
                a[an][0]=t1;a[an][1]=t2;
                an++;
            }    
            else
            {
                b[bn][0]=t1;b[bn][1]=t2;
                bn++;
            }
        }    
        sort();
        for(i=0;i< bn;i++)
        {
            a[an][0]=b[i][0];a[an][1]=b[i][1];
            an++;
        }        
        l1=l2=0;sum1=sum2=0;
  
        for(i=0;i< an;i++)
        {
            sum1+=a[i][0];
            if(sum1>sum2)sum2=sum1;
            sum2+=a[i][1];
        }    
        System.out.printf("%dn",sum2);
    }    
  }
}    

							

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

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


const int SIZE = ( 1<<18 );
const int LEAF = ( 1<<17) - 1;

int sum[SIZE],l_max[SIZE],r_max[SIZE],l_min[SIZE], r_min[SIZE], min_e[SIZE], 
    s_max[SIZE], s_min[SIZE], pn, n;

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

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

void modify( int c ) {
    int c1 = c*2+1, c2 = c*2+2;
    sum[c] = sum[c1] + sum[c2];
    l_max[c] = max( l_max[c1], sum[c1]+l_max[c2] );
    r_max[c] = max( r_max[c2], sum[c2]+r_max[c1] );
    l_min[c] = min( l_min[c1], sum[c1]+l_min[c2] );
    r_min[c] = min( r_min[c2], sum[c2]+r_min[c1] );
    s_max[c] = max( max( s_max[c1], s_max[c2] ), r_max[c1]+l_max[c2] );
    s_min[c] = min( min( s_min[c1], s_min[c2] ), r_min[c1]+l_min[c2] );
    min_e[c] = min( min_e[c1], min_e[c2] );
}

void modify_leaf( int c, int v ) {
    sum[c] = v;
    s_max[c] = l_max[c] = r_max[c] = max( 0, sum[c] );
    s_min[c] = l_min[c] = r_min[c] = min( 0, sum[c] );
    min_e[c] = ( c < LEAF+n ? sum[c] : 999999 );
}

void creat( int l, int r, int c ) {
    if( c >= LEAF ) {
        modify_leaf( c, sum[c] ); 
    }
    else {
        creat( l, (l+r)/2, c*2+1 );
        creat( (l+r)/2+1, r, c*2+2 );
        modify( c );
    }
}

int k, v;
void change( int l, int r, int c ) {
    int h = (l+r)/2;
    if( l == r ) {
        if( sum[c] > 0 && v <= 0 )
            pn--;
        else if( sum[c]<=0 && v > 0 )
            pn++;
        modify_leaf( c, v );
    }
    else if( k <= h ) {
        change( l, h, c*2+1 );
        modify( c );
    }
    else {
        change( h+1, r, c*2+2 );
        modify( c );
    }
}

void init() {
    int i;

    memset( sum, 0, sizeof sum );
    pn = 0;

    scanf( "%d", &n );
    for( i=LEAF; i<LEAF+n; i++ ) {
        scanf( "%d", sum+i );
        if( sum[i] > 0 )
            pn++;
    }
    creat( 0, LEAF, 0 );
}

int get_ans( ) {
    if( pn == n )
        return sum[0] - min_e[0];
    return max( s_max[0], sum[0]-s_min[0] );
}

int main( ) {
    int m;

    init( );
    scanf( "%d", &m );

    while( m-- ) {
        scanf( "%d %d", &k, &v );
        k--;
        change( 0, LEAF, 0 );
        printf( "%dn", get_ans( ) );
    }    

    return 0;
}
							

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

#include "stdio.h"
#include "memory.h"
#include "vector"
#include "algorithm"
#include "functional"
#include "math.h"
#define max asdfds
using namespace std;


const int SIZE = 700;
typedef pair<int,int> pair_int;

int sign[SIZE*2], MS;
pair_int e[SIZE*2][SIZE*2], _e[SIZE*2][SIZE*2];
int en[SIZE*2], _en[SIZE*2];

int n;

void init( ) {
    int i;
    MS = 0;
    for( i=0; i<n*2; i++ ) {
        en[i] = 0;
        _en[i] = 0;
    }
}

inline void insert( int u1, int u2, bool f1, bool f2, int v ) {
    // u1^f1 + u2^f2 = 1
    // with value v;
    int u10 = u1+f1*n, u11 = u1+(!f1)*n, u20 = u2+f2*n, u21 = u2+(!f2)*n;
    e[ u11 ][ en[u11]++ ] = pair_int( v, u20 );
    e[ u21 ][ en[u21]++ ] = pair_int( v, u10 );
    _e[ u20 ][ _en[u20]++ ] = pair_int( v, u11 );
    _e[ u10 ][ _en[u10]++ ] = pair_int( v, u21 );
}

void sort_edge( ) {
    int i;
    for( i=0; i<n*2; i++ ) {
        sort( e[i], e[i]+en[i], greater<pair_int>() );
        sort( _e[i], _e[i]+_en[i], greater<pair_int>() );
    }
}

int st[ SIZE*2 ] = { 0 }, sn;
int max, A, B, temp;

void search1( int k ) {
    int i;
    sign[k] = MS;
    for( i=0; i<en[k] && e[k][i].first>max; i++ ) {
        if( sign[ e[k][i].second ] < MS )
            search1( e[k][i].second );
        }
    st[ sn++ ] = k;
}

bool search2( int k ) {
    int i;

    if( sign[(k+n)%(2*n)] == MS )
        return true;

    sign[k] = MS;
    for( i=0; i<_en[k] && _e[k][i].first>max; i++ )
        if( sign[ _e[k][i].second ] <= temp ) {
            if( search2( _e[k][i].second ) )
                return true;
        }

    return false;
}

bool check( int ans ) {
    MS++;
    max = ans;
    sn = 0;

    int i;
    for( i=0; i<2*n; i++ )
        if( sign[i] < MS )
            search1( i );
    
    temp = MS;
    while( sn-- ) {
        if( sign[ st[sn] ] <= temp ) {
            MS ++;
            if( search2( st[sn] ) )
                return false;
        }
    }

    return true;
}

int sx[2], sy[2], s01;
int x[1000], y[1000];
int longest;

void input( ) {
    int a, b, i, j, l[2][2];
    scanf( "%d%d%d", &n, &A, &B );

    init( );    

    scanf( "%d%d%d%d", &sx[0], &sy[0], &sx[1], &sy[1] );
    s01 = abs( sx[0] - sx[1] ) + abs( sy[0] - sy[1] );

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

    for( i=0; i<A; i++ ) {
        scanf( "%d%d", &a, &b );
        a--, b--;
        insert( a, b, 0, 0, 1000000000 );
        insert( a, b, 1, 1, 1000000000 );
    }

    for( i=0; i<B; i++ ) {
        scanf( "%d%d", &a, &b );
        a--, b--;
        insert( a, b, 1, 0, 1000000000 );
        insert( a, b, 0, 1, 1000000000 );
    }
    longest = 0;
    for( i=0; i<n; i++ ) {
        l[0][0] = abs( x[i] - sx[0] ) + abs( y[i] - sy[0] );
        l[0][1] = abs( x[i] - sx[1] ) + abs( y[i] - sy[1] );

        if( l[0][0] > longest )
            longest = l[0][0];
        if( l[0][1] > longest )
            longest = l[0][1];

        for( j=i+1; j<n; j++ ) {
            l[1][0] = abs( x[j] - sx[0] ) + abs( y[j] - sy[0] );
            l[1][1] = abs( x[j] - sx[1] ) + abs( y[j] - sy[1] );
            insert( i, j, 1, 1, l[0][0]+l[1][0] );
            insert( i, j, 0, 0, l[0][1]+l[1][1] );
            insert( i, j, 1, 0, l[0][0]+l[1][1]+s01 );
            insert( i, j, 0, 1, l[0][1]+l[1][0]+s01 );
        }
    }
    sort_edge( );

}

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

    input( );

    a = longest; b = longest*2 + s01;

    if( !check( b ) ) {
        printf( "-1n" );
        return 0;
    }

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

    printf( "%dn", b );

    return 0;
}


							

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

import java.io.*;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int[] fb=new int[75000];
  fb[0]=1;
  fb[1]=1;
  for(int i=2;i< 75000;i++)
      fb[i]=(3*fb[i-1]-fb[i-2]+200000)%100000;
  while((a--)!=0)
  {
   int b=Integer.parseInt(in.readLine());
   System.out.println(fb[b%75000]);
  }
 }
}
							

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

/* @author: */
import java.util.Scanner;   
public class Main {   
   
 public static void main(String[] args) {   
 Scanner sc = new Scanner(System.in);   
    double b,v,e,f,t[]=new double[101],t1;
    int n,a[]=new int[101],r;
    int i,j,k,dis;
    while(sc.hasNext())
    {
        n=sc.nextInt();
        if(n==0) break;

        a[0]=0;
        for(i=1;i<=n;i++)
           a[i]=sc.nextInt();
        
        b=sc.nextDouble();
        r=sc.nextInt();
        v=sc.nextDouble();
        e=sc.nextDouble();
        f=sc.nextDouble();

        t[0]=0; 
        for(i=0;i< n;i++)
        {
            if(i==0)t1=0;else t1=b;
            for(j=i+1;j<=n;j++)
            {
                for(k=a[j-1];k< a[j];k++)
                {
                    dis=k-a[i];
                    if(dis>=r) t1+=1/(v-e*(dis-r));
                    else t1+=1/(v-f*(r-dis));
                }    
                if(i==0||t1+t[i]< t[j])t[j]=t[i]+t1;
            }    
        }      
        System.out.printf("%.4fn",t[n]);
    }    
   }
}    
							

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

import java.util.*;
 public class Main{
   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
      int n=1;
      while(true){
        n=sc.nextInt();
        if(n==0) break;
       System.out.println(test2(n));
      }
      
   }

   /*
    * Sum of Consecutive Prime Numbers 
    */  
  public static int test2(int x){ 
      int count=0; 
      for(int i=2;i+i< x;i++){
           int sum = 0;
           if(!isPrime(i)){
              continue; 
          }
           for(int j=i;j< x;j++){
              // �ж��Ƿ�Ϊ����
              if(!isPrime(j)) 
                 continue;
              sum = sum+j; 
             // �ж��Ƿ��������
              if(sum>=x){
                  if(sum==x){ 
                    count++;
                  } 
                 break;
              }
           } 
      } 
      if(isPrime(x))
           count++;
       return count;
    }

   /*
    * �ж�ij�����Ƿ�Ϊ��������Ƿ���true
    */ 

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

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

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

public class Main {
 static final int M = 2,N = 1000+2;
 static int value[] = new int[N];
 static int map[][][] = new int[N][N][M],n;
 public static int Get_Num(StreamTokenizer cin) throws Exception{
    cin.nextToken();
    return (int) cin.nval;
 }

 public static void main(String []args) throws Exception{
        
  int i,k=1;
        
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
    n = Get_Num(cin);
    if(n==0) break;
        
    for(i=1;i<=n;++i) value[i] = Get_Num(cin);
        
System.out.println("In game "+k+", the greedy strategy might lose by as many as "+solve()+" points.");
    ++k;
  }
}

 public static void init_map(){
    int i,j;
    for(i=0;i<=n;++i) for(j=0;j<=n;++j){
        map[i][j][0] = map[i][j][1] = -1;
    }
  }

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

 public static int get_ans(int left,int right,int p){
  if(map[left][right][p]!=-1)
    return map[left][right][p];
  if(left==right){
    if(p==1) return map[left][right][p] = value[left];
    return map[left][right][p] = 0;
  }
  if(p==1){
return map[left][right][p] = max(get_ans(left,right-1,1-p)+value[right],get_ans(left+1,right,1-p)+value[left]);
  }else{
return map[left][right][p] = (value[right]>value[left]?get_ans(left,right-1,1-p):get_ans(left+1,right,1-p));
 }
}

 public static int solve(){
    int i,k=0;
    init_map();
    for(i=1;i<=n;++i) k+=value[i];
    return get_ans(1,n,1)*2-k;
  }
}

							

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
class Node{
    int x,y,z;
}
public class Main {
    static int []mark=new int[1010];
    static double []dis=new double[1010];
    static int []from=new int [1010];
    static double sumup,sumdown;
    static double [][]up=new double [1010][1010];
    static double [][]down=new double [1010][1010];
    static double [][]map=new double [1010][1010];
    static double dist(double x1,double y1,double x2,double y2)
    {
        return Math.sqrt((double)(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    }
    static void prim(int n)
    {
        Arrays.fill(mark, 0);
        mark[1]=1;dis[1]=0;
        sumup=sumdown=0;
        for (int i=2;i<=n;i++) {
            dis[i]=map[1][i];
            from[i]=1;
        }
        for (int i=1;i< n;i++) {
            double min=1e100;
            int sit=0;
            for (int j=1;j<=n;j++) if (mark[j]==0&&dis[j]< min) {
                min=dis[j];
                sit=j;
            }
            mark[sit]=1;
            sumup+=up[sit][from[sit]];
            sumdown+=down[sit][from[sit]];
            for (int j=1;j<=n;j++) if (mark[j]==0&&dis[j]>map[sit][j]) {
                dis[j]=map[sit][j];
                from[j]=sit;
            }
        }
    }
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        Node []a=new Node[1010];
        while (true) {
            int n=in.nextInt();
            if (n==0) break;
            for (int i=1;i<=n;i++) {
                a[i]=new Node();
                a[i].x=in.nextInt();
                a[i].y=in.nextInt();
                a[i].z=in.nextInt();
            }
            double mid=30;
            for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) {
                up[i][j]=up[j][i]=Math.abs(a[i].z-a[j].z);
                down[i][j]=down[j][i]=dist(a[i].x,a[i].y,a[j].x,a[j].y);
            }
            double lastmid=30;
            while (true) {
                for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) {
                    map[j][i]=map[i][j]=up[i][j]-mid*down[i][j];
                }
                prim(n);
                mid=sumup/sumdown;
                if (Math.abs(mid-lastmid)< 0.001) break;
                lastmid=mid;
            }
            System.out.printf("%.3fn",mid);
        }
    }
}

							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
    int a=Integer.parseInt(in.readLine());
    if(a==0) break;
    my[] p=new my[a];
    for(int i=0;i< a;i++)
    {
    String[] ss=in.readLine().split(" ");
    p[i]=new my(Integer.parseInt(ss[0]),Integer.parseInt(ss[1]));
    }
    Arrays.sort(p);
    int cnt=0;
    for(int i=1,n=0;i< a;i++)
    {
    if(p[n].a==p[i].a){
        cnt++;
        n=i;
    }
    else if(p[n].b<=p[i].b) cnt++;
    else n=i;
     }
     System.out.println(a-cnt);
    }
  }    
}
class my implements Comparable< my>
{
    int a,b;
    public my(int x,int y)
    {
        a=x;
        b=y;
    }
    public int compareTo(my o) {
        if(a==o.a)return o.b-b;
        return a-o.a;
    }
}

							

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

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


#define null 0
const int size = 2010;
bool e[size][size];

int maxmatch( int n, int m, bool w[][size], int *p)
{

    int p_n[size];
    int p_m[size];

    bool sign[size];
    int q[size],from[size],s,t;

    int i,j,link,now,h;

    memset( p_n, -1, sizeof(int)*n );
    memset( p_m, -1, sizeof(int)*m );

    for(i=0;i<n;i++)
    if(p_n[i]==-1)
    {
        memset( sign, 0, sizeof(bool)*m );
                
        s=1;link=-1;
        from[0]=-1;

        q[0]=size-1;
        p_m[size-1]=i;

        for(t=0;t<s;t++)
        {
           now=q[t];
           for(j=0;j<m;j++)
           {
               if( w[p_m[now]][j] != null && sign[j]==0 )
               {
                    sign[j]=1;
                    q[s]=j;
                    from[s++]=t;

                    if(p_m[j]==-1)
                    {
                        link=s-1;
                        break;
                    }
               }
           }
           if(j<m)break;
        }

        if(t<s)
        {
             while(from[link]!=-1)
             {
                    h=from[link];
                    p_m[q[link]]=p_m[q[h]];
                    p_n[p_m[q[h]]]=q[link];
                    link=h;
             }
        }

    }
    int an;

    for(i=0,an=0;i<n;i++)
    {
        if(p)p[i]=p_n[i];
        if(p_n[i]>=0)an++;
    }
    return an;
}

char s[2010][11];

int check( char *a, char *b ) {
    int i;
    for( i=0; a[i] && a[i] == b[i]; i++ )
        ;
    if( !a[i] )
        return 2;
    for( i++; a[i] && a[i] == b[i]; i++ )
        ;
    return !a[i];
}

int h;

void add( char *w, int key ) {
    int k;

    for( k=0; k<h; k++ )
        if( check( s[k], w ) == 2 )
            return;

    for( k=0; k<h; k++ )
        if( check( s[k], w ) ) {
            if( key )
                e[k][h] = 1;
            else
                e[h][k] = 1;
        }

    if( k == h )
        strcpy( s[h++], w );
}

int main() {
    int n, m, i, k, c;
    char *cp;
    char w[11];

    while( scanf("%d%d", &m, &n ) == 2 && n >0 && m > 0 ) {
        h = 0;
        memset( e, 0, sizeof e );

        for( i=0; i<n; i++ ) {
            scanf( "%s", w );

            c = 0;
            for( k=0; w[k]; k++ )
                if( w[k]=='1' )
                    c++;

            cp = strchr( w, '*' );
            if( cp ) {
                *cp = '0';
                add( w, c%2 );
                *cp = '1';
                add( w, (c+1)%2 );
            }
            else {
                add( w, c%2 );
            }
        }
        printf( "%dn", h-maxmatch( h, h, e, 0 ) );
    }
    return 0;
}
							

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

/* @author: */
import java.util.Scanner;   
public class Main {   
   
 public static void main(String[] args) {   
 Scanner sc = new Scanner(System.in);   
 
    double angle,p,a,b,c,t,l,xa,xb,ya,yb,k1,k2,x1,x2,y1,y2,l2;
    int n,i;
    while(sc.hasNext())
    {
        n=sc.nextInt();
        if(n==0) break;
        xa=sc.nextDouble();
        ya=sc.nextDouble();
        xb=sc.nextDouble();
        yb=sc.nextDouble();
        l=l2=0;
        for(i=0;i< n;i++)
        {
         t=sc.nextDouble();
         l+=t;
         l2+=t*t/2;
         }    
        k1=ya/xa;k2=yb/xb;
        x1=l*(1+k2)/(k1-k2);x2=l*(1+k1)/(k1-k2);
        y1=k1*x1;y2=k2*x2;
        a=Math.sqrt(x1*x1+y1*y1);b=Math.sqrt(x2*x2+y2*y2);c=Math.sqrt(2)*l;
        p=0.5*(a+b+c);
        System.out.printf("%5.3fn",Math.sqrt(p*(p-a)*(p-b)*(p-c))-l2);
    }
  }
}    
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
   private int a,b;
   private double f1,f2,f3,f4,f5,f6,t1,t2,t3,t4,t5,t6;

   public Main(int a,int b){
    this.a=a;
    this.b=b;
    f1=13-a+1;f2=13-b+1;f3=1;
    t1=13;t2=13;t3=a+b;
    f4=1;f5=1;f6=26-(a+b)+1;
    t4=a;t5=b;t6=26;
   }

  

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  while(sc.hasNext()){
    int a=sc.nextInt();
    int b=sc.nextInt();
    if(a< 0) break;
    
    Main m=new Main(a,b);
    System.out.printf("%d-%d split: %10.8fn",a,b,m.doIt());
  }   
 }

 private int check()
  {
    if(f1<=t1||f2<=t2||f3<=t3||f4<=t4||f5<=t5||f6<=t6)return 1;
    return 0;
  }    
      
 public double doIt(){
        double x=1;
        while(check()!=0)
        {
            if(f1<=t1){x*=f1;f1++;}
            if(f2<=t2){x*=f2;f2++;}
            if(f3<=t3){x*=f3;f3++;}
            if(f4<=t4){x/=f4;f4++;}
            if(f5<=t5){x/=f5;f5++;}
            if(f6<=t6){x/=f6;f6++;}    
        }    
        if(a!=b)x*=2;
       return x;
    }    
}    
							

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

import java.util.Scanner;

public class Main{

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   while(true) {
    String str = cin.nextLine();
    char c = str.charAt(0);
    int re = 0;
    if(c == '0')
     break;
    int size = str.length();
    for(int i=0; i< size; i++) {
     c = str.charAt(i);
     if(c -'4' > 0)
      c -= 1;
     re = (int) (re + (c-'0') * Math.pow(9, size-1-i));
    }
    System.out.println(str + ": " +re);
   }
  
}

}


							

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

#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:    
    typedef int type;            // ��Ȩ����
    enum { size = 810 };        // �����ģ
    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;
}

/****************************************************************************/
char map[20][25];
char at[20][25];
int n, m, d, begin, end, total;
ff mf;

void init()
{
    int i, j, k, l;
    scanf( "%d %d", &n, &d );
    
    for( i=0; i<n; i++ )
        scanf( "%s", map[i] );
    for( i=0; i<n; i++ )
        scanf( "%s", at[i] );
        
     m = strlen( map[0] );
     
     mf.init();
     
     for( i=0; i<n; i++ )
     for( j=0; j<m; j++ )
        if( map[i][j] > '0' )
            mf.insert_edge( i*m+j, i*m+j+n*m, map[i][j] -'0' );
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    if( map[i][j] >'0' )
    for( k=(i-d>0)?i-d:0; k<=i+d&&k<n; k++ )
    for( l=(j-d>0)?j-d:0; l<=j+d&&l<m; l++ )
        if( map[k][l] > '0' && abs( i-k ) + abs( j-l ) <= d )
            mf.insert_edge( i*m+j+n*m, k*m+l, map[k][l] - '0' );

    begin = n*m*2;
    end = n*m*2+1;
    total = 0;
    
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
        if( at[i][j] == 'L' )
        {
              mf.insert_edge( begin, i*m+j, 1 );
              total++;
        }          
            
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    if( map[i][j] > '0' )        
          if( i-d<0 || i+d >= n || j-d<0 || j+d >= m )
            mf.insert_edge( i*m+j+n*m, end, map[i][j] - '0' );
}

int main()
{
    int cas, ans, i;
    
    scanf( "%d", &cas );
    
    for( i=1; i<=cas; i++ )
    {
        init();
        ans = total - mf.maxflow( n*m*2+2, begin, end );
        
        printf( "Case #%d: ", i );
        
        if( ans == 0 )
            printf( "no lizard was left behind.n" );
        else if( ans == 1 )
            printf( "1 lizard was left behind.n" );
        else
              printf( "%d lizards were left behind.n", ans );
     }             
    return 0;
}


							

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

//* @author: ccQ.SuperSupper
import java.util.*;
import java.math.*;
public class Main {
 public static void main(String []args) throws Exception{
        
 int t,cs=1,left,right,i,j;
 BigInteger a,b,seven;
 String str1,str2;
        
 seven = BigInteger.valueOf(1);
 for(i=0;i< 10000;++i)
    seven = seven.multiply(BigInteger.valueOf(7));
        
 Scanner cin = new Scanner(System.in);
        
 t = cin.nextInt();
 while(t--!=0){
    str1 = cin.next();
    str2 = cin.next();
    left = cin.nextInt();
    right = cin.nextInt();
    
    a = new BigInteger(str1);
    a = a.multiply(seven);
    a = a.divide(new BigInteger(str2));
            
    b = new BigInteger(str1);
    b = b.divide(new BigInteger(str2));
    b = b.multiply(seven);
    
    a = a.subtract(b);
    a = a.add(seven);
System.out.print("Problem set "+cs+": "+str1+" / "+str2+", base 7 digits "+left+" through "+right+": ");
    System.out.println(a.toString(7).substring(left+1, right+2));
    ++cs;
  }
 }
}

							

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

//* @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 a,b,c,d;
        int z,nz;
        while (true){
            a=scanner.nextInt();
            b=scanner.nextInt();
            c=scanner.nextInt();
            d=scanner.nextInt();
            if (a+b+c+d==0){
                break;
            }
            if (a*d>b*c){
                z=getN(a,c);
            }
            else{
                z=getN(b,d);
            }
            if (a*c>b*d){
                nz=getN(a,d);
            }
            else{
                nz=getN(b,c);
            }
            if (z< nz){
                if (nz>100){
                    nz=100;
                }
                System.out.println(nz+"%");
            }
            else{
                if (z>100){
                    z=100;
                }
                System.out.println(z+"%");
            }
        }
    }

    public static int getN(int a,int c){
        return 100*c/a;
    }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[][] p;
 static int a;
 static long[][] w;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
    a=Integer.parseInt(in.readLine());
    if(a==-1) break;
    p=new int[a][a];
    w=new long[a][a];
    w[0][0]=1;
    for(int i=0;i< a; i++)
    {
    for(int j=0;j< a; j++)
        p[i][j]=in.read()-'0';
    in.readLine();
    }
    for(int j=0;j< a;j++)
    if(p[0][j]+j< a) w[0][p[0][j]+j]+=w[0][j];
    for(int i=1;i< a;i++)
    {
    for(int j=0;j< a;j++)
        if(p[i-1][j]+i-1< a) w[p[i-1][j]+i-1][j]+=w[i-1][j];
    for(int j=0;j< a-1;j++)
        if(p[i][j]+j< a) w[i][p[i][j]+j]+=w[i][j];    
     }
     System.out.println(w[a-1][a-1]);
   }
  }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int k=in.nextInt();
  while((k--)!=0)
  {
    int[] arr=new int[9];
    for(int i=0;i< 9;i++)
    arr[i]=in.nextInt();
    int[] y=new int[arr[8]+1];
    y[0]=arr[0];
    y[1]=arr[1];
    y[2]=arr[2];
    for(int i=3;i<=arr[8];i++)
     f(y,i,arr);
    System.out.println(y[arr[8]]);
   }
 }


  public static void f(int[] y,int n,int[] arr)
  {
   int u=0;
   if(n%2==1){
     u=arr[3]*y[n-1]+arr[4]*y[n-2]-arr[5]*y[n-3];
     u=(u%arr[6]+arr[6])%arr[6];
    }
    else
    {
    u=arr[5]*y[n-1]-arr[3]*y[n-2]+arr[4]*y[n-3];
    u=(u%arr[7]+arr[7])%arr[7];
     }
  y[n]=u;
 }
}
							

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

 import java.util.Scanner;

 public class Main {

     final static int MAXVALUE = (int) Math.sqrt(Integer.MAX_VALUE) + 1;

     public static void main(String[] args) {
         int k, l, u, tt, index;
         boolean hasFlg;
         int a, b, aa, bb;
         int[] num = new int[MAXVALUE];
         boolean[] frimeflg = new boolean[MAXVALUE];
         boolean[] flg;
         index = 1;
         // 鏋勯€犱竴涓皬绱犳暟琛?
         for (int i = 2; i < MAXVALUE; i++) {
             if (!frimeflg[i]) {
                 k = i * 2;
                 num[index++] = i;
                 while (k < MAXVALUE) {
                     frimeflg[k] = true;
                     k += i;
                 }
             }
         }
         Scanner scan = new Scanner(System.in);
         while (scan.hasNextInt()) {
             l = scan.nextInt();
             u = scan.nextInt();
             tt = (int) Math.sqrt(u);
             // 鏋勯€犱竴涓猽-l+1鐨勫尯闂?
             flg = new boolean[u - l + 1];
             // 绛涢€夊尯闂达紝涓嶆槸绱犳暟鐨勬爣璁颁负true
             for (int i = 1; i < index && i <= tt; i++) {
                 k = Math.max(num[i], l / num[i]);
                 if (k * num[i] < l || k <= 1) {
                     k++;
                 }
                 if (k <= 1) {
                     k++;
                 }
                 while ((long) k * num[i] <= u) {
                     flg[k * num[i] - l] = true;
                     k++;
                 }
             }
             hasFlg = false;
             a = 0;
             b = Integer.MAX_VALUE;
             aa = 0;
             bb = 0;
             if (l == 1) {
                 flg[0] = true;
             }
             for (int i = 0; i < u - l + 1; i++) {
                 if (!flg[i]) {
                     for (int j = i + 1; j <= u - l; j++) {
                         if (!flg[j]) {
                             if (b - a > j - i) {
                                 a = i + l;
                                 b = j + l;
                             }
                             if (bb - aa < j - i) {
                                 bb = j + l;
                                 aa = i + l;
                             }
                             hasFlg = true;
                             break;
                         }
                     }
                 }
             }
             if (hasFlg) {
                 System.out.printf(
                         "%d,%d are closest, %d,%d are most distant.n", a, b,
                         aa, bb);
             } else {
                 System.out.println("There are no adjacent primes.");
             }
         }
     } 
}

							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 * poj2685  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            scan.nextLine();   
            for (int i = 0; i < n; i++) {   
                String[] ss = scan.nextLine().trim().split(" ");   
                char[] a = ss[0].toCharArray();   
                char[] b = ss[1].toCharArray();   
                int[] va = {0, 0, 0, 0};   
                int[] vb = {0, 0, 0, 0};   
                int[] vc = new int[4];   
                for (int j = 0; j < a.length; j++) {   
                    if (a[j] - '0' <= 9 && a[j] - '0' >= 2) {   
                        j++;   
                        va[getIndex(a[j])] = a[j - 1] - '0';   
                    } else {   
                        va[getIndex(a[j])] = 1;   
                    }   
                }   
                for (int j = 0; j < b.length; j++) {   
                    if (b[j] - '0' <= 9 && b[j] - '0' >= 2) {   
                        j++;   
                        vb[getIndex(b[j])] = b[j - 1] - '0';   
                    } else {   
                        vb[getIndex(b[j])] = 1;   
                    }   
                }   
                for (int j = vc.length - 1; j >= 0; j--) {   
                    vc[j] = vc[j] + va[j] + vb[j];   
                    if (vc[j] >= 10) {   
                        vc[j] = vc[j] - 10;   
                        if (j - 1 >= 0) {   
                            vc[j - 1] = vc[j - 1] + 1;   
                        }   
                    }   
                }   
                print(vc);   
            }   
        }   
    }   
  
    static void print(int[] c) {   
        for (int i = 0; i < c.length; i++) {   
            if (c[i] == 0) {   
                continue;   
            }   
            if (c[i] == 1) {   
                System.out.print(""+getChar(i));   
            } else {   
                System.out.print(c[i]+(getChar(i)+""));   
            }   
        }   
        System.out.println();   
    }   
  
    static int getIndex(char c) {   
        switch (c) {   
            case 'm':   
                return 0;   
            case 'c':   
                return 1;   
            case 'x':   
                return 2;   
            case 'i':   
                return 3;   
            default:   
                return -1;   
        }   
    }   
  
    static char getChar(int i) {   
        switch (i) {   
            case 0:   
                return 'm';   
            case 1:   
                return 'c';   
            case 2:   
                return 'x';   
            case 3:   
                return 'i';   
            default:   
                return '0';   
        }   
    }   
}  
 


							

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

//* @author: 82638882@163.com
import java.util.Scanner;
class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  in.nextLine();
  int u=0;
  while((a--)!=0)
  {
    u++;
    int[] p=new int[26];
    String s1=in.nextLine();
    String s2=in.nextLine();
    for(int i=0;i< s1.length();i++)
    {
        int t=s1.charAt(i)-'a';
        p[t]++;
    }
    for(int i=0;i< s2.length();i++)
    {
        int t=s2.charAt(i)-'a';
        p[t]--;
    }
    int cnt=0;
    for(int i=0;i< 26;i++)
        cnt+=Math.abs(p[i]);
    System.out.println("Case #"+u+":  "+cnt+" ");
   }
 }
}
							

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

import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    public static void main(String[] args)
    {
        int n;
        BigInteger two,ans;
        Scanner cin = new Scanner (System.in);
        while(cin.hasNext())
        {
            n = cin.nextInt();
            two = BigInteger.valueOf(2);
            ans = two;
            if(n%2==0)
            {
                ans=ans.pow(n-1).subtract(two).divide(BigInteger.valueOf(3)).add(BigInteger.ONE);
            }
            else
            {
                ans=ans.pow(n-1).subtract(BigInteger.ONE).divide(BigInteger.valueOf(3));
            }
            System.out.println(ans);
        }
    }
}
							

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

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

using namespace std;
const int size = 1110;

struct edge
{
    int len;
    int fee;
    edge *next;
};

edge e[size][size];
edge *link[size];
bool sign[size];
int m, n, begin, end;
int fee[size];

void search( int b )
{
    int a;
    sign[b] = true;
    for( a=0; a<n; a++ )
        if( !sign[a] && e[a][b].fee == fee[a] )
            search( a );
}


bool init( )
{
    int i, j, u, v, f1, f2, l;
    if( scanf( "%d %d %d %d", &n, &m, &begin, &end ) != 4 )
        return false;

    for( i=0; i<n; i++ )
    {
        fee[i] = 800;
        for( j=0; j<n; j++ )
            e[i][j].fee = 999;
    }

    char c[10];
    
    for( i=0; i<m; i++ )
    {
        scanf( "%1s", c );
        scanf( "%d,%d,%d[%d]%d)", &u, &v, &f1, &l, &f2 );

        if( e[u][v].fee > f1 || ( e[u][v].fee == f1 && e[u][v].len > l ) )
        {
            e[u][v].fee = f1, e[u][v].len = l;
            if( fee[u] > f1 ) fee[u] = f1;
        }

        if( e[v][u].fee > f2 || ( e[v][u].fee == f2 && e[v][u].len > l ) )
        {
            e[v][u].fee = f2, e[v][u].len = l;
            if( fee[v] > f2 ) fee[v] = f2;
        }
    }

    memset( link, 0, sizeof link );

    for( i=0; i<n; i++ )
    {
        for( j=0; j<n; j++ )
            if( e[i][j].fee == fee[i] )
            {
                e[i][j].next = link[i];
                link[i] = &e[i][j];
            }
    }

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

    return true;
}

int dis[size];
int len[size];
bool flag[size];

int dijstra( )
{
    int i, j, k, t;
    edge *p;

    memset( flag, 0, sizeof flag );
    for( i=0; i<n; i++ )
        len[i] = 999999;

    len[begin] = 0;
    for( i=0; i<n; i++ )
    {
        k = end;
        for( j=0; j<n; j++ )
            if( sign[j] && !flag[j] && len[j] < len[k] )
                k = j;
        
        if( k == end )
            return len[k];

        flag[k] = true;
        
        for( p=link[k]; p; p=p->next )
        {
            j = p-e[k];
            if( dis[j] - dis[k] == p->fee && len[j] > ( t = len[k] + p->len ) )
                len[j] = t;
        }
    }

    return 0;
}


void doit( )
{
    int i, j, t, l;
    edge *p;

    if( !sign[begin] )
    {
        printf( "VOIDn" );
        return;
    }

    for( i=0; i<n; i++ )
        dis[i] = 999999;

    dis[begin] = 0;

    for( i=0; i<n-1; i++ )
    {
        for( j=0; j<n; j++ )
        if( sign[j] )
        {
            for( p = link[j]; p; p=p->next )
            if( ( t = dis[j] + p->fee ) < dis[ l=p-e[j] ] )
                dis[l] = t;
        }
    }

    for( j=0; j<n; j++ )
    if( sign[j] )
    {
        for( p = link[j]; p; p=p->next )
        if( sign[ l=p-e[j] ] && dis[j]+p->fee < dis[l] )
            break;

        if( p ) break;
    }

    if( p )
    {
        printf( "UNBOUNDn" );
        return;
    }

    printf( "%d %dn", dis[end], dijstra() );
}
    

int main( )
{
    while( init( ) )
        doit( );

    return 0;
}


							

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

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

const double eps=1e-8;
const int size = 1010;
////////////////////////////////
typedef double Type;/*????????*/
////////////////////////////////
struct point
{
    Type x,y;
    point(){x=y=0;}
    point(Type x,Type y):x(x),y(y){;}
    bool operator==(point &a){return x==a.x&&y==a.y;}
};
//????
inline Type 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 Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}
inline Type 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 dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct line
{
    point a,b;
    line(){;}
    line(point &x,point &y):a(x),b(y){;}
};
point crosspoint(line l1,line l2)
{
    Type p1=cheng(l2.a,l1.a,l2.b),
         p2=cheng(l2.a,l2.b,l1.b);
    if(p1+p2==0)return l1.a;

    point c;
    c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
    c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
    return c;
}
int jiao(line l1,line l2)
{
    Type s1=cheng(l1.a,l1.b,l2.a),
    s2=cheng(l1.a,l1.b,l2.b),s3,s4;

    if((double)s1*s2>0)return 0;

    s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);

    if((double)s3*s4>0)return 0;

    if((double)s1*s2<0&&(double)s3*s4<0)return 1;

    if( dcheng(l1.a,l2.a,l2.b)<=0
      ||dcheng(l1.b,l2.a,l2.b)<=0
      ||dcheng(l2.a,l1.a,l1.b)<=0
      ||dcheng(l2.b,l1.a,l1.b)<=0)
    return 2;

    return 0;

}
int in(point *p,int n,point judge)
{
    int c,j,k;point up,low,temp; 

    c=0;j=0;

    while(p[j].y==judge.y)j++;

    for(;j<n;j=k)
    { 
        k=j+1;

        while(p[k%n].y==judge.y&&p[k%n].x>judge.x) k++;

        up=p[j];
        low=p[k%n];

        if(up.y<low.y){    temp=up;up=low;low=temp; }

        if(up.y<judge.y||low.y>judge.y)continue;

        if(cheng(low,up,judge)<=0&&k==j+1)continue;

        c++;
    }

    if(c%2)return 1;
    else return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////
int in_line( point c, point a, point b )
{
    return cheng( c, a, b ) == 0 &&    dcheng( c, a, b ) < 0;
}
point ploy[310][310];
int n, pn[310], m;

point p[size];
double e[size][size];
int st[size], sn;
void init( )
{
    int i, j, k, l, k1, k2;
    bool key;
    line ln, ln2;
    point c, d;    
    for( i=0; i<size; i++ )
    for( j=0; j<size; j++ )
        e[i][j] = 1e100;
    scanf( "%d %lf %lf %lf %lf", &n, &p[0].x, &p[0].y, &p[1].x, &p[1].y ); 
    k = 2;
    for( i=0; i<n; i++ )
    {
        scanf( "%d", &pn[i] );
        for( j=0; j<pn[i]; j++ )
        {
            scanf( "%lf %lf", &ploy[i][j].x, &ploy[i][j].y );
            p[k++] = ploy[i][j];
        }
        ploy[i][j] = ploy[i][0];
    }
    m = k;    
    for( i=0; i<m; i++ )
    for( j=i+1; j<m; j++ )
    {
        ln.a = p[i];
        ln.b = p[j];
        key = true;

        for( k=0; k<n; k++ )
        {
            for( l=0; l<pn[k]; l++ )
                if( jiao( ln, line( ploy[k][l], ploy[k][l+1] ) ) == 1 )
                        break;
            if( l< pn[k] )
            {    key = false;    break; }
        }
        if( key )
        {
            for( l=0; l<m; l++ )
                if( in_line( p[l], p[i], p[j] ) )
                    break;
            if( l < m )
            {    key = false; }
        }
        if( key )
        {
            c.x = (p[i].x+p[j].x)/2;
            c.y = (p[i].y+p[j].y)/2;
            for( k=0; k<n; k++ )
            {
                for( l=0; l<pn[k]; l++ )
                    if( in_line( c, ploy[k][l], ploy[k][l+1]  ) )
                            break;
                if( l == pn[k] && in( ploy[k], pn[k], c ) )
                {    key = false;    break;    }
            }
        }

        if( key )
            e[i][j] = e[j][i] = dis( p[i], p[j] );
    }
    k = m;
    for( k1=0; k1<n; k1++ )
    for( k2=k1+1; k2<n; k2++ )
    {
        for( i=0; i<pn[k1]; i++ )
        {
            sn = 0;
            for( j=0; j<pn[k2]; j++ )
            {
                ln.a = ploy[k1][i];
                ln.b = ploy[k1][i+1];

                ln2.a = ploy[k2][j];
                ln2.b = ploy[k2][j+1];

                if( jiao( ln, ln2 ) == 1 )
                {
                    st[sn++] = k;
                    p[k++] = crosspoint( ln, ln2 );
                }
            }

            int a;
            st[sn] = st[0];
            for( a=0; a<sn; a++ )
                e[st[a]][st[a+1]] = e[st[a+1]][st[a]] = dis( p[st[a]], p[st[a+2]] );
        }
    }
    m = k;
    for( i=0; i<m; i++ )
    for( j=i+1; j<m; j++ )
        if( dis( p[i], p[j] ) < 1e-5 )
            e[i][j] = e[j][i] = 0;

}
double dist[size];
bool sign[size];
void dijstra()
{
    int i, j, k, n = ::m;
    double temp;
    for( i=1; i<n; i++ )
        dist[i] = 1e100;
    dist[0] = 0;
    memset( sign, 0, sizeof sign );
    for( i=0; i<n; i++ )
    {
        k = 1;
        for( j=0; j<n; j++ )
            if( !sign[j] && dist[k] > dist[j] )
                k = j;
        if( k == 1 )
            return ;

        sign[ k ] = true;

        for( j=0; j<n; j++ )
        {
            if( ( temp = dist[k] + e[k][j] ) < dist[j] )
                dist[j] = temp;
        }
    }

    return;
}
int main( )
{
    int cas;
    scanf( "%d", &cas );
    while( cas-- )
    {
        init( );
        dijstra( );

        if( dist[1] < 1e99 )
            printf( "%.3lfn", dist[1] );
        else
            printf( "-1n" );
    }

    return 0;
}


							

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

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

struct point
{
    double x, y;
};
double dis( point &a, point &b )
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double s[1010][1010];
point p[1010];
int main( )
{
    int n, i, j;
    double t, ans;
    while( scanf( "%d", &n ) == 1 )
    {
    
        for( i=1; i<=n; i++ )
            scanf( "%lf %lf", &p[i].x, &p[i].y );
        p[0].x = p[1].x;
        p[0].y = p[1].y;
        n++;
        for( i=0; i<n; i++ )
        for( j=i+1; j<n; j++ )
            s[i][j] = -1;
        s[0][1] = 0;
        for( i=0; i<n-1; i++ )
        for( j=i+1; j<n-1; j++ )
        {
            t = s[i][j] + dis( p[i], p[j+1] );
            if( s[j][j+1] == -1 || t < s[j][j+1] )
                s[j][j+1] = t;

            t = s[i][j] + dis( p[j], p[j+1] );
            if( s[i][j+1] == -1 || t < s[i][j+1] )
                s[i][j+1] = t;
        }
        ans = 1e100;
        for( i=0; i<n-1; i++ )
            if( ans > ( t = s[i][n-1] + dis( p[i], p[n-1] ) ) )
                ans = t;
        printf( "%.2lfn", ans );
    }
    return 0;
}
							

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

//* @author: 82638882@163.com
import java.io.*;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int cnt=Integer.parseInt(in.readLine());
  while((cnt--)!=0)
  {
   int[][] p=new int[9][9];
   for(int i=0;i< 9;i++)
   {
    for(int j=0;j< 9;j++)
          p[i][j]=in.read()-'0';
        in.readLine();
   }
   uu(0,0,p);
   for(int i=0;i< 9;i++)
   {
     for(int j=0;j< 9;j++)
    System.out.print(p[i][j]);
     System.out.println();
    }
   }
  }

  public static boolean uu(int a,int b,int[][] p)
  {
   if(b>8)
    {
    a++;
    b=0;
    if(a>8) return true;
    }
    if(p[a][b]!=0)return uu(a,b+1,p);
    int[] uu=new int[10];
    for(int k=0;k< 9;k++)
    {
    uu[p[a][k]]++;
    uu[p[k][b]]++;
    }
    int w=a/3,t=b/3;
    for(int k=w*3;k< w*3+3;k++)
    for(int h=t*3;h< t*3+3;h++)
       uu[p[k][h]]++;
    for(int k=1;k< 10;k++)
    {
    if(uu[k]!=0) continue;
    p[a][b]=k;
    if(uu(a,b+1,p)) return true;
    }
    p[a][b]=0;
    return false;
   }
}
							

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

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
const double eps = 1e-6;
using namespace std;
double v[70000];
int id[70000], s[70000], l[70000];
bool cmp( int a, int b )
{
    return v[a]*l[b] < v[b]*l[a];
}
int main( )
{
    int i, n, a;
    while( scanf( "%d", &n ) == 1 )
    {
        for( i=0; i<n; i++ )
        {
            scanf( "%d%d%lf", id+i, l+i, v+i ); 
            s[i] = i;
        }
        sort( s, s+n, cmp );
        scanf( "%d", &a );
        printf( "%dn", id[ s[n-a] ] );
    }
    return 0;
}


							

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

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

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 
 int total,per,t,max;
 total=sc.nextInt();
 per=sc.nextInt();
 t=sc.nextInt();
 max=total;
 while((t--)!=0)
 {
   int dis,speed,fir,sum;
   dis=sc.nextInt();
   speed=sc.nextInt();
   if(speed==0) continue;
   if(speed>=dis) max=0;
   fir=dis/speed;
   if(dis%speed==0) fir--;
   sum=fir+(total-fir)/2;
   if(sum< max) max=sum;
  }
  System.out.printf("%d",max*per);
 }
}
							

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

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



//�����ͼ���ƥ�䣬

//����ƥ�����wΪn*m�ڽӾ���,p������X( |X|=n )ƥ��Ķ�����

#define null 0

const int size=30;

 

 

bool maxmatch(int n,int m,bool w[][size],int *p)
{

       int p_n[size];

       int p_m[size];

       bool sign[size];

       int q[size],from[size],s,t;

 

       int i,j,link,now,h;

      

 

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

       for(j=0;j<m;j++)p_m[j]=-1;

 

       for(i=0;i<n;i++)

       if(p_n[i]==-1)

       {

              for(j=0;j<m;j++)sign[j]=0;

                           

              s=1;link=-1;

 

              from[0]=-1;

              q[0]=size-1;

              p_m[size-1]=i;

             

              for(t=0;t<s;t++)

              {

                     now=q[t];

                     for(j=0;j<m;j++)

                     {

                            if(w[p_m[now]][j]!=null&&sign[j]==0)

                            {

                                   sign[j]=1;
                                   q[s]=j;
                                   from[s++]=t;
                                  if(p_m[j]==-1)

                                   {

                                          link=s-1;
                                          break;

                                   }
                            }
                     }                 
                     if(j<m)break;
              }
              if(t<s)
              {
                     while(from[link]!=-1)
                     {
                            h=from[link];
                            p_m[q[link]]=p_m[q[h]];                        
                            p_n[p_m[q[h]]]=q[link];

                            link=h;

                     } 

              }
                else return false;
       }

    return true;
       
}
bool e[10010][26];
bool w[26][30];
int sib[10010], child[10010];
int m;
char word[100];
void creat( int root )
{
    int c = -1;
    char *p;
    while( 1 )
    {
        gets( word );
        if( word[0] == '>' )
            return;
        if( word[0] == '<' )
            creat( c );
        else
        {
            if( c != -1 )
                sib[c] = m;
            else child[root] = m;
            
            sib[m] = -1;
            child[m] = -1;
            c = m;

            memset( e[m], 0, sizeof(bool)*26 );

            for( p = strtok( word, " nt" ); p; p = strtok( NULL, " nt" ) )
                e[m][ *p-'A' ] = true;
            m++;
        }
    }
}
bool search( int root )
{
    int i, j, k, n, c;
    bool key;
    for( i=0, c = child[root]; c != -1 && i < 26; c = sib[c], i++ )
        if( !search( c ) )return false;    
    if( i >= 26 )
        return false;
    if( i == 0 )
        return true;
    for( i=0, c = child[root]; c != -1 && i < 26; c = sib[c], i++ )
        for( j=0; j<26; j++ )
            w[i][j] = e[c][j];
    n = i;
    for( j=0; j<26; j++ )
        w[n][j] = 0;

    key = false;
    for( k=0; k<26; k++ )
    {
        if( e[root][k] )
        {
            w[n][k] = 1;
            e[root][k] = maxmatch( n+1, 26, w, 0 );
            if( e[root][k] )
                key = true;
            w[n][k] = 0;
        }
    }
    return key;
}
int main( )
{
    int i, c, j;
    
    child[ 0 ] = -1;
    gets( word );    
    m = 1;
    creat( 0 );
    for( i=0, c = child[0]; c!=-1; c = sib[c], i++ )
    {
        if( !search( c ) )
            break;
        for( j=0; j<26; j++ )
            w[i][j] = e[c][j];
    }
    if( c != -1 || i > 26 || !maxmatch( i, 26, w, 0 ) )
        printf( "No Solutionn" );
    else
        printf( "Got It!n" );
    return 0;
}
							

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

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
double dis[100][100];
int n, m;
bool e[100][100];
int son[100];
double len[100];
bool sign [100];
int v2[100], v[100], vn2, vn;
int calc2( int a, int f )
{
    int i, s, j;
    
    for( s=1,i=0, j=0; i<m; i++ )
    if( i!=f && e[a][i] )
    {
        s = ( s*calc2( i, a ) ) % 2005;
        j++;
    }

    while( j )
    {
        s = (s*j)%2005;
        j--;
    }

    return s;
}
void calc( )
{
    int i, j, k;
    double t, ans, s;    
    memset( e, 0, sizeof(e) );        
    m = n;
    ans = 0;
    vn = n;
    for( i=0; i<vn; i++ )
    {
        v[i] = i;
        son[i] = i;
        len[i] = 0;
    }
    while( vn > 1 )
    {
        if( vn == 2 )
        {
            e[ v[0] ][ v[1] ] = e[ v[1] ][ v[0] ] = 1;
            ans += dis[ v[0] ][ v[1] ];
            break;
        }
        vn2 = 0;
        for( i=0; i<vn; i++ )
        {
            s = 10000000;
            for( j=0; j<vn; j++ )
            if( j != i )
            for( k=j+1; k<vn; k++ )
            if( k != i )
            {
                if( s > ( t = (dis[v[j]][v[i]]+dis[v[i]][v[k]]-dis[v[j]][v[k]])/2 ) )
                    s = t;
            }
            if( s == 0 )
            {
                v2[ vn2++ ] = v[i];
                sign[ v[i] ] = 1;
            }
            else
            {
                v2[ vn2++ ] = m;
                sign[m] = 1;
                len[ m ] = s + len[v[i]];
                son[ m ] = son[v[i]];
                e[m][v[i]] = e[v[i]][m] = 1;                
                ans += s;                
                m++;
            }
        }
        int temp;
        temp = vn;
        vn = 0;
        for( i=0; i<vn2; i++ )
        if( sign[ v2[i] ] )
        {
            for( j=i+1; j<vn2; j++ )
            if( sign[ v2[j] ] )
            {
                dis[v2[j]][v2[i]] = dis[v2[i]][v2[j]] = dis[ son[v2[i]] ][ son[v2[j]] ] - len[ v2[i] ] - len[ v2[j] ];
                if( dis[v2[i]][v2[j]] == 0 )
                {
                    for( k=0; k<m; k++ )
                        if( e[ v2[j] ][ k ] )
                        {
                            e[ v2[j] ][ k ] = e[ k ][ v2[j] ] = 0;
                            e[ v2[i] ][ k ] = e[ k ][ v2[i] ] = 1;
                        }
                    sign[ v2[j] ] = 0;
                }
            }
            v[ vn++ ] = v2[i];
        }
        if( vn >= temp )
            while( printf( "ft!" ) );
    }
    int temp = calc2( 0, -1 );
    printf( "%.0f %dn", ans*2, temp  );
}
int main()
{
    int i, j;    
    while( 1 )
    {
        scanf( "%d", &n );

        if( n == 0 ) break;

        for( i=0; i<n; i++ )
        {
            for( j=0; j<n; j++ )
                scanf( "%lf", &dis[i][j] );
        }
        calc();
    }
    return 0;
}


							

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

//* @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 s,n,tn;
    while (true){
        s=scanner.nextInt();
        n=scanner.nextInt();
        if (s==0&&n==0){
            break;
        }
        tn=s+1;
        for (int i=0;i< n ;i++ ){
                   tn=tn+scanner.nextInt()-scanner.nextInt()-1;
        }
        System.out.println(tn);
    }
  }
}


							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   int a=in.nextInt();
   if(a==0) break;
   boolean bb=true;
   int b=in.nextInt();
   HashSet< Integer> hs=new HashSet< Integer>();
   while((a--)!=0) hs.add(in.nextInt());
   while((b--)!=0)
   {
    int c=in.nextInt();
    int d=in.nextInt();
    int cnt=0;
    while((c--)!=0)
    {
          int u=in.nextInt();
      if(hs.contains(u))cnt++;
    }
    if(cnt< d) bb=false;    
     }
     if(bb) System.out.println("yes");
     else System.out.println("no");    
    }
  }
}
							

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

import java.util.Scanner;
import java.util.Arrays;
public class Main{

  static long S(int n) //S(n)=3*S(n-2)+2*(S(n-4)+S(n-6)+...+S(2)+S(0))
{
    long s;
    int i;
    if(n==0)return 1;
     else
    {
        s=3*S(n-2);
        for(i=n-4;i>=0;i-=2)
        {
            s+=2*S(i);
        }
        return s;
    }
}

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);  
    int n;
    n=sc.nextInt();
    while(n>=0) 
    { 
        if(n%2!=0) System.out.printf("0n");
        else if(n==0) System.out.printf("1n");
        else System.out.printf("%dn",S(n));    
        n=sc.nextInt();
    } 
  }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
    int a=in.nextInt();
    if(a==0) break;
    a-=1960;
    a/=10;
    a=(int)Math.pow(2, a+2);
    double k=0;
    int n=2;
    while(k< a)
    {
          k+=Math.log(n)/Math.log(2);
      n++;
    }
    System.out.println(n-2);
   }
 }
}
							

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

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

static double lfabs(double x)
{
    return x>0?x:-x;
}    

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  double sat[][]=new double[100][3];
  double xa,xb,ya,yb,za,zb,s,s1,s2,s3,angle,r=20000/3.14159265;
  int k,m,i,j,flag=0,num;
    while(sc.hasNext())
    {
       k=sc.nextInt();
       m=sc.nextInt();
       if(k==0&&m==0) break;
        num=0;
        for(i=0;i< k;i++){
          sat[i][0]=sc.nextDouble();
          sat[i][1]=sc.nextDouble();
          sat[i][2]=sc.nextDouble();
        }
        for(i=0;i< m;i++)
        {
            flag=0;
            xb=sc.nextDouble();
            yb=sc.nextDouble();
            zb=sc.nextDouble();
            for(j=0;j< k;j++)
            {
                xa=sat[j][0];ya=sat[j][1];za=sat[j][2];
                s1=Math.sqrt(xa*xa+ya*ya+za*za);
                s2=Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
                if(s2<=Math.sqrt(s1*s1-r*r)){flag=1;break;}
            }    
            if(flag!=0)num++;
        }    
        System.out.printf("%dn",num);
    }    
  }
}    
							

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

 import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         int caseNum = 0;  
         int unhappyDay, unhappyValue;  
         int studyTime = 0;  
           
         while(true)  
         {  
             unhappyDay = 0;  
             unhappyValue = 0;  
             caseNum = cin.nextInt();  
           
             if(caseNum == 0)  
                 break;  
             else  
             {  
                 int[][] time = new int[caseNum][2];  
                 for(int i = 0; i < caseNum; i++)  
                 {     
                     for(int j = 0; j < 2; j++)  
                         time[i][j] = cin.nextInt();  
                       
                     studyTime = time[i][0] + time[i][1];  
                     if(studyTime > 8)  
                     {  
                         if(studyTime > unhappyValue)  
                         {  
                             unhappyValue = studyTime;  
                             unhappyDay = i + 1;  
                         }  
                     }  
   
                 }  
                 System.out.println(unhappyDay);   
             }  
         }  
     } 
}

							

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

//* @author:
import java.util.*;
public class Main {
  static double t=0;
  static double e( double s, int k) {
   if( k == 0 )
    return s;
   else {
     double temp = e( 2*s, k-1 );
     double h = s/temp;
     if( t > h )
    return temp*(1-t*t)/2/(1-t);
     else
    return (s*(h-t)+temp*(1-h*h)/2)/(1-t);
    }
}

 static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   while(sc.hasNext()) {
       int n=sc.nextInt();
       t=sc.nextDouble();
       if(n==0) break;
       System.out.printf( "%.3fn", e( 1, n) );
   }
 }
}

							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        Hashtable< Integer,Integer> table=new Hashtable< Integer,Integer>();
        Hashtable< Integer,Integer> table2=new Hashtable< Integer,Integer>();
               BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        int k=0;
        int n=0;
        int x,c=0,r,temp;
        boolean band;
        ArrayList< Integer> v=new ArrayList< Integer>();
        StringTokenizer t;
       while(stdin.ready()){
           t=new StringTokenizer(stdin.readLine());
            n=new Integer(t.nextToken());
            k=new Integer(t.nextToken());
            table.clear();
            table2.clear();
            v.clear();
            band=true;
            x=k;
            if(x!=0)
            {while(x%2==0){
                x/=2;table.put(2, table.get(2)==null?1:table.get(2)+1);
            }
            c=3;
            while(c<=(Math.sqrt((double)x)+1)){
                if(x%c==0){
                    x/=c;
                    table.put(c, table.get(c)==null?1:table.get(c)+1);
                } else c+=2;
            }
            if(x>1)table.put(x, table.get(x)==null?1:table.get(x)+1);
            }
            
            band=true;
            v=new ArrayList(table.keySet());
            if(k!=0&&n!=0&&k>n)
            for(int i=0;i< v.size();i++){
                c=table.get(v.get(i));

                x=0;
                r=0;
                while(x< c){
                    r++;
                    temp=r*v.get(i);
                    if(temp>n){
                        band=false;
                        break;
                    }
                    if(table2.get(temp)==null){
                        table2.put(temp,temp);
                    }
                    while(table2.get(temp)%v.get(i)==0){
                        table2.put(temp, table2.get(temp)/v.get(i));
                        x++;
                        if(x==c)break;
                    }
                }
                if(!band) break;
            }
            if(n==0&&k!=1) band=false;           
            if(band&&k!=0)System.out.println(k+" divides "+n+"!");
            else System.out.println(k+" does not divide "+n+"!");
        }
    }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   int a=in.nextInt();
   if(a==0) break;
   double[] d=new double[a];
   double total=0;
   for(int i=0;i< a;i++)
   {
    d[i]=in.nextDouble();
    total+=d[i];
   }
   double avg=total/a;
   long t=Math.round(avg*100);
   avg=(double)t/100;
   double d1=0,d2=0;
   for(int i=0;i< a;i++)
   {
    if(d[i]>avg)d1+=d[i]-avg;
    else d2+=avg-d[i];
   }
   System.out.printf("$%.2fn",Math.min(d1, d2));
  }
 }
}
							

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

//* @author:
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
  static public void main( String [] string ) throws Exception{
   Scanner cin = new Scanner( System.in );
   long p, q;
   while( true ) {
    p = cin.nextLong();
    q = cin.nextLong();
    if( p == 0 && q == 0 )
    break;
    if( p == 0 ) {
    System.out.println( "0 2" );
    continue;
    }
    long s, i, j, sum=2;
    boolean key = false;
    for( i=1; i<=50000 && !key; i++ ) {
    if( sum*q%p == 0 ){
      s = sum*q/p;
      j = (long)Math.sqrt( s );
      if( j+1 > 50000 )
        break;
      if( j*(j+1) == s ) {
        System.out.println( (i+1) + " " + (j-i) );
        key = true;
        break;
       }
    }
    sum += 2*i+2;
     }
     if( !key )
    System.out.println( "impossible" );
    }
    return;
   }
}


							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    String[] ss1=new String[n];
    String[] ss2=new String[n];
    int[] p=new int[n];
    in.nextLine();
    for(int i=0;i< n;i++)
    {
      ss1[i]=in.nextLine();
      ss2[i]=in.nextLine();
    }
    int m=in.nextInt();
    in.nextLine();
    String s;
    for(int i=0;i< m;i++)
    {
       s=in.nextLine();
       for(int j=0;j< n;j++)
       {
         if(s.equals(ss1[j]))
        {
           p[j]++;
           break;
         }
       }
    }
    int max=0,tag=-1;;
    boolean bb=false;
    for(int i=0;i< n;i++)
    {
       if(p[i]>max){
        max=p[i];
        bb=false;
        tag=i;
        }
        else if(p[i]==max)bb=true;
    }
    if(bb) System.out.println("tie");
    else System.out.println(ss2[tag]);
   }
}
							

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

//* @author:
import java.util.*;
public class Main {
 static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   while( sc.hasNext())
   {
     int a=sc.nextInt();
     int b=sc.nextInt();
     int s=sc.nextInt();
     int m=sc.nextInt();
     int n=sc.nextInt();
     if( a == 0 )
    break;
     double x = b*n;
     double y = a*m;
     System.out.printf( "%.2f %.2fn", Math.atan2( x, y )/Math.acos(-1)*180, Math.sqrt( x*x + y*y ) / s );
     }
    
    }
}