Category Archives: ACM

SGU 114 – Partical Sum with Numerical Analysis

/* Partial Sum & Simple Numerical Analysis
 * We want to minimize(Sum[Pi*|Xi-d|]) and d is the TV station
 * Take the absolute away, seperate to 2 parts.
 * Min(Sum[Pi*(d-Xi)] + Sum[Pj*(Xj-d)]), for 0<i<=k, k<j<=n and Xk<=d<=Xk+1
 * Target = d*[Sum(Pi)-Sum(Pj)]-[Sum(PiXi)-Sum(Pj*Xj)]
 * Target is a linear function, its min value is either on Xk or Xk+1 depend on (Sum(Pi)-Sum(Pj)) >? 0
 * Go throughtall the k and we get the answer
 * Use Partial Sum to speed up, note that we may need long long
 * Also the original data may not be sorted.
 */
 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
typedef __int64 LL;
 
typedef struct {
	LL x,p,c;
} City;
 
City city[15005];
LL sumP[15005],sumC[15005];
int n;
 
bool cmp(const City& a, const City& b) { return a.x<b.x; }
 
int main()
{	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d %I64d",&city[i].x, &city[i].p);
		city[i].c = city[i].x * city[i].p;
	}
	sort(city+1,city+(n+1),cmp);
 
	sumP[0]=0; sumC[0]=0;
	for(int i=1;i<=n;i++)
	{
		sumP[i]=sumP[i-1]+city[i].p;
		sumC[i]=sumC[i-1]+city[i].c;
	}
 
	LL bestM=-1,bestD,A,B,tmpM;
 
	for(int k=1;k<n;k++)
	{
		A = sumP[k]-sumP[n]+sumP[k];
		B = sumC[n]-sumC[k]-sumC[k];
		if(A<0) {
			tmpM = A*city[k+1].x + B;
			if(bestM<0 || bestM > tmpM) { bestM = tmpM; bestD = city[k+1].x; }
		}
		else {
			tmpM = A*city[k].x + B;
			if(bestM<0 || bestM > tmpM) { bestM = tmpM; bestD = city[k].x; }
		}		
	}
 
	if(n==1) printf("%I64d\n",city[1].x);	//Note case with only 1 city!!
	else printf("%I64d\n",bestD);
	return 0;
}

SGU 113 – Prime check & generate

/* Speed up to check prime
 * For x < 32000, return directly
 * otherwise use generated prime(<32000) to test
 */
#include<cstdio>
#include<cstring>
 
bool is[32000]={0};
int  p[3700],pn=0;
 
bool isPrime(int x)
{
	if(x<32000) return (!is[x]);
	else for(int i=0;i<pn;i++) if(x%p[i]==0) return false;
	return true;	
}
 
int main()
{
	int n,m,i,j;
	bool flag;
 
	is[0]=is[1]=true;
	for(i=2;i<32000;i++)
		if(!is[i]) {
			p[pn++]=i;
			for(j=i+i;j<32000;j+=i) is[j]=true;
		}
 
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		flag=false;
		for(int i=0;i<pn;i++)
			if(m%p[i]==0&&isPrime(m/p[i])) { flag=true; break; }
			else if(m<p[i]*p[i]) break;
		if(flag) puts("Yes");
		else puts("No");		
	}	
	return 0;
}

SGU 112 – Java BigInteger

/* 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;
}