立天地之心 改生民之命 继往圣之绝学 开万世之太平

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

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

#include <vector>

using namespace std;

typedef int type;                //��������

const int size = 230;            //ͼ�Ķ���ģ
const type MAX_FEE = (1<<30);        //��������
const int MAX = (1<<30);            //�������
const int MAX_SIZE = size*size*2;

class minfee_flow
{

public:

    //ɾ�����б�
    void clear();
    //���һ���from��to ����Ϊc ��λ������Ϊw �ı�
    void insert_edge( int from, int to, int c, type w );
    
    //    ����С�����������ط���
    //    nodenum���� ( �����0,1...nodenum-1 )
    //    beginΪԴ��endΪ�㣬flow��4���������( NULL��ʾ������ )
    type min_fee_max_flow( int nodenum, int begin, int end, int *flow );


private:
    /*    needn't care*/

    struct edge
    {
        int c,f;
        type w;
        int to;
        edge* rev;
        edge* next;
    };                    //�ߵĶ���

    edge* e[size];                    //�ڽӱ�
    static edge edge_cache[MAX_SIZE];
    static int en;

    type fee, sum, dis[size+1], l[size];    //�ܷ��ã����·���úͣ�(dijstra)��̾��룬��4�޸ı�Ȩ�ı��
    bool sign[size];                        //(dijstra)�Ƿ�ȷ�����·
    edge *from[size];                        //(dijstra)���·���У��õ�����
    int pri[size];                            //(dijstra)..�õ��ǰ��
    int n, s, t;                            //������Դ����
    int maxflow, add;                        //�����ÿ�ε�����

    bool dijstra( );                    //(dijstra)
    void increse( edge *ep, int d );    //����*ep�����d
    void modify( );                        //�޸�l,�������·���

};

///////////////////////////////////////////////////////////////////////
//    ����ʵ��

int minfee_flow::en = 0;
minfee_flow::edge minfee_flow::edge_cache[MAX_SIZE];
///////////////////////////////////////////////////////////////////////
//    ����ʵ��

void minfee_flow::clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i] = 0;
    en = 0;
}

bool minfee_flow::dijstra( )
{
    int i, j, k, to, v;
    edge *p;

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

    memset( sign, 0, sizeof(bool)*n );

    dis[ s ] = 0;

    for( i=0; i<n; i++ )
    {
        k = n;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[k] > dis[j] )
                k = j;

        if( k == n )
            break;

        sign[ k ] = true;

        for( p=e[k]; p != NULL ; p = p->next )
        if( p->f != p->c )
        {
            to = p->to;
            if( !sign[to] && dis[ to ] > ( v = dis[ k ] + l[k] - l[to] + p->w ) )
            {
                dis[ to ] = v;
                pri[ to ] = k;
                from[ to ] = p;
            }
        }
    }

    return sign[t] == true;
}

void minfee_flow::increse( edge *ep, int d )
{
    ep->f += d;
    ep->rev->f -= d;
}

void minfee_flow::modify( )
{
    int i, temp;

    add = MAX; sum = 0;
    for( i=t; i!=s; i = pri[i] )
    {
        sum += l[pri[i]] - l[i] + from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }

    sum += l[t];

    for( i=t; i!=s; i = pri[i] )
        increse( from[i], add );

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

    return;
}

void minfee_flow::insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, to, edge_cache+en+1, e[from] }, 
         eg2 = { 0, 0, -w, from, edge_cache+en, e[to] };
    edge_cache[en] = eg1;
    edge_cache[en+1] = eg2;

    e[from] = edge_cache+en;
    e[to] = edge_cache+en+1;

    en += 2;
}

type minfee_flow::min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;
    memset( l, 0, sizeof(type)*n );

    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }
    
    if( flow )
        *flow = maxflow;

    return fee;
}

minfee_flow mf;

int main( ) {
    int n, m, a, b, v, i, ans, t = 0, fee;
    while( 1 ) {
        scanf( "%d%d", &n, &m );
        if( n == 0 && m == 0 )
            break;
        mf.clear( );
        
        for( i=0; i<m; i++ ) {
            scanf( "%d%d%d", &a, &b, &v );
            mf.insert_edge( a, b+n, 1, v );
        }

        for( i=1; i<n; i++ )
            mf.insert_edge( i+n, i, 1, 0 );
        mf.insert_edge( n, 0, 2, 0 );

        fee = mf.min_fee_max_flow( n*2, n, n*2-1, &ans );
        printf( "Instance #%d: ", ++t );

        if( ans < 2 )
            printf( "Not possiblen" );
        else
            printf( "%dn", fee );
    }
    return 0;
}



							

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
 static long ans=0;
 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 cnt=0;
  while((a--)!=0)
  {
   ans=0;
   cnt++;
   String[] ss=in.readLine().split(" ");
   int n=Integer.parseInt(ss[2]);
   my[] p=new my[n];
   for(int i=0;i< n;i++)
   {
    ss=in.readLine().split(" ");
    int x1=Integer.parseInt(ss[0]);
    int y1=Integer.parseInt(ss[1]);
    p[i]=new my(x1,y1);
    }
    Arrays.sort(p);
    mergesort(p,0,n);
    System.out.println("Test case "+cnt+": "+ans);
   }
 }

 static void mergesort(my[] arr,int f,int n)
 {
   int n1,n2;
   if(n>1)
   {
    n1=n/2;
    n2=n-n1;
    mergesort(arr,f,n1);
    mergesort(arr,f+n1,n2);
    merge(arr,f,n1,n2);
   }
 }


 static void merge(my[] arr,int f,int n1,int n2)
 {
  int[] temp=new int[n1+n2];
  int cp=0,cp1=0,cp2=0,i=0;
  while((cp1< n1)&&(cp2< n2))
  {
    if(arr[f+cp1].y< arr[f+n1+cp2].y)
        temp[cp++]=arr[f+(cp1++)].y;
    else if (arr[f+cp1].y==arr[f+n1+cp2].y)
    {
        temp[cp++]=arr[f+(cp1++)].y;
    }
    else {
        temp[cp++]=arr[f+n1+(cp2++)].y;
        ans+=n1-cp1;
    }
   }
  while(cp1< n1)
    temp[cp++]=arr[f+(cp1++)].y;
  while(cp2< n2)
    temp[cp++]=arr[f+n1+(cp2++)].y;
  for(i=0;i< cp;i++)
    arr[f+i].y=temp[i];
 }
}

class my implements Comparable< my>
{
    int x,y;
    public my(int a,int b)
    {
         x=a;
      y=b;
    }
    public int compareTo(my arg0) {
      if(x==arg0.x)
         return y-arg0.y;
      return x-arg0.x;
    }
}
							

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

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


int main( ) {
    int m, p, a, b, k, i;
    double sum, q_a, a_p, ans, t;
    while( scanf( "%d%d%d%d", &m, &p, &a, &b ) == 4 ) {
        q_a = sqrt((double)a);
        sum = b*q_a+m/q_a;
        
        k = int(sum/(q_a+1.0/q_a)+1e-6);
        
        sum -= k*(q_a+1.0/q_a) + 1/q_a;
        
        while( k > m )
            ;

        for( a_p=1, i=0; i<p/2; i++ )
            a_p *= a;
        
        ans = k*a_p;
        if( k != m ) {
            for( t=1, i=0; i<p; i++ )
                t *= sum;
            ans += (m-k-1)/a_p + t;
        }
        


        printf( "%.0lfn", ans );
    }
    return 0;
}

							

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

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

int p[6000010];
int st[6000010];

void clear( int n ) {
    memset( p, -1, sizeof(int)*(n+1) );
}

void input( int &m, int &sa, int &sb ) {
    char w[2];
    m=1;sa=0;sb=1;

    if( scanf( "%1s", w ) != 1 )return;
    ungetc( w[0], stdin );

    if( !(w[0]>='0'&&w[0]<='9'||w[0]=='-') ) {
        return;
    }
    
    scanf( "%d", &m );
    if( scanf( "%1s", w ) != 1 )return;
    ungetc( w[0], stdin );
    if( !(w[0]>='0'&&w[0]<='9'||w[0]=='-') ) {
        return;
    }

    scanf( "%d", &sb );
    if( scanf( "%1s", w ) != 1 )return;
    ungetc( w[0], stdin );
    if( !((w[0]>='0'&&w[0]<='9')||w[0]=='-') ) {
        return;
    }

    scanf( "%d", &sa );
}

