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

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

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);  
  double x[]=new double[21],sum;
  int n,flag;
  int i,j;
  while(sc.hasNext())
    {
      n=sc.nextInt();
      if(n==0) break;
        for(i=0;i< n;i++)
         x[i]=sc.nextDouble();
        Arrays.sort(x,0,n);
        sum=0;flag=0;
        for(i=0;i< n-1;i++)
        {
            sum+=x[i];
            for(j=i+1;j< n;j++)
            if(x[j]<=sum)
            {
                flag=1; 
               break ;
            }
        }        
        
        if(flag!=0) System.out.printf("YESn");
        else System.out.printf("NOn");
    }    
   }
}
							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(stdin.readLine()),k,aux;
        StringTokenizer tokens;
        while((n--)!=0){
            tokens=new StringTokenizer(stdin.readLine());
            k=Integer.parseInt(tokens.nextToken());
            aux=-k+1;
            while((k--)!=0)aux+=Integer.parseInt(tokens.nextToken());            
            System.out.println(aux);
        }
    }
}

							

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

//* @author 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    static boolean h[];
    public static void main(String[] args)
    {
        int m,i,j=2;
        h=new boolean[1000005];
        BigInteger n,p,q,nn;
        for(i=1;i<=1000001;i++)
            h[i]=true;
        for(i=2;i<=1000001;i+=2)
            h[i]=false;
        h[1]=false;h[2]=true;    
        for(i=3;i<=1000;i+=2)
        {
          if(h[i]==true)
          {
              j=2;
              while(i*j<=1000000)
              {
                  h[i*j]=false;
                  j++;
              }
          }
        }
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext())
        {
            j=1000100;
            n=cin.nextBigInteger();
            m=cin.nextInt();
            nn=BigInteger.ZERO;
            if(n.compareTo(nn)==0&&m==0)
                break;
          for(i=2;i<=1000000;i++)
          {
          if(h[i]==true)
          {
            p=n.divide(BigInteger.valueOf(i));
            q=p.multiply(BigInteger.valueOf(i));
            if(q.compareTo(n)==0)
            {
                j=i;
                break;
            }
          }
         }
            if(j< m)
                System.out.println("BAD "+j);
            else
                System.out.println("GOOD");
        }
    }
}
 
							

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

import java.util.Scanner;  
    
 enum Direction {  
     N, S, W, E  
 }  
    
 class Robot {  
     int id;  
     int x;  
     int y;  
     Direction direction;  
    
     public Robot(int i, int x, int y, String direction) {  
         this.id = i;  
         this.x = x;  
         this.y = y;  
         if (direction.equalsIgnoreCase("N"))  
             this.direction = Direction.N;  
         else if (direction.equalsIgnoreCase("S"))  
             this.direction = Direction.S;  
         else if (direction.equalsIgnoreCase("W"))  
             this.direction = Direction.W;  
         else if (direction.equalsIgnoreCase("E"))  
             this.direction = Direction.E;  
     }  
    
     public void move(String command) {  
         if (command.equalsIgnoreCase("F")) {  
            switch (this.direction) {  
            case N:  
                 this.y++;  
                 break;  
             case S:  
                 this.y--;  
                 break;  
             case W:  
                 this.x--;  
                 break;  
             case E:  
                 this.x++;  
                 break;  
             }  
         } else {  
             this.rotate(command);  
         }  
     }  
    
     public void rotate(String s) {  
         if (s.equalsIgnoreCase("L")) {  
             switch (this.direction) {  
             case N:  
                 this.direction = Direction.W;  
                 break;  
             case S:  
                 this.direction = Direction.E;  
                 break;  
             case W:  
                 this.direction = Direction.S;  
                 break;  
             case E:  
                 this.direction = Direction.N;  
                 break;  
             }  
         } else {  
             switch (this.direction) {  
             case N:  
                 this.direction = Direction.E;  
                 break;  
             case S:  
                 this.direction = Direction.W;  
                 break;  
             case W:  
                 this.direction = Direction.N;  
                 break;  
             case E:  
                 this.direction = Direction.S;  
                 break;  
             }  
         }  
     }  
 }  
    
public class Main {  
    
     public static String collision(Robot[] robots, Robot r, int x_dim, int y_dim) {  
        int num = robots.length;  
         if (r.x <= 0 || r.x > x_dim || r.y <= 0 || r.y > y_dim) {  
             return "Robot " + r.id + " crashes into the wall";  
         }  
         for (int i = 0; i < num; i++) {  
             if (r.x == robots[i].x && r.y == robots[i].y  
                     && r.id != robots[i].id) {  
                 return "Robot " + r.id + " crashes into " + "robot " 
                         + robots[i].id;  
             }  
         }  
         return "OK";  
     }  
    
     public static void main(String[] args) {  
    
         Scanner in = new Scanner(System.in);  
         int rounds = in.nextInt();  
         for (int i = 0; i < rounds; i++) {  
             int x_dimension = in.nextInt();  
             int y_dimension = in.nextInt();  
             int num_robots = in.nextInt();  
             String response = "OK", temp;  
             Robot robots[] = new Robot[num_robots];  
             int num_ins = in.nextInt();  
             for (int j = 1; j < num_robots + 1; j++) {  
                 robots[j - 1] = new Robot(j, in.nextInt(), in.nextInt(), in  
                         .next());  
             }  
             for (int k = 0; k < num_ins; k++) {  
                 int r_id = in.nextInt();  
                 String command = in.next();  
                 int num_iteration = in.nextInt();  
                 Robot robot = robots[r_id - 1];  
                 for (int m = 0; m < num_iteration; m++) {  
                     robot.move(command);  
                     temp = collision(robots, robot, x_dimension, y_dimension);  
                     if (response.startsWith("O") && !temp.startsWith("O"))  
                         response = temp;  
                 }  
             }  
             System.out.println(response);  
         }  
     }  
    
 } 


							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
            String s=""; int[] l1,l2;
        while(stdin.ready()){
            l1=new int[26];l2=new int[26];
            s=stdin.readLine().trim();
            for(int i=0;i< s.length();i++){
                l1[(int)(s.charAt(i)-'a')]++;
            }
            s=stdin.readLine().trim();
            for(int i=0;i< s.length();i++){
                l2[(int)(s.charAt(i)-'a')]++;
            }
            for(int i=0;i< 26;i++){
                l1[i]=Math.min(l1[i], l2[i]);
            }
            for(int i=0;i< 26;i++){
                for(int j=0;j< l1[i];j++){
                    System.out.print((char)(i+'a'));
                }
            }
            System.out.print("n");
        }
    }
}
							

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

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

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 
    double x1,y1,x2,y2,x3,y3,x4,y4,x5=0,y5=0;
    while(sc.hasNext())
    {
       x1=sc.nextDouble();
       y1=sc.nextDouble();
       x2=sc.nextDouble();
       y2=sc.nextDouble();
       x3=sc.nextDouble();
       y3=sc.nextDouble();
       x4=sc.nextDouble();
       y4=sc.nextDouble();
       if(x1==x3&&y1==y3)
        {
            x5=x4-x3+x2;
            y5=y4-y3+y2;
        }
        else if(x1==x4&&y1==y4)
        {
            x5=x2-x1+x3;
            y5=y2-y1+y3;
        }
        else if(x2==x4&&y2==y4)
        {
            x5=x1-x2+x3;
            y5=y1-y2+y3;
        }
        else if(x2==x3&&y2==y3)
        {
            x5=x1-x2+x4;
            y5=y1-y2+y4;
        }
        System.out.printf("%4.3f %4.3fn",x5,y5);
    }
 }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{//1979
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    int a=Integer.parseInt(in.readLine());
    int[] arr=new int[a+1];
    for(int i=1;i<=a;i++)
        arr[i]=Integer.parseInt(in.readLine());
    Arrays.sort(arr);
    double t;
    if(a%2==0)t=arr[a/2]/2.0+arr[a/2+1]/2.0;
    else t=arr[(a+1)/2];
    System.out.printf("%.1f",t);
  }
}

							

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

