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

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

bool sign[25000];

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


int key;

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

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

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

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



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

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

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

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

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

    key = 1;
    doit( n );

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

    key = 2;
    doit( n );

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

    printf( "%dn", ans );

    return 0;
}
							

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

    printf( "%dn", count );

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

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

    return 0;
}
							

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

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

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

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

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

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

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

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

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

							

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

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

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

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

}

							

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

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

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

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


							

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

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

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

int n;

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

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



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

                m = 0;

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

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




							

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

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


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

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

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

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

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

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




							

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

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

int has_one[1<<16];

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

int a[16];

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

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

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

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

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

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



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

    int id[8];

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

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

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

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

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

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

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

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

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

        clac_result( );

        clac_ans( );

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



							

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

//* @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 p[]=new int[101];
    int i,j,n,s,t,m,id,t1,t2,sum,sid,tot,cas=0;;
    while (true) {
       s=sc.nextInt();t=sc.nextInt();m=sc.nextInt();
        if (s==0&&t==0&&m==0) break;
        for (i=1;i<=100;i++) p[i]=0;sum=0;cas++;
        for (i=1;i<=s;i++) {
          id=sc.nextInt();
          t1=sc.nextInt();
          t2=sc.nextInt();
          if (p[id]==0) { sum+=t1+t2;p[id]=1;}
         }
        for (i=1;i<=100;i++) p[i]=0;
        for (i=1;i<=t;i++) {
         sid=sc.nextInt();
         tot=sc.nextInt();
         if (p[sid]==0&&tot>=m) { sum++;p[sid]=1;}
        }        
        System.out.printf("Case %d: %dn",cas,sum);
    }
  }
}
							

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

#include <stdio.h>



bool sign[1010];
int a[20];
int ans, best;

int search( int k, int big ) {
    int b = 1000, t, temp, sb;
    
    if( a[k] == ans ) {
        best = k;
        return 0;
    }

    if( k >= best )
        return 1000;
    
    int i;
    for( i=k, sb=big; sb<ans; sb<<=1, i++ )
        ;
    if( i >= best )
        return 1000;

    for( int i=k; i>=k && i>=0; i-- )
    for( int j=i; j>=0; j-- ) {
        if( a[i]+a[j] <= ans && !sign[ a[i]+a[j] ] ) {
            a[k+1] = a[i]+a[j];
        
            sign[ a[k+1] ] = true;
            
            sb = big;
            if( sb < a[k+1] )
                sb = a[k+1];
                
            t = search( k+1, sb );
            if( t < b ) b = t;
            sign[ a[k+1] ] = false;
        }
    }
    
    for( int i=k; i>=k && i>=0; i-- )
    for( int j=i-1; j>=0; j-- ) {
        if( a[i] > a[j] )
            temp = a[i]-a[j];
        else
            temp = a[j]-a[i];
        
        if( !sign[ temp ] ) {
            a[k+1] = temp;
            
            sb = big;
            if( sb < a[k+1] )
                sb = a[k+1];
                
            sign[ temp ] = true;
            t = search( k+1, sb );
            if( t < b ) b = t;
            sign[ temp ] = false;
        }
    }
    return b+1;
}

int main( ) {
    int n, i;

    while( scanf( "%d", &n ) == 1 && n ) {

        for( i=0; i<=n; i++ )
            sign[i] = false;
        ans = n;
        best = 13;
        a[0] = 1;
        search( 0, 1 );
        printf( "%dn", best );
    }
    return 0;
}
    

							

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

//* @author:
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static ArrayList< Integer> primes = Prime.getPrimes(1120);

    public static void main(String[] args) {
        int[][] f = new int[1140][1140];
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        f[0][0] = 1;
        for (int j = 0; j < primes.size(); j++) {
        for (int i = 14; i >= 1; i--) {
               for (int v = 1120; v > 0; v--) {
                    if (v - primes.get(j) >= 0) {
                        f[i][v] += f[i - 1][v - primes.get(j)];
                    }
                }
            }
        }
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int k = scan.nextInt();
            if (n == 0 && k == 0) {
                break;
            }
            System.out.println(f[k][n]);
        }
    }
}

class Prime {

    public static ArrayList getPrimes(int n) {
        int i, j, k, x, num;
        n++;
        n /= 2;
        int[] b = new int[(n + 1) * 2];
        ArrayList a = new ArrayList();
        a.add(0, 2);
        a.add(1, 3);
        num = 2;
        for (i = 1; i <= 2 * n; i++) {
            b[i] = 0;
        }
        for (i = 3; i <= n; i += 3) {
            for (j = 0; j < 2; j++) {
                x = 2 * (i + j) - 1;
                while (b[x] == 0) {
                    a.add(num++, x);
                    for (k = x; k <= 2 * n; k += x) {
                        b[k] = 1;
                    }
                }
            }
        }
        return a;
    }
}
							

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

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

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);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.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;
}

bool check( point p[], int n ) {
    int i, j, ii, jj, k;
    point o;
    line l;
    for( i=0; i<n; i++ ) {
        ii = (i+1)%n;
        l.a = p[i]; l.b = p[ii];
        for( j=i+1; j<n; j++ ) {
            jj = (j+1)%n;
            if( (p[i].x-p[ii].x)*(p[j].y-p[jj].y) != (p[i].y-p[ii].y)*(p[j].x-p[jj].x) ) {
                o = crosspoint( l, line( p[j], p[jj] ) );
                for( k=0; k<n; k++ )
                    if( cheng( p[k], o, p[(k+1)%n] ) > 1e-7 )
                        break;
                if( k >= n )
                    return true;
            }
        }
    }
    return false;
}



point p[100];

int main( ) {
    int i, n;
    while( true ) {
        scanf( "%d", &n );
        if( n == 0 ) break;

        for( i=0; i<n; i++ )
            scanf( "%lf%lf", &p[i].x, &p[i].y );
        
        printf( "%dn", check( p, n ) );
    }
    return 0;
}


							

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

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


struct point {
    double x, y, z;
};

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

point p[500], q[50];
double r[50];

