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 | Comments Off on Poj Solution 3504

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 | Comments Off on Poj Solution 3488

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 | Comments Off on Poj Solution 3486

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 | Comments Off on Poj Solution 3485

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 | Comments Off on Poj Solution 3484

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 | Comments Off on Poj Solution 3483

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 | Comments Off on Poj Solution 3482

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 | Comments Off on Poj Solution 3481

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 | Comments Off on Poj Solution 3480

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 | Comments Off on Poj Solution 3476

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 | Comments Off on Poj Solution 3475

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 | Comments Off on Poj Solution 3472

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 | Comments Off on Poj Solution 3468

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 | Comments Off on Poj Solution 3461

Poj Solution 3444

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

//* @author  mekarlos@gmail.com
import java.util.Scanner;

/**
 *
 * @author usuario
 */
public class Main {

    public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);
        int n;
        int[] m,o;
        while (scan.hasNext()){
            n=scan.nextInt();
            if (n==0) {
                break;
            }
            m=new int[n];
            o=new  int[n];

            for (int i = 0; i < m.length; i++) {
                m[i]=scan.nextInt();
            }
            int k;
            for (int i = 1; 1<< i <= m.length; i++) {
                o=java.util.Arrays.copyOf(m, n);
                k=1<< i;
                for (int j = 0; j < k/2; j++) {

                    //System.out.println("2*k+1 = " + (k-1+j));
                        m[2*j]=(o[j]+o[k/2+j])/2;
                        m[2*j+1]=(o[j]-o[k/2+j])/2;
                }
                // System.out.println("");

                
            }
           for (int K = 0; K < m.length; K++) {
                    System.out.print(m[K]+" ");
           }
            System.out.println("");
        }
        System.out.println("");
    }
}
							
Posted in poj | Comments Off on Poj Solution 3444

Poj Solution 3438

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

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        int num = Integer.valueOf(cin.nextLine()).intValue();   
        String rawStr = null;   
           
           
        char repeatChar = 'n';   
        int repeat = 0;   
        char temp = 'n';   
        int newLineFlag = 0;   
           
        for(int i = 0; i < num; i++)   
        {   
            newLineFlag = 0;   
            StringBuffer sb = new StringBuffer();   
            boolean oneLetter = false;   
            rawStr = cin.nextLine();   
               
            for(int j = 0; j < rawStr.length(); j++)   
            {   
                temp = rawStr.charAt(j);   
                if(newLineFlag == 0)   
                {   
                    repeatChar = temp;   
                    repeat = 1;   
                    newLineFlag = 1;   
                    if(j == rawStr.length()-1)   
                        oneLetter = true;   
                    continue;   
                }   
                   
                if(temp == repeatChar)   
                {   
                    repeat++;   
                }else  
                {   
                    sb.append(repeat);   
                    sb.append(repeatChar);   
                    repeatChar = temp;   
                    repeat = 1;   
                }      
                   
                if(j == rawStr.length()-1)   
                {   
                    sb.append(repeat);   
                    sb.append(repeatChar);   
                }   
            }   
               
            if(oneLetter == true)   
            {   
                System.out.println("1" + temp);   
            }else  
            {   
                System.out.println(sb.toString());     
            }   
               
        }   
  
    }   
  
}  

							
Posted in poj | Comments Off on Poj Solution 3438

Poj Solution 3435

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

