Category Archives: poj

http://poj.org/problem?id=1946 #include <iostream> using namespace std; int maxs[101][101], n, e, d; // ʱ�� �� int need[101][101]; // ·�� �� void init() { int t, s, v, h; cin>>n>>e>>d; for( t=0; t<=d; t++ ) maxs[t][0] = 0; for( h=0; h<=e; h++ … Continue reading →

http://poj.org/problem?id=1944 #include <stdio.h> #include <algorithm> #include <memory.h> using namespace std; int t[4100]; int sum[4100]; void insert( int l, int r, int a, int b, int s, bool del ) { int c = (l+r)/2; if( l>=r || l>=b || r<=a … Continue reading →

http://poj.org/problem?id=1942 //* @author: 82638882@163.com import java.io.*; public class Main { 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 n=Long.parseLong(ss[0]); Long m=Long.parseLong(ss[1]); if(n==0&&m==0) break; long ans=1; n=m+n; if(m>n-m) m=n-m; … Continue reading →

http://poj.org/problem?id=1940 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); double[] x=new double[a]; double[] y=new double[a]; for(int i=0;i< a;i++) { x[i]=in.nextDouble(); y[i]=in.nextDouble(); } double sx=0,sy=0,uu=-1; System.out.print(a); for(int … Continue reading →

http://poj.org/problem?id=1939 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); System.out.print(a+" "); double x1,y1,x,y,kx,ky; x=x1=in.nextDouble(); y=y1=in.nextDouble(); for(int i=1;i< a;i++) { kx=in.nextDouble(); ky=in.nextDouble(); System.out.printf("%.6f %.6f ",(x+kx)/2,(y+ky)/2); x=kx; y=ky; … Continue reading →

http://poj.org/problem?id=1936 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String[] str = new String[2]; String a, b; boolean result; while(cin.hasNext()) { str = cin.nextLine().split(" "); a = str[0]; b = str[1]; … Continue reading →

http://poj.org/problem?id=1934 #include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <set> using namespace std; int ans[81][81]; int from[81][81]; char route1[100],route2[100]; int n,m; void doit() { int i,j; for( i=0; i<=n; i++) ans[i][0] = 0; for( j=0; j<=m; j++) ans[0][j] = … Continue reading →

http://poj.org/problem?id=1928 //* @author: 82638882@163.com import java.io.*; import java.util.Arrays; public class Main { 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) { String[] ss=in.readLine().split(" "); int cow=Integer.parseInt(ss[0]); int cul=Integer.parseInt(ss[1]); int sum=Integer.parseInt(ss[2])-2; my[] … Continue reading →

http://poj.org/problem?id=1927 /* @author: */ import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = 1; double l1, l2, l3, s, c, p, R, ctg1, ctg2, ctg3, len, r, ls, area; … Continue reading →

http://poj.org/problem?id=1925 #include"stdio.h" #include"math.h" #include"memory.h" int x[5010],h[5010]; int pos[1000001]; int n; void init() { int i; scanf( "%d", &n ); for( i=0; i<n; i++ ) scanf( "%d %d", x+i, h+i ); memset( pos, -1, sizeof(int)*(x[n-1]+1) ); } void doit() { int … Continue reading →

http://poj.org/problem?id=1923 import java.util.Scanner; public class Main { static int com(int a) { return a*(a-1)/2; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); long line[][]=new long[101][10001]; int i,j,k,p,q,cs=0; long max,tmp; for(i=1;i<=100;i++) line[i][0]=i+1; for(i=2;i<=100;i++) for(j=1;j<=com(i);j++) { max=0; for(k=1;k<=i-1;k++) … Continue reading →

http://poj.org/problem?id=1922 import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner s = new Scanner(System.in); while(true) { int n = s.nextInt(); if(n == 0) System.exit(-1); double min = 1000000000; while(n > 0) { int v = s.nextInt(); int … Continue reading →

http://poj.org/problem?id=1916 #include <iostream> #include <string.h> using namespace std; int a[1030][1030]; int main() { int test,d,n,i,max,j,temp,x,y,now; cin>>test; while(test–) { cin>>d; cin>>n; memset(a,0,sizeof(a)); for(i=0;i<n;i++) { cin>>x>>y; cin>>a[x][y]; } max=-1; for(i=1;i<1025;i++) { a[i][0]+=a[i-1][0]; a[0][i]+=a[0][i-1]; } temp=2*d+1; for(i=1;i<1025;i++) for(j=1;j<1025;j++) { a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; if(i>=temp&&j>=temp) { now=a[i][j]-a[i-temp][j]-a[i][j-temp]+a[i-temp][j-temp]; … Continue reading →

