Category Archives: poj

http://poj.org/problem?id=2498 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int a=in.nextInt(); int count=1; int[] arr=new int[]{9,3,7}; while((a–)!=0) { String s=in.next(); int total=0; int k=0; int p=0; int t=s.length(); for(int i=t-1;i>-1;i–) … Continue reading →

http://poj.org/problem?id=2497 //* @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()); int cnt=0; while((a–)!=0) { cnt++; String[] ss=in.readLine().split(" "); int t=Integer.parseInt(ss[0]); int w=Integer.parseInt(ss[1]); … Continue reading →

http://poj.org/problem?id=2496 #include <stdio.h> #include <algorithm> using namespace std; int e[100][100]; int n; int p; int a[10000]; int main() { int cas, i, j, l, k, ans; scanf( "%d", &cas ); for( l=1; l<=cas; l++ ) { scanf( "%d", &p ); … Continue reading →

http://poj.org/problem?id=2495 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { /** * @param args */ public static void main(String[] args)throws Exception { // TODO Auto-generated method stub int a,b,c,d,t,i; Scanner cin = new Scanner(System.in); t = cin.nextInt(); for(i=1;i<=t;++i){ … Continue reading →

http://poj.org/problem?id=2492 //* @author: 82638882@163.com import java.io.*; public class Main { static my[] p; 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()); int cnt=0; while((a–)!=0) { cnt++; String[] ss=in.readLine().split(" "); int n=Integer.parseInt(ss[0]); p=new … Continue reading →

http://poj.org/problem?id=2491 #include <stdio.h> #include <string.h> int next[400]; bool ishead[400]; char w1[400][100],w2[400][100]; int main() { int cas, i, n, j, k = 0; scanf( "%d", &cas ); while( cas– ) { scanf( "%d", &n ); n–; for( i=0; i<n; i++ ) … Continue reading →

http://poj.org/problem?id=2489 #include <stdio.h> #include <math.h> #include <memory.h> #include <algorithm> using namespace std; struct point { int x,y; }; struct line { point a,b; int dx,dy; }l[100001]; int n; __int64 ans; inline double crossproduct(point o, point a, point b) { return … Continue reading →

http://poj.org/problem?id=2488 import java.io.PrintWriter; import java.util.Scanner; import java.util.Stack; public class Main { static class Point{ int x ,y; public Point(int x ,int y){ this.x = x; this.y = y; } } static int[][] chessboard = new int[27][27]; static int num = … Continue reading →

http://poj.org/problem?id=2487 import java.io.BufferedInputStream; import java.util.Scanner; /** * *poj2487 * @author NC */ public class Main { private static int partition(int[] array, int low, int high) { int key = array[low]; while (low < high) { while (low < high && … Continue reading →

http://poj.org/problem?id=2486 #include <iostream> #include <list> #include <algorithm> using namespace std; int value[100]; int gone[100][201],m,K,n; int back[100][201]; list<int> e[100]; void merge_back(int bk1[], int bk2[], int bk[], int maxstep ) { int i,j; for( i=0; i<=maxstep; i++ ) { bk[i] = bk2[i]; … Continue reading →

http://poj.org/problem?id=2485 import java.util.Scanner; public class Main{ public static void main(String argvs[]){ int matrix[][]; int Max=65536; int m,n,t,i,j,k,max_len,count,num,min,point=0; int temp1[],temp2[],flag[]; Scanner in=new Scanner(System.in); t=in.nextInt(); for(i=0;i< t;i++){ n=in.nextInt(); matrix=new int[n][n]; flag=new int[n]; for(j=0;j< n;j++) flag[j]=0; flag[0]=1; count=0; num=0; min=Max; max_len=0; temp1=new int[n*(n-1)/2]; … Continue reading →

http://poj.org/problem?id=2479 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { int t; int l; int[] a; String[] s; int[] left; int[] right; int max = 0; int temp; public Main() throws Exception { BufferedReader read = new BufferedReader(new InputStreamReader( System.in)); t … Continue reading →