int main( ) {
    int n, a, b, m, sa, sb, ans, k, ta, tb, *sn;
    char s[2];

    while( 1 ) {
        if( scanf( "%1s", s ) != 1 )
            break;
        
        switch( s[0] ) {
        case 'D': case 'd':
            scanf( "%d", &n );
            clear( n );
            break;
        case 'C': case 'c':
            scanf( "%d%d", &a, &b );
            input( m, sa, sb );
            
            for( k=0; k<m; a+=sa, b+=sb, k++ ){

                if( p[ta=a] >= 0 ) {
                    sn=st;
                    do {
                        *(sn++) = ta;
                        ta = p[ta];
                    }while( p[ta] >= 0 );

                    while( (sn--)!=st )
                        p[*sn] = ta;
                }
                
                if( p[tb=b] >= 0 ) {
                    sn=st;
                    do{
                        *(sn++) = tb;
                        tb = p[tb];
                    }while( p[tb]>=0 );

                    while( (sn--)!=st )
                        p[*sn] = tb;
                }
                
                if( ta != tb ) {
                    if( p[ta] < p[tb] )
                        p[tb] = ta;
                    else if( p[ta] > p[tb] )
                        p[ta] = tb;
                    else {
                        p[ta] = tb;
                        p[tb]--;
                    }
                }
            }
            break;

        case 'Q': case 'q':
            scanf( "%d%d", &a, &b );
            input( m, sa, sb );
            
            ans = 0;
            for( k=0; k<m; a+=sa, b+=sb, k++ ) {
                if( a == b )
                    ans ++;
                else
                {
                        
                    if( p[ta=a] >= 0 ) {
                        sn=st;
                        do {
                            *(sn++) = ta;
                            ta = p[ta];
                        }while( p[ta] >= 0 );

                        while( (sn--)!=st )
                            p[*sn] = ta;
                    }
                    
                    if( p[tb=b] >= 0 ) {
                        sn=st;
                        do{
                            *(sn++) = tb;
                            tb = p[tb];
                        }while( p[tb]>=0 );

                        while( (sn--)!=st )
                            p[*sn] = tb;
                    }
                    
                    if( ta == tb )
                        ans ++;
                }

            }
            printf( "%d - %dn", ans, m-ans );
            
            break;
        }

    }
    return 0;
}


							

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

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


int m, n;
int s0[5000], s1[5000];
int mem[2][10000], *a = mem[0], *b = mem[1];
int w0, w1, b0, b1, sum;

#define mine( a, b ) ((a)<(b)?(a):(b))

void fill( ) {
    int i;
    int m0 = 0, m1 = 0;
    w0 = w1 = b0 = b1 = 0;
    for( i=0; i<n; i++ ) {
        if( m1 == n/2 ) {
            w0 += a[i];
            s0[m0++] = i;
        }
        else if( m0 == n/2 ) {
            w1 += a[i], b1 += b[i];
            s1[m1++] = i;
        }
        else if( a[i] > b[i] ) {
            if( w0-b0<w1-b1 ) {
                w0 += a[i], b0 += b[i];
                s0[m0++] = i;
            }
            else {
                w1 += a[i], b1 += b[i];
                s1[m1++] = i;
            }
        }
        else {
            if( w0-b0>w1-b1 ) {
                w0 += a[i], b0 += b[i];
                s0[m0++] = i;
            }
            else {
                w1 += a[i], b1 += b[i];
                s1[m1++] = i;
            }
        }
    }
    sum = n/2*m;
    return;
}


double random( int count ) {
    int i, j, k;
    int nw0, nw1;
    double r, t;
    r = mine( 1.0*w0/sum, 1.0*w1/sum );
    while( count-- ) {
        i = rand()%(n/2);
        j = rand()%(n/2);
        nw0 = w0-a[s0[i]]+a[s1[j]];
        nw1 = w1-a[s1[j]]+a[s0[i]];
        
        t = mine( 1.0*nw0/sum, 1.0*nw1/sum );

        if( t > r ) {
            k = s0[i]; s0[i] = s1[j]; s1[j] = k;
            w0 = nw0, w1 = nw1;
            r = t;
        }
    }
    return r;
}


int main( ) {
    int i, *temp;
    double ans, t;
    char c;

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

        scanf( "%d", &m );
        for( i=0; i<n; i++ )
            scanf( "%d%d", &a[i], &b[i] );
        fill( );

        ans = random( n*1000 );
        c = 'W';

        temp = a; a = b; b = temp;

        fill( );
        t = random( n*1000 );
        if( t > ans )
            ans = t, c = 'B';

        if( ans <= 0.5 )
            printf( "No solutionn" );
        else
            printf( "%c %.2lfn", c, ans*100 );
    }
    return 0;
}
							

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

