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

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

#include <iostream>   
using namespace std;   
  
const int M=2147483647;   
int b[5][5];   
  
void calc(int a[][5],int i,int j);   
void print(int i,int j);   
 
int main() 
  {   
    int i,j;   
    int a[5][5];   
   for(i=0;i<=4;i++)   
        for(j=0;j<=4;j++)   
        {   
          cin>>a[i][j];   
            if(a[i][j]==1) a[i][j]=M;   
        }   
    calc(a,0,0);   
    print(4,4);   
    return 0;   
}   

  
void calc(int a[][5],int i,int j)   
{   
    int indexX[4]={-1,0,0,1};   
    int indexY[4]={0,-1,1,0};   
    if(a[i][j]==M)  return;   
    for(int ii=0;ii<=3;ii++)   
        {
               int s=i+indexX[ii];   
           int t=j+indexY[ii];   
          if(a[s][t]!=M&&0<=s&&s<=4&&0<=t&&t<=4)   
           {   
                int temp=a[i][j]+1;   
                if(temp<a[s][t]||a[s][t]==0)    
                {   
                    a[s][t]=temp;   
                    b[s][t]=i*5+j;   
                    calc(a,s,t);   
                }   
            }   
        }   
    return;   
}   
  
void print(int i,int j)   
{   
    if(i==0&&j==0)  {cout<<"(0, 0)"<<endl; return;}   
    print(b[i][j]/5,b[i][j]%5);   
    cout<<"("<<i<<", "<<j<<")"<<endl;   
}  


							

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

#include<stdio.h>
int main(){
printf("5*(5-(1/5))n");
return 0;
}
							

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

#include <stdio.h>   
#include <string.h>   
#include <stdlib.h>   
  
#define MAX_LEN 1024   
  
void BigIntegerAdd(const char a[], const char b[], char res[])   
{   
    int i, j, k;   
    int x, y, z;   
    int up, l;   
  
    char *c;   
  
    if(strlen(a) > strlen(b))   
    {   
        l = strlen(a) + 2;   
    }   
    else  
    {   
        l = strlen(b) + 2;   
    }   
  
    c = (char *)malloc(l * sizeof(char));   
    i = strlen(a) - 1;   
    j = strlen(b) - 1;   
    k = up = 0;   
  
    while(i >= 0 || j >= 0)   
    {   
        x = i < 0 ? '0' : a[i];   
        y = j < 0 ? '0' : b[j];   
        z = x - '0' + y - '0';   
        if(up)   
        {   
            ++z;   
        }   
        if(z > 9)   
        {   
            up = 1;   
            z -= 10;   
        }   
        else  
        {   
            up = 0;   
        }   
        c[k++] = z + '0';   
        --i;   
        --j;   
    }   
  
    if(up)   
    {   
        c[k++] = '1';   
    }   
    i = 0;   
    c[k] = '';   
  
    for(k -= 1; k >= 0; --k)   
    {   
        res[i++] = c[k];   
    }   
    res[i] = '';   
  
    free(c);   
}   
  
int main(int argc, char **argv)   
{   
    char a[4][MAX_LEN];   
    int i, n = 99;   
    while(EOF != scanf("%s %s %s", a[0], a[1], a[2]))   
    {   
        for(i = 3; i <= 99; ++i)   
        {   
            BigIntegerAdd(a[0], a[1], a[3]);   
            BigIntegerAdd(a[2], a[3], a[3]);   
            strcpy(a[0], a[1]);   
            strcpy(a[1], a[2]);   
            strcpy(a[2], a[3]);   
        }   
        printf("%sn", a[3]);   
    }   
    return 0;   
}  

							

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

#include <stdio.h>   
#include <string.h>   
  
#define MAX_LEN 1024   
  
int main(int argc, char **argv)   
{   
    char str[MAX_LEN];   
    int i, len;   
  
    while(gets(str))   
    {   
        len = strlen(str);   
        for(i = 0; i < len; ++i)   
        {   
            if('y' != str[i])   
            {   
                putchar(str[i]);   
            }   
            else  
            {   
                if(i + 2 < len && str[i+1] == 'o' && str[i+2] == 'u')   
                {   
                    putchar('w');   
                    putchar('e');   
                    i += 2;   
                }   
                else  
                {   
                    putchar(str[i]);   
                }   
            }   
        }   
        putchar('n');   
    }   
  
    return 0;   
}  

							

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

#include <stdio.h>
int mod(int n, int m){
   return n%m;
}
int main(){
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF){
      printf("%dn",mod(n,m));
    }
return 0;
}
							

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

#include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <math.h>
 
 int gdb(int a,int b)
 {
     int tmp,ret;
     if(a < b)
      {
    tmp = a;
    a = b;
    b =tmp;
      }
    while(b)
   {
      tmp = a;
      a = b;
      b = tmp%b;
    }
    ret = a;
    return ret;
}
int main(void)
{
    int a,b,c,d;
    char opt;
    int ans_a,ans_b;
    while(EOF != scanf("%d/%d%c%d/%d",&a,&b,&opt,&c,&d))
    {
        if('+' == opt)
          {
       ans_b = b*d;        ans_a = a*d+b*c;      
        a = gdb(ans_a,ans_b);
        ans_a /= a;
        ans_b /= a;
          }
        else
          {
        ans_b = b*d;
        ans_a = a*d-b*c;
        if(ans_a < 0)
          {
            a = gdb(-ans_a,ans_b);        
         }
        else
                  {
            a = gdb(ans_a,ans_b);
          }
        ans_a /= a;
        ans_b /= a;                
          }
       if(0 == ans_a)
        printf("0n");
       else
        {
           if(ans_a%ans_b == 0)
            printf("%dn",ans_a/ans_b);
            else
                    printf("%d/%dn",ans_a,ans_b);
         }
    
    }
    return 0;
}

							

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

#include <stdio.h>
int dp[81][201];
int main()
{
    int n,m,i,j,k;
    for(i=1;i<=80;i++){
        for(j=0,k=i-1;j<k;j++) dp[i][j]=0;
    }
    dp[1][0]=1;
    dp[2][1]=2;
    dp[3][2]=4;
    dp[3][3]=2;
    for(i=4;i<=80;i++){
        for(j=i-1;j<=200;j++){
            dp[i][j]=0;
            if(j>=2) dp[i][j]=(dp[i-1][j-2]*(i-2))%9937;
            if(j>=1) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*2)%9937;
        }
    }
    while(scanf("%d%d",&n,&m),n||m){
        if(m>=200) printf("0n");
        else printf("%dn",dp[n][m]);
    }
    return 0;
}
 


							

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

