Platinum Partner

CodeJam 2009

/*
File name - A.cpp 

*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

//BEGINTEMPLATE_BY_ACRUSH_TOPCODER
#define SIZE(X) ((int)(X.size()))//NOTES:SIZE(
#define LENGTH(X) ((int)(X.length()))//NOTES:LENGTH(
#define MP(X,Y) make_pair(X,Y)//NOTES:MP(
typedef long long int64;//NOTES:int64
typedef unsigned long long uint64;//NOTES:uint64
#define two(X) (1<<(X))//NOTES:two(
#define twoL(X) (((int64)(1))<<(X))//NOTES:twoL(
#define contain(S,X) (((S)&two(X))!=0)//NOTES:contain(
#define containL(S,X) (((S)&twoL(X))!=0)//NOTES:containL(
const double pi=acos(-1.0);//NOTES:pi
const double eps=1e-11;//NOTES:eps
template inline void checkmin(T &a,T b){if(b inline void checkmax(T &a,T b){if(b>a) a=b;}//NOTES:checkmax(
template inline T sqr(T x){return x*x;}//NOTES:sqr
typedef pair ipair;//NOTES:ipair
template inline T lowbit(T n){return (n^(n-1))&n;}//NOTES:lowbit(
template inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}//NOTES:countbit(
//Numberic Functions
template inline T gcd(T a,T b)//NOTES:gcd(
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template inline T lcm(T a,T b)//NOTES:lcm(
  {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
template inline T euclide(T a,T b,T &x,T &y)//NOTES:euclide(
  {if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;}
   if(b<0){T d=euclide(a,-b,x,y);y=-y;return d;}
   if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,x,y);T t=x;x=y;y=t-(a/b)*y;return d;}}
template inline vector > factorize(T n)//NOTES:factorize(
  {vector > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));}
   i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;}
template inline bool isPrimeNumber(T n)//NOTES:isPrimeNumber(
  {if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
template inline T eularFunction(T n)//NOTES:eularFunction(
  {vector > R=factorize(n);T r=n;for (int i=0;i inline void showMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:showMatrix(
  {for (int i=0;i inline T checkMod(T n,T m) {return (n%m+m)%m;}//NOTES:checkMod(
template inline void identityMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:identityMatrix(
  {for (int i=0;i inline void addMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addMatrix(
  {for (int i=0;i inline void subMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subMatrix(
  {for (int i=0;i inline void mulMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulMatrix(
  { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
  for (int i=0;i inline void addModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addModMatrix(
  {for (int i=0;i inline void subModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subModMatrix(
  {for (int i=0;i inline T multiplyMod(T a,T b,T m) {return (T)((((int64)(a)*(int64)(b)%(int64)(m))+(int64)(m))%(int64)(m));}//NOTES:multiplyMod(
template inline void mulModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulModMatrix(
  { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
  for (int i=0;i inline T powerMod(T p,int e,T m)//NOTES:powerMod(
  {if(e==0)return 1%m;else if(e%2==0){T t=powerMod(p,e/2,m);return multiplyMod(t,t,m);}else return multiplyMod(powerMod(p,e-1,m),p,m);}
//Point&Line
double dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}//NOTES:dist(
double distR(double x1,double y1,double x2,double y2){return sqr(x1-x2)+sqr(y1-y2);}//NOTES:distR(
template T cross(T x0,T y0,T x1,T y1,T x2,T y2){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//NOTES:cross(
int crossOper(double x0,double y0,double x1,double y1,double x2,double y2)//NOTES:crossOper(
  {double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return 0;return (t<0)?-1:1;}
bool isIntersect(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)//NOTES:isIntersect(
  {return crossOper(x1,y1,x2,y2,x3,y3)*crossOper(x1,y1,x2,y2,x4,y4)<0 && crossOper(x3,y3,x4,y4,x1,y1)*crossOper(x3,y3,x4,y4,x2,y2)<0;}
bool isMiddle(double s,double m,double t){return fabs(s-m)<=eps || fabs(t-m)<=eps || (s='A' && c<='Z';}//NOTES:isUpperCase(
bool isLowerCase(char c){return c>='a' && c<='z';}//NOTES:isLowerCase(
bool isLetter(char c){return c>='A' && c<='Z' || c>='a' && c<='z';}//NOTES:isLetter(
bool isDigit(char c){return c>='0' && c<='9';}//NOTES:isDigit(
char toLowerCase(char c){return (isUpperCase(c))?(c+32):c;}//NOTES:toLowerCase(
char toUpperCase(char c){return (isLowerCase(c))?(c-32):c;}//NOTES:toUpperCase(
template string toString(T n){ostringstream ost;ost<>r;return r;}//NOTES:toInt(
int64 toInt64(string s){int64 r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toInt64(
double toDouble(string s){double r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toDouble(
template void stoa(string s,int &n,T A[]){n=0;istringstream sin(s);for(T v;sin>>v;A[n++]=v);}//NOTES:stoa(
template void atos(int n,T A[],string &s){ostringstream sout;for(int i=0;i0)sout<<' ';sout< void atov(int n,T A[],vector &vi){vi.clear();for (int i=0;i void vtoa(vector vi,int &n,T A[]){n=vi.size();for (int i=0;i void stov(string s,vector &vi){vi.clear();istringstream sin(s);for(T v;sin>>v;vi.push_bakc(v));}//NOTES:stov(
template void vtos(vector vi,string &s){ostringstream sout;for (int i=0;i0)sout<<' ';sout< struct Fraction{T a,b;Fraction(T a=0,T b=1);string toString();};//NOTES:Fraction
  template Fraction::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
  template string Fraction::toString(){ostringstream sout;sout< Fraction operator+(Fraction p,Fraction q){return Fraction(p.a*q.b+q.a*p.b,p.b*q.b);}
  template Fraction operator-(Fraction p,Fraction q){return Fraction(p.a*q.b-q.a*p.b,p.b*q.b);}
  template Fraction operator*(Fraction p,Fraction q){return Fraction(p.a*q.a,p.b*q.b);}
  template Fraction operator/(Fraction p,Fraction q){return Fraction(p.a*q.b,p.b*q.a);}
//ENDTEMPLATE_BY_ACRUSH_TOPCODER

const int oo=10000000;
const int maxsize=20+5;
const int M=2000;
const int MX[]={-1,1,0,0};
const int MY[]={0,0,-1,1};

int size;
char G[maxsize][maxsize];
int D[maxsize][maxsize][M+M+1];
int sizeQ,Q[maxsize*maxsize*(M+M+1)];
bool visited[maxsize][maxsize][M+M+1];
string R[maxsize][maxsize][M+M+1];

void addnode(int x,int y,int v,int d)
{
	if (abs(v)>M) return;
	if (D[x][y][v+M]>=0) return;
	D[x][y][v+M]=d;
	Q[sizeQ++]=x+y*size+(v+M)*size*size;
}
string construct(int x,int y,int value)
{
	if (visited[x][y][value+M]) return R[x][y][value+M];
	visited[x][y][value+M]=true;
	string &ret=R[x][y][value+M];
	if (D[x][y][value+M]==1) 
		return ret=string(1,G[x][y]);
	ret=string(D[x][y][value+M],char(126));
	for (int d1=0;d1<4;d1++)
	{
		int x2=x+MX[d1];
		int y2=y+MY[d1];
		if (x2>=0 && x2=0 && y2=0 && x3=0 && y3=0 && D[x3][y3][oldvalue+M]+2==D[x][y][value+M])
					{
						string t=construct(x3,y3,oldvalue);
						t+=G[x2][y2];
						t+=G[x][y];
						if (t=0 && x2=0 && y2=0 && x3=0 && y30;cnt--)
		{
			int key;
			scanf("%d",&key);
			int minL=1000000000;
			for (int x=0;x=0)
					checkmin(minL,D[x][y][key+M]);
			string r=string(minL,char(126));
			for (int x=0;x
{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}