/* @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 a,b;
       a=sc.nextInt();
       b=sc.nextInt();
    int p1,p2,p3,d1,d2,d3;
    p1=(int)Math.sqrt(a*1.0);
    if(p1*p1< a) p1++;
    d1=(int)Math.sqrt(b*1.0);
    if(d1*d1< b) d1++;
    int v1=(p1-1)*(p1-1);
    int v2=(d1-1)*(d1-1);
    p2=(a-v1+1)/2;
    d2=(b-v2+1)/2;
    p3=(p1*p1-a)/2+1;
    d3=(d1*d1-b)/2+1;
    int ans=Math.abs(p1-d1)+Math.abs(p2-d2)+Math.abs(p3-d3);
    System.out.printf("%dn",ans);
 }
}
							

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

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

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

  int a[]=new int[3],b[]=new int[3],c[]=new int[3],d[]=new int[3],p,q,r,s;
  int maxn;
  double sum;

    int i,flag;
    maxn=100000001;
    while(sc.hasNext())
    {
        p=sc.nextInt();
        q=sc.nextInt();
        r=sc.nextInt();
        s=sc.nextInt();

        a[0]=p;a[1]=s;a[2]=r-s;b[0]=r;b[1]=q;b[2]=p-q;
        for(i=0;i< 3;i++)c[i]=d[i]=2;
        sum=1;flag=1;
        while(flag!=0)
        {
            flag=0;
            for(i=0;i< 3;i++)
            {
                if(sum< maxn&&c[i]<=a[i])
                {
                    flag=1;
                    sum*=c[i]++;
                }    
                if(sum>0.00000001&&d[i]<=b[i])
                {
                    flag=1;
                    sum/=d[i]++;
                }    
            }    
        }    
        System.out.printf("%.5fn",sum);
    }    
   }
}    

							

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

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;


int main()
{
char mine[15][15];
char touch[15][15];
char board[15][15];
int i,j,n,num=0;
bool flag=false;
scanf("%d",&n);
for(i=0;i<n;i++)
   scanf("%s",mine[i]);
for(i=0;i<n;i++)
   scanf("%s",touch[i]);
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
   {
    if(touch[i][j]=='x')
    {
     if(mine[i][j]=='*')
     {
      flag=true;
      board[i][j]='*';
     }
     else if(mine[i][j]=='.')
     {
      if((j-1)>=0&&mine[i][j-1]=='*')
       num++;
      if((j+1)<n&&mine[i][j+1]=='*')
       num++;
      if(i-1>=0)
      {
       if((j-1)>=0&&mine[i-1][j-1]=='*')
        num++;
       if(mine[i-1][j]=='*')
        num++;
       if((j+1)<n&&mine[i-1][j+1]=='*')
        num++;
      }
      if(i+1<n)
      {
       if((j-1)>=0&&mine[i+1][j-1]=='*')
        num++;
       if(mine[i+1][j]=='*')
        num++;
       if((j+1)<n&&mine[i+1][j+1]=='*')
        num++;
      }

      board[i][j]=num+48;
      num=0;
     }
    }
    else if(touch[i][j]=='.')
     board[i][j]='.';
   }
if(flag)
{
   for(i=0;i<n;i++)
    for(j=0;j<n;j++)
     if(mine[i][j]=='*')
      board[i][j]='*';
}
for(i=0;i<n;i++)
{
   for(j=0;j<n;j++)
    printf("%c",board[i][j]);
   printf("n");
}
system("pause");
return 0;
}
							

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

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


public class Main{
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  double x1 = in.nextDouble();
  double y1 = in.nextDouble();
  double x2 = in.nextDouble();
  double y2 = in.nextDouble();
  //double r1 = 0;
  //double r2 = 0;
  //double d3 = 0;
  boolean canEscape = false;
  while(in.hasNext())
   {
    String s1 = in.next();
    in.skip(" ");
    String s2 = in.nextLine();
    //in.nextLine();
    double x3 = Double.parseDouble(s1);
    double y3 = Double.parseDouble(s2);
    double d1 = (x3 - x1)*(x3 - x1) + (y3 - y1)*(y3 - y1);
    double d2 = (x3 - x2)*(x3 - x2) + (y3 - y2)*(y3 - y2);
    if(d2 > 4 *  d1)
    {
      canEscape = true;
      System.out.print("The gopher can escape through the hole at ("+s1+','+s2+").");
       break;
    }
    }

    if(canEscape == false)
    System.out.println("The gopher cannot escape.");
  }
}

							

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

#include<iostream>
#include<string>
#include<map>
#include<cstdlib>
#include<algorithm>
using namespace std;

char ss[21];
int a[21];


int main()
{
map<char,int>m;
m['B']=1;     m['A']=0;
m['F']=1;     m['E']=0;
m['P']=1;     m['I']=0;
m['V']=1;     m['O']=0; 
m['C']=2;     m['U']=0;
m['G']=2;     m['H']=0;
m['J']=2;     m['W']=0;
m['K']=2;     m['Y']=0;
m['Q']=2;
m['S']=2;
m['Z']=2;
m['X']=2;
m['D']=3;
m['T']=3;
m['L']=4;
m['M']=5;
m['N']=5;
m['R']=6;
int i,j,len,t;
while(scanf("%s",ss)!=EOF)
{
   len=strlen(ss);
   j=0;
   for(i=0;i<len;i++)
   {
    if(m[ss[i]]==0)
     continue;
    t=m[ss[i]];
    if(j==0)
     a[j++]=t;
    else
    {
     if((a[j-1]!=t)||m[ss[i-1]]==0)                            
      a[j++]=t;
     else
      continue;
    }
   }
   for(i=0;i<j;i++)
    printf("%d",a[i]);
   printf("n");
}
system("pause");
return 0;
}
							

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

#include <cstdio>
const int M = 505, INF = 1000000000;
int mp[M][M], n, m, f[105];

int main () {
 int i, j, k, x, y, d, u, ans, Max, Min;
 while ( scanf("%d %d", &m, &n) != EOF ) {
  for ( i = 1; i <= m; i++ )
   scanf("%d", f + i);

  for ( i = 1; i <= n; i++ ) {
   for ( j = 1; j <= n; j++ )
    mp[i][j] = INF;
   mp[i][i] = 0;
   }

  while ( scanf("%d %d %d", &x, &y, &d) != EOF ) {
   mp[x][y] = mp[y][x] = d;
   }
//  for ( i = 1; i <= n; i++ ) {
//   for ( j = 1; j <= n; j++ )
//    printf("%d ", mp[i][j]);
//   printf("n");
//   }
//  printf("n");

  for ( k = 1; k <= n; k++ )
   for ( i = 1; i <= n; i++ )
    for ( j = 1; j <= n; j++ )
     if ( mp[i][j] > mp[i][k] + mp[k][j] )
      mp[i][j] = mp[i][k] + mp[k][j];

//  for ( i = 1; i <= n; i++ ) {
//   for ( j = 1; j <= n; j++ )
//    printf("%d ", mp[i][j]);
//   printf("n");
//   }
//  printf("n");

  ans = INF;
  for ( i = 1; i <= n; i++ ) {
   f[m+1] = i;
   Max = 0;
   for ( j = 1; j <= n; j++ ) {
    Min = INF;
    for ( k = 1; k <= m + 1; k++ ) {
     if ( mp[j][ f[k] ] < Min )
      Min = mp[j][ f[k] ];
     }
    if ( Min > Max ) Max = Min;
    }
   if ( Max < ans ) { ans = Max; u = i;}
   }
  printf("%dn", u);
  }
 }
							

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

//* @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();
  int[] arrx=new int[a];
  int[] arry=new int[a];

  for(int i=0;i< a;i++)
  {
   arrx[i]=in.nextInt();
   arry[i]=in.nextInt();
  }
  int max=0;
  for(int i=0;i< a-2;i++)
  {
   for(int j=i+1;j< a-1;j++)
   {
    int c=0;
    for(int u=j+1;u< a;u++)
    {
     if((arrx[i]-arrx[u])*(arry[i]-arry[j])==(arrx[i]-arrx[j])*(arry[i]-arry[u])) c++;
    }
    if(c>max) max=c;
   }
  }
  System.out.println(max+2);
 }
}
							

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

#include <iostream>
#include <string>
#include <vector>

using namespace std;
typedef vector<string>::size_type VST;
vector<string> v;
char Stack[1000];
int pos[1000];
int vpos[1000];
int top = 0;
void process()
{
    bool bEnd;

    for (VST i = 0;i < v.size();i++)
    {
        if (v[i].empty())
        {
            if (top != 0)
            {
                while (top--)
                {
                    v[vpos[top]].erase(pos[top],1);
                }
                top++;
            }
            continue;
        }

        string &s = v[i];
        for (int j = 0;j < s.size();j++)
        {
            if (s[j] == '"')
            {
                if (top == 0)
                {
                    Stack[top] = '"';
                    pos[top] = j;
                    vpos[top++] = i;
                }
                else
                {
                    s[j] = 39;
                    s.insert(j,1,39);
                    v[vpos[--top]][pos[top]] = 96;
                    v[vpos[top]].insert(pos[top],1,96);
                    if(vpos[top] == i)
                        j += 2;
                    else
                        j += 1;
                }
                continue;
            }
            else if (s[j] == '\')
            {
                if (j + 1 < s.size() && s[j + 1] == '"')
                {
                    j += 2;
                    continue;
                }

                if (s.substr(j,4) == string("\par") || s.substr(j,9) == string("\endinput"))
                {
                    if (top != 0)
                    {
                        while (top--)
                        {
                            v[vpos[top]].erase(pos[top],1);
                        }
                        top++;
                        j = 0;
                        continue;
                    }
                }
            }
        }
    }
}

int main()
{
    string str;
    while (1)
    {
        getline(cin,str,'n');
        v.push_back(str);
        if (str.find("\endinput") != string::npos)
            break;
    }
    process();
    for(int i = 0;i < v.size();i++)
        cout<<v[i]<<endl;
    return 0;
}

/*
Preparing an article
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 431  Accepted: 93 

Description

TeX is the leading typesetting system for mathematics, science, and engineering and has been adopted as standard by the American Mathematical Society. LaTeX was developed later by Leslie Lamport. It is based on TeX and provides a set of higher level commands for production of complex documents. In TeX or LaTeX, any text editor program may be used to enter and modify the input text. The source text contains the actual text as well as formatting commands beginning with . Commands are delimited by any non-alphabetic character. One example of beautification by TeX is that it uses `` (two left-single-quotes) and '' (two right-single-quotes) to delimit quotations, rather than the mundane " (one double quote) which is provided by most keyboards. Keyboards typically do not have an oriented double-quote, but they do have a left-single-quote (`) and right-single-quote ('). TeX lets the user type two left-single-quotes (``) to create a left-double-quote and two right-single-quotes ('') to create a right-double-quote. Now, you have a text only file containing at most 250 lines at most 80 symbols each, as source or input, and you want to use TeX to beautify it. Rather than doing everything by hand, as the first step of automation you want to convert the quotes into the TeX format by using a program. This program will convert the text with double-quotes (") into an identical text except that double quotes have been replaced by the two-character sequences required by TeX for delimiting quotations with oriented double-quotes. The double-quote (") characters should be replaced appropriately by proper double single quotes depending on whether it is an opening or closing quotation mark. Question of nested quotations does not arise. The first " must be replaced by ``, the next by '', the next by ``, the next by '', and so on. An opening double quote must have its closing quote in the same paragraph. If a match is not found in the same paragraph for an opening quote, this quote has to be deleted. Paragraph ends in the source text are marked either by at least one blank line, or a par command or both. Your program must also be careful about the " command which is used to produce umlaut or dieresis ("e leads to ?). These are to be left untouched.
Input

Input will consist of several lines of text containing a number of double quotes ("), as well as some TeX commands. End of input will be marked by an endinput command.
Output

Output will be an exact replica of the input, except the double quotes are to be modified according to the rules described above.
Sample Input

There is no "q in this sentence. par 
"Talk child," said the unicorn. 

She s"aid, "thinspace `Enough!', he said." 
endinput 

Sample Output

There is no q in this sentence. par 
``Talk child,'' said the unicorn. 

She s"aid, ``thinspace `Enough!', he said.'' 
endinput 

Hint

Double-quote (") has ASCII code 34, 
left-single-quote (`) has ASCII code 96, 
right-single-quote (') has ASCII code 39.

*/
							

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int x,i,n=10;int a[10002];a[1]=0;memset(a,0,sizeof(a));
while(n--)
{
  
   scanf("%d",&x);
   for(i=2;x!=1;i++)
   {
    while(x%i==0&&x!=1)
    {
     a[i]++;x/=i;
    }
    if(x==1)
     break;
   }
}
x=1;
for(i=2;i<10000;i++)
{
   if(a[i]!=0)
   {
    x=x*(1+a[i])%10;
   }
}
printf("%dn",x);
return 0;
}
							

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

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

 public class Main {

     public static void main(String[] args) throws NumberFormatException,
             IOException {
         BufferedInputStream read = new BufferedInputStream(System.in);
         byte[] b = new byte[5000007];
         read.read(b);
         String s = "";
         int index = 0;
         while (b[index] != 'r') {
             s += (char) b[index];
             index++;
         }
         int n = Integer.parseInt(s);
         byte[] c = new byte[n];
         for (int i = 0; i < n; i++) {
             index++;
             index++;
             c[i] += b[index] - 48;
             index++;
             index++;
             c[i] += b[index] - 48;
             index++;
         }
         int cf = 0;
         for (int i = n - 1; i >= 0; i--) {
             c[i] += cf;
             if (c[i] >= 10) {
                 cf = 1;
                 c[i] += 38;
             } else {
                 cf = 0;
                 c[i] += 48;
             }
         }
         System.out.write(c);
         System.out.println();
     } 
}

							

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