import java.util.Scanner;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner sc = new Scanner(System.in);   
        while (sc.hasNextInt()) {   
            int n = sc.nextInt();   
            if (n == 0)   
                break;   
            sc.nextLine();   
            String[] template = new String[n];   
            for (int i = 0; i < n; ++i) {   
                String s = sc.nextLine();   
                template[i] = new String(s);   
            }   
            // sc.nextLine();   
            // sc.nextLine();   
            int level = sc.nextInt();   
            copy(template, template, level);   
        }   
    }   
  
    private static void copy(String[] template1, String[] template2, int level) {   
        --level;   
        if (level > 0) {   
            int n1 = template1.length;   
            int n2 = template2.length;   
            String[] tmpTemplate = new String[n1 * n2];   
            int k = 0;   
            String spaceS = spaceStr(n2);   
            for (int i = 0; i < n1; ++i) {   
                for (int j = 0; j < n1; ++j) {   
                    k = i * n2;   
                    if (template1[i].charAt(j) == ' ') {   
                        for (int x = 0; x < n2; ++x) {   
                            if (tmpTemplate[k] != null)   
                                tmpTemplate[k] += (spaceS);   
                            else  
                                tmpTemplate[k] = new String(spaceS);   
                            k++;   
                        }   
                    } else {   
                        for (int x = 0; x < n2; ++x) {   
                            if (tmpTemplate[k] != null)   
                                tmpTemplate[k] += template2[x];   
                            else  
                                tmpTemplate[k] = template2[x];   
                            k++;   
                        }   
                    }   
                }   
                // print(tmpTemplate);   
            }   
            copy(template1, tmpTemplate, level);   
        } else  
            print(template2);   
  
    }   
  
    private static String spaceStr(int n) {   
        StringBuilder sb = new StringBuilder();   
        for (int i = 0; i < n; ++i) {   
            sb.append(" ");   
        }   
        return sb.toString();   
    }   
  
    private static void print(String[] template) {   
        int n = template.length;   
        // System.out.println(n);   
        for (int i = 0; i < n; ++i) {   
            System.out.print(template[i]);   
            System.out.println();   
        }   
    }   
}  


							

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

import java.util.Scanner; 

public class Main{ 

 public static void dijkstra(int[][] GA, int[] leader, int road) { 

  if (road == 0)
   System.out.println(-1);
  else { 

   int size = GA.length;
   // System.out.println(size);
   int[] dist = new int[size];
   int[] isUsed = new int[size];
   isUsed[1] = 1;
   dist[1] = Integer.MAX_VALUE;
   for (int i = 2; i < size; i++) {
    dist[i] = GA[1][i];
   } 

   for (int i = 1; i < size - 2; i++) {
    int min = Integer.MAX_VALUE;
    int m = 0;
    for (int j = 1; j < size; ++j) {
     if (isUsed[j] == 0 && dist[j] < min) {
      min = dist[j];
      m = j;
     }
    } 

    if (m != 0)
     isUsed[m] = 1;
    else
     break; 

    for (int j = 1; j < size; ++j) {
     if (isUsed[j] == 0
       && (leader[m] == leader[j] || leader[j] == 2)
       && GA[m][j] != Integer.MAX_VALUE
       && dist[m] + GA[m][j] < dist[j]) {
      dist[j] = dist[m] + GA[m][j];
     }
    }
   }
   System.out.println(dist[2] == Integer.MAX_VALUE ? -1 : dist[2]);
  }
 } 

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  while (sc.hasNextInt()) {
   int countCity = sc.nextInt(); 

   if (countCity == 0)
    break; 

   int road = sc.nextInt(); 

   int[][] GA = new int[countCity + 1][countCity + 1]; 

   for (int i = 1; i <= countCity; ++i) {
    for (int j = 1; j <= countCity; ++j) {
     GA[i][j] = Integer.MAX_VALUE;
    }
   } 

   for (int i = 0; i < road; ++i) {
    int c1 = sc.nextInt();
    int c2 = sc.nextInt();
    GA[c1][c2] = sc.nextInt();
    GA[c2][c1] = GA[c1][c2];
   }
   int[] leader = new int[countCity + 1];
   for (int i = 1; i < countCity + 1; ++i)
    leader[i] = sc.nextInt();
   dijkstra(GA, leader, road); 

  }
 } 

}

							

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

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

public class Main {
 static Scanner in = new Scanner(System.in);
 static class Node extends LinkedList< Node> {
    final int[] dp = new int[]{-1, -1};
    int query(int b) {
        if(dp[b]< 0) init(null);
        return dp[b];
    }
    void init(Node father) {
         dp[0] = dp[1] = 0;
     if(this.size()==1) return;
     int f = 0;
     int[] deta = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
     for(Node v: this) {
        if(v == father) continue;
        v.init(this);
        dp[0] += v.dp[1]+1;
        deta[f] = Math.min(deta[f], v.dp[0]-v.dp[1]);
        if(deta[f]< deta[f^1]) f^=1;
    }
    dp[0] += deta[f^1] - 1;
    dp[1] = dp[0]+Math.min(0, deta[f]-1);
       }
   }

