Author Archives: toad, die

Poj Solution 1978

http://poj.org/problem?id=1978 import java.io.BufferedInputStream; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(new BufferedInputStream(System.in)); while (scan.hasNext()) { int m = scan.nextInt(); int n = scan.nextInt(); if (m == 0 && n … Continue reading

Posted in poj | Leave a comment

Poj Solution 1977

http://poj.org/problem?id=1977 #include<iostream> #include"string.h" using namespace std; char m[30][100][100]; int n,t,v[100]; char name[100][100][100]; char nm[100][100]; int s[100]; char ans[100][100]; char temp[100][100]; void multiply(char a[100][100],char b[100][100],char c[100][100]) { int i,j,k; for(i=0;i<n;i++) for(j=0;j<n;j++) { c[i][j]=0; for(k=0;k<n;k++) c[i][j]+=a[i][k]*b[k][j]; c[i][j]%=2; } return; } void init() … Continue reading

Posted in poj | Leave a comment

Poj Solution 1976

http://poj.org/problem?id=1976 #include<stdio.h> #include<string.h> #define debug 0 #define NMAX 10002 int a[NMAX]; int s[4][NMAX]; int main() { #if debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int i,j,k,t,d,N; scanf("%d",&t); while(t–) { scanf("%d",&N); memset(s,0,sizeof(int)); memset(a,0,sizeof(int)); for(i=1;i<=N;i++) { scanf("%d",&a[i]); a[i]+=a[i-1]; } scanf("%d",&d); for(k=1;k<=3;k++) { for(i=1;i<=N;i++) { j=0>i-d?0:i-d; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1974

http://poj.org/problem?id=1974 #include<stdio.h> #include<stdlib.h> #define debug 0 #define NMAX 1000003 struct data { long x,y; }v[NMAX]; long t,m,n,k; long count; int cmp1(void const *a,void const *b) { if((*(struct data*)a).y==(*(struct data*)b).y) return (*(struct data*)a).x-(*(struct data*)b).x; else return (*(struct data*)a).y-(*(struct data*)b).y; } int … Continue reading

Posted in poj | Leave a comment

Poj Solution 1973

http://poj.org/problem?id=1973 #include<iostream> using namespace std; int f[110],ft[110]; int n,m; int t1[110],t2[110]; bool checkout(int t) { int i,j,a,b; for(i=1;i<=m;i++) f[i]=-1; f[0]=0; for(j=0;j<=m;j++) ft[j]=f[j]; for(i=0;i<n;i++) { for(a=0;a<=t/t1[i]&&a<=m;a++) { b=(t-t1[i]*a)/t2[i]; for(j=0;j<=m-a;j++) if(f[j]>=0) { if(ft[j+a]<f[j]+b) ft[j+a]=f[j]+b; } } for(j=0;j<=m;j++) f[j]=ft[j]; if(f[m]>=m)return 1; } return … Continue reading

Posted in poj | Leave a comment

Poj Solution 1972

http://poj.org/problem?id=1972 //* @author: <strong> import java.util.*; public class Main { static int max(int u,int v,int w,int x) { if (u< v)u=v; if (u< w)u=w; if (u< x)u=x; return u; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); … Continue reading

Posted in poj | Leave a comment

Poj Solution 1971

http://poj.org/problem?id=1971 #include<stdio.h> #include<string.h> #include<stdlib.h> #define debug 0 #define INF 30000 #if debug #define NMAX 10 #else #define NMAX 1003 #endif typedef struct { int x,y; }point; point a[NMAX],m[NMAX*NMAX]; int cmp(const void*a,const void *b) { if((*(point*)a).x==(*(point*)b).x) return (*(point*)a).y-(*(point*)b).y; else return (*(point*)a).x-(*(point*)b).x; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1970

