Category Archives: SGU

SGU 125 – System of difference constraints

/* Nearly forget how to write bellman_ford...
 * System of difference constraints
 * for i-j <= t, add a edge(j,i)=t
 * add a src node and add edges (src, i)=0 for all node i
 * run bellman ford
 * a good pratice on dfs !!
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
 
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
 
int  C[5][5];
char S[5][5][6][5];
 
int B[4][4];
int n,N;
int G[10][10];
int U[100],V[100],W[100],E,D[10];
 
 
bool Bellman_Ford(int src)
{
	for(int i=0;i<=N;i++) D[i]=1<<29;
	D[src]=0;
 
	for(int i=0;i<N;i++)
		for(int j=0;j<E;j++)
			if(D[U[j]]+W[j]<D[V[j]])
				D[V[j]]=D[U[j]]+W[j];
 
	for(int j=0;j<E;j++)
		if(D[U[j]]+W[j]<D[V[j]])
			return false;
 
	int low=1<<29, high=-(1<<29);
	for(int i=0;i<N;i++)
	{
		low=min(low,D[i]);
		high=max(high,D[i]);
	}
 
	if(high-low>9) return false;
	else for(int i=0;i<N;i++) D[i]-=low;
 
	return true;
}
 
bool dfs(int now)
{
	int nx=now/n,ny=now%n;
	if(now==N) {			
		E=0;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)
				if(G[i][j]==1) U[E]=j, V[E]=i, W[E]=-1, E++; //G[i][j]==1 i<j ==> i-j<=-1
				else if(G[i][j]==0) U[E]=i, V[E]=j, W[E]=-1, E++;	//G[i][j]==0 j<i ==> j-i<=-1
			U[E]=N, V[E]=i, W[E]=0, E++;
		}
 
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<4;k++)
				{
					int tx=i+dx[k], ty=j+dy[k], tn=tx*n+ty, sn=i*n+j;
					if(tx>=0 && tx<n && ty>=0 && ty<n && G[sn][tn]==-1) {
						U[E]=sn, V[E]=tn, W[E]=0, E++;
					}
				}
		if(Bellman_Ford(N)) return true;		
		return false;
	} else {		
		int a[4],b[4],an=0,t,tx,ty,tn;
		for(int k=0;k<4;k++)
		{
			tx=nx+dx[k]; ty=ny+dy[k]; tn=tx*n+ty;
			if(tx>=0 && tx<n && ty>=0 && ty<n && G[now][tn]==-1) a[an++]=tn;		
		}
 
		if(an<B[nx][ny]) return false;
		if(B[nx][ny]==0) return dfs(now+1);
		for(int k=0;k<C[an][B[nx][ny]];k++)
		{			
			for(int i=0;i<B[nx][ny];i++)
			{
				t=S[an][B[nx][ny]][k][i]-48;		
				G[a[t]][now]=0; G[now][a[t]]=1;
			}
			if(dfs(now+1)) return true;
			for(int i=0;i<B[nx][ny];i++)
			{
				t=S[an][B[nx][ny]][k][i]-48;
				G[a[t]][now]=G[now][a[t]]=-1;
			}
		}
		return false;
	}
}
 
void init()
{
	C[1][1]=1;	strcpy(S[1][1][0],"0");
	C[2][1]=2;	strcpy(S[2][1][0],"0"); strcpy(S[2][1][1],"1");
	C[2][2]=1;	strcpy(S[2][2][0],"01");
	C[3][1]=3;	strcpy(S[3][1][0],"0"); strcpy(S[3][1][1],"1"); strcpy(S[3][1][2],"2");
	C[3][2]=3;	strcpy(S[3][2][0],"01"); strcpy(S[3][2][1],"12"); strcpy(S[3][2][2],"02");
	C[3][3]=1;  strcpy(S[3][3][0],"012");
	C[4][1]=4;  strcpy(S[4][1][0],"0"); strcpy(S[4][1][1],"1"); strcpy(S[4][1][2],"2"); strcpy(S[4][1][3],"3");
	C[4][2]=6;  strcpy(S[4][2][0],"01"); strcpy(S[4][2][1],"02"); strcpy(S[4][2][2],"03"); strcpy(S[4][2][3],"12"); strcpy(S[4][2][4],"13"); strcpy(S[4][2][5],"23");
	C[4][3]=4;  strcpy(S[4][3][0],"012"); strcpy(S[4][3][1],"013"); strcpy(S[4][3][2],"023"); strcpy(S[4][3][3],"013");
	C[4][4]=1;  strcpy(S[4][4][0],"0123");
}
 
int main()
{	
	init();
	scanf("%d",&n); N=n*n;
 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) scanf("%d",&B[i][j]);
 
	memset(G,-1,sizeof(G));
 
	if(dfs(0)) {
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				printf("%d ",D[i*n+j]);
			printf("\n");
		}
	} else {
		printf("NO SOLUTION\n");
	}
	return 0;
}

SGU 103 – Shortest Path Variant

/* Shortest Path Vairant
 * Don't be scared!!!
 * Greedy strategy is still applied.
 * Just do it!
 */
 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