  public static void main(String[] args) {
   int n = in.nextInt();
   Node[] nodes = new Node[n];
   for(int i=0; i!=n; ++i)
    nodes[i] = new Node();
   for(int i=1; i!=n; ++i) {
    int x = in.nextInt()-1;
    int y = in.nextInt()-1;
    nodes[x].add(nodes[y]);
    nodes[y].add(nodes[x]);
   }
   System.out.println(nodes[0].query(1)+1);
 }
}

							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 *poj3753  
 * C�������  
 * while(EOF != scanf("%s",source))  
 *�ȼ���java���while (scan.hasNext())  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            String src = scan.nextLine().trim();   
            while (true) {   
                String key = scan.nextLine().trim();   
                if (key.endsWith("END")) {   
                    break;   
                }   
                if (key.equals("NULL")) {   
                    System.out.println("0 NULL");//�ݾ�   
                } else if (key.isEmpty() || key.equals("") || !src.contains(key)) {   
                    System.out.println(src.length() + " " + src);//�ݾ�   
                } else if (src.contains(key)) {   
                    String sub = src.substring(0, src.indexOf(key));   
                    if (src.indexOf(key) == 0) {   
                        System.out.println("0 NULL");//�ݾ�   
                    } else {   
                        System.out.println(sub.length() + " " + sub);   
                    }   
                }   
            }   
        }   
    }   
}  


							

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

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 *poj3752  
 * ģ��  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int m = scan.nextInt();   
            int n = scan.nextInt();   
            int num = m * n;   
            int[][] letter = new int[m][n];   
            for (int i = 0; i < letter.length; i++) {   
                for (int j = 0; j < letter[i].length; j++) {   
                    letter[i][j] = -1;   
                }   
            }   
            int i = 0, j = 0;   
            int count = 0;   
            if (m != 1 && n != 1) {   
                while (true) {   
                    if (letter[i][j] != -1) {   
                        break;   
                    }   
                    for (int k = 0; k < n; k++) {   
                        letter[i][j + k] = count;   
                        count++;   
                    }   
                    j = j + n - 1;   
                    if (m != 1) {   
                        for (int k = 1; k < m - 1; k++) {   
                            letter[i + k][j] = count;   
                            count++;   
                        }   
                        i = i + m - 1;   
  
                        for (int k = 0, c = 0; c < n; k--, c++) {   
                            letter[i][j + k] = count;   
                            count++;   
                        }   
                        j = j - n + 1;   
                        for (int k = -1, c = 1; c < m - 1; c++, k--) {   
                            letter[i + k][j] = count;   
                            count++;   
                        }   
                        i = i - m + 2;//���ﲻһ��   
                    }   
                    j = j + 1;   
                    m = m - 2;   
                    n = n - 2;   
                }   
            } else if (m == 1 && n == 1) {   
                letter[0][0] = 0;   
            } else if (m == 1) {   
                for (int k = 0; k < n; k++) {   
                    letter[0][k] = k;   
                }   
            } else {   
                for (int k = 0; k < m; k++) {   
                    letter[k][0] = k;   
                }   
            }   
            for (int k = 0; k < letter.length; k++) {   
                for (int v = 0; v < letter[k].length; v++) {   
                    char ch = (char) (letter[k][v] % 26 + 'A');   
                    System.out.print("   " + ch);   
                }   
                System.out.println();   
            }   
        }   
  
    }   
}  


							

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

import java.io.BufferedInputStream;   
import java.text.ParseException;   
import java.text.SimpleDateFormat;   
import java.util.Locale;   
import java.util.Scanner;   
import java.util.logging.Level;   
import java.util.logging.Logger;   
  
/*  
 * To change this template, choose Tools | Templates  
 * and open the template in the editor.  
 */  
/**  
 *  
 * poj3751 easy  
 *  
 * API���  
 * ��ĸ  ���ڻ�ʱ��Ԫ��  ��ʾ  ʾ��  
 *G  Era ��־��  Text  AD  
 *y  ��  Year  1996; 96  
 *M  ���е��·�  Month  July; Jul; 07  
 *w  �������  Number  27  
 *W  �·��е�����  Number  2  
 *D  �������  Number  189  
 *d  �·��е�����  Number  10  
 *F  �·��е�����  Number  2  
 *E  ���������  Text  Tuesday; Tue  
 *a  Am/pm ���  Text  PM  
 *H  һ���е�Сʱ��0-23��  Number  0  
 *k  һ���е�Сʱ��1-24��  Number  24  
 *K  am/pm �е�Сʱ��0-11��  Number  0  
 *h  am/pm �е�Сʱ��1-12��  Number  12  
 *m  Сʱ�еķ�����  Number  30  
 *s  ���������  Number  55  
 *S  ������  Number  978  
 *z  ʱ��  General time zone  Pacific Standard Time; PST; GMT-08:00  
 *Z  ʱ��  RFC 822 time zone  -0800  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        int n = Integer.parseInt(scanner.nextLine());   
        //DateFormat ��һ�������4��   
        SimpleDateFormat df1 =   
                new SimpleDateFormat("yyyy/MM/dd-HH:mm:ss", Locale.US);   
        //��ʮ��Сʱ��   
        SimpleDateFormat df2 =   
                new SimpleDateFormat("MM/dd/yyyy-hh:mm:ssa", Locale.US);   
        //ʮ��Сʱ�ƣ�12��01�賿��ʮ�����   
        //ϵͳĬ������������磬����am��pm   
        for (int i = 0; i < n; i++) {   
            try {   
                String s = scanner.nextLine();   
                //�Ȱ��ַ����Ϊ���ڣ��ٸ�ʽ�����ڣ�ת���ַ������תСд   
                System.out.println(df2.format(df1.parse(s)).toLowerCase());   
            } catch (ParseException ex) {   
                  
            }   
        }   
    }   
}  

							

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

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

int main()
{
    int n, w, s;
    int i, j;
    char name[65][16];
    scanf("%d", &n);
    getchar();
    for (i=0; i<n; ++i)
    {
        gets(name[i]);
    }
    scanf("%d,%d", &w, &s);
    
    i = w-1;
    while (n != 0)
    {
        if (i+s-1 > n-1)
        {
            i = (i+s-1)%n;
        }
        else
        {
            i = i+s-1;
        }
        puts(name[i]);
        for (j=i; j<n-1; ++j)
        {
            strcpy(name[j], name[j+1]);
        }
        --n;
    }
    
    return 0;
}
							

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

#include<stdio.h>
#include<string.h>
int main()
{
    void translate(char word[]);
    char start[20];
    char end[20];
    char word[205];

    while(1)
    {
        gets(start);
        if(strcmp(start,"START")!=0) break;
        gets(word);
        translate(word);
        puts(word);
        gets(end);
    }

}

void translate(char word[])
{
    int i,len;
    len=strlen(word);
    for(i=0;i<len;i++)
    {
        if(word[i]>='A'&&word[i]<='E')
        {
            word[i]+=21;
        }
        else if(word[i]>='F'&&word[i]<='Z')
        {
            word[i]-=5;
        }
    }
}
							

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

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 *
 *poj3748
 * ���
 * @author NC
 */
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        if (scan.hasNext()) {
            String[] ss = scan.nextLine().trim().split("[,]");
            Integer r = Integer.parseInt(ss[0], 16);//��16���ƽ����ַ�
            Integer x = Integer.parseInt(ss[1]);//Ĭ�ϰ�10���ƽ���
            Integer y = Integer.parseInt(ss[2]);
            r = r & ~(0x1 << x);//��xλ���ó�0
            r = r & ~(0x1 << (y - 2));//0
            r = r | (0x1 << (y - 1));//1
            r = r | (0x1 << y);//1
            System.out.println(Integer.toHexString(r));
        }
    }
}

							

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