http://poj.org/problem?id=1915 import java.io.BufferedInputStream; import java.util.LinkedList; import java.util.Scanner; public class Main { private static int[][] directions = new int[][]{ {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; static void BreadthFirstSearch(int startX, int startY, … Continue reading →

http://poj.org/problem?id=1914 //* @author popop0p0popo import java.util.*; import java.io.*; import java.text.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n=scanner.nextInt(); BigInteger[][] a; BigInteger[] b; BigInteger aa,aa1,aa2,aa3; for (int i=0;i< n ;i++ ){ a=new … Continue reading →

http://poj.org/problem?id=1909 //* @author: ccQ.SuperSupper import java.util.*; import java.io.*; class node{ int init_have; int sum_have; int nodes; Vector son = new Vector(); } public class Main { static int N = 10000+100; public static void main(String []args) throws Exception{ int n,i,j,ans,cnt,sons,root; … Continue reading →

http://poj.org/problem?id=1906 //* @author: import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[]args){ BigInteger dat[]=new BigInteger[100]; dat[0]=BigInteger.ONE; BigInteger tr=new BigInteger("3"); for(int i=1;i< 100;i++){ dat[i]=dat[i-1].multiply(tr); } long N; int t; boolean first; Scanner cin=new Scanner(System.in); while(cin.hasNext()){ N=cin.nextLong(); if(N==0) break; … Continue reading →

http://poj.org/problem?id=1905 /* @author: */ import java.util.Scanner; public class Main{ static final double PI=3.1415926; static final double eps=1e-6; public static void main(String args[]) { Scanner sc=new Scanner(System.in); double L,n,C,M,y1,low,high,mid; while(true) { L=sc.nextDouble(); n=sc.nextDouble(); C=sc.nextDouble(); if(L==-1&&n==-1&&C==-1)break; if(L<=eps||n<=eps||C<=eps) { System.out.println("0.000"); continue; } M=(1+n*C)*L; … Continue reading →

http://poj.org/problem?id=1904 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int e2[2010], ee2[2010], n; vector<int> e1[2010]; vector<int> ee1[2010]; vector<int> ans[2010]; void input( ) { int i, k, m; scanf( "%d", &n ); for( i=0; i<n; i++ ) { scanf( "%d", … Continue reading →

http://poj.org/problem?id=1901 #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; const int size = 1000; struct point { double x, y, z; int k; }p[size]; inline double dis( point &a, point &b ) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z); … Continue reading →

http://poj.org/problem?id=1896 //* @author:alpc12 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; StringBuffer sb = new StringBuffer(); while ((line = in.readLine()) != null) { for … Continue reading →

http://poj.org/problem?id=1894 import java.io.*; import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { BigInteger sum,m,D[] = new BigInteger[2]; int i,b[] = new int[340]; Scanner cin = new Scanner(System.in); m = cin.nextBigInteger(); sum = cin.nextBigInteger(); int k … Continue reading →

http://poj.org/problem?id=1887 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int totalnum; int count = 0; //while((totalnum=Integer.parseInt(in.readLine()))!=-100){ while(true) { int num; ArrayList < Integer> array = … Continue reading →

http://poj.org/problem?id=1882 #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define NMAX 101 #define INF 10000 int anset[NMAX],alen,min; int m[10020]; int t[NMAX]; int N,S,len; void solve() { int i,j; m[0]=0; i=1; while(1) { m[i]=INF; for(j=0;j<len;j++) { if(t[j]>i) break; if(m[i]>m[i-t[j]]+1) { m[i]=m[i-t[j]]+1; } } if(m[i]>S) break; … Continue reading →

http://poj.org/problem?id=1868 /* @author: */ import java.util.Scanner; public class Main { private int n; private int a[]; public Main(int n,int[] a){ this.n=n; this.a=a; } public boolean doIt(){ for(int j=1;j< n/2;j++) { for(int i=j;i< n-j;i++) { if((a[i-j]-a[i])*(a[i+j]-a[i])< 0) { return true; } … Continue reading →

http://poj.org/problem?id=1867 #include <stdio.h> #include <vector> #include <string.h> using namespace std; #define YES { printf( "samen" ); continue; } #define NO { printf( "differentn" ); continue; } #define PT(a) (printf("an")); struct node { vector< node* > next; char c; }mem[500]; char … Continue reading →

http://poj.org/problem?id=1862 import java.util.*; import java.text.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int num = Integer.valueOf(cin.nextLine()).intValue(); List list = new ArrayList(); for(int i = 0; i < num; i++) list.add(Double.valueOf(cin.nextLine())); Collections.sort(list); double … Continue reading →