http://poj.org/problem?id=1970 /* @author: */ import java.util.Scanner; public class Main{ static int p[][]=new int[21][21]; public static void main(String args[]) { Scanner sc=new Scanner(System.in); int tt,i,j,k,x=0,y=0; tt=sc.nextInt(); while((tt–)!=0) { for(i=1;i< 20;i++) for(j=1;j< 20;j++) p[i][j]=sc.nextInt(); int tag=0; for(i=1;i< 20;i++) { for(j=1;j< 16;j++) { … Continue reading

Posted in poj | Leave a comment

Poj Solution 1969

http://poj.org/problem?id=1969 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext()) { int num = cin.nextInt(); int index = 1; int result = 0; while(result <= num) { result += index; index … Continue reading

Posted in poj | Leave a comment

Poj Solution 1965

http://poj.org/problem?id=1965 //* @author mekarlos@gmail.com import java.math.BigDecimal; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); BigDecimal k; BigDecimal root=new BigDecimal("1"); BigDecimal aux=new BigDecimal("0.0000000001"); BigDecimal tr=new BigDecimal("3"); String a; int ind=0,sum; while(scan.hasNext()){ k=scan.nextBigDecimal(); root=k.divide(new BigDecimal("2")); … Continue reading

Posted in poj | Leave a comment

Poj Solution 1964

http://poj.org/problem?id=1964 //* @author mekarlos@gmail.com import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scan=new Scanner(System.in); int[][] N=new int[1001][1001]; int[][] M=new int[1001][1001]; int k=scan.nextInt(); int n=0,m=0,d,maxA; for(int z=0;z< k;z++){ maxA=0; m=scan.nextInt(); n=scan.nextInt(); for(int i=0;i< m;i++) for(int j=0;j< n;j++) … Continue reading

Posted in poj | Leave a comment

Poj Solution 1961

http://poj.org/problem?id=1961 //* @author: import java.util.Scanner; public class Main { static int next[]=new int[1000010]; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n; String input = ""; int j=0; int k=0; while(scn.hasNext()){ n=scn.nextInt(); input = scn.next(); if(n==0){ … Continue reading

Posted in poj | Leave a comment

Poj Solution 1959

http://poj.org/problem?id=1959 /* @author: */ import java.text.DecimalFormat; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a[]=new int[100]; int n,T; long sum; a[0]=0; for(int i=1;i<=20;i++) { a[i]=i; a[20+i]=2*(i); a[40+i]=3*(i); } a[61]=25; a[62]=50; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1953

http://poj.org/problem?id=1953 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()) { long[] f = new long[46]; f[0] = 0; f[1] = 2; f[2] = 3; for (int … Continue reading

Posted in poj | Leave a comment

Poj Solution 1952

http://poj.org/problem?id=1952 //* @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); int a=Integer.parseInt(in.readLine()); int n=0; my[] p=new my[a]; String[] ss; while(a-n>10) { ss=in.readLine().split(" "); for(int i=0;i< 10;i++) … Continue reading

Posted in poj | Leave a comment

Poj Solution 1950

http://poj.org/problem?id=1950 //* @author:alpc12 import java.io.*; import java.util.*; import java.math.*; public class Main { char[] opa = { ‘+’, ‘-‘, ‘.’ }; char[] op; int cnt; int n; int rec[] = {88, 162, 197, 437, 1350 }; void print() { cnt++; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1948

http://poj.org/problem?id=1948 #include <stdio.h> #include <memory.h> #include <math.h> #include <list> using namespace std; bool sign[800][800]; int l[40], n; typedef pair<int,int> node; node q[800*800]; int qn; int main() { int i, j, x, y, s, m; list< node >::iterator iter; scanf( "%d", … Continue reading

Posted in poj | Leave a comment

Poj Solution 1947

http://poj.org/problem?id=1947 #include <list> #include <iostream> using namespace std; list< int > e[150]; int ans[150][151]; int n, p, answer; int root; int creat( int r ) { int i, j, n, m, c, temp[151]; n = 1; ans[r][0] = 1; ans[r][1] … Continue reading

Posted in poj | Leave a comment

Poj Solution 1946