//* @author 
/**
 * @version 2009/08/31
 * @author sbzlyessit
 */

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

public class Main {

    private static BufferedReader   in =new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static double[] x = new double[10], y = new double[10];
    private static double[] d = new double[20];
    private static double   x0, y0;
    private static int      N;
    private static double   R;

    public static void main(String[] argv) throws Exception {
        while (in.ready()) {
            N = nextInt();
            R = nextDouble();
            x0 = nextDouble();
            y0 = nextDouble();
            for (int i = 0; i < N; i++) {
                x[i] = nextDouble();
                y[i] = nextDouble();
            }
            solve();
        }
    }

    private static void solve() {
        double  a, b, c, delta, t1, t2, a0, a1, b0, b1, x1, y1;
        for (int i = 0; i < N; i++) {
            if (doubleCmp(x[i], x0) == 0 && doubleCmp(y[i], y0) == 0) {
                System.out.println("No");
                return;
            }
            a0 = x[i] - x0;
            b0 = y[i] - y0;
            x1 = x0 + a0 / 2;
            y1 = y0 + b0 / 2;
            a1 = -b0;
            b1 = a0;
            a = sqr(a1) + sqr(b1);
            b = 2 * a1 * x1 + 2 * b1 * y1;
            c = sqr(x1) + sqr(y1) - sqr(R);
            delta = Math.sqrt(sqr(b) - 4 * a * c);
            t1 = (-b + delta) / 2 / a;
            t2 = (-b - delta) / 2 / a;
            d[2 * i] = Math.atan2(y1 + t1 * b1, x1 + t1 * a1);
            d[2 * i + 1] = Math.atan2(y1 + t2 * b1, x1 + t2 * a1);
        }
        Arrays.sort(d, 0, 2 * N);
        for (int i = 0; i < 2 * N; i++)
            if (check(d[i], d[(i + 1) % (2 * N)])) {
                System.out.println("Yes");
                return;
            }
        System.out.println("No");
    }

    private static boolean check(double xt, double yt) {
        if (yt < xt) yt += 2 * Math.PI;
        xt = (xt + yt) / 2;
        yt = R * Math.sin(xt);
        xt = R * Math.cos(xt);
        for (int i = 0; i < N; i++)
            if (doubleCmp(dist(x[i], y[i], xt, yt), dist(x0, y0, xt, yt)) < 0) return false;
        return true;
    }

    private static double dist(double x1, double y1, double x2, double y2) {
        return Math.sqrt(sqr(x1 - x2) + sqr(y1 - y2));
    }

    private static int doubleCmp(double a, double b) {
        if (Math.abs(a - b) < 1e-6) return 0;
        return a < b ? -1 : 1;
    }

    private static double sqr(double x) {
        return x * x;
    }

    private static int nextInt() throws Exception {
        return Integer.parseInt(next());
    }

    private static double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    private static String next() throws Exception {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

}


							

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

//* @author: <strong>
import java.util.*;
public class Main{
 
public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    
   double p,p1,p2,p3;
   while (sc.hasNext()) {
       int n=sc.nextInt();
       int a[]=new int[n+1];
       p=sc.nextDouble();
    for (int i=1;i<=n;i++)
           a[i]=sc.nextInt();
    if (a[1]==1) {System.out.println("0.0000000");continue;}
       int now=1;
    p1=0;p2=1;
    for (int i=2;;i++) {
      p3=p2*p+(1-p)*p1;
      if (i==a[now]) {
        now++;
        if (now>n) break;
        p3=0;
      }
      if (Math.abs(p2-p3)< 1e-8&&Math.abs(p2-p1)<1e-8) i=a[now]-1;
      p1=p2;p2=p3;
    }
    System.out.printf("%.7fn",p2*(1-p));
   }
  }
}


							

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

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

public class Main {
    static int n;
    static BigInteger t=new BigInteger("1");
    static BigInteger c[][] = new BigInteger [210][210];

    /*
    static BigInteger C(int n,int m)
    {
        if(m==0||m==n)
            return BigInteger.ONE;
        BigInteger res=new BigInteger("1");
        int i;
        for(i=n;i>=n-m+1;i--)
            res=res.multiply(BigInteger.valueOf(i));
        for(i=m;i>=1;i--)
            res=res.divide(BigInteger.valueOf(i));
        return res;
    }
    */

    static int a[]=new int[202];
    static BigInteger ans[]=new BigInteger [202];

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        for(int i=0;i<=200;i++) c[i][0]=c[i][i]=BigInteger.ONE;
        for(int i=2;i<=200;i++)
        {
            for(int j=1;j<i;j++)
            {
                c[i][j]=c[i-1][j].add(c[i-1][j-1]);
            }
        }
        Scanner cin = new Scanner (new BufferedInputStream(System.in));
        while(cin.hasNext())
        {

            n=cin.nextInt();
            t=cin.nextBigInteger();
            int i,j;
            for(i=0;i<=n;i++)
                a[i]=cin.nextInt();
            for(i=0;i<=n;i++)
                ans[i]=BigInteger.ZERO;

            for(i=0;i<=n;i++)
                for(j=i;j<=n;j++)
                   if(j-i<i)
                    ans[i]=ans[i].add(c[j][j-i].multiply(t.pow(j-i)).multiply(BigInteger.valueOf(a[j])));
                   else
                    ans[i]=ans[i].add(c[j][i].multiply(t.pow(j-i)).multiply(BigInteger.valueOf(a[j])));
            for(i=0;i<n;i++)
            {
                System.out.print(ans[i]);
                System.out.print(" ");
            }
             System.out.println(ans[n]);

            /*
            String res=new String ("");
            for(i=0;i<n;i++)
            {
                res+=ans[i].toString();
                res+=" ";
            }
            res+=ans[n].toString();
            System.out.print(res);
            System.out.println();
             * */

       }
 
    }
}
							

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

//* @author 
/**
 * @version 2009/08/28
 * @author sbzlyessit
 */

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

public class Main {

    private static BufferedReader   in = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static int[] matrix = new int[300];

