学而

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

雍也

yongye

Posted in 默写 | Leave a comment

子罕

zihan

Posted in 默写 | Leave a comment

季路

zilun

Posted in 默写 | Leave a comment

ORM设计

首希望本文的读者拥有一定的ORM框架设计经验,或者熟悉ORM原理,最好是自己动手实现过ORM映射
如果没有请参考Doctrine或者Zend DB实现
在传统的ORM框架中都会有这样一个需求:"将一个一维数组或二维数组插入或替换到数据库中"
关于一维数组的处理这里不讨论,这里只关心二维数组
如下一个二维数组(这里使用php编码比较通俗易懂),假设某张表有三个字段 a,b,c
$arr=array(
array(
'a'=>1,
'b'=>2,
),
array(
'a'=>3,
'b'=>4,
)
);
这种数组每一维键和键顺序完全相同 只要取出第一维键值作为 INSERT INTO `table_name`(#####) 括号里的键值 然后把所有维的值拼起来作为
VALUES部分就解决了,问题是不是所有程序员都会遵循使用规则,有可能传给你一个这样的数组
$arr=array(
array(
'a'=>1,
'b'=>2,
),
array(
'a'=>3,
'b'=>4,
'c'=>5,
)
);
这样就会导致那个SQL初学者常见的columns does not match values错误,这时候我们应该使用一个函数判断一个函数是否是完全符合二维数组标准,类似如下
function is_standard_2darray($array)
{
$current=current($array);
//第一维必须为数组
if(is_array($current))
{
//这里使用crc32作为唯一校验,当然也可以不用
$crc=crc32(join('', array_keys($current)));
foreach ($array as $k=>$v)
{
$lcrc=crc32(join('', array_keys($v)));
if($lcrc!=$crc)
{
return FALSE;
}
}
}else{
return FALSE;
}
return TRUE;
}
这样可以检测到数组是否是标准二维数组,如果是那直接用第一种方法处理,如果不是那就需要将数组进行按键值分类,使用类似如下函数
function classify($array) {
$ret = array ();
$current = current ( $array );
if (is_array ( $current )) {
foreach ( $array as $k=>$v )
{
$lcrc = crc32 ( join ( '', array_keys ( $v ) ) );
//按数组键值CRC进行分类可以保证顺序也是对的
!isset($ret[$lcrc])&&$ret[$lcrc]=array();
$ret[$lcrc][]=$v;
}
}
return $ret;
}
这样将一个二维数组变成一个三维数组,其中每个第二维都是一个整理好的可以一次性插入而数据库不会报错的数据
然后遍历该数组将每一维作为参数再调用一下自身
完美解决PS
BTW
原本的框架设计原则是 "在易用性和可扩展性之间寻找一个平衡",关于这点我很佩服BOOST那伙人.
因为我们一开始并不知道一个系统最终是什么样子的,所以我们没办法对系统做更高程度的抽象(其实就是重构啦)
如此做的结果是虽然框架很智能,但这在耗费性能的同时还把风险留给了程序员,本来应该遵守数据一致性的原则会变的不那么严谨
姑且也算找到一个平衡点吧

Posted in 默写 | Leave a comment

vps 升级 数据库丢了

没了就没了吧 没有备份………………

Posted in 未分类 | Leave a comment

Poj Solution 3639

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

//* @author: 
import java.util.*;
public   class Main{    
   
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
      
    int i,n;
    double rate,us,ca,tus,tca,t1,t2;
    while (sc.hasNext()) {
        n=sc.nextInt();
        if(n==0) break;
        ca=1000;us=0;
        for (i=1;i<=n;i++) {
            rate=sc.nextDouble();
            t1=ca/rate*.97;
            t1=(Math.floor(t1*100))/100;
            t2=us*rate*.97;
            t2=(Math.floor(t2*100))/100;
            tus=(us>t1?us:t1);
            tca=(ca>t2?ca:t2);
            us=tus;ca=tca;
        }
        System.out.printf("%.2fn",ca);
    }
  }
    
}

 


							
Posted in poj | Leave a comment

Poj Solution 3637

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

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

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n=scanner.nextInt();
        int t,total;
        int[] prs;
        for (int i=0;i< n ;i++ ){
            t=scanner.nextInt();
            prs=new int[t];
            for (int j=0;j< t ;j++ ){
                prs[j]=scanner.nextInt();
            }
            Arrays.sort(prs);
            total=0;
            for (int j=t-1;j>=0 ;j-- ){
                if ((t-j)%3==0){
                    total=total+prs[j];
                }
            }
            System.out.println(total);
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3633

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

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

 /*������. ״̬����, ���ü��仯����, ����ת�ƺķѾ޴�, ���������֦. 
  *����Ҫ��һ���֦����ÿһλƥ��ʱ��Ҫȡ��ij��Ƚ�����һ������. 
  */

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

public class Main {

    private static final int        MAX_N = 18;

    private static BufferedReader   in =
        new BufferedReader(new InputStreamReader(System.in));
    private static char[]           s, t, sr;
    private static int[]            matchs, matchsr;
    private static int[]            hash = new int[1 <<  MAX_N];

    public static void main(String[] argv) throws Exception {
        for(int caseSize = Integer.parseInt(in.readLine()); caseSize > 0; caseSize--){
            if (!readIn()) {
                System.out.println("impossible");
            } else {
                System.out.println(solve(0));
            }
        }
    }

    private static boolean readIn() throws Exception {
        String  S = in.readLine(), T = in.readLine();
        int     i;
        if ((!S.contains("A") && T.contains("A")) || (!S.contains("C") && T.contains("C")) ||
                (!S.contains("G") && T.contains("G")) || (!S.contains("T") && T.contains("T"))) {
            return false;
        }
        s = S.toCharArray();
        t = T.toCharArray();
        sr = new char[s.length];
        matchs = new int[t.length];
        matchsr = new int[t.length];
        Arrays.fill(hash, Integer.MAX_VALUE);
        hash[(1 <<  t.length) - 1] = 0;
        reverse(s, sr);
        for (i = 0; i <  t.length; i++) {
            matchs[i] = longestMatch(i, t.length, s);
            matchsr[i] = longestMatch(i, t.length, sr);
        }
        return true;
    }

    private static void reverse(char[] a, char[] ar) {
        for (int i = 0; i < a.length; i++) {
            ar[i] = a[a.length - i - 1];
        }
    }

    private static int longestMatch(int from, int to, char[] a) {
        int i, len, max = 0;
        for (i = 0, len = 0; i < a.length; i++, len = 0) {
            while (len < to - from && i + len < a.length && a[i + len] == t[from + len]) {
                len++;
            }
            max = Math.max(max, len);
        }
        return max;
    }

    private static int solve(int state) {
        if (hash[state] != Integer.MAX_VALUE) {
            return hash[state];
        }
        char[] done = new char[t.length];
        char[] doner = new char[t.length];
        int i, m = 0, len, g;
        for (i = 0; i < done.length; i++) {
            done[i] = (state & (1 << i)) != 0 ? t[i] : '0';
        }
        reverse(done, doner);
        for(i = 0; i < t.length; i++) {
            if ((state & (1 << i)) != 0) {
                m = 0;
                continue;
            }
            len = 1;
            while (i + len < t.length && (state & (1 << (i + len))) == 0) {
                len++;
            }
            g = Math.min(len, Math.max(matchs[i], matchsr[i]));
            g = Math.max(g, longestMatch(i, i + len, done));
            g = Math.max(g, longestMatch(i, i + len, doner));
            if(g > m - 1) {
                hash[state] = Math.min(hash[state], 1 + solve(state | ((1 << (i + g)) - (1 << i))));
            }
            m = g;
        }
        return hash[state];
    }

}


							
Posted in poj | Leave a comment

Poj Solution 3632

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  while(a!=0)
  {
    int b=in.nextInt();
    int[] c=new int[b];
    for(int i=0;i< b;i++)
    {
        c[i]=in.nextInt();
    }
    int d,e,g;
    for(d=e=c[0],g=0;g< b;g++)
    {
        if(d>c[g])d=c[g];
        if(e< c[g])e=c[g];
    }
    System.out.println((e-d)*2);
    a--;
    }
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3630

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

import java.util.Scanner;   
  
public class Main {   
    private static Trie trie = new Trie();   
    private static boolean isConsistent = true;   
  
    public static void main(String[] args) {   
        Scanner sc = new Scanner(System.in);   
        int t = sc.nextInt();   
        for (int i = 0; i < t; ++i) {   
            int n = sc.nextInt();   
            sc.nextLine();   
            trie = new Trie();   
            isConsistent = true;   
            for (int j = 0; j < n; ++j) {   
                String phone = sc.nextLine();   
                if (isConsistent)   
                    buildTrie(phone);   
            }   
            if (isConsistent)   
                System.out.println("YES");   
            else  
                System.out.println("NO");   
        }   
    }   
  
    static void buildTrie(String s) {   
        // char[] c = s.toCharArray();   
        int len = s.length();   
        Trie tmpTrie = trie;   
        for (int i = 0; i < len; ++i) {   
            int ch = Integer.parseInt(s.substring(i, i + 1));   
            // System.out.println(ch+"---"+(int)ch);   
            Trie tmp = tmpTrie.next[ch];   
            if (tmp == null) {   
                tmp = new Trie();   
                tmp.node = 1;   
                if (i == len - 1)   
                    tmp.isDispear = true;// 表示这是一个电话的结尾   
                tmpTrie.next[ch] = tmp;   
                tmpTrie = tmp;   
            } else {   
                if (tmp.isDispear) {   
                    isConsistent = false;   
                    break;   
                }   
  
                if (i == len - 1) {   
                    isConsistent = false;   
                    break;   
                }   
                tmpTrie = tmp;   
            }   
        }   
    }   
  
    private static class Trie {   
        int node = 0;   
        boolean isDispear = false;//是否是某个电话号码的最后一个   
        Trie[] next = new Trie[10];   
    }   
}  

//出处:<a href="http://blog.csdn.net/lazy_p/archive/2010/06/21/5683414.aspx" target="_blank">http://blog.csdn.net/lazy_p/archive/2010/06/21/5683414.aspx</a>

							
Posted in poj | Leave a comment

Poj Solution 3628

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

 import java.io.BufferedReader;
 import java.io.InputStreamReader;
 import java.util.Arrays;

 public class Main {

     static int n, b;
     static int[] h;
     static boolean[] used;
     static int min = Integer.MAX_VALUE;

     public static void main(String[] args) throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String[] s = read.readLine().split(" ");
         n = Integer.parseInt(s[0]);
         h = new int[n];
         used = new boolean[n];
         b = Integer.parseInt(s[1]);
         for (int i = 0; i < n; i++) {
             h[i] = Integer.parseInt(read.readLine());
         }
         Arrays.sort(h);
         search(0, 0);
         System.out.println(min);
     }

     public static boolean search(int sum, int deep) {
         if (sum >= b) {
             if (sum - b < min) {
                 min = sum - b;
             }
             return true;
         }
         for (int i = deep; i < n; i++) {
             if (used[i]) {
                 continue;
             }
             used[i] = true;
             if (search(sum + h[i], i + 1)) {
                 used[i] = false;
                 break;
             }
             used[i] = false;
         }
         return false;
     } 
}

							
Posted in poj | Leave a comment

