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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main 
{
    public static int mat[][]=new int[505][505];
    public static int d[]=new int[505];
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int F,P,C,M;
        int i,j,k;
        int a,b,c;
        F=cin.nextInt();
        P=cin.nextInt();
        C=cin.nextInt();
        M=cin.nextInt();
        for(i=0;i< F;++i)
          for(j=0;j< F;++j)
            mat[i][j]=i==j?0:1000000000;
        while(P>0)
        {
            --P;
            a=cin.nextInt();
            b=cin.nextInt();
            c=cin.nextInt();
            --a;
            --b;
            if(c< mat[a][b])
                mat[a][b]=mat[b][a]=c;
        }
        for(i=0;i< F;++i)d[i]=1000000000;
        d[0]=0;
        boolean v[]=new boolean[505];
        Arrays.fill(v, false);
        for(i=0;i< F;++i)
        {
            k=-1;
            for(j=0;j< F;++j)
                   if(!v[j]&&(k==-1||d[j]< d[k]))k=j;
            for(v[k]=true,j=0;j< F;++j)
               if(!v[j]&&d[k]+mat[k][j]< d[j])
                d[j]=d[k]+mat[k][j];
        }
        int hash[]=new int[505];
        Arrays.fill(hash, -1);
        for(i=0;i< C;++i)
        {
            c=cin.nextInt();
            --c;
            hash[i]=c;
        }
        int ans=0;
        for(i=0;i< C;++i)
            if(hash[i]!=-1&&d[hash[i]]<=M)
                ++ans;
        System.out.println(ans);
        for(i=0;i < C;++i)
            if(hash[i]!=-1&&d[hash[i]]<=M)
                System.out.println(i+1);
    }
}
							

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

import java.util.Scanner;

public class Main{

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   int n = cin.nextInt();
   int m = n;
   int s = cin.nextInt();
   Node[] node = new Node[n];
   int i = 0;
   long sum = 0;
   while(m > 0) {
    node[i] = new Node(cin.nextInt(), cin.nextInt());
    i++;
    m--;
   }
   for(i=0; i< n-1; i++) {
    if(node[i].c + s < node[i+1].c) {
     node[i+1].c = node[i].c + s;
    }
     sum += node[i].c * node[i].y;
   }
   sum += node[i].c * node[i].y;
   System.out.println(sum);
}

}

class Node {
int c;
int y;
public Node(int c, int y) {
   this.c = c;
   this.y = y;
}
}

							

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

//* @author: 
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  private int k;
  private Block block[];
  private boolean access[]=new boolean[400001];

   public Main(int k,Block block[]){
    this.k=k;
    this.block=block;
  }

  private int doIt(){
   int maxs=0;
   access[0]=true;
   Arrays.sort(block);
   for(int i=0;i< k;i++)
    {
       int t=0;
       int tmp=maxs;
       for(int j=maxs;j>=t;j--)
       {
          if(access[j])
           for(int h=1;h<=block[i].c;h++)
           {
                  int x=h*block[i].h+j;
                  if(x>block[i].a) break;
                  if(tmp< x) tmp=x;
                  access[x]=true;        
           }      
       }
       maxs=tmp;
    }
    return maxs;
   }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     int k=sc.nextInt();
     Block b[]=new Block[k];
     for(int i=0;i< k;i++){
       b[i]=new Block();
       b[i].h=sc.nextInt();
       b[i].a=sc.nextInt();
       b[i].c=sc.nextInt();
     }
     Main m=new Main(k,b);
     System.out.println(m.doIt());
   }
}

class Block implements Comparable{//ʯͷ����
  int h;//ʯͷ�ĸ߶�
  int a;//�����߶�
  int c;//����ʯͷ����

  public Block(){
    h=0;
    a=0;
    c=0;
  }

  public Block(int h,int a,int c){
     this.h=h;
     this.a=a;
     this.c=c;
  }

   public int compareTo(Object o){ 
        Block bl = (Block)o; 
        return (int)(this.a - bl.a); 
    } 

   
 public String toString(){ 
        return "( "+ h +"-"+ a +"-"+c +" )"; 
    } 
 }
							

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

import java.io.BufferedInputStream;   
import java.math.BigInteger;   
import java.util.Scanner;   
  
/**  
 *  
 * Poj2390   
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
        int r = scan.nextInt();   
        long m = scan.nextLong();   
        int y = scan.nextInt();   
        double s = m;   
        for(int i = 1;i<=y;i++){   
            s=s*(r/100.0+1);   
        }   
            System.out.println((long)(Math.floor(s)));   
    }   
    }   
}  


							

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

import java.io.BufferedInputStream;   
import java.math.BigInteger;   
import java.util.Scanner;   
  
/**  
 *  
 * poj2389  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            BigInteger a = scan.nextBigInteger();   
            BigInteger b = scan.nextBigInteger();   
            System.out.println(a.multiply(b));   
        }   
    }   
}  

							

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

import java.io.BufferedInputStream; 
import java.util.Scanner; 
public class Main{ 

    public static void main(String[] args) { 
        Scanner scan = new Scanner(new BufferedInputStream(System.in)); 
        if (scan.hasNext()) { 
            int n = scan.nextInt(); 
            int[] array = new int[n + 1]; 
            for (int i = 0; i < n; i++) { 
                array[i + 1] = scan.nextInt(); 
            } 
            quickSort(array); 
            System.out.println(array[n / 2 + 1]); 

        } 
    } 

    private static int partition(int[] array, int low, int high) { 
        int key = array[low]; 
        while (low < high) {
            while (low < high && array[high] >= key) {
                high--; 
            } 
            array[low] = array[high]; 
            while (low < high && array[low] <= key) {
                low++; 
            } 
            array[high] = array[low];  
        } 
        array[low] = key; 
        return low; 
    } 

    private static void qSort(int[] array, int low, int high) { 
        int pivotloc; 
        if (low < high) {
            pivotloc = partition(array, low, high); 
            qSort(array, low, pivotloc - 1); 
            qSort(array, pivotloc + 1, high); 
        } 
    } 

    public static void quickSort(int[] array) { 
        int n = array.length - 1; 
        qSort(array, 1, n); 
    } 
} 


							

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

import java.util.*;   
public class Main{   
    public static void main(String args[]){   
        Scanner in=new Scanner(System.in);   
        int c=0;   
        int t=in.nextInt();//����˳�����WA��N�Σ������������⣡   
        int n=in.nextInt();   
        int dist[]=new int[n+1];//��������ȷ�������С������RE��N�Σ�   
        int[][] w=new int[n+1][n+1];   
        for(int i=1;i<=n;i++){   
            for(int j=1;j<=n;j++){   
                w[i][j]=Integer.MAX_VALUE;   
            }   
        }   
        for(int i=0;i< t;i++){//����}�㼰֮�����   
            int sn=in.nextInt();   
            int en=in.nextInt();   
            c=in.nextInt();   
            if(c< w[sn][en])   
                w[sn][en]=w[en][sn]=c;   
        }   
        dijkstra(n,w,dist);   
        System.out.println(dist[1]);   
    }   
       
    public static void dijkstra(int v ,int[][] a, int[] dist){//���·��dijkstra�㷨   
         int nn = dist.length - 1 ;         
         boolean[] s = new boolean[nn+1];        
               //��ʼ��         
         for(int i = 1; i <= nn; i++)      
             dist[i] = a[v][i];               
         dist[v] = 0;          
         s[v] = true;        
         for(int i = 1; i < nn; i++){          
             int temp =Integer.MAX_VALUE;       
             int u = v;         
             for(int j = 1; j < nn; j++){       
                 if(!s[j] && dist[j] < temp&&dist[j]>0){           
                     u = j;                  
                     temp = dist[j];            
                 }         
             }             
             s[u] = true;  //�ҵ��˵�һ����S�Ľڵ�      
             for(int j = 1; j <= nn; j++)         
                 if(!s[j] &&dist[u]+a[u][j]< dist[j]&& a[u][j] < Integer.MAX_VALUE)   
                         dist[j] =dist[u]+a[u][j];                                    
         }   
    }    
} 

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int b=in.nextInt();
  int count=0;
  int[][] arr=new int[a+2][b+2];
  for(int i=1;i<=a;i++){
   String s=in.next();
   for(int j=1;j<=b;j++)
    arr[i][j]=s.charAt(j-1);
  }
  for(int i=1;i<=a;i++)
   for(int j=1;j<=b;j++)
     if(arr[i][j]==87){
    find(arr,i,j);
    count++;
      }
   System.out.println(count);
                
   }

  public static void find(int[][] a,int i,int j)
  {
   if(a[i][j]==87)
   {
    a[i][j]=65;
    for(int k=i-1;k<=i+1;k++)
          for(int w=j-1;w<=j+1;w++)
        if(a[k][w]==87)find(a,k,w);
   }
 }
}
							

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

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

public class Main {

    /**
     * @param args
     */
    public static int max(int x,int y)
    {
        if(x>y) return x;
        return y;
    }
    
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        
        int t,w,i,j,k,ans=0;
        int dp[][][]=new int[1005][35][2];
        int way[]=new int[1005];
        
        for(i=0;i< 1005;++i) for(j=0;j< 35;++j) for(k=0;k< 2;++k)
            dp[i][j][k]=0;
        
        Scanner cin = new Scanner(System.in);
        
        t = cin.nextInt();
        w = cin.nextInt();
        
        for(i=1;i<=t;++i)
            way[i]=cin.nextInt()-1;
        
        for(i=1;i<=t;++i) for(j=0;j<=w;++j) for(k=0;k< 2;++k)
        {
          if(way[i]==k)
            dp[i][j][k]=max(dp[i-1][j][k]+1,j>0?dp[i-1][j-1][1-k]+1:1);
          else dp[i][j][k]=max(dp[i-1][j][k],j>0?dp[i-1][j-1][1-k]:0);
          if(dp[i][j][k]>ans&&((k==1&&j< w)||(k==0&&j<=w))) ans=dp[i][j][k];
        }
        
        System.out.println(ans);
    }

}

							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