http://poj.org/problem?id=1946 #include <iostream> using namespace std; int maxs[101][101], n, e, d; // ʱ�� �� int need[101][101]; // ·�� �� void init() { int t, s, v, h; cin>>n>>e>>d; for( t=0; t<=d; t++ ) maxs[t][0] = 0; for( h=0; h<=e; h++ … Continue reading

Posted in poj | Leave a comment

Poj Solution 1944

http://poj.org/problem?id=1944 #include <stdio.h> #include <algorithm> #include <memory.h> using namespace std; int t[4100]; int sum[4100]; void insert( int l, int r, int a, int b, int s, bool del ) { int c = (l+r)/2; if( l>=r || l>=b || r<=a … Continue reading

Posted in poj | Leave a comment

Poj Solution 1942

http://poj.org/problem?id=1942 //* @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); while(true) { String[] ss=in.readLine().split(" "); Long n=Long.parseLong(ss[0]); Long m=Long.parseLong(ss[1]); if(n==0&&m==0) break; long ans=1; n=m+n; if(m>n-m) m=n-m; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1940

http://poj.org/problem?id=1940 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); double[] x=new double[a]; double[] y=new double[a]; for(int i=0;i< a;i++) { x[i]=in.nextDouble(); y[i]=in.nextDouble(); } double sx=0,sy=0,uu=-1; System.out.print(a); for(int … Continue reading

Posted in poj | Leave a comment

Poj Solution 1939

http://poj.org/problem?id=1939 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); System.out.print(a+" "); double x1,y1,x,y,kx,ky; x=x1=in.nextDouble(); y=y1=in.nextDouble(); for(int i=1;i< a;i++) { kx=in.nextDouble(); ky=in.nextDouble(); System.out.printf("%.6f %.6f ",(x+kx)/2,(y+ky)/2); x=kx; y=ky; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1936

http://poj.org/problem?id=1936 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String[] str = new String[2]; String a, b; boolean result; while(cin.hasNext()) { str = cin.nextLine().split(" "); a = str[0]; b = str[1]; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1934

http://poj.org/problem?id=1934 #include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <set> using namespace std; int ans[81][81]; int from[81][81]; char route1[100],route2[100]; int n,m; void doit() { int i,j; for( i=0; i<=n; i++) ans[i][0] = 0; for( j=0; j<=m; j++) ans[0][j] = … Continue reading

Posted in poj | Leave a comment

Poj Solution 1928

http://poj.org/problem?id=1928 //* @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()); while((a–)!=0) { String[] ss=in.readLine().split(" "); int cow=Integer.parseInt(ss[0]); int cul=Integer.parseInt(ss[1]); int sum=Integer.parseInt(ss[2])-2; my[] … Continue reading

Posted in poj | Leave a comment

Poj Solution 1927

http://poj.org/problem?id=1927 /* @author: */ import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = 1; double l1, l2, l3, s, c, p, R, ctg1, ctg2, ctg3, len, r, ls, area; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1925

http://poj.org/problem?id=1925 #include"stdio.h" #include"math.h" #include"memory.h" int x[5010],h[5010]; int pos[1000001]; int n; void init() { int i; scanf( "%d", &n ); for( i=0; i<n; i++ ) scanf( "%d %d", x+i, h+i ); memset( pos, -1, sizeof(int)*(x[n-1]+1) ); } void doit() { int … Continue reading

Posted in poj | Leave a comment

Poj Solution 1923

http://poj.org/problem?id=1923 import java.util.Scanner; public class Main { static int com(int a) { return a*(a-1)/2; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); long line[][]=new long[101][10001]; int i,j,k,p,q,cs=0; long max,tmp; for(i=1;i<=100;i++) line[i][0]=i+1; for(i=2;i<=100;i++) for(j=1;j<=com(i);j++) { max=0; for(k=1;k<=i-1;k++) … Continue reading

Posted in poj | Leave a comment

Poj Solution 1922