    public static void main(String[] argv) throws Exception {
        int  N, M;
        int  i, j, x;
        boolean found;
        while (in.ready()) {
            N = nextInt();
            M = nextInt();
            Arrays.fill(matrix, 0);
            for (i = 0; i < N; i++)
                for (j = 0; j < M; j++)
                    if (nextInt() == 1)
                        matrix[j] |= 1 <<  i;
            for (found = false, i = (1 <<  N) - 1; !found && i >= 0; i--) {
                for (j = 0; j < M; j++) {
                    x = i & matrix[j];
                    if (x == 0 || x - (x & (-x)) != 0) break;
                }
                if (j == M) {
                    found = true;
                    System.out.println("Yes, I found it");
                }
            }
            if (!found) System.out.println("It is impossible");
        }
    }

    private static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return Integer.parseInt(st.nextToken());
    }

}


							

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

//* @author: <strong>
import java.util.*;
public class Main{
 static final double pi=Math.PI;
public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    double s;
    while (sc.hasNext()) {
      s=sc.nextDouble();
      double h=Math.sqrt(2*s/pi);
      double r=Math.sqrt(s*s/(pi*pi*h*h+2*pi*s));
      double v=(1.0/3.0)*(s*s)*h/(pi*h*h+2*s);
      System.out.printf("%.2fn%.2fn%.2fn",v,h,r);
    }
  }
}

							

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

//* @author: 
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.Comparator;
import java.util.ArrayList;
public class Main {
 public static class node
 {
  double x,y,s,r,d,t;
  node(double xx,double yy,double ss,double rr,double dd,double tt)
  {
   x=xx;y=yy;s=ss;r=rr;d=dd;t=tt;
  }
  double getx(){return x;}
  double gety(){return y;}
  double gets(){return s;}
  double getr(){return r;}
  double getd(){return d;}
  double gett(){return t;}
 }
/* class MyComparator implements Comparator
 {
     public int compare(Object  obj1, Object obj2) 
     {
      node w1 = (node)obj1;
      node w2 = (node)obj2;
         return w1.get() < w2.get() ? 1 : -1;
     }
 }*/

 public static void main(String[] args) {
    int n,i;
    double pt,hp,x,y,s,r,d,t;
    Scanner in =new Scanner(System.in);
    
    node p[] = new node [101];
    while(in.hasNext())
    {
     n=in.nextInt();
     pt=100;
        for(i=0;i< n;i++)
        {
         x=in.nextDouble();
         y=in.nextDouble();
         s=in.nextDouble();
         r=in.nextDouble();
         d=in.nextDouble();
         t=Math.sqrt((x-100.0)*(x-100.0)+y*y)-r;
         if(t< 0) t=0;
         p[i]=new node(x,y,s,r,d,t);
        }
        hp=in.nextDouble();
           Arrays.sort(p, 0, n, new Comparator< node>(){
               public int compare(node w1, node w2) {
                  return w1.gett() > w2.gett() ? 1 : -1;
               }
           });

//    for(i=0;i< n;i++)System.out.println(p[i].t);
           i=0;
           while(p[i].gett()<=pt)
           {                 
              hp-=p[i].getd();
              pt+=p[i].gets();
              i++;
              if(i==n)break;
           }
           if(hp<=0)System.out.println("Danger!");
           else System.out.println("Safe!");
    }
    }
}
 

							

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

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

public class Main {

/**
 * @param args
 * @return 
 */
 static int pow_mod(int a,int b,int c)
 {
    int r=1,d=a;
    while(b>0){
        if((b&1)==1) r = r*d%c;
        d = d*d%c;
        b>>=1;
    }
    return r;
  }
  
public static void main(String[] args)throws Exception {
    // TODO Auto-generated method stub
    int ans,t,n;
    Scanner cin = new Scanner(System.in);
    
    t = cin.nextInt();
    for(int i=0;i< t;i++)
    {
        n = cin.nextInt();
        ans = pow_mod(2,n-1,10007);
        ans = (ans+1) *ans %10007;
        System.out.println(ans);
    }
  }

}

							

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

//* @author: 
//Kruskal �㷨:
import java.io.*;
import java.util.*;

class cin
{
static int leave=0;
static StringTokenizer st;
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static int nextInt() throws Exception
{
    while (leave==0)
    {
     st=new StringTokenizer(in.readLine());
     leave=st.countTokens();
    }
    leave--;
    return Integer.parseInt(st.nextToken());
}
}

class E
{
int weight,from,to;
void init(int x,int y,int z)
{
   weight=z;
   from=x;
   to=y;
}
}

class Cmp implements Comparator
{
public int compare(Object a,Object b)
{
   int c=((E)a).weight-((E)b).weight;
   if(c< 0)return -1;
   return 1;
}
}

class Set
{
int father[];
int num;
Set(int n)
{
   num=n;
   father=new int[n];
   this.clear();
}

void clear()
{
   int i;
   for(i=0;i< num;i++)father[i]=i;
}

int findF(int x)
{
   int t=x;
   while(t!=father[t])
   {
    t=father[t];
   }
   while(x!=father[x])
   {
    father[x]=t;
    x=father[x];
   }
   return t;
}

boolean union(int x,int y)
{
   int fx=findF(x),fy=findF(y);
   if(fx==fy)return false;
   father[fy]=fx;
   num--;
   return true;
}
}

class Kruskal
{
E e[];
int numOfE,numOfTree,i,j,numOfD;
Set points;

Kruskal(E a[],int m,int n)
{
   e=a;
   numOfE=m;
   numOfD=n;
   points=new Set(numOfD);
}

int cost()
{
   int sum=0,f1,f2;
   Arrays.sort(e,new Cmp());
   for(i=0;i< numOfE;i++)
   {
    if(points.num==1)break;
    if(points.union(e[i].from,e[i].to))
    {
     sum+=e[i].weight;
    }
   }
   return sum+10000*points.num;
}

}
public class Main {
    public static void main(String args[]) throws Exception
    {
    int g,b,r,t,i;
    E e[];
    t=cin.nextInt();
    Kruskal data;
    while((t--)>0)
    {
       g=cin.nextInt();
       b=cin.nextInt();
       r=cin.nextInt();
       e=new E[r];
       for(i=0;i< r;i++)
       {
        e[i]=new E();
        e[i].init(cin.nextInt(),cin.nextInt()+g,10000-cin.nextInt());
       }
       data=new Kruskal(e,r,g+b);
       System.out.println(data.cost());
    }
    }
}
							

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


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * @author Administrator ѭ��С��+ѭ����
 */