class circle{
    int x,y,r,color;
}
class Set{
    int n,m;
    int next[][] = new int[1010][1010];
    void init(int _n,int _m){
        for(n=0;n<=_n;++n) for(m=0;m<=_m;++m)
            next[n][m] = m;
        n = _n;
        m = _m;
    }
    public int find(int x,int y){
        if(next[x][y]==y) return y;
        return next[x][y] = find(x,next[x][y]);
    }
}
public class Main {
    static final int N = 1000+10,M = 1000000+10;
    static int Graph[][] = new int[N][N];
    static int que[] = new int[M],n,m,k;
    static circle cir[] = new circle[10009];
    static Set set = new Set();
    static void start(){
        for(int i=0;i< 10009;++i) cir[i] = new circle();
    }
 public static void main(String[]args) throws Exception{
        
 int i;
 start();
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
 while(cin.nextToken()!=StreamTokenizer.TT_EOF){
    m = (int) cin.nval;
    cin.nextToken();
    n = (int) cin.nval;
    cin.nextToken();
    k = (int) cin.nval;
    for(i=0;i< k;++i){
        cin.nextToken();
        cir[i].y = (int)cin.nval;
        cin.nextToken();
        cir[i].x = (int)cin.nval;
        cin.nextToken();
        cir[i].r = (int)cin.nval;
        cin.nextToken();
        cir[i].color = (int)cin.nval;
    }
    solve();
   }
 }

  static void draw(int x,int y,int r,int color){
   int i,j,start,end,ret;
   for(i=-r;i<=r;++i)if(i+x>=0 && i+x< n){
    ret = r*r-i*i;
    if(ret< 0) continue;
    else ret = (int) Math.sqrt(ret);
            
    start = Max(y-ret,0);
    end = Min(m-1,y+ret);
    for(j=start;j<=end;j=set.find(x+i, j)){
        if(set.next[x+i][j]==j){
            Graph[x+i][j] = color;
            set.next[x+i][j] = j+1;
        }
    }
   }
 }


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

 static int Min(int a,int b){
    return a< b?a:b;
 }

 static void solve(){
  int i,j;
  PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  for(i=0;i<=n;++i) for(j=0;j<=m;++j) Graph[i][j] = 0;
  set.init(n, m);
  for(i=k-1;i>=0;--i){
    draw(cir[i].x,cir[i].y,cir[i].r,cir[i].color);
  }
  for(i=0;i< n;++i){
    for(j=0;j< m;++j)
        out.print(Graph[i][j]);
    out.println();
  }
  out.flush();
 }
    
}

							

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

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


char b[16000002];
int main()
{
    unsigned long a,m,c,r;
    memset(b,0,sizeof(b));
    scanf("%lu%lu%lu%lu",&a,&c,&m,&r);
    while(1)
    {
        r=(a*r+c)%m;
        if(b[r])
            break;
        else b[r]=1;
    }
    long i,max=0,last=0;
    for(i=0;i<16000002;i++)
        if(b[i])
            break;
    last=i++;
    for(;i<16000002;i++)
    {
        if(b[i])
        {
//            printf("%lu ",i);
            if(i-last>max)
            {
                max=i-last;
            }
            last=i;
        }
    }
    printf("%lu",max);
    return 0;
}
							

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

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


#define INF 30000
#define NMAX 500003
typedef struct
{
    long q,s,v;
}data;
data a[NMAX];
data b[NMAX];
long y[NMAX];
long x[NMAX];
long N;
int cmp(const void *a,const void *b)
{
    if(((data*)a)->s==((data*)b)->s)
        return ((data*)a)->q-((data*)b)->q;
    else
        return ((data*)a)->s-((data*)b)->s;
}
int cmp2(const void *a,const void *b)
{
    if(((data*)a)->q==((data*)b)->q)
        return ((data*)a)->s-((data*)b)->s;
    else
        return ((data*)a)->q-((data*)b)->q;
}
void solve()
{
    int i,j,k,nmax,ymax,xmax;
    qsort(a,N,sizeof(data),cmp);
    y[0]=a[0].s;
    
    j=0;
    b[0].s=a[0].s;
    b[0].q=a[0].q;
    b[0].v+=a[0].v;
    k=0;
    for(i=1;i<N;i++)
    {
        if(a[i].s==a[i-1].s&&a[i].q==a[i-1].q)
        {
            b[j].s=a[i].s;
            b[j].q=a[i].q;
            b[j].v+=a[i].v;
        }
        else
        {
            j++;
            b[j].s=a[i].s;
            b[j].q=a[i].q;
            b[j].v+=a[i].v;
        }
        if(a[i].s>y[k])
        {
            y[++k]=a[i].s;
        }
    }
    ymax=k+1;
    nmax=j+1;
    qsort(b,nmax,sizeof(data),cmp2);
    x[0]=b[0].q;
    k=0;
    for(i=1;i<nmax;i++)
    {
        if(b[i].q>x[k])
            x[++k]=b[i].q;
    }
    xmax=k+1;
    qsort(b,nmax,sizeof(data),cmp);

    
    printf("-1 ");
    for(i=0;i<xmax;i++)
    {
        printf("%d",x[i]);
        if(i<xmax-1)
            printf(" ");
        else
            printf("n");
    }
    k=0;
    for(i=0;i<ymax;i++)
    {
        printf("%d ",y[i]);
        for(j=0;j<xmax;j++)
        {
            if(b[k].q==x[j]&&b[k].s==y[i])
                printf("%d",b[k++].v);
            else
                printf("0");
            if(j<xmax-1)
                printf(" ");
            else
                printf("n");
        }
    }


}