int main( ) {
    int i, j, n, m, counter;
    double t;
    while( scanf( "%d", &n ) == 1 && n ) {
        for( i=0; i<n; i++ )
            scanf( "%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z );
        scanf( "%d", &m );
        for( i=0; i<m; i++ )
            scanf( "%lf%lf%lf%lf", &q[i].x, &q[i].y, &q[i].z, &r[i] );

        counter = 0;
        for( i=0; i<n; i++ ) {
            t = dcheng(p[i],p[i]);
            for( j=0; j<m; j++ ) {
                if( acos( dcheng( p[i], q[j] )/sqrt(t*dcheng(q[j],q[j])) ) < r[j] )
                    break;
            }
            if( j < m )
                counter++;
        }
        printf( "%dn", counter );
    }
    return 0;
}
							

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

/* @author: */
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
 
  int t, i, c, j;
  char w[]=new char[100];
  boolean s[]=new boolean[100];
  int ans[]=new int[100];
  t=sc.nextInt();
  while(( t-- )!=0) {
     w=sc.next().toCharArray();
     for( i=0; i< 26; i++ ) {
      s[i] = false;
      w[i]-='A';
      ans[i+1] = 0;
     }

     for( i=0; i< 26; i++ ) {
    if( !s[i] ) {
       s[i] = true;
       for( j=w[i], c=1; j!=i; j=w[j], c++ )
        s[j] = true;
       if( (c&1)==0 )
        ans[c]++;
    }
     }
     for( i=2; i<=26; i++ )
    if( (ans[i] & 1)!=0 )
       break;
    System.out.printf( "%sn", i<=26?"No":"Yes" );
   }
  }
}


							

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

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
public class Main {   
  
    static boolean[] isPrime = Prime.getPrimes(10000);   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        int cas = scan.nextInt();   
        for (int i = 1; i <= cas; i++) {   
            int start = scan.nextInt();   
            int end = scan.nextInt();   
            boolean[] isVisited = new boolean[10000];   
            int[] step = new int[10000];   
            LinkedList<Integer> queue = new LinkedList();   
            queue.addLast(start);   
            isVisited[start] = true;   
            while (!queue.isEmpty()) {   
                int current = queue.pop();   
                if (current == end) {   
                    break;   
                }   
                for (int j = 0; j <= 9; j++) {   
                    int next1 = getNext(1, j, current);   
                    int next2 = getNext(2, j, current);   
                    int next3 = getNext(3, j, current);   
                    int next4 = getNext(4, j, current);   
                    if (!isVisited[next1]) {   
                        queue.addLast(next1);   
                        step[next1] = step[current] + 1;   
                        isVisited[next1] = true;   
                    }   
                    if (!isVisited[next2]) {   
                        queue.addLast(next2);   
                        step[next2] = step[current] + 1;   
                        isVisited[next2] = true;   
                    }   
                    if (!isVisited[next3]) {   
                        queue.addLast(next3);   
                        step[next3] = step[current] + 1;   
                        isVisited[next3] = true;   
                    }   
                    if (!isVisited[next4]) {   
                        queue.addLast(next4);   
                        step[next4] = step[current] + 1;   
                        isVisited[next4] = true;   
                    }   
                }   
            }   
            System.out.println(step[end]);   
        }   
    }   
  
    public static int getNext(int flag, int i, int current) {   
        int next = 0;   
        if (flag == 1) {   
            if (i == 0) {   
                return current;   
            }   
            next = current % 1000 + i * 1000;   
        }   
        if (flag == 2) {   
            int t = current / 1000;   
            next = t * 1000 + current % 1000 % 100 + i * 100;   
        }   
        if (flag == 3) {   
            int t = current / 100;   
            int tt = current % 10;   
            next = t * 100 + i * 10 + tt;   
        }   
        if (flag == 4) {   
            next = current / 10 * 10 + i;   
  
        }   
        if (!isPrime[next]) {   
            return current;   
        }   
        return next;   
    }   
}   
  
class Prime {   
  
    public static boolean[] getPrimes(int n) {   
        int i, j, k, x;   
        boolean[] a = new boolean[n];   
        n++;   
        n /= 2;   
        int[] b = new int[(n + 1) * 2];   
        a[2] = true;   
        a[3] = true;   
        for (i = 1; i <= 2 * n; i++) {   
            b[i] = 0;   
        }   
        for (i = 3; i <= n; i += 3) {   
            for (j = 0; j < 2; j++) {   
                x = 2 * (i + j) - 1;   
                while (b[x] == 0) {   
                    a[x] = true;   
                    for (k = x; k <= 2 * n; k += x) {   
                        b[k] = 1;   
                    }   
                }   
            }   
        }   
        return a;   
    }   
}  


							

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

import java.io.BufferedInputStream;   
import java.util.Arrays;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
/**  
 * @author NC  
 * poj3125  
 */  
public class Main {   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        int cas = scan.nextInt();   
        for (int i = 1; i <= cas; i++) {   
            int n = scan.nextInt();   
            int position = scan.nextInt();   
            LinkedList<Job> queue = new LinkedList();   
            int[] priority = new int[n];   
            for (int j = 0; j < n; j++) {   
                priority[j] = scan.nextInt();   
                queue.addLast(new Job(j + 1, priority[j]));   
            }   
            Arrays.sort(priority);//非递减的   
            int time = 0;   
            int count = priority.length - 1;   
            Job current = null;   
            do {   
                current = queue.getFirst();   
                if (current.priority < priority[count]) {   
                    current = queue.removeFirst();   
                    queue.addLast(current);   
                } else if (current.priority == priority[count]) {   
                    time++;   
                    count--;   
                    queue.removeFirst();   
                    if (current.number == position + 1) {   
                        break;   
                    }   
                } else {   
                    System.out.println("error");   
                }   
            } while (true);   
            System.out.println(time);   
        }   
    }   
}   
  
class Job {   
  
    int priority;   
    int number;   
  
    Job(int n, int p) {   
        this.priority = p;   
        this.number = n;   
    }   
}  

							

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

/* @author: */
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    int r[]=new int[10000], t, i, n, f, count;
    double a, b, c;
    t=sc.nextInt();
    while(( t--)!=0 ) {
      n=sc.nextInt();
      f=sc.nextInt();
      f++;
      b = 0;
      for( i=0; i< n; i++ ) {
    r[i]=sc.nextInt();
    r[i] *= r[i];
    b += r[i];
      }

      a = 0;
      while( b-a> 1e-5 ) {
    c = (b+a)/2;
    count = 0;
    for( i=0; i< n; i++ )
       count += (int)(r[i]/c);
    if( count >= f )
       a = c;
    else
       b = c;
    }
    System.out.printf( "%.4fn", a*3.14159265358979324 );
    }
   }
}
							

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

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