public class Main {
    /**
     *����
     */
    private int numerator;
    /**
     *��ĸ
     */
    private int denominator;
    /**
     * ѭ���ڲ��ᳬ��100�����
     */
    private static int MAX_NUM = 101;

    /**
     * @return��ȡС����ʽ���㵽ѭ����+ѭ���ڴ�С ������numerator>=denominator�����;ֻ���������
     */
    private class Node {
        private boolean RemainFlag[];

        private int RemainPreFlag[];

        public boolean[] getRemainFlag() {
            return RemainFlag;
        }

        public void setRemainFlag(boolean[] remainFlag) {
            RemainFlag = remainFlag;
        }

        public int[] getRemainPreFlag() {
            return RemainPreFlag;
        }

        public void setRemainPreFlag(int[] remainPreFlag) {
            RemainPreFlag = remainPreFlag;
        }

    }

    private class Result {

        private int result[];

        private int size;

        public int[] getResult() {
            return result;
        }

        public void setResult(int[] result) {
            this.result = result;
        }

        public int getSize() {
            return size;
        }

        public void setSize(int size) {
            this.size = size;
        }

    }

    public Result getRepeatingPresentation(int numerator, int denominator) {

        int gcd = getGCD(numerator, denominator);
        numerator /= gcd;
        denominator /= gcd; // ���������ʽ
        Result res = new Result();
        res.result = new int[MAX_NUM];
        int remain;
        Node node = new Node();
        node.RemainFlag = new boolean[MAX_NUM];
        node.RemainPreFlag = new int[MAX_NUM];
        for (int i = 0; i < MAX_NUM; i++) {
            node.RemainFlag[i] = false;
            node.RemainPreFlag[i] = 0;
        }
        remain = numerator;
        int i = 0;
        while (true) {
            int tmp = remain * 10 % denominator; // ����
            if (true == node.RemainFlag[tmp]
                    && node.RemainPreFlag[tmp] == remain) {
                break;
            }
            node.RemainFlag[tmp] = true;
            node.RemainPreFlag[tmp] = remain;
            res.result[i] = remain * 10 / denominator; // ��
            remain = remain * 10 % denominator; // ����
            //System.out.print(res.result[i]);
            res.size = i;
            i++;
            if (tmp == 0)
                break;

        }
        return res;

    }

    /**
     * @param a
     * @param b
     * @return ���Լ��+շת���
     */
    public int getGCD(int a, int b) {
        if (a % b == 0)
            return b;
        else
            return getGCD(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        Main t = new Main();
        // t.getRepeatingPresentation(1,6);
        BufferedReader stdin = new BufferedReader(new InputStreamReader(
                System.in));

        while (true) {
            String line = stdin.readLine();
            if(line==null) break;
            StringTokenizer st = new StringTokenizer(line);
            String a1 = st.nextToken();
            String b1 = st.nextToken();
            int a = Integer.parseInt(a1);
            int b = Integer.parseInt(b1);
            Result res[] = new Result[a + 1];
            for (int i = 2; i <= a; i++) {
                res[i] = t.getRepeatingPresentation(1, i);
                //System.out.println();
            }
            int sum = 0;
            for (int i = 2; i <= a; i++) {
                for (int j = 0; j <= res[i].size; j++) {
                    if (res[i].result[j] == b)
                        sum++;
                }
            }
            System.out.println(sum);
        }

    }

    public int getNumerator() {
        return numerator;
    }

    public void setNumerator(int numerator) {
        this.numerator = numerator;
    }

    public int getDenominator() {
        return denominator;
    }

    public void setDenominator(int denominator) {
        this.denominator = denominator;
    }

}


							

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

import java.util.*;
import java.math.*;
public class Main {
    static BigInteger x,y;
    static BigInteger[] a=new BigInteger[1000];
    static BigInteger[] m=new BigInteger[1000];
    static void egcd(BigInteger a,BigInteger b){
        if(b.equals(BigInteger.ZERO)){
            x=BigInteger.ONE;
            y=BigInteger.ZERO;
            return ;
        }
        egcd(b,a.mod(b));
        BigInteger temp=y;
        y=x.subtract((a.divide(b)).multiply(y));
        x=temp;
    }
    static BigInteger solve(int n){
        BigInteger M=BigInteger.ONE;
        BigInteger ans=BigInteger.ZERO;
        BigInteger mk=null;
        for(int i=0;i< n;i++)
            M=M.multiply(m[i]);
        for(int i=0;i< n;i++){
            mk=M.divide(m[i]);
            egcd(mk,m[i]);
            ans=ans.add(x.multiply(mk).multiply(a[i])).mod(M);
        }
        if(ans.compareTo(BigInteger.ZERO)<0)
            ans=ans.add(M);
        return ans;
    }
    static int[] a1=new int[1000];
    static int[] a2=new int[1000];
    static int[] m1=new int[1000];
    static int[] k1=new int[1000];
    static int[] w1=new int[1000];
    static int[] w2=new int[1000];
    static int[] w3=new int[101];
    static int[] w4=new int[101];
    static int[] w5=new int[101];
    static String mm;
    static String kk;
    static int prime(int x,int y){
        for(int i=2;x>1;i=i*i<=x?i+1:x)
            if(x%i==0){
                int k=0,p=1;
                while(x%i==0){
                    x/=i;
                    k++;
                    p=p*i;
                }
                //System.out.println("w5[i]="+w5[i]+",i="+i+",p="+p+",y="+y);
                if(w5[i]!=0&&w3[w5[i]]%p!=y%p&&w3[w5[i]]%w5[i]!=y%w5[i])
                    return 0;
                p=i;
                for(int j=1;j< k;j++){
                    w4[p]=0;
                    p*=i;
                }
                w3[p]=y%p;
                if(w5[i]< p)
                    w5[i]=p;
            }
        return 1;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while(true){
            int d=Integer.parseInt(in.next());
            if(d==-1)
                break;
            for(int i=1;i< d;i++)
                a1[i]=Integer.parseInt(in.next());
            for(int i=0;i< d;i++)
                a2[i]=Integer.parseInt(in.next());
            mm=in.next();
            kk=in.next();
            int l1=0,l2=0;
            BigInteger m2=new BigInteger(mm);
            while(!m2.equals(BigInteger.ZERO)){
                m1[l1++]=m2.mod(BigInteger.valueOf(d)).intValue();
                m2=m2.divide(BigInteger.valueOf(d));
            }
            BigInteger k2=new BigInteger(kk);
            while(!k2.equals(BigInteger.ZERO)){
                k1[l2++]=k2.mod(BigInteger.valueOf(d)).intValue();
                k2=k2.divide(BigInteger.valueOf(d));
            }
            if(l1!=l2){
                System.out.println("NO");
                continue ;
            }
            int q=a1[m1[l1-1]];
            int l=1;
            w1[0]=-1;
            boolean mark=true;
            for(int i=1;i<=d;i++){
                if(q==k1[l1-1]){
                    w1[0]=i;
                }
                if(q==m1[l1-1]){
                    w2[0]=l;
                    break;
                }
                q=a1[q];
                l++;
            }
            if(w1[0]==-1){
                System.out.println("NO");
                mark=false;
                continue ;
            }
            for(int i=1;i< l1;i++){
                q=a2[m1[l1-1-i]];
                l=1;
                w1[i]=-1;
                for(int j=0;j<=d;j++){
                    if(q==k1[l1-i-1]){
                        w1[i]=j+1;
                    }
                    if(q==m1[l1-1-i]){
                        w2[i]=l;
                        break;
                    }
                    l++;
                    q=a2[q];
                }
                if(w1[i]==-1){
                    System.out.println("NO");
                    mark=false;
                    break;
                }
            }
            if(!mark)
                continue ;
            int num=0;
            for(int i=0;i<=d;i++){
                w3[i]=-1;
                w4[i]=1;
                w5[i]=0;
            }
            int tt=0;
            for(int i=0;i< l1;i++){
                if((tt=prime(w2[i],w1[i]))==0){
                    mark=false;
                    System.out.println("NO");
                    break;
                }
            }
            if(!mark)
                continue ;
            for(int i=0;i<=d;i++)
                if(w3[i]!=-1&&w4[i]==1){
                    a[num]=BigInteger.valueOf(w3[i]);
                    m[num++]=BigInteger.valueOf(i);
                    //System.out.println("i="+i+",w="+w3[i]);
                }
            if(num==0)
                System.out.println(1);
            else System.out.println(solve(num));
        }
    }

}


							

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

//* @author: 
import java.util.Scanner;

public class Main {
Scanner cin = new Scanner(System.in);
int n;

public void inPut() {
   n = cin.nextInt();

   reverse();
}

private void reverse() {
   if (n == 1) {
    System.out.println(0);
   } else {
    if (n == 2) {
     System.out.println(1);
     System.out.println(2 + " " + 1 + " " + 0);
    } else {
     if (n % 2 == 0) {
      int m = (n + 1) / 2 + 1;
      System.out.println(m);
      print(n, m);
     } else {
      if(n % 2 != 0) {
       int m = (n + 1) / 2;
       System.out.println(m);
       print(n, m);
      }
     }
    }
   }
}

void print(int n, int m) {
   if (n % 2 != 0) {
    for (int i = 0; i < m - 1; i++) {
     System.out.println((n / 2 + i + 1) + " " + 2 + " " + i);
    }
    System.out.println(1 + " " + (n - 1) / 2 + " " + (n - 1) / 2);

   } else {
    for (int i = 0; i < m - 2; i++) {
     System.out.println((n / 2 + i + 1) + " " + 2 + " " + (i + 1));
    }
    System.out.println(2 + " " + (n - 1) / 2 + " " + (n) / 2);
    System.out.println(1 + " " + 1 + " " + (n - 1));
   
   }
}

public static void main(String[] args) {
   new Main().inPut();
}

}

							

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

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

public class Main
{
    public static int b;
    public static int g;
    public static int m;
    public static boolean[][] graph;
    public static boolean[] checked;
    public static int[] link;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    graph = new boolean[200][200];
    checked = new boolean[200];
    link = new int[200];
    int t = 0;