int main()
{
    
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%d",&N);
    long i;
    for(i=0;i<N;i++)
    {
        scanf("%d%d%d",&a[i].q,&a[i].s,&a[i].v);
    }
    
    solve();

#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
							

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

//* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot;
import java.util.*;
import java.io.*;

public class Main 
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] mind = new int[n];
        boolean[] reached = new boolean[n];
        int[][] dist = new int[n][n];
        
        for(int i = 0; i < n; i++)
        {
            mind[i] = 0;
            reached[i] = false;
            
            for(int j = 0; j < n; j++)
            {
                dist[i][j] = 0;
            }
        }
        
        for(int i = 0; i < m; i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            
            if(dist[a-1][b-1] < c)
            {
                dist[a-1][b-1] = c;
                dist[b-1][a-1] = c;
            }
        }
        
        boolean isPossible = true;
        int total = 0;
        reached[0] = true;
        for(int j = 0; j < n; j++)
        {
            if(!reached[j] && dist[j][0] > mind[j])
            {
                mind[j] = dist[j][0];
            }
        }
        for(int i = 1; i < n; i++)
        {
            int max = 0;
            int index = -1;
            for(int j = 0; j < n; j++)
            {
                if(!reached[j] && mind[j] > max)
                {
                    max = mind[j];
                    index = j;
                }
            }
            if(index == -1)
            {
                isPossible = false;
                break;
            }
            reached[index] = true;
            total += mind[index];
            for(int j = 0; j < n; j++)
            {
                if(!reached[j] && dist[j][index] > mind[j])
                {
                    mind[j] = dist[j][index];
                }
            }
        }
        if(isPossible)
        {
            System.out.println(total);
        }else
        {
            System.out.println(-1);
        }
    }
    
}

							

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

 
							

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

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


char w[1000], *symbol="=+-*/0123456789n";

bool check_comment(int &s)
{
    do
    {
        while( w[s] && w[s] != '*' )
            s++;
        
        if( !w[s] || !w[ s+1 ] ) return false;
        else if( w[ ++s ] == ')' ) return true;

    }while(1);
    
    return true;
}

bool check_expression(int &s)
{
    do
    {
        while( w[s] && w[s] !='(' && w[s] != ')' )
        {
            if( !strrchr( symbol, w[s] ) ) return false;
            s++ ;
        }
        
        if(w[s] == ')' ) return true;
        
        if( !w[s] || !w[s+1] ) return false;
        
        if( w[ ++s ] == '*' )
        {
            s++;
            if( !check_comment( s ) ) return false;
        }
        else if( !check_expression( s ) ) return false;
        
        s++;

    }while(1);
}

bool check()
{
    int s = 0;
    while( w[s] )
    {
        if( w[s] == ')' ) return false;

        if( w[s] == '(' )
        {
            if( w[s+1] && w[s+1] == '*' )
            {
                s+=2;
                if( !check_comment( s ) ) return false;
            }
            
            else
            {
                s++;
                if( !check_expression( s ) ) return false;
            }
        }
        
        s++;
    }
    
    return true;
}

void init()
{
    int i;
    for( i=0; scanf("%1c",&w[i]) == 1 && w[i] != '#' ; i++ )
        ;

    w[i] = '';
}

int main()
{
    init();
    
    if( check() ) printf( "YESn" );
    else printf( "NOn" );
    
    return 0;
}
							

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

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

    public static void quickSort(int[] data, int s, int t) {
        int i = s+1;
        int j = t;
        int x = data[s];
        while (i <= j) {
            while (i <= j && data[j] >= x)
                --j;
            while (i <= j && x >= data[i])
                ++i;
            if (i <= j) {
                data[i] = data[j] + ((data[j] = data[i]) & 0);
                i++;
                j--;
            }
        }

        if (j != s) {
            data[s] = data[j];
            data[j] = x;
        }
        if (s < j - 1)
            quickSort(data, s, j - 1);
        if (j + 1 < t)
            quickSort(data, j + 1, t);
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int sum = sc.nextInt();
        int[] database = new int[sum];
        for (int i = 0; i < sum; ++i) {
            database[i] = sc.nextInt();
        }
        // Arrays.sort(database);
        quickSort(database, 0, database.length-1);
        sc.nextLine();
        sc.nextLine();
        int queryCount = sc.nextInt();
        for (int i = 0; i < queryCount; ++i) {
            int queryNum = sc.nextInt();
            System.out.println(database[queryNum - 1]);
        }
//        for(int i = 0 ; i < database.length ;++i)
//            System.out.print(database[i]+" ");
    }

}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt(),t=0,i;
  int[] b=new int[a];
  for(i=0;i< a;i++)
    b[i]=in.nextInt();
  a/=2;
  Arrays.sort(b);
  for(i=0;i<=a;i++)
    t+=b[i]/2+1;
  System.out.println(t);
 }
}
							

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

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 
 * Accepted. BigInteger is used here.
 * 
 * 
 */
public class Main {

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

        int n = cin.nextInt();

        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = 0;
            }
        }

        int[] depth = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            depth[i] = 0;
        }

        for (int i = 1; i <= n; i++) {
            while (true) {
                int k = cin.nextInt();

                if (k == 0) {
                    break;
                }

                a[i][k] = 1;
                depth[k]++;
            }
        }

        List<Integer> list = new ArrayList<Integer>();

        boolean[] picked = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            picked[i] = false;
        }

        while (list.size() < n) {

            for (int i = 1; i<= n; i++) {
                if (picked[i] == false && depth[i] == 0) {
                    list.add(i);
                    picked[i] = true;
                    

                    for (int j = 1; j<= n; j++) {
                        
                        if (picked[j] == false && a[i][j] == 1) {
                            depth[j]--;
                        }
                    }
                    
                    break;
                }
            }
        }
        
        for (int i = 0; i < list.size(); i++) {
            
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(list.get(i));
        }
        
        System.out.println();
    }


}



							

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

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

public class Main {
    
 static double N = 10000.0;
 public static void main(String []args) throws Exception{
        
    double temp;
    int i,j,n,m,t=1;
    Map first = new HashMap();
 StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
    in.nextToken();n=(int)in.nval;//n = cin.nextInt();
    for(i=0;i< n;++i){
        in.nextToken();
        first.put(in.nval,1);
        //first.put(cin.nextDouble(), 1);
    }
    j = 0;
    //m = cin.nextInt();
    in.nextToken();m =(int)in.nval;
    
    for(i=0;i< m;++i){
        in.nextToken();
        temp = in.nval;
        //temp = cin.nextDouble();
        temp = N-temp;
        if(first.containsKey(temp)){
            j = 1;
            break;
        }
    }
    
    if(j==1) System.out.println("YES");
    else System.out.println("NO");
        
  }
}

							

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int n=scanner.nextInt();
    double r=scanner.nextDouble();
    double[] x=new double[n];
    double[] y=new double[n];
    for (int i=0;i< n ;i++ ){
        x[i]=scanner.nextDouble();
        y[i]=scanner.nextDouble();
    }
    double l=2*r*Math.PI;
    for (int i=0;i < n ;i++ ){
          if (i!=n-1){
        l=l+Math.sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]));
      }
     else{
       l=l+Math.sqrt((x[i]-x[0])*(x[i]-x[0])+(y[i]-y[0])*(y[i]-y[0]));
        }
    }
    l=Math.round(l*100.0)/100.0;
    System.out.println(l);
   }
}


							

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

//* @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 c=scanner.nextInt();
    int n,sm;
    for (int l=0;l< c ;l++ ){
       n=scanner.nextInt();
        sm=4*n+2;
        for (int i=1;i<=n ;i++ ){
            for (int j=1;j*i<=n ;j++ ){
                for (int k=0;k*j*k<=n ;k++ ){
                    if (i*j*k==n){
                        if (2*(i*j+j*k+k*i)< sm){
                            sm=2*(i*j+j*k+k*i);
                        }
                    }
                }
            }
        }
        System.out.println(sm);
    }
  }
}


							

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

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