http://poj.org/problem?id=2477 #include<iostream> #include"stdio.h" using namespace std; struct tree { int l,r; __int64 value; int child; }t[100]; int n,root; bool init() { int i,times[100]; cin>>n; if(n==0) return 0; for(i=1;i<=n;i++) times[i]=0; for(i=1;i<=n;i++) { cin>>t[i].l>>t[i].r; if(t[i].l>0) times[t[i].l]++; if(t[i].r>0) times[t[i].r]++; } for(i=1;i<=n;i++) if(times[i]==0) { … Continue reading →

http://poj.org/problem?id=2473 #include<iostream> #include"algorithm" using namespace std; struct rect { int x1,x2,y1,y2; }r[210]; int n,w,h,n1,n2,m; int x[411],y[411]; void init() { int i; cin>>n>>w>>h; for(i=0;i<n;i++) { cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2; x[i]=r[i].x2; y[i]=r[i].y2; } m=n+1; x[n]=0,y[n]=0; std::sort(x,x+m); std::sort(y,y+m); n1=std::unique_copy(x,x+m,x)-x; n2=std::unique_copy(y,y+m,y)-y; } inline int max(int a,int b) … Continue reading →

http://poj.org/problem?id=2472 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static int N = 100+5; static int n; static double Graph[][] = new double[N][N]; public static void init(){ int i,j; for(i=0;i< N;++i) for(j=0;j< N;++j) Graph[i][j] = 0.0; } … Continue reading →

http://poj.org/problem?id=2470 //* @author ������&lt;hongxp11@163.com&gt; //�t���� buffered import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); while (true) … Continue reading →

http://poj.org/problem?id=2469 #include<iostream> using namespace std; char *suit[]={"Clubs", "Diamonds", "Hearts", "Spades"}; char *value[]={"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"}; int shuffles[101][52],n; int card[52]; void init() { int i,j; cin>>n; for(i=0;i<n;i++) for(j=0;j<52;j++) cin>>shuffles[i][j]; for(i=0;i<52;i++) card[i]=i; } … Continue reading →

http://poj.org/problem?id=2465 #include<iostream> using namespace std; inline int min(int a,int b) { return a<b?a:b; } int dis[112],price[112]; int l,n; void init() { n=0; cin>>l; while(cin>>dis[n]) cin>>price[n++]; price[n]=99999999; dis[n]=l; n++; } int doit() { int i,j,s,temp[212],p; int best[212]; for(i=0;i<201;i++) best[i]=-1; best[100]=0; for(s=dis[0],i=0;i<n;i++) … Continue reading →

http://poj.org/problem?id=2463 #include<iostream> #include"math.h" using namespace std; double k,l,s,w; const double g=9.81; bool init() { cin>>k>>l>>s>>w; return !(k==0&&l==0&&s==0&&w==0); } int calculate() { double v,v0,h,vv; if(s<=l||k==0) { v=sqrt(2*s*g); if(v>10)return -1; else return 1; } else { v0=sqrt(2*l*g); h=(2*w*g+sqrt(4*w*w*g*g+8*k*w*g*l))/(2*k); h+=l; if(h<s)return 0; vv=(2*w*g*s-k*(s-l)*(s-l))/w; … Continue reading →

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

http://poj.org/problem?id=2460 //* @author: ccQ.SuperSupper import java.io.*; class point{ int x,y; } public class Main { static int n; static final int N = 200000+100; static point position[] = new point[N]; public static void main(String[]args) throws Exception{ int i; start(); StreamTokenizer … Continue reading →

http://poj.org/problem?id=2459 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static final int N = 2000+10; static int DP[] = new int[N]; public static void main(String[]args) throws Exception{ int n,F1,F2,Day,i,sum,a,b,j; //Scanner cin = new Scanner(new FileInputStream("input.txt")); Scanner cin … Continue reading →

