Poj Solution 3768

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


							
Posted in poj | Leave a comment

Poj Solution 3767

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

  }
 } 

}

							
Posted in poj | Leave a comment

Poj Solution 3763

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

							
Posted in poj | Leave a comment

Poj Solution 3753

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


							
Posted in poj | Leave a comment

Poj Solution 3752

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


							
Posted in poj | Leave a comment

Poj Solution 3751

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

							
Posted in poj | Leave a comment

Poj Solution 3750

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;
}
							
Posted in poj | Leave a comment

Poj Solution 3749

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;
        }
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3748

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

							
Posted in poj | Leave a comment

Poj Solution 3747

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

}


							
Posted in poj | Leave a comment

Poj Solution 3744

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


							
Posted in poj | Leave a comment

Poj Solution 3742

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();
             * */

       }
 
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3740

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

}


							
Posted in poj | Leave a comment

Poj Solution 3737

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

							
Posted in poj | Leave a comment

Poj Solution 3736

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

							
Posted in poj | Leave a comment

Poj Solution 3734

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

}

							
Posted in poj | Leave a comment

Poj Solution 3723

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());
    }
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3720

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

}


							
Posted in poj | Leave a comment

Poj Solution 3708

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

}


							
Posted in poj | Leave a comment

Poj Solution 3705

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

}

							
Posted in poj | Leave a comment

Poj Solution 3692

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

							
Posted in poj | Leave a comment

Poj Solution 3687

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();
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3677

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

							
Posted in poj | Leave a comment

Poj Solution 3673

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));
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3672

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

//* @author ������&lt;hongxp11@163.com&gt;
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);
    }

}

							
Posted in poj | Leave a comment

Poj Solution 3671

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);
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3670

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);
   }
}
							
Posted in poj | Leave a comment

Poj Solution 3665

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;
  }
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3664

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

//* @author ������&lt;hongxp11@163.com&gt;
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);
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3663

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int b=in.nextInt();
  ArrayList< Integer> arr=new ArrayList< Integer>();
  for(int i=0;i< a;i++)
    arr.add(in.nextInt());
  Collections.sort(arr);
  int count=0;
  for(int i=0;i< a-1;i++)
  {
    int l=b-arr.get(i);
    int min=i+1;
    int max=a-1;
    boolean bb=false;
    while(max>min)
    {
        int mid=(max+min)/2;
        if(arr.get(mid)>l) max=mid-1;
        else if(arr.get(mid)<=l) min=mid+1;
        bb=true;
        
    }
    if(bb)
    {
        if(arr.get(min)>l) count--;
        count+=min-i;
    }
    
    }
    System.out.println(count);
  }
}

							
Posted in poj | Leave a comment

Poj Solution 3660

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

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

public class Main{
 public static void main(String[] args){
  Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n=in.nextInt();
        int m=in.nextInt();
        int[][] p=new int[n][n];
        for (int i=0;i< n ;i++ ){
            for (int j=0;j< n ;j++ ){
                p[i][j]=101;
            }
            p[i][i]=0;
        }
        for (int i=0;i< m ;i++ ){
            p[in.nextInt()-1][in.nextInt()-1]=1;
        }
        for (int k=0;k< n ;k++ ){
            for (int i=0;i< n ;i++ ){
                for (int j=0;j< n ;j++ ){
                 p[i][j]=getMin(p[i][j],p[i][k]+p[k][j]);
                }
            }
        }
        int w=0;
        for (int i=0;i< n ;i++ ){
            int t=0;
            for (int j=0;j< n ;j++ ){
                if (p[i][j]< 101||p[j][i]< 101){
                    t++;
                }
            }
            if (t==n){
                w++;
            }
        }
        System.out.println(w);
    }