public class Main {

//记录数字的总长度。
int totalNum;
//记录各个数字的值的数组。
int[] numArr;
//记录每个小短棒是否被使用过。
boolean[] used;

public static void main(String args[]) throws Exception {
   Main m=new Main();
   m.begin();
}

private void begin() throws Exception {
   Scanner cin = new Scanner(System.in);
   int totalLine = cin.nextInt();
   for(int i=0; i< totalLine; i++){
    totalNum = cin.nextInt();
    numArr = new int[totalNum];
    //总长度。
    int sumLen = 0;
    for(int j=0; j< totalNum; j++){
     numArr[j] = cin.nextInt();
     sumLen += numArr[j];
    }
    //初始化每个小短棒都没被使用过。
    used = new boolean[totalNum];
    for(int j=0; j< totalNum; j++)
     used[j] = false;
    //和必须时 4 的倍数。
    if(sumLen%4==0){
     //排序，逆序。
     Arrays.sort(numArr);
     int temp;
     for(int k=0; k< totalNum/2; k++){
      temp = numArr[k];
      numArr[k] = numArr[totalNum-1-k];
      numArr[totalNum-1-k] = temp;
     }
     //获得最大值。
     int maxNum = numArr[0];
     //重置已经拼好的边数为 0。
     passNum = 0;
     //最大值不能大于总长的 1/4。
     if(maxNum <= sumLen/4){
      //开始深度优先搜索。
      if(DFS(0, sumLen/4, 0))
       System.out.println("yes");
      else
       System.out.println("no");
     }else
      System.out.println("no");
    }else
     System.out.println("no");
   }
}

//记录已经拼出的符合长度的边的个数，最多 4 个。
int passNum = 0;
//参数分别是当前循环的标识符、要测试的长度、需要加上的底数。
private boolean DFS(int f_num, int f_len, int f_sum){
   //当底数和需要的长度相等时。
   if(f_len == f_sum){
    //增加一条通过的边数。
    passNum++;
    //重置底数和开始时标识符。
    f_sum = 0;
    f_num = 0;
    //当通过的边数和 4 相等就说明成功。
    if(passNum == 4)
     return true;
   }
   //开始遍历下一层。
   for(int i=f_num; i< totalNum; i++){
    //当底数加上本数小于等于需要的长度时，并且本数没被使用。
    if(f_sum+numArr[i]<=f_len && !used[i]){
     //暂时记录为已经使用。
     used[i] = true;
     //进行下一次的递归。
     DFS(i+1, f_len, f_sum+numArr[i]);
     //边数达到 4 后即可跳出循环。
     if(passNum == 4)
      break;
     //通过了上面的脚本，说明边数没有达到 4，而又能拼出一条边，取消掉这条边，以便测试其他的组合。
     if(f_sum+numArr[i] == f_len)
      passNum--;
     //取消本数的记录。
     used[i] = false;
    }
   }
   //退出时检查一次是否拼好正方形。
   if(passNum == 4)
    return true;
   //返回失败。
   return false;
}
}

							

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

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

   int n,i,j;
   n=sc.nextInt();
   while((n--)!=0)
   {
    for(i=0;i< 3;i++)
        cc[i]=sc.next().toCharArray();
            
    int x=0,o=0;
       boolean xw=false,ow=false;
       boolean bb=true;
     for(i=0;i< 3;i++)
     for(j=0;j< 3;j++)
     {
        if(cc[i][j]=='X')x++;
        else if(cc[i][j]=='O')o++;
     }
    if(x-o>1||x< o)bb=false;
    for(i=0;i< 3;i++)
    {
      boolean tt=true;
      for(j=0;j< 2;j++)
      {
        if(cc[i][j]!=cc[i][j+1])
        {
        tt=false;
        break;
         }
            
       }
       if(tt)
       {
        if(cc[i][0]=='X')xw=true;
        else if(cc[i][0]=='O')ow=true;
        }
      }

     for(j=0;j< 3;j++)
    {
      boolean  tt=true;
      for(i=0;i< 2;i++)
      {
        if(cc[i][j]!=cc[i+1][j])
         {
        tt=false;
        break;
         }
       }
       if(tt)
        {
        if(cc[0][j]=='X')xw=true;
        else if(cc[0][j]=='O')ow=true;
        }
      }
     if(cc[0][0]==cc[1][1]&&cc[1][1]==cc[2][2]&&cc[2][2]=='X')xw=true;
     else if(cc[0][0]==cc[1][1]&&cc[1][1]==cc[2][2]&&cc[2][2]=='O')ow=true;
     if(cc[0][2]==cc[1][1]&&cc[1][1]==cc[2][0]&&cc[2][0]=='X')xw=true;
     else if(cc[0][2]==cc[1][1]&&cc[1][1]==cc[2][0]&&cc[2][0]=='O')ow=true;
     if(ow&&xw) bb=false;
     else if(ow&&x!=o)bb=false;
     else if(xw&&x==o)bb=false;
     if(bb) System.out.println("yes");
     else System.out.println("no");
    }
   }
}
							

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

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

#define NMAX 501
#define INF 2000000001
long m[NMAX][NMAX]={0};
long a[NMAX][NMAX]={0};
long M,N;
long b[NMAX*NMAX]={0};
int xp[3]={-1,0,1},yp[3]={0,-1,0};
void solve()
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        m[1][i]=a[1][i];
    }
    for(i=2;i<=M;i++)
    {
        for(j=1;j<=N;j++)
        {
            if(m[i][j]>a[i][j]+m[i-1][j])
                m[i][j]=a[i][j]+m[i-1][j];
        }
        for(j=2;j<=N;j++)
        {
            if(m[i][j]>a[i][j]+m[i][j-1])
                m[i][j]=a[i][j]+m[i][j-1];
        }
        for(j=N-1;j>=1;j--)
        {
            if(m[i][j]>a[i][j]+m[i][j+1])
                m[i][j]=a[i][j]+m[i][j+1];
        }
    }
}
void output()
{
    int kx,ky,i;
    long min=INF;
    int index=1;
    long q=0;
    for(i=1;i<=N;i++)
    {
        if(min>m[M][i])
        {
            min=m[M][i];
            index=i;
        }
    }
    ky=M;
    kx=index;
    b[q++]=kx;
    ky--;
    if(M==1)
    {
        printf("%d",kx);
        return ;
    }
    while(1)
    {
        b[q++]=kx;
        if(ky==1)
            break;
        for(i=0;i<3;i++)
        {
            if(kx+xp[i]<1||kx+xp[i]>N)
                continue;
            if(m[ky][kx]==a[ky][kx]+m[ky+yp[i]][kx+xp[i]])
            {
                ky=ky+yp[i];
                kx=kx+xp[i];
                break;
            }
        }
    }
    for(i=q-1;i>=0;i--)
        printf("%dn",b[i]);
        

}

int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%d%d",&M,&N);
    int i,j;
    for(i=1;i<=M;i++)
        for(j=1;j<=N;j++)
        {
            scanf("%d",&a[i][j]);
            m[i][j]=INF;
        }
    solve();
    output();
#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}
							

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

import java.io.*;
public class Main
{
    static int[] star=new int[32002];
    static int[] lev=new int[15000];
    public static void main(String[] args) throws NumberFormatException, IOException
    {
        InputStreamReader is=new InputStreamReader(System.in);
        BufferedReader in=new BufferedReader(is);
        int a=Integer.parseInt(in.readLine());
        int n=a;
        while((a--)!=0)
        {
            String[] ss=in.readLine().split(" ");
            int b=Integer.parseInt(ss[0]);
            lev[sum(b+1)]++;
            update(b+1);
        }
        for(int i=0;i< n;i++)
            System.out.println(lev[i]);
    }

    static int lowbit(int n)
    {
        return n&(-n);
    }

    static int sum(int n)
    {
        int r=0;
        while(n!=0)
        {
            r+=star[n];
            n-=lowbit(n);
        }
        return r;
    }
    
    static void update(int n)
    {
        while(n< 32002)
        {
            star[n]++;
            n+=lowbit(n);
        }
    }
}

							

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

import java.util.Scanner;   
  