int sx[65536], sy[65536];
int c, r, to;
const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };

void next( int &x, int &y ) {
    c++;
    if( c == (2*r-1)*(2*r-1) ) {
        to = 0;
        r++;
        x--;
        return;
    }

    x += dx[to];
    y += dy[to];

    if( abs(x) == r-1 && abs(y) == r-1 )
        to = (to+1)%4;
}

int main( ) {
    int n, i, a, b, caso, k, x, y, s1, s2;

    scanf( "%d", &caso );

    for( k=1; k<=caso; k++ ){

        scanf( "%d%d", &a, &b );
        c = 0; r = 1; to = 0;

        x = y = 0;

        for( i=0; i<65536; i++ ) {
            while( x*a+b == y )
                next( x, y );
            sx[i] = x;
            sy[i] = y;
            next( x, y );
        }

        scanf( "%d", &n );
        printf( "Caso %dn", k );

        while( n-- ) {
            scanf( "%d%d", &s1, &s2 );
            if( (sx[s1]*a+b<sy[s1]) == (sx[s2]*a+b<sy[s2]) )
                printf( "Mesmo lado da fronteiran" );
            else
                printf( "Lados opostos da fronteiran" );
        }
    }
    return 0;
}
							

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

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


							

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

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

using namespace std;

int main( ) {
    __int64 m[4][2], *ans = m[0], *temp = m[1], *id = m[2], *idt = m[3], s1, s2, 
        mem[2][20], *res = mem[0], *rest = mem[1];
    int en[20], ti[20];
    int f, p, e, a, i, j;

    while( 1 ) {
        scanf( "%d%d%d%d", &f, &p, &e, &a );
        e *= a;
        if( f == 0 && p == 0 && e == 0 && a == 0 ) break;

        ans[0] = 0;
        ans[1] = 50000000000;
        id[0] = 0;
        id[1] = 1;

        for( j=0; j<f; j++ )
            res[j] = 50000000000;

        for( i=0; i<p; i++ ) {
            for( j=0; j<f; j++ ) {
                scanf( "%d%d", en+j, ti+j );
                en[j] *= ti[j];
            }

            temp[0] = 50000000000;
            temp[1] = 50000000000;

            for( j=0; j<f; j++ ) {
                s1 = ans[0] + en[j] + e*(j!=id[0]);
                s2 = ans[1] + en[j] + e*(j!=id[1]);
                rest[j] = res[j] + en[j];

                if( s1 < rest[j] ) rest[j] = s1;
                if( s2 < rest[j] ) rest[j] = s2;

                if( rest[j] < temp[0] ) {
                    temp[1] = temp[0], idt[1] = idt[0];
                    temp[0] = rest[j], idt[0] = j;
                }
                else if( rest[j] < temp[1] )
                    temp[1] = rest[j], idt[1] = j;
            }

            swap( temp, ans );
            swap( id, idt );
            swap( rest, res );
        }

        printf( "%I64dn", ans[0] );
    }
    return 0;
}


							

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

 
							

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

#include <stdio.h>


int m[1000];

int main( ) {
    int n, p, c, i, j, t, ans;

    while( 1 ) {
        scanf( "%d%d%d", &p, &n, &c );
        if( n == 0 && p == 0 && c == 0 )
            break;

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

        for( i=0; i<n; i++ ) {
            for( j=0; j<p; j++ ) {
                scanf( "%d", &t );
                if( t == 0 ) {
                    if( m[j] >= c )ans++;
                    m[j] = 0;
                }
                else
                    m[j]++;
            }
        }
        for( j=0; j<p; j++ )
            if( m[j] >= c )
                ans++;
        printf( "%dn", ans );
    }
    return 0;
}
							

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

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

struct node{
    int v, w, id;
}nd[100010];

double r;

bool cmp( node &a, node &b ) {
    return a.v-a.w*r > b.v-b.w*r;
}

int main( ){
    int n, k, i;
    double t, s1, s2;
    scanf( "%d%d", &n, &k );
    for( i=0; i<n; i++ ) {
        scanf( "%d %d", &nd[i].v, &nd[i].w );
        nd[i].id = i+1;
    }

    t = 0;
    r = 1.0;
    while( r != t ) {
        std::sort( nd, nd+n, cmp );
        s1 = s2 = 0;
        for( i=0; i<k; i++ )
            s1 += nd[i].v, s2 += nd[i].w;
        t = r;
        r = s1/s2;
    }

    for( i=0; i<k; i++ )
        printf( "%d ", nd[i].id );

    return 0;
}
        
							

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

#include <stdio.h>
#include <queue>

using namespace std;

int days[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int getDays( int dd, int mm, int year ) {
    int res = (year-1700)*365 + (year-1700-1)/4 + days[mm-1] + dd;
    if( year > 1800 )
        res--;
    if( year > 1900 )
        res--;
    if( mm > 2 && year % 4 == 0 && ( year % 100 != 0 || year % 400 ==0 ) )
        res ++;
    return res;
}

void toDate( int &dd, int &mm, int &year, int s ) {
    int i, j, t;
    
    year = s/366 + 1700;

    while( getDays( 1, 1, year+1 ) <= s )
        year++;

    for( i=1; i<=12; i++ ) {
        t = days[i]-days[i-1];
        if( i == 2 && year%4 == 0 && ( year%100!=0 || year%400==0 ) )
            t++;
        for( j=1; j<=t; j++ )
            if( getDays( j, i, year ) == s ) {
                dd = j, mm = i;
                return;
            }
    }

    return;
}

struct Exam {
    char w[12];
    int dd, mm, yy;
    int s, t;
}exam[50000];

struct Cmp {
    bool operator()( Exam *a, Exam *b ) const {
        return a->t < b->t;
    }
};

priority_queue< Exam*, vector<Exam*>, Cmp > q;

bool cmp( const Exam &a, const Exam &b ) {
    return a.s>b.s;
}

int main( ) {
    int i, n, ans;
    bool key = true;
    for( i=1; i<=12; i++ )
        days[i] += days[i-1];

    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%s%d.%d.%d%d", &exam[i].w, &exam[i].dd, &exam[i].mm, &exam[i].yy, &exam[i].t );
        exam[i].s = getDays( exam[i].dd, exam[i].mm, exam[i].yy );
        exam[i].t = exam[i].s-exam[i].t;
    }

    sort( exam, exam+n, cmp );
    
    ans = 10000000;
    for( i=0; i<=n && key; i++ ) {
        while( !q.empty() && ( i== n || ans > exam[i].s ) ) {
            if( ans < q.top()->t ) {
                key = false;
                break;
            }
            ans--;
            q.pop();
        }
        if( i < n ) {
            q.push( &exam[i] );
            ans = exam[i].s-1;
        }
    }

    if( !key )
        printf( "Impossiblen" );
    else {
        int a, b, c;
        toDate( a, b, c, ans+1 );
        printf( "%02d.%02d.%04dn", a, b, c );
    }
    return 0;
}



							

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

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