Poj Solution 3627

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

//* @author 
import java.io.*; 
import java.util.*; 
import java.math.*; 
public class Main 
{ 
    static int[] bookHeight; 
    static int n; 
    static BigInteger b; 
    public static void main(String[] args) throws Exception 
    { 
        readFile(); 
    }    
    public static void readFile() throws Exception 
    { 
        BufferedReader br = new BufferedReader( 
            new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer( 
            br.readLine()," "); 
        n = Integer.valueOf(st.nextToken()); 
        b = new BigInteger(st.nextToken()); 
        int iCount = 0; 
        bookHeight = new int[n]; 
        while(iCount< n) 
        { 
            bookHeight[iCount++] = Integer.valueOf( 
                br.readLine());  
        } 
        process(); 
    } 
    public static void defbug() 
    { 
        for(int i=0; i< bookHeight.length; i++) 
            System.out.println(bookHeight[i]+" "); 
        System.out.println(); 
    } 
    public static void process() 
    { 
        Arrays.sort(bookHeight); 
        BigInteger sum = BigInteger.valueOf(0L); 
        BigInteger temp; 
        int iCount = 0; 
        for(int i=bookHeight.length-1; i>=0; i--) 
        { 
            sum = sum.add(BigInteger.valueOf( 
                    (long)(bookHeight[i]))); 
            temp = sum.max(b); 
            iCount++; 
            if(temp.equals(sum)) 
                break;   
        } 
        System.out.print(iCount); 
    } 
}
							
Posted in poj | Leave a comment

Poj Solution 3626

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

//* @author:

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

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
public class Main {

    static int[][] field = new int[1001][1001];
    static int y;
    static int n;
    static int x;

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        x = scan.nextInt();
        y = scan.nextInt();
        n = scan.nextInt();
        field[x + 500][y + 500] = 1;
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            field[a + 500][b + 500] = -1;
        }
        solve();
    }

    public static void solve() {
        System.out.println(bsf(500, 500));
    }
    public static int bsf(int r, int c) {

        LinkedList< Point> queue = new LinkedList();
        queue.add(new Point(r, c, 0));
        field[r][c] = -1;

        while (!queue.isEmpty()) {
            Point current = queue.removeFirst();
            int ai = current.a;
            int bi = current.b;

            if (ai - 1 >= 0 && field[ai - 1][bi] == 0) {
                queue.addLast(new Point(ai - 1, bi, current.step + 1));
                field[ai - 1][bi] = -1;
            } else if (field[ai - 1][bi] == 1) {
                return current.step + 1;
            }

            if (ai + 1 <= 1000 && field[ai + 1][bi] == 0) {
                queue.addLast(new Point(ai + 1, bi, current.step + 1));
                field[ai + 1][bi] = -1;
            } else if (field[ai + 1][bi] == 1) {
                return current.step + 1;
            }
            if (bi - 1 >= 0 && field[ai][bi - 1] == 0) {
                queue.addLast(new Point(ai, bi - 1, current.step + 1));
                field[ai][bi - 1] = -1;
            } else if (field[ai][bi - 1] == 1) {
                return current.step + 1;
            }

            if (bi + 1 <= 1000 && field[ai][bi + 1] == 0) {
                queue.addLast(new Point(ai, bi + 1, current.step + 1));
                field[ai][bi + 1] = -1;
            } else if (field[ai][bi + 1] == 1) {
                return current.step + 1;
            }
        }
        return 0;
    }
}

class Point {

    int a = 0;
    int b = 0;
    int step = 0;