/* @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,i,j,k1,k2,p[][]=new int[101][101];
 n=sc.nextInt();
    
 int len=n*n;
 for(i=0;i< len;i++)
   for(j=0;j< len;j++)
    p[i][j]=sc.nextInt();
 boolean bb[]=new boolean[101],is=true;
  //memset(bb,0,sizeof(bb));
 for(i=0;i< len;i++)
 {
    Arrays.fill(bb,false);
    for(j=0;j< len;j++)
    {
         if(p[i][j]==0)continue;
      if(bb[p[i][j]])break;
      bb[p[i][j]]=true;
    }
    if(j< len)break;
   }
  if(i< len)is=false;
  for(j=0;j< len;j++)
  {
    Arrays.fill(bb,false);
    for(i=0;i< len;i++)
    {
         if(p[i][j]==0)continue;
      if(bb[p[i][j]])break;
      bb[p[i][j]]=true;
    }
    if(i< len)break;
   }
   if(j< len)is=false;
   for(i=0;i< len;i+=n)
    {
    for(j=0;j< len;j+=n)
    {
       Arrays.fill(bb,false);
       for(k1=i;k1< i+n;k1++)
       {
        for(k2=j;k2< j+n;k2++)
        {
             if(p[k1][k2]==0)continue;
          if(bb[p[k1][k2]])break;
          bb[p[k1][k2]]=true;
        }
        if(k2!=j+n)break;
        }
       if(k1!=i+n)is=false;
       if(is==false)break;
    }
    if(is==false)break;
     }
     if(is) System.out.println("CORRECT");
     else System.out.println("INCORRECT");    
   }
}
							
Posted in poj | Comments Off on Poj Solution 3435

Poj Solution 3429

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

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


public class Main {
    
 int n;

 BigInteger[] x = new BigInteger[115];
 BigInteger[] y = new BigInteger[115];
    
 public class Line {
    BigInteger a, b, c;
 }
    
    
 void run() {
   Scanner cin = new Scanner(System.in);
   BigInteger Zero = BigInteger.ZERO;
   n = cin.nextInt();
   int i;
   for(i = 0; i < n; ++i) {
    x[i] = cin.nextBigInteger();
    y[i] = cin.nextBigInteger();
   }
        
   int m = cin.nextInt(), ok = 0;
   for(i = 0; i < m; ++i) {
    int a, b, c, d;
    a = cin.nextInt();
    b = cin.nextInt();
    c = cin.nextInt();
    d = cin.nextInt();
    --a; --b; --c; --d;
    Line l1 = new Line(), l2 = new Line();
    l1.a = y[b].subtract(y[a]);
    l1.b = x[a].subtract(x[b]);
    l1.c = (l1.a.multiply(x[a])).add(l1.b.multiply(y[a]));
            
    l2.a = y[d].subtract(y[c]);
    l2.b = x[c].subtract(x[d]);
    l2.c = (l2.a.multiply(x[c])).add(l2.b.multiply(y[c]));
            
    BigInteger det = (l1.a.multiply(l2.b)).subtract((l2.a.multiply(l1.b)));
    BigInteger sx = (l2.b.multiply(l1.c)).subtract((l1.b.multiply(l2.c)));
    BigInteger sy = (l1.a.multiply(l2.c)).subtract((l2.a.multiply(l1.c)));
    int j;
    for(j = 0; j < n; ++j) {
        x[j] = x[j].multiply(det);
        y[j] = y[j].multiply(det);
    }
    if(sx.compareTo(Zero) == 0 && sy.compareTo(Zero) == 0) {
        if(ok == 0)
            ok = i+1;
    }
    x[n] = sx;
    y[n] = sy;
    n++;
    }
    System.out.println(ok);
   }

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

    }

}

							
Posted in poj | Comments Off on Poj Solution 3429

Poj Solution 3427

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

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,L,v;
 n=sc.nextInt();
 L=sc.nextInt();
 int m=0;
 while((n--)!=0)
 {
     v=sc.nextInt();
     if(v%L==0)continue;
     int u=L-v%L;
     if(u>m)m=u;
  }
  System.out.printf("%d",m);
 }
}
							
Posted in poj | Comments Off on Poj Solution 3427

Poj Solution 3425

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

//* @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);
    int n = sc.nextInt();
    Call[] calls = new Call[n];
    for(int i = 0; i < n; i++)
    {
        int q = sc.nextInt();
        int a = sc.nextInt();
        int x = sc.nextInt();

        calls[i] = new Call(q,a,x);
    }
    Arrays.sort(calls);

    int preQ = 0;
    int num = 0;
    int amount = 0;
    for(int i = 0; i < n; i++)
    {
        if(calls[i].q != preQ)
        {
            preQ = calls[i].q;
        num = 0;
        }
        if(calls[i].a == 1)
        {
        if(calls[i].x == 1)
        {
            amount += 40;
        }else
        {
            amount += 20;
        }
        amount += 10 * num;
        num++;

        }else
        {
        amount += 10;
        }
    }
    System.out.println(amount);
    }
}

class Call implements Comparable< Call>
{
    int q;
    int a;
    int x;

    Call(int q, int a, int x)
    {
        this.q = q;
    this.a = a;
    this.x = x;
    }

    public int compareTo(Call other)
    {
        if(this.q < other.q)
    {
        return -1;
    }else if(this.q == other.q)
    {
        return 0;
    }else
    {
        return 1;
    }
    }
}

							
Posted in poj | Comments Off on Poj Solution 3425

Poj Solution 3414

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

//* @author:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main{
 private static final String[] status = new String[] { "", "FILL(1)",
    "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" };
 private static boolean[][] visted = new boolean[101][101];
 private static int a;
 private static int b;
 private static int c;

 public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    for (int i = 0; i < 101; ++i) {
        for (int j = 0; j < 101; ++j)
            visted[i][j] = false;
    }
    a = sc.nextInt();
    b = sc.nextInt();
    c = sc.nextInt();
    bfs();
  }

  static void bfs() {
    boolean is = false;
    LinkedList< Node> queue = new LinkedList< Node>();
    Node p = new Node();
    p.aa = 0;
    p.bb = 0;
    visted[p.aa][p.bb] = true;
    queue.addLast(p);
    // visted[p.aa][p.bb] = true;
    // p = new Node();
    // p.aa = 0;
    // p.bb = b;
    // p.status.add(2);
    // visted[p.aa][p.bb] = true;
    // queue.addLast(p);
    while (!queue.isEmpty()) {
     Node front = queue.getFirst();
     queue.remove();
     int r = -1;
     for (int i = 1; i <= 6; ++i) {
      int aa = front.aa;
      int bb = front.bb;
      int flag = i;
      switch (flag) {
       case 1:
        aa = a;
        break;
       case 2:
        bb = b;
        break;
       case 3:
        aa = 0;
        break;
       case 4:
        bb = 0;
        break;
       case 5:
        r = b - bb;
        bb = bb + (r <= aa ? r : aa);
        aa = (r <= aa ? (aa - r) : 0);
        break;
       case 6:
        r = a - aa;
        aa = aa + (r <= bb ? r : bb);
        bb = (r <= bb ? (bb - r) : 0);
        break;
       default:
        break;
       }
       if (aa == c || bb == c) {
        int size = front.status.size();
        System.out.println(size + 1);
        for (int j = 0; j < size; ++j)
             System.out.println(status[front.status.get(j)]);
        System.out.println(status[flag]);
        is = true;
        return;
        }
        if (!visted[aa][bb]) {
         Node tmp = new Node();
         tmp.aa = aa;
         tmp.bb = bb;
         int size = front.status.size();
         for (int j = 0; j < size; ++j)
            tmp.status.add(front.status.get(j));
         tmp.status.add(flag);
         visted[aa][bb] = true;
         queue.addLast(tmp);
         }
     }
    }
    if (!is)
      System.out.println("impossible");
 }

 private static class Node {
    private int aa;
    private int bb;
    private ArrayList< Integer> status = new ArrayList< Integer>();
 }
}
							
Posted in poj | Comments Off on Poj Solution 3414

Poj Solution 3406

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

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
   Scanner in=new Scanner(System.in);
   int[] b2=new int[]{6,2,4,8};
   int[] b3=new int[]{1,3,9,7};
   int[] b7=new int[]{1,7,9,3};
   int[] b9=new int[]{1,9,1,9};
   int n=in.nextInt();
   int m=in.nextInt();
   int w=n-m;
   int e,a2=0,a3=0,a5=0,a7=0,a9=0;
   e=n;while((e=e/2)!=0) a2+=e;
   e=m;while((e=e/2)!=0) a2-=e;
   e=w;while((e=e/2)!=0) a2-=e;
   e=n;while((e=e/5)!=0) a5+=e;
   e=m;while((e=e/5)!=0) a5-=e;
   e=w;while((e=e/5)!=0) a5-=e;
   a3=f(n,3)-f(m,3)-f(w,3);
   a7=f(n,7)-f(m,7)-f(w,7);
   a9=f(n,9)-f(m,9)-f(w,9);
   int ans=1;
   if(a5>a2) System.out.println(5);
   else{
    a2-=a5;
    if(a2!=0){
         a2=a2%4;
      ans*=b2[a2];
      ans=ans%10;
    }
    ans*=b3[(a3%4+4)%4];
    ans=ans%10;
    ans*=b7[(a7%4+4)%4];
    ans=ans%10;
    ans*=b9[(a9%4+4)%4];
    ans=ans%10;
    System.out.println(ans);
    }
  }

  public static int f(int n,int a)
  {
    if(n==0) return 0;
    else return f(n/2,a)+g(n,a);
   }

  public static int g(int n,int a)
  {
    if(n==0)return 0;
    else if(n%10< a)return n/10+g(n/5,a);
    else return n/10+1+g(n/5,a);
  }
}
							
Posted in poj | Comments Off on Poj Solution 3406

Poj Solution 3404

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

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

public class Main {
    
 public static void main(String[] args) {
        
    int i,n,ans;
    int way[] = new int[60];
    Scanner cin = new Scanner(System.in);
    
    while(cin.hasNext())
    {
        n = cin.nextInt();
        for(i=0;i< n;++i)
            way[i] = cin.nextInt();
        Arrays.sort(way,0,n);
        ans = search(n,way);
        System.out.println(ans);
    }
   }

  public static int search(int n,int way[])
  {
    int  ans=0,i,j;
    if(n==1) return way[0];
    if(n==2) return way[1];
    if(n==3) return min(way[2]+way[0]+way[1],way[2]+way[1]+way[1]);
    return search(n-2,way)+min(way[n-1]+way[0]+way[1]+way[1],way[n-1]+way[n-2]+way[0]+way[0]);
   }
    public static int min(int a,int b)
    {
        if(a>b) return b;
        return a;
    }
    
}

							
Posted in poj | Comments Off on Poj Solution 3404

Poj Solution 3399

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


import java.util.*;
import java.math.*;
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int k1=0,k2=0,a=0,kk=0;
        int[] a1=new int[101],a2=new int[101],ans=new int[101];
        for(int i=0;i< n;++i){
            a=in.nextInt();
            if(a>=0)
                a1[k1++]=a;
            else a2[k2++]=a;
        }
        Arrays.sort(a1,0,k1);
        Arrays.sort(a2,0,k2);
        if(k%2==1){
            k--;
            if(k1>0)
                ans[kk++]=a1[--k1];
            else{
                for(int i=k2-1;i>k2-1-k;--i)
                    System.out.print(a2[i]+" ");
                System.out.println(a2[k2-1-k]);
                return ;
            }
        }
        int j2=0;
        for(int i=0;i< k/2;++i){
            int t1=-1000000000;
            int t2=-1000000000;
            if(k1==1&&k2-j2==1){
                ans[kk++]=a1[--k1];
                ans[kk++]=a2[j2++];
            }else{
                if(k1>1)
                    t1=a1[k1-1]*a1[k1-2];
                if(k2-j2>1)
                    t2=a2[j2]*a2[j2+1];
                if(t1>t2){
                    ans[kk++]=a1[--k1];
                    ans[kk++]=a1[--k1];
                }else{
                    ans[kk++]=a2[j2++];
                    ans[kk++]=a2[j2++];
                }
            }
        }
        Arrays.sort(ans,0,kk);
        for(int i=kk-1;i>0;--i)
            System.out.print(ans[i]+" ");
        System.out.println(ans[0]);
    }

}


							
Posted in poj | Comments Off on Poj Solution 3399

Poj Solution 3386

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

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;
int main()
{
    int A,a,B,b,P;
    while (cin>>A>>a>>B>>b>>P)
    {
        map<int,int> m;
        if (a == b)
        {
            if (!(A + B <= P))
                printf("Non");
            else
                printf("Yesn");
            continue;
        }
        m[a] = A;
        m[b] = B;
        if (A > P || B > P)
        {
            printf("Non");
            continue;
        }
        if (A + B <= P)
        {
            printf("Yesn");
            continue;
        }

        map<int,int>::iterator p = m.begin();
        p++;
        if ((*p).first < (*m.begin()).second)
        {
            printf("Non");
            continue;
        }
        printf("Yesn");


    }
    return 0;
}

/*
Halloween Holidays
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 1827  Accepted: 706 

Description

Planet Cucurbita is inhabited with intelligent pumpkins. These pumpkins are not only extremely clever, they also are fond of tourism. One of their main routes is the Earth during Halloween.

As you know, pumpkins cannot move by themselves (intelligent pumpkins are not an exception), so they make somebody else to transport them. In the case of Halloween this is done by humans. First, they make people to grow special biological docking stations, then prepare the stations (people cut special holes, fire candles etc �C you know the procedure), and after these preparations pumpkins come and have fun. People usually do not see anything and think that this is just a holiday and that this holiday is for humans, but remember �C if somebody is frightened at Halloween, he was frightened not by his not-very-friendly friends, but by alien pumpkins.

To use the biological docking station, a pumpkin must have a special transmitter. It��s main elements are two rings made of gold and for some unexplainable reasons these rings should be cut from one round plate. The sizes of these rings (inner and outer radii) are pumpkin-specific, so each alien should order a special set for himself.

Mr. Calabaza, an adolescent pumpkin, wants to make his first trip to the Earth. He found a discount plate, which was not redeemed by a previous customer, and it is necessary to check, whether this plate allows Mr. Calabaza to cut the rings he needs from it, or he should order a new larger plate.

Input

The input file contains five integer numbers A, a, B, b, P (0 < A, a, B, b, P �� 1 000 000, a < A and b < B), separated with spaces. Here, A and B are the outer radii of the rings, a and b are the inner radii of the corresponding rings, and P is the plate radius.

Output

Output a word ��Yes�� if the plate suits Mr. Calabaza, or a word ��No�� if he needs to order another one.

Sample Input

2 1 5 3 6
Sample Output

Yes

*/
							