using namespace std;

const int size = 100010;

int s[size];
int m;

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

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

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

    y++;

    for(j=y;j<=m;j+=lowbit(j))
        s[j]++;

}

void reset( int y )
{
    int j;

    y++;

    for(j=y;j<=m;j+=lowbit(j))
        s[j]--;

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

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

    return ans;
}


pair<int,int> q[size*2];
pair<int,int> p[size];
int f[100010];

int main( ) {
    int i, j, k, n, t, ans = 0, N, h;
 
    scanf( "%d", &n ); 
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].first, &p[i].second );

    sort( p, p+n );

    k = 0;
    h = 0;
    for( i=0; i<n; i=j ) {
        for( j=i+1; j<n && p[j].first == p[i].first; j++ )
            ;
        f[h++] = p[i].first;
    
        q[k].first = p[i].second;
        q[k++].second = ((p[i].first)<<1);
        q[k].first = p[j-1].second+1;
        q[k++].second = ((p[i].first)<<1)|1;
    }
    m = h;
    N = k;

    for( i=0; i<n; i++ )
        swap( p[i].first, p[i].second );

    sort( p, p+n );
    sort( q, q+N );

    k = 0;
    for( i=0; i<n; i=j ) {
        for( j=i+1; j<n && p[j].first == p[i].first; j++ )
            ;
        
        while( k < N && q[k].first <= p[i].first ) {
            t = lower_bound( f, f+m, q[k].second>>1 ) - f;
            if( q[k].second&1 )
                reset( t );
            else
                set( t );
            k++;
        }
        ans += count( lower_bound( f, f+m, p[j-1].second ) - f ) 
            - count( lower_bound( f, f+m, p[i].second ) - f-1 );
    }

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



							

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

#include <stdio.h>


static char str[100010];
static char input[310][310], ans[310][310];
static int n, m;

static int doit( int s ) {
    int i = s/1000, j = s%1000, a = i, b = j;
    int nn = n;
    int mm = m, t;
    
    for( int k=0; str[k]; k++ ) {
        switch( str[k] ){
        case '1':
            a = j; b = i;
            t = nn; nn = mm; mm = t; 
            break;
        case '2':
            a = nn-j; b = mm-i; 
            t = nn; nn = mm; mm = t; 
            break;
        case 'H':
            a = mm-i; b = j; break;
        case 'V':
            a = i; b = nn-j; break;
        case 'B': case 'Y':
            a = mm-i; b = nn-j; break;
        case 'A': case 'Z':
            a = j; b = mm-i;
            t = nn; nn = mm; mm = t; 
            break;
        case 'C': case 'X':
            a = nn-j; b = i; 
            t = nn; nn = mm; mm = t; 
            break;
        }
        i = a;
        j = b;
    }
    return i*1000+j;
}

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

    for( i=0; i<m; i++ )
        scanf( "%s", input[i] );

    getchar( );
    gets( str );
    
    int *x=new int[3], *y = new int[3];
    int t;
    n--; m--;
    t = doit( 0*1000+0 );
    x[0] = t/1000; y[0] = t%1000;
    
    t = doit( m*1000+0 );
    x[1] = t/1000; y[1] = t%1000;
    
    t = doit( 0*1000+n );
    x[2] = t/1000; y[2] = t%1000;
    n++;m++;

    int a = x[0], b = y[0], aa, bb;
    int da = ((x[1]==x[0]) ? 0 : ((x[1]>x[0])?1:-1) ),
        db = ((y[1]==y[0]) ? 0 : ((y[1]>y[0])?1:-1) ),
        da1= ((x[2]==x[0]) ? 0 : ((x[2]>x[0])?1:-1) ),
        db1= ((y[2]==y[0]) ? 0 : ((y[2]>y[0])?1:-1) );

    int nn = 0, mm = 0;

    for( i=0; i<m; i++ ) {
        aa = a; bb = b;
        for( j=0; j<n; j++ ) {
            ans[aa][bb] = input[i][j];
            if( aa > nn )
                nn = aa;
            if( bb > mm )
                mm = bb;
            aa += da1; bb += db1;
        }
        a += da; b += db;
    }
    nn++;mm++;
    
    printf( "%d %dn", nn, mm );
    
    for( i=0; i<nn; i++ ) {
        for( j=0; j<mm; j++ )
            printf( "%c", ans[i][j] );
        printf( "n" );
    }
            
    return 0;
}
							

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