    public Point(int a, int b, int step) {
        this.a = a;
        this.b = b;
        this.step = step;
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3625

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

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

 public class Main {

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String[] s = read.readLine().split(" ");
         int n = Integer.parseInt(s[0]);
         int m = Integer.parseInt(s[1]);
         int p1, p2;
         double[][] a = new double[n][n];
         int[][] p = new int[n][2];
         for (int i = 0; i < n; i++) {
             s = read.readLine().split(" ");
             p[i][0] = Integer.parseInt(s[0]);
             p[i][1] = Integer.parseInt(s[1]);
         }
         for (int i = 0; i < n; i++) {
             for (int j = i + 1; j < n; j++) {
                 a[i][j] = a[j][i] = Math.sqrt(Math.pow(p[i][0] - p[j][0], 2)
                         + Math.pow(p[i][1] - p[j][1], 2));
             }
         }
         for (int i = 0; i < m; i++) {
             s = read.readLine().split(" ");
             p1 = Integer.parseInt(s[0]);
             p2 = Integer.parseInt(s[1]);
             a[p1 - 1][p2 - 1] = a[p2 - 1][p1 - 1] = 0;
         }
         System.out.printf("%.2f", prim(a, n));
     }

     public static double prim(double[][] a, int count) {
         double sum = 0;
         int i, j, k;
         double[] lowcost = new double[count];
         double[] closeset = new double[count];
         boolean[] used = new boolean[count];
         for (i = 0; i < count; i++) {
             lowcost[i] = a[0][i];
             closeset[i] = 0;
             used[i] = false;
         }
         used[0] = true;
         for (i = 1; i < count; i++) {
             j = 0;
             while (used[j]) {
                 j++;
             }
             for (k = 0; k < count; k++) {
                 if ((!used[k]) && (lowcost[k] < lowcost[j])) {
                     j = k;
                 }
             }
             sum += lowcost[j];
             used[j] = true;
             for (k = 0; k < count; k++) {
                 if (!used[k] && (a[j][k] < lowcost[k])) {
                     {
                         lowcost[k] = a[j][k];
                         closeset[k] = j;
                     }
                 }
             }
         }
         return sum;
     } 
}

							
Posted in poj | Leave a comment

Poj Solution 3624

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] p,q,d;
 static int a,b;
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss=in.readLine().split(" ");
    a=Integer.parseInt(ss[0]);
    b=Integer.parseInt(ss[1]);
    p=new int[a+1];
    q=new int[a+1];
    for(int i=1;i<=a;i++)
    {
         ss=in.readLine().split(" ");
      p[i]=Integer.parseInt(ss[0]);
      q[i]=Integer.parseInt(ss[1]);
    }
    d=new int[b+1];
    for(int i=1;i<=a;i++)
        for(int j=b;j>=p[i];j--)
            d[j]=Math.max(d[j-p[i]]+q[i], d[j]);
    System.out.println(d[b]);
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3619

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



import java.util.*;
import java.io.*;
/*
 * n ����;
 * s[i] ÿ���ӿ���ɵĹ���
 * t[i] һ����l��������ֵ�ʱ��
 * r[i] һ��l�������Ҫ��Ϣ��ʱ�� 
*/
public class Main{
    
    public static void main(String rgs[]) throws Exception
    {
        BufferedReader stdin = 
            new BufferedReader(
                new InputStreamReader(System.in));
           String line = stdin.readLine();
           StringTokenizer st = new StringTokenizer(line);
           int k,s,t,r,i,j,n,m,l,p;   
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken()); 
        for(i=0;i< k;i++){
            m=l=p=0;
            line = stdin.readLine();
               st = new StringTokenizer(line);
               s = Integer.parseInt(st.nextToken());
               t = Integer.parseInt(st.nextToken());
               r = Integer.parseInt(st.nextToken());
               while(l< n){
                   while(l< n && p< t){
                       l+=s;
                       m++;
                       p++;
                   }
                   if(l< n){
                       m+=r;
                       p=0;
                   }
               }
            System.out.println(m);    
        }    
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3601

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

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

public class Main{
    public static int step;
    public static int[] h;
    public static void main(String[] args){
     Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n,m;
        while (scanner.hasNext()){
            n=scanner.nextInt();
            m=scanner.nextInt();
            step=0;
            h=new int[n];
            for (int i=0;i< n ;i++ ){
                h[i]=scanner.nextInt();
            }
            step=getStep(h.length-1,m);
            System.out.println(step%m);
        }
    }

    public static int getStep(int moved,int m){
        if (moved==0){
            return 2*h[moved]-1;
        }
        int total=h[0];
        for (int i=1;i< moved ;i++ ){
            total=(total*2+h[i])%m;
        }
        if (h[moved]==1){
            return total*2+1;
        }
        else{
            return 2*total+2*h[moved]+getStep(moved-1,m);
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3589

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

//* @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);
    int n = Integer.parseInt(in.nextLine());
    for(int j = 0; j< n; j++)
    {
        String first = in.next();
        String second = in.next();
        int res1 = 0;
        int res2 = 0;
        int[] done = new int[4];
        for(int i = 0; i< 4; i++)
        {
            if(first.charAt(i)==second.charAt(i))
            {    
                res1++;
                done[i]=1;
            }        
        }
        for(int i = 0; i< 4; i++)
        {
                for(int k = 0; k< 4; k++)
           {
            if(first.charAt(i)==second.charAt(k))
            {
                if(done[i]==0)
                    res2++;
            }
        }
    }
    System.out.println(res1+"A"+res2+"B");
  }
 }
}

							
Posted in poj | Leave a comment

Poj Solution 3536

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(in.hasNext())
  {
   int a=in.nextInt();
   int x=1,y=1,z=a,m=1,n=1,q=a;
   for(int i=(int)Math.pow(a,1.0/3)+1;i>0;i--)
   {
    if(a%i==0)
    {
         x=i;
      for(int j=(int)Math.sqrt(a/x)+1;j>0;j--)
      {
       if((a/x)%j==0)
       {
        y=j;
        z=a/x/j;
        if(x*y+y*z+z*x< m*n+n*q+q*m)
        {
        m=x;
        n=y;
        q=z;
        }
        break;
       }
      }
     }
     }
     System.out.println(m+" "+n+" "+q);
   }
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3522

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

//* @author: 
import java.io.*;
import java.util.*;
/*�����������Ȩֵ����СȨֵ����С��:
 *��˼��:�ȶԱ�����. ���������ڵ�һ����������,��¼���Ȩֵ����СȨֵ����С��,ö���������
 *��α�֤�������������Ž���,��Ϊ���Ѿ���Ȩֵ��������,���ڵ�һ�����ɵ����Ȼ����С��(�Ͻ���½�֮����С)
 */
class cin
{
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static int a,c;
static int nextInt() throws IOException
{
   c=in.read();
   a=0;
   while(c==' '||c=='r'||c=='n')c=in.read();
   while(c!=' '&&c!='r'&&c!='n')
   {
    a=a*10+c-'0';
    c=in.read();
   }
   return a;
}
}

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+1];
   this.clear();
}

void clear()
{
   int i;
   num=father.length-1;
   for(i=1;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 dis=100000,h,k=0;
   Arrays.sort(e,new Cmp());
   for(i=0;i< numOfE;i++)    //��Ҫ���ִ���
   {
    if(points.union(e[i].from,e[i].to))
    {
     if(points.num==1)   //���һ����
     {
      k++;
      while(true)
      {
       points.clear();
       for(h=k;h<=i;h++)
       {
        points.union(e[h].from, e[h].to);
       }
       if(points.num==1)k++; //ȥ���Ҫ�ı�
       else break;
      }
      if(dis>e[i].weight-e[k-1].weight) //���㲢������С��ֵ
       dis=e[i].weight-e[k-1].weight;
     }
    }
   }
   if(dis==100000)dis=-1;
   return dis; 
}

}

public class Main {
    public static void main(String args[]) throws IOException
    {
    int n,m,i;
    E e[];
    while(true)
    {
       n=cin.nextInt();
       m=cin.nextInt();
       if(n==0&&m==0)break;
       e=new E[m];
       for(i=0;i< m;i++)
       {
        e[i]=new E();
        e[i].init(cin.nextInt(), cin.nextInt(), cin.nextInt());
       }
       Kruskal data=new Kruskal(e,m,n);
       System.out.println(data.cost());
    }
    }
 }
							