import java.util.*;  
      
    public class Main {  
      
        public static void main(String[] args) {  
            Scanner cin = new Scanner(System.in);  
              
            while(cin.hasNext())  
            {  
               System.out.println(cin.nextLine());  
           }  
       }  
   }  

							

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {

//    private static int ans[] =new int[100000];
    private static int index = 0;
    public static void get(int[] seq, int s , int[]ans) {
        int sum = 0;
        int k = 0;
        int len = 0;
        for (int i = 0 ; i <seq.length ; i++) {
            sum = sum + seq[i];
            //System.out.println(sum);
            len++;
            if (sum >= s){
                for(int j = k ;j< i;j++ ){
                    int temp = sum - seq[j];
                    if(temp >= s){
                        sum = temp;
                        len --;
                    }else{
                        k = j;
                        ans[index++] = len;
                        break;
                    }
                }
            }
                
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testNum = sc.nextInt();

        for (int i = 0; i < testNum; i++) {
            
            int n = sc.nextInt();
            int s = sc.nextInt();
            int[] seq = new int[n];
            int[] ans = new int[n];
            index = 0;
            for (int j = 0; j < n; j++) {
                seq[j] = sc.nextInt();
            }
            get(seq, s , ans);
            //Arrays.sort(seq);
            Arrays.sort(ans , 0 ,index);
            System.out.println(ans[0]);
        }

    }

}
							

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

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

int m[1000][1000];
int sx[1000], sy[1000];
int main() {
    int t, n, i, j, d, a, b, best;
    
    scanf( "%d", &t );
    while( t-- ) {
        scanf( "%d%d", &d, &n );

        best = 99999999;
        memset( m, 0, sizeof m );
        memset( sx, 0, sizeof sx );
        memset( sy, 0, sizeof sy );

        for( i=0; i<n; i++ ) {
            scanf( "%d%d", &a, &b );
            m[(a%d+d)%d][(b%d+d)%d]++;
            sx[(a%d+d)%d]++;
            sy[(b%d+d)%d]++;
        }
        for( i=0; i<d; i++ )
        for( j=0; j<d; j++ )
            if( sx[i] + sy[j] - m[i][j] < best )
                best = sx[i] + sy[j] - m[i][j];
        printf( "%dn", best );
    }
    return 0;
}
							

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

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

int w1[1000000];


int main() {
    int t, i, j, m;
    char c, temp;

    scanf( "%d", &t );
    getchar();

    while( t-- ) {

        m = 0;

        while( 1 ){
            c = getchar();
            
            if( c == 'n' )
                break;
            
            if( c >= '0' && c <= '9' ) {
                j = 0;
                while( c >= '0' && c <= '9' ) {
                    j = j*10 + c-'0';
                    c = getchar();
                }
                while( --j ) {
                    w1[m] = (temp<<20)|m;
                    m++;
                }

                ungetc( c, stdin );
            }
            else {
                w1[m] = (c<<20)|m;
                m++;
            }

            temp = c;
        }

    
        sort( w1, w1+m );

        for( j = (w1[0]&((1<<20)-1)), i=0; i<m; i++ ) {
            printf( "%c", w1[j]>>20 );
            j = (w1[j]&((1<<20)-1));
        }
        printf( "n" );

    }
    return 0;
}



							

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

#include <stdio.h>


int main() {
    int n, i, j, k;
    char mm[2][200], *w1 = &mm[0][0], *w2 = &mm[1][0], *t;
    int a[10], b[10], temp;
    bool key;
    
    scanf( "%d", &n );
    while( n-- ) {
        scanf( "%s %s", w1, w2 );
        for( i=0; i<10; i++ )
            a[i] = b[i] = 0;

        for( i=0; w1[i]; i++ )
            a[ w1[i] - '0' ]++;

        for( i=0; w2[i]; i++ )
            b[ w2[i] - '0' ]++;

        for( i=0; i<10; i++ )
            if( (a[i]==0) != (b[i]==0) )
                break;

        if( i == 10 ) {
            printf( "friendsn" );
            continue;
        }

        key = false;
        for( k=0; k<2; k++ ) {

            for( i=1; w1[i]; i++ ) {
                a[ w1[i-1] - '0' ] --;
                a[ w1[i] - '0' ] --;
                
                if( ( i != 1 || w1[0] > '1' ) && w1[i-1] > '0' && w1[i] < '9' ) {

                    a[ w1[i-1] - '0' - 1 ] ++;
                    a[ w1[i] - '0' + 1 ] ++;
                    for( j=0; j<10; j++ )
                        if( (a[j]==0) != (b[j]==0) )
                            break;
                    if( j == 10 ) {
                        key = true;
                        goto end;
                    }
                    
                    a[ w1[i-1] - '0' - 1 ] --;
                    a[ w1[i] - '0' + 1 ] --;
                }

                if( w1[i-1] < '9' && w1[i] > '0' ) {

                    a[ w1[i-1] - '0' + 1 ] ++;
                    a[ w1[i] - '0' - 1 ] ++;
                    for( j=0; j<10; j++ )
                        if( (a[j]==0) != (b[j]==0) )
                            break;
                    if( j == 10 ) {
                        key = true;
                        goto end;
                    }
                    
                    a[ w1[i-1] - '0' + 1 ] --;
                    a[ w1[i] - '0' - 1 ] --;
                }

                a[ w1[i-1] - '0' ] ++;
                a[ w1[i] - '0' ] ++;
            }

            t = w1;
            w1 = w2;
            w2 = t;
            for( i=0; i<10; i++ ) {
                temp = a[i];
                a[i] = b[i];
                b[i] = temp;
            }
        }
end:
        if( key )
            printf( "almost friendsn" );
        else
            printf( "nothingn" );
    }
    return 0;
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    static int[][] p;
    static int a,b,max=0,cnt;
    public static void main(String[] args) throws IOException
    {
        InputStreamReader is=new InputStreamReader(System.in);
        BufferedReader in=new BufferedReader(is);
        String[] ss=in.readLine().split(" ");
        a=Integer.parseInt(ss[0]);
        b=Integer.parseInt(ss[1]);
        p=new int[b+2][a+2];
        for(int i=1;i<=b;i++)
        {
          for(int j=1;j<=a;j++)
            p[i][j]=in.read();
          in.readLine();
        }
        for(int i=1;i<=b;i++)
        {
          for(int j=1;j<=a;j++)
          {
            cnt=0;
            f(i,j);
            if(cnt>max) max=cnt;
           }
        }
        System.out.println(max);
    }
    static void f(int x,int y)
    {
        if(p[x][y]!='*')return;
        p[x][y]=0;
        cnt++;
        f(x,y+1);
        f(x,y-1);
        f(x+1,y);
        f(x-1,y);
    }
}
							

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

 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.HashSet;
 import java.util.Set;

 public class Main {

     static Set<Integer> set;
     static int[][] a;

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         a = new int[5][5];
         String[] s;
         for (int i = 0; i < 5; i++) {
             s = read.readLine().split(" ");
             for (int j = 0; j < 5; j++) {
                 a[i][j] = Integer.parseInt(s[j]);
             }
         }
         set = new HashSet<Integer>();
         for (int i = 0; i < 5; i++) {
             for (int j = 0; j < 5; j++) {
                 search(0, 0, i, j);
             }
         }
         System.out.println(set.size());
     }

     public static void search(int sum, int dp, int x, int y) {
         if (dp == 6) {
             set.add(sum);
             return;
         }
         if (x - 1 >= 0) {
             search(sum * 10 + a[x - 1][y], dp + 1, x - 1, y);
         }
         if (x + 1 < 5) {
             search(sum * 10 + a[x + 1][y], dp + 1, x + 1, y);
         }
         if (y - 1 >= 0) {
             search(sum * 10 + a[x][y - 1], dp + 1, x, y - 1);
         }
         if (y + 1 < 5) {
             search(sum * 10 + a[x][y + 1], dp + 1, x, y + 1);
         }
     } 
}

							

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

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

public class Main {
    
    static final int N = 20;
    static int n,l;
    static String ans;
    static char word[] = new char[N];
    static char ansp[] = new char[N];
    
    public static void main(String []args)throws Exception{
        
        int i;
        String str;
        //Scanner cin = new Scanner(new FileInputStream("input.txt"));
        Scanner cin = new Scanner(System.in);
        l = cin.nextInt();
        n = cin.nextInt();
        for(i=0;i< n;++i){
            str = cin.next();
            word[i] = str.charAt(0);
        }
        Arrays.sort(word,0,n);
        dfs(0,0,false);
    }

public static void dfs(int start,int dept,boolean have){
    int i;
    if(dept>=l){
        if(!have) return ;
        for(i=0;i< dept;++i)
            System.out.print(ansp[i]);
        System.out.println("");
        return ;
    }
    for(i=start;i< n;++i){
      ansp[dept] = word[i];
         if(word[i]=='a' || word[i]=='e'||word[i]=='i'||word[i]=='o'||word[i]=='u'){
        dfs(i+1,dept+1,have|true);
       }
        else dfs(i+1,dept+1,have);
    }
 }
}

							

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

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

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
    
 int n,mx=-1,tag=-1,i,v;
 n=sc.nextInt();
 while((n--)!=0)
 {
   v=sc.nextInt();
   int u=v;
   int maxx=1;
   if(v%2==0)
   {
    maxx=2;
    while(v%2==0)v/=2;
   }
   for(i=3;i*i<=v;i+=2)
   {
    if(v%i==0)
    {
          maxx=i;
       while(v%i==0)v/=i;
     }
    }
    if(v>maxx)maxx=v;
    if(maxx>mx)
    {
    mx=maxx;
    tag=u;
     }
   }
   System.out.printf("%dn",tag);
  }
}  
							

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

//* @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[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    String  s[]={"monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday"};
    int n,y,m,d,t;
    y=sc.nextInt();
    m=sc.nextInt();
    d=sc.nextInt();
    t=(y-1)*365;
    for (int i=1;i< y;i++) if ((i%4==0&&i%100!=0)||(i%400==0)) t++;
    if ((y%4==0&&y%100!=0)||(y%400==0)) a[2]++;
    for (int i=1;i< m;i++) t+=a[i];
    t+=d+6;
    System.out.println(s[t%7]);
 }
}
							

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

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


int c[1001];
int ans[1001][10000];

int main() {
    int i, j, k, sum, n, a, t, left, right;
    scanf( "%d%d%d%d", &n, &a, &left, &right );

    if( a > 10000 )
        while( printf( "asdf" ) );

    for( i=0; i<n; i++ )
        c[i] = 0;
    for( i=0; i<a; i++ ) {
        scanf( "%d", &t );
        c[t-1]++;
    }

    memset( ans, 0, sizeof ans );
    ans[0][0] = 1;
    sum = 0;

    for( i=0; i<n; i++ ) {
        for( j=0; j<=right && j<=sum; j++ ) {
            for( k=0; k<=c[i]; k++ ) {
                ans[i+1][j+k] += ans[i][j];
                ans[i+1][j+k] %= 1000000;
            }
            
        }
        sum += c[i];
    }

    sum = 0;
    for( i=left; i<=right; i++ )
        sum += ans[n][i];
    printf( "%dn", sum%1000000 );
    return 0;
}
							

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

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

struct cow {
    int sum, w, s;
}c[50000];

int n;

bool cmp( cow a, cow b ) {
    return a.sum < b.sum;
};

bool check( int k ) {
    int sum = 0, i;
    for( i=0; i<n; i++ ) {
        if( c[i].sum - sum > k )
            return false;
        sum += c[i].w;
    }
    return true;
}

int main() {
    int i, sum = 0, a, b, cc;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%d%d", &c[i].w, &c[i].s );
        sum += c[i].w;
    }

    for( i=0; i<n; i++ )
        c[i].sum = sum - c[i].w - c[i].s;

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

    a = -500000000; b = 500000000;
    while( a < b-1 ) {
        cc = (a+b)/2;
        if( check( cc ) )
            b = cc;
        else 
            a = cc;
    }
    printf( "%dn", b );
    return 0;
}
							

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

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

int id[50000];
int h[50000];
bool sign[50000];
int temp[2][51000];
int *next = &temp[0][1];
int *pri = &temp[1][1];

bool cmp( int a, int b ) {
    return h[a] > h[b];
}

