# Monthly Archives: April 2011

## Poj Solution 1775

http://poj.org/problem?id=1775 /* @author: */ import java.util.*; public class Main { static StringBuffer res = new StringBuffer(); public static void main(String[] args){ Scanner in = new Scanner(System.in); int maxn=1100000; int a[]=new int[11]; boolean f[]=new boolean[maxn]; int n; a[0]=1; for(int i=1;i<=10;i++) a[i]=i*a[i-1]; … Continue reading

## Poj Solution 1774

http://poj.org/problem?id=1774 #include<iostream> using namespace std; struct point {double x,y;}; struct line {point a,b;}; point a[1010],b[1010]; int n,d[1010]; 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);} /////////////// void init() {int i; d[0]=-1; a[0].x=0;b[0].x=0; … Continue reading

## Poj Solution 1766

http://poj.org/problem?id=1766 #include<iostream> using namespace std; int edge[32][32],sign[32]; int e[][2]={{0,1},{0,2},{0,3},{0,4},{0,5}, {11,6},{11,7},{11,8},{11,9},{11,10}, {1,2},{2,3},{3,4},{4,5},{5,1}, {6,7},{7,8},{8,9},{9,10},{10,6}, {1,6},{1,7}, {2,7},{2,8}, {3,8},{3,9}, {4,9},{4,10}, {5,10},{5,6}, }; void find(int a) {int i; for(i=0;i<32;i++) if(edge[a][i]&&sign[i]==0){sign[i]=1;find(i);} } int main() {int i,j,a,b,k,h,n,yes,no,past; for(i=0;i<32;i++) for(j=0;j<32;j++)edge[i][j]=0; for(i=0;i<30;i++) {a=e[i][0];b=e[i][1];edge[a][b]=edge[b][a]=1;} h=12; for(i=0;i<12;i++) for(j=i+1;j<12;j++) for(k=j+1;k<12;k++) if(edge[i][j]&&edge[i][k]&&edge[j][k]) {edge[h][i]=edge[i][h]=1; … Continue reading

## Poj Solution 1763

http://poj.org/problem?id=1763 #include<iostream> #include"memory.h" #include"algorithm" using namespace std; long x[260000],y[260000]; long ordx[260000],ordy[260000]; inline long abs(long a) {return a>0?a:-a;} int cmpx(long a,long b) {return x[a]<x[b]||(x[a]==x[b]&&y[a]<y[b]);} int cmpy(long a,long b) {return y[a]<y[b]||(y[a]==y[b]&&x[a]<x[b]);} int main() {char c;long xn,yn,n,i,bb,eb,lb,b,e,l; cin>>n; xn=0;yn=0;ordx[0]=0;ordy[0]=0;x[0]=0;y[0]=0; for(i=1;i<=n;i++) {cin>>c; switch(c) {case’N’:yn–;break; … Continue reading

## Poj Solution 1761

http://poj.org/problem?id=1761 #include<iostream> #include"string.h" #include"stdio.h" using namespace std; char name[62][10],w[10]; long ci[62][9],ti[62][9]; int main() {long i,n,j,m,t,c;char q,a; for(i=0;i<62;i++) for(j=0;j<9;j++){ti[i][j]=-1;ci[i][j]=0;} cin>>n; m=0; while(n–) {cin>>t>>w>>q>>a; for(i=0;i<m;i++)if(strcmp(name[i],w)==0)break; if(i==m){m++;strcpy(name[m-1],w);} j=q-‘A’; if(ti[i][j]==-1){ci[i][j]++;if(a==’A’)ti[i][j]=t;} } int ac; for(j=0;j<9;j++) {c=0;t=0;ac=0; for(i=0;i<62;i++) if(ti[i][j]!=-1){ac++;c+=ci[i][j];t+=ti[i][j];} printf("%c %ld",j+’A’,ac); if(ac)printf(" %.2f %.2f",(float)c/ac,(float)t/ac); printf("n"); } … Continue reading

## Poj Solution 1753

http://poj.org/problem?id=1753 import java.io.BufferedInputStream; import java.util.LinkedList; import java.util.Scanner; public class Main { static boolean[] isVisited = new boolean[65536]; public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); if (scan.hasNext()) { int[][] chessBoard = new int[4][4]; for (int i … Continue reading

## Poj Solution 1751

http://poj.org/problem?id=1751 //* @author: 82638882@163.com import java.io.*; 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; int b=Integer.parseInt(in.readLine()); int[] ax=new int[b]; int[] ay=new int[b]; int[][] p=new int[b][b]; for(int i=0;i< … Continue reading

## Poj Solution 1745

http://poj.org/problem?id=1745 //* @author: ccQ.SuperSupper import java.util.*; public class Main { static int M = 100+10; static int N = 2; public static void main(String []args) throws Exception{ int n,m,i,j,k,cnt; int DP[][] = new int[N][M]; Scanner cin = new Scanner(System.in); n … Continue reading

## Poj Solution 1742

http://poj.org/problem?id=1742 /* @author: */ import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String args[]) { int N, M; Scanner sc=new Scanner(System.in); while(sc.hasNext()) { N=sc.nextInt();//Ӳ�ҵ����� M=sc.nextInt();// if(N==0&&M==0) break; int a[]=new int[100];//a[i]��ʾ��i��Ӳ�ҵ���ֵ int c[]=new int [100];//c[i]��ʾ��i��Ӳ�ҵĸ��� for (int i=0; i< … Continue reading

## Poj Solution 1741

http://poj.org/problem?id=1741 #include"stdio.h" #include"algorithm" using namespace std; long use[14]; long lchild[10010][14]; long rchild[10010][14]; long sum[510010][14]; long depth[10010][14]; long value[10010],dist[10010]; long m,n,k,kind,answer; long findit(long key,long s1,long deep) { long &lc=lchild[s1][deep],&rc=rchild[s1][deep],sumnow=sum[s1][deep]; long now=depth[s1][deep]; if(now==key) { if(rc>=0)return sumnow-sum[rc][deep+1]; else return sumnow; } else if(key<now) … Continue reading

## Poj Solution 1740

http://poj.org/problem?id=1740 /* @author: */ import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int a[]=new int[11]; boolean flag=false; while(sc.hasNext()) { flag=true; int n=sc.nextInt(); if(n==0) break; for(int i=1;i<=n;i++) a[i]=sc.nextInt(); if(n%2==1) { System.out.printf("1n"); continue; }//������������Ȼ�ǵ�һ����Ӯ for(int i=1;i< n&&flag;i++) … Continue reading

## Poj Solution 1737

http://poj.org/problem?id=1737 import java.util.*; import java.math.*; public class Main { BigInteger[] ans = new BigInteger[52]; public Main() { DP(); solve(); } //求组合数 BigInteger combinationNum(int n, int m) { BigInteger ret = new BigInteger("1"); int i; for (i = 0; i < … Continue reading

## Poj Solution 1732

http://poj.org/problem?id=1732 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class word{ String str,num; public void change(){ } } public class Main { static final int N = 100+10,M = 50000+10; static Map mymap = new HashMap(); static int DP[] = new … Continue reading