Category Archives: poj

http://poj.org/problem?id=1152 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static int get_base(char c){ if(c>=’0’&&c<=’9′) return c-‘0’+0; if(c>=’A’ && c<=’Z’) return c-‘A’+ 10; if(c>=’a’ && c<=’z’) return c-‘a’ + 36; return -1; } public static void main(String[]args) throws … Continue reading →

http://poj.org/problem?id=1151 #include<iostream> #include"stdio.h" #include"vector" #include <algorithm> using namespace std; struct rect {double xt,yt,xb,yb; }; struct point {double x,y;}; double max(double a,double b) {if(a>b)return a; else return b; } double min(double a,double b) {if(a>b)return b; else return a; } /* rect … Continue reading →

http://poj.org/problem?id=1150 #include<iostream> #include<cstring> #include<cmath> using namespace std; int get2(int n)//计算n!中质因子2的出现次数 { if(n==0) return 0; return n/2+get2(n/2); } int get5(int n)//计算n!中质因子5的出现次数 { if(n==0) return 0; return n/5+get5(n/5); } ////////////////////////////////////////////////////////////////////////// int g(int n,int x)//计算f(1) to f(n) 中，奇数数列中末尾为x的数出现的次数 { if(n==0) return 0; return … Continue reading →

http://poj.org/problem?id=1149 #include <list> #include <vector> using namespace std; class pre_f { public: enum{ MAX = 1000000000 }; //��������� enum{ size = 103 }; //ͼ�����ģ(*) // ����һ��� from �� to �� ��Ϊ c �ı� void insert_edge( int from, int to, int … Continue reading →

http://poj.org/problem?id=1148 #include <stdio.h> #include <algorithm> using namespace std; int num[20000], n; int ans_x[10000], ans_y[10000],sign_x[10000], sign_y[10000]; const int xsign[]={ 1, -1, -1, 1 },ysign[]={ 1, 1, -1, -1}, h[]={ 1, -1}; void creat(int end, int num[], int sign[], int ans[], int … Continue reading →

http://poj.org/problem?id=1147 #include"stdio.h" int a[3001]; int next[3001]; int main() { int n,i,j,k=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); if(!a[i])k++; } j=1; k++; for(i=1;i<=n;i++) if(a[i]) { next[k]=i; k++; } else { next[j]=i; j++; } k=1; for(i=1;i<=n;i++) { k=next[k]; printf("%d ",a[k]); } return 0; }

http://poj.org/problem?id=1146 /* @author:zeropinzuo */ import java.io.*; import java.util.*; public class Main{ static Scanner cin; public static void main(String args[]){ cin = new Scanner(System.in); while(run(cin.next())) ; } static boolean run(String input){ if(input.compareTo("#") == 0) return false; System.out.println(next(input)); return true; } static … Continue reading →

http://poj.org/problem?id=1142 import java.util.Scanner; public class Main { public static int sum = 0; public static boolean isPrime(int num) { for (int i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) return false; } return true; … Continue reading →

http://poj.org/problem?id=1141 //* @author: import java.util.*; public class Main { //f[i][j]��λ��i��λ��j����Ҫ�������С�ַ���ans[i][j]��ʾi��j֮������(��ƥ���ַ� private char s[]; private int len; private int f[][]; private String ans[][]; public Main(char s[]){ this.s=s; this.len=s.length; f=new int[len][len]; ans=new String[len][len]; for(int i=0;i< len;i++) Arrays.fill(ans[i],""); dp(); } public String[][] getAns(){ … Continue reading →

http://poj.org/problem?id=1140 /* @author: */ import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int a,b,i,j,c[],f,d; c=new int[2000]; for(;;) { a=cin.nextInt(); b=cin.nextInt(); if(a==0&b==0)break; c[0]=a;i=0;f=0;j=0;d=1; System.out.print("."); for(;;) { a=(a*10)%b; if(a!=0) { … Continue reading →

http://poj.org/problem?id=1137 //* @author:alpc12 import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.lang.Integer; class Node { int x, mask; int s; int f; int action; public Node(int x, int mask, int s, int f, int aa) … Continue reading →

http://poj.org/problem?id=1135 import java.util.Scanner; public class Main { static final int Inf=9999999; public static void main(String[] args) { Scanner in=new Scanner(System.in); int cnt=0; while(true) { cnt++; int n=in.nextInt(); int m=in.nextInt(); if(n==0&&m==0)break; int[][] p=new int[n][n]; for(int i=0;i< n;i++) for(int j=0;j< n;j++) p[i][j]=Inf; … Continue reading →

http://poj.org/problem?id=1133 #include<iostream> #include"math.h" #include<algorithm> #include<vector> using namespace std; struct point {long x,y;}; typedef point vect; struct {point p; int bright; }star[1001]; int sn,vn; double v_sin,v_cos,bi; vect vec[1001]; double len; point pt[1001]; inline double jl(point &a,point &b) {return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} inline long … Continue reading →