http://poj.org/problem?id=2458 #include "stdio.h" char map[6][6]; bool sign[6][6]; int flag[6][6]; bool inline inmap( int x, int y ) { return 0<=x&&x<5&&0<=y&&y<5; } int dx[]={ 0,-1, 0, 1}; int dy[]={-1, 0, 1, 0}; int ans; int reach; int visit; void find( int … Continue reading →

http://poj.org/problem?id=2457 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static final int N = 10000+10; static int meat[] = new int[N],pre[] = new int[N],n,K; static Vector Graph[] = new Vector[N]; static Queue que = new LinkedList<Integer>(); static … Continue reading →

http://poj.org/problem?id=2456 #include <stdio.h> #include <algorithm> using namespace std; int pos[100000], n, cc; bool check( int l ) { int i, r, j; for( r=cc-1,i=0,j=1; j<n && r; j++ ) { if( pos[j]-pos[i]>=l ) { r–; i=j; } } return r … Continue reading →

http://poj.org/problem?id=2454 #include"stdio.h" #include"memory.h" #include"algorithm" #include"stdlib.h" using namespace std; typedef pair<int,int> city; city c[180]; int n, k; void init() { int i; scanf( "%d", &n ); k = n; n *= 3; for( i=0; i<n; i++ ) { scanf( "%d", &c[i].first … Continue reading →

http://poj.org/problem?id=2453 import java.util.Scanner; public class Main { /** * 获得一个Integer对应的二进制中1的个数 * @param i * @return sum */ public static int getSum(int i) { int sum = 0; while (i > 0) { i = i & (i – 1); ++sum; … Continue reading →

http://poj.org/problem?id=2452 //* @author: import java.util.*; public class Main { static public void main( String [] str ) throws Exception{ Scanner sc = new Scanner(System.in); int i, j, h, ans; while(sc.hasNext()) { int n=sc.nextInt(); int s[]=new int[n]; for( i=0; i< n; … Continue reading →

http://poj.org/problem?id=2450 //* @author: import java.util.*; import java.math.*; public class Main { static int gcd(int a,int b) { int c; while( (a%=b) != 0 ) { c=b; b=a; a=c; } return b; } static int a,b,c,d,n,m,p,q; static int t[] = new … Continue reading →

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

http://poj.org/problem?id=2447 #include<stdlib.h> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef unsigned __int64 u64; #define MAX 30 #define MAXN 5 u64 len, dig, limit; u64 factor[MAXN]; u64 mod(u64 a, u64 b, u64 n){ if(!a)return 0; else return ( ((a&dig)*b)%n + (mod(a>>len,b,n)<<len)%n )%n; … Continue reading →

http://poj.org/problem?id=2446 #include<iostream> #include<string> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1050; int link[MAXN]; int total; bool vist[33][33]; //用来标记那些位置有洞 bool usedif[MAXN]; bool mat[MAXN][MAXN]; bool Can(int t) { int i; for(i=0;i<total;i++) if(mat[t][i]&&!usedif[i]) { usedif[i]=true; if(link[i]==-1||Can(link[i])) { link[i]=t; return true; … Continue reading →

http://poj.org/problem?id=2445 #include"stdio.h" #include"algorithm" using namespace std; int l[1500][1500],r[1500][1500],u[1500][1500],d[1500][1500],lu[1500][1500],rd[1500][1500]; int n; inline int max(int a,int b) { return a>b?a:b; } inline int min(int a,int b) { return a<b?a:b; } bool init() { int i,j,m,k,a,b; char c; if(scanf("%d",&n)!=1) return 0; scanf("%d",&m); for(i=0;i<n;i++) … Continue reading →

http://poj.org/problem?id=2443 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class Set{ void init(){ for(int i=0;i< 35;++i) state[i] = 0; } void get_int(int cnt){ int k = cnt/30; int posi = cnt%30; state[k]|=dir[posi]; } int dir[] = {1,1<<1,1<<2,1<<3,1<<4,1<<5,1<<6,1<<7,1<<8,1<<9,1<<10,1<<11,1<<12,1<<13,1<<14, 1<<15,1<<16,1<<17,1<<18,1<<19,1<<20,1<<21,1<<22,1<<23,1<<24,1<<25,1<<26,1<<27, 1<<28,1<<29,1<<30,1<<31}; int state[] … Continue reading →