/**  
 * poj2350 easy  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int nn = scan.nextInt();   
                float sum = 0f;   
                int[] aa = new int[nn];   
                for (int j = 0; j < nn; j++) {   
                    aa[j]= scan.nextInt();   
                    sum = sum + aa[j];   
                }   
                float average = sum/nn;   
                float count = 0f;   
                for(int j = 0; j < nn; j++){   
                    if(aa[j]>average){   
                        count++;   
                    }   
                }   
                System.out.printf("%.3f",count/nn*100);   
                System.out.println("%");   
  
            }   
        }   
    }   
}  

							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
 static int[] p;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int n=Integer.parseInt(in.readLine());
  while((n--)!=0)
  {
   String[] ss=in.readLine().split(" ");
   int a=Integer.parseInt(ss[0]);
   int b=Integer.parseInt(ss[1]);
   p=new int[b];
   int[] ax=new int[b];
   int[] ay=new int[b];
   mymy[] gg=new mymy[b*b/2];
   int ll=0;
   for(int i=0;i< b;i++)
    p[i]=i;
   for(int i=0;i< b;i++)
   {
    ss=in.readLine().split(" ");
    ax[i]=Integer.parseInt(ss[0]);
    ay[i]=Integer.parseInt(ss[1]);
   }
   for(int i=0;i< b;i++)
   {
    for(int j=i+1;j< b;j++)
     {
    int juli=(ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]);
    gg[ll++]=new mymy(i,j,juli);
     }
    }
   Arrays.sort(gg,0,ll);
   int cnt=0;
   for(int i=0;i< ll;i++)
   {
    if(un(gg[i].x,gg[i].y))
     {
    cnt++;
    if(cnt==b-a)
    {
      double hehe=Math.sqrt(gg[i].juli);
      System.out.printf("%.2fn",hehe);
      break;
    }
      }
    }
  }
 }

  static int root(int x)
   {
   int b=x;
   while(p[b]!=b)
    b=p[b];
   return p[x]=b;
   }

 static boolean un(int a,int b)
 {
  int aa=root(a);
  int bb=root(b);
  if(aa==bb)return false;
  if(aa>bb)
   p[aa]=bb;
  else p[bb]=aa;
   return true;
 }

}
class mymy implements Comparable< mymy>
{
    int x,y,juli;
    public mymy(int xx,int yy,int j)
    {
        x=xx;y=yy;juli=j;
    }
    @Override
    public int compareTo(mymy o) {
        return juli-o.juli;
    }
}
    


							

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

/* @author: */
import java.util.Scanner;
public class Main{
 static boolean judge(int x,int y)
{
    int t;
    if(x< y) {t=x;x=y;y=t;}
    if(x%y==0) return true;
    if(x-y< y) return !judge(y,x-y);
    return true;
}

 public static void main(String args[])
{
   Scanner sc=new Scanner(System.in);
   int m,n;
   while(sc.hasNext())
   {
      m=sc.nextInt();
      n=sc.nextInt();
      if(m==0&&n==0) break;
      if(judge(m,n)) System.out.println("Stan wins");
      else System.out.println("Ollie wins");
   }
  }
}
							

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


import java.util.*;
/**
 *
 * @author leo
 */
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n, max=0;
        int[][] dp = new int[6][46];
        for(int i=0;i<=9;i++){
            dp[1][i]=1;
        }
        for(int i=1;i<=5;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=5;i++){
            for(int j=1;j<=i*9;j++){
                if(j< 10) dp[i][j]=dp[i-1][j]+dp[i][j-1];
                else dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-10];
            }
        }

        n = sc.nextInt();
        for(int i=0;i<=(n*9)/2;i++){
            max+=(dp[n/2][i]*dp[n/2][i]);
        }
        System.out.println(max);
    }
}
							

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

#include"stdio.h"
#include"algorithm"
#include"math.h"

using namespace std;

int n,m;
const double eps=1e-8;
const int size=2000;

double a[size][size];
bool sign[size];

void swap_c(int k,int l)
{
    int i;
    for(i=0;i<m;i++)
        std::swap(a[i][k],a[i][l]);
}

bool guass()
{
    int i,j,k,l;double temp;
    for(i=0;i<m;i++)
        sign[i]=1;
    
    for(l=0,i=0;i<n;i++)
    {
        while(fabs(a[l][i])<eps)
        {
            for(j=i+1;j<n;j++)
                if(fabs(a[l][j])>eps)
                {
                    swap_c(i,j);
                    break;
                }
            
            if(j==n)
            {
                sign[l]=0;
                l++;
            }
            if(l>=m)
                return 0;
        }
        for(k=l+1;k<m;k++)
        if(fabs(a[k][i])>eps)
        {
            temp=a[k][i]/a[l][i];
            for(j=i;j<n;j++)
                a[k][j]-=a[l][j]*temp;
        }
        l++;
    }
    return 1;
}
int value[size];
int id[size];
int b[size][size];
int flag[size];

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

int main()
{
    int i,j;
    scanf("%d %d",&m,&n);
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        scanf("%d",&b[i][j]);
    for(i=0;i<m;i++)
    {
        scanf("%d",&value[i]);
        value[i]=value[i]*10000+i;
    }

    for(i=0;i<m;i++)
        id[i]=i;

    sort(id,id+m,cmp);

    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        a[i][j]=b[id[i]][j];
    
    if(!guass())
        printf("0n");
    else
    {
        int ans=0;
        for(i=0;i<m;i++)
            flag[i]=0;

        for(i=0,j=0;i<m&&j<n;i++)
            if(sign[i])
            {
                j++;
                ans+=value[id[i]]/10000;
                flag[id[i]]=1;
            }
        printf("%dn",ans);
        for(i=0,j=0;i<m&&j<n;i++)
            if(flag[i])
            {
                printf("%dn",i+1);
                j++;
            }
    }
    return 0;
}



							

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

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

public class Main {

    /**
     * @param args
     */
    public static int row;
    public static int column;

    public static int replace(int i, int j, int[][] array) {
        int temp = 0;
        if (array[i][j] == 'R')
            temp = 'P';
        else if (array[i][j] == 'S')
            temp = 'R';
        else if (array[i][j] == 'P')
            temp = 'S';

        if (i + 1 < row && array[i + 1][j] == temp)
            return temp;
        if (j + 1 < column && array[i][j + 1] == temp)
            return temp;
        if (i > 0 && array[i - 1][j] == temp)
            return temp;
        if (j > 0 && array[i][j - 1] == temp)
            return temp;
        return array[i][j];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
    
        for (int i = 0; i < n; i++) {
            row = in.nextInt();
            column = in.nextInt();
            int day = in.nextInt();
            String s = in.nextLine();
            int[][] array = new int[row][column];
            int[][] temp = new int[row][column];
            for (int j = 0; j < row; j++) {
               String line = in.nextLine();
               //System.out.println(line);
               for (int k = 0; k < column; k++) {
                array[j][k] = line.charAt(k);
               }
            }

         for (int m = 0; m < day; m++) {
          for (int j = 0; j < row; j++) {
            for (int k = 0; k < column; k++) {
                temp[j][k] = replace(j, k, array);
            }
          }
         int count = 0;
         for (int j = 0; j < row; j++) {
            for (int k = 0; k < column; k++) {
                if (temp[j][k] == temp[0][0])
                    count++;
                array[j][k] = temp[j][k];
            }
        }
        if (count == row * column) {
            break;
        }
    }
    for (int j = 0; j < row; j++) {
        // String line = in.nextLine();
        for (int k = 0; k < column; k++) {
            System.out.print((char) array[j][k]);
        }
            
            System.out.println();
    }
    if(i!=n-1)
        System.out.println();
     }

  }

}

							

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

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


public class Main {
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  int num = in.nextInt();
  for(int i = 0; i< num; i++)
  {
    int n = in.nextInt();
    int t = in.nextInt();
    int m = in.nextInt();
    int[] time = new int[m];
    int starttime = 0;
    for(int j = 0; j< m; j++)
    {
        time[j] = in.nextInt();            
    }
    if(m % n == 0)
    {    
        starttime = time[n-1];
        for(int k = 1; k< m/n; k++)
        {
            if(time[n*(k+1)-1] > starttime + 2*t)
                starttime = time[n*(k+1)-1];
            else
                starttime += 2*t;
            
        }
    }
    else
    {
        starttime = time[m%n -1];
        int p = m/n;
            int index = m%n -1;
        for(int k = 0; k< p; k++)
        {
          if(time[n*(k+1)+ index] > starttime + 2*t)
           starttime = time[n*(k+1)+ index];
          else
           starttime += 2*t;
        }
    }
    int result = (int)Math.ceil(1.0*m/n);
    System.out.println(starttime+t+" "+ result);
  }
 }
    
}

							

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