//* @author: 82638882@163.com
import java.util.Scanner;
class Main
{
 public static void main(String[] args)
 {
   Scanner in=new Scanner(System.in);
   int n=in.nextInt();
   double a0=in.nextDouble();
   double an=in.nextDouble();
   double total=n*a0+an;
   double sum=0;
   int u=n;
   for(int i=0;i< n;i++,u--)
    sum+=in.nextDouble()*u;
   double ans=(total-sum*2)/(n+1);
   System.out.printf("%.2f",ans);
 }
}
							

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

#include <stdio.h>
#include <math.h>
 
const double eps = 1e-4;
const double pi = acos(-1.0);
 
struct TPoint 
{
        double x, y;
}p[60], a[60];
double angle[60];
 
double multi(TPoint p1, TPoint p2, TPoint p0)
{
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
 
TPoint fine_a2(TPoint a1, TPoint m, double angle1)
{
    TPoint a2;
    double r, angle2, angle3;
    r = sqrt((a1.x - m.x) * (a1.x - m.x) + (a1.y - m.y) * (a1.y - m.y));
    angle2 = acos((a1.x - m.x) / r);
    if(a1.y < m.y) {
        if(angle2 <= pi / 2) angle2 = -angle2;
        if(angle2 > pi / 2) angle2 = 3 * pi / 2 - (angle2 - pi / 2);
    }
    angle3 = angle2 - angle1;
    a2.x = m.x + r * cos(angle3);
    a2.y = m.y + r * sin(angle3);
    if(multi(m, a2, a1) < 0) return a2;
    angle3 = angle2 + angle1;
    a2.x = m.x + r * cos(angle3);
    a2.y = m.y + r * sin(angle3);
    if(multi(m, a2, a1) < 0) return a2;    
}
 
int main()
{
    int n, i, j;
    while(scanf("%d", &n) != EOF){
        for(i = 0;i < n;i++){
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        for(i = 0;i < n;i++){
            scanf("%lf", &angle[i]);
            angle[i] = angle[i] * pi / 180;
        }
        a[0].x = 0;
        a[0].y = 0;
        while(1){
            for(i = 1;i <= n;i++){
                a[i] = fine_a2(a[i - 1], p[i - 1], angle[i - 1]);
            }
            if(fabs(a[n].x - a[0].x) <= eps  
                    && fabs(a[n].y - a[0].y) <= eps) break;
            else {
                a[0].x = (a[0].x + a[n].x) / 2;
                a[0].y = (a[0].y + a[n].y) / 2;
            }
        }
        for(i = 0;i < n;i++){
            printf("%.0lf %.0lfn", a[i].x, a[i].y);
        }        
    }
    return 0;
}
							

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

#include <iostream>
#include <cstring>
using namespace std;
int N,K;
bool map[1010][1010];
bool visited[1010];
bool dfs(int n,int step)
{
    bool z = false;
    visited[n] = true;
    bool HasPath = false;
    for(int i = 1;i <= N;i++)
    {
        if(!visited[i] && map[n][i])
        {
            HasPath = true;
            z = dfs(i,step+1);
            if(step % 2 == 0)
            {
                if(z)
                    return true;
            }
            else
            {
                if(!z)
                    return false;
            }
        }
    }
    if(!HasPath)
    {
        if(step % 2 == 0)
            return false;
        else
            return true;
    }
    return z;
}

int main()
{
    while(cin>>N>>K)
    {
        int x,y;
        for(int z = 0;z < N - 1;z++)
        {
            cin>>x>>y;
            map[x][y] = map[y][x] = true;
        }

        bool Yes = false;
        int i;
        for(i = 1;i <= N;i++)
        {
            memset(visited,0,sizeof(visited));
            if(map[K][i])
            {
                visited[K] = true;
                bool n = dfs(i,1);
                if(n)
                {
                    Yes = true;
                    break;
                }
            }
        }
        if(Yes)
            cout<<"First player wins flying to airport "<<i<<endl;
        else
            cout<<"First player loses"<<endl;

        for(int i = 0;i < 1000;i++)
        {
            for(int j = 0;j < 1000;j++)
                map[i][j] =  false;
        }
    }
    return 0;
}

/*
A funny game
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 1281  Accepted: 510 

Description

There are several airports in one country, and there are flights between some of them. One can fly from any airport to any other, probably with some changes. For any pair of airports there exists only one sequence of flights that connects them. 

Two terrorists play a game. They make moves in turn. Each move consists of the following operations. A player mines an airport, chooses a flight and flies away together with his colleague. After the take-off he actuates a radio-controlled fuse. As a result the airport that the terrorists have just left is destroyed, and all the flights to and from this airport are no longer possible. After the aircraft lands the other player makes his move, and so forth. One loses if one cannot make a move. 

Given an initial list of flights and the number of an airport where the terrorists are at the start of the game, write a program which would determine who wins if the terrorists play a perfect game (each chooses the best move).
Input

The first line of an input contains two integers: N and K separated with a space. Here N is the number of airports (N <= 1000) and K is the number of an airport, which is the starting point of the game (1 <= K<= N). The next n-1 lines of the file contain pairs of integers separated with a space. These integers are numbers of airports, connected with a flight (all the flights are symmetric and are mentioned only once). There are at most 20 flights to each airport. Input data are always correct.
Output

If the player who starts the game wins, the program should write: "First player wins flying to airport L" where L is the number of an airport to which the players should fly first. If there are more than one such airports, the program should find one of them that has the minimal number. Otherwise the program should write "First player loses".
Sample Input

4 3
3 2
3 1
1 4

Sample Output

First player wins flying to airport 2


*/
							

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

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

/////////////////////////
#define Type double /*�������*/
/////////////////////////


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

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

const double pi=3.14159265359;

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

point crosspoint(line l1,line l2)
{Type p1=cheng(l2.a,l1.a,l2.b),
      p2=cheng(l2.a,l2.b,l1.b);
if(p1+p2==0)return l1.a;

point c;
c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
return c;
}

/////////////////////////////////////////////////////////
int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}


/////////////////////////////////////////////////////
#define CONVEX_SIZE 50000
int stack[CONVEX_SIZE],sign[CONVEX_SIZE];


int convex(point *p,int n,point *wall)
{int i;int st;Type h;

if( n < 3 )
{
    for( i=0; i<n; i++ )
    wall[i] = p[i];
     return n;
 }    

st=0;
stack[st++]=0;
stack[st++]=1;

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

sign[1]=1;
i=2;

while(i<n)
    {while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ > /**/ 0)
                                                         //��͹�����Ҳ�㣬use '>'
            {st--;if(h)sign[stack[st]]=0;}
    stack[st++]=i;sign[i]=1;i++;
    }

i--;

while(i>=0)
    {while(sign[i])i--;
    
     while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ > /**/ 0)st--;
     
     stack[st++]=i;
     i--;
    }
