Author Archives: toad, die

http://poj.org/problem?id=2711 #include <vector> #include <string.h> #include <math.h> #include <stdio.h> #define min(a,b) (((a)<(b))?(a):(b)) using namespace std; class ff { public: typedef int type; // ��Ȩ���� enum { size = 810 }; // �����ģ enum { max = ( 1<<30 ) }; … Continue reading →

http://poj.org/problem?id=2710 //* @author: ccQ.SuperSupper import java.util.*; import java.math.*; public class Main { public static void main(String []args) throws Exception{ int t,cs=1,left,right,i,j; BigInteger a,b,seven; String str1,str2; seven = BigInteger.valueOf(1); for(i=0;i< 10000;++i) seven = seven.multiply(BigInteger.valueOf(7)); Scanner cin = new Scanner(System.in); t = … Continue reading →

http://poj.org/problem?id=2707 //* @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 a,b,c,d; int z,nz; while (true){ a=scanner.nextInt(); b=scanner.nextInt(); c=scanner.nextInt(); d=scanner.nextInt(); if (a+b+c+d==0){ break; } if (a*d>b*c){ z=getN(a,c); } else{ … Continue reading →

http://poj.org/problem?id=2704 //* @author: 82638882@163.com import java.io.*; public class Main { static int[][] p; static int a; static long[][] w; public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); while(true) { a=Integer.parseInt(in.readLine()); if(a==-1) break; p=new int[a][a]; … Continue reading →

http://poj.org/problem?id=2696 //* @author: 82638882@163.com import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int k=in.nextInt(); while((k–)!=0) { int[] arr=new int[9]; for(int i=0;i< 9;i++) arr[i]=in.nextInt(); int[] y=new int[arr[8]+1]; y[0]=arr[0]; y[1]=arr[1]; y[2]=arr[2]; for(int i=3;i<=arr[8];i++) f(y,i,arr); System.out.println(y[arr[8]]); … Continue reading →

http://poj.org/problem?id=2689 import java.util.Scanner; public class Main { final static int MAXVALUE = (int) Math.sqrt(Integer.MAX_VALUE) + 1; public static void main(String[] args) { int k, l, u, tt, index; boolean hasFlg; int a, b, aa, bb; int[] num = new int[MAXVALUE]; … Continue reading →

http://poj.org/problem?id=2685 import java.io.BufferedInputStream; import java.util.Scanner; /** * * poj2685 * @author NC */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); if (scan.hasNext()) { int n = scan.nextInt(); scan.nextLine(); for (int i … Continue reading →

http://poj.org/problem?id=2681 //* @author: 82638882@163.com import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int a=in.nextInt(); in.nextLine(); int u=0; while((a–)!=0) { u++; int[] p=new int[26]; String s1=in.nextLine(); String s2=in.nextLine(); for(int i=0;i< s1.length();i++) { int t=s1.charAt(i)-‘a’; p[t]++; … Continue reading →

http://poj.org/problem?id=2680 import java.io.*; import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { int n; BigInteger two,ans; Scanner cin = new Scanner (System.in); while(cin.hasNext()) { n = cin.nextInt(); two = BigInteger.valueOf(2); ans = two; if(n%2==0) { … Continue reading →

http://poj.org/problem?id=2679 #include <stdio.h> #include <vector> #include <memory.h> using namespace std; const int size = 1110; struct edge { int len; int fee; edge *next; }; edge e[size][size]; edge *link[size]; bool sign[size]; int m, n, begin, end; int fee[size]; void search( … Continue reading →

http://poj.org/problem?id=2678 #include<iostream> #include"stdio.h" #include"math.h" #include<vector> #include<algorithm> using namespace std; const double eps=1e-8; const int size = 1010; //////////////////////////////// typedef double Type;/*????????*/ //////////////////////////////// struct point { Type x,y; point(){x=y=0;} point(Type x,Type y):x(x),y(y){;} bool operator==(point &a){return x==a.x&&y==a.y;} }; //???? inline Type cheng(point … Continue reading →

http://poj.org/problem?id=2677 #include <stdio.h> #include <memory.h> #include <math.h> struct point { double x, y; }; double dis( point &a, point &b ) { return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ); } double s[1010][1010]; point p[1010]; int main( ) { int n, i, … Continue reading →

http://poj.org/problem?id=2676 //* @author: 82638882@163.com import java.io.*; class Main { public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); int cnt=Integer.parseInt(in.readLine()); while((cnt–)!=0) { int[][] p=new int[9][9]; for(int i=0;i< 9;i++) { for(int j=0;j< 9;j++) p[i][j]=in.read()-‘0’; in.readLine(); } … Continue reading →