int  g[305][305],it[305],bt[305],pt[305],d[305],p[305];
int  src,dst,n,m;
bool used[305];
char ic[305];
 
void Current(int nowT, int at, char &fromC, int &remC)
{
	if(nowT<it[at]) {
		fromC=ic[at];
		remC=it[at]-nowT;
	} else {
		nowT-=it[at];
		nowT%=(bt[at]+pt[at]);
		if(ic[at]=='P') {	//Careful!
			if(nowT<bt[at]) {
				fromC='B'; remC=bt[at]-nowT;
			} else {
				fromC='P'; remC=pt[at]-(nowT-bt[at]);
			}
		} else {
			if(nowT<pt[at]) {
				fromC='P'; remC=pt[at]-nowT;
			} else {
				fromC='B'; remC=bt[at]-(nowT-pt[at]);
			}
		}
	}
}
 
int calWait(int nowT, int from, int to)
{
	char fromC,toC;
	int  fromR,toR,nextFT,nextTT,nnextFT,nnextTT;
	//printf("!!%d %d %d = %d\n",nowT,from,to);
	Current(nowT,from,fromC,fromR);
	//printf("--CurrentF %d %d %c %d\n",nowT,from,fromC,fromR);
	Current(nowT,to,toC,toR);
	//printf("--CurrentT %d %d %c %d\n",nowT,to,toC,toR);
	//printf("--%d %d %d %d\n",fromC, toC, fromR, toR);
	if(fromC==toC) return 0;
	else {
		if(fromR<toR) return fromR;
		else if(fromR>toR) return toR;
		else {
			if(fromC=='B') nextFT=pt[from]; else nextFT=bt[from];
			if(fromC=='B') nnextFT=bt[from]; else nnextFT=pt[from];
			if(toC=='B') nextTT=pt[to]; else nextTT=bt[to];
			if(toC=='B') nnextTT=bt[to]; else nnextTT=pt[to];
			if(nextTT+nnextTT==nextFT+nnextFT) return -1;
			if(nextTT==nextFT) return fromR+nextFT+min(nnextFT,nnextTT);
			else return fromR+min(nextFT,nextTT);			
		}
	}
}
 
void print(int x)
{
	if(p[x]!=x) print(p[x]);
	printf("%d ",x);
}
int main()
{
	char str[100];
	int u,v,w;
	scanf("%d %d",&src,&dst);
	scanf("%d %d",&n,&m); gets(str);
	for(int i=1;i<=n;i++)
	{
		scanf("%s %d %d %d",str,&it[i],&bt[i],&pt[i]);
		ic[i]=str[0];		
	}
 
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		g[u][v]=g[v][u]=w;
	}
 
	memset(used,0,sizeof(used));
	for(int i=1;i<=n;i++) d[i]=1<<29;
	d[src]=0; p[src]=src;
	for(int cc=1;cc<n;cc++)
	{
		int md=1<<29,mp=0;
		for(int i=1;i<=n;i++)
			if(!used[i]&&d[i]<md) { md=d[i]; mp=i; }
		if(!mp) break; else used[mp]=true;
		for(int i=1;i<=n;i++) if(!used[i]&&g[mp][i])
		{
			int wait=calWait(d[mp],mp,i);
			//printf("wait=%d\n",wait);
			if(wait<0) continue;
			if(d[i]>wait+d[mp]+g[mp][i]) {
				d[i]=wait+d[mp]+g[mp][i];
				p[i]=mp;
			}
		}
	}
	//for(int i=1;i<=n;i++) printf("%d ",d[i]); printf("\n");
	if(d[dst]<(1<<29)) printf("%d\n",d[dst]);
	print(dst);
	return 0;
}

SGU 122 – Find Hamilton Cycle

/* Hamiltonian Path Finding.
 * If each vertex of a simple graph has degree >= n/2
 * There must be Hamiltonian Path/Cycle
 * Algorithm go like this:
 * Step 1: Init a path, add start point in
 * Step 2: Find any unused vertex which is reachable 
 *         BOTH from the head of the path and the tail of the path !!Attention: BOTH!!
 *         and insert it front head or after tail
 * Step 3: Continue Step2 until cannot find any more
 * Step 4: The formed path can become a cycle, i.e. path = a[1]a[2]...a[m],
           there must exist ai, s.t. edge(a[1],a[i+1]) && edge(a[i],a[m])
		   The path can be changed to a[1]...a[i]a[m]...a[i+1]a[1]
 * Step 5: If the cycle contains all the vertices, we've done.
           Otherwise, for any unused point P, there must be some edge(a[k],P)
		   Reform the cycle to be a path like Pa[k]...a[end]a[begin]..a[k-1]
 * Step 6: Go to Step 2
 *
 * Linked List are used for faster reverse and insert
 * To Reverse a linked list, simply swap each node's (Previous, Next)
 * Good Practice!
 */