st--;
if(wall){for(i=0;i<st;i++)wall[i]=p[stack[i]];}
return st;
}
/////////////////////////////////
point p[50001], pt[50001];
int n,c;
void doit()
{
    int i, j;
    double up=-10000, down=10000, s;   
    sort( p, n );
    n = convex( p, n, pt );    
    for( i=0; i<n; i++ )
    {
        j = ( i==n-1 ? 0 : i+1 );        
        if( pt[i].x == c ) s = pt[i].y;
        else if( ( pt[i].x - c ) * ( pt[j].x - c ) < 0 )
            s = pt[i].y + ( c - pt[i].x ) * ( pt[j].y - pt[i].y ) / ( pt[j].x - pt[i].x );
        else continue;            
        if( up < s ) up = s;
        if( down > s ) down = s;
    }    
    printf( "%.3lf %.3lfn", down, up );
}
bool init()
{
    int i;
    if( scanf( "%d %d", &n, &c ) != 2 )
    return false;
    
    for( i=0; i<n; i++ )
    scanf( "%lf", &p[i].x );
    
    for( i=0; i<n; i++ )
    scanf( "%lf", &p[i].y );
    
    return true;
}
int main()
{
    while( init() )
        doit();   
    return 0;
}        


							

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

#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
#define null 0
const int size=510;
bool w[size][size]; 
int maxmatch(int n,int m,bool w[][size],int *p)
{
       int p_n[size];
       int p_m[size];
       bool sign[size];
       int q[size],from[size],s,t;
       int i,j,link,now,h;
       for(i=0;i<n;i++)p_n[i]=-1;
       for(j=0;j<m;j++)p_m[j]=-1;
       for(i=0;i<n;i++)
       if(p_n[i]==-1)
       {
              for(j=0;j<m;j++)sign[j]=0;                         
              s=1;link=-1;
              from[0]=-1;
              q[0]=size-1;
              p_m[size-1]=i;
              for(t=0;t<s;t++)
              {
                     now=q[t];
                     for(j=0;j<m;j++)
                     {
                            if(w[p_m[now]][j]!=null&&sign[j]==0)
                            {
                                   sign[j]=1;
                                   q[s]=j;
                                   from[s++]=t;                                
                                   if(p_m[j]==-1)
                                   {
                                          link=s-1;
                                          break;
                                   }
                            }
                     }                  
                     if(j<m)break;
              }
              if(t<s)
              {
                     while(from[link]!=-1)
                     {
                            h=from[link];
                            p_m[q[link]]=p_m[q[h]];                           
                            p_n[p_m[q[h]]]=q[link];
                            link=h;

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

              if(p_n[i]>=0)an++;

       }  
       return an;

}
vector< int > e[500];
bool sign[500];
void find( int s, int r )
{
    int i, t;
    sign[s] = 1;
    if( s != r ) w[r][s] = 1;

    for( i=0; i<e[s].size(); i++ )
        if( !sign[ t=e[s][i] ] )
            find( t, r );

}
int main()
{
    int n, m, i, j, a, b, ans, k;
    while( scanf( "%d %d", &n, &m ) == 2 )
    {
        if( n == 0 && m == 0 ) break;
        memset( w, 0, sizeof( w ) );
        for( i=0; i<n; i++ )
            e[i].clear();
        for( i=0; i<m; i++ )
        {
            scanf( "%d %d", &a, &b );
            w[a-1][b-1] = 1;
            e[a-1].push_back( b-1 );
        }
        for( k=0; k<n; k++ )
        {
            memset( sign, 0, n );
            find( k, k );
        }
        ans = n - maxmatch( n, n, w, 0 );
        printf( "%dn", ans );

    }

    return 0;
}


							

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

//* @author 
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
     
  int data[]=new int[100000];
  int dp[]=new int[100000];   
  int n;
  Scanner in=new Scanner(System.in);   
    while((n=in.nextInt())!=0){   
           
        int sum = 0, tmp = -999999999;   
        for(int i = 0; i < n; i++){   
            data[i]=in.nextInt();   
            sum += data[i];   
            if(sum > tmp)   
                tmp = sum;   
            dp[i] = tmp;   
            if(sum < 0)   
                sum = 0;   
        }   
        sum = 0;   
        int ans = -999999999;   
        for(int i = n-1; i > 0; i--){   
            sum += data[i];   
            if(dp[i-1]+sum > ans)   
                ans = dp[i-1]+sum;   
            if(sum < 0)   
                sum = 0;   
        }   
        System.out.printf("%dn", ans);   
    }   
 }
}


							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
   TreeSet< Long> t=new TreeSet< Long>();
   Scanner in=new Scanner(System.in);
   int[] arr=new int[10000001];
   arr[0]=1;
   int k1=0,k2=0;
   for(int i=1;i< 10000001;i++)
    {
    int y1=arr[k1]*2+1;
    int y2=arr[k2]*3+1;
    arr[i]=Math.min(y1, y2);
    if(arr[i]==y1) k1++;
    if(arr[i]==y2) k2++;
     }
    while(in.hasNext())
    {
    int a=in.nextInt();
    System.out.println(arr[a-1]);
    }
  }
}
							

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

//* @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();
    for(int i=0;i< a;i++)
    {
          long x=in.nextLong();
      x=in.nextLong()-x;
      long b=(long)Math.sqrt(x);
      long ans=-1;
      if(b==0) ans=0;
      else if(b*b==x)ans=2*b-1;
      else if(x<=b*b+b)ans=2*b;
      else ans=2*b+1;
      System.out.println(ans);
     }
  }
}
							

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