int main() {
    int n, i, j, count;
    scanf( "%d%*d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%*d%d", h+i );
        id[i] = i;
        next[i] = i+1;
        pri[i] = i-1;
        sign[i] = true;
    }

    std::sort( id, id+n, cmp );

    count = 0;
    for( i=0; i<n && h[ id[i] ]; i++ ) 
    if( sign[id[i]] ){
        j = id[i];
        count ++;
        if( pri[j] >= 0 && next[j] < n && h[ pri[j] ] == h[ next[j] ] ) {
            sign[ next[j] ] = false;
            next[ pri[j] ] = next[ next[j] ];
            pri[ next[next[j]] ] = pri[j];
        }
        else {
            next[ pri[j] ] = next[j];
            pri[ next[j] ] = pri[j];
        }
    }

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

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

#include <stdio.h>


#define max(a,b) ((a)>(b)?(a):(b))

int clac( char *w, int len, char map[32][32], int n, int m ) {
    int s[5][1000], sn[5] = {0};
    int ans[5][1000] = { 0 }, i, j, k, ii, l, sum = 0;
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    for( k=0; k<len; k++ )
        if( map[i][j] == w[k] )
            s[k][sn[k]++] = (i<<5)|j;

    for( i=0; i<sn[0]; i++ )
        ans[0][i] = 1;
    for( i=0; i<len-1; i++ ) {
        ii = i+1;
        k = 0;
        for( j=0; j<sn[i] && k<sn[ii]; j++ ) 
        if( ans[i][j] ){
            while( k<sn[ii] && s[ii][k]<=s[i][j] )
                k++;
            for( l=k; l<sn[ii]; l++ ) {
                if( ( s[ii][l] & 31 ) >= ( s[i][j] & 31 ) )
                    ans[ii][l] += ans[i][j];
            }
        }
    }
    
    for( i=0; i<sn[len-1]; i++ )
        sum += ans[len-1][i];
    return sum;
}
        
int main( ) {
    char map[32][32], w[10];
    int count[256] = { 0 };
    int n, m, i, ans = 0, j;

    scanf( "%d%d", &n, &m );
    for( i=n-1; i>=0; i-- ) {
        scanf( "%s", map[i] );
        for( j=0; j<m; j++ )
            count[map[i][j]]++;
    }

    while( scanf( "%s", w ) == 1 ) {
        for( i=0; w[i]; i++ )
            if( count[ w[i] ] == 0 )
                break;
        if( w[i] == 0 )
            ans += clac( w, i, map, n, m );
    }
    printf( "%dn", ans );
    return 0;
}
							

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

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

int x[1001];
__int64 ans[1001][1001][2];

int main() {
    int i, j, n, k;
    scanf( "%d%d", &n, &k );
    
    for( i=0; i<n; i++ ) {
        scanf( "%d", &x[i] );
    }

    x[n] = k;

    std::sort( x, x+n+1 );
    for( i=0; i<=n; i++ )
        if( x[i] == k ) {
            k = i;
            break;
        }

    memset( ans, 0x7f, sizeof ans );
    ans[k][k][0] = ans[k][k][1] = 0;

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

    k = ans[0][n][0];
    if( k > ans[0][n][1] )
        k = ans[0][n][1];
    printf( "%dn", k );

    return 0;
}
							

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

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

public static boolean find(int k)
{
 for(int i=1;i<=a;i++)
  if(map[k][i]==1&&used[i]==0)
  {
    used[i]=1;
    if(match[i]==0||find(match[i]))
    {
         match[i]=k;
      return true;
    }
   }
  return false;
 }
}
							

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

/* @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 a,b,e,min;
 int c,d,u=0,v=0;
 a=sc.nextDouble();
 b=sc.nextDouble();
 a=a/b;
 c=d=1;
 min=32768;
 while(c< 32768&&d<32768)
 {
    e=c*1.0/d*1.0;
    if(e==a){
    d++;
    continue;
    }
    if(e>a){
    if(e-a< min){
     min=e-a;
     u=c;
     v=d;
    }
    d++;
    }
   else {
      if(a-e< min){
     min=a-e;
     u=c;
     v=d;
      }
      c++;
   }
  }
  System.out.printf("%d %d",u,v);
  }
}
							

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

#include <stdio.h>


int ans[20][40][40] = { 0 };

int main( ) {
    int i, j, k, t;
    ans[0][20][20] = 1;
    for( i=0; i<14; i++ ) {
        for( j=1; j<39; j++ )
            for( k=1; k<39; k++ ) {
                t = ans[i][j][k];
                ans[i+1][j][k-1] += t;
                ans[i+1][j][k+1] += t;
                ans[i+1][j-1][k] += t;
                ans[i+1][j-1][k-(j%2?1:-1)] += t;
                ans[i+1][j+1][k] += t;
                ans[i+1][j+1][k-(j%2?1:-1)] += t;
            }
    }
    scanf( "%d", &t );
    while( t-- ) {
        scanf( "%d", &k );
        printf( "%dn", ans[k][20][20] );
    }
    return 0;
}
							

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

//* @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();
  while((a--)!=0)
  {
    int b=in.nextInt();
    int[] arr=new int[b];
    int u=0;
    for(int i=1;i<=b;i++)
    {
        int y=i;
     while(true)
     {
      if(arr[u]==0) y--;
      if(y==-1)
      {
        arr[u]=i;
        break;
       }
      u++;
      if(u>=b) u%=b;
     }
    }
    for(int i=0;i< b-1;i++)
        System.out.print(arr[i]+" ");
    System.out.println(arr[b-1]);
   }
  }
}
							

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

//* @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();
        int r,e,c;
        for (int i=0;i< n ;i++ ){
            r=scanner.nextInt();
            e=scanner.nextInt();
            c=scanner.nextInt();
            if (r< e-c){
                System.out.println("advertise");
            }
            else if (r==e-c){
                System.out.println("does not matter");
            }
            else{
                System.out.println("do not advertise");
            }
        }
    }
}


							

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

/* @author:����acmilan_fan@yahoo.cn */
import java.util.*;
public class Main {

 static public void main( String [] str ){

  Scanner sc=new Scanner(System.in);
  int tt=sc.nextInt();
  while(( tt--)!=0 ) { 
    int a, b, r1, r2, t, r, s;
    a=sc.nextInt();
    b=sc.nextInt();
    r1=sc.nextInt();
    r2=sc.nextInt();
    for( r2--; r2>r1; r2-- ) {
    r = r2; t = 0; s = 1;
    while( r!=0 ) {
      t += (r%a)*s;
      s *= b;
      r/=a;
    }
    if( t % r2 == 0 )
      break;
    }
    if( r2 > r1 )
    System.out.printf( "%dn", r2 );
    else
    System.out.printf( "Non-existent.n" );
   }
  }
}

							

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

import java.io.PrintWriter;  
 import java.util.LinkedList;  
 import java.util.Queue;  
 import java.util.Scanner;  
    