http://poj.org/problem?id=1922 import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner s = new Scanner(System.in); while(true) { int n = s.nextInt(); if(n == 0) System.exit(-1); double min = 1000000000; while(n > 0) { int v = s.nextInt(); int … Continue reading

Posted in poj | Leave a comment

Poj Solution 1916

http://poj.org/problem?id=1916 #include <iostream> #include <string.h> using namespace std; int a[1030][1030]; int main() { int test,d,n,i,max,j,temp,x,y,now; cin>>test; while(test–) { cin>>d; cin>>n; memset(a,0,sizeof(a)); for(i=0;i<n;i++) { cin>>x>>y; cin>>a[x][y]; } max=-1; for(i=1;i<1025;i++) { a[i][0]+=a[i-1][0]; a[0][i]+=a[0][i-1]; } temp=2*d+1; for(i=1;i<1025;i++) for(j=1;j<1025;j++) { a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; if(i>=temp&&j>=temp) { now=a[i][j]-a[i-temp][j]-a[i][j-temp]+a[i-temp][j-temp]; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1915

http://poj.org/problem?id=1915 import java.io.BufferedInputStream; import java.util.LinkedList; import java.util.Scanner; public class Main { private static int[][] directions = new int[][]{ {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; static void BreadthFirstSearch(int startX, int startY, … Continue reading

Posted in poj | Leave a comment

Poj Solution 1914

http://poj.org/problem?id=1914 //* @author popop0p0popo import java.util.*; import java.io.*; import java.text.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n=scanner.nextInt(); BigInteger[][] a; BigInteger[] b; BigInteger aa,aa1,aa2,aa3; for (int i=0;i< n ;i++ ){ a=new … Continue reading

Posted in poj | Leave a comment

Poj Solution 1909

http://poj.org/problem?id=1909 //* @author: ccQ.SuperSupper import java.util.*; import java.io.*; class node{ int init_have; int sum_have; int nodes; Vector son = new Vector(); } public class Main { static int N = 10000+100; public static void main(String []args) throws Exception{ int n,i,j,ans,cnt,sons,root; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1906

http://poj.org/problem?id=1906 //* @author: import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[]args){ BigInteger dat[]=new BigInteger[100]; dat[0]=BigInteger.ONE; BigInteger tr=new BigInteger("3"); for(int i=1;i< 100;i++){ dat[i]=dat[i-1].multiply(tr); } long N; int t; boolean first; Scanner cin=new Scanner(System.in); while(cin.hasNext()){ N=cin.nextLong(); if(N==0) break; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1905

http://poj.org/problem?id=1905 /* @author: */ import java.util.Scanner; public class Main{ static final double PI=3.1415926; static final double eps=1e-6; public static void main(String args[]) { Scanner sc=new Scanner(System.in); double L,n,C,M,y1,low,high,mid; while(true) { L=sc.nextDouble(); n=sc.nextDouble(); C=sc.nextDouble(); if(L==-1&&n==-1&&C==-1)break; if(L<=eps||n<=eps||C<=eps) { System.out.println("0.000"); continue; } M=(1+n*C)*L; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1904

http://poj.org/problem?id=1904 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int e2[2010], ee2[2010], n; vector<int> e1[2010]; vector<int> ee1[2010]; vector<int> ans[2010]; void input( ) { int i, k, m; scanf( "%d", &n ); for( i=0; i<n; i++ ) { scanf( "%d", … Continue reading

Posted in poj | Leave a comment

Poj Solution 1901

http://poj.org/problem?id=1901 #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; const int size = 1000; struct point { double x, y, z; int k; }p[size]; inline double 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); … Continue reading

Posted in poj | Leave a comment

Poj Solution 1896

http://poj.org/problem?id=1896 //* @author:alpc12 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; StringBuffer sb = new StringBuffer(); while ((line = in.readLine()) != null) { for … Continue reading

Posted in poj | Leave a comment

Poj Solution 1894