#include <stdio.h>


const int size = 5010;

struct point
{
    int x, y;
}p[size], pt[size];

__int64 s[size];

inline __int64 cross( point &o, point &a, point &b )
{
    return (__int64)(a.x-o.x)*(b.y-o.y) - (__int64)(a.y-o.y)*(b.x-o.x);
}

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

int n, l;

void init( )
{
    int i;
    scanf( "%d %d", &n, &l );

    for( i=0; i<n; i++ )
    {
        scanf( "%d %d", &p[i].x, &p[i].y );
        p[i].y = 1000010 - p[i].y;
        pt[i].x = p[i].x;
        pt[i].y = 0;
    }

    s[0] = 0;
    for( i=1; i<n; i++ )
    {
        s[i] = s[i-1] + (__int64)( p[i].x - p[i-1].x ) * ( p[i].y + p[i-1].y );
    }

}

void doit( )
{
    int i, j, k, t;
    __int64 ans = 0, temp, ll;

    for( i=0; i<n; i++ )
    {
        t = p[i].x + l;
        ll = (__int64) l* l;
        
        k=i+1;

        for( j=i+1; j<n && p[j].x <= t; j++ )
            if( cross( p[k], p[i], p[j] ) <= 0 && dis( p[i], p[j] ) <= ll )
            {
                k = j;
                temp =  (__int64)( p[j].x - p[i].x ) * ( p[j].y + p[i].y ) - ( s[j] - s[i] );
                if( temp > ans )
                    ans = temp;
            }
    }

    if( ans % 2 == 0 )
        printf( "%I64dn", ans/2 );
    else
        printf( "%I64d.5n", ans/2 );
}

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

    return 0;
}
							

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

    import java.util.*;  
      
    public class Main {  
      
        public static void main(String[] args) {  
              
            Scanner cin = new Scanner(System.in);  
          
            List guess = new ArrayList();  
           List response = new ArrayList();  
             
           while(cin.hasNext())  
           {  
               String guessNum = cin.nextLine();  
               if(guessNum.equals("0"))  
                   break;  
              String result = cin.nextLine();  
                
              guess.add(guessNum);  
              response.add(result);  
                 
               if(!result.equals("right on"))  
                   continue;  
                 
               else  
               {  
                   int honest = check(guess, response);  
                   if(honest == 1)  
                       System.out.println("Stan may be honest");  
                   else  
                       System.out.println("Stan is dishonest");  
                   guess.clear();  
                   response.clear();  
               }  
           }  
       }  
         
       private static int check(List guess, List response)  
       {  
           int honest = 1;  
             
           int lower = 0;  
           int upper = 11;  
             
           for(int i = 0; i < guess.size(); i++)  
           {  
               int g = Integer.valueOf((String)guess.get(i)).intValue();  
               String r = (String)response.get(i);  
                 
               if(r.equals("too high"))  
               {  
                   if(g <= lower)  
                   {  
                       honest = -1;  
                       break;  
                  }  
                   if(g < upper)  
                   {  
                       upper = g;  
                   }  
                     
               }  
               if(r.equals("too low"))  
               {  
                   if(g >= upper)  
                   {  
                       honest = -2;  
                       break;  
                   }  
                   if(g > lower)  
                   {  
                       lower = g;  
                   }  
               }  
                 
               if(r.equals("right on"))  
               {  
                   if(upper <= g || lower >= g || upper < lower)  
                   {  
                       honest = -3;  
                       break;  
                   }  
               }  
           }  
             
           return honest;  
       }  
     
   }  

							

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

//* @author 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    public static void main(String[] args) 
    {
        BigInteger n,zero,ten;
        int count,flag,a[],i,j;
        a=new int[2000];
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext())
        {
            n = cin.nextBigInteger();
            zero=BigInteger.ZERO;
            ten=BigInteger.TEN;
            if(n.compareTo(BigInteger.valueOf(-1))==0)
               break;
            if(n.compareTo(ten)< 0)//n< 10
            {
                System.out.println("1"+n);
                continue;
            }
            flag=0;count=0;
            while(true)
            {
                flag=0;
                for(i=9;i>=2;i--)
                {
                    if(n.mod(BigInteger.valueOf(i)).compareTo(zero)==0)
                    {
                        flag=1;
                        a[++count]=i;
                        n=n.divide(BigInteger.valueOf(i));
                        break;
                    }
                }
                if(n.compareTo(ten)< 0)
                {
                    flag=1;
                    a[++count]=n.intValue();
                    break;
                }
                if(flag==0)//�����ڶ���ÿһ��i�������Ļ�
                    break;
            }
            if(flag==0)
                System.out.println("There is no such number.");
            else
            {
                for(i=count;i>=1;i--)
                    System.out.print(a[i]);
                System.out.println();
            }
        }
    }

 }
							

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

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

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

    }
    
    BigInteger [][] dp;

    private void run() throws FileNotFoundException {
        Scanner cin = new Scanner(System.in);
        //Scanner cin = new Scanner(new BufferedReader(new FileReader("t.in")));
        dp = new BigInteger[19][201];
        for(int i = 0; i < 19; ++i) {
            Arrays.fill(dp[i], BigInteger.ZERO);
        }
        dp[1][0] = BigInteger.ONE;
        for(int i = 2; i < 19; ++i) {
            for(int j = 0; j <= (i-1)*i/2 && j < 201; ++j) {
                for(int k = j; k >= j-i+1 && k >= 0; --k) {
                    dp[i][j] = dp[i][j].add(dp[i-1][k]);
                }
            }
        }
        while(true) {
            int a = cin.nextInt(), b = cin.nextInt();
            if(a == 0 && b == 0)
                break;
            System.out.println(dp[a][b]);
        }
        
    }

}

							

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

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin = new Scanner(System.in);
  while(run() != false)
    ;
  }
  
static boolean run(){
   int n = cin.nextInt();
   if(n==0)
    return false;
   Box box = new Box(n, cin);
   System.out.println();
   return true;
 }
}

class Box{
  int n,m;
  int X1,Y1,X2,Y2;

  PartitionList pList;

  public Box(int n, Scanner cin){
    this.n = n;
    m = cin.nextInt();
    X1 = cin.nextInt();
    Y1 = cin.nextInt();
    X2 = cin.nextInt();
    Y2 = cin.nextInt();

    int[] map = new int[n+1];
    Partition.setBound(Y1, Y2);
    pList = new PartitionList(n);

    for(int i=0;i< n;i++){
    pList.add(new Partition(cin.nextInt(), cin.nextInt()));
    map[i] = 0;
    }
    map[n] = 0;

    for(int i=0;i< m;i++)
    map[pList.search(cin.nextInt(), cin.nextInt())]++;
    for(int i=0;i<=n;i++)
    System.out.println(i+": "+map[i]);
  }


}

class Partition{
  static int Y1, Y2;
  int U,L;

  public Partition(int U, int L){
    this.U = U;
    this.L = L;
  }

  static void setBound(int y1, int y2){
    Y1 = y1;
    Y2 = y2;
  }

 int compareTo(int X, int Y){
   double position = L+(double)(Y-Y2)*(U-L)/(Y1-Y2);
   if(X > position)
     return -1;
   else
    return 1;
 }
}

class PartitionList{
  Partition[] list;

  private int count=0;

  public PartitionList(int n){
    list = new Partition[n];
  }

  void add(Partition p){
    list[count++] = p;
  }

  int search(int X, int Y){
    if(list[0].compareTo(X, Y) == 1)
    return 0;
    else if(list[list.length-1].compareTo(X, Y) == -1)
    return list.length;
    else
    return find(0, list.length-1, X, Y);
   }

 
 private int find(int start, int end, int X, int Y){
   if((start+1)==end)
    return end;

   int mid = (start+end)/2;

   if(list[mid].compareTo(X, Y) == 1)
    return find(start, mid, X, Y);
   else 
    return find(mid, end, X, Y);
 }
}

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] a=new int[300];
  int k=0;
  while(in.hasNextInt())
  {
        
   String s=in.next();
   for(int i=0;i< s.length();i++)
    a[i]=(a[i]+s.charAt(i)-'0')%10;
   k=s.length();
  }
  for(int i=0;i< k;i++)
  {
   System.out.print(a[i]);
  }
 }
}
							

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