Posted in poj | Comments Off on Poj Solution 3386

Poj Solution 3378

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

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

class Binary
{
    int n,i;
    long ret;
    long a[],c[];
    void init(int x)
    {
        n = x;
        a = new long [x+10];
        c = new long [x+10];
        for(i=0;i< x+10;++i)
        {
            a[i]=c[i]=0;
        }
    }
    void update(int x,long v)
    {
        a[x]+=v;
        for(i=x;i<=n;i+=lowbit(i)) c[i]+=v;
    }
    int lowbit(int x)
    {
        return (x)&(-x);
    }
    long query(int x)
    {
        for(ret=0,i=x;i>0;i^=lowbit(i)) ret+=c[i];
        return ret;
    }
}
public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int n,i,j;
    int way[] = new int[50010];
    int num[] = new int[50010];
    int mapping[]= new int[50010];
    
    BigInteger ans,temp;
        
    Binary array[] = new Binary[5];
    
     Scanner cin = new Scanner(System.in);
     while(cin.hasNext())
     {
    n = cin.nextInt();
    for(i=0;i< n;++i)
    {
        way[i]=cin.nextInt();
        num[i]=way[i];
    }
    Arrays.sort(num,0,n);
    mapping[0]=2;
    for(i=1;i< n;++i)
    {
        if(num[i]==num[i-1]) mapping[i]=mapping[i-1];
        else mapping[i]=mapping[i-1]+1;
    }
        
    for(i=0;i< n;++i)
    {
        way[i]=mapping[binary_search(0,n-1,way[i],num)];
    }
    for(i=0;i< 5;++i)
    {
        array[i]=new Binary();
        array[i].init(50010);
    }
            
    ans = new BigInteger("0");
    for(i=0;i< n;++i)
    {
        for(j=4;j>0;--j)
        {
           array[j].update(way[i], array[j-1].query(way[i]-1));
        }
        array[1].update(way[i], 1);
                
        temp = BigInteger.valueOf(array[4].query(way[i]-1));
        ans = ans.add(temp);
    }
            
    System.out.println(ans);
            
    }
 }
    public static int binary_search(int left,int right,int value,int num[])
    {
        int mid;
        while(left+1< right)
        {
            mid=(left+right)/2;
            if(num[mid]>value) right = mid;
            else left = mid;
        }
        if(num[left]==value) return left;
        return right;
    }

}

							
Posted in poj | Comments Off on Poj Solution 3378

Poj Solution 3372

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

//* @author: 82638882@163.com<br />
/*��Ŀ���⣺��n��ͬѧ���һ��Բ��һ��ʦ���ǹ��4η����1��2��4��7...��ͬѧ�����Ƿ�ÿ��ͬѧ���ܵõ�����һ���ǡ�
 *����д�����صij������1~100�������ѷ��֣�ֻ�е�n=2^k��kΪ����ʱ�����YES��
 */