    public static int getMin(int a,int b){
        if (a>=b){
            return b;
        }
        else{
            return a;
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3658

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

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

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

public class Main {

    private static final int        MAX_N = 100000;

    private static BufferedReader   in =new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static int[]            height = new int[MAX_N];
    private static long[]           width = new long[MAX_N + 1];
    private static long[]           area = new long[MAX_N + 1];
    private static int[]            l = new int[MAX_N], r = new int[MAX_N];
    private static int[]            stack = new int[MAX_N + 1];
    private static int[]            min = new int[MAX_N], max = new int[MAX_N];
    private static long[]           base = new long[MAX_N];
    private static boolean[]        used = new boolean[MAX_N];
    private static long[]           result = new long[MAX_N];
    private static int              N, pos, root;

    public static void main(String[] argv) throws Exception {
        readIn();
        solve();
    }

    private static void readIn() throws Exception {
        int top = 0, minH = Integer.MAX_VALUE;
        int i, x;
        N = nextInt();
        width[0] = area[0] = 0;
        for (i = 0; i < N; i++) {
            x = nextInt();
            height[i] = nextInt();
            width[i + 1] = width[i] + x;
            area[i + 1] = area[i] + (long) x * height[i];
            if (height[i] < minH) {
                minH = height[i];
                pos = i;
            }
            for (stack[top] = -1; top > 0 && height[stack[top - 1]] < height[i]; top--);
            if (top > 0) {
                r[stack[top - 1]] = i;
            }
            l[i] = stack[top] != -1 ? stack[top] : -1;
            r[i] = -1;
            stack[top++] = i;
        }
        root = stack[0];
    }

    private static void solve() {
        int top = 0;
        int i, x, y;
        stack[top++] = root;
        min[root] = 0; max[root] = N;
        base[root] = 0;
        while (top > 0) {
            x = stack[top - 1];
            if (!used[x]) {
                result[x] = base[x] + (width[max[x]] - width[min[x]]) * (height[x] + 1) - 
                       area[max[x]] + area[min[x]];
                used[stack[top - 1]] = true;
            }
            if ((y = getChild(x)) == 0) {
                top--;
            } else if (y < 0) {
                stack[top++] = l[x];
                min[l[x]] = min[x]; max[l[x]] = x;
                base[l[x]] = base[x] + (pos > x ? (width[max[x]] - width[x + 1]) * height[x] -
                        area[max[x]] + area[x + 1] : 0);
            } else {
                stack[top++] = r[x];
                min[r[x]] = x + 1; max[r[x]] = max[x];
                base[r[x]] = base[x] + (pos < x ? (width[x] - width[min[x]]) * height[x] -
                        area[x] + area[min[x]] : 0);
            }
        }
        for (i = 0; i < N; i++) {
            System.out.println(result[i]);
        }
    }

    private static int getChild(int x) {
        if (l[x] != -1 && !used[l[x]]) {
            return -1;
        } else if (r[x] != -1 && !used[r[x]]) {
            return 1;
        }
        return 0;
    }

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

}


							
Posted in poj | Leave a comment

Poj Solution 3657

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

 
							
Posted in poj | Leave a comment

Poj Solution 3653

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

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

public class Main {
 static final int INF = 100000000;
 public static void main(String[] args){
   Scanner in = new Scanner(new BufferedInputStream(System.in));
   int x = in.nextInt();
   int y = in.nextInt();
   while(x != 0 || y != 0){
    int w[][] = new int[(x+1)*(y+1)+1][(x+1)*(y+1)+1];
    //int num = 1;
    int row = 1;
    for(int i = 1; i <= 2*x+1; i++){
        if(i % 2 == 1){
       //num = (row-1)*(y+1) + 1;
       for(int j = 1; j <= y; j++){
        int tm = in.nextInt();
        String tms = in.next();
                        
        if(tms.equals("*")){
          w[(row-1)*(y+1)+j][(row-1)*(y+1)+j+1] = tm;
          w[(row-1)*(y+1)+j + 1][(row-1)*(y+1)+j] = tm;
        }
        else if(tms.equals("< ")){
          w[(row-1)*(y+1)+j + 1][(row-1)*(y+1)+j] = tm;
        }
        else if(tms.equals(">")){
          w[(row-1)*(y+1)+j][(row-1)*(y+1)+j+1] = tm;
        }
        }
        row++;
      }
     else{
       for(int j = 1; j <= y + 1; j++){
        int tm = in.nextInt();
        String tms = in.next();
            
          if(tms.equals("*")){
        w[(row-2)*(y+1) + j][(row-1)*(y+1) + j] = tm;
        w[(row-1)*(y+1) + j][(row-2)*(y+1) + j] = tm;
       }
      else if(tms.equals("^")){
        w[(row-1)*(y+1) + j][(row-2)*(y+1) + j] = tm;
      }
      else if(tms.equals("v")){
        w[(row-2)*(y+1) + j][(row-1)*(y+1) + j] = tm;
      }
    }
    }
   }
  for(int p = 1; p <= (x+1)*(y+1); p++){
   for(int q = 1; q <= (x+1)*(y+1); q++){
    if(p == q){
         continue;
    }
    if(w[p][q] > 0){
      w[p][q] = 2520/w[p][q];
      continue;
    }
    w[p][q] = INF;
     }
   }
            
   dijkstra(w, (x+1)*(y+1));            
   x = in.nextInt();
   y = in.nextInt();
 }
}

public static void dijkstra(int w[][], int v){
  int i, vnear = 0;
  int touch[] = new int[v+1];
  int length[] = new int[v+1];
  boolean y[] = new boolean[v+1];
  int map[] = new int[v+1];
  PriorityQueue< Item> heap = new PriorityQueue< Item>(v, new ItemCompare());
        
  for(i = 2; i <= v; i++){
   length[i] = w[1][i];
   if(length[i] < INF){
    heap.add(new Item(1, i, w[1][i]));
   }
  }
  //System.out.println(heap);
  while(!heap.isEmpty()){
    Item temp = heap.remove();
            
    for(i = 1; i <= v; i++){
        if(i == temp.sv){
        continue;
      }
      else if(w[temp.ev][i] == INF){
        continue;
      }
      if(length[temp.ev] + w[temp.ev][i] < length[i]){
       length[i] = length[temp.ev] + w[temp.ev][i];
       heap.add(new Item(temp.ev, i, length[i]));
      }
     }
    }
    if(length[v] < INF){
      System.out.println(length[v] + " blips");
    }
    else{
      System.out.println("Holiday");
    }
    }
    
}

class Item{
 int sv;
 int ev;
 int w;
    
 Item(int sv, int ev, int w){
    this.sv = sv;
    this.ev = ev;
    this.w  = w;
   }
    
  public String toString(){
    return this.sv + " " + this.ev +" " + this.w;
  }
}

class ItemCompare implements Comparator< Item>{
    public int compare(Item i1, Item i2){
        return (i1.w - i2.w);
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3652

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

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

 public class Main {

     int a;
     int b;
     int c;
     int s;
     int x;
     char[] result;
     int flg;
     boolean[] dup;

     public Main() {
         Scanner scan = new Scanner(System.in);
         while ((a = scan.nextInt()) != 0) {
             b = scan.nextInt();
             c = scan.nextInt();
             s = scan.nextInt();
             result = new char[16];
             Arrays.fill(result, '0');
             initFlg(Integer.toBinaryString(s));
             dup = new boolean[c];
             dup[s] = true;
             x = (a * s + b) % c;
             while (!dup[x]) {
                 dup[x] = true;
                 if (setFlg(Integer.toBinaryString(x))) {
                     break;
                 }
                 x = (a * x + b) % c;
             }
             System.out.println(result);
         }
     }

     public void initFlg(String str) {
         for (int i = 15, k = str.length() - 1; k >= 0; i--, k--) {
             if (str.charAt(k) == '1') {
                 result[i] = '1';
             }
         }
     }

     public boolean setFlg(String str) {
         flg = 0;
         for (int i = 15, k = str.length() - 1; k >= 0; i--, k--) {
             if (result[i] == '?') {
                 flg++;
                 if (flg == 16) {
                     return true;
                 }
                 continue;
             } else {
                 if (str.charAt(k) != result[i]) {
                     result[i] = '?';
                 }
             }
         }
         return false;
     }

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

 } 

							
Posted in poj | Leave a comment

Poj Solution 3650

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

//* @author ������&lt;hongxp11@163.com&gt;
import java.util.Scanner;


public class Main {
 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
   while(true)
    {
       String input = in.nextLine();
    if(input.equals("#"))
        break;
    int len = input.length();
    for(int i = 0; i < len; i++)
    {
        if(input.charAt(i)==' ')
            System.out.print("%20");
        else if(input.charAt(i)=='!')
            System.out.print("%21");
        else if(input.charAt(i)=='$')
            System.out.print("%24");
        else if(input.charAt(i)=='%')
            System.out.print("%25");
        else if(input.charAt(i)=='(')
            System.out.print("%28");
        else if(input.charAt(i)==')')
            System.out.print("%29");
        else if(input.charAt(i)=='*')
            System.out.print("%2a");
        else
            System.out.print(input.charAt(i));
    }
    System.out.println();
    }
  }
}

							
Posted in poj | Leave a comment

Poj Solution 3646

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

//* @author: 
import java.util.*;
public   class Main{    
   
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
 
    int i,j,ans;
    end: while (sc.hasNext()) {
        int n=sc.nextInt();
        if(n==0) break;
        int m=sc.nextInt();
        int a[]=new int[n+1];
        int b[]=new int[m+1];
       
        for ( i=1;i<=n;i++) 
           a[i]=sc.nextInt();
        for ( i=1;i<=m;i++) 
           b[i]=sc.nextInt();
        Arrays.sort(a, 1,n+1);
        Arrays.sort(b,1,m+1);
        for (ans=0,j=i=1;i<=n;i++) {
        if (j>m) {
             System.out.println("Loowater is doomed!");
              continue end;
         }
            while (a[i]>b[j]) {
              j++;if (j>m) {
                System.out.println("Loowater is doomed!");
                continue end;
              }
            }
            ans+=b[j];j++;
        }
        System.out.printf("%dn",ans);
       
    }
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3641

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
    long p=in.nextLong();
    long a=in.nextLong();
    if(a==0&&p==0) break;
    if(isPrime(p)){
        System.out.println("no");
        continue;
    }
    System.out.println(sum(a,p,p)==a?"yes":"no");
   }
  }

 public static boolean isPrime(long a)
 {
    if(a==2) return true;
    for(int i=3;i<=Math.sqrt(a);i+=2)
        if(a%i==0) return false;
    return true;
  }

 public static long sum(long a,long n,long p)
 {
    if(n==0) return 1;
    long w=sum(a*a%p,n/2,p);
    if(n%2==1) w=(w*a)%p;
    return w;
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3640

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

//* @author ������&lt;hongxp11@163.com&gt;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

/**
 * @param args
 * @throws IOException
 * @throws NumberFormatException
 */
public static void main(String[] args) throws NumberFormatException,
    IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  while (true) {
    Map< String, Integer> map = new HashMap< String, Integer>();
    int max = 0;
    int n = Integer.parseInt(br.readLine());
    if (n == 0)
        break;
    for (int i = 0; i < n; i++) {
        String s = br.readLine();
        String[] array = s.split(" ");
        Arrays.sort(array);
        String key = new String();
        for (int j = 0; j < array.length; j++) {
            key += array[j];
        }
        // System.out.println("key:"+key);
        if (map.get(key) == null)
            map.put(key, 1);
        else {
            // System.out.println("here");
            map.put(key, map.get(key) + 1);
        }
        if (max < map.get(key))
            max = map.get(key);
    }
    int result = 0;
    Set<String> set = map.keySet();
    for (String s : set) {
        if (max == map.get(s))
            result += max;
    }
    System.out.println(result);
  }
 }

}

							
Posted in poj | Leave a comment

书单

sight_stop2sanyan_erpailinux_kernaldragon_bookbcasm+32

Posted in books, 未分类 | Leave a comment

八佾

bayi

Posted in 默写 | Leave a comment

入门者学

heart

Posted in 默写 | Leave a comment

泰伯

taibo

Posted in 默写 | Leave a comment

学而

talk

Posted in 默写 | Leave a comment

为政

weizheng

Posted in 默写 | Leave a comment

乡党

xiangdang

Posted in 默写 | Leave a comment

先进

xianjin_01
xianjin

Posted in 默写 | Leave a comment

宪问

xianwen

Posted in 默写 | Leave a comment

大师兄

yanyuan

Posted in 默写 | Leave a comment

公冶长

yecangself

Posted in 默写 | Leave a comment