http://poj.org/problem?id=2675 #include <stdio.h> #include <algorithm> #include <string.h> #include <math.h> const double eps = 1e-6; using namespace std; double v[70000]; int id[70000], s[70000], l[70000]; bool cmp( int a, int b ) { return v[a]*l[b] < v[b]*l[a]; } int main( ) { … Continue reading →

http://poj.org/problem?id=2673 /* @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 total,per,t,max; total=sc.nextInt(); per=sc.nextInt(); t=sc.nextInt(); max=total; while((t–)!=0) { int dis,speed,fir,sum; dis=sc.nextInt(); speed=sc.nextInt(); if(speed==0) continue; if(speed>=dis) max=0; fir=dis/speed; if(dis%speed==0) fir–; sum=fir+(total-fir)/2; … Continue reading →

http://poj.org/problem?id=2672 #include <stdio.h> #include <string.h> #include <memory.h> //�����ͼ���ƥ�䣬 //����ƥ�����wΪn*m�ڽӾ���,p������X( |X|=n )ƥ��Ķ����� #define null 0 const int size=30; bool maxmatch(int n,int m,bool w[][size],int *p) { 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) { for(j=0;j<m;j++)sign[j]=0; … Continue reading →

http://poj.org/problem?id=2669 #include <stdio.h> #include <memory.h> #include <vector> #include <algorithm> using namespace std; double dis[100][100]; int n, m; bool e[100][100]; int son[100]; double len[100]; bool sign [100]; int v2[100], v[100], vn2, vn; int calc2( int a, int f ) { int … Continue reading →

http://poj.org/problem?id=2665 //* @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 s,n,tn; while (true){ s=scanner.nextInt(); n=scanner.nextInt(); if (s==0&&n==0){ break; } tn=s+1; for (int i=0;i< n ;i++ ){ tn=tn+scanner.nextInt()-scanner.nextInt()-1; } … Continue reading →

http://poj.org/problem?id=2664 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(true) { int a=in.nextInt(); if(a==0) break; boolean bb=true; int b=in.nextInt(); HashSet< Integer> hs=new HashSet< Integer>(); while((a–)!=0) hs.add(in.nextInt()); while((b–)!=0) { int c=in.nextInt(); … Continue reading →

http://poj.org/problem?id=2663 import java.util.Scanner; import java.util.Arrays; public class Main{ static long S(int n) //S(n)=3*S(n-2)+2*(S(n-4)+S(n-6)+…+S(2)+S(0)) { long s; int i; if(n==0)return 1; else { s=3*S(n-2); for(i=n-4;i>=0;i-=2) { s+=2*S(i); } return s; } } public static void main(String args[]){ Scanner sc=new Scanner(System.in); int … Continue reading →

http://poj.org/problem?id=2661 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(true) { int a=in.nextInt(); if(a==0) break; a-=1960; a/=10; a=(int)Math.pow(2, a+2); double k=0; int n=2; while(k< a) { k+=Math.log(n)/Math.log(2); n++; } System.out.println(n-2); … Continue reading →

http://poj.org/problem?id=2660 /* @author: */ import java.util.Scanner; import java.util.Arrays; public class Main{ static double lfabs(double x) { return x>0?x:-x; } public static void main(String args[]){ Scanner sc=new Scanner(System.in); double sat[][]=new double[100][3]; double xa,xb,ya,yb,za,zb,s,s1,s2,s3,angle,r=20000/3.14159265; int k,m,i,j,flag=0,num; while(sc.hasNext()) { k=sc.nextInt(); m=sc.nextInt(); if(k==0&&m==0) break; … Continue reading →

http://poj.org/problem?id=2656 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int caseNum = 0; int unhappyDay, unhappyValue; int studyTime = 0; while(true) { unhappyDay = 0; unhappyValue = 0; caseNum = cin.nextInt(); … Continue reading →

http://poj.org/problem?id=2651 //* @author: import java.util.*; public class Main { static double t=0; static double e( double s, int k) { if( k == 0 ) return s; else { double temp = e( 2*s, k-1 ); double h = s/temp; … Continue reading →

http://poj.org/problem?id=2649 //* @author mekarlos@gmail.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Hashtable; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Hashtable< Integer,Integer> table=new Hashtable< Integer,Integer>(); Hashtable< Integer,Integer> table2=new Hashtable< Integer,Integer>(); BufferedReader stdin=new … Continue reading →

http://poj.org/problem?id=2646 //* @author: 82638882@163.com import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(true) { int a=in.nextInt(); if(a==0) break; double[] d=new double[a]; double total=0; for(int i=0;i< a;i++) { d[i]=in.nextDouble(); total+=d[i]; } double avg=total/a; long … Continue reading →

http://poj.org/problem?id=2645 //* @author: import java.util.*; import java.io.*; import java.lang.reflect.Array; public class Main { static public void main( String [] string ) throws Exception{ Scanner cin = new Scanner( System.in ); long p, q; while( true ) { p = cin.nextLong(); … Continue reading →

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