bool  m[1005][1005]={0};	//Graph Map m
int   vis[1005],n;			
int L[1005],R[1005],X[1005],root,count;
void FindHamiltonCycle()	//check connectivity first
{
	memset(vis,0,sizeof(vis));
	root=count=0;
	X[++count]=1;
	L[count]=root; R[root]=count;
	L[root]=count; R[count]=root;
	vis[1]=true;
 
	bool updated;
	int  head,headPos,newHead;
	int  tail,tailPos,newTail;
	int  start,addin,temp;
	while(1)
	{		
		do {
			head=X[R[root]]; headPos=R[root]; updated=false;
			tail=X[L[root]]; tailPos=L[root]; updated=false;
			for(int i=1;i<=n;i++) if(!vis[i]&&m[head][i]&&m[tail][i])
			{
				newHead=i;				
				vis[newHead]=updated=true;
				X[++count]=newHead;
				R[count]=headPos; L[headPos]=count;				
				L[count]=root; R[root]=count; 
				break;
			}			
		} while(updated);
 
		head=X[R[root]]; tail=X[L[root]]; 
		headPos=R[root]; tailPos=L[root];
		for(int ptr=R[root];ptr!=root;ptr=R[ptr])
		{
			if(m[head][X[R[ptr]]] && m[tail][X[ptr]]) {				
				start=R[ptr];
				while(1) {
					temp=L[start];
					L[start]=R[start];
					R[start]=temp;
					if(L[start]==root) {
						L[start]=ptr;
						R[R[ptr]]=root;
						L[root]=R[ptr];
						R[ptr]=start;
						break;
					} else start=L[start];
				}				
				break;
			}
		}		
		if(count==n) break;
		else {
			for(int i=1;i<=n;i++) if(!vis[i]) { addin=i; break; };
			for(int ptr=R[root];ptr!=root;ptr=R[ptr])
			{
				if(m[X[ptr]][addin]) {		
					X[++count]=addin;					
					vis[addin]=true;
					tailPos=L[root]; headPos=R[root];	
					R[root]=count; 
					if(L[ptr]!=root) { 
						L[root]=L[ptr]; R[L[ptr]]=root;
						R[tailPos]=headPos; L[headPos]=tailPos;
					}
					L[count]=root; R[count]=ptr;
					L[ptr]=count;					
					break;
				}
			}			
		}
	}
	printAns(1);
}

SGU 120 – 2D Gemo Translation & Rotation

/* Gemo rotation and translation
 * Originally use equations to solve for center, but failed due to the precision
 * Rotation is easier
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
#define EPS 1e-6
#define feq(x,y) (fabs((x)-(y))<EPS)
#define fgt(x,y) ((x)>((y)+EPS))
#define fge(x,y) (((x)+EPS)>(y))
 
const double pi = acos(-1.0);
 
typedef struct Pt{
    double x,y;
    Pt(){}
    Pt(double x,double y):x(x),y(y){}
    Pt operator+(const Pt&p){ return Pt(x+p.x,y+p.y); }
    Pt operator-(const Pt&p){ return Pt(x-p.x,y-p.y); }
    Pt operator*(double k){ return Pt(x*k,y*k); }
    double operator*(const Pt&p){ return x*p.x+y*p.y; }
    double operator^(const Pt&p){ return x*p.y-y*p.x; }
    double len2(){ return x*x+y*y; }
    double len(){ return sqrt(len2()); }
    bool operator==(const Pt&p){ return feq(x,p.x)&&feq(y,p.y); }
    void eat(){ scanf("%lf%lf",&x,&y); }
	void out(){ printf("%.6lf %.6lf\n",feq(x,0)?0:x,feq(y,0)?0:y); }	
} Pt;
 
int N,N1,N2;
Pt p[200],Center,pN1,pN2,P;
double totalAngle, eachAngle, R;
 
Pt rotate(Pt P, double angle)
{
	double c=cos(angle);
	double s=sin(angle);
	return Pt(P.x*c+P.y*s, P.y*c-P.x*s);
}
 
int main()
{
	double halfAngle,a,b,A,B,C,D,x1,x2,y1,y2,t;
	int tmp;
	//Get Input
	scanf("%d %d %d",&N, &N1, &N2);
	if(N1 > N2) { 
		tmp=N1; N1=N2; N2=tmp; 
		pN2.eat(); pN1.eat();
	} else {
		pN1.eat(); pN2.eat();
	}
 
	//Get Radius
	totalAngle = 2*pi;
	eachAngle = totalAngle/N;	
	halfAngle = (N2-N1)*eachAngle/2;
	R = (pN1-pN2).len()/2/sin(halfAngle);
 
	//Rotate for center
	halfAngle = pi/2-halfAngle;
	P=rotate(pN2-pN1, halfAngle);
	Center = pN1 + P*(R/P.len());
 
	//printf("Get Radius = %lf\n",R);
	//printf("Get Center = "); Center.out();
 
	p[0]=pN1;
	P=pN1-Center;
	for(int i=1;i<N;i++)
	{
		//printf("before rotate P="); P.out();		
		P=rotate(P,eachAngle);
		//printf("after rotate P="); P.out();
		p[i]=Center+P;		
	}
 
	for(int i=1;i<=N;i++)
		p[(i-N1+N)%N].out();
	return 0;
}

SGU 118 – Recursion

/* Note that f(A1*A2) = f(f(A1)*f(A2))
 * and f(A1+A2) = f(f(A1)+f(A2))
 * So use recursion
 */