import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
    Scanner in=new Scanner(System.in);
    
    while(in.hasNext())
    {
        int a=in.nextInt();
        while(a%2==0)
            a=a/2;
        if(a==1) System.out.println("YES");
        else System.out.println("NO");
    }
  }
}
							
Posted in poj | Comments Off on Poj Solution 3372

Poj Solution 3371

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

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.text.DecimalFormat;

class Main
{
  public static boolean isvowel(char a)
  {
     if (a=='a' || a=='e' || a=='i' || a=='o' || a=='u' || a=='y')
      return true;
     else
      return false;
  }

  public static boolean isword(char a)
  {
    if (a==',' || a==''' || a=='"')
      return true;
    else
      return false;
   }

  public static boolean issen(char a)
  {
     if (a==':' || a==';' || a=='?' || a=='.' || a=='!')
     return true;
     else
     return false;
  }

  public static void main(String [] args) throws IOException
  {
    Scanner cin=new Scanner(new BufferedInputStream(System.in));
    DecimalFormat df=new DecimalFormat("0.00");
    String inp,temp;
    int word,wordnum=0,sentnum=0,sylnum=0,i,len;
    double score;
    boolean hasaddsyl,hasaddword,hasvow,sinquo,douquo;
    while (cin.hasNext())
    {
    inp=cin.next();
    temp=inp.toLowerCase();
    len=temp.length();
    word=0;
    hasaddsyl=false;
    hasaddword=false;
    hasvow=false;
    sinquo=false;
    douquo=false;
    for (i=0;i< len;i++)
    {
      if (temp.charAt(i)>='a' && temp.charAt(i)<='z')
       {
        word++;
        if ((word<=3) && ((i+1==len) || isword(temp.charAt(i+1)) || issen(temp.charAt(i+1))))
        {
              word=0;
           if (!hasvow)
            sylnum++;
        }
        else if (isvowel(temp.charAt(i)))
        {
           hasvow=true;
           if (!hasaddsyl)
           {
            sylnum++;
            hasaddsyl=true;
           }
           else if (!isvowel(temp.charAt(i-1)))
           {
            if (temp.charAt(i)=='e')
               {
              if (((i+1==len) || (temp.charAt(i+1)>'z') || 
               (temp.charAt(i+1)< 'a')) && (temp.charAt(i-1)=='l'))
             {
               sylnum++;
               continue;
             }
             if ((i+1==len) || ((temp.charAt(i+1)< 'a') || (temp.charAt(i+1)>'z')))
               continue;
             if ((i+1< len) && ((temp.charAt(i+1)=='s') || 
               (temp.charAt(i+1)=='d')) && ((i+2==len) || 
               (temp.charAt(i+2)>'z') || (temp.charAt(i+2)< 'a')))
               continue;
             else
               sylnum++;
            }
            else
              sylnum++;
           }
       }
    }
    else if (isword(temp.charAt(i)))
    {
        hasvow=false;
        if (temp.charAt(i)==''' && !sinquo)
        {
             sinquo=true;
          continue;
        }
        if (temp.charAt(i)=='"' && !douquo)
        {
           douquo=true;
           continue;
        }
        wordnum++;
        word=0;
        hasaddword=true;
        hasaddsyl=false;
    }
    else if (issen(temp.charAt(i)))
    {
       wordnum++;
       word=0;
       hasvow=false;
       if ((i+1< len) && temp.charAt(i)=='.' && temp.charAt(i+1)=='.')
        while ((i+1< len) && temp.charAt(i+1)=='.')
             i++;
       else
        sentnum++;
        hasaddword=true;
    }
    }
    if (!hasaddword)
        wordnum++;
  }
  score=206.835-1.015*((double)(wordnum)/(double)(sentnum))-84.6*((double)(sylnum)/(double)(wordnum));
  System.out.println(df.format(score));
 }
}
							
Posted in poj | Comments Off on Poj Solution 3371

Poj Solution 3368

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

import java.io.*;
import java.util.*;
public class Main
{
  static  treex[] mytreex=new treex[210000];
  static int[] hash=new int[100005];
  static int[] left=new int[100005];
  static int[] right=new int[100005];
  static int[] data=new int[100005];
  static boolean build=false;
  static int k=0;
  
  public static void main(String args[]) throws Exception
  {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss;
    StringBuffer res=new StringBuffer();
    while(true)
    {
        build=false;
       ss=in.readLine().split(" ");
       int n=Integer.parseInt(ss[0]);
       if(n==0)
           break;
       int q=Integer.parseInt(ss[1]);
       ss=in.readLine().split(" ");
       k=1;
       for(int i=0;i< n;i++)
       {
           data[i]=Integer.parseInt(ss[i]);
           if(i>0&&data[i]!=data[i-1])
           {
               right[k]=i-1;
               left[k+1]=i;
              k++;
           }
           hash[i]=k;
         }
         right[k]=n-1;
         for(int i=0;i< q;i++)
         {
            ss=in.readLine().split(" ");
            int begin=Integer.parseInt(ss[0])-1;
            int end=Integer.parseInt(ss[1])-1;
            if(hash[begin]==hash[end])
            {
                  res.append(end-begin+1);
                  res.append("n");
                  continue;
            }
            if(hash[end]-hash[begin]==1)
            {
                int l=right[hash[begin]]-begin+1;
                int r=end-left[hash[end]]+1;
                int temp=l>r?l:r;
                res.append(temp);
                res.append("n");
                continue;
                        
            }
            if(!build)
            {
                  build=true;
                  buildtreex(1,k,1);
            }
            int n1=right[hash[begin]]-begin+1;
            int n2=end-left[hash[end]]+1;
            if(n1< n2)
                  n1=n2;
            n2=query(hash[begin]+1,hash[end]-1,1);
            res.append(n1>n2?n1:n2);
            res.append("n");    

        }
      }
      System.out.print(res.toString());
   }
            
  public static void buildtreex(int a,int b,int i)
  {
      if(mytreex[i]==null)
            mytreex[i]=new treex();
      mytreex[i].left=a;
      mytreex[i].right=b;
      if(a==b)
           mytreex[i].max=right[a]-left[a]+1;
      if(a!=b)
      {
           int mid=(a+b)/2;
           buildtreex(a,mid,i*2);
           buildtreex(mid+1,b,i*2+1);
           mytreex[i].max=mytreex[i*2].max>mytreex[i*2+1].max?mytreex[i*2].max:mytreex[i*2+1].max;
      }
   }
            
            
  public static int query(int a,int b,int i)
  {
     if(a==mytreex[i].left&&b==mytreex[i].right)
          return mytreex[i].max;
     int mid=(mytreex[i].left+mytreex[i].right)/2;
     if(b<=mid)
        return query(a,b,2*i);
     else if(a>=mid+1)
        return query(a,b,2*i+1);
     else
     {
       int l =query(a,mid,2*i);
       int r = query(mid+1,b,2*i+1);
       return l>r?l:r;
     }
  }
            
}

class treex
{
    int left;
    int right;
    int max;
}
							
Posted in poj | Comments Off on Poj Solution 3368

Poj Solution 3366

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