http://poj.org/problem?id=1132 #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define NMAX 33 #define INF 1000000001 int xp[4]={0,1,0,-1},yp[4]={1,0,-1,0}; int dx[4]={0,0,-1,-1},dy[4]={0,-1,-1,0}; int stx,sty; int map[NMAX][NMAX]; char in[NMAX*NMAX]; int set(char t) { switch(t) { case ‘N’:return 0; case ‘E’:return 1; case ‘S’:return 2; case ‘W’:return 3; } … Continue reading →

http://poj.org/problem?id=1131 import java.io.*; import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner cin=new Scanner(System.in); BigDecimal temp,sum,ans,num; String str; int i,len; while(cin.hasNext()){ str=cin.next(); len=str.length(); temp=BigDecimal.valueOf(8.0); sum=BigDecimal.ONE; ans=BigDecimal.ZERO; for(i=2;i< len;i++) { int val=str.charAt(i)-‘0’; num=BigDecimal.valueOf(val); sum=sum.multiply(temp); ans=ans.add(num.divide(sum)); } System.out.printf("%s … Continue reading →

http://poj.org/problem?id=1129 import java.util.*; import java.io.*; /* *����������ŵ7��䡣��һ������ͼ��Ϊÿ����������ɫ��Ҫ���������ڵĶ�����ɫ��ͬ�� * �����ٵ���ɫ���Ƕ���? *������������ɫ���?ֱ��ö����ɫ��+DFS������DFS�DZ�fö��ÿ�����ɫ���Ա��ҵ�һ����н⡣ */ public class Main{ public static int[][] g=new int[26][26]; public static int solve(int n){ int i,j,cnum; boolean tag=true; // �ޱ�ͼֻ��1ɫ���� for(i=0;i< n && tag;i++){ for(j=i+1;j< n && tag;j++){ if(g[i][j]==1) tag=false; … Continue reading →

http://poj.org/problem?id=1126 import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { Scanner s = new Scanner(System.in); String sentence = null; int count; char ch; while ((sentence = s.nextLine()) != null) { count = … Continue reading →

http://poj.org/problem?id=1122 //* @author: 82638882@163.com import java.util.Arrays; import java.util.Scanner; public class Main { static final int Inf=9999999; 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(); int loc =in.nextInt()-1; … Continue reading →

http://poj.org/problem?id=1120 /* @author: */ import java.util.Scanner; import java.util.Arrays; public class Main{ int map[][]=new int[22][22]; int d[]=new int[16]; char code[]={‘.’,’!’,’X’,’#’}; int sum(int i,int j){ return map[i][j]+map[i-1][j]+map[i+1][j]+map[i][j-1]+map[i][j+1]; } public void doIt(){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i< 16;i++) d[i]=sc.nextInt(); for(int i=1;i<=20;i++) … Continue reading →

http://poj.org/problem?id=1119 import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.HashMap; import java.util.Map; public class Main{ private static String convertString(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) >= … Continue reading →

http://poj.org/problem?id=1118 //* @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; 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 … Continue reading →

http://poj.org/problem?id=1113 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) throws IOException { … Continue reading →

http://poj.org/problem?id=1112 #include <vector> #include <algorithm> #include <stdio.h> #include <memory.h> #include <math.h> using namespace std; vector<int> unknow[100]; vector< pair<int,int> > s; int sign[100]; bool e[100][100]; int flag[110][110]; int a, b, an, bn; bool search( int k, int key ) { int … Continue reading →

http://poj.org/problem?id=1111 //* @author: 82638882@163.com import java.io.*; class Main { static int cnt; static char[][] map; static int[][] bool; public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); while(true) { cnt=0; String[] ss=in.readLine().split(" "); int row=Integer.parseInt(ss[0]); … Continue reading →

http://poj.org/problem?id=1110 #include "stdio.h" char map[80][10][80]; int n; int main( ) { int n, r, c, i, j, k, l, test = 0; while( scanf( "%d%d%d", &n, &r, &c ) == 3 ) { if( n == 0 ) break; for( … Continue reading →

http://poj.org/problem?id=1108 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> struct window { char c; int hig, wid; int rc, lc; bool al; } wi[70]; char str[70]; int stack[70]; int top; char res[70][70]; void change(int len, bool worh, int w) { int rl, ll, rn, … Continue reading →

http://poj.org/problem?id=1105 /* @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 n,m,times=1,map[]=new int[7]; char bits[]=new char[129],s[]=new char[20]; while(true){ n=sc.nextInt(); if(n==0) break; for(int i=0;i< n;i++){ s=sc.next().toCharArray(); map[s[1]-‘1’]=(char)i; } bits=sc.next().toCharArray(); m=sc.nextInt(); System.out.printf("S-Tree #%d:n",times++); … Continue reading →