#include<cstdio>
int n,x[1005];
int d(int x)
{
	int s=0;
	while(x>0) s+=x%10, x/=10;
	if(s<10) return s;
	else return d(s);
}
int f(int i)
{
	if(i==n-1) return d(x[i]);
	else return d(d(x[i])*d(1+f(i+1)));
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++) scanf("%d",x+i);
		printf("%d\n",f(0));
	}
	return 0;
}

SGU 117 – Big Mod

// compute (x^m)%k 
int pow(int x,int m, int k)
{
	if(m==0) return 1;
	else if(m&1) return pow(x,m-1,k)*x%k;
	else {
		int t=pow(x,m/2,k);
		return t*t%k;
	}
}

SGU 116 – Prime Generate & DP

/* Prime Generate and DP
 * Good Pratice, remember to see the output format!
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
bool is[10005]={0};
int  superPrime[205],pn=0,spn=0;
int  n,k;
 
bool dp[10005]={0};
int  num[10005],pre[10005],ans[10005],an=0;
 
void getAns(int now, int before)
{
	if(now==0) return;
	ans[an++]=now-before;
	getAns(before,pre[before]);
}
 
int main()
{
	/* Prime Gen */
	is[0]=is[1]=true;
	for(int i=2;i<=10000;i++)
		if(!is[i]) {
			++pn;
			if(!is[pn]) superPrime[spn++]=i;
			for(int j=i+i;j<=10000;j+=i) is[j]=true;
		}
 
	/* DP Start */
	scanf("%d",&n);
	dp[0]=true;
	num[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<spn;j++)
		{
			k=i-superPrime[j];
			if(k>=0 && dp[k]) {				
				if(dp[i]==false) { dp[i]=true; num[i]=num[k]+1; pre[i]=k; }
				else if(num[i] > num[k]+1) { num[i]=num[k]+1; pre[i]=k; }
			} else 
			if(k<0) break;
		}
 
	/* Output*/
	if(dp[n]) {
		printf("%d\n",num[n]);
		an=0;
		getAns(n,pre[n]);
		sort(ans,ans+an);
		for(int i=an-1;i>=0;i--)
			if(i) printf("%d ",ans[i]);
			else printf("%d\n",ans[i]);
	} else puts("0");
	return 0;
}

SGU 115 – Zeller’s formular

/* Compute the day name in a week by dd/mm/yyyy
 * Zeller Formular
 * c : century, first 2 bits of year
 * y : year   , last  2 bits of year
 * m : month  , if(m<3) m=m+12, y=y-1
 * d : days   
 * return : 1-6 for Mon, Tue, Wed ..., 0 for Sun.
 */
#include<cstdio>
 
int allow[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};	//only for 2001. typo WA here...WTF
int getWeek(int c, int y, int m, int d)
{
	return  (y + y/4 + c/4 - 2*c + (26*(m+1))/10 + d - 1)%7;
}
 
int main()
{
	int n,m,t;
	scanf("%d %d",&n,&m);	
	if(m>12 || n<1 || m<1 || n>allow[m]) printf("Impossible\n");
	else {
		if(m<3) t=getWeek(20,00,m+12,n);
		else t=getWeek(20,01,m,n);		
		if(t>0) printf("%d\n",t);
		else if(t<0) printf("%d\n",t+7);
		else printf("7\n");
	}
	return 0;
}

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