Posted in poj | Leave a comment

Poj Solution 3518

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

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

public class Main{
    
    public static void main(String rgs[]) throws Exception
    {
        boolean[] prime=new boolean[1299710];
        Arrays.fill(prime,true);
        prime[1] = false;
        prime[0] = false;
        for(int i=2; i<=10000; ++i){
            if(prime[i])
                for (int j=i; i*j< 1299710; ++j)
                    prime[i*j] = false;
        }
        int n, left, right;
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        n = cin.nextInt();
        while(n!=0){
            if(prime[n])
                System.out.println(0);
            else{
                right = left = n;
                while(!prime[--left]);
                while(!prime[++right]);
                System.out.println(right - left);                
            }
            n = cin.nextInt();
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3517

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

//* @author: 82638882@163.com
import java.io.*;
class Main
{
 static int n,k,m;
 public static void main(String[] args) throws IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    while(true)
    {
        String[] ss=in.readLine().split(" ");
     n=Integer.parseInt(ss[0]);
     k=Integer.parseInt(ss[1]);
     m=Integer.parseInt(ss[2]);
     if(n==0) break;
     System.out.println((f(n-1)+m)%n+1);
    }
   }

 static int f(int num)
 {
    if(num==1) return 0;
    else return (k+f(num-1))%num;
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3516

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Queue{
    int pre;
    int cnt_posi;
    int cnt_num;
    int cnt_sum;
    void set(int pre_t,int cnt_num_t,int cnt_sum_t,int cnt_posi_t){
        this.pre = pre_t;
        this.cnt_num = cnt_num_t;
        this.cnt_sum = cnt_sum_t;
        this.cnt_posi = cnt_posi_t;
    }
}
class node{
    int who;
    int value;
}
public class Main {
    static final int N = 4000000+10,P=256;
    
    static int n,p;
    static Queue myque[] = new Queue[N];

    static HashMap map[] = new HashMap[P];
    static int ans[] = new int[P],num[][] = new int[P][6];
    
    static void start_que(){
        int i,j;
        for(i=0;i< N;++i)
            myque[i] = new Queue();
        for(i=0;i< P;++i)
            map[i] = new HashMap();
    }
    
public static void main(String []args) throws Exception{
        
  int i,j,cs=1;
  String str = new String();
  Scanner cin = new Scanner(System.in);
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  start_que();
  while(cin.hasNext()){
    str = cin.next();
    if(str.equalsIgnoreCase("0=0"))
        break;
    for(i=0;i< str.length();++i){
        if(str.charAt(i)=='=')
            break;
    }
    n = i;
    p = Integer.valueOf(str.substring(i+1, str.length()));

    System.out.print(cs+". ");
    ++cs;
    solve(str,cs);
   }
 }

 public static void init_num(String str){
  int i,j;
  for(i=0;i< n;++i){
    num[i][0] = 0;
    for(j=1;j< 6 && i+j<=n;++j){
        num[i][j] = num[i][j-1]*10+str.charAt(i+j-1)-'0';
        //System.out.println(num[i][j]);
    }
   }
   for(i=0;i<=n;++i)
    map[i].clear();
  
   }


  static void get_ans(int cnt){
    String str="";
    int i,j,top=0;
    while(cnt>0){
        ans[top++] = myque[cnt].cnt_num;
        cnt = myque[cnt].pre;
    }
    str += String.valueOf(ans[top-1]);
    for(i=top-2;i>=0;--i){
        str+="+";
        str+=String.valueOf(ans[i]);
    }
    str+="="+String.valueOf(p);
    System.out.println(str);
  }

  public static void solve(String str,int cs){
   init_num(str);

   int i,j,k,left=0,right=0;
        
   myque[right].set(-1, 0, 0, 0);
   ++right;
        
   while(left< right){
    //System.out.println(left+" "+right);
    for(i=1;i< 6 && num[myque[left].cnt_posi][1]>0 && myque[left].cnt_posi+i<=n;++i){
    if(num[myque[left].cnt_posi][i]+myque[left].cnt_sum<=p){
                    
      myque[right].set(left, num[myque[left].cnt_posi][i], 
           num[myque[left].cnt_posi][i]+myque[left].cnt_sum, myque[left].cnt_posi+i);
      if(myque[right].cnt_posi==n && myque[right].cnt_sum==p){
        get_ans(right);
        return ;
        }
        if(!has_in_hash(myque[right].cnt_posi,myque[right].cnt_sum,cs))continue;
            ++right;
        }
        
    }
    ++left;
    }
    System.out.println("IMPOSSIBLE");
  }

  public static boolean has_in_hash(int posi,int sum,int cs){

        if(map[posi].containsKey(sum))
            return false;
        map[posi].put(sum, 1);
        return true;
    }
    
}

							
Posted in poj | Leave a comment

Poj Solution 3512

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

//* @author: 82638882@163.com
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss;
  String s;
  int count=0;
  while(true)
  {
    count++;
    node[] arr=new node[1001];
    node[] pp=new node[1001];
    int i=0,j,zNum,maxNum,x,y,p,max=-1, a=0;
    while(true)
    {
         s=in.readLine();
      if(s.charAt(0)=='-'&&s.charAt(1)=='-') break;
      ss=s.split(" ");
      x=Integer.parseInt(ss[0]);
      y=Integer.parseInt(ss[1]);
      arr[a]=new node(x,y);
      pp[a]=new node(); 
      a++;
     }
     if(a==0) break;
     for(i=0;i< a-1;i++)
     {
       int k=0;
       zNum=maxNum=-1;
       for(j=i+1;j< a;j++)
       {
        x=arr[i].x-arr[j].x;
        y=arr[i].y-arr[j].y;
        if(y==0) zNum++;
        else if(x==0) maxNum++;
        else
        {
             p=gcd(Math.abs(x),Math.abs(y));
          pp[k].x=x/p;
          pp[k].y=y/p;
          if(pp[k].x< 0)
          {
           pp[k].x*=-1;
           pp[k].y*=-1;
          }
          k++;
        }
         }
         max=Math.max(max,Math.max(zNum, maxNum));
         int cnt=0;
         Arrays.sort(pp, 0, k);
         for(j=0;j< k-1;j++)
         {
        if(pp[j].x==pp[j+1].x&&pp[j].y==pp[j+1].y) cnt++;
        else{
            if(cnt>max) max=cnt;
            cnt=0;
        }
         }
         max=Math.max(max, cnt);
      }
     System.out.println(count+". "+(max+2));
     }
  }

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

class node implements Comparable< node>{
    public int x,y;
    public node(){}
    public node(int a,int b)
    {
        x=a;
        y=b;
    }
    public int compareTo(node o) {
        if(x==o.x) return y-o.y;
        return x-o.x;
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3511

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
     public static void main(String args[]) throws IOException{
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        int[] prims=new int[1000001];
        int[] ferms=new int[1000001];
        for(int i=3;i< 1000000;i+=2) 
          prims[i]=1;
        prims[2]=1;
        int index=1;
        while((index+=2)< 1000000) 
           if(prims[index]==1)
             for(int i=2*index;i< 1000000;i+=index) prims[i]=0;
        ferms[2]=1;
        for(int i=3;i< 1000000;i+=2){
            if(prims[i]==1&&i%4==1) ferms[i]=1;
            prims[i]+=prims[i-1];
            prims[i+1]=prims[i];
            ferms[i]+=ferms[i-1];
            ferms[i+1]=ferms[i];
         }
        int limi=0,lims=0,in,su;
        while(true){
            tokens=new StringTokenizer(stdin.readLine());
            limi=Integer.parseInt(tokens.nextToken());
            lims=Integer.parseInt(tokens.nextToken());
            if(limi==-1&&lims==-1) break;
            in=limi;
            su=lims;
            if(limi<=0) limi=1;
            if(lims<=0) lims=1;
            System.out.println(in+" "+su+" "+(prims[lims]-prims[limi-1])+" "+(ferms[lims]-ferms[limi-1]));
        }
      }
}
							
Posted in poj | Leave a comment

Poj Solution 3510

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

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   String s=in.nextLine();
   StringBuffer sb=new StringBuffer("");
   int l=s.length();
   boolean bb=false;
   for(int i=0;i< l;i++)
   {
    char c=s.charAt(i);
    if(i< l-1&&c=='d'&&s.charAt(i+1)=='d'){
        sb.append('p');
        i++;
    }
    else if(i< l-1&&c=='e'&&s.charAt(i+1)=='i'&&(i==0||s.charAt(i-1)!='c')){
        sb.append("ie");
        i++;
    }            
    else if(i< l-3&&c=='p'&&s.charAt(i+1)=='i'&&s.charAt(i+2)=='n'&&s.charAt(i+3)=='k'){
        sb.append("floyd");
        i+=3;
    }    
    else if(i< l-2&&c=='E'&&s.charAt(i+1)=='O'&&s.charAt(i+2)=='F'){
        bb=true;
        break;
    }
    else if(c>='a'&&c<='z'||c==' ') sb.append(c);
    }
    System.out.println(sb);
    if(bb) break;
   }
 }
}
							
Posted in poj | Leave a comment

Poj Solution 3508

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

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

 

public class Main {

 