http://poj.org/problem?id=1103 #include <iostream> #include <memory> #define MAX_N 75 #define MAX_T 150 using namespace std; bool visited[MAX_N + 5][MAX_N + 5][2]; char input[MAX_N + 5][MAX_N + 5]; int w, h, cyNum, lCy = INT_MIN; int startH, startW, startP; bool inRange(int curH, … Continue reading →

http://poj.org/problem?id=1102 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader( System.in)); int s; String[] ss; String str; String[] num = new String[] { "1111110", "0000110", … Continue reading →

http://poj.org/problem?id=1101 #include <iostream> #include <queue> using namespace std; const int MAXN = 80; char cmap[MAXN][MAXN]; bool used[MAXN][MAXN]; short turn[MAXN][MAXN]; // [i,j]’s turn direction int vis[MAXN][MAXN]; // the number int w, h, res; bool isSucceed; struct node { int x, y; … Continue reading →

http://poj.org/problem?id=1100 #include <iostream> #include <sstream> #include <string> #include <vector> using namespace std; #define NIL (unsigned)-1 #define MAX 12 typedef vector <int> VI; typedef unsigned int UI; int cas, N, F; int equ, tmp_num[MAX], UFS[MAX]; VI num, prio, pos, opr, v0, … Continue reading →

http://poj.org/problem?id=1096 #include<iostream> #include"memory.h" using namespace std; char map[60][60][60]; long answer; int n,m,h; void find() {int i,j,k,key; answer=0; for(i=0;i<m;i++) for(j=0;j<n;j++) {key=1; for(k=0;k<h;k++)if(map[k][i][j]==1&&key){answer++;key=0;} else if(map[k][i][j]==2)key=1; key=1; for(k=h-1;k>=0;k–)if(map[k][i][j]==1&&key){answer++;key=0;} else if(map[k][i][j]==2)key=1; } for(i=0;i<h;i++) for(j=0;j<m;j++) {key=1; for(k=0;k<n;k++)if(map[i][j][k]==1&&key){answer++;key=0;} else if(map[i][j][k]==2)key=1; key=1; for(k=n-1;k>=0;k–)if(map[i][j][k]==1&&key){answer++;key=0;} else if(map[i][j][k]==2)key=1; } for(i=0;i<h;i++) … Continue reading →

http://poj.org/problem?id=1095 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static final int N = 20+10; static int sum[] = new int[N],catana[] = new int[N]; static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws Exception{ … Continue reading →

http://poj.org/problem?id=1093 #include<iostream> using namespace std; const char space=’ ‘; char word[10001],l; int len[10002],m,n; int jie[10002]; int chen[10002]; long bad[10002]; void init() {int h=0,j=1,t=0; while(cin.get()) {if(cin.peek()==10)break; while(cin.peek()!=10) {if(cin.peek()==32){cin.get();if(t){len[j++]=t;t=0;}} else {cin.get(word[h++]); t++;} } if(t){len[j++]=t;t=0;} } len[0]=0; m=j-1; l=h; //for(i=0;i<l;i++)cout<<word[i]; //cout<<endl; //for(i=1;i<=m;i++)cout<<len[i]<<endl; } … Continue reading →

http://poj.org/problem?id=1091 //* @author popop0p0popo import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int[] yue=getYue(m); for (int i=0;i< yue.length ;i++ ){ if (yue[i]==0){ break; } m=m/yue[i]; } BigInteger ok=(new BigInteger(""+m)).pow(n); … Continue reading →

http://poj.org/problem?id=1090 /* @author: */ import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner stdin=new Scanner(System.in); int n=stdin.nextInt(); int[] a=new int[n],b=new int[n]; for(int i=0;i< n;i++)a[i]=stdin.nextInt(); b[0]=a[n-1]; for(int i=1;i< n;i++){ b[i]=b[i-1]^a[n-1-i]; } BigInteger ans=new BigInteger("0"),two=new BigInteger("2"); for(int … Continue reading →

http://poj.org/problem?id=1089 //* @author: SmilingWang import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n; n = in.nextInt(); Interval intervals[] = new Interval[n]; for(int i = 0; i < n; i++){ int x = … Continue reading →

http://poj.org/problem?id=1087 #include<iostream> #include"string.h" using namespace std; #define null 0 const int size=1000; bool w[size][size]; void maxmatch(int n,int m,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; s=0; for(j=0;j<m;j++) if(w[i][j]!=null) { … Continue reading →

http://poj.org/problem?id=1083 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader read = new BufferedReader(new InputStreamReader( System.in)); int t = Integer.parseInt(read.readLine()); int s; int[][] m; String[] str; int[] … Continue reading →

