Monthly Archives: June 2011

http://poj.org/problem?id=1830 //* @author: /*��˹��Ԫ,Ȼ������Ԫ��ľ���õ���,����ì�ܵ������޽� �����ĸ���Ϊ2^k kΪ����ȫΪ0������ */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; 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 { return Integer.parseInt(next()); } static … Continue reading →

http://poj.org/problem?id=1829 #include <stdio.h> #include <memory.h> #include <algorithm> using namespace std; int ans[1025][161], s[1025]; int v[161], n, m; const int MAX = ( (unsigned int)1<<31-1 ); void clac( ) { int i, j, k, t, h, best; memset( ans, 0x7F, sizeof … Continue reading →

http://poj.org/problem?id=1828 //* @author: ccQ.SuperSupper import java.util.*; //Monkeys’ Pride class node implements Comparable { int x,y; public int compareTo(Object o) { node oo=(node)o; if(this.x!=((node)o).x) return this.x>((node)o).x?1:0; return this.y>((node)o).y?1:0; } } public class Main{ static int N = 500000+100; public static void … Continue reading →

http://poj.org/problem?id=1825 #include"stdio.h" #include<iostream> #include"memory.h" using namespace std; int x[20],y[20],m; int s[2000],len; void cheng(int a) {int i,t; for(i=0,t=0;i<len;i++) {s[i]*=a;s[i]+=t; t=s[i]/10; s[i]%=10; } while(t) {s[len++]=t%10; t/=10; } } int p[]={2,3,5,7,11,13,17,19,23,29,31 ,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101, 103 , 107, 109 , 113, 127 , 131 , … Continue reading →

http://poj.org/problem?id=1823 #include"stdio.h" #include"memory.h" const int L=2048*16; short left[L],right[L],max[L];char stop[L]; #define bigger(a,b) (((a)>(b))?(a):(b)) //inline short bigger(short a,short b) //{return a>b?a:b;} short a,b,key; void insert(short root,short begin,short end) { if(begin>end||b<begin||end<a)return; short l1,l2,*l=&left[root],*r=&right[root]; if(a<=begin&&end<=b) { stop[root]=1; if(key==1) { (*l)=(*r)=max[root]=0; } else { (*l)=(*r)=max[root]=end-begin+1; … Continue reading →

http://poj.org/problem?id=1819 #include<iostream> #include"math.h" using namespace std; double r[1000]; double x[1000],t[1000]; char set[1000]; int n; void init() {int i; cin>>n; for(i=0;i<n;i++){set[i]=1;cin>>r[i];} } void doit() {int i,j,k=0,s; for(i=0;i<n;i++) {x[i]=r[i]; k=-1; for(j=0;j<i;j++) if(set[j]) {t[j]=sqrt((r[i]+r[j])*(r[i]+r[j])-(r[i]-r[j])*(r[i]-r[j]))+x[j]; if(t[j]>x[i]){x[i]=t[j];k=j;} } for(j=k+1;j<i;j++)set[j]=0; } double right=0; for(i=0;i<n;i++)if(x[i]+r[i]>right){right=x[i]+r[i];k=i;} for(j=k+1;j<n;j++)set[j]=0; for(i=0,s=0;i<n;i++)if(!set[i])s++; … Continue reading →

http://poj.org/problem?id=1816 #include <stdio.h> #include <string.h> #include <memory.h> char w[100000][7]; int len[100000]; int code[100000]; bool check( char *p, int n, char *w, int m ) { bool ans[7][21] = { false }; char *a = p-1, *b = w-1; ans[0][0] = … Continue reading →

http://poj.org/problem?id=1813 #include<iostream> #include"math.h" #include"stdio.h" using namespace std; struct point {double x,y;}; const double pi=3.14159265359; inline double cheng(point a,point b,point c) {return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);} inline double dcheng(point a,point b,point c) {return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);} double doit(point p1,point p2,point o,double r) {point px,p[16];int set[16];int s=0;double … Continue reading →

http://poj.org/problem?id=1812 #include <stdio.h> #include <queue> #include <vector> #include <memory.h> #include <algorithm> using namespace std; char op[10]; int opn, ans; void search( int h, const int *str, int len ) { int i, j, k; if( h >= ans ) return; … Continue reading →

http://poj.org/problem?id=1811 /* @author: */ //��һ����N���ж���N�Ƿ�Ϊ������������������"Prime"�����������N����С������ import java.util.Random; import java.util.Scanner; //http://en.wikipedia.org/wiki/Pollard’s_rho_algorithm public class Main{ static int MAX_COUNT = 6; static long allFactor[ ]=new long [65]; static int nFactor; static Random rn=new Random(); static long fMultiModular( long a, long b, long n) … Continue reading →

http://poj.org/problem?id=1810 #include<iostream> #include"algorithm" using std::sort; using namespace std; int s[1001],N,K,M; long d[10000]; int max() {int i,k=M; for(i=M+1;i<=N;i++)if(s[k]<=s[i])k=i; return k; } void find() {int i,j,k,h,down,up,x=N,y=N,best=0; for(i=N,j=0,h=0;i>=M;i–) {while(h<j&&d[h]%2000>i) {down=d[h]/2000;up=down+M-1<N?down+M-1:N; for(k=down;k<=up;k++)s[k]–; h++; } while(j<K&&i-d[j]%2000<M) {down=d[j]/2000;up=down+M-1<N?down+M-1:N; for(k=down;k<=up;k++)s[k]++; j++; } k=max(); if(s[k]>best){best=s[k];y=k;x=i;} if(j>=K)break; } cout<<x-M<<‘ … Continue reading →

http://poj.org/problem?id=1808 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; import java.math.*; public class Main { public static long mod(long a,long b,long c) { long ret=1%c; while(b!=0) { if((b&0x1)!=0) ret=ret*a%c; a=a*a%c; b>>=1; } return ret; } public static void main(String args[]) throws … Continue reading →