#include<iostream>
#include"string.h"
#include"stdlib.h"
using namespace std;
int main()
{
char a[110],b[110],ar[110],br[110];
int n1,r1,n2,r2,k=0,i,g1,g2,r;


cin>>a>>b;
n1=n2=strlen(a);
r1=0;r2=0;
g1=0;g2=0;

    while(k<1000)
    {if(g1==n1){if(r1==0){cout<<"John wins."<<endl;break;}for(i=r1-1;i>=0;i--)a[i]=ar[i];n1=r1;r1=0;g1=0;}
     if(g2==n2){if(r2==0){cout<<"Jane wins."<<endl;break;}for(i=r2-1;i>=0;i--)b[i]=br[i];n2=r2;r2=0;g2=0;}
     ar[r1++]=a[g1++];br[r2++]=b[g2++];
     if(ar[r1-1]==br[r2-1]) {r=rand()/99%2;
         if(r==0){for(i=0;i<r2;i++)ar[r1+i]=br[i];r1+=r2;r2=0;
        cout<<"Snap! for Jane: ";for(i=r1-1;i>=0;i--)cout<<ar[i];cout<<endl;
        }
            
     else {for(i=0;i<r1;i++)br[r2+i]=ar[i];r2+=r1;r1=0;
        cout<<"Snap! for John: ";for(i=r2-1;i>=0;i--)cout<<br[i];cout<<endl;}
     }
     k++;}
    
     if(k==1000)cout<<"Keeps going and going ..."<<endl;


return 1;
}
							

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

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


const double eps=1e-7;

struct cir
{
    double x,y,r;
}c[1000];

inline bool edge(cir &a,cir &b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))<=a.r+b.r;
}

int n;

bool init()
{
    int i;
    
    if(scanf("%d",&n)!=1)return false;

    for(i=0;i<n;i++)
        scanf("%lf %lf %lf",&c[i].x,&c[i].y,&c[i].r);

    return true;
}
inline bool touch_up(cir &a)
{
    return a.y+a.r>=1000;
}

inline bool touch_down(cir &a)
{
    return a.y-a.r<=0;
}
inline bool touch_left(cir &a)
{
    return a.x-a.r<=0;
}
inline bool touch_right(cir &a)
{
    return a.x+a.r>=1000;
}
double f(cir &a,double x)
{
    return a.y-sqrt(a.r*a.r-(a.x-x)*(a.x-x));
}
bool sign[1000];
double l,r;
bool search(int s)
{
    double temp;
    sign[s] = true;
    if(touch_down(c[s]))
        return false;
    if(touch_left(c[s]))
    {
        temp=f(c[s],0);
        if(temp<l)l=temp;
    }
    if(touch_right(c[s]))
    {
        temp=f(c[s],1000);
        if(temp<r)r=temp;
    }
    for(int i=0;i<n;i++)
    {
        if(!sign[i]&&edge(c[s],c[i]))
            if(!search(i))return false;
    }
    return true;
}
void doit()
{
    int i;
    for(i=0;i<n;i++)
        sign[i] = false;
    
    l=1000,r=1000;
    
    for(i=0;i<n;i++)
    if(!sign[i]&&touch_up(c[i]))
    {
        if(!search(i))
        {
            printf("Bill will be bitten.n");
            return ;
        }
    }
    
    printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).n",l,r);
}
int main()
{
    while(init())
    {
        doit();
    }
    return 0;
}
							

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

import java.io.PrintWriter;  

 import java.util.Scanner;   
    
public class Main {  
     
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);  
   PrintWriter out = new PrintWriter(System.out);  
  int s,d,result;  
   while(scn.hasNext()){  
    result = 0;  
    s = scn.nextInt();  
    d = scn.nextInt();  
    if(d > 4 * s){  
     result = 10*s - 2*d;  
    }else if( 2*d > 3*s){  
     result = 8*s - 4*d;  
    }else if( 3*d > 2*s){  
     result = 6*s - 6*d;  
    }else if( 4*d > s){  
     result = 3*s - 9*d;  
    }  
   out.println("" + (result >0 ?result:"Deficit"));  
  }  
  out.flush();  
 }   
    
}  


							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[][] map=new int[10][10];
 static int[][]    p=new int[4][4];
 public static void main(String[] args)throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
   String s=in.readLine();
   if(s.equals("ENDOFINPUT"))break;
   String[] ss;
   for(int i=0;i< 4;i++)
   {
    ss=in.readLine().split(" ");
    for(int j=0;j< 4;j++)
        p[i][j]=Integer.parseInt(ss[j]);
   }
   in.readLine();
   for(int i=1;i< 10;i++)
     for(int j=1;j< 10;j++)
         map[i][j]=0;
   f();
   for(int i=1;i< 10;i++)
    map[i][i]=0;        
   while(true)
   {
      boolean qq=false;
      for(int i=1;i< 10;i++)
    for(int j=1;j< 10;j++)
          for(int k=1;k< 10;k++)
        if(map[i][j]==1&&map[j][k]==1&&map[i][k]==0)
        {
        map[i][k]=1;
        qq=true;
        }
      if(!qq)break;
    }
    boolean bb=true;
    for(int i=1;i< 10;i++)
    if(map[i][i]==1){
          bb=false;
      break;
    }
    if(bb) System.out.println("THESE WINDOWS ARE CLEAN");
    else System.out.println("THESE WINDOWS ARE BROKEN");
   }
 }

  static void f()
  {
        int x;
     x=p[0][1];
    map[x][1]=1;
    map[x][2]=1;
    x=p[0][2];
    map[x][2]=1;
    map[x][3]=1;
    x=p[1][0];
    map[x][1]=1;
    map[x][4]=1;
    x=p[2][0];
    map[x][4]=1;
    map[x][7]=1;
    x=p[1][3];
    map[x][3]=1;
    map[x][6]=1;
    x=p[2][3];
    map[x][6]=1;
    map[x][9]=1;
    x=p[3][1];
    map[x][7]=1;
    map[x][8]=1;
    x=p[3][2];
    map[x][8]=1;
    map[x][9]=1;
    x=p[1][1];
    map[x][1]=1;
    map[x][2]=1;
    map[x][4]=1;
    map[x][5]=1;
    x=p[1][2];
    map[x][2]=1;
    map[x][3]=1;
    map[x][5]=1;
    map[x][6]=1;
    x=p[2][1];
    map[x][4]=1;
    map[x][5]=1;
    map[x][7]=1;
    map[x][8]=1;
    x=p[2][2];
    map[x][5]=1;
    map[x][6]=1;
    map[x][8]=1;
    map[x][9]=1;
   }
}
							

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

#include"iostream"
#include"algorithm"
using namespace std;
char *size="SMLXT";
int find( char c )
{
    char *q = size;

    while( *q != c )
        q++;

    return q - size;
}
struct person
{
    int b,e;
}p[20];
bool cmp( person p1, person p2 )
{
    return p1.b < p2.b || ( p1.b == p2.b && p1.e < p2.e );
}
int main()
{
    int i, j, n, s[20];
    char t[15],a,b;
    cin>>t;
    while( cin>>n )
    {
        for( i=0; i<n; i++ )
        {
            cin>>a>>b;
            p[i].b = find( a );
            p[i].e = find( b );
        }
        for( i=0; i<5; i++ )
            cin>>s[i];    
        sort( p, p+n, cmp );

        for( i=0,j=0; j<n; j++  )
        {
            while( i < 5 && ( p[j].b > i || s[i] == 0 ) )
                i++;

            if( i >= 5 || p[j].e < i )
                break;
            s[i]--;
        }
        if( j == n ) cout<<"T-shirts rock!n";
        else cout<<"I'd rather not wear a shirt anyway...n";

        cin>>t;
        cin>>t;
    }

    return 0;
}



							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *poj2583 easy  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int f0 = scan.nextInt();   
            int f1 = scan.nextInt();   
            int f2 = scan.nextInt();   
            int c = f0;   
            int a = (f2 - 2 * f1 + f0) / 2;   
            int b = f1 - c - a;   
            int f3 = a * 9 + b * 3 + c;   
            int f4 = a * 16 + b * 4 + c;   
            int f5 = a * 25 + b * 5 + c;   
            System.out.println(f3 + " " + f4 + " " + f5);   
        }   
  
    }   
}  


							

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

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

struct point
{
    int x,y,z;
}b[20],f[20];

inline int sq_dis( point a, point b )
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z);
}