//* @author:
import java.util.*;
public class Main {
 
static long abs(long a)
{
    if(a< 0)
        return -a;
    else
        return a;
}

static  boolean in(long a,long b,long c)
{
    if(abs(a-c)+abs(b-c)==abs(a-b))
        return true;
    else return false;
}

static public void main( String [] str ) throws Exception{
   Scanner sc = new Scanner(System.in);
   long sum=0;
   int n;
   n=sc.nextInt();
   long a[]=new long[n+1];
   long b[]=new long[n+1];

    for(int i=1;i<=n;i++)
    {
       a[i]=sc.nextLong();;
    }
    b[0]=a[0]=0;
    b[0]=a[1];
    b[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(in(a[i-1],b[i-2],a[i]))
     {
        b[i-1]=a[i];
      }
     else
     {
       if(abs(a[i]-a[i-1])< abs(a[i]-b[i-2]))
        b[i-1]=a[i-1];
       else
        b[i-1]=b[i-2];

      }
    sum+=abs(a[i]-b[i-1]);
      }
    
   System.out.printf("%d",sum);
 
   }
}

							

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

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

  public static void  main(String args[])   
{   
   Scanner sc=new Scanner(System.in);
   int p[][]=new int[305][305];
   char c[][]=new char[305][305];

   int n,m,i,j,k;

   while(sc.hasNext())
   {
      n=sc.nextInt();
      m=sc.nextInt();

     if(m==0&&n==0) break;
     for(i=0;i< n;i++)
        c[i]=sc.next().toCharArray();
            
     int x1=0,y1=0,x2=0,y2=0;
     for(i=0;i< n;i++)
    for(j=0;j< m;j++) p[i][j]=999999;
     for(i=0;i< n;i++)
     {
    for(j=0;j< m;j++)
    {
      if(c[i][j]=='Y')
      {
        x1=i;
        y1=j;
        c[i][j]=1;
      }
      else if(c[i][j]=='T')
      {
        x2=i;
        y2=j;
        c[i][j]=1;
       }
     else if(c[i][j]=='E')c[i][j]=1;
     else if(c[i][j]=='B')c[i][j]=2;
    }
      }
      p[x1][y1]=0;
      while(true)
      {
     boolean bb=false;
     for(i=0;i< n;i++)
     {
       for(j=0;j< m;j++)
       {
        if(p[i][j]==999999)continue;
        if(i>0&&c[i-1][j]<3&&p[i-1][j]>p[i][j]+c[i-1][j])
        {
              p[i-1][j]=p[i][j]+c[i-1][j];
           bb=true;
        }
        if(i< n-1&&c[i+1][j]<3&&p[i+1][j]>p[i][j]+c[i+1][j])
        {
          p[i+1][j]=p[i][j]+c[i+1][j];
          bb=true;
        }
        if(j>0&&c[i][j-1]<3&&p[i][j-1]>p[i][j]+c[i][j-1])
        {
           p[i][j-1]=p[i][j]+c[i][j-1];
           bb=true;
        }
        if(j< m-1&&c[i][j+1]<3&&p[i][j+1]>p[i][j]+c[i][j+1])
        {
          p[i][j+1]=p[i][j]+c[i][j+1];
          bb=true;
        }
        }
    }
    if(!bb)break;
     }
     if(p[x2][y2]>50000) System.out.println("-1");
     else System.out.printf("%dn",p[x2][y2]);
   }
  }
}  
							

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        long n=scan.nextInt();
        long k=0,j,v,temp,l,r;
        for(int i=0;i< n;i++){
            k=scan.nextInt();
            if(k%2==1)System.out.println(k+" "+k);
            else{
                j=(int)Math.floor(Math.log(k)/Math.log(2));
                v=1<< j;
                while(v!=k){
                    j--;
                    if(v>k)v-=(1<< j);
                    else v+=(1<< j);
                }
                l=k;
                r=k;
                l-=(1<< j)-1;
                r+=(1<< j)-1;
                System.out.println(l+" "+r);
            }
        }
    }
}
							

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



import java.io.BufferedInputStream;   
import java.math.BigInteger;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int b = scan.nextInt();   
            if (b == 0) {   
                break;   
            }   
            BigInteger p = scan.nextBigInteger(b);   
            BigInteger m = scan.nextBigInteger(b);   
            System.out.println(p.mod(m).toString(b));   
        }   
    }   
}


							

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

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

public class Main {

/**
 * @param args
 */
 public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
      while (true) {
    int begin = in.nextInt();
    int one = in.nextInt();
    int two = in.nextInt();
    int three = in.nextInt();
    if ((begin | one | two | three) == 0)
    break;
    int result = 1080;
    // ��ʱ��
    result += begin < one ? (begin + 40 - one) * 9 : (begin - one) * 9;
    // ˳ʱ��
    result += one < two ? (two - one) * 9 : (40 + two - one) * 9;
    // ��ʱ��
    result += two < three ? (two + 40 - three) * 9 : (two - three) * 9;
    System.out.println(result);
    }
  }

}

							

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

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin = new Scanner(System.in);
  int n = cin.nextInt();
  for(int i=0;i< n;i++)
   run();
  }

 static void run(){
   Card card = new Card(cin);
   boolean first=true;
   int n;
   for(int i=0;i< 75;i++){
    n = cin.nextInt();
    if(first==true){
    card.mark(n);
    if(card.check()==true){
      System.out.println("BINGO after "+(i+1)+" numbers announced");
      first = false;
    }
    }
   }
 }
}

class Card{
 int[][] map;
 boolean[][] marked;

 public Card(Scanner cin){
  int size=5;
  map = new int[size][size];
  marked = new boolean[size][size];
        
  int i,j;
  for(i=0;i< size;i++)
   for(j=0;j< size;j++){
     marked[i][j] = false;
     if((i!=2)||(j!=2))
    map[i][j] = cin.nextInt();
    }
   marked[2][2] = true;
 }

 void mark(int n){
   int row=0, column=0;

   while(row< 5){
    column=0;
    while(column< 5){
    if(map[row][column]==n){
      marked[row][column] = true;
      break;
    }
       column++;
     }

    if(column< 5)
    break;
    row++;
   }
 }

 boolean check(){
   if(checkRow())
    return true;
   else if(checkColumn())
    return true;
   else if(checkDiagonal())
    return true;
  else
    return false;
}

boolean checkRow(){
 int row=0;
 while(row< 5){
   int column=0;
   while(column< 5){
    if(marked[row][column]==false)
        break;
    column++;
   }

  if(column==5){
    break;
   }
   row++;
 }

 if(row< 5){
   return true;
  }
 return false;
}

 boolean checkColumn(){
    int column=0;
    while(column< 5){
    int row=0;
    while(row< 5){
      if(marked[row][column]==false)
       break;
      row++;
    }

    if(row==5)
      break;
    column++;
    }

    if(column< 5)
    return true;
    return false;
 }


 boolean checkDiagonal(){
   if(checkLeftDiagonal())
     return true;
   else if(checkRightDiagonal())
     return true;
   else
     return false;
  }

 boolean checkLeftDiagonal(){
   int element=0;
   while(element< 5){
     if(marked[element][element] == false)
         return false;
     element++;
   }
   return true;
 }

boolean checkRightDiagonal(){
  int element=0;
  while(element< 5){
   if(marked[element][4-element] == false)
    return false;
   element++;
  }
 return true;
 }
}

							

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

import java.util.Scanner;   
  
public class Main{   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int s = scan.nextInt();   
                int d = scan.nextInt();   
                if (s < d ||(s+d)%2==1) {   
                    System.out.println("impossible");   
                } else {   
                    int a = (s + d) / 2;   
                    int b = (s - d) / 2;   
                    System.out.println(a + " " + b);   
                }   
            }   
        }   
  
    }   
}  


							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
public class Main {   
  