/* @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 );
    int m = cin.nextInt();
    int n, i, p1, p0, s;
    double v;
    while( (m--) > 0 ) {
    s = n = cin.nextInt();
    v = 0;
    for( i=1; i< n; i<<=1 ) {
      if( (s&1) == 1 ) {
        p0 = (s/2+1)*i;
        p1 = n-p0;
      }
      else {
        p1 = s/2*i;
        p0 = n-p1;
      }
      v += i*(2.0*p1/n*p0/n);
      s >>= 1;
    }
    System.out.printf( "%.2fn", new Object[]{ Double.valueOf(v) } );
    }
    return;
   }
}


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    static int[] p;
    static int a,k;
    public static void main(String[] args) throws IOException
    {
        InputStreamReader is=new InputStreamReader(System.in);
        BufferedReader in=new BufferedReader(is);
        a=Integer.parseInt(in.readLine());
        p=new int[a];
        String[] ss=in.readLine().split(" ");
        long total=0;
        for(int i=0;i< a;i++){
            p[i]=Integer.parseInt(ss[i]);
            total+=p[i];
        }
            
        k=Integer.parseInt(in.readLine());
        int v=k+a-1;
        long min=total/v;
        long high=total;
        while(high>min)
        {
            long mid=(high+min)/2;
            if(f(mid)) high=mid;
            else min=mid+1;
        }
        System.out.println(min);
    }
    static boolean f(long t)
    {
        long u=t;
        for(int i=0;i< a;i++)
        {
            if(p[i]<=t)continue;
            long sy=p[i]-t;
            u-=sy/(k-1);
            if(sy%(k-1)!=0)
                u--;
        }
        if(u< 0) return false;
        else return true;
    }
}
							

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

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

public class Main {
 static double dis[][];
 static int e[][];
 static int [] x, y, en;
    
 static double distance( int a, int b ) {
    return Math.sqrt( (x[a]-x[b])*(x[a]-x[b]) + 
        (y[a]-y[b])*(y[a]-y[b]) );
 }
    
static void dfs( int k, int f, double [] dis, double s ){
  dis[k] = s;
  int j;
  for( int i=0; i< en[k]; i++ ) {
   if( e[k][i] != f ) {
    j = e[k][i];
    dfs( j, k, dis, s+distance( k, j ) );
   }
  }
 }
    
 static public void main( String [] str ) throws Exception{
  Scanner cin = new Scanner( System.in );
  int n = cin.nextInt();
  x = new int[n+1];
  y = new int[n+1];
  en = new int[n+1];
  dis = new double[n+1][n+1];
  e = new int[n+1][n+1];
        
  for( int i=1; i<=n; i++ ) {
    x[i] = cin.nextInt();
    y[i] = cin.nextInt();
  }
        
  int a, b;
  double t, ans = 0;
  for( int i=1; i<=n; i++ ) {
    a = cin.nextInt();
    b = cin.nextInt();
    e[a][en[a]++] = b;
    e[b][en[b]++] = a;
   }
        
   for( int i=0; i<=n; i++ )
    dfs( i, -1, dis[i], 0 );
        
   a = -1;
   b = -1;
   for( int i=0; i<=n; i++ )
    for( int j=i+1; j<=n; j++ ) {
    int k;
    for( k =0; k<=n; k++ )
      if( k!= i && k!=j && 
       (x[i]-x[k])*(y[j]-y[k])-(y[i]-y[k])*(x[j]-x[k]) == 0 &&
       (x[i]-x[k])*(x[j]-x[k])+(y[i]-y[k])*(y[j]-y[k]) <= 0 )
        break;
      if( k <= n )
       continue;
      t = - dis[i][j] + distance( i, j );
      if( t < ans ) {
        ans = t;
        a = i;
        b = j;
      }
    }
    System.out.println();

    if( a < 0 )
    System.out.println( -1 );
    else
    System.out.println( a+" "+b );
   }
}
							

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

import java.util.*;
import java.math.*;
public class Main {
    public static int[] p=new int[3000];
    public static int pc;
    public static int[] a=new int[3000];
    public static boolean[] che=new boolean[10001];
    public static void init(){
        int t1=2;
        while(t1*t1<=10000){
            int t2=t1*t1;
            while(t2<=10000){
                che[t2]=true;
                t2+=t1;
            }
            t1++;
            while(t1*t1<=10000&&che[t1])
                t1++;
        }
        for(int i=2;i< 10000;i++)
            if(!che[i])
                p[pc++]=i;
    }
    public static void solve(int k){
        for(int i=0;i< pc&&p[i]<=k;i++){
            int temp=0;
            while(k%p[i]==0){
                temp++;
                k/=p[i];
            }
            if(temp>a[i])
                a[i]=temp;
        }
    }
    public static int gcd(int x1,int x2){
        if(x2==0)
            return x1;
        return gcd(x2,x1%x2);
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        init();
        int n=in.nextInt();
        int[] q=new int[1000];
        for(int i=0;i< n;i++){
            q[i]=in.nextInt();
            solve(q[i]);
        }
        BigInteger ans1=BigInteger.ONE;
        for(int i=0;i< pc;i++)
            for(int j=0;j< a[i];j++)
                ans1=ans1.multiply(BigInteger.valueOf(p[i]));
        int ans2=0;
        for(int i=1;i< n;i++)
            if(q[0]!=q[i])
                ans2=gcd(ans2,Math.abs(q[i]-q[0]));
        if(a[0]>0)
            ans1=ans1.divide(BigInteger.valueOf(2));
        else ans2*=2;
        if(ans2==0)
            ans1=BigInteger.ZERO;
        System.out.println(ans1+" "+ans2);
    }
}


							

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

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 );
    int b, n;
    while( true ) {
      b = cin.nextInt();
      n = cin.nextInt();
      if( b == 0 && n == 0 )
     break;
      int x = (int)Math.pow( b, 1.0/n );
      if( Math.abs(Math.pow( x, n )-b)>Math.abs(Math.pow( x+1, n )-b) )
     x = x+1;
      System.out.println( x );
    }
    return;
  }
}
							

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

//* @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)));
    boolean flag;
    int index;
    String s;
    String[] pair;
    while (true){
        s=scanner.next();
        if (s.equals("*")){
            break;
        }
        if (s.length()==1){
            System.out.println(s+" is surprising.");
            continue;
        }
        index=0;
        flag=true;
        while (index< s.length()-1){
            pair=new String[s.length()-index-1];
            for (int i=0;i< pair.length ;i++ ){
                pair[i]=""+s.charAt(i)+s.charAt(i+index+1);
            }
            if (!check(pair)){
                flag=false;
                break;
            }
            index++;
        }
        if (flag){
            System.out.println(s+" is surprising.");
        }
        else{
            System.out.println(s+" is NOT surprising.");
        }
    }
  }

  public static boolean check(String[] s){
    for (int i=0;i< s.length-1 ;i++ ){
        for (int j=i+1;j< s.length ;j++ ){
            if (s[i].equals(s[j])){
                return false;
            }
        }
    }
    return true;
 }
}


							

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

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

public class Main { 

    public static void main(String[] args) throws IOException { 
        BufferedReader read = new BufferedReader(new InputStreamReader( 
                System.in)); 
        String s; 
        while (!(s = read.readLine()).equals("#")) { 
            char[] c = s.toCharArray(); 
            int[] p = new int[c.length]; 
            for (int i = 0; i < c.length; i++) { 
                if (c[i] == '.') { 
                    p[i] = 100; 
                } else if (c[i] == '_') { 
                    p[i] = 0; 
                } else if (c[i] == '|') { 
                    int k = 1; 
                    while (true) { 
                        if (i - k < 0) { 
                            p[i] += 50; 
                            break; 
                        } 
                        if (c[i - k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i - k] == '.' || c[i - k] == '/') { 
                            p[i] += 50; 
                            break; 
                        } else if (c[i - k] == '|' || c[i - k] == '\') { 
                            break; 
                        } 
                    } 
                    k = 1; 
                    while (true) { 
                        if (i + k == c.length) { 
                            p[i] += 50; 
                            break; 
                        } 
                        if (c[i + k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i + k] == '.' || c[i + k] == '\') { 
                            p[i] += 50; 
                            break; 
                        } else if (c[i + k] == '|' || c[i + k] == '/') { 
                            break; 
                        } 
                    } 
                } else if (c[i] == '/') { 
                    int k = 1; 
                    while (true) { 
                        if (i - k < 0) { 
                            p[i] = 100; 
                            break; 
                        } 
                        if (c[i - k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i - k] == '.' || c[i - k] == '/') { 
                            p[i] = 100; 
                            break; 
                        } else if (c[i - k] == '|' || c[i - k] == '\') { 
                            break; 
                        } 
                    } 
                } else if (c[i] == '\') { 
                    int k = 1; 
                    while (true) { 
                        if (i + k == c.length) { 
                            p[i] = 100; 
                            break; 
                        } 
                        if (c[i + k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i + k] == '.' || c[i + k] == '\') { 
                            p[i] = 100; 
                            break; 
                        } else if (c[i + k] == '|' || c[i + k] == '/') { 
                            break; 
                        } 
                    } 
                } 
            } 
            int sum = 0; 
            for (int i = 0; i < p.length; i++) { 
                sum += p[i]; 
            } 
            System.out.println(sum / p.length); 
        } 
    } 
} 

							

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

//* @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)));
        String s;
        int total;
        while (true){
            s=scanner.nextLine();
            if (s.equals("#")){
                break;
            }
            total=0;
            for (int i=0;i< s.length() ;i++ ){
                total=total+(i+1)*getValue(s.charAt(i));
            }
            System.out.println(total);
        }
    }

    public static int getValue(char c){
        if (c==' '){
            return 0;
        }
        else{
            return c-'A'+1;
        }
    }
}


							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
    
    static final int N = 30+5;
    static final int M = 1000+10;
    static int n,m;
    static int DP[] = new int[M],value[] = new int[N];
    
    public static void main(String []args) throws Exception{
        
        int t,cs=1,i,j;
        //Scanner cin = new Scanner(new FileInputStream("input.txt"));
        Scanner cin = new Scanner(System.in);
        
        t = cin.nextInt();
        while(t--!=0){
            n = cin.nextInt();
            m = cin.nextInt();
            for(i=0;i< n;++i) {
                value[i] = cin.nextInt();
            }
            Arrays.sort(value,0,n);

            System.out.println(cs+" "+solve());
            cs++;
        }
    }
    public static int solve(){
        int i,j,t,sum=0;
        
        for(t=0;t< n;++t){
            init(t);
            for(i=t+1;i< n;++i){
                for(j=m;j>=value[i];--j){
                    DP[j] += DP[j-value[i]];
                }
            }
            for(i=m;i>m-value[t] && i>0;--i)
                sum+=DP[i];
        }
        return sum;
    }
    public static void init(int t){
        int i,j=0;
        for(i=0;i<=m;++i) DP[i] = 0;
        for(i=0;i< t;++i)
            j+=value[i];
        if(j<=m)
            DP[j] = 1;
    }
}

							

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

/* @author: */
import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n, i, k, t, tt, p, count = 0;
       tt=sc.nextInt();
    while(( tt-- )!=0) {
         n=sc.nextInt();
         int a[]=new int[100];
         int b[]=new int[100];
         k = 0;
      p = 0;
      while( n!=0 ) {
       for( ; (n&1)==0; p++, n>>=1 )
        ;
        for( t=1, i=0; t*3<=n; t*=3,i++ )
        ;
        a[k] = p;
        b[k] = i;
        n -= t;
        k++;
      }
      System.out.printf( "%d %d", ++count, k );
      while(( k--)!=0 )
        System.out.printf( " [%d,%d]", a[k], b[k] );
      System.out.printf( "n" );
    }
   }
}
							

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

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