http://poj.org/problem?id=2641 //* @author: import java.util.*; public class Main { static public void main( String [] str ){ Scanner sc = new Scanner(System.in); while( sc.hasNext()) { int a=sc.nextInt(); int b=sc.nextInt(); int s=sc.nextInt(); int m=sc.nextInt(); int n=sc.nextInt(); if( a == 0 ) … Continue reading →

http://poj.org/problem?id=2640 import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); double x[]=new double[21],sum; int n,flag; int i,j; while(sc.hasNext()) { n=sc.nextInt(); if(n==0) break; for(i=0;i< n;i++) x[i]=sc.nextDouble(); Arrays.sort(x,0,n); sum=0;flag=0; for(i=0;i< n-1;i++) { sum+=x[i]; for(j=i+1;j< n;j++) if(x[j]<=sum) … Continue reading →

http://poj.org/problem?id=2636 //* @author mekarlos@gmail.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(stdin.readLine()),k,aux; StringTokenizer tokens; while((n–)!=0){ tokens=new StringTokenizer(stdin.readLine()); k=Integer.parseInt(tokens.nextToken()); aux=-k+1; while((k–)!=0)aux+=Integer.parseInt(tokens.nextToken()); System.out.println(aux); } … Continue reading →

http://poj.org/problem?id=2635 //* @author import java.io.*; import java.util.*; import java.math.*; public class Main { static boolean h[]; public static void main(String[] args) { int m,i,j=2; h=new boolean[1000005]; BigInteger n,p,q,nn; for(i=1;i<=1000001;i++) h[i]=true; for(i=2;i<=1000001;i+=2) h[i]=false; h[1]=false;h[2]=true; for(i=3;i<=1000;i+=2) { if(h[i]==true) { j=2; while(i*j<=1000000) { … Continue reading →

http://poj.org/problem?id=2632 import java.util.Scanner; enum Direction { N, S, W, E } class Robot { int id; int x; int y; Direction direction; public Robot(int i, int x, int y, String direction) { this.id = i; this.x = x; this.y = … Continue reading →

http://poj.org/problem?id=2629 //* @author mekarlos@gmail.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in)); String s=""; int[] l1,l2; while(stdin.ready()){ l1=new int[26];l2=new int[26]; s=stdin.readLine().trim(); for(int i=0;i< s.length();i++){ l1[(int)(s.charAt(i)-‘a’)]++; } … Continue reading →

http://poj.org/problem?id=2624 /* @author: */ import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String args[]) { Scanner sc=new Scanner(System.in); double x1,y1,x2,y2,x3,y3,x4,y4,x5=0,y5=0; while(sc.hasNext()) { x1=sc.nextDouble(); y1=sc.nextDouble(); x2=sc.nextDouble(); y2=sc.nextDouble(); x3=sc.nextDouble(); y3=sc.nextDouble(); x4=sc.nextDouble(); y4=sc.nextDouble(); if(x1==x3&&y1==y3) { x5=x4-x3+x2; y5=y4-y3+y2; } else if(x1==x4&&y1==y4) { … Continue reading →

http://poj.org/problem?id=2623 //* @author: 82638882@163.com import java.io.*; import java.util.*; public class Main {//1979 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[] arr=new int[a+1]; for(int i=1;i<=a;i++) arr[i]=Integer.parseInt(in.readLine()); Arrays.sort(arr); double t; if(a%2==0)t=arr[a/2]/2.0+arr[a/2+1]/2.0; else t=arr[(a+1)/2]; … Continue reading →

http://poj.org/problem?id=2619 /* @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 a,b; a=sc.nextInt(); b=sc.nextInt(); int p1,p2,p3,d1,d2,d3; p1=(int)Math.sqrt(a*1.0); if(p1*p1< a) p1++; d1=(int)Math.sqrt(b*1.0); if(d1*d1< b) d1++; int v1=(p1-1)*(p1-1); int v2=(d1-1)*(d1-1); p2=(a-v1+1)/2; d2=(b-v2+1)/2; … Continue reading →

http://poj.org/problem?id=2613 /* @author: */ import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int a[]=new int[3],b[]=new int[3],c[]=new int[3],d[]=new int[3],p,q,r,s; int maxn; double sum; int i,flag; maxn=100000001; while(sc.hasNext()) { p=sc.nextInt(); q=sc.nextInt(); r=sc.nextInt(); s=sc.nextInt(); a[0]=p;a[1]=s;a[2]=r-s;b[0]=r;b[1]=q;b[2]=p-q; for(i=0;i< 3;i++)c[i]=d[i]=2; sum=1;flag=1; … Continue reading →