int main()
{
    int l,w,d,n,m,ans,i,j;
    char t[100],c;

    cin>>t;
    while( cin>>l>>w>>d )
    {

        m = 0;
        while( 1 )
        {
            cin>>b[m].x>>c>>b[m].y>>c>>b[m].z;
            if( b[m].z > d ) b[m].z = d;

            m++;
            if( cin.peek() == 'n' ) break;
        }

        n = 0;
        while( 1 )
        {
            cin>>f[n].x>>c>>f[n].y>>c>>f[n].z;
            
            n++;
            if( cin.peek() == 'n' ) break;
        }

        ans = 0;
        for( i=0; i<n; i++ )
        for( j=0; j<m; j++ )
            if( sq_dis( f[i], b[j] ) <=1 )
            {
                ans++;
                break;
            }

        if( ans != 0 ) cout<<"AIEE, I got "<<ans<<" fish, me!n";
        else cout<<"None of dem fish blowed up!n";

        cin>>t>>t;

    }
    return 0;

}
							

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

//* @author:
import java.util.*;
public class Main {
 static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   while(sc.hasNext())
   {
       int a,b,c,d,e,i,j,k,total,s,value;
    int as=0,bs=0,cs=0,ds=0;
    double t;
       t=sc.nextDouble();
       b=sc.nextInt();
       c=sc.nextInt();
       d=sc.nextInt();
       e=sc.nextInt();
    a = (int)(t*100);
    total = 99999;
    s = 0; value = 0;

    for( i=0; i<=b && i< total && value+i*25<=a; i++ )
    {
         s += i;
      value += i*25;
      for( j=0 ; j<=c && s+j< total && value+j*10<=a; j++ )
      {
        s += j;
        value += j*10;
        for( k=0 ; k<=d && s+k< total && value+k*5<=a; k++ )
        {
        s += k;
        value += k*5;
        if( a-value<=e && s+a-value < total )
        {
          total = s+a-value;
          as=i;bs=j;cs=k;ds=a-value;
        }
        s -= k;
        value -= k*5;
        }
        s -= j;
        value -= j*10;
      }
      s -= i;
      value -= i*25;
    }
    if( total == 99999 )
    System.out.printf("NO EXACT CHANGEn" );
    else System.out.printf( "%d %d %d %dn", as, bs, cs, ds);
   }
  }
}


							

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

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


int k[20],keys[20][200],to[20][200];
int key[20];
int n,begin;

bool init()
{
    char w[100],num[100],t;
    int i,j,h;

    scanf( "%s", w );

    if( strcmp( "ENDOFINPUT", w ) == 0 )
        return false;

    scanf( "%d %d", &begin, &n );
    getchar();

    for( i=0; i<n; i++ )
    {
        k[i] = 0;
        while(1)
        {
            j=0;

            while(1)
            {
                t = getchar();
                if( t >= '0' && t <= '9' ) num[j++] = t;
                else break;
            }
            num[j] = '';
            
            to[i][ k[i] ] = atoi( num );
            keys[i][ k[i] ] = 0;

            while( t <= 'Z' && t >= 'A' )
            {
                keys[i][ k[i] ] |= 1 << (t-'A');
                t = getchar();
            }
            
            if(j)k[i]++;
            if( t == 'n' ) break;
        }
    }

    for( i=0; i<n; i++ )
    {
        key[i] = 0;
        do
        {
            t = getchar();
            if( t <= 'Z' && t >= 'A' )    key[i] |= 1 << (t-'A');
        }while( t != 'n' );
    }

    scanf( "%s", w );

    for( i=0; i<n; i++ )
    {
        for( j=0; j<k[i] && (h=to[i][j]) > i; j++ )
        {
            to[ h ][ k[h] ] = i;
            keys[ h ][ k[h] ] = keys[i][j];
            k[h]++;
        }
    }
    return true;
}

int KEY;
bool sign[20];

bool search( int s )
{
    int i;

    sign[s] = true;
    
    if( s == 0 ) return true;
    
    if( ( KEY | key[s] ) != KEY )
    {
        KEY |= key[s];
        return true;
    }

    for( i=0; i<k[s]; i++ )
    if( !sign[ to[s][i] ] && ( KEY | keys[s][i] ) == KEY )
    {
        if( search( to[s][i] ) ) return true;
    }

    return false;
}

void doit()
{
    int i;

    KEY = 0;
    while( 1 )
    {
        for( i=0; i<n; i++)
            sign[i] = false;

        if( !search( begin ) )
        {
            printf( "NOn" );
            return;
        }
        
        if( sign[0] == true )
        {
            printf( "YESn" );
            return;
        }
    }
}

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

    return 0;
}
							

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

#include"stdio.h"

char map[10][10];

int main()
{
    int i, j, m, n;

    scanf( "%*s" );
    while( scanf( "%d %d", &n, &m ) == 2 )
    {
        for( i=0; i<n; i++ )
            scanf( "%s", &map[i] );
        
        for( i=0; i<n-1; i++ )
        {
            for( j=0; j<m-1; j++ )
                printf( "%d", ( (int)map[i][j] + map[i+1][j] + map[i][j+1] + map[i+1][j+1] - (int)'0'*4 ) / 4 );

            printf( "n" );
        }
        
        scanf( "%*s" );
        scanf( "%*s" );
    }

    return 0;
}
							

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

//* @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);
    int height = 168;
    int crash = 0;
    for(int i = 0; i< 3; i++){
        int temp = in.nextInt();
        if(temp<=height){
          System.out.println("CRASH "+temp);
          crash=1;
          break;
        }
    }
    if(crash==0)
        System.out.println("NO CRASH");
 }

}

							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
 public static void main(String[] args) throws IOException {
  BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
  int[] ram=new int[1000];
  int[] reg=new int[10];
  int pos=0;
  int num=1;
  while(stdin.ready()){
   ram[pos++]=new Integer(stdin.readLine());
  }
  pos=0;
  while(ram[pos]!=100){
   switch(ram[pos]/100){
    case 0:
    if(reg[ram[pos]%10]==0){
        pos++;
    }
    else{
        pos=reg[(ram[pos]%100)/10];
    }
    break;
    case 2:
    reg[(ram[pos]%100)/10]=ram[pos]%10;
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 3:
    reg[(ram[pos]%100)/10]+=(ram[pos]%10);
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 4:
    reg[(ram[pos]%100)/10]*=(ram[pos]%10);
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 5:
    reg[(ram[pos]%100)/10]=reg[ram[pos]%10];
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 6:
    reg[(ram[pos]%100)/10]+=reg[ram[pos]%10];
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 7:
    reg[(ram[pos]%100)/10]*=reg[ram[pos]%10];
    reg[(ram[pos]%100)/10]%=1000;
    pos++;
    break;
    case 8:
    reg[(ram[pos]%100)/10]=ram[reg[ram[pos]%10]];
    pos++;
    break;
    case 9:
    ram[reg[ram[pos]%10]]=reg[(ram[pos]%100)/10];
    pos++;
    break;
   }
  num++;
 }
  System.out.println(num);        
 }
}

							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
    
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int total=0,l1=0,l2=0,i;
  int[] arr=new int[a];
  for(i=0;i< a;i++)
  {
   arr[i]=Integer.parseInt(in.readLine());
   total+=arr[i];
  }
  int u=a/2;
  int[] p1=new int[u];
  int[] p2=new int[a-u];
  Arrays.sort(arr);
  int sum1=0,sum2=0,u1,ans1=-1,ans2=-1;
  for(i=0;l1< u;i++)
   {
    p1[l1++]=arr[i];
    if(l1< u){
        p1[l1++]=arr[a-i-1];
        sum1+=arr[a-i-1];
    }
    sum1+=arr[i];
   }
   for(;l2< a-u;i++)
   {
    p2[l2++]=arr[i];
    sum2+=arr[i];
   }
   u1=Math.abs(sum1-sum2);
   ans1=sum1;
   ans2=sum2;
   for(i=0;i< 10000;i++)
   {
    int t1=(int) (Math.random()*l1);
    int t2=(int) (Math.random()*l2);
    sum1+=p2[t2]-p1[t1];
    sum2+=p1[t1]-p2[t2];
    int ww=p1[t1];
    p1[t1]=p2[t2];
    p2[t2]=ww;
    if(Math.abs(sum1-sum2)< u1)
    {
        u1=Math.abs(sum1-sum2);
        ans1=sum1;
        ans2=sum2;
    }
    }
    sum1=Math.min(ans1, ans2);
    sum2=Math.max(ans1, ans2);
    System.out.println(sum1+" "+sum2);
   }
}
							

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