//* @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();
    int b=in.nextInt();
    String[] s1=new String[a];
    String[] s2=new String[a];
    for(int i=0;i< a;i++)
    {
        s1[i]=in.next();
        s2[i]=in.next();
    }
    for(int i=0;i< b;i++)
    {
         String s=in.next();
      boolean bb=false;
      for(int j=0;j< a;j++)
      {
       if(s.equals(s1[j]))
       {
        System.out.println(s2[j]);
        bb=true;
        break;
        }
       }
      if(!bb){
        if(s.endsWith("y"))
        {
            if(s.endsWith("ay")||s.endsWith("ey")||s.endsWith("iy")||s.endsWith("oy")||s.endsWith("uy"))
            System.out.println(s+"s");
         else
            System.out.println(s.substring(0,s.length()-1)+"ies");
        }
        else if(s.endsWith("o")||s.endsWith("s")||s.endsWith("ch")||s.endsWith("sh")
                ||s.endsWith("x")) System.out.println(s+"es");
        else System.out.println(s+"s");
        }
      }
    }
}
							
Posted in poj | Comments Off on Poj Solution 3366

Poj Solution 3365

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

/* @author: */
//����һ�ų�ΪH��Ϊw��ֽ��Ҫ����һ���������Բ����ʹ����Բ�İ뾶����
//���}�����һ����wΪ����Բ���ܳ���һ����H-2RΪ����Բ���ܳ���Ȼ��ȡ���ֵ�ͺ���

import java.util.Scanner;
import java.util.Arrays;
public class Main{
  static double pi=Math.PI;
  static double epx=1e-6;
  
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  double w,h,v1,v2,temp,r,d;   
    while(sc.hasNext()){
     w=sc.nextDouble();
     h=sc.nextDouble();
     if(w==0&&h==0) break;
        if(h>w){temp=h;h=w;w=temp;}   
        v1=h*h*(w-h/pi)/(4.0*pi);   
        d=w/(pi+1);   
        if(d>h+epx){/*�ж�d�Ƿ������*/  
           r=h/2.0;   
          v2=pi*r*r*h;   
        }   
        else v2=pi*w*w*h/(4.0*(pi+1)*(pi+1));   
        System.out.printf("%.3fn",Math.max(v1,v2));   
    }   
   }
  
}  

							
Posted in poj | Comments Off on Poj Solution 3365

Poj Solution 3364

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

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,m,c;
     while(sc.hasNext()){
        n=sc.nextInt();
        if(n==0) break;
        m=sc.nextInt();
        c=sc.nextInt();
       int t=(m-7)*(n-7);
    int t1=(t+1)/2;
    if (c==0) System.out.printf("%dn",t-t1);
    else System.out.printf("%dn",t1);
    
  }
}
}
							
Posted in poj | Comments Off on Poj Solution 3364

Poj Solution 3356

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

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


public class Main{

public static void main(String[] args) throws Exception{
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 String str ;
 while((str=in.readLine())!=null){
  StringTokenizer toke1 = new StringTokenizer(str);
  StringTokenizer toke2 = new StringTokenizer(in.readLine());
  int m = Integer.parseInt(toke1.nextToken());
  String str1 = toke1.nextToken();
  int n = Integer.parseInt(toke2.nextToken());
  String str2 = toke2.nextToken();
        
  int[][]array = new int[m+1][n+1];
        
  for(int i=0;i<=m;i++){
    array[i][0] = i;
  }
  for(int i=0;i<=n;i++){
    array[0][i] = i;
    }
        
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
     if(str1.charAt(i-1)==str2.charAt(j-1))
      array[i][j] = Math.min(Math.min(array[i-1][j-1], array[i-1][j]+1), array[i][j-1]+1);
     else
      array[i][j] = Math.min(Math.min(array[i-1][j-1]+1, array[i-1][j]+1), array[i][j-1]+1);
    }
    }
        
    System.out.println(array[m][n]);
    }
    }

}


							
Posted in poj | Comments Off on Poj Solution 3356

Poj Solution 3352

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 static int a,cnt=1;
 static int[] rank,un;
 static boolean[][] map;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss=in.readLine().split(" ");
    a=Integer.parseInt(ss[0]);
    map=new boolean[a+1][a+1];
    rank=new int[a+1];
    un=new int[a+1];
    for(int i=1;i<=a;i++)
        un[i]=i;
    int b=Integer.parseInt(ss[1]);
    for(int i=0;i< b;i++)
    {
        ss=in.readLine().split(" ");
        int x=Integer.parseInt(ss[0]);
        int y=Integer.parseInt(ss[1]);
        map[x][y]=map[y][x]=true;
    }
    dsf(1,1,rank,un);
    int cnt=0;
    for(int i=1;i<=a;i++)
        rank[i]=0;
    for(int i=1;i<=a;i++)
    {
      int yy=root(i,un);
      for(int j=1;j<=a;j++)
      {
        if(!map[i][j])continue;
        int ww=root(j,un);
        if(ww!=yy)
        {
             rank[yy]++;
          if(rank[yy]>1)break;
        }
       }
    }
    for(int i=1;i<=a;i++)
    {
       if(rank[i]==1)cnt++;
    }
    System.out.println((cnt+1)/2);
 }


 static void dsf(int n,int pre,int[] rank,int[] un)
 {
    if(rank[n]!=0)
    {
      for(int i=1;i<=a;i++)
        if(rank[i]>rank[n]) union(i,n,un);
    }
    else
    {
      rank[n]=cnt++;
      for(int i=1;i<=a;i++)
      {
        if(map[i][n]&&i!=pre&&root(i,un)!=root(n,un))
          dsf(i,n,rank,un);
       }
       rank[n]=0;
    }
  }

static void union(int a,int b,int[] un)
 {
    int x1=root(a,un);
    int y1=root(b,un);
    if(x1>y1)un[x1]=y1;
    else un[y1]=x1;
 }

static int root(int a,int[] un)
 {
    int b=a;
    while(b!=un[b])
        b=un[b];
    return un[a]=b;
 }
}


							
Posted in poj | Comments Off on Poj Solution 3352

Poj Solution 3349

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

//* @author: 
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Node
{
    int index;
    Node next;
}
public class Main
{
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    final int N=9997;