    public static void main(String[] args) throws IOException {

       BufferedReader read = new BufferedReader(new InputStreamReader(

              System.in));

       int num = 1;

       int flg, tt, last;

       while (true) {

           char[] c = read.readLine().toCharArray();

           if (c.length == 1 && c[0] == '0') {

              break;

           }

           last = c[c.length - 1];

           flg = 0;

           for (int j = c.length - 2; j >= 0; j--) {

              tt = c[j] - last;

              if (flg + tt < 0) {

                  c[j] = (char) ('0' + flg + tt + 10);

                  flg = -1;

              } else {

                  c[j] = (char) ('0' + flg + tt);

                  flg = 0;

              }

              last = c[j];

           }

           if (c[0] != '0') {

              System.out.println(num + ". " + String.valueOf(c));

           } else {

              System.out.println(num + ". IMPOSSIBLE");

           }

           num++;

       }

    }

}

							
Posted in poj | Leave a comment

Poj Solution 3507

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

import java.util.Scanner;


public class Main {
 public static void main(String[] args)
 {
    Scanner in = new Scanner(System.in);
    float[] input = new float[6];
    while(true)
    {
        input[0] = in.nextFloat();
        float max = input[0];
        float min = input[0];
        float sum = input[0];
        for(int i = 1; i < 6; i++)
        {
            input[i] = in.nextFloat();
            if(max < input[i])
                max = input[i];
            if(min > input[i])
                min = input[i];
            sum = sum + input[i];
        }
        if(sum == 0.0)
            break;
        else
        {
            sum -= min;
            sum -= max;
        }
        float result = sum/4;
        int res = (int)sum/4;
        if(res*4 == sum)
            System.out.println(res);
        else
            System.out.println(result);    
    }
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3505

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

//* @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 nn,n,m,ans;
     nn=sc.nextInt();
     while((nn--)!=0) {
      n=sc.nextInt();
      m=sc.nextInt();
      int a[][]=new int[n+1][m+1];
       ans=0;
    for (int i=1;i<=n;i++) {
      for (int j=1;j<=m;j++) 
           a[i][j]=sc.nextInt();
        int tp=0,now=1,t1,t2;
        for (int j=1;j<=m;j++) if (a[i][j]!=-1) tp++;
         while ((tp--)!=0) {
          int pos=1,tmp=1000000;
         for (int j=1;j<=m;j++) if (a[i][j]!=-1&&a[i][j]< tmp) {pos=j;tmp=a[i][j];}
          ans+=(i-1)*20;
        t1=now-pos;
        t2=pos-now;
        if (t1< 1) t1+=m;
        if (t2< 1) t2+=m;
        if (t1>t2) t1=t2;
        ans+=t1*5;now=pos;
        a[i][pos]=-1;
    }
     }
     System.out.printf("%dn",ans);
    }
  }
}
							
Posted in poj | Leave a comment

Poj Solution 3504

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

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

public class Main {
 public static Scanner in=new Scanner(System.in).useLocale(Locale.US);


 public void run() {
  boolean[] singles=new boolean[26];
  Map< String,String>[][] words=new Map[26][26];
  for(int i=0;i< 26;++i) for(int j=0;j< 26;++j) words[i][j]=new HashMap< String,String>();
  Set< String>[][] doublewords=new Set[26][26];
  for(int i=0;i< 26;++i) 
    for(int j=0;j< 26;++j)
      doublewords[i][j]=new HashSet< String>();
  String s=in.next();
  int n=in.nextInt();
  for(int i=0;i< n;++i) {
    String word=in.next();
    if(word.length()==1) {
         singles[word.charAt(0)-'a']=true;
    } else {
      int a=word.charAt(0)-'a',b=word.charAt(word.length()-1)-'a';
      char[] letters=word.substring(1,1+word.length()-2).toCharArray();
      Arrays.sort(letters);
      if(words[a][b].containsKey(new String(letters))) 
       doublewords[a][b].add(new String(letters));
      else words[a][b].put(new String(letters),word);
    }
    }
   String[] prev=new String[s.length()+1];
   int[] ways=new int[s.length()+1]; ways[0]=1;
   for(int i=0;i< s.length();++i) if(ways[i]>0) {
    if(singles[s.charAt(i)-'a']) { 
        ways[i+1]=Math.min(2,ways[i+1]+ways[i]);
        prev[i+1]=""+s.charAt(i);
      }
    for(int len=2;i+len<=s.length() && len<=100;++len) {
      int a=s.charAt(i)-'a',b=s.charAt(i+len-1)-'a';
      char[] letters=s.substring(i+1,i+1+len-2).toCharArray();
      Arrays.sort(letters);
      String word=new String(letters);
      if(doublewords[a][b].contains(word)) 
           ways[i+len]=Math.min(2,ways[i+len]+2*ways[i]);
      else if(words[a][b].containsKey(word)) { 
           ways[i+len]=Math.min(2,ways[i+len]+ways[i]); 
           prev[i+len]=words[a][b].get(word); 
         }
    }
     }
     if(ways[s.length()]==0) System.out.println("impossible");
     else if(ways[s.length()]==2) System.out.println("ambiguous");
     else {
    List< String> ret=new ArrayList< String>();
    for(int i=s.length();i!=0;i-=prev[i].length()) ret.add(prev[i]);
    Collections.reverse(ret);
    for(int i=0;i< ret.size();++i) {
      if(i!=0) System.out.print(" ");
        System.out.print(ret.get(i));
    }
    System.out.println();
   }
    
 }
    