http://poj.org/problem?id=1082 //* @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(); while((a–)!=0) { in.nextInt(); boolean bb=false; int m=in.nextInt(); int d=in.nextInt(); if((m+d)%2==0)bb=true; else if(m==9&&d==30)bb=true; else if(m==11&&d==30)bb=true; if(bb)System.out.println("YES"); else System.out.println("NO"); } } … Continue reading →

http://poj.org/problem?id=1080 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static int[][] chart; public static void main(String[] args){ init(); Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int p=in.nextInt(); for (int k=0;k< p ;k++ ){ int m=in.nextInt(); String a=in.next(); int n=in.nextInt(); … Continue reading →

http://poj.org/problem?id=1079 import java.io.*; public class Main { public static int gcd(int a,int b){ while(a%b!=0){ int temp=a; a=b; b=temp%b; } return b; } public static void main(String[] args) throws IOException{ StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); while(in.nextToken()!=StreamTokenizer.TT_EOF){ int a,b; double last=100000; a=(int)in.nval; … Continue reading →

http://poj.org/problem?id=1078 #include<iostream> using namespace std; int t[100],n; int go(int i,long s,long a,long b) {if(s==1)return 1; if(i==n)return 0; if(a%t[i]==0)if(go(i+1,s/t[i],a/t[i],b))return 1; if(b%t[i]==0)if(go(i+1,s/t[i],a,b/t[i]))return 1; if(go(i+1,s,a,b))return 1; return 0; } int main() {int i;long a,b,s; while(1) {cin>>a;if(cin.fail())break; cin>>b; if(a<b){a=a+b;b=a-b;a=a-b;} s=a*b;n=0; for(i=100;i>1;i–) if(s%i==0&&(a%i==0||b%i==0))t[n++]=i; if(!go(0,b,b,1)){cout<<a<<endl;continue;} if(!go(0,a,a,1)){cout<<b<<endl;continue;} … Continue reading →

http://poj.org/problem?id=1077 //* @author: 82638882@163.com import java.util.*; public class Main { static int[][] arr; static boolean[] bb=new boolean[10000000]; static Queue< my> qu=new LinkedList< my>(); public static void main(String[] args) { Scanner in=new Scanner(System.in); arr=new int[5][5]; String s; for(int i=1;i< 4;i++) { … Continue reading →

http://poj.org/problem?id=1072 #include <stdio.h> #include <string.h> #include <algorithm> //#define DEBUG //#define PRINT_TREE #ifdef DEBUG #include <time.h> #endif using namespace std; const char NONE = 30; const char WORD = 50; struct node { node(){ p=0; m=”; for(int i=0;i<27;i++)id[i]=NONE; } char id[27]; … Continue reading →

http://poj.org/problem?id=1068 import java.util.Scanner; public class Main { int t; int len; int[] p; int[] w; String[] s; int index; int temp; int pos; public Main() { Scanner scan = new Scanner(System.in); t = scan.nextInt(); for (int i = 0; i … Continue reading →

http://poj.org/problem?id=1067 #include <iostream> #include <algorithm> #include <cmath> #include <stdio.h> using namespace std; int main() { int ax,bx,temp; int k,wantedax; while(scanf("%d%d",&ax,&bx)!=EOF) /*题中没有输入结标志时，必须这样写，否则会WA*/ { if(ax>bx) swap(ax,bx); k = bx – ax; wantedax = (floor)( k*(1.0+sqrt(5.0))/2.0 ); if(ax==wantedax) printf("%dn",0); else printf("%dn",1); } return … Continue reading →

http://poj.org/problem?id=1066 #include <iostream> #include <cstdio> #include <algorithm> #define MAX 35 int N; using namespace std; typedef struct Point { double x,y; Point() {} Point(double tx,double ty):x(tx),y(ty) {} }Vector; int WallY0[MAX]; //��ַ����ݸ��� int WallY100[MAX]; int WallX0[MAX]; int WallX100[MAX]; struct Line { … Continue reading →

http://poj.org/problem?id=1065 import java.util.*; public class Main{ public static void main(String[] args){ int l[]=new int[10000]; int w[]=new int[10000]; int tt[]=new int[5000]; int k=0; Scanner keyin=new Scanner(System.in); int m=keyin.nextInt(); int mm=m; int n=0; for(;m>0;m–){ n=keyin.nextInt(); for(int j=0;j< n;j++){ l[j]=keyin.nextInt(); w[j]=keyin.nextInt(); } int … Continue reading →

http://poj.org/problem?id=1064 #include <iostream> #include <cstdio> using namespace std; int N,K; long long len[10001]; int main() { while(cin>>N>>K) { double t; long long sum = 0; for(int i = 0;i < N;i++) { cin>>t; t *= 100; len[i] = (long long)t; … Continue reading →