    int [][]snow=new int[100010][6];
    boolean check(int s1,int  s2)
    {
        boolean flag;
        int temp;
        
        for(int j=0;j< 6;j++)
        {
            flag=true;
            for(int step=0;step< 6;step++)
            {
                if(snow[s1][(j+step)%6]!=snow[s2][step])
                {    flag=false;    break;    }
            }
            if(flag) return true;
        }
        
        for(int j=0;j< 6;j++)
        {
            flag=true;
            for(int step=0;step< 6;step++)
            {
                temp=j-step;
                if(temp< 0) temp+=6; 
                if(snow[s1][temp]!=snow[s2][step])
                {    flag=false;    break;    }
            }
            if(flag) return true;
        }    
        return false;
    }
    boolean solve() throws IOException
    {
        int num,sum;
        String input;
        StringTokenizer st;
        num=Integer.parseInt(cin.readLine());
        
        Node[]vs=new Node[N];
        for(int i=1;i<=num;i++)
        {
            sum=0;
            input=cin.readLine();
            st=new StringTokenizer(input);
            for(int j=0;j< 6;j++)
            {
                snow[i][j]=Integer.parseInt(st.nextToken());
                sum+=snow[i][j];
            }
            if(vs[sum%N]==null)        //���t��
            {
                Node node=new Node();
                node.index=i;
                node.next=null;
                vs[sum%N]=node;
            }
            else
            {
                Node node=new Node();
                node.index=i;
                node.next=vs[sum%N];
                vs[sum%N]=node;
            }
        }
        for(int i=0;i< N;i++)
        {
            for(Node n1=vs[i]; n1!=null; n1=n1.next)
                for(Node n2=n1.next; n2!=null; n2=n2.next)
                    if(check( n1.index , n2.index ))    return true;
        }
        return false;
    }

    public static void main(String args []) throws IOException
    {
        Main test=new Main();
        if(test.solve())
            System.out.println("Twin snowflakes found.");
        else
            System.out.println("No two snowflakes are alike.");            
    }
}

 


							
Posted in poj | Comments Off on Poj Solution 3349

Poj Solution 3340

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

//* @author ������&lt;hongxp11@163.com&gt;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
 * @param args
 * @throws IOException
 */
public static int count(String a, String b) {
 int len = a.length();
 int result = 1;
 for (int i = 0; i < len; i++) {
    if (Character.isDigit(a.charAt(i))) {
        if (a.charAt(i) > b.charAt(i)) {
            for (int j = i + 1; j < len; j++) {
                if (a.charAt(j) == '?')
                    result *= 10;
            }
            return result;
        }
        if (a.charAt(i) < b.charAt(i))
            return 0;
    } else {
        if (len == i + 1)
            return '9' - b.charAt(i);
        else {
            String new_a = a.substring(i + 1);
            String new_b = b.substring(i + 1);
            for (int j = i + 1; j < len; j++) {
                if (a.charAt(j) == '?')
                    result *= 10;
            }
            return ('9' - b.charAt(i)) * result + count(new_a, new_b);
        }
    }
  }
  return 0;
}

 public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
        String wild = br.readLine();
        if (wild.equals("#"))
            break;
        String num = br.readLine();
        System.out.println(count(wild, num));
    }
 }

}

							
Posted in poj | Comments Off on Poj Solution 3340

Poj Solution 3332

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

import java.util.regex.*;import java.util.*;
public class Main { 
     public static void main(String[] args){ 
         String str; 
         int n; 
         Scanner cin = new Scanner(System.in);
          n=cin.nextInt();  
          str=cin.nextLine(); 
         Pattern pattern = Pattern.compile("(\s)*(\+|\-)?(\d)+(\.(\d)+)?((e|E)(\+|\-)?(\d)+)?");
         int i;
          for(i=0;i< n;++i){
              str=cin.nextLine(); 
             Matcher matcher = pattern.matcher(str); 
             if(matcher.matches()){ 
                 System.out.println("LEGAL"); 
             } 
             else{ 
                 System.out.println("ILLEGAL");
              } 
         } 
     }
}


							
Posted in poj | Comments Off on Poj Solution 3332

Poj Solution 3331

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

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.Scanner;   
  