 public static void main(String[] args) {
   int n=in.nextInt(); 
   for(int i=0;i< n;++i)
    new Main().run();
 }
}

							
Posted in poj | Leave a comment

Poj Solution 3488

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            int n;
            try {
                n=in.nextInt();
            }
            catch(Exception e) {return;}
            String []s=new String [n];
            for (int i=0;i< n;i++) s[i]=in.next();
            int m=s[0].length();
            String tp=new String();
            for (int i=m-1;i>=0;i--) for (int j=n-1;j>=0;j--)
                tp=tp.concat(String.valueOf(s[j].charAt(i)));
            int lastone=0;
            for (int i=tp.length()-1;i>=0;i--)
                if (tp.charAt(i)!='_') {lastone=i;break;}
            for (int i=0;i< tp.length();i++) {
                if (tp.charAt(i)=='_') System.out.print(' ');
                else if (tp.charAt(i)=='\') System.out.println();
                else System.out.print(tp.charAt(i));
                if (i==lastone) break;
            }
            System.out.println();
            System.out.println();
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3486

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

/* @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 n,c;
    int m[][]=new int[1003][1003];
    int f[]=new int[1003];
    while(sc.hasNext()){
          c=sc.nextInt();
          n=sc.nextInt();
          for(int i=0;i< m.length;i++)
             Arrays.fill( m[i],0);
          for(int i=1;i<=n;i++){
               for(int j=i;j<=n;j++)
                 m[i][j]=sc.nextInt();
                    
          }
          for(int i=1;i<=n;i++){
               f[i]=c+m[1][i];        
          }
          for(int i=2;i<=n;i++){
               for(int j=i;j<=n;j++){
                    if(f[j]>f[i-1]+c+m[i][j])
                         f[j]=f[i-1]+c+m[i][j];        
               }        
          }
          System.out.printf("%dn",f[n]);                  
    }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3485

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
class SEG implements Comparable<SEG>
{
    double b,e;
    SEG(double x,double y) {
        b=x;e=y;
    }
    public int compareTo(SEG other) {
        if (b< other.b) return -1;
        else if (b==other.b) {
            if (e< other.e) return -1;
            else if (e==other.e) return 0;
        }
        return 1;
    }
}
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            double l,d;
            int n;
            try {
                l=in.nextDouble();
            }
            catch (Exception e) {return;}
            d=in.nextDouble();
            n=in.nextInt();
            int ans=1;
            double d2=d*d,r,x,y;
            SEG []s=new SEG[n];
            for (int i=0;i< n;i++) {
                x=in.nextDouble();
                y=in.nextDouble();
                r=Math.sqrt(d2 - y*y);
                s[i]=new SEG(x-r,x+r);
            }
            Arrays.sort(s);
            double cr=s[0].e;
            for(int i=1;i< n;i++) {
                if (s[i].b>cr) {
                    cr=s[i].e;
                    ans++;
                }
                else if (cr>s[i].e) cr=s[i].e;
            }
            System.out.println(ans);
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3484

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

//* @author: 
import java.util.*;
import java.math.*;
import java.io.FileReader;
class node{
    int x,y,z;
    node(String s) {
        int t=0,cnt=0;
        for (int i=0;i<=s.length();i++) {
            if (i!=s.length()&&s.charAt(i)>='0'&&s.charAt(i)<='9') {
                t=t*10+s.charAt(i)-'0';
            }
            else {
                if (cnt==0) x=t;
                else if (cnt==1) y=t;
                else if (cnt==2) z=t;
                cnt++;
                t=0;
            }
        }
    }
}
public class Main {
    static void doit(Vector a) {
        int n=a.size();
        node tt=null;
        long beg=2147483647,end=0,ans=0;
        long total=0;
        for (int i=0;i< n;i++) {
            tt=(node)a.get(i);
            total+=(tt.y-tt.x)/tt.z+1;
            if (beg>tt.x) beg=tt.x;
            if (end< tt.y) end=tt.y;
        }
        if (total%2==0) {
            System.out.println("no corruption");
            return;
        }
        while (beg<=end) {
            long mid=(beg+end)/2;
            total=0;
            for (int i=0;i< n;i++) {
                tt=(node)a.get(i);
                long left,right,x=tt.x,y=tt.y,z=tt.z;
                if (x>beg) left=x;
                else {
                    if (beg%z==x%z) left=beg;
                    else if (beg%z>x%z) left=beg-beg%z+x%z+z;
                    else left=beg-beg%z+x%z;
                }
                if (y< mid) right=y;
                else right=mid;
                if (right>=left) total+=(right-left)/z+1;
            }
            if (total%2==1) {
                end=mid;
                if (beg==end) {
                    ans=beg;
                    break;
                }
            }
            else {
                beg=mid+1;
            }
        }
        System.out.print(ans);
        int ans2=0;
        for (int i=0;i< n;i++) {
            tt=(node)a.get(i);
            if (ans>=tt.x&&ans<=tt.y&&ans%tt.z==tt.x%tt.z) ans2++;
        }
        System.out.print(' ');
        System.out.println(ans2);
    }
    public static void main(String[] args) throws Exception{
        Scanner in=new Scanner(System.in);
        while (true) {
            Vector a=new Vector(0);
            while (true) {
                String s;
                try {s=in.nextLine();}
                catch (Exception e) {
                    if (a.size()!=0) doit(a);
                    return;
                }
                if (s.length()==0) {
                    if (a.size()!=0) {
                        doit(a);
                        break;
                    }
                }
                else a.add(new node(s));
            }
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3483

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

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


public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        new Main().run();
    }
    
    int[] f;
    int[] dp;
    
    int Root(int x) {
        if(f[x] == x) 
            return x;
        return f[x] = Root(f[x]);
    }
    
    private class Node implements Comparable {
        int p, d;

        public Node() {
            super();
        }

        public Node(int p, int d) {
            super();
            this.p = p;
            this.d = d;
        }

        public int compareTo(Object arg0) {
            return -(p-((Node)arg0).p);
        }
    }

    private void run() throws FileNotFoundException {
         Scanner cin = new Scanner(System.in);
 
        while(cin.hasNextInt()) {
            int n = cin.nextInt();
            int l = cin.nextInt();
 
            Node p[] = new Node[n];
            int max = 0;
            for(int i = 0; i < n; ++i) {
                p[i] = new Node(cin.nextInt(), cin.nextInt());
                p[i].d++;
                p[i].d *= l;
                max = Math.max(max, p[i].d);
            }
            max++;
            Arrays.sort(p);

            f = new int[max];
            for(int i = 0; i < max; ++i) f[i] = i;
            
            int sum = 0;
            for(int i = 0; i < n; ++i) {
                int x = p[i].d;
 
                int r = Root(x);
                if(r != 0) {
                    f[r] = r-1;
                    sum += p[i].p;
 
                }
            }
            System.out.println(sum);
            
        }
        
    }

}

							
Posted in poj | Leave a comment

Poj Solution 3482

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

//* @author: 
import java.util.*;
import java.io.FileReader;
import java.math.*;
public class Main {
    public static void main(String[] args)  throws Exception{
        int n=0;
        int [] dx=new int[1000];
        Scanner in=new Scanner(System.in);
        int fir=1;
        while (true) {
            String s;
            try {
                while (true) {
                    s=in.nextLine();
                    if (s.length()!=0) break;
                }
            }
            catch(Exception e) {
                break;
            }
            if (fir==1) fir=0;
            else System.out.println();
            int ll=s.length();
            n=0;
            for (int i=0;i< ll;i++) if (s.charAt(i)>0x20) {
                dx[s.charAt(i)]=n++;
            }
            while (true) {
                try{
                    s=in.nextLine();
                }
                catch(Exception e2) {
                    return;
                }
                int l=s.length();
                if (l==0) break;
                int max=0;
                for (int i=0;i< l;i++) 
                 if (s.charAt(i)>0x20&&max< dx[s.charAt(i)]) max=dx[s.charAt(i)];
                BigInteger ans=BigInteger.ZERO;
                for (int dig=max+1;dig<=n;dig++) {
                    BigInteger tmp=BigInteger.ZERO;
                    for (int i=0;i< l;i++) if (s.charAt(i)>0x20) {
                        tmp=tmp.multiply(BigInteger.valueOf(dig));
                        tmp=tmp.add(BigInteger.valueOf(dx[s.charAt(i)]));
                    }
                    ans=ans.add(tmp);
                }
                System.out.println(ans);
            }
        }
    }
}


							
Posted in poj | Leave a comment

Poj Solution 3481

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

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

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        BinaryMinimumHeap minHeap = new BinaryMinimumHeap();
        BinaryMaximumHeap maxHeap = new BinaryMaximumHeap();
        
        while(true)
        {
            int request = sc.nextInt();
            if(request == 0)
            {
                break;
            }else if(request == 1)
            {
                int k = sc.nextInt();
                int p = sc.nextInt();
                Client client = new Client(k,p);
                minHeap.offer(client);
                maxHeap.offer(client);
            }else if(request == 2)
            {
                if(maxHeap.size() == 0)
                {
                    System.out.println(0);
                }else
                {
                    Client client = maxHeap.poll();
                    minHeap.remove(client);
                    System.out.println(client);
                }
            }else if(request == 3)
            {
                if(minHeap.size() == 0)
                {
                    System.out.println(0);
                }else
                {
                    Client client = minHeap.poll();
                    maxHeap.remove(client);
                    System.out.println(client);
                }
            }else
            {
                throw new RuntimeException("No such type of request");
            }
        }
    }
    
}

class Client implements Comparable< Client>
{
    int id;
    int priority;
    int posInMinimumHeap;
    int posInMaximumHeap;
    
    Client(int id, int priority)
    {
        this.id = id;
        this.priority = priority;
        this.posInMaximumHeap = 0;
        this.posInMinimumHeap = 0;
    }
    
    public int compareTo(Client client)
    {
        if(this.priority < client.priority)
        {
            return - 1;
        }else if(this.priority == client.priority)
        {
            return 0;
        }else
        {
            return 1;
        }
    }
    
    public String toString()
    {
        return Integer.toString(id);
    }
}

class BinaryMinimumHeap
{
    
    public static final int capacity = 1000001;
    int count;
    Client[] clients;
    public BinaryMinimumHeap()
    {
        clients = new Client[capacity];
        count = 0;
    }
    
    public void offer(Client client)
    {
        if(count == capacity - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && clients[i/2].compareTo(client) == 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMinimumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMinimumHeap = i;
    }
    
    public Client poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        Client result = clients[1];
        result.posInMinimumHeap = 0;
        Client last = clients[count];
        count--;
        int i = 1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child+1 <= count && clients[child].compareTo(clients[child+1]) == 1)
            {
                child += 1;
            }
            if(last.compareTo(clients[child]) == -1)
            {
                break;
            }
            clients[i] = clients[child];
            clients[i].posInMinimumHeap = i;
            i = child;
        }
        clients[i] = last;
        clients[i].posInMinimumHeap = i;
        
        return result;
    }
    
    public void remove(Client client)
    {
        int i = client.posInMinimumHeap;
        while(i > 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMinimumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMinimumHeap = i;
        poll();
    }
    
    public int size()
    {
        return count;
    }
    
    public int capacity()
    {
        return capacity - 1;
    }
}

class BinaryMaximumHeap
{
    
    public static final int capacity = 1000001;
    int count;
    Client[] clients;
    public BinaryMaximumHeap()
    {
        clients = new Client[capacity];
        count = 0;
    }
    
    public void offer(Client client)
    {
        if(count == capacity - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && clients[i/2].compareTo(client) == -1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMaximumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMaximumHeap = i;
    }
    
    public Client poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        Client result = clients[1];
        result.posInMaximumHeap = 0;
        Client last = clients[count];
        count--;
        int i = 1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child+1 <= count && clients[child].compareTo(clients[child+1]) == -1)
            {
                child += 1;
            }
            if(last.compareTo(clients[child]) == 1)
            {
                break;
            }
            clients[i] = clients[child];
            clients[i].posInMaximumHeap = i;
            i = child;
        }
        clients[i] = last;
        clients[i].posInMaximumHeap = i;
        
        return result;
    }
    
    public void remove(Client client)
    {
        int i = client.posInMaximumHeap;
        while(i > 1)
        {
            clients[i] = clients[i/2];
            clients[i].posInMaximumHeap = i;
            i /= 2;
        }
        clients[i] = client;
        clients[i].posInMaximumHeap = i;
        poll();
    }
    
    public int size()
    {
        return count;
    }
    
    public int capacity()
    {
        return capacity - 1;
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3480

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

//* @author: 
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args)  throws Exception{
        int nn;
        Scanner in=new Scanner(System.in);
        nn=in.nextInt();
        while ((nn--)!=0) {
            int n=in.nextInt();
            long ans=0,max=0;
            for (int i=1;i<=n;i++) {
                long j=in.nextLong();
                if (j>max) max=j;
                ans=ans^j;
            }
            if ((ans!=0)&&(max>1)||(ans==0)&&(max<=1)) System.out.println("John");
            else System.out.println("Brother");
        }
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3476

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

//* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    BallSeq head, tail;
    BinaryHeap pq = new BinaryHeap();
    String s = sc.next();
    char previousChar = s.charAt(0);
        Ball ball = new Ball(0+1);
    BallSeq seq = new BallSeq(previousChar,0+1);
        head=seq;
        tail = seq;
    seq.firstBall = ball;
        seq.lastBall = ball;
    seq.number++;
    for(int i = 1; i < s.length(); i++)
    {
        char currentChar = s.charAt(i);
        if(currentChar==previousChar)
        {
        ball = new Ball(i+1);
                seq.lastBall.nextBall = ball;
                //ball.previousBall = seq.lastBall;
                seq.lastBall = ball;
                seq.number++;
        }else
        {
        previousChar = currentChar;
                pq.offer(seq);
        seq = new BallSeq(previousChar,i+1);
                tail.nextBallSeq = seq;
                seq.previousBallSeq = tail;
                tail = seq;
        ball = new Ball(i+1);
                seq.firstBall = ball;
                seq.lastBall = ball;
        seq.number++;
        }
    }
        pq.offer(seq);
    while(true)
    {
        int size = pq.size();
        if(size==0)
        {
            break;
        }
        seq = pq.poll();
        if(seq.number==1)
        {
            break;
        }
        System.out.print(seq.color);
            ball = seq.firstBall;
        for(int i = 0; i < seq.number; i++)
        {
            System.out.print(" "+ball.position);
                ball = ball.nextBall;
        }
        System.out.println();
        if(seq == head)
            {
                head = seq.nextBallSeq;
                if(head != null)
                {
                    head.previousBallSeq = null;
                }
            }else if(seq == tail)
            {
                tail = seq.previousBallSeq;
                if(tail !=null )
                {
                    tail.nextBallSeq = null;
                }
            }else
            {
                BallSeq p = seq.previousBallSeq;
                BallSeq n = seq.nextBallSeq;
                if(p.color == n.color)
                {
                    pq.remove(p);
                    pq.remove(n);
                    p.number += n.number;
                    p.lastBall.nextBall = n.firstBall;
                    //n.firstBall.previousBall = p.lastBall;
                    p.lastBall = n.lastBall;
                    p.nextBallSeq = n.nextBallSeq;
                    if(n != tail)
                    {
                        n.nextBallSeq.previousBallSeq = p;
                    }else
                    {
                        tail =p;
                    }
                    pq.offer(p);
                }else
                {
                    p.nextBallSeq = n;
                    n.previousBallSeq = p;
                }
            }
    }
    }   
}

class BallSeq implements Comparable< BallSeq>
{
    public char color;
    public int number;
    public int start;
    public int position;
    Ball firstBall;
    Ball lastBall;
    BallSeq previousBallSeq;
    BallSeq nextBallSeq;
    public BallSeq(char color, int start)
    {
        this.color = color;
    this.start = start;
    this.number = 0;
        position = 0;
        firstBall = null;
        lastBall = null;
        previousBallSeq = null;
        nextBallSeq = null;
    }
    public int compareTo(BallSeq bs)
    {
        if(this.number == bs.number)
    {
        if(this.start == bs.start)
        {
            return 0;
        }else if(this.start < bs.start)
        {
            return -1;
        }else
        {
            return 1;
        }
    }else if(this.number < bs.number)
    {
        return 1;
    }else
    {
        return -1;
    }
    }
}

class Ball
{
    //Ball previousBall;
    Ball nextBall;
    int position;//position in the sequence
    public Ball(int position)
    {
        this.position = position;
        //previousBall = null;
        nextBall = null;
    }
}
class BinaryHeap
{
    public static final int max = 1000000;
    int count;
    BallSeq[] segments;
    public BinaryHeap()
    {
        count = 0;
        segments = new BallSeq[max];
    }
    public void offer(BallSeq seq)
    {
        if(count == max - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && segments[i/2].compareTo(seq) == 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
    }
    public void remove(BallSeq seq)
    {
        int i = seq.position;
        while(i > 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
        poll();
    }
    public BallSeq poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        BallSeq result = segments[1];
        BallSeq last = segments[count];
        count--;
        int i =1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child + 1 <= count && segments[child].compareTo(segments[child+1]) == 1)
            {
                child += 1;
            }
            if(last.compareTo(segments[child]) == -1)
            {
                break;
            }
            segments[i] = segments[child];
            segments[i].position = i;
            i = child;
        }
        segments[i] = last;
        segments[i].position = i;
        return result;
    }
    public int size()
    {
        return count;
    }
    public int capacity()
    {
        return max;
    }
}
							
Posted in poj | Leave a comment

Poj Solution 3475

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

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

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    while(sc.hasNext())
    {
        long a = sc.nextLong();
        long b = sc.nextLong();
        double c = sc.nextDouble();
        double d = sc.nextDouble();
        int steps = 0;
        if(a > b)
        {
            long temp = a;
        a = b;
        b = temp;
        }
        while(true)
        {
            if(c > d)
        {
            double temp = c;
            c = d;
            d = temp;
        }

        if(a >= c && b >=d)
        {
            break;
        }else if(b < d)
        {
            d = d/2;
            steps++;
        }else
        {
            c = c/2;
            steps++;
        }
        }
        System.out.println(steps);
    }
    }
}

							
Posted in poj | Leave a comment

Poj Solution 3472

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

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

public class Main {

    /**
     * @param args the command line arguments
     */
    static BigInteger []a=new BigInteger[10005];
    public static void main(String[] args) {
       // TODO code application logic here
        int n;
        a[0]=BigInteger.ONE;
        a[1]=BigInteger.ONE;
        for(int i=2;i<=10000;i++) a[i]=a[i-1].add(a[i-2]);
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            n=cin.nextInt();
            BigInteger ans=a[n-1].pow(4);
            ans=ans.add(a[n].pow(2).multiply(a[n-2].pow(2)));
            ans=ans.add(BigInteger.valueOf(6).multiply(a[n].multiply(a[n-2].multiply(a[n-1].pow(2)))));
            ans=ans.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(2));
            String s=ans.toString();
            StringBuffer sbf=new StringBuffer();
            int p=0;
            for(int i=s.length()-1;i>=0;i--){
                p++;
            sbf.append(s.charAt(i));
                if(p==3&&i>0){
                    sbf.append(",");
                    p=0;
                }
            }
            sbf.reverse();
            System.out.println(sbf.toString());
        }

    }

}


							
Posted in poj | Leave a comment

