Category Archives: poj

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 →

http://poj.org/problem?id=2594 #include <stdio.h> #include <memory.h> #include <vector> using namespace std; #define null 0 const int size=510; bool w[size][size]; int 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) { … Continue reading →

http://poj.org/problem?id=2593 //* @author import java.util.Scanner; public class Main{ public static void main(String args[]){ int data[]=new int[100000]; int dp[]=new int[100000]; int n; Scanner in=new Scanner(System.in); while((n=in.nextInt())!=0){ int sum = 0, tmp = -999999999; for(int i = 0; i < n; i++){ … Continue reading →

http://poj.org/problem?id=2591 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { TreeSet< Long> t=new TreeSet< Long>(); Scanner in=new Scanner(System.in); int[] arr=new int[10000001]; arr[0]=1; int k1=0,k2=0; for(int i=1;i< 10000001;i++) { int y1=arr[k1]*2+1; int y2=arr[k2]*3+1; arr[i]=Math.min(y1, y2); … Continue reading →

http://poj.org/problem?id=2590 //* @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(); for(int i=0;i< a;i++) { long x=in.nextLong(); x=in.nextLong()-x; long b=(long)Math.sqrt(x); long ans=-1; if(b==0) ans=0; else if(b*b==x)ans=2*b-1; else if(x<=b*b+b)ans=2*b; else ans=2*b+1; … Continue reading →

http://poj.org/problem?id=2589 #include<iostream> #include"string.h" #include"stdlib.h" using namespace std; int main() { char a[110],b[110],ar[110],br[110]; int n1,r1,n2,r2,k=0,i,g1,g2,r; cin>>a>>b; n1=n2=strlen(a); r1=0;r2=0; g1=0;g2=0; while(k<1000) {if(g1==n1){if(r1==0){cout<<"John wins."<<endl;break;}for(i=r1-1;i>=0;i–)a[i]=ar[i];n1=r1;r1=0;g1=0;} if(g2==n2){if(r2==0){cout<<"Jane wins."<<endl;break;}for(i=r2-1;i>=0;i–)b[i]=br[i];n2=r2;r2=0;g2=0;} ar[r1++]=a[g1++];br[r2++]=b[g2++]; if(ar[r1-1]==br[r2-1]) {r=rand()/99%2; if(r==0){for(i=0;i<r2;i++)ar[r1+i]=br[i];r1+=r2;r2=0; cout<<"Snap! for Jane: ";for(i=r1-1;i>=0;i–)cout<<ar[i];cout<<endl; } else {for(i=0;i<r1;i++)br[r2+i]=ar[i];r2+=r1;r1=0; cout<<"Snap! for John: ";for(i=r2-1;i>=0;i–)cout<<br[i];cout<<endl;} } k++;} … Continue reading →

http://poj.org/problem?id=2588 #include"stdio.h" #include"math.h" const double eps=1e-7; struct cir { double x,y,r; }c[1000]; inline bool edge(cir &a,cir &b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))<=a.r+b.r; } int n; bool init() { int i; if(scanf("%d",&n)!=1)return false; for(i=0;i<n;i++) scanf("%lf %lf %lf",&c[i].x,&c[i].y,&c[i].r); return true; } inline bool touch_up(cir … Continue reading →

http://poj.org/problem?id=2586 import java.io.PrintWriter; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int s,d,result; while(scn.hasNext()){ result = 0; s = scn.nextInt(); d = scn.nextInt(); if(d > 4 … Continue reading →

http://poj.org/problem?id=2585 //* @author: 82638882@163.com import java.io.*; public class Main { static int[][] map=new int[10][10]; static int[][] p=new int[4][4]; public static void main(String[] args)throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); while(true) { String s=in.readLine(); if(s.equals("ENDOFINPUT"))break; String[] ss; for(int i=0;i< … Continue reading →

http://poj.org/problem?id=2584 #include"iostream" #include"algorithm" using namespace std; char *size="SMLXT"; int find( char c ) { char *q = size; while( *q != c ) q++; return q – size; } struct person { int b,e; }p[20]; bool cmp( person p1, person … Continue reading →

http://poj.org/problem?id=2583 import java.io.BufferedInputStream; import java.util.Scanner; /** *poj2583 easy * @author NC */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); while (scan.hasNext()) { int f0 = scan.nextInt(); int f1 = scan.nextInt(); int … Continue reading →

http://poj.org/problem?id=2582 #include<iostream> #include"math.h" using namespace std; struct point { int x,y,z; }b[20],f[20]; inline int sq_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); } int main() { int l,w,d,n,m,ans,i,j; char t[100],c; cin>>t; while( cin>>l>>w>>d ) { … Continue reading →

http://poj.org/problem?id=2581 //* @author: import java.util.*; public class Main { static public void main( String [] str ){ Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int a,b,c,d,e,i,j,k,total,s,value; int as=0,bs=0,cs=0,ds=0; double t; t=sc.nextDouble(); b=sc.nextInt(); c=sc.nextInt(); d=sc.nextInt(); e=sc.nextInt(); a = (int)(t*100); total = … Continue reading →

http://poj.org/problem?id=2580 #include "stdio.h" #include "string.h" #include "stdlib.h" int k[20],keys[20][200],to[20][200]; int key[20]; int n,begin; bool init() { char w[100],num[100],t; int i,j,h; scanf( "%s", w ); if( strcmp( "ENDOFINPUT", w ) == 0 ) return false; scanf( "%d %d", &begin, &n ); … Continue reading →

http://poj.org/problem?id=2579 #include"stdio.h" char map[10][10]; int main() { int i, j, m, n; scanf( "%*s" ); while( scanf( "%d %d", &n, &m ) == 2 ) { for( i=0; i<n; i++ ) scanf( "%s", &map[i] ); for( i=0; i<n-1; i++ ) … Continue reading →

http://poj.org/problem?id=2578 //* @author ������&lt;hongxp11@163.com&gt; import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int height = 168; int crash = 0; for(int … Continue reading →

http://poj.org/problem?id=2577 //* @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)); int[] ram=new int[1000]; int[] reg=new int[10]; int pos=0; int num=1; while(stdin.ready()){ ram[pos++]=new Integer(stdin.readLine()); } … Continue reading →

http://poj.org/problem?id=2576 //* @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 total=0,l1=0,l2=0,i; int[] arr=new int[a]; for(i=0;i< a;i++) { arr[i]=Integer.parseInt(in.readLine()); total+=arr[i]; } int … Continue reading →

http://poj.org/problem?id=2575 //* @author: 82638882@163.com import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); int[] b=new int[a]; for(int i=0;i< a;i++) b[i]=in.nextInt(); HashSet< Integer> h=new HashSet< Integer>(); for(int i=1;i< a;i++) … Continue reading →