Author Archives: toad, die

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 →

http://poj.org/problem?id=2414 #include"stdio.h" #include"string.h" int best[1024][26]; int min[1024]; char m[1024][1001]; char answer[1001]; int n,l; bool init() { int i; scanf("%d %d",&n,&l); if(n==0&&l==0) return 0; for(i=0;i<n;i++) scanf("%s",m[i]); return 1; } inline int min_int(int a,int b) { return a<b?a:b; } void doit(int k) … Continue reading →

http://poj.org/problem?id=2413 import java.io.BufferedInputStream; import java.math.BigInteger; import java.util.Scanner; /** * * poj2413 * @author NC */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); while (scan.hasNext()) { BigInteger a = scan.nextBigInteger(); BigInteger b … Continue reading →

http://poj.org/problem?id=2411 import java.util.Scanner; import java.util.Arrays; public class Main{ /* f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出） 的方案数。用DFS进行状态转移。*/ static long f[][]=new long[12][2048]; static int n, m; static void dfs(int i, int j, int jj, int s)//j是初始状态，jj是目标状态.s表示列数 { if (s == m)//把i行m列放好 f[i + 1][jj] += f[i][j];//等于I+1行被占去的格子的2进制为JJ应该可以多放f[i][j]的方略 else … Continue reading →

http://poj.org/problem?id=2407 import java.util.Scanner; import java.util.Arrays; public class Main { // ���1��n-1��n���ʵ���ĸ���,�������� static int eular(int n) { int ret = 1,i; for (i = 2;i * i <= n;i++) if (n % i == 0) { n /= i; ret *= … Continue reading →

http://poj.org/problem?id=2406 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 1000000 char substr[MAXN + 2]; int sublen; int next[MAXN + 1]; void getNext() { next[1] = 0; int i, j = 0; for (i = 2; i <= … Continue reading →

http://poj.org/problem?id=2405 //* @author ������&lt;hongxp11@163.com&gt; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(true) { int D = in.nextInt(); int V = in.nextInt(); if(D==0 && V==0) break; //double v1 = (d * … Continue reading →

http://poj.org/problem?id=2403 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String[] fLine = cin.nextLine().split(" "); int kwNum = Integer.valueOf(fLine[0]).intValue(); int descNum = Integer.valueOf(fLine[1]).intValue(); HashMap hm = new HashMap(); for(int i = 0; … Continue reading →

http://poj.org/problem?id=2402 #include<iostream> #include<cmath> using namespace std; //int a[20]={9,9,90,90,900,900,9000,9000,90000,90000,900000,900000,9000000,9000000,90000000};//x位上的回文数个数为f(x)=9*10^((x+1)/2); __int64 b[19]={0,9,18,108,198,1098,1998,10998,19998,109998,199998,1099998,1999998, 10999998,19999998,109999998,199999998,1099999998,1999999998};//前x位上的回文数总个数 int c[10]; int main() { __int64 i,j,n,d,k,l; double temp; while(scanf("%I64d",&i)!=EOF&&i) { for(j=0;;j++) { if(i<=b[j]) break; } //j回文数的位数 n=b[j-1];//1…n-1 数的回文数总数 d=i-n-1; temp=(j+1)/2-1; k=(int)pow(10.0,temp); k+=d; l=k; if(j%2==1) l=k/10; for(j=0;l>0;j++) { c[j]=l%10;//前半部分和后半部分对称 … Continue reading →

http://poj.org/problem?id=2400 #include<iostream> #include"string.h" #include"stdio.h" using namespace std; #define valuetype int #define null 0 const int size=20; bool maxmatch(int n,int m,bool w[size][size],int *p,bool *setn,bool *setm) { int p_n[size]; int p_m[size]; bool sign[size]; int q[size],from[size],s,t; int i,j,link,now,h; for(i=0;i<n;i++)p_n[i]=-1; for(j=0;j<m;j++)p_m[j]=-1; for(i=0;i<n;i++) if(p_n[i]==-1) { … Continue reading →

http://poj.org/problem?id=2398 /* @author:����acmilan_fan@yahoo.cn */ import java.io.*; import java.util.Map; import java.util.TreeMap; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n, m, y1, y2, i, t; String s; String[] ss; Point p,p2; … Continue reading →

http://poj.org/problem?id=2395 /* @author: */ import java.util.Scanner; public class Main{ public static void main(String args[]) { int p[][]=new int[2001][2001]; int n,m,i,j,k; int dis[]=new int[2001]; int u,v,l; int ne[]=new int[2001]; Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); int max=0; for(i=0;i< n;i++) for(j=0;j< n;j++) p[i][j]=1000000001; … Continue reading →

http://poj.org/problem?id=2394 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; import java.math.*; import java.text.*; public class Main { public static int mat[][]=new int[505][505]; public static int d[]=new int[505]; public static void main(String args[]) throws Exception { Scanner cin=new Scanner(System.in); int F,P,C,M; int … Continue reading →

http://poj.org/problem?id=2393 import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int m = n; int s = cin.nextInt(); Node[] node = new Node[n]; int i = 0; long sum … Continue reading →

http://poj.org/problem?id=2392 //* @author: import java.util.Scanner; import java.util.Arrays; public class Main{ private int k; private Block block[]; private boolean access[]=new boolean[400001]; public Main(int k,Block block[]){ this.k=k; this.block=block; } private int doIt(){ int maxs=0; access[0]=true; Arrays.sort(block); for(int i=0;i< k;i++) { int t=0; … Continue reading →