public class Main {
  static public void main( String [] str ) throws Exception{
   int n;
   int m;
   Scanner cin = new Scanner( System.in );
   n = cin.nextInt();
   for( int k=1; k<=n; k++ ) {
     m = cin.nextInt();
     System.out.println( k+" "+m+" "+(m*2+1)/3 );
     int j = 1;
     int count = -1;
     for( int i=(m+4)/3; i<=m; i+=2 ) {
    System.out.print( "["+i+","+j+"] " );
    j++;
    count++;
    if( count % 8 == 7 )
      System.out.println();
     }
     j = (m+4)/3+1;

     for( int i=(m+4)/3+1; i<=m; i+=2 ) {
    System.out.print( "["+i+","+j+"] " );
    j++;
       count++;
    if( count % 8 == 7 )
      System.out.println();
     }
     if( count % 8 != 7 )
    System.out.println();
     System.out.println();
   }
        
  return;
 }
}
							

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

//* @author: 
import java.util.*;
public class Main {
    public static void main(String[] args){
    int[] p=new int[1001];
    p[1]=3;
    p[2]=5;
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
for(int a=3;a<=1000;a++){
   p[a]=p[a-1]+2;
for(int i=2;i<=a;i++)
   p[a]+=2*c(a,i);
}
for(int t=1;t<=T;t++){
   int r=cin.nextInt();
   System.out.println(t+" "+r+" "+p[r]);
}
}
public static int c(int a,int b){
   while(a!=0){
    b=b%a;
    if(a>b){
     int temp=a;
     a=b;
     b=temp;
    } 
   }
   if(b==1)
    return 1;
   else 
    return 0;
}
}
							

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

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

public class Main {
  static int a[][] = new int[12][12];
  static long ans[] = new long[12];
    
  static public void main( String [] str ) throws Exception{
    int n;
    int m;
    Scanner cin = new Scanner( System.in );
    n = cin.nextInt();
        
    a[1][1] = 1;
    a[1][0] = 1;
    for( int i=2; i<=11; i++ ) {
     for( int j=1; j<=i; j++ )
    for( int k=1; k< i; k++ )
      a[i][j] += a[k][j]*j+a[k][j-1]*j;
    }
    
    for( int i=1; i<=11; i++ ) {
      ans[i] = ans[i-1];
      for( int j=1; j<=i; j++ )
     ans[i] += a[i][j];
    }
        
    for( int k=1; k<=n; k++ ) {
    m = cin.nextInt();
    System.out.println( k+" "+m+" "+ans[m] );
    }
    return;
   }
}


							

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