http://poj.org/problem?id=1894 import java.io.*; import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { BigInteger sum,m,D[] = new BigInteger[2]; int i,b[] = new int[340]; Scanner cin = new Scanner(System.in); m = cin.nextBigInteger(); sum = cin.nextBigInteger(); int k … Continue reading

Posted in poj | Leave a comment

Poj Solution 1887

http://poj.org/problem?id=1887 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int totalnum; int count = 0; //while((totalnum=Integer.parseInt(in.readLine()))!=-100){ while(true) { int num; ArrayList < Integer> array = … Continue reading

Posted in poj | Leave a comment

Poj Solution 1882

http://poj.org/problem?id=1882 #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define NMAX 101 #define INF 10000 int anset[NMAX],alen,min; int m[10020]; int t[NMAX]; int N,S,len; void solve() { int i,j; m[0]=0; i=1; while(1) { m[i]=INF; for(j=0;j<len;j++) { if(t[j]>i) break; if(m[i]>m[i-t[j]]+1) { m[i]=m[i-t[j]]+1; } } if(m[i]>S) break; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1868

http://poj.org/problem?id=1868 /* @author: */ import java.util.Scanner; public class Main { private int n; private int a[]; public Main(int n,int[] a){ this.n=n; this.a=a; } public boolean doIt(){ for(int j=1;j< n/2;j++) { for(int i=j;i< n-j;i++) { if((a[i-j]-a[i])*(a[i+j]-a[i])< 0) { return true; } … Continue reading

Posted in poj | Leave a comment

Poj Solution 1867

http://poj.org/problem?id=1867 #include <stdio.h> #include <vector> #include <string.h> using namespace std; #define YES { printf( "samen" ); continue; } #define NO { printf( "differentn" ); continue; } #define PT(a) (printf("an")); struct node { vector< node* > next; char c; }mem[500]; char … Continue reading

Posted in poj | Leave a comment

Poj Solution 1862

http://poj.org/problem?id=1862 import java.util.*; import java.text.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int num = Integer.valueOf(cin.nextLine()).intValue(); List list = new ArrayList(); for(int i = 0; i < num; i++) list.add(Double.valueOf(cin.nextLine())); Collections.sort(list); double … Continue reading

Posted in poj | Leave a comment

Poj Solution 1861

http://poj.org/problem?id=1861 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class Edge implements Comparable{ int u,v,disten; Edge(){}; void set(int u,int v,int disten){ this.u = u; this.v = v; this.disten = disten; } public int compareTo(Object obj){ Edge temp = (Edge)obj; if(this.disten>temp.disten) return … Continue reading

Posted in poj | Leave a comment

Poj Solution 1860

http://poj.org/problem?id=1860 //* @author import java.io.File; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; //���·��bellman_ford public class Main { Scanner cin = new Scanner(System.in); int n; int m; int s; double v; Edge[] rate; Edge[] commission; double[] value; public static final double EPS … Continue reading

Posted in poj | Leave a comment

Poj Solution 1859

http://poj.org/problem?id=1859 #include <stdio.h> #include <algorithm> using namespace std; struct pairs { int first, second; }p[20100]; bool cmp( const pairs& a, const pairs& b ) { return a.first<b.first || a.first==b.first&&a.second<b.second; } int main( ) { int n, i, sx, sy; while( … Continue reading

Posted in poj | Leave a comment

Poj Solution 1852

http://poj.org/problem?id=1852 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { /** * @param args */ static int max(int a,int b) { if(a>b) return a; return b; } static int min(int a,int b) { if(a>b) return b; return a; … Continue reading

Posted in poj | Leave a comment

Poj Solution 1850

http://poj.org/problem?id=1850 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); String s=in.next(); boolean bb=false; for(int i=0;i< s.length()-1;i++) { if(s.charAt(i)-s.charAt(i+1)>=0) { System.out.println(0); bb=true; break; } } if(bb) System.exit(0); int l=s.length(); long ans=0; … Continue reading

Posted in poj | Leave a comment