    while(true)
    {
        b = sc.nextInt();
        g = sc.nextInt();
        m = sc.nextInt();

        if(b == 0 && g == 0 && m == 0)
        {
            break;
        }

        Arrays.fill(checked,false);
        Arrays.fill(link,-1);

        for(int i = 0; i < b; i++)
        {
            Arrays.fill(graph[i],true);
        }
        for(int i = 0; i < m; i++)
        {
            int a = sc.nextInt();
        int b = sc.nextInt();
        graph[a-1][b-1] = false;
        }
        int ans = 0;
        for(int i = 0; i < b; i++)
        {
            Arrays.fill(checked,false);
        if(find(i))
        {
            ans++;
        }
        }
        System.out.println("Case " + (++t) + ": " + (g+b-ans));
    }
    }

    public static boolean find(int a)
    {
        for(int i = 0; i < g; i++)
    {
        if(graph[a][i] && !checked[i])
        {
        checked[i] = true;
        if(link[i] == -1 || find(link[i]))
        {
            link[i] = a;
            return true;
        }
        }
    }
    return false;
    }
}

							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  int degree[]=new int[210];
  boolean visit[][]=new boolean[210][210];
  int path[]=new int[210];
  int n,m,t;

  void topsort(){
     for(int k=n;k>=1;k--){
          int i=n;
          while(i>=1 && degree[i]!=0) i--;
          if(i< 1){ System.out.printf("-1n"); return; }
          degree[i]=-1; 
          path[i]=k; 
          for(int x=1;x<=n;x++) if(visit[x][i]) degree[x]--;
     }    
     for(int j=1;j<=n;j++)  System.out.printf("%d ",path[j]);
     System.out.printf("n");     
}

 public void doit(){
   Scanner sc=new Scanner(System.in);
 
    int x,y;
    t=sc.nextInt();
    while((t--)!=0){
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(degree,0);
        for(int i=0;i< visit.length;i++)
           Arrays.fill(visit[i],false);
        for(int i=1;i<=m;i++){
           x=sc.nextInt();
           y=sc.nextInt();
           if(!visit[x][y]){
              visit[x][y]=true;
              degree[x]++;              
            }  
        }       
        topsort();
    }
  }
 public static void main(String args[]){
   Main m=new Main();
     m.doit();
  }
}
							

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

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