http://poj.org/problem?id=2441 //* @author: /* ����: N��ţ��M�������(barn)��ÿ��ţ���м����Լ�ϲ����barn��Ҫ��Ϊÿ��ţ����һ��barn�� ʹ��ÿ��ţ��ֵ���barn�����Լ�ϲ���ģ���ÿ��barn�v�ֻ������һ��ţ����Ϸ��ķ��䷽��������N,M<=20�� ����: ��һ����N��M(1<=N<=20, 1<=M<=20); ����4��N��: ��i�еĵ�һ�������ǵ�i��ţϲ����barn��,���������ǵ�i��ţϲ����barn���(1<=i<=N) ���: ���䷽�������� */ import java.util.*; public class Main { static final int N=20+2; static final int M=1<< 20+1; public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n, … Continue reading →

http://poj.org/problem?id=2440 import java.util.Scanner; public class Main { public static int[][] org; public static int[][] m; public static int[][] f = new int[4][1]; public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext()) { int n = cin.nextInt(); if(test(n)) … Continue reading →

http://poj.org/problem?id=2437 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class POOL implements Comparable{ int left,right; public int compareTo(Object oo){ POOL temp = (POOL) oo; if(temp.left< this.left) return 1; return -1; } } public class Main { static final int N = … Continue reading →

http://poj.org/problem?id=2436 //* @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); String[] ss=in.readLine().split(" "); int n=Integer.parseInt(ss[0]); int d=Integer.parseInt(ss[1]); int k=Integer.parseInt(ss[2]); int[] q=new int[n]; for(int i=0;i< n;i++) { … Continue reading →

http://poj.org/problem?id=2435 #include <stdio.h> #include <queue> using namespace std; typedef pair<int,int> point; int dx[] = { 0, 1,-1, 0}; int dy[] = { 1, 0, 0,-1}; char way[] = { ‘-‘,’|’,’|’,’-‘}; char to[] = { ‘E’,’S’,’N’,’W’}; int n,m,bx,by,ex,ey; bool sign[100][100]; char … Continue reading →

http://poj.org/problem?id=2431 #include<iostream> #include"algorithm" using namespace std; const int size=10010; struct stop { int f,x; }p[size]; int n,l,h; bool cmp(stop a,stop b) { return a.x>b.x; } void init() { int i; cin>>n; for(i=0;i<n;i++) { cin>>p[i].x>>p[i].f; } cin>>l>>h; p[n+1].x=l;p[n+1].f=0; p[n].x=0;p[n].f=0; n+=2; std::sort(p,p+n,cmp); … Continue reading →

http://poj.org/problem?id=2430 #include<iostream> #include"algorithm" using namespace std; const int size=1010; int ans[size][size][4]; int best[size][size]; int n,m,b,nn; enum{both,up,down,sep}; const int inf=99999999; struct point { int y; int x; int s; }pt[size],p[size]; bool cmp(point a,point b) { return a.x<b.x; } void init() { … Continue reading →

http://poj.org/problem?id=2428 #include<iostream> #include"stdio.h" #include"math.h" using namespace std; struct point { double x,y,z; }p1[110],p2[110],p3[110]; int n,m; double best[110][110]; double cross(point a,point b,point c) { b.x-=a.x;b.y-=a.y;b.z-=a.z; c.x-=a.x;c.y-=a.y;c.z-=a.z; double s1,s2,s3; s1=b.y*c.z-b.z*c.y; s2=b.z*c.x-b.x*c.z; s3=b.x*c.y-b.y*c.x; return sqrt(s1*s1+s2*s2+s3*s3); } int init(void) { int i;double s1,s2; cin>>n; … Continue reading →