public class Main {  
  static class Point{  
  int x,y,step;  
   int result = 1;  
   char c;  
   public Point(int x, int y, char c){  
   this.x = x;  
    this.y = y;  
  this.c = c;  
    step = 1;  
  }  
  public Point(int x, int y,int step, char c){  
    this.x = x;  
   this.y = y;  
    this.c = c;  
    this.step = step;  
  }  
   @Override 
   public int hashCode() {  
    if(result != 1){  
     return result;  
    }  
    final int prime = 31;  
    result = 1;  
    result = prime * result + c;  
    result = prime * result + x;  
    result = prime * result + y;  
    return result;  
   }  
   @Override 
   public boolean equals(Object obj) {  
    if (this == obj)  
     return true;  
    Point other = (Point) obj;  
    if (c != other.c)  
     return false;  
    if (x != other.x)  
     return false;  
    if (y != other.y)  
     return false;  
    return true;  
   }  
      
  }  
  static int[][] all = new int[150][150];  
  static int[] DX = {0,-1,0,1};//e n w s  
  static int[] DY = {-1,0,1,0};  
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);  
  
   PrintWriter out = new PrintWriter(System.out);  

      
   int n = scn.nextInt(),x,y;  
   int num;//S �� A ����  
   char[][] data = new char[101][101];  
  int[][] table = new int[101][101];  
   Point[] points = new Point[101];  
   Point point;  
   String str;  
  while(n-- > 0){  
    x = scn.nextInt();  
    y = scn.nextInt();  
    
    scn.nextLine();  
    for(int i = 0; i < y; i++){  
     str = scn.nextLine();  
     data[i] = str.toCharArray();  
    }  
    //�õ�������������points������4  
   num = getNum(data,y,x,points);  
   for(int i = 0; i < num; i++){  
     bfs(data,table,points[i]);  
    }  
    out.println(prim(table, num));  
   }  
   out.flush();  
  }  
 private static void bfs(char[][] data, int[][] table, Point point) {  
   Queue<Point> queue = new LinkedList<Point>();  
   queue.add(point);  
   int x,y,nx,ny;  
   int px = all[point.x][point.y];  
   int[][] visted = new int[150][150];  
   while(!queue.isEmpty()){  
    point = queue.poll();  
    x = point.x;  
    y = point.y;  
    for(int i = 0; i < 4; i++){  
     nx = x + DX[i];  
    ny = y + DY[i];  
     if(data[nx][ny] == '#'){  
      continue;  
     }  
     if(visted[nx][ny] == 1){  
      continue;  
     }  
     visted[nx][ny] = 1;  
     if(data[nx][ny] == 'A' || data[nx][ny] == 'S'){  
      table[px][all[nx][ny]] = point.step;  
     }  
     queue.add(new Point(nx,ny,point.step + 1,data[nx][ny]));  
    }  
  }  
 }  

     
  /**  
   * �õ� y �� s ����  
   * @param data  
   * @param y  
   * @param x  
   * @return  
   */ 
  private static int getNum(char[][] data, int x, int y,Point[] points) {  
   int num = 0;  
   char c;  
   for(int i = 0; i < x; i++){  
    for(int j = 0; j < y; j++){  
     c = data[i][j];  
     if(c == 'A' || c == 'S'){  
      all[i][j] = num;  
      points[num] = new Point(i,j,c);  
      num++;  
     }  
    }  
   }  
   return num;  
  }  
  public static int prim(int[][] table, int n) {  
    
   int[] lowcost = new int[n];  
   boolean[] s = new boolean[n];  
   int sum = 0;  
   s[0] = true;// �ӵ�һ��λ�ÿ�ʼ  
   for (int i = 1; i < n; i++) {  
    lowcost[i] = table[0][i];  
    s[i] = false;  
   }  
   // �ҵ� j - s �е���СȨ��  
   for (int i = 1; i < n; i++) {  
    int min = Integer.MAX_VALUE;  
    int j = 1;  
   for (int k = 1; k < n; k++) {  
     if ((lowcost[k] < min) && (!s[k])) {  
      min = lowcost[k];  
      j = k;  
     }  
    }  
    s[j] = true;// ���뵽j ���뵽 s ������4  
    // sum += min;  
   for (int k = 1; k < n; k++) {  
     if (table[j][k] < lowcost[k] && (!s[k])) {  
      lowcost[k] = table[j][k];  
     }  
    }  
   }  
      
  for (int i = 0; i < n; i++) {  
    sum += lowcost[i];  
   }  
   return sum;  
  }  
    }


							

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

//* @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));
        Container cn= new Container();
        boolean noSuchCut =false;
        int n = sc.nextInt();
        long m = sc.nextLong();
        Wrapper[] sequence = new Wrapper[n+1];
        sequence[0] = new Wrapper();
        sequence[0].opt = 0;
        sequence[0].num = 0;
        sequence[0].sum = 0;
        sequence[0].k = 0;
        sequence[0].l = 0;
        cn.add(sequence[0]);
        for(int i = 1; i < n+1; i++)
        {
            sequence[i] = new Wrapper();
            sequence[i].num = sc.nextLong();
            if(sequence[i].num > m)
            {
                noSuchCut = true;
            }
            sequence[i].sum += sequence[i].num + sequence[i-1].sum;
            sequence[i].k = i;
        }
        if(noSuchCut)
        {
            System.out.println(-1);
        }else
        {
        int p = n-1;
        int i;
        boolean first =false;
        for(i = n; i >=1; i--)
        {
            for(int j = p; j >= 0; j--)
            {
                if(sequence[i].sum - sequence[j].sum > m)
                {
                    sequence[i].l = j+2;
                    p = j;
                    break;
                }else if(j == 0)
                {
                    sequence[i].l = 1;
                    p = j;
                    first =true;
                    break;
                }
            }
            if(p == 0 && first)
            {
                break;
            }
        }
       
        for(int j = i - 1; j >= 1; j--)
        {
            sequence[j].l = 1;
        }
        /*
        for(int j = 0; j < n+1; j++)
        {
            System.out.println(sequence[j]);
        }
        */
        for(i = 1; i < n+1; i++)
        {
            cn.add(sequence[i]);
            //System.out.println("----");
            //System.out.println(cn);
            //System.out.println("----");
            long min = sequence[sequence[i].l-1].opt + cn.array[cn.s].num;
            //System.out.println(min);
            for(int j = cn.s; j < cn.e-1; j++)
            {
                long temp = cn.array[j].opt + cn.array[j+1].num;
                if(temp < min)
                {
                    min = temp;
                }
            }
            sequence[i].opt = min;
            //System.out.println(min);
        }  
        System.out.println(sequence[n].opt);
    }
    }
    
}

class Wrapper implements Comparable< Wrapper>
{
    long opt;
    long num;
    long sum;
    int l;
    int k;
    
    public int compareTo(Wrapper w)
    {
        if(this.num == w.num)
        {
            return 0;
        }else if(this.num > w.num)
        {
            return -1;
        }else
        {
            return 1;
        }
    }
    public String toString()
    {
        return "opt:" + opt + " num:" + num + " sum:" + sum +
                " l:" + l + " k:" + k;
    }
}
class Container
{
    Wrapper[] array;
    int s , e;
    public Container()
    {
        array = new Wrapper[100008];
        s = 0;
        e = 0;
    }
    public void add(Wrapper w)
    {
        int i;
        for(i = s; i < e; i++)
        {
            if(array[i].k >= w.l)
            {
                break;
            }
        }
        s = i;
        for(i = e-1; i >= s; i-- )
        {
            if(array[i].compareTo(w) == -1)
            {
                break;
            }
        }
        array[i+1] = w;
        e = i+2;
    }
    public String toString()
    {
        String result = "";
        for(int i = s; i < e; i++)
        {
            result += array[i].num + " "; 
        }
        return result;
    }
}

							

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

import java.util.*;
import java.io.*;
public class Main{
   static int dp[][]=new int[4501][4501];   
  public static void main(String args[]){
    
    Scanner scan = new Scanner(new BufferedInputStream(System.in));
        while(scan.hasNext()) {
                int n = scan.nextInt();
                int m = scan.nextInt();
                System.out.println(f(n, m));
            }
        }
    
  public static int f(int n ,int m ){ //m个东西往n个盒子放  
    
   for(int i = 1; i <= m; i++) dp[1][i] = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (i == j) dp[i][j]++;
            if (j > i) dp[i][j] += dp[i][j - i];
            if (dp[i][j] >= 1000000007) dp[i][j] -= 1000000007;
        }
    }
     return dp[n][m];
  }
}
   

							

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

#include <stdio.h>


