/* Water problem...but I don't have a Java compiler in my office. * Several compilation error...so sad...worked in notepad. */ import java.util.*; import java.io.*; import java.math.BigInteger; public class Solution { public static void main (String[] argv) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); String str = st.nextToken(); int a = Integer.parseInt(str); BigInteger A = new BigInteger(str); str = st.nextToken(); int b = Integer.parseInt(str); BigInteger B = new BigInteger(str); System.out.println(A.pow(b).subtract(B.pow(a))); } } |
SGU 111 – High Precision Square Root
/* HP Template is SJTU's * Square root is using manually square root * reference on baike.baidu.com */ #define MaxStrLen 1005 #define MaxAnsLen 505 HP ans[MaxAnsLen]; int ansLen; void ManualSqrt(char* s) { int strLen=strlen(s),num,l,i; ansLen = 0; HP sq,rem,di,tmp,tmp2; HP hundred,twenty,ten,one; Int2HP(100, hundred); Int2HP(20, twenty); Int2HP(10, ten); Int2HP(1, one); bool first=true; if(strLen&1) { num=s[0]-48; l=1; } else { num=(s[0]-48)*10+(s[1]-48); l=2; } // sq = (int)sqrt(num) Int2HP((int)sqrt((double)num), sq); ans[ansLen++]=sq; while(l<strLen) { Int2HP((s[l]-48)*10+s[l+1]-48, tmp); if(first) { // rem = (num-sq*sq)*100 + (s[l]-48)*10 + (s[l+1]-48) first=false; Int2HP(num, tmp2); Multi(sq,sq,rem); Subtract(tmp2, rem, rem); Multi(rem, hundred, rem); Plus(rem, tmp, rem); } else { // rem = (rem - (sq*20+di)*di)*100 + (s[l]-48)*10 + (s[l+1]-48) Multi(twenty, sq, tmp2); Plus(tmp2, di, tmp2); Multi(tmp2, di, tmp2); Subtract(rem, tmp2, rem); Multi(rem, hundred, rem); Plus(rem, tmp, rem); //sq=sq*10+di; Multi(sq, ten, sq); Plus(sq, di, sq); } //di=(rem/(20*sq)); Multi(twenty, sq, tmp2); Divide(rem, tmp2, di, tmp); while(1) { //while((sq*20+di)*di>rem) Multi(sq, twenty, tmp2); Plus(tmp2, di, tmp2); Multi(tmp2, di, tmp2); if(HPCompare(tmp2, rem) <=0) break; Subtract(di, one, di); } ans[ansLen++] = di; l+=2; } //output ans for(int i=0;i<ansLen;i++) PrintHP(ans[i]); printf("\n"); } |
SGU 110 – 3D Gemo Practice
/* Good Gemo Pratice * No reference, CSCI3260 is helpful! * Line - Sphere intersection * Point - Line distance * Reflection vector compute * WA on 6: should intersect the very first sphere in the direction */ #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define EPS 1e-9 #define feq(x,y) (fabs((x)-(y))<EPS) #define fgt(x,y) ((x)>((y)+EPS)) #define fge(x,y) (((x)+EPS)>(y)) typedef struct Pt{ double x,y,z,r; Pt(){} Pt(double x,double y,double z):x(x),y(y),z(z){} Pt operator+(const Pt&p){ return Pt(x+p.x,y+p.y,z+p.z); } Pt operator-(const Pt&p){ return Pt(x-p.x,y-p.y,z-p.z); } Pt operator*(double k){ return Pt(x*k,y*k,z*k); } double operator*(const Pt&p){ return x*p.x+y*p.y+z*p.z; } Pt operator^(const Pt&p){ return Pt(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x); } double len2(){ return x*x+y*y+z*z; } double len(){ return sqrt(len2()); } bool operator==(const Pt&p){ return feq(x,p.x)&&feq(y,p.y)&&feq(z,p.z); } void eat(){ scanf("%lf%lf%lf",&x,&y,&z); } void out(){ printf("(%lf,%lf,%lf)\n",x,y,z); } } Pt; double P2Ldist(Pt P, Pt A, Pt B) { return ((P-A)^(B-A)).len() / (B-A).len(); } bool L2Sinter(Pt A, Pt B, Pt S, Pt& insP, double& tt) { Pt norm = (B-A)*(1/(B-A).len()); double a,b,c,delta,t1,t2; a=norm.len2(); b=2*(norm*(A-S)); c=(A-S).len2()-S.r*S.r; delta = b*b - 4*a*c; t1 = (-b-sqrt(delta))/(2*a); if(fgt(t1,0)) { insP = A+norm*t1; tt = t1; return true; } else return false; } Pt newDir(Pt V, Pt N) { N = N*(1/N.len()); return V-N*(2*(V*N)); } int main() { int n,pos; double tt,mint; Pt s[55],A,B,insP,nDIR,recP; scanf("%d",&n); for(int i=1;i<=n;i++) { s[i].eat(); scanf("%lf",&s[i].r); } A.eat(); B.eat(); bool never=false; int refcnt=0; while(refcnt <= 10) { never=true; mint=1000000000; for(int i=1;i<=n;i++) { if(fge(s[i].r, P2Ldist(s[i],A,B))) if(L2Sinter(A,B,s[i],insP,tt)) { never=false; if(fgt(mint, tt)) { pos=i; recP=insP; mint=tt; } } } if(never) break; else { refcnt++; if(refcnt>10) printf("etc.\n"); else printf("%d ",pos); nDIR=newDir(B-A, recP-s[pos]); A=recP; B=A+nDIR; } } return 0; } |
SGU 108 – “Fake Prime Generator”
/* A very very very good problem * WA & MLE at least 10 times...WTF... * Need rolling array to reduce memeory to 4MB * Need pre-calc digit sum to reduce time * Cannot store whole a[MAXN] for 1..10^7 since memory is not enough * Checking while calculating and dupliated data should be handled * A problem similar to compute prime. */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; bool is[65]={0}; int digitSum[10000]={0}; int maxn, m; int r[5005],id[5005],ans[5005]; bool cmp(const int& i,const int& j) { return r[i]<r[j]; } int main() { int i; //Compute digitSum of 0-9999 for(i=0;i<10000;i++) digitSum[i]=digitSum[i/10]+i%10; while(scanf("%d %d",&maxn,&m)!=EOF) { memset(is,0,sizeof(is)); for(i=0;i<m;i++) { scanf("%d",&r[i]); id[i]=i; } sort(id,id+m,cmp); int pos=0,n=0,pr=0,tmp; for(i=1;i<=maxn;i++) { if(!is[pos]) { ++n; while(pr<m && r[id[pr]]==n) ans[id[pr++]]=i; // Same for multiple, WA: missing pr<m !!! } is[pos]=false; tmp=digitSum[i%10000]+digitSum[i/10000]; if(tmp+i<=maxn) { is[(pos+tmp)%64]=true; } pos=(pos+1)%64; } printf("%d\n",n); //Forget to output!!! WTF for(int i=0;i<m;i++) { if(i) printf(" "); printf("%d",ans[i]); } printf("\n"); } return 0; } |
SGU 107 – Numerical Tricky Problem
/* N*N%100000000 = 987654321 * (N%1000000000)*(N%1000000000) = 987654321 * First compute all the N < 1000000000, get 8 in total * Then it's simple... * 111111111 * 119357639 * 380642361 * 388888889 * 611111111 * 619357639 * 880642361 * 888888889 */ #include<cstdio> typedef __int64 LL; int main() { /* Generater for(LL i=0;i<1000000000;i++) { if(i*i%1000000000 == 987654321) printf("%I64d\n",i); } */ int n; while(scanf("%d",&n)!=EOF) { if(n<9) printf("0\n"); else if(n==9) printf("8\n"); else{ printf("72"); n=n-10; for(int i=0;i<n;i++) printf("0"); printf("\n"); } } return 0; } |
SGU 106 – extend GCD & Linear Congruence Equation
/* Extend GCD and Linear congruence equation with 2 unkonwns. * ax + by = c, has solutions iff c | gcd(a,b) * use eGCD to get ax' + by' = gcd(a,b) * x0=x'*c/gcd(a,b) * y0=y'*c/gcd(a,b) * solution is : x = x0 + b/gcd(a,b) * t * y = y0 - a/gcd(a,b) * t * for any int t */ #include<cstdio> #include<cstring> #include<cmath> typedef __int64 LL; LL egcd(LL a, LL b, LL &x, LL &y) { if(b==0) { x=1; y=0; return a; } else { LL ans = egcd(b,a%b,x,y); LL tx=x,ty=y; x=ty; y=tx-(a/b)*ty; return ans; } } LL abs(LL x) { return x>0?x:-x; } LL sign(LL x) { if(x>0) return 1; else if(x<0) return -1; return 0; } LL max(LL a, LL b) { return a>b?a:b; } LL min(LL a, LL b) { return a<b?a:b; } int main() { LL a,b,c,x1,x2,y1,y2; LL xL,xR,yL,yR,dx,dy,g,x0,y0; LL tl,tr,pl,pr,inc; while(scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&x1,&x2,&y1,&y2)!=EOF) { if(a==0&&b==0) { if(c) printf("0\n"); else printf("%I64d\n",(x2-x1+1)*(y2-y1+1)); } else if(a==0&&b!=0) { if(c%b) printf("0\n"); else if(c!=0) printf("%I64d\n",(x2-x1+1)); else printf("%d\n",((x1<=0)&&(x2>=0))?1:0); } else if(a!=0&&b==0) { if(c%a) printf("0\n"); else if(c!=0) printf("%I64d\n",(y2-y1+1)); else printf("%d\n",((y1<=0)&&(y2>=0))?1:0); } else { g=egcd(a,b,x0,y0); inc=-sign(a)*sign(b); if(-c%g) printf("0\n"); else { x0*=(-c/g); y0*=(-c/g); //printf("%I64d*%I64d + %I64d*%I64d = %I64d\n",a,x0,b,y0,-c); dx=b/g; dy=-a/g; if((x1-x0)%dx) { double tt=(x1-x0)/((double) dx); LL ttl=(LL)floor(tt); if(x0+dx*ttl>=x1) tl=ttl; LL ttr=(LL)ceil(tt); if(x0+dx*ttr>=x1) tl=ttr; } else { tl=(x1-x0)/dx; } if((x2-x0)%dx) { double tt=(x2-x0)/((double) dx); LL ttl=(LL)floor(tt); if(x0+dx*ttl<=x2) tr=ttl; LL ttr=(LL)ceil(tt); if(x0+dx*ttr<=x2) tr=ttr; } else tr=(x2-x0)/dx; if((y1-y0)%dy) { double tt=(y1-y0)/((double) dy); LL ttl=(LL)floor(tt); if(y0+dy*ttl>=y1) pl=ttl; LL ttr=(LL)ceil(tt); if(y0+dy*ttr>=y1) pl=ttr; } else { pl=(y1-y0)/dy; } if((y2-y0)%dy) { double tt=(y2-y0)/((double) dy); LL ttl=(LL)floor(tt); if(y0+dy*ttl<=y2) pr=ttl; LL ttr=(LL)ceil(tt); if(y0+dy*ttr<=y2) pr=ttr; } else pr=(y2-y0)/dy; if(inc>0) { if(y1>y0+tl*dy) { tl=pl; } if(y2<y0+tr*dy) { tr=pr; } } else { if(y1>y0+tr*dy) { tr=pl; } if(y2<y0+tl*dy) { tl=pr; } } //printf("%I64d %I64d\n",dx,dy); //printf("%I64d %I64d %I64d %I64d\n",tl,tr,pl,pr); printf("%I64d\n",max(tr,tl)-min(tr,tl)+1); } } } return 0; } |
SGU 105 – Find the pattern
/* Pattern is 0 1 1 0 1 1 0 1 1... * 0 for not divisible by 3 * 1 for divisible by 3 */ #include<cstdio> int main() { int n; while(scanf("%d",&n)!=EOF) printf("%d\n",((n/3)<<1)+((n%3)-1>0?(n%3-1):0)); return 0; } |
SGU 104 – Classical DP Problem
/* Classic DP Problem, first appear in my high school. * dp[i][j] represent the max value to put flower i in vase j. * dp[i][j] = max(dp[i-1][k]) + a[i][j] (i-1 <= k < j) * the value dp[i-1][k] can be used and reduce one for loop, i.e for(int k=i-1;k<j;k++) * put[i][j] represent the vase id of flower i-1 put. */ #include<cstdio> #include<cstring> int F,V; int a[105][105]; //appear value int dp[105][105]; int put[105][105]; void print_order(int i, int j) { if(i==0) return; print_order(i-1,put[i][j]); printf("%d",j); if(i==F) putchar('\n'); else putchar(' '); } int main() { while(scanf("%d %d",&F,&V)!=EOF) { for(int i=1;i<=F;i++) for(int j=1;j<=V;j++) scanf("%d",&a[i][j]); memset(dp,0,sizeof(dp)); for(int i=1;i<=F;i++) { int k=i-1,tmp=-(1<<29),p; for(int j=i;j<=V;j++) { while(k<j) { if(tmp<dp[i-1][k]) p=k,tmp=dp[i-1][k]; k++; } dp[i][j]=dp[i-1][p]+a[i][j]; put[i][j]=p; } } int ans=-(1<<29),p; for(int j=F;j<=V;j++) if(dp[F][j]>ans) p=j,ans=dp[F][j]; printf("%d\n",ans); print_order(F,p); } return 0; } |
SGU 102 – GCD
/* The simplest GCD function. * but not eGCD. * Need to change to LL sometimes */ int gcd(int a, int b) { return b?gcd(b,a%b):a; } |
SGU 101 – Euler Path
/* Find euler path or circle function * g[][] is the bi-directional graph * 0->6 are all the node * stack[] store the nodes in the path * adjacent nodes in stack[] form an edge * Function Call: euler(startNode x) */ void euler(int x) { for(int i=0;i<=6;i++) if(g[x][i]) // or "while(g[x][i])" both accepted { g[x][i]--; g[i][x]--; euler(i); } stack[++top]=x; } |