初赛#1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _MAXL 2000000
void GetN(char *s,long long &N)
{
N=0;
for (int i=0;s[i];i++)
N=N*10+(s[i]-48);
}
void print_bigint(long long n)
{
if (n>=10)
print_bigint(n/10);
printf("%d",int(n%10));
}
void Solve(long long N)
{
bool find_answer=false;
long long L,T,A1,k;
for (L=2;L<=_MAXL && L*(L-1)/2<N;L++);
for (L--;L>=2;L--)
{
T=L*(L-1)/2;
if (N>T && (N-T)%L==0)
{
find_answer=true;
A1=(N-T)/L;
for (k=0;k<L;k++)
{
if (k>0)
printf(" ");
print_bigint(A1+k);
}
printf("\n");
}
}
if (!find_answer)
printf("NONE\n");
}
int main(int argc,char *arg[])
{
long long N;
GetN(arg[1],N);
Solve(N);
return 0;
}
初赛#2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
//buf
const int bufsize=128*1024;
int bufL,bufP;
char buf[bufsize];
//segments
const int maxn=1000005;
int n;
unsigned int A[maxn],B[maxn];
//sort
const int countsize=65536;
int arcA[maxn],arcB[maxn],turnB[maxn];
int count[countsize],tmp[maxn];
//solve
unsigned int maxB[maxn],maxL[maxn];
void swap(unsigned int &a,unsigned int &b)
{
unsigned int t=a;
a=b;
b=t;
}
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
if (bufL==0)
return 0;
bufP=0;
}
return buf[bufP++];
}
bool readnumber(unsigned int &v)
{
char c;
do{
c=readchar();
if (c==0)
return false;
}while (c<'0' || c>'9');
for (v=0;c>='0' && c<='9';c=readchar())
v=v*10+(c-48);
return true;
}
void init()
{
bufL=bufP=0;
for (n=0;readnumber(A[n+1]) && readnumber(B[n+1]);)
{
n++;
if (A[n]>B[n])
swap(A[n],B[n]);
}
}
void count_sort(unsigned int A[],int arc[])
{
int i;
//lower bit
memset(count,0,sizeof(count));
for (i=1;i<=n;i++)
count[A[i]&65535]++;
for (i=1;i<countsize;i++)
count[i]+=count[i-1];
for (i=n;i>=1;i--)
tmp[count[A[i]&65535]--]=i;
//higher bit
memset(count,0,sizeof(count));
for (i=1;i<=n;i++)
count[A[i]>>16]++;
for (i=1;i<countsize;i++)
count[i]+=count[i-1];
for (i=n;i>=1;i--)
arc[tmp[i]]=(count[A[tmp[i]]>>16]--);
}
void preprocess()
{
count_sort(A,arcA);
count_sort(B,arcB);
for (int i=1;i<=n;i++)
turnB[arcB[i]]=i;
}
void checkmax(double &answer,unsigned int S,unsigned int T)
{
if (S>T)
return;
double t=double(T)-double(S)+1;
if (t>answer)
answer=t;
}
#define lowbit(n) (((n)^((n)-1))&(n))
void add_maxB(int i,unsigned int v)
{
for (;i<=n;i+=lowbit(i))
if (v>maxB[i])
maxB[i]=v;
}
void add_maxL(int i,unsigned int v)
{
i=n+1-i;
for (;i<=n;i+=lowbit(i))
if (v>maxL[i])
maxL[i]=v;
}
unsigned int get_maxB(int i)
{
unsigned int t=0;
for (;i>0;i-=lowbit(i))
if (maxB[i]>t)
t=maxB[i];
return t;
}
unsigned int get_maxL(int i)
{
i=n+1-i;
unsigned int t=0;
for (;i>0;i-=lowbit(i))
if (maxL[i]>t)
t=maxL[i];
return t;
}
void solve()
{
double answer=0;
memset(maxB,0,sizeof(maxB));
memset(maxL,0,sizeof(maxL));
for (int T=1;T<=n;T++)
{
int i=turnB[T],LA=arcA[i];
checkmax(answer,A[i],get_maxB(LA));
checkmax(answer,1 ,get_maxL(LA));
add_maxB(LA,B[i]);
add_maxL(LA,B[i]-A[i]+1);
}
printf("%0.0lf\n",answer);
}
int main()
{
freopen("input.txt","r",stdin);
init();
preprocess();
solve();
return 0;
}
初赛#3
#include <stdio.h>
#include <string.h>
#include <unistd.h>
//buf
const int bufsize=128*1024;
int bufL,bufP;
char buf[bufsize];
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
if (bufL==0)
return 0;
bufP=0;
}
return buf[bufP++];
}
//data
const int max_strlen=512*1024;
const int hashsize=30011;
struct THashPoint
{
char *s1,*s2;
THashPoint *next;
};
char lines[max_strlen],*s1,*s2;
FILE *f;
THashPoint *Hash[hashsize];
bool read_str()
{
lines[0]=0;
fgets(lines,max_strlen,f);
if (strlen(lines)>0 && lines[strlen(lines)-1]=='\n')
lines[strlen(lines)-1]=0;
if (strlen(lines)<3)
return false;
for (int i=0;lines[i];i++)
if (lines[i]==' ' || lines[i]=='\t')
{
s1=lines;
s2=lines+i+1;
lines[i]=0;
return true;
}
return false;
}
int HashTable_function(char *s)
{
int address=strlen(s)%hashsize;
for (int i=0;s[i];i++)
address=(address*107+s[i]+128)%hashsize;
return address;
}
void HashTable_Insert()
{
int address=HashTable_function(s1);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s1,s1)==0)
{
p->s2=new char[strlen(s2)+1];
strcpy(p->s2,s2);
return;
}
p=new THashPoint;
p->s1=new char[strlen(s1)+1];
p->s2=new char[strlen(s2)+1];
strcpy(p->s1,s1);
strcpy(p->s2,s2);
p->next=Hash[address];
Hash[address]=p;
}
void Print(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s1,s1)==0)
{
printf("%s",p->s2);
return;
}
printf("%s",s);
}
void Init_HashTable()
{
f=fopen("dict.txt","r");
while (read_str())
HashTable_Insert();
fclose(f);
}
int main()
{
Init_HashTable();
//Main
freopen("text.txt","r",stdin);
bufL=bufP=0;
int L=0;
for (char c;(c=readchar())!=0;)
if (c==' ' || c=='\t' || c=='\n')
{
lines[L]=0;
Print(lines);
printf("%c",c);
L=0;
}
else
lines[L++]=c;
lines[L]=0;
Print(lines);
return 0;
}
初赛#4
#include <stdio.h>
#include <string.h>
#include <unistd.h>
const int bufsize=128*1024;
int bufL;
char buf[bufsize];
struct THashPoint
{
char *s;
int c;
THashPoint *next;
};
int MemoryID=0;
THashPoint **Hash,*Memory;
char *text;
int L,HashSize,minC;
void ReadFile()
{
text=new char[bufsize+5];
L=0;
int textL=bufsize+5;
while (1)
{
bufL=read(0,buf,bufsize);
if (bufL==0)
break;
while (L+bufL>=textL)
{
char *t_text=text;
textL*=2;
text=new char[textL];
memcpy(text,t_text,L);
}
memcpy(text+L,buf,bufL);
L+=bufL;
}
text[L]=0;
}
bool Prime(int n)
{
for (int i=2;i*i<=n;i++)
if (n%i==0)
return false;
return true;
}
void Prepare()
{
int N=0,i;
for (i=0;i<L;i++)
if (text[i]==' ' || text[i]=='\t' || text[i]=='\n')
text[i]=0;
for (i=0;i<L;i++)
if ((i==0 || text[i-1]==0) && text[i]!=0)
N++;
for (HashSize=N*2+10;!Prime(HashSize);HashSize++);
Hash=new THashPoint* [HashSize];
for (i=0;i<HashSize;i++)
Hash[i]=NULL;
MemoryID=0;
Memory=new THashPoint[N+10];
}
int HashTable_function(char *s)
{
int address=strlen(s)%HashSize;
for (int i=0;s[i];i++)
address=(address*137+s[i]+128)%HashSize;
return address;
}
void HashTable_Insert(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s,s)==0)
{
p->c++;
return;
}
p=&Memory[MemoryID++];
p->s=s;
p->c=1;
p->next=Hash[address];
Hash[address]=p;
}
bool Print(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s,s)==0 && p->c==minC)
return false;
return true;
}
void Solve()
{
int i;
for (i=0;i<L;i++)
if ((i==0 || text[i-1]==0) && text[i]!=0)
HashTable_Insert(text+i);
minC=2000000000;
for (i=0;i<MemoryID;i++)
if (Memory[i].c<minC)
minC=Memory[i].c;
bool first=true;
for (i=0;i<L;i++)
if ((i==0 || text[i-1]==0) && text[i]!=0 && Print(text+i))
{
if (!first)
printf(" ");
first=false;
printf("%s",text+i);
}
}
int main()
{
freopen("corpus.txt","r",stdin);
ReadFile();
Prepare();
Solve();
return 0;
}
网上决赛#1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
const int maxn2=100000+5;
const int maxn=5000+5;
const int max_outputL=10000000;
const int oo=1000000000;
//buf
const int bufsize=256*1024;
int bufL,bufP;
char buf[bufsize];
char *bufp;
//输入图
int n2,indexID[maxn2],indexP[maxn2];
int deg2[maxn2],*G2[maxn2],*W2[maxn2];
//并查集
int father[maxn2],sortlist[maxn2];
//新建图
int n,listM[maxn],G[maxn][maxn],tG[maxn][maxn];
//输出
int outputL=0;
char outputs[max_outputL];
//最小树形图
int prev[maxn],tmpG[maxn];
bool saved[maxn],incycle[maxn];
//深度优先搜索
int DFS_count;
bool DFS_vis[maxn];
//输入数据函数
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
if (bufL==0)
return 0;
bufP=0;
}
return buf[bufP++];
}
bool Valid(char c)
{
return (c!=' ') && (c!='\t') && (c!='\n') && (c!=0);
}
bool ReadString(char *s)
{
while (1)
{
if (*bufp==0)
return false;
if (Valid(*bufp))
break;
bufp++;
}
int L=0;
for (;Valid(*bufp);bufp++)
s[L++]=*bufp;
s[L]=0;
return true;
}
void ReadLine()
{
char c;
while (1)
{
int L=0;
while (1)
{
c=readchar();
if (c=='\n' || c==0)
break;
outputs[L++]=c;
}
outputs[L]=0;
if (L>=2)
break;
}
}
//输出数据函数
void push_char(char c)
{
outputs[outputL++]=c;
}
void write(int v)
{
if (v>=10)
write(v/10);
push_char('0'+v%10);
}
//并查集函数
int getfather(int v)
{
return (father[v]==0)?v:(father[v]=getfather(father[v]));
}
void merge(int i,int j)
{
i=getfather(i);
j=getfather(j);
if (i<j)
father[j]=i;
if (j<i)
father[i]=j;
}
void ReadData()
{
int i,j,v,k;
char s[100];
ReadLine();
bufp=outputs;
ReadString(s);
for (n2=0;ReadString(s);)
{
sscanf(s,"%d",&v);
indexID[++n2]=v;
}
int maxd=0;
for (i=1;i<=n2;i++)
{
ReadLine();
bufp=outputs;
ReadString(s);
sscanf(s,"%d",&v);
for (k=1;indexID[k]!=v;k++);
//calc deg[k]
deg2[k]=0;
for (;ReadString(s);)
{
if (s[0]=='/')
continue;
sscanf(s,"%d",&v);
if (v>0)
deg2[k]++;
}
if (deg2[k]>maxd)
maxd=deg2[k];
G2[k]=new int[deg2[k]+5];
W2[k]=new int[deg2[k]+5];
//read again
bufp=outputs;
ReadString(s);
deg2[k]=0;
for (j=1;j<=n2;j++)
{
ReadString(s);
if (s[0]=='/')
continue;
sscanf(s,"%d",&v);
if (v>0)
{
G2[k][++deg2[k]]=j;
W2[k][deg2[k]]=v;
}
}
}
}
void DFS(int v)
{
if (DFS_vis[v])
return;
DFS_vis[v]=true;
DFS_count++;
for (int i=1;i<=n;i++)
if (G[v][i]<oo)
DFS(i);
}
bool process()
{
if (n==1)
{
write(listM[1]);
push_char(' ');
write(0);
push_char('\n');
return true;
}
int i,j,u,v;
int answer=oo,total;
for (int srcp=1;srcp<=n;srcp++)
{
for (u=1;u<=n;u++)
for (v=1;v<=n;v++)
G[u][v]=tG[u][v];
DFS_count=0;
for (i=1;i<=n;i++)
DFS_vis[i]=false;
DFS(srcp);
if (DFS_count<n)
continue;
total=oo;
for (i=1;i<=n;i++)
if (G[i][srcp]<total)
total=G[i][srcp];
if (total==oo)
continue;
for (i=1;i<=n;i++)
{
prev[i]=0;
saved[i]=true;
}
while (1)
{
int minCost=oo;
for (i=1;i<=n;i++) if(i!=srcp && prev[i]==0 && saved[i])
for (j=1;j<=n;j++) if (saved[j])
if (G[j][i]<minCost)
{
minCost=G[j][i];
u=j;
v=i;
}
if (minCost==oo)
break;
total+=minCost;
//insert edge (u,v)
prev[v]=u;
for (i=u;prev[i]!=0 && i!=v;i=prev[i]);
if (prev[i]==0)
continue;
//cycle
for (i=1;i<=n;i++)
incycle[i]=false;
incycle[v]=true;
for (i=u;i!=v;i=prev[i])
incycle[i]=true;
for (i=1;i<=n;i++)
tmpG[i]=oo;
for (i=1;i<=n;i++) if (saved[i] && !incycle[i])
for (j=1;j<=n;j++) if (saved[j] && incycle[j])
{
if (G[j][i]<G[v][i])
G[v][i]=G[j][i];
if (G[i][j]<oo)
{
int t=G[i][j]-G[prev[j]][j];
if (t<tmpG[i])
tmpG[i]=t;
}
}
for (i=1;i<=n;i++) if (saved[i] && !incycle[i])
if (prev[i]>0 && incycle[prev[i]])
prev[i]=v;
prev[v]=0;
for (i=u;i!=v;i=prev[i])
saved[i]=false;
for (i=1;i<=n;i++)
G[i][v]=tmpG[i];
}
if (total<answer)
answer=total;
}
if (answer==oo)
return false;
for (i=1;i<=n;i++)
{
write(listM[i]);
push_char(' ');
}
write(answer);
push_char('\n');
return true;
}
int qsort_comp(const void *p1,const void *p2)
{
int t1=*(int *)p1,t2=*(int *)p2;
if (getfather(t1)!=getfather(t2))
return getfather(t1)-getfather(t2);
return t1-t2;
}
void solve()
{
int i,j,u,v;
memset(father,0,sizeof(father));
for (i=1;i<=n2;i++)
for (j=1;j<=deg2[i];j++)
merge(i,G2[i][j]);
for (i=1;i<=n2;i++)
sortlist[i]=i;
qsort(sortlist+1,n2,sizeof(int),qsort_comp);
for (i=1;i<=n2;i=j)
if (father[sortlist[i]]==0)
{
for (j=i;j<=n2 && getfather(sortlist[i])==getfather(sortlist[j]);j++);
n=j-i;
if (n>maxn-5)
{
printf("NONE\n");
return;
}
for (v=i;v<j;v++)
{
listM[v-i+1]=indexID[sortlist[v]];
indexP[sortlist[v]]=v-i+1;
}
for (u=1;u<=n;u++)
for (v=1;v<=n;v++)
tG[u][v]=oo;
for (u=i;u<j;u++)
for (v=1;v<=deg2[sortlist[u]];v++)
tG[indexP[sortlist[u]]][indexP[G2[sortlist[u]][v]]]=W2[sortlist[u]][v];
if (!process())
{
printf("NONE\n");
return;
}
}
outputs[outputL]=0;
printf("%s",outputs);
}
int main()
{
freopen("sites.txt","r",stdin);
bufP=bufL=0;
ReadData();
solve();
return 0;
}
网上决赛#2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
const char *rules_filename="rules.txt";
const char *facts_filename="facts.txt";
const int hashsize=1000007;
const int maxm=100000+5;
const int maxn=1000000+5;
const int bufsize=256*1024;
//读入
int bufL,bufP;
char buf[bufsize];
char str[1000000];
//读入函数
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
bufP=0;
if (bufL==0)
return 0;
}
return buf[bufP++];
}
bool valid(char c)
{
return (c!=0 && c!='\t' && c!='\n' && c!=' ' && c!='&' && c!='-' && c!='>');
}
bool readstring(char *s)
{
int L=0;
char c;
do{
c=readchar();
if (c==0)
return false;
if (L==0 && c=='>')
s[L++]=c;
}while (!valid?);
for (;valid?;c=readchar())
s[L++]=c;
s[L]=0;
return true;
}
//目标变量
int goal;
//规则集合
struct TRule
{
char *rule_name;
int n,*C,A;
};
int m;
TRule Rules[maxm];
int _n,_C[1000000];
int left[maxm],nlist,list[maxm];
//命题集合
struct Tpoint
{
int v;
Tpoint *next;
};
int n;
bool fact[maxn],need_prove[maxn],org_fact[maxn];
Tpoint *Appear[maxn];
//HashTable,用于保存(命题名)->(int)的映射
struct THashTable
{
char *var;
int id;
THashTable *next;
};
THashTable *Hash[hashsize];
int find(char *s)
{
int L=strlen(s);
int address=L;
for (int i=0;s[i];i++)
address=(address*101+s[i])%hashsize;
THashTable *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->var,s)==0)
return p->id;
p=new THashTable;
p->next=Hash[address];
Hash[address]=p;
p->var=new char[L+2];
strcpy(p->var,s);
p->id=(++n);
return n;
}
void insert_Point(int v,int pp)
{
Tpoint *p=new Tpoint;
p->v=pp;
p->next=Appear[v];
Appear[v]=p;
}
void read_rules()
{
m=0;
while (1)
{
if (!readstring(str))
return;
m++;
Rules[m].rule_name=new char[strlen(str)+2];
strcpy(Rules[m].rule_name,str);
_n=0;
while (1)
{
readstring(str);
if (str[0]=='>')
{
Rules[m].A=find(str+1);
break;
}
else
_C[++_n]=find(str);
}
Rules[m].C=new int[_n+2];
Rules[m].n=_n;
for (int k=1;k<=_n;k++)
{
Rules[m].C[k]=_C[k];
insert_Point(_C[k],m);
}
}
}
void read_facts()
{
memset(fact,false,sizeof(fact));
FILE *f=fopen(facts_filename,"r");
while (fscanf(f,"%s",&str)!=-1)
fact[find(str)]=true;
fclose(f);
}
void TPsort()
{
int i,j,k;
Tpoint *p;
nlist=0;
for (i=1;i<=m;i++)
{
left[i]=0;
for (j=1;j<=Rules[i].n;j++)
if (!fact[Rules[i].C[j]])
left[i]++;
if (left[i]==0)
list[++nlist]=i;
}
for (i=1;i<=nlist;i++)
{
k=Rules[list[i]].A;
if (fact[k])
continue;
fact[k]=true;
for (p=Appear[k];p!=NULL;p=p->next)
{
left[p->v]--;
if (left[p->v]==0)
list[++nlist]=p->v;
}
}
}
void solve_data()
{
for (int i=1;i<=nlist;i++)
{
printf(" %s",Rules[list[i]].rule_name);
if (Rules[list[i]].A==goal)
break;
}
printf("\n");
}
void solve_goal()
{
int i,k;
memset(need_prove,false,sizeof(need_prove));
need_prove[goal]=true;
for (i=1;i<=nlist;i++)
if (Rules[list[i]].A==goal)
break;
for (;i>0;i--)
if (need_prove[Rules[list[i]].A] && !org_fact[Rules[list[i]].A])
{
printf(" %s",Rules[list[i]].rule_name);
for (k=1;k<=Rules[list[i]].n;k++)
need_prove[Rules[list[i]].C[k]]=true;
}
printf("\n");
}
int main(int argc,char *arg[])
{
if (argc!=3)
{
printf("Argument Error!\n");
return 0;
}
freopen(rules_filename,"r",stdin);
bufP=bufL=n=0;
memset(Hash,0,sizeof(Hash));
memset(Appear,0,sizeof(Appear));
goal=find(arg[2]);
read_rules();
read_facts();
memcpy(org_fact,fact,sizeof(fact));
if (fact[goal])
{
printf("TRUE %s\n",arg[1]);
return 0;
}
TPsort();
if (!fact[goal])
printf("UNCERTAIN\n");
else
{
printf("TRUE %s",arg[1]);
if (strcmp(arg[1],"data")==0)
solve_data();
else
solve_goal();
}
return 0;
}
总决赛
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int hashsize=70001;
const int maxnode=50000;
const int maxp=40;
const int ten[]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
const int C[]={2,3,2,3,4,3,2,3,2};
const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}};
struct Tlist
{
int data,d;
Tlist *next;
};
struct Thashpoint
{
int data;
Thashpoint *next;
};
//Memory
int ID;
Tlist listM[maxnode],*q;
Thashpoint hashM[maxnode],*p;
//data
int src,dest;
//heap
Tlist *head[maxp],*expand[maxp],*lp1,*lp2;
//Hash
Thashpoint *hash[hashsize];
//expand
int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9];
int data,G,newdata,newG;
bool find_answer;
void readdata(const char *filename,int &data)
{
int i,v;
FILE *f=fopen(filename,"r");
data=0;
for (i=0;i<9;i++)
{
fscanf(f,"%d",&v);
data=data+v*ten[i];
}
fclose(f);
}
bool check_noanswer()
{
int p[9],i,b1,b2;
bool vis[9];
for (i=0;i<9;i++)
p[i]=arcT[src/ten[i]%10];
for (b1=0; src/ten[b1]%10!=0;b1++);
for (b2=0;dest/ten[b2]%10!=0;b2++);
int countP=0;
memset(vis,false,sizeof(vis));
for (i=0;i<9;i++)
if (!vis[i])
{
countP++;
for (int k=i;!vis[k];k=p[k])
vis[k]=true;
}
return (countP-dist[b1][b2])%2==0;
}
void preprocess()
{
ID=0;
find_answer=false;
memset(hash,0,sizeof(hash));
memset(head,0,sizeof(head));
memset(expand,0,sizeof(expand));
for (int k=0;k<9;k++)
arcT[dest/ten[k]%10]=k;
for (int u=0;u<9;u++)
for (int v=0;v<9;v++)
{
dist[u][v]=abs(u/3-v/3)+abs(u%3-v%3);
swap[u][v]=ten[u]-ten[v];
}
}
void addnode()
{
if (newdata==dest)
{
printf("%d\n",depth);
find_answer=true;
return;
}
int address=newdata%hashsize;
for (p=hash[address];p!=NULL;p=p->next)
if (p->data==newdata)
return;
if (ID==maxnode)
return;
p=&hashM[ID];
p->data=newdata;
p->next=hash[address];
hash[address]=p;
q=&listM[ID];
ID++;
q->data=newdata;
q->d=depth;
if (newG>=maxp)
return;
if (newG==nowp)
{
q->next=expand[depth];
expand[depth]=q;
}
else
{
q->next=head[newG];
head[newG]=q;
}
}
void solve()
{
nowp=-1;
newdata=src;
newG=0;
for (int k=0;k<9;k++)
if (src/ten[k]%10!=0)
newG+=dist[arcT[src/ten[k]%10]][k];
depth=0;
addnode();
if (find_answer)
return;
for (int p=0;p<maxp;p++) if (head[p]!=NULL)
{
nowp=p;
for (lp1=head[p];lp1!=NULL;lp1=lp2)
{
lp2=lp1->next;
lp1->next=expand[lp1->d];
expand[lp1->d]=lp1;
}
for (int d=0;d<=p;d++)
for (;expand[d]!=NULL;)
{
data=expand[d]->data;
G=p-expand[d]->d;
depth=expand[d]->d+1;
expand[d]->d=-2;
expand[d]=expand[d]->next;
for (b=0;data/ten[b]%10!=0;b++);
for (int v=0;v<C[b];v++)
{
int u=EP[b][v];
int c=data/ten[u]%10;
newdata=data+swap[b][u]*c;
c=arcT[c];
newG=depth+G-dist[c][u]+dist[c][b];
addnode();
if (find_answer)
return;
}
}
}
printf("-1\n");
}
int main()
{
readdata("start.txt",src);
readdata("goal.txt",dest);
preprocess();
if (check_noanswer())
printf("-1\n");
else
solve();
return 0;
}