int main( ) {
    int n, k, m, t, i;
    __int64 a[32], ans, temp;
    
    scanf( "%d", &t );

    while( t-- ) {
        scanf( "%d%d%d", &n, &k, &m );

        a[0] = 10%m;
        ans = 1;
        temp = 1;
        for( i=1; i<32; i++ )
            a[i] = (a[i-1]*a[i-1])%m;
        
        for( i=0; (1<<i)<=k; i++ )
            if( k & (1<<i) )
                temp = (temp*a[i])%m;
        
        a[0] = (temp+1)%m;
        for( i=1; i<32; i++ )
            a[i] = (a[i-1]*a[i-1])%m;

        for( i=0; (1<<i)<=n; i++ )
            if( n & (1<<i) )
                ans = (ans*a[i])%m;

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

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

//* @author 

import java.util.*;
public class Main {

static final int MAX= 30;
static int w,h;
static int start_x,start_y;
static int flag[][] = new int[MAX][MAX];
static int min=11;
static int step=1;

static void dfs(int x,int y,int step)
{
    if(step>10) return;
    if(step==min) return;
for(int i=x+1;i< h;i++)
{
 if(i==x+1&&flag[i][y]==1) break;
 if(flag[i][y]==3){if(min>step) min=step;return;}
 if(flag[i][y]==1&&step< min){flag[i][y]=0;dfs(i-1,y,step+1);flag[i][y]=1;break;}
}
for(int i=x-1;i>=0;i--)
{
 if(i==x-1&&flag[i][y]==1) break;
 if(flag[i][y]==3){if(min>step);min=step;return;}
 if(flag[i][y]==1&&step< min){flag[i][y]=0;dfs(i+1,y,step+1);flag[i][y]=1;break;}
 }
for(int i=y+1;i< w;i++)
{
 if(i==y+1&&flag[x][i]==1) break;
 if(flag[x][i]==3){if(min>step) min=step;return;}
 if(flag[x][i]==1&&step< min){flag[x][i]=0;dfs(x,i-1,step+1);flag[x][i]=1;break;}
}
for(int i=y-1;i>=0;i--)
{
 if(i==y-1&&flag[x][i]==1) break;
 if(flag[x][i]==3&&step< min){if(min>step) min=step;return;}
 if(flag[x][i]==1&&step< min){flag[x][i]=0;dfs(x,i+1,step+1);flag[x][i]=1;break;}
}
return;
}

public static void main(String[] args) {
 Scanner in = new Scanner(System.in);    
  while(true)
  {
    w=in.nextInt();
    h=in.nextInt();
    if(w==0&&h==0) break;
    for(int i=0;i< h;i++)
    {
          for(int j=0;j< w;j++)
       {
        flag[i][j]=in.nextInt();
        if(flag[i][j]==2) 
        {
            start_x=i;
         start_y=j;
         flag[i][j]=0;
           }
         }
    }
    step=1;
    min=11;
    dfs(start_x,start_y,step);
    if(min==11) System.out.println("-1");
    else System.out.println(min); 
  }
 }
}
 

							

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

//* @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)));
    while (true){
        int a=scanner.nextInt();
        int d=scanner.nextInt();
        int n=scanner.nextInt();
        if (a+d+n==0){
            break;
        }
        int index=0;
        int i=0;
        while (index< n){
            if (isZh(a+d*i)){
                index++;
            }
            i++;
        }
        System.out.println(a+d*(i-1));
    }
  }

    public static boolean isZh(int p){
        if (p==1){
            return false;
        }
        if (p==2){
            return true;
        }
        if (p%2==0){
            return false;
        }
        for (int i=3;i*i<=p ;i=i+2 ){
            if (p%i==0){
                return false;
            }
        }
        return true;
    }
}


							

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

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

 static long gcd(long a,long b)
{
  if(b==0) return a;
  return gcd(b,a%b);
}


 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 int t,n,i;
 long p[]=new long[6];
 t=sc.nextInt();
 while((t--)!=0)
 {
    n=sc.nextInt();
    for(i=0;i< n;i++)
      p[i]=sc.nextLong();
    long u=p[0];
    boolean bb=false;
    for(i=1;i< n;i++)
    {
    u=u*p[i]/gcd(p[i],u);
    if(u>1000000000){
         bb=true;
      break;
    }
    }
    if(!bb) System.out.printf("%dn",u);
    else System.out.println("More than a billion.");
   }
  }
}
							

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

 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;

 public class Main {

     class Compara implements Comparator< String[]> {

         public int compare(String[] o1, String[] o2) {
             if (o1[1].charAt(1) == o2[1].charAt(1)) {
                 return o1[1].charAt(0) - o2[1].charAt(0);
             } else if (Character.isUpperCase(o1[0].charAt(0))) {
                 return o1[1].charAt(1) - o2[1].charAt(1);
             } else {
                 return o2[1].charAt(1) - o1[1].charAt(1);
             }
         }
     }

     static char[] a = new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' };

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String s;
         char c;
         String[] q;
         List< String[]> list = new ArrayList< String[]>();
         String[] t;
         for (int i = 0; i < 17; i++) {
             if (i % 2 == 0) {
                 read.readLine();
                 continue;
             }
             s = read.readLine();
             q = s.split("\|");
             for (int j = 1; j <= 8; j++) {
                 c = q[j].charAt(1);
                 if (c == '.' || c == ':') {
                     continue;
                 }
                 t = new String[2];
                 t[0] = "" + c;
                 t[1] = "" + a[j - 1] + (8 - i / 2);
                 list.add(t);
             }
         }
         System.out.print("White: ");
         print("K", list);
         print("Q", list);
         print("R", list);
         print("B", list);
         print("N", list);
         print("P", list);
         System.out.println();
         System.out.print("Black: ");
         print("k", list);
         print("q", list);
         print("r", list);
         print("b", list);
         print("n", list);
         print("p", list);
         System.out.println();
     }

     public static void print(String key, List< String[]> list) {
         if (key.equals("k") || key.equals("K") || key.equals("q")
                 || key.equals("Q")) {
             String[] s = null;
             for (int i = 0; i < list.size(); i++) {
                 s = list.get(i);
                 if (s[0].equals(key)) {
                     break;
                 }
             }
             if (s != null) {
                 if (key.equals("k") || key.equals("K")) {
                     System.out.print(Character.toUpperCase(key.charAt(0))
                             + s[1]);
                 } else {
                     System.out.print("," + Character.toUpperCase(key.charAt(0))
                             + s[1]);
                 }
             }
         } else {
             List< String[]> temp = new ArrayList< String[]>();
             String[] s;
             for (int i = 0; i < list.size(); i++) {
                 s = list.get(i);
                 if (s[0].equals(key)) {
                     temp.add(s);
                 }
             }
             if (temp.size() > 0) {
                 Collections.sort(temp, new Main().new Compara());
                 if (key.equals("p") || key.equals("P")) {
                     for (int i = 0; i < temp.size(); i++) {
                         System.out.print("," + temp.get(i)[1]);
                     }
                 } else {
                     for (int i = 0; i < temp.size(); i++) {
                         System.out.print(","
                                 + Character.toUpperCase(key.charAt(0))
                                 + temp.get(i)[1]);
                     }
                 }
             }
         }
     } 
}

							

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  char[][] arr=new char[8][8];
  String s1=in.nextLine();
  s1=s1.substring(7);
  String[] ws=s1.split(",");
  for(int i=0;i< ws.length;i++)
  {
    if(ws[i].length()==3)
    {
         int x=8-ws[i].charAt(2)+'0';
      int y=ws[i].charAt(1)-'a';
      arr[x][y]=ws[i].charAt(0);
    }
    else if(ws[i].length()==2)
    {
      int x=8-ws[i].charAt(1)+'0';
      int y=ws[i].charAt(0)-'a';
      arr[x][y]='P';
     }
  }
  String s2=in.nextLine();
  s2=s2.substring(7);
  String[] bs=s2.split(",");
  for(int i=0;i< bs.length;i++)
  {
   if(bs[i].length()==3)
   {
    int x=8-bs[i].charAt(2)+'0';
    int y=bs[i].charAt(1)-'a';
    arr[x][y]=(char)(bs[i].charAt(0)+32);
   }
   else if(bs[i].length()==2)
   {
    int x=8-bs[i].charAt(1)+'0';
    int y=bs[i].charAt(0)-'a';
    arr[x][y]='p';
   }
  }
  for(int i=0;i< 8;i++)
  {
    System.out.println("+---+---+---+---+---+---+---+---+");
    for(int j=0;j< 8;j++)
    {
      if(arr[i][j]==0)
      {
        if((i+j)%2==0)System.out.print("|...");
        else System.out.print("|:::");
      }
      else
      {
        if((i+j)%2==0)System.out.print("|."+arr[i][j]+".");
        else System.out.print("|:"+arr[i][j]+":");
      }
    }
    System.out.println("|");
   }
   System.out.println("+---+---+---+---+---+---+---+---+");
 }
}
							

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] prime=new int[]
   {
    2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
    53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,
    127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,
    199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
    283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,
    383,389,397,401,409,419,421,431
   };
   int[] arr=new int[84];
   while(in.hasNext())
   {
    int c=in.nextInt();
    int n=in.nextInt();
    int k=c-n;
    for(int i=0;i< 83;i++)
         arr[i]= cal(c,prime[i])-cal(n,prime[i])-cal(k,prime[i]);
    long ans=1;
    for(int i=0;i< 84;i++)
      if(arr[i]!=0) ans*=(arr[i]+1);
    System.out.println(ans);
    }
  }

public static int cal(int n, int p) {
     if(n < p) return 0;
     else return n / p + cal(n / p, p);
 }
}
							

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

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


int tree[600000];

int k, key;
void set( int l, int r, int s ) {
    int c = (l+r)/2;
    
    tree[s] += key;
    
    if( r == l+1 )
        return;
    if( k < c )
        set( l, c, s*2+1 );
    else
        set( c, r, s*2+2 );
}