http://poj.org/problem?id=1861 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class Edge implements Comparable{ int u,v,disten; Edge(){}; void set(int u,int v,int disten){ this.u = u; this.v = v; this.disten = disten; } public int compareTo(Object obj){ Edge temp = (Edge)obj; if(this.disten>temp.disten) return … Continue reading →

http://poj.org/problem?id=1860 //* @author import java.io.File; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; //���·��bellman_ford public class Main { Scanner cin = new Scanner(System.in); int n; int m; int s; double v; Edge[] rate; Edge[] commission; double[] value; public static final double EPS … Continue reading →

http://poj.org/problem?id=1859 #include <stdio.h> #include <algorithm> using namespace std; struct pairs { int first, second; }p[20100]; bool cmp( const pairs& a, const pairs& b ) { return a.first<b.first || a.first==b.first&&a.second<b.second; } int main( ) { int n, i, sx, sy; while( … Continue reading →

http://poj.org/problem?id=1852 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { /** * @param args */ static int max(int a,int b) { if(a>b) return a; return b; } static int min(int a,int b) { if(a>b) return b; return a; … Continue reading →

http://poj.org/problem?id=1850 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); String s=in.next(); boolean bb=false; for(int i=0;i< s.length()-1;i++) { if(s.charAt(i)-s.charAt(i+1)>=0) { System.out.println(0); bb=true; break; } } if(bb) System.exit(0); int l=s.length(); long ans=0; … Continue reading →

http://poj.org/problem?id=1845 import java.util.*; public class Main { static long modPow(long a,long n) { long MOD=9901; if (n==1) return a%MOD; long tmp=modPow(a,n>>1); tmp=tmp*tmp%MOD; if ((n&1)==1) tmp=tmp*a%MOD; return tmp; } static long myPow(long a,long n) { if (n==0) return 1; long ans=modPow(a,(n>>1)+1); … Continue reading →

http://poj.org/problem?id=1844 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int sun=in.nextInt(); int sum=0; int i; for(i=1;i< 9999;i++) { sum+=i; if (sum>=sun)break; } if((sum-sun)%2==0) System.out.println(i); else if((sum-sun)%2==1&&i%2==1) System.out.println(i+2); else if((sum-sun)%2==1&&i%2==0) System.out.println(i+1); … Continue reading →

http://poj.org/problem?id=1840 //* @author: import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a1=sc.nextInt(); int a2=sc.nextInt(); int a3=sc.nextInt(); int a4=sc.nextInt(); int a5=sc.nextInt(); System.out.println( hashQuestions(a1,a2, a3,a4,a5)); } /** * @param a1 * @param a2 * @param … Continue reading →

http://poj.org/problem?id=1837 //PKU_1837_Balance_DP(û˼·) #include <iostream> #include <cstring> using namespace std; int C,G; int Pos[22]; int Weight[22]; int Value[22][7505];//������ȫΪ��25���������һͷ�����ʮ��Ϊ25*10*15(�۳�) = 3750 //Ȼ���״̬ƽ��ȫΪ��Ϊ7500��״̬��ȡ7505 int main() { while(cin>>C>>G) { for(int i = 1;i <= C;i++) cin>>Pos[i]; for(int i = 1;i <= G;i++) cin>>Weight[i]; memset(Value,0,sizeof(Value)); … Continue reading →

http://poj.org/problem?id=1836 //* @author: import java.util.Scanner; public class Main{ private int n; private double a[]; int b[],c[],sum[]; public Main(int n,double a[]){ this.n=n; this.a=a; b=new int[n+1]; c=new int[n+1]; sum=new int[n+1]; } public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); double … Continue reading →

http://poj.org/problem?id=1835 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static int x,y,z,p,h; public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n=scanner.nextInt(); int m,s; String f; for (int i=0;i< n ;i++ ){ m=scanner.nextInt(); x=y=z=p=0; h=2; … Continue reading →

http://poj.org/problem?id=1833 //* @author: 82638882@163.com import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws NumberFormatException, IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); int a=Integer.parseInt(in.readLine()); while((a–)!=0) { String[] ss=in.readLine().split(" "); int l=Integer.parseInt(ss[0]); int cnt=Integer.parseInt(ss[1]); int[] arr=new int[l]; … Continue reading →

http://poj.org/problem?id=1832 import java.math.*; import java.util.*; public class Main { static BigInteger[] base = new BigInteger[128]; static void init(){ base[0] = BigInteger.ONE; for (int i=1; i< 128; i++){ base[i] = base[i-1].multiply(BigInteger.valueOf(2)); } } public static void main(String args[]){ init(); Scanner cin … Continue reading →

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 →