/* @author: */

import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
 static int a[] = new int[200];
 static char start[], result[];
    
 static public void main( String [] str ) throws Exception{
   int n;
   int m;
   Scanner cin = new Scanner( System.in );
   n = cin.nextInt();
   for( int k=1; k<=n; k++ ) {
    m = cin.nextInt();
    String input1 = cin.next(),
    input2 = cin.next(),
    input3 = cin.next();
    input1 += input2;
    start = input1.toCharArray();
    boolean [] sign = new boolean[m*2];
    for( int i=0; i< m; i++ )
         a[i] = i*2+1;
    for( int i=m; i< m*2; i++ )
      a[i] = (i-m)*2;
            
    int i;
    for( i=0; ; i++ ) {
      //System.out.println( start );
      if( input3.equals( String.valueOf(start) ) )
        break;
            
    for( int j=0; j< 2*m; j++)
      sign[j] = false;
                
    for( int j=0; j< 2*m; j++ ) {
      if( !sign[j] ) {
        char t = start[j], tt;
        sign[j] = true;
        for( int l=a[j]; l!=j; l=a[l] ) {
        sign[l] = true;
        tt = start[l];
        start[l] = t;
        t = tt;
        }
        start[j] = t;
      }
    }
                
    if( input1.equals( String.valueOf(start) ) ) {
       i = -1;
       break;
    }
    }
            
    System.out.println( k+" "+i );
   }
   return;
  }
}


							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 * @author NC  
 * Poj3086  
 */  
public class Main {   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        int n = scan.nextInt();   
        for (int i = 1; i <= n; i++) {   
            int kk = scan.nextInt();   
            if (kk == 1) {   
                System.out.println(i + " 1 3");   
                continue;   
            }   
            int sum = 0;   
            int t = 1;   
            for (int j = 2; j <= kk + 1; j++) {   
                t += j;   
                sum += (j - 1) * t;   
            }   
            System.out.println(i + " " + kk + " " + sum);   
        }   
    }   
}  


							

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

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


public class Main {
 public static void main(String[] args)
 {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    for(int i = 0; i < n; i++)
    {
    int sum = in.nextInt();
    int quarter = sum/25;
    sum = sum %25;
    int dime = sum/10;
    sum = sum%10;
    int nickel = sum/5;
    sum = sum%5;
    int penny = sum;
    System.out.println((i+1)+" "+quarter+" QUARTER(S), "+dime+" DIME(S), "+nickel+
        " NICKEL(S), "+penny+" PENNY(S)");
    }        
  }
}

							

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

/* @author: */
import java.util.*;
class ff
{
  static int min( int a, int b ) {
    return a< b?a:b;
  }
    
  class edge
 {
  int to;
  int c, f; 
  int rev_i;
  edge( int pa, int pb, int pc ) {
    to = pa; c = pb; f = 0;
    rev_i = pc;
   }
  }

  edge e[][] = new edge[30][1000];
  int en[] = new int[30];
  boolean sign[] = new boolean[30];
    
  void insert_edge( int from, int to, int limit )
  {
    e[from][en[from]] = new edge( to, limit, en[to] );
    e[to][en[to]] = new edge( from, 0, en[from] );
    en[from]++;
    en[to]++;
   }
    
   void add_flow( edge ee, int d )
  {
    ee.f += d;
    e[ ee.to ][ ee.rev_i ].f -= d;
   }
    
   int search( int k, int t, int best )
   {
    int i, m = en[k];
    int 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;
     }
    
   int maxflow( int n, int s, int t )
   {
     int total = 0, add = 0;
     do
     {
    total += add;
    for( int i=0; i< 30; i++ )
      sign[i] = false;
      }
     while( ( add = search( s, t, (1<< 30) ) ) > 0 );
    return total;
    }
 }

class Main {
 public static void main(String args[]) throws Exception
 {
   Scanner cin = new Scanner( System.in );
   int t, n, m, i, j, ans, b = 0;
   int h, g;
   String w;
   t = cin.nextInt();
   while( t-- != 0 ) {
     ff f = new ff();
     n = cin.nextInt();
     m = cin.nextInt();
     for( i=0; i< n; i++ ) {
        w = cin.next();
        if( w.equals( "I" ) ) {
         b = i;
          f.insert_edge( n, i, 1000000 );
        }
        h = cin.nextInt();
        for( j=0; j< h; j++ ) {
          g = cin.nextInt();
          f.insert_edge( g, i, 1 );
          f.insert_edge( i, g, 1000000 );
        }
      }

     ans = f.maxflow( n+1, n, m );
     if( ans >= 1000000 )
        System.out.println( "PANIC ROOM BREACH" );
     else
        System.out.println( ans );
   }
   return;
  }
}


							

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

/* @author: */
import java.util.*;
public class Main
{
  static String map[] = new String[50];
  static int q[] = new int[2000];
  static int n, m;
  static boolean inmap( int x, int y ) {
    return 0<=x&&x< n && 0<=y&&y< m;
  }
    
  static boolean sign[][] = new boolean[50][50];
  static final int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };

 static int search( int x, int y, int towards, int key ) {
   int xx, yy;
   if( map[x].charAt(y) == 'E' )
    return 1;
    //    System.out.print( x + " " + y + "n" );    
   for( int i=towards+4-key; ;i+=key )
    if( inmap(xx=x+dx[i&3],yy=y+dy[i&3]) && map[xx].charAt(yy) != '#' )
         return search( xx, yy, i&3, key ) + 1;
  }
    
  static int shortest( int x, int y ) {
    int i, j, qh, qt, xx, yy;
    for( i=0; i< n; i++ )
    for( j=0; j< m; j++ )
      sign[i][j] = false;
    qh = 0;
    qt = 2;
    q[0] = (x<< 8)+y;
    q[1] = -1;
    sign[x][y] = true;
        
    int count = 2;
    while( true ) {
    int c = q[qh++];
    if( c < 0 ) {
      count++;
      q[qt++] = c;
      continue;
    }
      x = c>>8;
      y = ( c & ((1<<8)-1) );
     for( i=0; i< 4; i++ )
      if( inmap(xx=x+dx[i],yy=y+dy[i]) && map[xx].charAt(yy) != '#' && !sign[xx][yy] ) {
      q[qt++] = (xx<<8) + yy;
      if( map[xx].charAt(yy) == 'E' )
        return count;
      sign[xx][yy] = true;
    }
    }

  }
    
 public static void main(String args[])
 {
    int t, j, i;
    Scanner cin = new Scanner( System.in );
    t = cin.nextInt();
    while( t-- != 0 ) {
        m = cin.nextInt();
        n = cin.nextInt();
        for( i=0; i< n; i++ )
        map[i] = cin.next();
      loop: for( i=0; i< n; i++ ) {
          for( j=0; j< m; j++ )
           if( map[i].charAt( j ) == 'S' ) {
             System.out.println( search( i, j, 0, -1 ) + " " + search( i, j, 0, 1 ) 
                + " " + shortest(i,j) );
             break loop;
           }
        }
    }
       return;
   }
}


							

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