int get( int l, int r, int s ) {
    int c = (l+r)/2;
//    printf( "%d %d %dn", l, r, tree[s] );
    if( r == l+1 )
        return l;
    
    if( tree[s*2+1] >= k )
        return get( l, c, s*2+1 );
    else {
        k -= tree[s*2+1];
        return get( c, r, s*2+2 );
    }
}

int p[200100], n, m;
int st[200100], sn;

int find( int k ) {
     for( sn=0; p[k] >= 0; k = p[k] )
         st[sn++] = k;
     while( sn-- )
         p[ st[sn] ] = k;
     return k;
}

void merge( int a, int b ) {
    key = -1;
        
    k = -p[a];
    set( 0, n+1, 0 );
    k = -p[b];
    set( 0, n+1, 0 );
    
    k = -p[a]-p[b];
    key = 1;
    set( 0, n+1, 0 );
    
    if( -p[a] < -p[b] )
        p[a] = b, p[b] = -k;
    else
        p[b] = a, p[a] = -k;
}

int main( ) {
    int i, j, c, h;
    scanf( "%d%d", &n, &m );
    memset( tree, 0, sizeof tree );
    memset( p, -1, sizeof p );
    
    key = n;
    k=1;
    set( 0, n+1, 0 );
    h = n;
    
    while( m-- ) {
        scanf( "%d", &c );
        if( c == 0 ) {
            scanf( "%d%d", &i, &j );
            i = find(i);
            j = find(j);
            if( i != j ) {
                merge( i, j );
                h--;
            }
        }
        else {
            scanf( "%d", &k );
            k = h-k+1;
            printf( "%dn", get( 0, n+1, 0 ) );
        }
    }
    return 0;
}
							

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

//* @author 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    public static int a[];
    public static int luckpeople(int n)
    {
        if(n==1)
            return 1;
        if(n%2==1)
            return luckpeople((n-1)/2)*2+1;
        else
            return luckpeople(n/2)*2-1;
    }
    public static int fun(int n)
    {
        int b;
        while(true)
        {
            b=a[n];
            if(b==n)
                return b;
            n=b;
        }
    }
    public static void main(String[] args) 
    {
        int i,count;
        //a = new int[110];
        //for(i=1;i<=100;i++)
            //System.out.println(luckpeople(i));
            //a[i]=luckpeople(i);
        //for(i=1;i<=100;i++)
        //System.out.println(fun(i));
        BigInteger n,ans;
        String s;
        Scanner cin = new Scanner (System.in);
        while(cin.hasNext())
        {
            n = cin.nextBigInteger();
            s = n.toString(2);
            count = 0;
            for(i=0;i< s.length();i++)
                if(s.charAt(i)=='1')
                    count++;
            ans=BigInteger.valueOf(2);
            ans = ans.pow(count);
            ans = ans.subtract(BigInteger.ONE);
            System.out.println(ans);
        }
         
    }

}
 
							

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

//* @author: 
import java.io.*;
import java.util.Scanner;
/*
 *SPFA �����Լ������.һ��ʼû���Դ��һֱWA....- -!~~~~
 */

class Node
{
 int dian,value;
 Node next;
 Node(int x,int h)
 {
  dian=x;
  value=h;
  next=null;
 }
 void insert(Node a)
 {
  next=a;
 }
}

class Point
{
 int dian;
 Node head;
 Node last;
 Point(int d)
 {
  dian=d;
  head=new Node(0,0);
  last=head;
 }
 void insert(Node a)
 {
  last.insert(a);
  last=last.next;
 }
}

class Quen
{
 int front,rear,num;
 int data[];
 boolean include[];
 
 Quen(int n)
 {
  front=rear=0;
  num=n+1;
  data=new int[n+1];
  include=new boolean[n+1];
  for(int i=0;i<=n;i++)include[i]=false;
 }
 
 boolean isEmpty()
 {
  if(rear==front)return true;
  return false;
 }
 
    boolean add(int s)
    {
     if(include[s])return false;
     data[rear]=s;
     include[s]=true;
     rear=(++rear)%num;
     return true;
    }
    
    int get()
    {
     int s=data[front];
     include[s]=false;
     front=(++front)%num;
     return s;
    }
}

class SPFA 
{
    int numOfD;
    int distance[],count[];
    Point dian[];
    Quen q;

    SPFA(int n,Point s[])
    {
     numOfD=n;
     dian=s;
     q=new Quen(n);
     distance=new int[numOfD+1];
     count=new int[numOfD+1];
    }
    
    boolean haveMin()
    {
     q.add(0);
     int now,i;
     Node p;
     for(i=1;i<=numOfD;i++)
     {
      distance[i]=Integer.MAX_VALUE;
      count[i]=0;
     }
     distance[0]=0;
     count[0]=1;
     while(true)
     {
      if(q.isEmpty())break;
      now=q.get();
      p=dian[now].head;
      while(p.next!=null)
      {
       p=p.next;
       if(distance[p.dian]>distance[now]+p.value)
       {
        distance[p.dian]=distance[now]+p.value;
        if(q.add(p.dian))
        {
         count[p.dian]++;
         if(count[p.dian]==numOfD)return false;
        }
       } 
      }
     }
     return true;
    }
}

public class Main {
    public static void main(String args[]) throws IOException
    {
     Scanner cin=new Scanner(System.in);
     int n,m,i,x,y,h;
     String str;
     SPFA data;
     Point points[];
     Node temp;
     boolean ok;
     while(cin.hasNextInt())
     {
      n=cin.nextInt();
      m=cin.nextInt();
      points=new Point[n+1];
      points[0]=new Point(0);
      for(i=1;i<=n;i++)
      {
       points[i]=new Point(i);
       temp=new Node(i,0);
       points[0].insert(temp);
      }
      for(i=0;i< m;i++)
      {
       str=cin.next();
       if(str.charAt(0)=='P')
       {
        x=cin.nextInt();
        y=cin.nextInt();
        h=cin.nextInt();
        temp=new Node(x,h);
        points[y].insert(temp);
        temp=new Node(y,-h);
        points[x].insert(temp);
       }
       else
       {
        x=cin.nextInt();
        y=cin.nextInt();
        temp=new Node(y,-1);
        points[x].insert(temp);
       }
      }
      data=new SPFA(n,points);
      ok=data.haveMin();
      if(ok)System.out.println("Reliable");
      else System.out.println("Unreliable");
     }
    }
}
							

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

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


int cast[111][111];
int a[111], b[111], c[111];
int n, m, k;
bool sign[111];

int main() {
    int i, j, l, s, x, y, h;
    while( 1 ) {
        scanf( "%d%d%d", &n, &m, &k );
        if( !n && !m && !k )
            break;

        for( i=0; i<k; i++ ) {
            scanf( "%d%d%d", a+i, b+i, c+i );
        }
        
            
        for( i=0; i<=n; i++ )
        for( j=0; j<=m; j++ )
            cast[i][j] = 99999999;
        
        cast[0][0] = 0;
        
        for( i=0; i<=n; i++ ) {
            memset( sign, 0, sizeof sign );
            for( j=0; j<=m; j++ ) {
                
                h = -1;
                for( l=0; l<=m; l++ )
                    if( !sign[l] && ( h < 0 || cast[i][h] > cast[i][l] ) )
                        h = l;
                sign[h] = true;
                
                if( cast[i][h] == 99999999 )
                    break;
                    
                s = cast[i][h];
                for( l=0; l<k; l++ ) {
                    x = i+a[l];
                    y = h+b[l];
                    if( 0 <= x && x <= n && 0 <= y && y <= m && s+c[l] < cast[x][y] )
                        cast[x][y] = s+c[l];
                }
            }
        }
        if( cast[n][m] == 99999999 )
            cast[n][m] = -1;
        printf( "%dn", cast[n][m] );
    }
    return 0;
}
							

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

//* @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 i,j,n,k;
    while (sc.hasNext()) {
        n=sc.nextInt();
        k=sc.nextInt();
       if(n==0) break;
        int num[]=new int[n];
        int den[]=new int[n];
        double scores[]=new double[n];
        for (i=0;i< n;i++) 
            num[i]=sc.nextInt();
        for (i=0;i< n;i++)
            den[i]=sc.nextInt();
        double lb = 0, ub = 1;
        for (i = 0; i < 100; i++) {
            double x = (lb+ub)/2;
            for (j = 0; j < n; j++)
            scores[j] = num[j] - x*den[j];
            Arrays.sort(scores);
            double total = 0;
            for (j = k; j < n; j++)
            total += scores[j];
            if (total >= 0) lb = x;
            else ub = x;
         }
        System.out.printf("%dn",(int)(100*lb + 0.5));
    }
  }
}
							

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