http://poj.org/problem?id=2612 #include<iostream> #include<string> #include<cstdlib> using namespace std; int main() { char mine[15][15]; char touch[15][15]; char board[15][15]; int i,j,n,num=0; bool flag=false; scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",mine[i]); for(i=0;i<n;i++) scanf("%s",touch[i]); for(i=0;i<n;i++) for(j=0;j<n;j++) { if(touch[i][j]==’x’) { if(mine[i][j]==’*’) { flag=true; board[i][j]=’*’; } else if(mine[i][j]==’.’) { if((j-1)>=0&&mine[i][j-1]==’*’) num++; … Continue reading →

http://poj.org/problem?id=2610 //* @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); double x1 = in.nextDouble(); double y1 = in.nextDouble(); double x2 = in.nextDouble(); double y2 = in.nextDouble(); //double r1 = 0; … Continue reading →

http://poj.org/problem?id=2608 #include<iostream> #include<string> #include<map> #include<cstdlib> #include<algorithm> using namespace std; char ss[21]; int a[21]; int main() { map<char,int>m; m[‘B’]=1; m[‘A’]=0; m[‘F’]=1; m[‘E’]=0; m[‘P’]=1; m[‘I’]=0; m[‘V’]=1; m[‘O’]=0; m[‘C’]=2; m[‘U’]=0; m[‘G’]=2; m[‘H’]=0; m[‘J’]=2; m[‘W’]=0; m[‘K’]=2; m[‘Y’]=0; m[‘Q’]=2; m[‘S’]=2; m[‘Z’]=2; m[‘X’]=2; m[‘D’]=3; m[‘T’]=3; m[‘L’]=4; … Continue reading →

http://poj.org/problem?id=2607 #include <cstdio> const int M = 505, INF = 1000000000; int mp[M][M], n, m, f[105]; int main () { int i, j, k, x, y, d, u, ans, Max, Min; while ( scanf("%d %d", &m, &n) != EOF ) … Continue reading →

http://poj.org/problem?id=2606 //* @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[] arrx=new int[a]; int[] arry=new int[a]; for(int i=0;i< a;i++) { arrx[i]=in.nextInt(); arry[i]=in.nextInt(); } int max=0; for(int i=0;i< a-2;i++) { … Continue reading →

http://poj.org/problem?id=2604 #include <iostream> #include <string> #include <vector> using namespace std; typedef vector<string>::size_type VST; vector<string> v; char Stack[1000]; int pos[1000]; int vpos[1000]; int top = 0; void process() { bool bEnd; for (VST i = 0;i < v.size();i++) { if (v[i].empty()) … Continue reading →

http://poj.org/problem?id=2603 #include<stdio.h> #include<stdlib.h> #include<string.h> int main() { int x,i,n=10;int a[10002];a[1]=0;memset(a,0,sizeof(a)); while(n–) { scanf("%d",&x); for(i=2;x!=1;i++) { while(x%i==0&&x!=1) { a[i]++;x/=i; } if(x==1) break; } } x=1; for(i=2;i<10000;i++) { if(a[i]!=0) { x=x*(1+a[i])%10; } } printf("%dn",x); return 0; }

http://poj.org/problem?id=2602 import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedInputStream read = new BufferedInputStream(System.in); byte[] b = new byte[5000007]; read.read(b); String s = ""; int index = … Continue reading →

http://poj.org/problem?id=2601 //* @author: 82638882@163.com import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); double a0=in.nextDouble(); double an=in.nextDouble(); double total=n*a0+an; double sum=0; int u=n; for(int i=0;i< n;i++,u–) sum+=in.nextDouble()*u; double ans=(total-sum*2)/(n+1); System.out.printf("%.2f",ans); } }

http://poj.org/problem?id=2600 #include <stdio.h> #include <math.h> const double eps = 1e-4; const double pi = acos(-1.0); struct TPoint { double x, y; }p[60], a[60]; double angle[60]; double multi(TPoint p1, TPoint p2, TPoint p0) { return (p1.x – p0.x) * (p2.y – … Continue reading →

http://poj.org/problem?id=2599 #include <iostream> #include <cstring> using namespace std; int N,K; bool map[1010][1010]; bool visited[1010]; bool dfs(int n,int step) { bool z = false; visited[n] = true; bool HasPath = false; for(int i = 1;i <= N;i++) { if(!visited[i] && map[n][i]) … Continue reading →

http://poj.org/problem?id=2595 #include <stdio.h> #include <math.h> #include <vector> #include <algorithm> using namespace std; ///////////////////////// #define Type double /*�������*/ ///////////////////////// struct point {Type x,y; point(){x=y=0;} point(Type &x,Type &y):x(x),y(y){;} bool operator==(point &a){return x==a.x&&y==a.y;} }; struct line {point a,b; line(){;} line(point &x,point &y):a(x),b(y) {;} … Continue reading →