/**  
 *  
 * poj3331  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int a = scan.nextInt();   
                int b = scan.nextInt();   
                BigDecimal sum = BigDecimal.ONE;   
                while (a > 0) {   
                    BigDecimal aa = new BigDecimal(a);   
                    sum = sum.multiply(aa);   
                    a--;   
                }   
                char[] cs = sum.toString().toCharArray();   
                int count = 0;   
                String s = b+"";   
                for (int k = 0; k < cs.length; k++) {   
                    if ((cs[k]+"").equals(s)) {   
                        count++;   
                    }   
                }   
                System.out.println(count);   
            }   
        }   
    }   
}  


							
Posted in poj | Comments Off on Poj Solution 3331

Poj Solution 3325

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

 import java.util.*;  
 import java.text.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         while(true)  
         {  
             int num = cin.nextInt();  
             if(num == 0)  
                 break;  
               
             int[] list = new int[num];  
             int max = 0;  
             int min = 1000;  
             int result = 0;  
             int tmp = 0;  
             for(int i = 0; i < num; i++)  
             {  
                 tmp = cin.nextInt();  
                 if(tmp > max)  
                     max = tmp;  
                 if(tmp < min)  
                     min = tmp;  
                 result += tmp;  
             }  
             result = (result - max - min)/(num-2);  
             DecimalFormat df = new DecimalFormat("");  
             System.out.println(df.format(result));  
         }  
   
     }  
}

							
Posted in poj | Comments Off on Poj Solution 3325

Poj Solution 3324

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
 public static void main(String args[]) throws Exception {
    Scanner cin=new Scanner(System.in);
    BigInteger s,M;
    int p,i;
    while(cin.hasNext())
    {
        p=cin.nextInt();
        s=BigInteger.valueOf(4);
        M=BigInteger.ONE;
        M=M.shiftLeft(p).subtract(BigInteger.ONE);
        for(i=0;i< p-2;++i)
        {
            s=s.multiply(s).subtract(BigInteger.valueOf(2));
            while(s.bitLength()>p)
            {
                s=s.shiftRight(p).add(s.and(M));
            }
        }
        if(s.compareTo(BigInteger.ZERO)==0||s.compareTo(M)==0)
        {
            System.out.println(0);
            continue;
        }
        String ans="";
        while(s.compareTo(BigInteger.ZERO)>0)
        {
            long buf=s.mod(BigInteger.valueOf(16)).longValue();
            ans+=Integer.toHexString((int)buf);
            s=s.divide(BigInteger.valueOf(16));
        }
        for(i=ans.length()-1;i>=0;--i)System.out.print(ans.charAt(i));
        System.out.println();
    }
  }
}
							
Posted in poj | Comments Off on Poj Solution 3324

Poj Solution 3321

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

//* @author: 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class cin
{
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int leave=0;
static int nextInt() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return Integer.parseInt(st.nextToken());
}
static String nextString() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return st.nextToken();
}
static boolean hasNext() throws IOException
{
   while(leave==0)
   {
    String temp=in.readLine();
    if(temp==null)return false;
    st=new StringTokenizer(temp);
    leave=st.countTokens();
   }
   return true;
}
}

class Node //���ڽӱ�
{
int now,v=1;
Node next;
Node(int y)
{
   now=y;
   next=null;
}
}

class TreeArray //��״����
{
    int value[],n;
    int now;
    Node tree[];
    int pis[][];
    TreeArray(int num,Node e[])
    {
    n=num;
    value=new int[n+1];
    tree=e;
    pis=new int[n+1][2];
    Arrays.fill(value,0);
    }
    
    int lowBit(int t)
    {
    return t&(t^(t-1));
    }
    
    void plus(int a,int i)
    {
    while(i<=n)
    {
       value[i]+=a;
        i+=lowBit(i);
    }
    }
    
    int getSum(int i)
    {
    int sum=0;
    while(i>0)
    {
       sum+=value[i];
       i=i-lowBit(i);
    }
    return sum;
    }
    void dfs(int t) //dfs��¼ʱ��
    {
    pis[t][0]=now;
    now++;
    Node p=tree[t].next;
    while(p!=null)
    {
       dfs(p.now);
       p=p.next;
    }
    pis[t][1]=now;
    
    }
    void init()
    {
    now=0;
    dfs(1);
    for(int i=1;i<=n;i++) //��ʼ����״����
    {
       plus(1,i); 
    }
    }
}

public class Main {
    public static void main(String args[]) throws IOException
    {
    int n,t1,t2,i;
    String s;
    n=cin.nextInt();
    Node lunch[]=new Node[n+1],temp;
    for(i=1;i<=n;i++)
    {
       lunch[i]=new Node(i);
    }
    for(i=0;i< n-1;i++)
    {
       t1=cin.nextInt();
       t2=cin.nextInt();
       temp=new Node(t2);
         temp.next=lunch[t1].next;
         lunch[t1].next=temp;
    }
    TreeArray data=new TreeArray(n,lunch);
    data.init();
    n=cin.nextInt();
    for(i=0;i< n;i++)
    {
       s=cin.nextString();
       t1=cin.nextInt();
       if(s.charAt(0)=='C')
       {
        if(data.tree[t1].v==1)
        {
         data.tree[t1].v=0;
         data.plus(-1,data.pis[t1][0]+1);
        }
        else
        {
         data.tree[t1].v=1;
         data.plus(1,data.pis[t1][0]+1);
        }
       }
       else 
       {
        t2=data.getSum(data.pis[t1][0]);
        int t3=data.getSum(data.pis[t1][1]);
        System.out.println(t3-t2);
       }
    }
    }
}
							
Posted in poj | Comments Off on Poj Solution 3321

Poj Solution 3307

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

//* @author 
import java.util.*;
public class Main{
  public static void main(String args[]){
  
    int k,n;
    Scanner in=new Scanner(System.in);
    k=in.nextInt();
    init();
    while(k-->0){
        n=in.nextInt();
       System.out.printf("%dn",s[n]);
    }
   
   }

  static int MAX=80000;
  static long s[]=new long[MAX];       //���ڴ洢�������
  static long d2[]=new long[MAX];     //�洢���к���������2�ҷ���������
  static long d3[]=new long[MAX];     //�洢���к���������3�ҷ���������
  static long d5[]=new long[MAX];
  static long d7[]=new long[MAX];

  public static void init(){
    int i;
    int pos2,pos3,pos5,pos7;
    long a,b;
    s[1]=1;
    pos2=pos3=pos5=pos7=1;
    for(i=1;i< MAX-1;i++){
        d2[i]=s[i]*2;
        d3[i]=s[i]*3;
        d5[i]=s[i]*5;
        d7[i]=s[i]*7;
        while(d2[pos2]<=s[i])pos2++;     //��������С��s[i]����ô��һ���Ѿ���s[i]�У�����ȥ��
        while(d3[pos3]<=s[i])pos3++;     //��Ȼs[i]�Ǵ��ĸ������д�С����ѡ��4�ģ�
        while(d5[pos5]<=s[i])pos5++;     //�����������һ������ȷ��
        while(d7[pos7]<=s[i])pos7++;
        a=d2[pos2]< d3[pos3]?d2[pos2]:d3[pos3];
        b=d5[pos5]< d7[pos7]?d5[pos5]:d7[pos7];
        s[i+1]=a< b?a:b;
    }
  }
}



							
Posted in poj | Comments Off on Poj Solution 3307

Poj Solution 3302

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

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

public class Main {

    /**
     * @param args
     */
    public static boolean isSubsequence(String s1, String s2) {
        int len = s2.length();
        int index = -1;
        int i = 0;
        for (i = 0; i < len; i++) {
            index = s1.indexOf(s2.charAt(i), index + 1);
            if (index == -1) {
                break;
            }
        }
        if (i == len && index != -1)
            return true;
        index = -1;
        for (i = len; i > 0; i--) {
            index = s1.indexOf(s2.charAt(i - 1), index + 1);
            if (index == -1)
                break;
        }
        if (i == 0 && index != -1)
            return true;
        return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        for (int i = 0; i < num; i++) {
            String s1 = in.next();
            String s2 = in.next();
            if (isSubsequence(s1, s2)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

}

							
Posted in poj | Comments Off on Poj Solution 3302

Poj Solution 3300

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

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

public class Main {
    static final int N = 20;
    static int n,m;
    static double front[] = new double[N],rear[] = new double[N],cnt[]=new double[N*N];
    
    static double Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    
public static void main(String[]args) throws Exception{
 int i;
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
 while(true){
    n = (int) Get_Num(cin);
    if(n<=0) break;
    m = (int) Get_Num(cin);
    for(i=0;i< n;++i)
        front[i] = Get_Num(cin);
    for(i=0;i< m;++i)
        rear[i] = Get_Num(cin);
    System.out.printf("%.2fn",solve());
  }
 }

static double solve(){
  double ans=0.0;
  int i,j,top=0;
  for(i=0;i< n;++i){
    for(j=0;j< m;++j){
        cnt[top++] = rear[j]/front[i];
    }
   }
  Arrays.sort(cnt,0,top);
  for(i=1;i< top;++i){
    ans = ans>(cnt[i]/cnt[i-1])?ans:(cnt[i]/cnt[i-1]);
  }
    return ans;
 }
}

							
Posted in poj | Comments Off on Poj Solution 3300

Poj Solution 3299

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

import java.util.Scanner;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        while (scan.hasNext()) {   
            double temperature = 0, dewpoint = 0, humidex = 0;   
            String[] ss = scan.nextLine().split(" ");   
            String sa = ss[0];   
            if (sa.equals("E")) {   
                break;   
            }   
            double a = Double.parseDouble(ss[1]);   
            String sb = ss[2];   
            double b = Double.parseDouble(ss[3]);   
            if (sa.equals("T") && sb.equals("D")) {   
                temperature = a;   
                dewpoint = b;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                humidex = temperature + h;   
            }   
            if (sa.equals("D") && sb.equals("T")) {   
                temperature = b;   
                dewpoint = a;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                humidex = temperature + h;   
            }   
            if (sa.equals("D") && sb.equals("H")) {   
                dewpoint = a;   
                humidex = b;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                temperature = humidex - h;   
            }   
            if (sa.equals("H") && sb.equals("D")) {   
                dewpoint = b;   
                humidex = a;   
                double e = 6.11 * Math.pow(2.718281828, 5417.7530 * ((1 / 273.16) - (1 / (dewpoint + 273.16))));   
                double h = (0.5555) * (e - 10.0);   
                temperature = humidex - h;   
            }   
            if (sa.equals("T") && sb.equals("H")) {   
                temperature = a;   
                humidex = b;   
                double h = humidex - temperature;   
                double e = h / 0.5555 + 10.0;   
                dewpoint = 1 / ((1 / 273.16) - Math.log(e / 6.11) / 5417.7530) - 273.16;   
            }   
            if (sa.equals("H") && sb.equals("T")) {   
                temperature = b;   
                humidex = a;   
                double h = humidex - temperature;   
                double e = h / 0.5555 + 10.0;   
                dewpoint = 1 / ((1 / 273.16) - Math.log(e / 6.11) / 5417.7530) - 273.16;   
            }   
            System.out.print("T ");   
            System.out.printf("%.1f", temperature);   
            System.out.print(" D ");   
            System.out.printf("%.1f", dewpoint);   
            System.out.print(" H ");   
            System.out.printf("%.1f", humidex);   
            System.out.println();   
        }   
    }   
}  


							
Posted in poj | Comments Off on Poj Solution 3299