/* @author: */
import java.util.*;
class point
{
  int x,y;
  point(){x=y=0;}
};

public class Main
{
  static int cheng(point a,point b,point c)
  {
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  }
    
  static int dcheng(point a,point b,point c)
  {
    return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);
  }
    
  static 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++;
    }

    return c%2;
   }

   static point p[][] = new point[30][];
   static int len[] = new int[50];
   
static boolean judge( int a, int b ) {
  point p1[] = p[a], p2[] = p[b];
  int i, j;
  for( i=0; i< len[a]; i++ )
   for( j=0; j< len[b]; j++ ) {
     if( cheng( p1[i], p2[j], p2[(j+1)%len[b]] ) == 0 &&
    dcheng( p1[i], p2[j], p2[(j+1)%len[b]] ) <= 0 )
    return true;
    }

  for( i=0; i< len[b]; i++ )
   for( j=0; j< len[a]; j++ )
     if( cheng( p2[i], p1[j], p1[(j+1)%len[a]] ) == 0 &&
     dcheng( p2[i], p1[j], p1[(j+1)%len[a]] ) <= 0 )
     return true;
        
  for( i=0; i< len[a]; i++ )
    if( in( p2, len[b], p1[i] ) > 0 )
    return true;
  for( i=0; i< len[b]; i++ )
    if( in( p1, len[a], p2[i] ) > 0 )
    return true;
  return false;
 }
    
 public static void main(String args[]) throws Exception
 {
   int t, n, j, i, k=1, g;
   int ans[] = new int[500];
   int answer;
   String w;
        
   Scanner cin = new Scanner( System.in );
   t = cin.nextInt();
   while( t-- != 0 ) {
      n = cin.nextInt();
     for( i=0; i< n; i++ ) {
        len[i] = cin.nextInt();
        p[i] = new point[len[i]];
        for( j=0; j< len[i]; j++ ) {
         w = cin.next();
          g = w.indexOf( ',' );
          p[i][j] = new point();
          p[i][j].x = Integer.parseInt( w.substring(0,g) );
          p[i][j].y = Integer.parseInt( w.substring(g+1) );
        }
    }
    answer = 0;
    for( i=0; i< n; i++ )
    for( j=i+1; j< n; j++ )
      if( judge( i, j ) )
       ans[ answer++ ] = (i+1)*100+j+1;
    System.out.println( "Data Set #" + k );
    k++;
    if( answer == 0 )
    System.out.println( "no collisions" );
    else {
    for( i=0; i< answer; i++ )
       System.out.println( ans[i]/100 + " " + ans[i]%100 );
    }
                
  }
  return;
 }
}


							

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

import java.util.*;

public class Main
{
 static String w[] = new String[10];
 public static void main(String args[])
{
   int t, n, i, j = 0, k;
   Scanner cin = new Scanner( System.in );
       
   t = cin.nextInt();
   String p = new String();
   String best;// = new String("");
       
   while( t-- != 0 ) {
     n = cin.nextInt();
     best = "";
     for( i=0; i< n; i++ )
         w[i] = cin.next();

     for( i=w[0].length(); i>=3; i-- ) {
        for( j=0; j<=w[0].length()-i; j++ ) {
            p = w[0].substring( j, i+j );
            for( k=1; k< n; k++ ) {
            if( w[k].indexOf( p ) == -1 )
               break;
            }
                   
           if( k == n && ( best == "" || p.compareTo( best ) < 0 ) )
               best = p;
        }
       if( best != "" )
          break;
    }
    if( i >= 3 )
    System.out.println( best );
   else
    System.out.println( "no significant commonalities" );
  }
  return;
 }
}
							

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

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

public class Main
{
    static String name[] = new String[20];
    static int pos[] = new int[20];
    public static void main(String args[])
    {
       Scanner cin = new Scanner( System.in );
       int t, n, m, a, b;
       t = cin.nextInt();
       while( t-- != 0 ) {
         n = cin.nextInt();
         m = cin.nextInt();
         for( int i=0; i< n; i++ ) {
           name[i] = cin.next();
           pos[i] = i;
         }
         boolean sign[] = new boolean[20];
         boolean flag[] = new boolean[20];
         while( m-- != 0 ) {
           a = cin.nextInt();
           b = cin.nextInt();
           a--;
           b--;
           pos[b] = a;
           sign[a] = true;
           flag[b] = true;
         }
         int j=0;
         for( int i=0; i< n; i++ ){
           if( flag[i])
             System.out.print( name[pos[i]] );
           else {
             while( sign[j] )
               j++;
           System.out.print( name[j] );
               j++;
        }
        if( i< n-1 )
           System.out.print( " " );
        else
           System.out.print( "n" );
     }
   }
   return;
  }
}
							

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

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

public class Main
{

    public static void main(String args[])
    {
       int n, s, i;
       Scanner cin = new Scanner( System.in );
       n = cin.nextInt();
       while( n-- != 0 ) {
           s = cin.nextInt();
           for( i=10; i<=100000000; i*=10 )
               if( s >= i ) {
                   s = (s+i/2)/i*i;
               }
           System.out.println( s );
       }
       return;
    }
}
							

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

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
   
    public class Main {
   
        public static void main(String[] args) throws IOException {
            BufferedReader read = new BufferedReader(new InputStreamReader(
                    System.in));
          int[] f = new int[15000];
           f[0] = 0;
           f[1] = 1;
           f[2] = 1;
           for (int i = 2; i < f.length - 1; i++) {
               f[i + 1] = (f[i - 1] + f[i]) % 10000;
           }
           int i;
           while ((i = Integer.parseInt(read.readLine())) != -1) {
               System.out.println(f[i % 15000]);
           }
       }
   }