//* @author: 82638882@163.com
import java.util.HashSet;
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(in.hasNext())
   {
    int a=in.nextInt();
    int[] b=new int[a];
    for(int i=0;i< a;i++)
        b[i]=in.nextInt();
    HashSet< Integer> h=new HashSet< Integer>();
    for(int i=1;i< a;i++)
        h.add(Math.abs(b[i]-b[i-1]));
    boolean bb=true;
    for(int i=1;i< a;i++)
    {
        if(!h.contains(i)){
                  bb=false;
          break;
            }
    }
    if(bb) System.out.println("Jolly");
    else System.out.println("Not jolly");
    }
  }
}
							

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

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

#include"algorithm"

using namespace std;

//////////////////////////////
#define Type double /*????????*/
//////////////////////////////

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


struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

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

line l[110];
long xmin,ymin,xmax,ymax;
double ly[110];
int n,m;

struct piece
{
    double yl,yr;
}pc[110];

void fillpiece(long x)
{
    line l1,l2;int i;
        
    m=0;
    for(i=0;i<n;i++)
    if(l[i].a.x<=x&&x+1<=l[i].b.x)
    {
        pc[m].yl=l[i].a.y+ly[i]*(x-l[i].a.x);
        pc[m].yr=l[i].a.y+ly[i]*(x+1-l[i].a.x);
        m++;
    }

}

void doit()
{
    long x,i,t;double t1,t2;
    __int64 s=0;

    for( x=xmin; x<xmax; x++ )
    {
        fillpiece(x);
        for( i=0; i<m; i+=2 )
        {
            t1=pc[i+1].yl<pc[i+1].yr?pc[i+1].yl:pc[i+1].yr;
            t2=pc[i].yl>pc[i].yr?pc[i].yl:pc[i].yr;
            
            t=(long)t1-(long)(t2+0.999999);
            if(t>0)s+=t;
        }
    }

    printf("%I64dn",s);
    return ;
}

int cmp1(line l1,line l2)
{
    double min = l1.a.x > l2.a.x ? l1.a.x : l2.a.x ,
           max = l1.b.x < l2.b.x ? l1.b.x : l2.b.x ,
           c = ( min + max ) / 2 ;
        
    return max > min && l1.a.y+(l1.b.y-l1.a.y)/(l1.b.x-l1.a.x)*(c-l1.a.x) < 
                        l2.a.y+(l2.b.y-l2.a.y)/(l2.b.x-l2.a.x)*(c-l2.a.x) ;
}

void init()
{
    xmin=2000000;ymin=2000000;ymax=-2000000;xmax=-2000000;

    int i,j;point a,b;

    for( n=0; scanf( "%lf %lf", &a.x, &a.y ) == 2 ; n++ )
    {
        xmax=xmax>a.x?xmax:a.x;
        xmin=xmin<a.x?xmin:a.x;
        ymax=ymax>a.y?ymax:a.y;
        ymin=ymin<a.y?ymin:a.y;
        
        if(n)
        {
            l[n].a=a;l[n].b=b;
        }
        b=a;
    }

    l[0].a=l[1].b;l[0].b=b;

    for(i=0;i<n;i++)
    {
        if(l[i].a.x>l[i].b.x)
            swap(l[i].a,l[i].b);
    }

    for( i=0;i<n; )
    {
        bool key;
        for( i=0,key=true; i<n&&key; i++ )
        for( j=i+1; j<n; j++ )
            if( cmp1( l[j], l[i] ) )
            {
                swap( l[j], l[i] );
                key = false;
                break;
            }
    }

    for(i=0;i<n;i++)
    {
        ly[i]=(double)(l[i].b.y-l[i].a.y)/(l[i].b.x-l[i].a.x);
    }
    ymin--;
    ymax++;
}

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




							

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

//* @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();
  ArrayList< Integer> t=new ArrayList< Integer>();
  for(int i=0;i< a;i++)
    t.add(in.nextInt());
  if(a==1){
    System.out.println(t.get(0));
    System.out.println(t.get(0));
  }
  else{
    int total=0;
    Collections.sort(t);
    ArrayList< Integer> t2=new ArrayList< Integer>();
    ArrayList< Integer> t3=new ArrayList< Integer>();
    int m1=t.get(0);
    int m2=t.get(1);
    int w=a;
    while(w>3)
    {
    total+=t.get(w-1)+m1+Math.min(m2*2,m1+t.get(w-2));
    if(m2*2>(m1+t.get(w-2)))
    {
        t2.add(m1);
        t2.add(t.get(w-2));
        t3.add(m1);
        t2.add(m1);
        t2.add(t.get(w-1));
        t3.add(m1);
    }
    else
    {
        t2.add(m1);
        t2.add(m2);
        t3.add(m1);
        t2.add(t.get(w-2));
        t2.add(t.get(w-1));
        t3.add(m2);
    }
    w-=2;
     }
    if(w==2){
    total+=m2;
    t2.add(m1);
    t2.add(m2);
     }
    else {
    total+=m1+m2+t.get(2);
    t2.add(m1);
    t2.add(m2);
    t3.add(m1);
    t2.add(m1);
    t2.add(t.get(2));

     }
     System.out.println(total);
     for(int i=0;i< a-2;i++)
     {
    System.out.println(t2.get(i*2)+" "+t2.get(i*2+1));
    System.out.println(t3.get(i));
     }
     System.out.println(t2.get(a*2-4)+" "+t2.get(a*2-3));
   }
 }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
   {
    String s=in.next();
    String[] s1=s.split("\+");
    String[] s2=s1[1].split("\=");
    StringBuffer b1=new StringBuffer(s1[0]);
    StringBuffer b2=new StringBuffer(s2[0]);
    StringBuffer b3=new StringBuffer(s2[1]);
    b1=b1.reverse();
        b2=b2.reverse();
    b3=b3.reverse();
    int a1=Integer.parseInt(b1.toString());
    int a2=Integer.parseInt(b2.toString());
    int a3=Integer.parseInt(b3.toString());
    if(a1+a2==a3) System.out.println("True");
    else System.out.println("False");
    }
  }
}

							

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

//* @author:
import java.util.*;
import static java.lang.Math.*;
public class Main {
 static double  a, b, c;
 static double[] change( double th,double fi, double l)
{
    double z = l * sin( th/180*PI );
    double y = l * cos( th/180*PI ) * sin( fi/180*PI );
    double x = l * cos( th/180*PI ) * cos( fi/180*PI );
      return new double[]{z,y,x};
 }

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

 double th, fi, l;
 int n,i,cas=1;
 char name[]=new char[100];
 while( true )
 {
   n=sc.nextInt();
   if( n == 0 ) break;
   System.out.printf( "Test case %d:n", cas++ );
   th=sc.nextDouble();
   fi=sc.nextDouble();
   l=sc.nextDouble();
   l += 6378;
   double x[]=change( th, fi, l);
   for( i=0; i< n; i++ )
   {
      name=sc.next().toCharArray();
      th=sc.nextDouble();
      fi=sc.nextDouble();
      double a[]=change( th, fi, 6378);
      if( (x[2]-a[2])*a[2] + (x[1]-a[1])*a[1] + (x[0]-a[0])*a[0] >= 0 )
     System.out.printf( "%sn", String.valueOf(name) );
    }
    System.out.println();
  }
 }
}


							

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

//* @author: 82638882@163.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
 static int[][] m=new int[201][201];
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
   {
    int n=Integer.parseInt(in.readLine());
    if(n==0)break;
    for(int i=0;i< 201;i++)
     for(int j=0;j< 201;j++)
    m[i][j]=0;
    String[] ss;
    while(true)
    {
    ss=in.readLine().split(" ");
    int a=Integer.parseInt(ss[0]);
    int b=Integer.parseInt(ss[1]);
    if(a==0&&b==0)break;
    for(int i=0;i< ss[2].length();i++)
    {
      int w=ss[2].charAt(i)-'a';
      m[a][b]|=1<< w;
    }
     }
     for(int k=1;k<=n;k++)
       for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
       m[i][j]|=m[i][k]&m[k][j];
     while(true)
     {
    ss=in.readLine().split(" ");
    int a=Integer.parseInt(ss[0]);
    int b=Integer.parseInt(ss[1]);
    if(a==0&&b==0) break;
    char ch;
    for(ch='a';ch<='z';ch++)
    {
      if((m[a][b]&(1<<(ch-'a')))!=0)
       System.out.print(ch);
    }
    if(m[a][b]==0) System.out.print("-");
    System.out.println();
      }
     System.out.println();
   }
 }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  HashMap< String,Integer> ts=new HashMap< String,Integer>();
  while(true)
  {
   int a=Integer.parseInt(in.readLine());
   if(a==0)break;
   String k="";
   int t=0;
   for(int i=0;i< a;i++)
   {
    String s=k+in.readLine();
    for(int j=1;j< s.length();j++)
    {
          t++;
      String w=s.substring(j-1,j+1);
      ts.put(w, ts.containsKey(w)?ts.get(w)+1:1);
        }
    k=s.substring(s.length()-1);
    }
    List< Map.Entry< String, Integer>> ww=new ArrayList< Map.Entry< String, Integer>>(ts.entrySet());
    Collections.sort(ww,new Comparator< Map.Entry< String, Integer>>(){

    @Override
    public int compare(Entry< String, Integer> arg0,
    Entry< String, Integer> arg1) {
    int r1=arg1.getValue();
    int r0=arg0.getValue();
    if(r1!=r0)return r1-r0;
    else return arg0.getKey().compareTo(arg1.getKey());
    }
    });
   for(int i=0;i< 5;i++)
   {
    int u=ww.get(i).getValue();
    System.out.print(ww.get(i).getKey()+" "+u+" ");
    System.out.printf("%.6fn",(double)u/(double)t);
   }
   System.out.println();
   ts.clear();
  }    
 }
}
							

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