//* @author: 82638882@163.com
import java.util.*;
import java.io.*;
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[] arr=new int[a];
  int u,total;
  for(int i=0;i< a;i++)
  {
    total=0;
    while(true)
    {
         u=in.read();
      if(u>'9'||u< '0')break;
        total*=10;
        total+=u-'0';
    }
    arr[i]=total;
    }
    if(a< 4)
    System.out.println("The set is rejected.");
    else
    {
    Arrays.sort(arr);
    if(arr[a-1]-arr[0]< arr[1])
        System.out.println("The set is rejected.");
    else{
      boolean bb=false;
      for(int i=a-1;i>=2;i--)
      {
        if(arr[i]-arr[i-2]< arr[i-1])
        {
        System.out.println("The set is accepted.");
        bb=true;
        break;
        }
       }
       if(!bb) System.out.println("The set is rejected.");
    }
     }
  }
}

							

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

//* @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();
    while((a--)!=0)
    {
         double D=in.nextDouble();
      double d=in.nextDouble();
      double s=in.nextDouble();
      System.out.printf("%dn", (int)(Math.PI/Math.asin((d+s)/(D-d))));
    }
  }
}
							

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Point{
    int x,y;
}
public class Main {
    
    static Point triangle[] = new Point[3];
    static int GCD(int a,int b){
        if(b==0) return a;
        return GCD(b,a%b);
    }
    static int area(Point a,Point b,Point c){
        return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
    }
    static int solve(){
        int ans=0,i=0;
        int area = area(triangle[0],triangle[1],triangle[2]);
        i += node_in_line(triangle[0],triangle[1]);
        i += node_in_line(triangle[1],triangle[2]);
        i += node_in_line(triangle[0],triangle[2]);
        if(area< 0) area = -area;
        ans = (area-i+2)/2;
        return ans;
    }
    static int node_in_line(Point a,Point b){
        int x,y;
        x = a.x-b.x;
        if(x< 0) x = -x;
        y = a.y-b.y;
        if(y< 0) y = -y;
        if(x==0) return y;
        if(y==0) return x;
        return GCD(x,y);
    }
    public static void main(String[]args) throws Exception{
        
        int i,j;
        //Scanner cin = new Scanner(new FileInputStream("input.txt"));
        Scanner cin = new Scanner(System.in);
        for(i=0;i< 3;++i) triangle[i] = new Point();
        while(true){
            for(i=j=0;i< 3;++i){
                triangle[i].x = cin.nextInt();
                triangle[i].y = cin.nextInt();
                if(triangle[i].x!=0) j=1;
                if(triangle[i].y!=0) j=1;
            }
            if(j==0) break;
            
            System.out.println(solve());
        }
    }
}

							

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

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (n == 0 && m == 0)
                break;
            sc.nextLine();
            HashMap< String, Integer> map = new HashMap< String, Integer>();
            int[] dispear = new int[n];
            for (int i = 0; i < n; ++i) {
                String dna = sc.nextLine();
                // /Integer hasCode = dna.hashCode();
                if (map.get(dna) != null) {
                    map.put(dna, map.get(dna) + 1);
                    dispear[map.get(dna) - 1]--;
                    dispear[map.get(dna)]++;
                } else {
                    map.put(dna, 0);
                    dispear[0]++;
                }
            }
            for (int i = 0; i < n; ++i) {
                System.out.println(dispear[i]);
            }
        }
    }
}
							

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 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();
    int a=Integer.parseInt(s);
    if(a==0)break;
    int[][] arr=new int[a][a];
    String[] ss;
    for(int i=0;i< a;i++)
    {
      ss=in.readLine().split(" ");
      for(int j=0;j< a;j++)
       arr[i][j]=Integer.parseInt(ss[j]);
    }
    boolean bb=true;
    for(int i=0;i< a-1;i++)
    {
        int k=arr[i][0]-arr[i+1][0];
        for(int j=1;j< a;j++)
        {
             if(k!=arr[i][j]-arr[i+1][j])
          {
            bb=false;
            break;
          }
        }
        if(!bb)break;
    }
    System.out.println((bb?"":"not ")+"homogeneous");
   }
 }
}
							

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

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

public class Main {
    
    static final int N = 100000+100;
    static int n;
    static long num[] = new long[N];
    
    public static double Get_Num(StreamTokenizer cin) throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    
public static void main(String []args) throws Exception{
        
 int i;
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
 while(true){
    n = (int) Get_Num(cin);
    if(n==0) break;
    for(i=1;i<=n;++i)
        num[i] = (long) Get_Num(cin);
    System.out.println(solve());
  }
}

public static long solve(){
        int i;
        long cnt=0,ans=0;
        for(i=1;i<=n;++i){
            cnt +=num[i];
            ans+=abs(cnt);
        }
        return ans;
    }
    public static long abs(long cnt){
        if(cnt< 0) return -cnt;
        return cnt;
    }
}

							

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

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;
#define count dofudf
const int prime = 3374521;
int hash[prime] = { 0 };
int num[prime];
int id[prime];
int count = 0;

int get( int x ) {
    int y = x%prime;
    while( hash[y] == count && num[y] != x ) {
        y++;
        if( y == prime )
            y = 0;
    }
    return y;
}
        

int main( ) {
    int a, b, n, i, k;
    long long x;

    while( scanf( "%d%d%d", &n, &a, &b ) == 3 ) {
        if( n < 0 )
            break;
        x = 0;
        count++;
        i = 0;
        a%=n, b%=n;
        while( hash[k=get(int(x))] < count ){
            num[k] = x;
            id[k] = i;
            hash[k] = count;
            x = (a*x%n*x+b) % n;
            i++;
        }
        printf( "%dn", n-(i-id[k]) );
    }
    return 0;
}



							

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

#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

string str[1100];
int year[1100];
int ans[1100];


int doit( int l, int r ) {
    int i, j, b, e;
    ans[l] = 0;
    for( i=l+1; i<=r; i++ ) {
        ans[i] = 999999;
        for( j=l; j<i; j++ ) {
            if( year[i]>=year[j]+2 )
                continue;
            else if( year[i] == year[j] ) {
                if( ans[j]+1 < ans[i] )
                    ans[i] = ans[j]+1;
            }
            else {
                if( ans[j]+1 < ans[i] && str[j] >= str[i] )
                    ans[i] = ans[j]+1;
            }
        }
    }
    return ans[r];
}
                

int main( ) {
    int n, i, need, cur, l;
    char w[100], f[100];
    
    while( 1 ) {
        scanf( "%d", &n );
        if( n == 0 )
            break;
            
        cur = 0;
        l = -1;
        need = 0;
        
        for( i=0; i<n; i++ ) {
            scanf( "%s%*s%s", w, f );
            str[i] = w;
            
            if( i && str[i-1] >= str[i] )
                cur++;
            year[i] = cur;
            
            if( f[0] == '+' ) {
                if( l >= 0 )
                    need += doit( l, i );
                else
                    need++;
                l = i;
            }
        }
        
        if(l>=0 && year[l] != year[n-1] ) {
            str[n] = "";
            year[n] = year[n-1]+1;
            need += doit( l, n ) - 1;
        }
        
        printf( "%dn", need );
    }
    return 0;
}



							

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

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

int main( ) {
    int n, pos, t, s;
    char c[2];
    while( 1 ) {
        scanf( "%d", &n );
        
        if( n == 0 )
            break;
            
        pos=0, s=1;
        
        while( 1 ) {
            if( scanf( "%1s", c ) != 1 )
                break;
            if( strchr( "0123456789", c[0] ) ) {
                ungetc( c[0], stdin );
                break;
            }
            scanf( "%d", &t );
            
            if( c[0] == 'm' ) {
                if( t&1 )
                    pos = (n-pos)%n, s=-s;
            }
            else
                pos = (pos + t)%n;
        }
        
        if( pos == 0 && s == 1 )
            printf( "n" );
        else if( pos == 0 )
            printf( "m1n" );
        else if( s < 0 ) {
            if( n-pos +1 < 1 + pos )
                printf( "r%d m1n", n-pos );
            else
                printf( "m1 r%dn", pos );
        }else {
            if( pos < 2 + n-pos )
                printf( "r%dn", pos );
            else
                printf( "%m1 r%d m1n", n-pos );
        }
    }
    return 0;
}