http://poj.org/problem?id=2427 //* @author import java.util.*; import java.math.*; public class Main { static BigInteger p1,p2,p3,q1,q2,q3,a1,a2,a0,h1,h2,g1,g2,p,q; static int nn; static void solve(){ p2=BigInteger.ONE; p1=BigInteger.ZERO; q2=BigInteger.ZERO; q1=BigInteger.ONE; a1=BigInteger.valueOf((long)Math.sqrt(nn)); a0=BigInteger.valueOf((long)Math.sqrt(nn)); g1=BigInteger.ZERO;h1=BigInteger.ONE; BigInteger n0=BigInteger.valueOf(nn); while(true){ g2=a1.multiply(h1).subtract(g1); h2=(n0.subtract(g2.multiply(g2))).divide(h1); a2=g2.add(a0).divide(h2); p=p2.multiply(a1).add(p1); q=q2.multiply(a1).add(q1); if(p.multiply(p).subtract(n0.multiply(q.multiply(q))).compareTo(BigInteger.ONE)==0) return ; a1=a2; g1=g2; … Continue reading →

http://poj.org/problem?id=2425 #include <vector> #include <iostream> using namespace std; vector<int> edges[1000]; int N,M,GS[1000],ans; int DFS(int n) /* 典型求 SG 函数的办法 */ { if(GS[n]!=-1) return GS[n]; bool used[1000]; memset(used,0,sizeof(used)); for(int i=0;i<edges[n].size();i++) { used[DFS(edges[n][i])]=true; } int i=0; while(used[i]) i++; return GS[n]=i; } int … Continue reading →

http://poj.org/problem?id=2424 #include"queue" #include"stdio.h" using namespace std; struct node { int time; int dinners; }; int a[3],ans; queue<node> have[3]; bool init() { char c,t; int u[3],t1,t2,i; node nd,nd1; //cin>>a[0]>>a[1]>>a[2]; scanf("%d%d%d",&a[0],&a[1],&a[2]); if(a[0]==0&&a[1]==0&&a[2]==0) return 0; for(i=0;i<3;i++) { while(!have[i].empty()) have[i].pop(); } ans=0; u[0]=0,u[1]=0,u[2]=0; while(1) … Continue reading →

http://poj.org/problem?id=2421 //* @author: 82638882@163.com import java.util.Scanner; public class Main { static int[] bin; public static void main(String[] args) { Scanner in=new Scanner(System.in); int a=in.nextInt(); int[][] p=new int[a][a]; for(int i=0;i< a;i++) for(int j=0;j< a;j++) p[i][j]=in.nextInt(); bin=new int[a]; for(int i=0;i< a;i++) bin[i]=i; … Continue reading →

http://poj.org/problem?id=2420 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; import java.math.*; class Point{ double x,y; } public class Main { static int n; static final int N = 100+10; static Point point[] = new Point[N]; static void start(){ for(int i=0;i< N;++i) … Continue reading →

http://poj.org/problem?id=2419 //* @author: 82638882@163.com import java.io.*; import java.util.Arrays; public class Main { 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(" "); int a=Integer.parseInt(ss[0]); int b=Integer.parseInt(ss[1]); boolean[][] p=new boolean[a][b]; my[] p2=new my[a]; … Continue reading →

http://poj.org/problem?id=2418 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static class TreeNode{ private String species; private TreeNode left; private TreeNode right; private int count; } public static class Tree{ private int total; private TreeNode root=new TreeNode(); public … Continue reading →

http://poj.org/problem?id=2415 #include<iostream> #include"queue" #include"algorithm" using namespace std; char edge[51][51]; int sign[51][51][51],n,p1,p2,p3; struct node { int p[3]; int steps; }; queue<node> q; bool init() { int i,j,k; cin>>n>>p1>>p2>>p3; if(n==0)return 0; for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>edge[i][j]; for(i=0;i<n;i++) for(j=0;j<n;j++) for(k=0;k<n;k++) sign[i][j][k]=0; while(!q.empty()) q.pop(); return 1; … Continue reading →