class Main
{
 static int armor[];
 final static int MAX = 1000000;
 static class Node
 {
    Node l = null, r = null;
    int flag, step, value;
    Node(int k, int v)
    {
         flag = 0;
     step = MAX;
     value = v;
     if(k>=0&&v<=30)
     {
        l = new Node(k, v+armor[k]);
        r = new Node(k-1, v);
     }
    }
    

  int update(int f, int v, int s)
  {
    if(value>v||l==null&&r==null)return MAX;
    if(f==flag)step = Math.min(s, step);
    else step = s;
    s = step;
    flag = f+1;
    //System.err.println(value+":"+s);
    if(value==v)return s;
    return step = Math.min(l.update(f, v, s+1)+1, r.update(f, v, s));
  }
  int query(int v)
  {
    if(l==null&&r==null)return MAX;
    if(value==v)return step;
    return Math.min(l.query(v), r.query(v));
  }
 }

 public static void main(String[] args) throws IOException
 {
  Scanner in = new Scanner(System.in);
  for(int T = in.nextInt(); T!=0; --T)
  {
    int n = in.nextInt();
    armor = new int[n];
    for(int i=0; i!=n; ++i)
        armor[i] = in.nextInt();
    Arrays.sort(armor);
    int cnt=0;
    Node root = new Node(n-1, 0);
    root.step = 0;
    int k = 0, m = in.nextInt();
    for(int i=0; i!=m; ++i)
        root.update(cnt++, k=in.nextInt(), MAX);
    k = root.query(k);
    if(k==MAX)System.out.println(-1);
    else System.out.println(k);
    }
  }
}

							

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

import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
  Scanner scanner=new Scanner(System.in);
  String str1=scanner.next();
  String str2=scanner.next();
  char[] array1=str1.toCharArray();
  char[] array2=str2.toCharArray();
  int sum1=0;
  for(int i=0;i< array1.length;i++){
    sum1+=array1[i]-48;
   }

  int sum2=0;
  for(int i=0;i< array2.length;i++){
   sum2+=array2[i]-48;
  }

  System.out.println(""+(sum1*sum2));
 }
}
							

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

//* @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 M = in.nextInt();
        int T = in.nextInt();
        int U = in.nextInt();
        int F = in.nextInt();
        int D = in.nextInt();
        int num = 0;
        int sum = 0;
        for(int i = 0; i < T; i++)
        {
            String s = in.next();
            if(sum > M)
                break;
            if(s.equals("u") || s.equals("d"))
                sum += U + D;
            else if(s.equals("f"))
                sum += F + F;
            num++;
        }
        System.out.println(num - 1);
    }

}

							

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

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;
  int v[]=new int[30002];
  int f[]=new int[30002];
  int g[]=new int[30002];
  n=sc.nextInt();
  for(int i=1;i<=n;i++)
    v[i]=sc.nextInt();
  
 f[0]=0; g[n+1]=0;
 for(int i=1;i<=n;i++){
     if(v[i]==2) f[i]=f[i-1]+1;
      else f[i]=f[i-1];     
  }
  for(int i=n;i>=1;i--){
      if(v[i]==1) g[i]=g[i+1]+1;
       else g[i]=g[i+1];       
  }
  int mins=100000000;
  for(int i=0;i<=n;i++)
      if(f[i]+g[i+1]< mins)
  mins=f[i]+g[i+1];
 System.out.printf("%dn",mins);
 }
}
							

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  static int mintwo(int a,int b){ return a< b?a:b; }
  static int minthird(int a,int b,int c){
    int temp=mintwo(a,b);
    return mintwo(temp,c);   
} 

 public static void main(String args[]){
   Scanner sc=new Scanner(System.in);
 
   int f[][]=new int[30010][3];
   int g[][]=new int[30010][3];
   int v[]=new int[30010];
   int n=sc.nextInt();
    
  for(int i=1;i<=n;i++){
   v[i]=sc.nextInt();  
   f[i][0]=f[i-1][0];
   if(v[i]!=1) f[i][0]++;
   f[i][1]=mintwo(f[i-1][0],f[i-1][1]);
   if(v[i]!=2) f[i][1]++;
   f[i][2]=minthird(f[i-1][0],f[i-1][1],f[i-1][2]);
   if(v[i]!=3) f[i][2]++;                 
  }
     for(int i=1;i<=n;i++){
        g[i][2]=g[i-1][2];
        if(v[i]!=3) g[i][2]++;
        g[i][1]=mintwo(g[i-1][2],g[i-1][1]);
        if(v[i]!=2) g[i][1]++;
        g[i][0]=minthird(g[i-1][2],g[i-1][1],g[i-1][0]);
        if(v[i]!=1) g[i][0]++;        
     }
     int mins=100000000;
     for(int i=0;i< 3;i++){
          if(mins>f[n][i]) mins=f[n][i];
          if(mins>g[n][i]) mins=g[n][i];       
     }
     System.out.printf("%dn",mins);
   }
}
							

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

/* @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 arr[]=new int[10010];
 int n,m,i,j,u;
 n=sc.nextInt();
 m=sc.nextInt();
 for(i=0;i< n;i++)
    arr[i]=sc.nextInt();
 for(i=0;i< m;i++)
 {
   int maxx=-1,tag=0;
   for(j=0;j< n;j++)
    if(arr[j]>maxx)
    {
    maxx=arr[j];
    tag=j;
     }
   System.out.printf("%dn",tag+1);
   int add=arr[tag]/(n-1);
   int mod=arr[tag]%(n-1);
   for(j=0;j< n;j++)
    arr[j]+=add;
   for(j=0;j< mod;j++)
   {
    arr[j]++;
    if(j==tag) mod++;
   }
   arr[tag]=0;
  }
 }
}
							

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

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

public class Main {
    static class vote {
        int first;
        int second;
        int index;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        // vote[] voters = new vote[N];
        ArrayList< vote> voters = new ArrayList< vote>();
        for (int i = 0; i < N; i++) {
            vote temp = new vote();
            temp.first = in.nextInt();
            temp.second = in.nextInt();
            temp.index = i + 1;
            voters.add(temp);
        }
        Collections.sort(voters, new Comparator< Object>() {
            public int compare(Object o1, Object o2) {
                vote a = (vote) o1;
                vote b = (vote) o2;
                return b.first - a.first;
            }

        });
        
        int result = 0;
        for (int i = 1; i < K; i++) {
            if (voters.get(result).second < voters.get(i).second) {
                
                result = i;
            }
        }
        System.out.println(voters.get(result).index);
    }
}