http://poj.org/problem?id=2390 import java.io.BufferedInputStream; import java.math.BigInteger; import java.util.Scanner; /** * * Poj2390 * @author NC */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); if (scan.hasNext()) { int r = scan.nextInt(); long m … Continue reading →

http://poj.org/problem?id=2389 import java.io.BufferedInputStream; import java.math.BigInteger; import java.util.Scanner; /** * * poj2389 * @author NC */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); if (scan.hasNext()) { BigInteger a = scan.nextBigInteger(); BigInteger b … Continue reading →

http://poj.org/problem?id=2388 import java.io.BufferedInputStream; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); if (scan.hasNext()) { int n = scan.nextInt(); int[] array = new int[n + 1]; for (int i = 0; i … Continue reading →

http://poj.org/problem?id=2387 import java.util.*; public class Main{ public static void main(String args[]){ Scanner in=new Scanner(System.in); int c=0; int t=in.nextInt();//����˳�����WA��N�Σ������������⣡ int n=in.nextInt(); int dist[]=new int[n+1];//��������ȷ�������С������RE��N�Σ� int[][] w=new int[n+1][n+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ w[i][j]=Integer.MAX_VALUE; } } for(int i=0;i< t;i++){//����}�㼰֮����� int sn=in.nextInt(); int en=in.nextInt(); … Continue reading →

http://poj.org/problem?id=2386 //* @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(); int count=0; int[][] arr=new int[a+2][b+2]; for(int i=1;i<=a;i++){ String s=in.next(); for(int j=1;j<=b;j++) arr[i][j]=s.charAt(j-1); } for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) … Continue reading →

http://poj.org/problem?id=2385 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { /** * @param args */ public static int max(int x,int y) { if(x>y) return x; return y; } public static void main(String[] args) throws Exception{ // TODO Auto-generated … Continue reading →

http://poj.org/problem?id=2383 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; import java.math.*; class circle{ int x,y,r,color; } class Set{ int n,m; int next[][] = new int[1010][1010]; void init(int _n,int _m){ for(n=0;n<=_n;++n) for(m=0;m<=_m;++m) next[n][m] = m; n = _n; m = _m; } … Continue reading →

http://poj.org/problem?id=2381 #include <stdio.h> #include <string.h> char b[16000002]; int main() { unsigned long a,m,c,r; memset(b,0,sizeof(b)); scanf("%lu%lu%lu%lu",&a,&c,&m,&r); while(1) { r=(a*r+c)%m; if(b[r]) break; else b[r]=1; } long i,max=0,last=0; for(i=0;i<16000002;i++) if(b[i]) break; last=i++; for(;i<16000002;i++) { if(b[i]) { // printf("%lu ",i); if(i-last>max) { max=i-last; } … Continue reading →

http://poj.org/problem?id=2380 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<string.h> #include<math.h> #define INF 30000 #define NMAX 500003 typedef struct { long q,s,v; }data; data a[NMAX]; data b[NMAX]; long y[NMAX]; long x[NMAX]; long N; int cmp(const void *a,const void *b) { if(((data*)a)->s==((data*)b)->s) return ((data*)a)->q-((data*)b)->q; else return … Continue reading →

http://poj.org/problem?id=2377 //* @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)); int n = sc.nextInt(); int m = sc.nextInt(); int[] mind = new int[n]; boolean[] reached = … Continue reading →

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

http://poj.org/problem?id=2372 #include <stdio.h> #include <string.h> char w[1000], *symbol="=+-*/0123456789n"; bool check_comment(int &s) { do { while( w[s] && w[s] != ‘*’ ) s++; if( !w[s] || !w[ s+1 ] ) return false; else if( w[ ++s ] == ‘)’ ) return … Continue reading →

http://poj.org/problem?id=2371 import java.util.Arrays; import java.util.Scanner; public class Main { public static void quickSort(int[] data, int s, int t) { int i = s+1; int j = t; int x = data[s]; while (i <= j) { while (i <= j … Continue reading →

http://poj.org/problem?id=2370 //* @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(),t=0,i; int[] b=new int[a]; for(i=0;i< a;i++) b[i]=in.nextInt(); a/=2; Arrays.sort(b); for(i=0;i<=a;i++) t+=b[i]/2+1; System.out.println(t); } }

http://poj.org/problem?id=2367 import java.math.BigInteger; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * * Accepted. BigInteger is used here. * * */ public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int[][] … Continue reading →

http://poj.org/problem?id=2366 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static double N = 10000.0; public static void main(String []args) throws Exception{ double temp; int i,j,n,m,t=1; Map first = new HashMap(); StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); … Continue reading →

http://poj.org/problem?id=2365 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n=scanner.nextInt(); double r=scanner.nextDouble(); double[] x=new double[n]; double[] y=new double[n]; for (int i=0;i< n ;i++ ){ x[i]=scanner.nextDouble(); y[i]=scanner.nextDouble(); } … Continue reading →

http://poj.org/problem?id=2363 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int c=scanner.nextInt(); int n,sm; for (int l=0;l< c ;l++ ){ n=scanner.nextInt(); sm=4*n+2; for (int i=1;i<=n ;i++ ){ for (int … Continue reading →