#include<iostream>
#include"stdio.h"
#include"stdlib.h"
#include"memory.h"
using namespace std;
bool e[51][51];
bool s[51]; 
int a[51],n;
void print( int f )
{
    int i;
    printf( "(%d", f );
    
    for( i=1; i<=n; i++ )
    if( e[f][i] )
    {
        printf( " " );
        print( i );
    }

    printf( ")" );
}
int main()
{
    int i, j;
    char c;
    while( 1 )
    {
        n = 1;
        while( 1 )
        {
            if( cin.peek() == 'n' )
            {
                c = cin.get();
                break;
            }
            cin>>a[n++];
            if( cin.fail() ) return 0;
        }        
        memset( e, 0, sizeof( e ) );
        memset( s, 0, sizeof( s ) ); 
        s[ n ] = true;
        for( i=n-1; i; i-- )
        {
            if( i>1 && !s[ a[i-1] ] )
            {
                e[ a[i] ][ a[i-1] ] = true;
                s[ a[i-1] ] = true;
            }
            else
            {
                for( j=n-1; j; j-- )
                if( !s[ j ] )
                {
                    e[ a[i] ][ j ] = true;
                    s[ j ] = true;
                    break;
                }
            }
        }
        print(n);
        printf( "n" );
    }
    return 0;
}
							

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

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


int d[51],n;
bool e[51][51];

void creat( int f )
{
    int s;
    char t[10];

    scanf( "%[ ,0-9]", t );
    s = atoi( t );
    if( s > n ) n = s;

    if( f ) e[f][s] = e[s][f] = true;

    while( 1 )
    {
        scanf( "%1s", t );

        if( t[0] == ')' )
            return;
        else creat( s );
    }
}

int main()
{
    int i, j, k;
    char c;

    while( scanf( "%c" ,&c ) == 1 )
    {
        n = 0;
        memset( e, 0, sizeof(e) );
        creat(0);
    

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

        for( i=1; i<n; i++ )
        {
            for( j=1; j<=n; j++ )
                if( d[j] == 1 ) break;

            for( k=1; k<=n; k++ )
            if( e[j][k] )
            {
                printf( "%d", k );
                e[k][j] = false;
                d[k]--,d[j]--;
                break;
            }

            if( i<n-1 )printf( " " );
            
        }
        printf( "n" ); 
        scanf( "%c", &c );
    }
    return 0;
}
							

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

#include"stdio.h"
#include"algorithm"
#include"math.h"
using namespace std;
int sum[100010];
int *id[100010];
const bool cmp( int *a, int *b )
{
    return *a<*b;
}
int main()
{
    int n,m,i,t,j,a,b,ans,temp,k;
    while( 1 )
    {
        scanf( "%d %d", &n, &m );
        if( n == 0 && m == 0 ) break;        
        sum[0] = 0;
        id[0] = sum;
        for( i=1; i<=n; i++ )
        {
            scanf( "%d", &sum[i] );
            
            id[i] = sum + i;
            sum[i] += sum[i-1];
        }
        n++;
        sort( id, id+n, cmp );
        for( k=0; k<m; k++ )
        {
            scanf( "%d", &t );
            ans = 2000000000;
            for( i=0,j=1; i<n; i++ )
            {
                if( i >= j ) j++;
                if( j >= n ) break;
                while( j<n-1 && *id[j]-*id[i] < t )
                    j++;
                if( ( temp = abs( *id[j] - *id[i] - t ) ) < ans )
                    a = i, b = j, ans = temp;
                if( j-1 > i && ( temp = abs( *id[j-1] - *id[i] - t ) ) < ans )
                    a = i, b = j-1, ans = temp;
            }
            if( id[a] > id[b] )swap( a, b );
            printf( "%d %d %dn", abs( *id[a] - *id[b] ), id[a]-sum+1, id[b]-sum );
        }
    }
    return 0;             

}


							

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
 public static void main(String[] args) throws IOException{
  // TODO Auto-generated method stub
  Scanner scan=new Scanner(System.in);
  BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer tokens;
  tokens=new StringTokenizer(scan.nextLine());
  int n=new Integer(tokens.nextToken());
  double d=new Double(tokens.nextToken());
  double result;
  int num;
  String a="";
  int h,m,s;
  int i1,i2;
  int aux;
  while(scan.hasNext()){
    h=0;
    m=0;
    s=0;
    tokens=new StringTokenizer(scan.nextLine());
    num=new Integer(tokens.nextToken());
    for(int i=0;i< n;i++){
        a=tokens.nextToken();
        if(a.lastIndexOf('-')>=0) {
            h=-1;
            break;
        }
        i1=a.indexOf(':');
        i2=a.lastIndexOf(':');
        aux=new Integer(a.substring(0, i1));
        h+=aux;
        aux=new Integer(a.substring(i1+1,i2));
        m+=aux;
        s+=new Integer(a.substring(i2+1,a.length()));
    }
    if(h==-1) {
            a=num+"";
            for(int j=0;j< 3-a.length();j++) System.out.print(" ");
            System.out.print(num+": -n");
    }
    else{
            result=h*3600+m*60+s;
            result=result/(d*60);
            m=(int)Math.floor(result);
            result=result-m;
            result*=60;
            s=(int)Math.round(result);
            if(s==60){
                s=0;
                m++;
            }
            a=num+"";
            for(int j=0;j< 3-a.length();j++) System.out.print(" ");
            a="";
            if(s< 10)a="0";
            System.out.print(num+": "+m+":"+a+s+" min/kmn");
    }
  }
 }
}

							

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

#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;

const int size = 25000;

vector< char* > s1[18][26];
vector< char* > s2[18][26];


char w[size][17];
int ans[size],len[size];

bool check( char *a, char *b )
{
    int la = len[ ( a - w[0] ) / 17 ],
        lb = len[ ( b - w[0] ) / 17 ];

    while( *a == *b )
        a++,b++;
    if( la >= lb ) a++;
    if( la <= lb ) b++;

    while( *a == *b && *b != '' )
        a++,b++;
    return *a == '' && *b == '';
}

int main()
{
    int i,j,l,t,h,k,answer=0,m;

    for( i=0; i<18; i++ )
    {
        for( j=0; j<26; j++ )
        {
            s1[i][j].clear();
            s2[i][j].clear();
        }
    }

    for( i=0; scanf( "%s", w[i] ) == 1 ; i++ )
    {
        l = len[i] = strlen( w[i] );
        ans[i] = 0;

        for( h = l-1; h <= l+1 ; h++ )
        {

            j = w[i][0] - 'a';
            m = s1[h][j].size();

            for( k=0; k<m; k++ )
            if( check( w[i], s1[h][j][k] ) && ( t = ans[ ( s1[h][j][k] - w[0] ) / 17 ] ) > ans[i] )
                ans[i] = t;
                        
            j = w[i][l-1] - 'a'; 
            m = s2[h][j].size();

            for( k=0; k<m; k++ )
            if( check( w[i], s2[h][j][k] ) && ( t = ans[ ( s2[h][j][k] - w[0] ) / 17 ] ) > ans[i] )
                ans[i] = t;
        
        }

        ans[i]++;

        s1[l][ w[i][0] - 'a' ].push_back( w[i] );
        s2[l][ w[i][l-1] - 'a' ].push_back( w[i] );
        
        if( ans[i] > answer )
            answer = ans[i];
    }

    printf( "%dn", answer );

    return 0;
}