    static long num = 0;  
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            if (n == 0) {   
                break;   
            }   
            num = 0;   
            int data[] = new int[n];   
            for (int i = 0; i < n; i++) {   
                data[i] = scan.nextInt();   
            }   
            mergeSort(data, 0, n - 1);   
            System.out.println(num);   
        }   
    }   
  
    static void mergeSort(int[] array, int left, int right) {   
  
        if (left < right) {   
            int center = (left + right) / 2;   
            mergeSort(array, left, center);   
            mergeSort(array, center + 1, right);   
            Merge(array, left, center, right);   
        }   
    }   
  
    static void Merge(int[] array, int left, int center, int right) {   
        //[1,2,3,4] left=1,ceter=2,right=4   
        int[] temp = new int[right - left + 1];  
        int i = left;   
        int j = center + 1;   
        int k = 0;   
        while (i <= center && j <= right) {   
            if (array[i] > array[j]) {   
                temp[k++] = array[j++];   
               
                num += center - i + 1;   
  
            } else {   
                temp[k++] = array[i++];   
            }   
        }   
        while (i <= center) {   
            temp[k++] = array[i++];   
        }   
        while (j <= right) {   
            temp[k++] = array[j++];   
        }   
        for (i = left, k = 0; i <= right; i++, k++) {   
            array[i] = temp[k];   
        }   
    }   
}  


							

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

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

public class Main{
 public static void main(String[] args) throws Exception{
  BufferedReader scanner=new BufferedReader(new InputStreamReader(System.in));
  int n=Integer.parseInt(scanner.readLine());
  String f;
  String[] t;
  double a1,a2,b1,b2;
  for (int i=0;i< n ;i++ ){
    a1=0;
    a2=0;
    b1=0;
    b2=0;
    f=scanner.readLine();
    t=f.split("=");
    String e="";
    char oper='+';
    for (int j=0;j< t[0].length() ;j++ ){
        if (t[0].charAt(j)=='-'||t[0].charAt(j)=='+'){
            if (e.charAt(e.length()-1)=='x'){
                if (e.equals("x")){
                    e="1x";
                }
          a1=a1+Double.parseDouble(oper+e.substring(0,e.length()-1));
            }
            else{
                b1=b1+Double.parseDouble(oper+e);
            }
            oper=t[0].charAt(j);
            e="";
        }
        else{
            if (t[0].charAt(j)!=' '){
                e=e+t[0].charAt(j);
            }
        }
    }
    if (!e.equals("")){
        if (e.charAt(e.length()-1)=='x'){
            if (e.equals("x")){
                e="1x";
            }
      a1=a1+Double.parseDouble(oper+e.substring(0,e.length()-1));
        }
        else{
            b1=b1+Double.parseDouble(oper+e);
        }
    }
    e="";
    oper='+';
    for (int j=0;j< t[1].length() ;j++ ){
        if (t[1].charAt(j)=='-'||t[1].charAt(j)=='+'){
            if (e.charAt(e.length()-1)=='x'){
                if (e.equals("x")){
                    e="1x";
                }
              a2=a2+Double.parseDouble(oper+e.substring(0,e.length()-1));
            }
            else{
                b2=b2+Double.parseDouble(oper+e);
            }
            e="";
            oper=t[1].charAt(j);
        }
        else{
            if (t[1].charAt(j)!=' '){
                e=e+t[1].charAt(j);
            }
        }
    }
    if (!e.equals("")){
        if (e.charAt(e.length()-1)=='x'){
            if (e.equals("x")){
                e="1x";
            }
        a2=a2+Double.parseDouble(oper+e.substring(0,e.length()-1));
        }
        else{
            b2=b2+Double.parseDouble(oper+e);
        }
    }
    if (a1==a2){
        if (b1==b2){
            System.out.println("IDENTITY");
        }
        else{
            System.out.println("IMPOSSIBLE");
        }
    }
    else{
      System.out.println((int)Math.floor((b2-b1)/(a1-a2)));
    }
  }
 }
}


							

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

//* @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=scanner.nextInt();
        int n,max;
        int[] r;
        for (int i=0;i< t ;i++ ){
            n=scanner.nextInt();
            r=new int[n];
            for (int j=0;j< n ;j++ ){
                r[j]=scanner.nextInt();
            }
            intSort(r,0,n-1);
            max=n*r[0];
            for (int j=1;j< n ;j++ ){
                if ((n-j)*r[j]>max){
                    max=(n-j)*r[j];
                }
            }
            System.out.println(max);
        }
    }

    public static void intSort(int[] number,int left,int right){
        if (left< right){
            int s=number[(left+right)/2];
            int i=left-1;
            int j=right+1;
            while (true){
                while (number[++i]< s);
                while (number[--j]>s);
                if (i>=j) break;
                swap(number,i,j);
            }
            intSort(number,left,i-1);
            intSort(number,j+1,right);
        }
    }

    public static void swap(int[] number,int i,int j) {
        int t;
        t=number[i];
        number[i]=number[j];
        number[j]=t;
    }
}


							

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

// author:M.J
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.CountDownLatch;
import java.io.*;
import java.math.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int[] t = new int[1002];
        int[] king = new int[1002];
        int ans = 0;
        while(cin.hasNextInt()) {
            ans = 0;
            int n = cin.nextInt();
            if(n == 0) break;
            for(int i = 0;i < n; i++) 
                t[i] = cin.nextInt();
            for(int i = 0;i < n; i++)
                king[i] = cin.nextInt();
            Arrays.sort(t,0,n);
            Arrays.sort(king,0,n);
            int et = n-1,ek = n-1,st = 0,sk = 0;
            for(int i = 0;i < n; i++){
                    if(t[et] > king[ek]){       
                            ans ++;
                            et --;
                            ek --;
                    }
                    else if(t[et] < king[ek]){
                            ans --;
                            ek --;
                            st ++;
                    }
                    else{                          
                            if(t[st] > king[sk]){
                                ans ++;
                                st ++;
                                sk ++;
                            }
                            else if(t[st] > king[sk]){
                                    ans --;
                                    st ++;
                                    ek --;
                            }
                            else{
                               if(t[st] < king[ek])
                                 ans --;
                                 st ++;
                                 ek --;
                            }
                    }
            }
            ans *= 200;
            System.out.println(ans);
        }
    }
}

							

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

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

struct point
{
    double x,y;
};

struct line
{
    point a,b;
};
typedef double Type;

inline bool equal(point a,point b)
{
    return a.x==b.x&&a.y==b.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;}

/////////////////////////////////////////
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(s1*s2>0)return 0;

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

if(s3*s4>0)return 0;

if(s1*s2<0&&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;

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

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


line edge[400];
int n;


struct cmp
{
    bool operator()(point a,point b)const
    {
        return a.x<b.x||(fabs(a.x-b.x)<1e-8&&a.y<b.y);
    }

};

set<point,cmp> p;
set<point,cmp> p_on_l[310];

void init()
{
    point p1,p2;line lt;
    int i;
    
    p.clear();
    for(i=0;i<n;i++)
        p_on_l[i].clear();
        
    cin>>p1.x>>p1.y;

    for(i=0;i<n;i++)
    {
        cin>>p2.x>>p2.y;
        p.insert(p2);
        
        lt.a=p1;lt.b=p2;        
        edge[i]=lt;
        
        p_on_l[i].insert(p1);
        p_on_l[i].insert(p2);

        p1.x=p2.x;
        p1.y=p2.y;
    }
}


int doit()
{
    int i,j;point pt;
    
    for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(jiao(edge[i],edge[j]))
        {
            pt=crosspoint(edge[i],edge[j]);
            
            if(p_on_l[i].find(pt)==p_on_l[i].end())p_on_l[i].insert(pt);
            if(p_on_l[j].find(pt)==p_on_l[j].end())p_on_l[j].insert(pt);
            if(p.find(pt)==p.end())p.insert(pt);
        }

    int m=0;
    for(i=0;i<n;i++)
        m+=p_on_l[i].size()-1;

    return m+2-p.size();
}


int main()
{
    int i=1;
    while(1)
    {
        cin>>n;
        if(n==0)break;
        n--;
        
        init();
        cout<<"Case "<<i++<<": There are "<<doit()<<" pieces."<<endl;
    }
    return 0;
}