Poj Solution 3468

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

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

public class Main 
{
 public static void main(String []args)
 {
  SegmentTree segmentTree=new SegmentTree();
 }
};
class SegmentTree
{
 public SegmentTree()
 {
  tot=0;
  int n,m,left,right,value;
  String str;
  Scanner input=new Scanner(System.in);
  n=input.nextInt();
  m=input.nextInt();
  for(int i=1;i<=n;i++)
   a[i]=input.nextInt();
  creatTree(1,1,n);
  for(int i=0;i< m;i++)
  {
   str=input.next();
   if(str.charAt(0)=='Q')
   {
    left=input.nextInt();
    right=input.nextInt();
    System.out.println(query(1,left,right,0));
   }
   else
   {
    left=input.nextInt();
    right=input.nextInt();
    value=input.nextInt();
    insert(1,left,right,value);
   }
  }
 }
 public long creatTree(int now,int left,int right)
 {
  if(now>tot)
   tot=now;
  _left[now]=left;
  _right[now]=right;
  long lSum=0,rSum=0;
  if(left< right)
  {
   lSum=creatTree(2*now,left,(left+right)/2);
   rSum=creatTree(2*now+1,(left+right)/2+1,right); 
   _sum[now]=lSum+rSum;
  }
  else
   _sum[now]=a[left];
  return _sum[now];
 }
 public void insert(int now,int left,int right,int value)
 {
  if(now>tot)
   return ;
  if(left<=_left[now]&&right>=_right[now])
  {
   _d[now]+=value;
   return ;
  }
  long lSum=0,rSum=0;
  if(left<=(_left[now]+_right[now])/2)
   insert(2*now,left,right,value);
  if(right>(_left[now]+_right[now])/2)
   insert(2*now+1,left,right,value);
  if(2*now<=tot)
   lSum=_sum[2*now]+_d[2*now]*(_right[2*now]-_left[2*now]+1);
  if(2*now+1<=tot)
   rSum=_sum[2*now+1]+_d[2*now+1]*(_right[2*now+1]-_left[2*now+1]+1);
  _sum[now]=lSum+rSum;
 }
 public long query(int now,int left,int right,long d)
 {
  if(now>tot)
   return 0;
  if(left<=_left[now]&&right>=_right[now])
   return _sum[now]+(_d[now]+d)*(_right[now]-_left[now]+1);
  long lSum=0,rSum=0;
  if(left<=(_left[now]+_right[now])/2)
   lSum=query(2*now,left,right,d+_d[now]);
  if(right>(_left[now]+_right[now])/2)
   rSum=query(2*now+1,left,right,d+_d[now]);
  return lSum+rSum;
 }
 public static final int N=100005;
 public int tot;
 public int[] a=new int[N];
 public int[] _left=new int [3*N];
 public int[] _right=new int [3*N];
 public long[] _sum=new long [3*N];
 public long[] _d=new long [3*N];
} 
							
Posted in poj | Leave a comment

Poj Solution 3461

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int[] next;
 static String s1,s2;
 static int l1,l2,cnt;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  while((a--)!=0)
  {
    s1=in.readLine();
    s2=in.readLine();
    l1=s1.length();
    l2=s2.length();
    cnt=0;
    next=new int[l1];
    next();
    kmp();
    System.out.println(cnt);
   }
 }

 static void kmp()
 {
  int i=0,j=0;
  while(i< l2&&j< l1)
  {
    if(j==-1||s2.charAt(i)==s1.charAt(j))
    {
    i++;
    j++;
    }
    else j=next[j];
    if(j==l1)
    {
    cnt++;
    i=i-1;
    j=next[j-1];
    }
   }
 }

  static void next() 
  {
   int i = 0;
   next[0] = -1;
   int j = -1;
   while(i < l1 - 1) 
   {
    if(j == -1 || s1.charAt(i) == s1.charAt(j))
    {
        ++i;
        ++j;
        next[i] = j;
    }
    else
        j = next[j];
    }
  }

}

							
Posted in poj | Leave a comment