Poj Solution 3298

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

// author:M.J
import java.util.*;
import java.io.*;
public class Main{
 public static void main(String[] args){
  Scanner in = new Scanner(new BufferedInputStream(System.in));
    int T = in.nextInt();
    while(T > 0){
        T--;
        int n = in.nextInt();
        int k = in.nextInt();
        n--;
        int curr = k;
        int flag = 0;
        int ans = 1;
        while(n > 0){
            n--;
            k = in.nextInt();
            if(flag%2==0 && curr < k)
                curr = k;
            else if(flag%2==1 && curr > k)
                curr = k;
            if(flag%2==0 && k < curr){
                flag ++;
                ans ++;
                curr = k;
            }
            else if(flag%2==1 && k > curr){
                flag ++;
                ans ++;
                curr = k;
            }
        }
        System.out.println(ans);
    }
   }
}

							
Posted in poj | Comments Off on Poj Solution 3298

Poj Solution 3295

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

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

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

 public void init() {
  Scanner sc = new Scanner(System.in);
  char[] s;
  boolean flag;
  while (!sc.hasNextInt()) {
    flag = true;
    s = sc.next().toCharArray();
    for (int i = 0; i < 32; i++) {
        if (!check(i, s)) {
            flag = false;
            break;
        }
    }
    if (flag)
        System.out.println("tautology");
    else
        System.out.println("not");
   }
 }

  public boolean check(int i, char[] s) {
   Stack< Integer> stack = new Stack< Integer>();
   for (char c : s) {
    if (c >= 'p' && c <= 't') {
        int d = c - 'p';
        d = (1 <<  d & i) >> d;
        boolean flag = true;
        while (flag) {
            if (stack.isEmpty()) {
                stack.push(d);
                flag = false;
            } else if (isoperate(stack.peek())) {
                stack.push(d);
                flag = false;
            } else if (stack.peek() == 'N') {
                d = 1 - d;
                stack.pop();
            } else {
                int dd = stack.pop();
                int oper = stack.pop();
                switch (oper) {
                case 'K':
                    d &= dd;
                    break;
                case 'A':
                    d |= dd;
                    break;
                case 'C':
                    d = dd - d > 0 ? 0 : 1;
                    break;
                case 'E':
                    d = 1 - (d ^ dd);
                    break;
                default:
                    break;
                }
            }
        }
    } else {
        stack.push((int) c); 
    }
   }

   return stack.pop() == 1;
  }


  private boolean isoperate(Integer peek) {
    switch (peek.intValue()) {
    case 'K':
    case 'A':
    case 'C':
    case 'E':
        return true;
    default:
        return false;
    }
  }

}
							
Posted in poj | Comments Off on Poj Solution 3295

Poj Solution 3286

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

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
    static long[] a=new long[]{
        1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000
    };
    static long[] b=new long[]{
        0,1,11,192,2893,38894,488895,5888896,68888897,788888898
    };
    static long[] c=new long[]{
        0,1,20,300,4000,50000,600000,7000000,80000000,900000000
    };
    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(" ");
            long a=Long.parseLong(ss[0]);
            long b=Long.parseLong(ss[1]);
            if(a==-1&&b==-1)break;
            if(a==0)System.out.println(f(b)+1);
            else System.out.println(f(b)-f(a-1));
        }
    }
    static long f(long w)
    {
        int i;
        long q=w;
        for(i=0;i< 10;i++)
            if(a[i]>w)break;
        long sum=0;
        for(int j=i-1;j>0;j--)
        {
            long u=w/a[j];
            if(u>0)
                sum+=b[j]+(u-1)*c[j];
            w=w%a[j];
        }
        long total=0,oo=0;
        w=q;
        String s=w+"";
        for(int j=1;j< i-1;j++)
        {
            if(w%(a[j]*10)>=a[j]){
                total+=a[j]-1;
                oo+=total;
            }
            else oo+=w%(a[j]*10);
        }
        int bb=0;
        long yy=0;
        for(int g=1;g< s.length();g++)
        {
            if(s.charAt(g)!='0'){
                bb++;
                continue;
            }
            yy+=(Math.pow(10, s.length()-g-1)-1)*bb;
        }
        sum+=oo;
        sum+=yy;
        return sum;    
    }
}
							
Posted in poj | Comments Off on Poj Solution 3286

Poj Solution 3282

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

//* @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 sl,sr,left,right;
    int nn=sc.nextInt();
    while((nn--)!=0)
    {
      int l=sc.nextInt();
      int n=sc.nextInt();
        l*=100;sl=0;sr=0;left=0;right=0;
        for (int i=1;i<=n;i++) {
         int  t=sc.nextInt();
         char s[]=sc.next().toCharArray();
            if (s[0]=='l') {
                 if (sl+t>l) {sl=t;left++;}
                 else sl+=t;
            }
            else {
                 if (sr+t>l) {sr=t;right++;}
                 else sr+=t;
            }
        }
        if (sl!=0) left++;
        if (sr!=0) right++;
        System.out.printf("%dn",left>right?left+left-1:right+right);        
    }
  }
}
							
Posted in poj | Comments Off on Poj Solution 3282

Poj Solution 3278

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

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
public class Main {   
  
    public static final int MAX = 200000;   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            int k = scan.nextInt();   
            System.out.println(catchTheCow(n, k));   
        }   
    }   
  
    public static int catchTheCow(int n, int k) {   
        if (n == k) {   
            return 0;   
        }   
        LinkedList<Integer> queue = new LinkedList();   
        boolean[] visited = new boolean[MAX + 5];   
        int[] minutes = new int[MAX + 5];   
        visited[n] = true;   
        queue.add(n);   
        while (!queue.isEmpty()) {   
            int current = queue.removeFirst();   
            for (int i = 0; i < 3; i++) {   
                int next = current;   
                if (i == 0) {   
                    next++;   
                } else if (i == 1) {   
                    next--;   
                } else if (i == 2) {   
                    next <<= 1;   
                }   
                if (next < 0 || next > MAX) {   
                    continue;   
                }   
                if (!visited[next]) {   
                    queue.add(next);   
                    visited[next] = true;   
                    minutes[next] = minutes[current] + 1;   
                }   
                if (next == k) {   
                    return minutes[k];   
                }   
            }   
        }   
  
        return 0;   
    }   
}  
							
Posted in poj | Comments Off on Poj Solution 3278