NOI 2000 解題報告

本文正體字版由OpenCC轉換

NOI2000的題目是[瓷片項鍊][單詞查找樹][青蛙過河][程序分析器][古城之謎][算符破譯]。[瓷片項鍊][單詞查找樹][青蛙過河][程序分析器]都是簡單題，[古城之謎]難度一般，[算符破譯]是較難。

[瓷片項鍊]是簡單的二次函數求最值的問題，數學方法可以直接解決。[單詞查找樹]是一種基本的字符串處理的數據結構。[青蛙過河]是一個遞歸的數學問題，可以求出直接的公式。[程序分析器]是個模擬題，需要細心。[古城之謎]是個動態規劃問題，但是需要對題意尤其是對範式的深入分析。[算符破譯]是個較難的搜索題，需要大量剪枝和優化。

[瓷片項鍊]

看似送分的題，有些細節需要注意。不建議枚舉保留最大值，因爲精度誤差不可避免，容易出問題。

總體積爲Vt，每片損耗爲V0，設燒製x片
則每片體積 V=Vt/x 應滿足V>V0 即x<Vt/V0
直徑 D=0.3 * sqrt(V-V0)
總長度
- L=x*D
=x * 0.3 * sqrt(Vt/x-V0)
=0.3 *sqrt( Vt * x - V0 * x^2 )

根號內部是一個二次函數，求其最值即可。當L取到最大值，有x=V/(2*V0)。

無解的條件是x的小數部分爲0.5。

/* 
 * Problem: NOI2000 ring
 * Author: Guo Jiabao
 * Time: 2009.3.8 17:11
 * State: Solved
 * Memo: 二次函數最值
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int Vt,V0,Ans;
double x,dx;
int main()
{
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	scanf("%d%d",&Vt,&V0);
	dx=floor(x=(double)Vt/V0/2);
	if (x-dx==0.5) Ans=0;
	else Ans=dx;
	printf("%dn",Ans);
	return 0;
}

[單詞查找樹]

如果學過Trie，這道題太簡單了，只需在創建新節點時計數即可。就算沒有學過Trie，通過定義和樣例也一樣能看懂，很容易搞定。

/* 
 * Problem: NOI2000 trie
 * Author: Guo Jiabao
 * Time: 2009.3.8 17:44
 * State: Solved
 * Memo: 單詞查找樹 Trie
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
struct TTrie
{
	struct Trie_node
	{
		Trie_node *c[26];
		Trie_node(){memset(c,0,sizeof(c));}
	};
	Trie_node *root;
	int cnt;
	void ins(Trie_node *&p,char *s)
	{
		if (!p) p=new Trie_node(),cnt++;
		if (*s) ins(p->c[*s-'A'],s+1);
	}
}Trie;
using namespace std;
int main()
{
	char Word[70];
	freopen("trie.in","r",stdin);
	freopen("trie.out","w",stdout);
	while (scanf("%s",Word)!=EOF)
		Trie.ins(Trie.root,Word);
	printf("%dn",Trie.cnt);
	return 0;
}

[青蛙過河]

在NOI冬令營上，吳文虎教授曾經多次把這道題當作遞歸思想的例題講授。我想這道題很不錯，需要一定的數學思維。

首先簡化問題，考慮沒有石墩的情況。我們設F[s,y]表示有s個石墩和y片荷葉，最多能跳過的青蛙個數。

顯然F[0,0]=1，F[0,1]=2，F[0,2]=3，…，可以歸納出F[0,y]=y+1。理解就是先把y只青蛙放在每片荷葉上，讓最後一隻直接跳過去，然後荷葉上的青蛙依次跳過去。

如果有石墩，假設有兩個石墩S1,S2。可以分兩步考慮，首先對於A,S1,S2，對於這個系統，讓A的一半青蛙跳到S2。然後對於 A,S1,D這個系統，把A的剩餘青蛙跳到D。最後對於S1,S2,D這個系統，把S2的青蛙跳到D。這樣恰好 F[2,0]=F[1,0]+F[1,0]。

更一般的，F[s,y]=F[s,y]*2 (s>0)，再加上F[0,y]=y+1這個關係，可以很容易地遞推出了。實際上F[s,y]可以找到直接的公式，不難證明，即F[s,y]=(y+1)*2^s。

/* 
 * Problem: NOI2000 frog
 * Author: Guo Jiabao
 * Time: 2009.3.9 20:00
 * State: Solved
 * Memo: 遞歸F[s,y]=F[s-1,y]*2 F[0,y]=y+1
*/
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
	int s,y;
	freopen("frog.in","r",stdin);
	freopen("frog.out","w",stdout);
	scanf("%d%d",&s,&y);
	printf("%dn",(y+1)*1<<s);
	return 0;
}

[程序分析器]

這道題就是一個模擬，只要能看懂範式就行了。由於有大量的訪問，建議按行號排序後使用鏈表+哈希。

對於不能正常結束的問題，有這幾種情況

跳轉到了一個未定義的行
執行完了最後一條語句，沒有遇到End
死循環

前兩個還好判斷，死循環比較棘手。事實上死循環是被證明不可判定的，對於這道題，我的方法是記錄如果執行次數大於10000000，就當作死循環終止，這顯然是不完備的，但是可以通過所有測試點。

另外NOI原數據的最後一組答案是錯的，應該是5099760。

/* 
 * Problem: NOI2000 analyser
 * Author: Guo Jiabao
 * Time: 2009.3.9 21:49
 * State: Solved
 * Memo: BNF模擬
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXS=101,MAXL=3001,PLUS=0,PRINT=1,GO=2,IFGO=3,END=4;
using namespace std;
struct statement
{
	statement *next;
	int line,var,value,goline,type;
}L[MAXS];
statement *Skip[MAXL];
int N,l,cnt=1;
int Vars[30];
inline int cmp(const void *a,const void *b)
{
	return ((statement *)a)->line-((statement *)b)->line;
}
void init()
{
	int l,i;char C[MAXL];
	freopen("analyser.in","r",stdin);
	freopen("analyser.out","w",stdout);
	while (scanf("%d",&l)!=EOF)
	{
		L[++N].line=l;
		l=getchar();
		scanf("%s",C);
		if (C[1]=='?') //print
		{
			L[N].var=C[0]-'A';
			L[N].type=PRINT;
		}
		else if (C[1]=='+') //plus
		{
			L[N].var=C[0]-'A';
			L[N].type=PLUS;
			sscanf(C+2,"%d",&l);
			L[N].value=l;
		}
		else if (C[1]=='O') //GO
		{
			L[N].type=GO;
			scanf("%d",&l);
			L[N].goline=l;
		}
		else if (C[1]=='F') //IF
		{
			l=getchar();l=getchar();
			L[N].type=IFGO;
			L[N].var=l-'A';
			l=getchar();
			scanf("%d",&l);
			L[N].value=l;
			l=getchar();l=getchar();l=getchar();l=getchar(); //<S>GO<S>
			scanf("%d",&l);
			L[N].goline=l;
		}
		else
			L[N].type=END;
	}
	qsort(L+1,N,sizeof(L[0]),cmp);
	for (i=1;i<N;i++)
	{
		L[i].next=&L[i+1];
		Skip[L[i].line]=&L[i];
	}
	Skip[L[i].line]=&L[i];
}
bool execute()
{
	for (statement *p=&L[1];p;cnt++)
	{
		if (cnt>10000000) return false;
		if (p->type==PLUS)
			Vars[p->var]+=p->value;
		else if (p->type==END)
			return true;
		else if (p->type==GO)
		{
			p=Skip[p->goline];
			continue;
		}
		else if (p->type==IFGO && Vars[p->var]==p->value)
		{
			p=Skip[p->goline];
			continue;
		}
		p=p->next;
	}
	return false;
}
int main()
{
	init();
	if (!execute())cnt=-1;
	printf("%dn",cnt);
	return 0;
}

[古城之謎]

做出這道題關鍵在於理解語法。其中名詞短語和動詞短語給出的都是遞歸定義，可以轉化爲更直觀的，<名詞短語> ::= {<輔詞>} <名詞>，<動詞短語> ::= {<輔詞>} <動詞>，也就是以一個名詞或動詞結尾，前面可以加上任意多個輔詞。而句子就是要以名詞短語開頭，後面的名詞短語和動詞短語交錯出現。

分析出語法結構，可以動態規劃。定義詞性j={0,1,2,3}。j=0表示該詞爲一個名詞，j=1表示該詞爲一個動詞，j=2表示該詞爲一個輔詞，且在它前面的最近的非輔詞爲名詞，j=3表示該詞爲一個輔詞，且在它前面的最近的非輔詞爲動詞。

狀態設定

F[i,j,k]表示，前i個字母，末尾單詞詞性爲j，組成第k個句子的最少單詞數。文章長度爲M。

狀態轉移方程

滿足文章中第[a+1,i]可以匹配一個單詞，則可以狀態轉移。i-L<=a<=i-1 且 a>=0，L爲所有單詞最大長度。

如果匹配的單詞爲名詞

F[i,0,k]=Min { F[a,j,k] + 1 | j=1或j=3, F[a,j,k-1] + 1 | j=0或j=1 }

如果匹配的單詞爲動詞

F[i,1,k]=Min { F[a,j,k] + 1 | j=0或j=2 }

如果匹配的單詞爲輔詞

F[i,2,k]=Min { F[a,j,k] + 1 | j=0或j=2 }

F[i,3,k]=Min { F[a,j,k] + 1 | j=1或j=3, F[a,j,k-1] + 1 | j=0或j=1 }

邊界條件

F[0,0,0]=0

目標結果

找到最小的k，使得Min{F[M,0,k],F[M,1,k]}有意義，則最小的句子數爲k，單詞數爲Min{F[M,0,k],F[M,1,k]}。

時間複雜度爲O(NML)，匹配單詞的時候可以用Trie樹，第三維狀態可以使用滾動數組。

/* 
 * Problem: NOI2000 lostcity
 * Author: Guo Jiabao
 * Time: 2009.3.11 14:00
 * State: Solved
 * Memo: 動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXL=22,MAXM=5002,IMP=0x7FFFFFF;
using namespace std;
struct TTrie
{
	struct Trie_node
	{
		Trie_node *c[26];
		int Wm;
		Trie_node():Wm(0){memset(c,0,sizeof(c));}
	};
	Trie_node *root;
	void ins(Trie_node *&p,int *S,int L,int Wm)
	{
		if (!p) p=new Trie_node();
		if (L==0) p->Wm|=Wm;
		else ins(p->c[*S],S+1,L-1,Wm);
	}
	int find(Trie_node *p,int *S,int L)
	{
		if (!p) return 0;
		if (L==0) return p->Wm;
		else return find(p->c[*S],S+1,L-1);
	}
}Trie;
int N,M,MaxL,Ans1,Ans2;
char Word[MAXL],Passage[MAXM];
int W[MAXL],P[MAXM],F[MAXM][4][2],Mat[MAXM][MAXL];
void init()
{
	int i,j,len,type;
	freopen("lostcity.in","r",stdin);
	freopen("lostcity.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%s",Word);
		len=strlen(Word)-2;
		if (len>MaxL) MaxL=len;
		for (j=1;j<=len;j++)
			W[j]=Word[j+1]-'a';
		if (Word[0]=='n')
			type=1;
		else if (Word[0]=='v')
			type=2;
		else
			type=4;
		Trie.ins(Trie.root,W+1,len,type);
	}
	scanf("%s",Passage);
	M=strlen(Passage)-1;
	for (j=1;j<=M;j++)
		P[j]=Passage[j-1]-'a';
	for (i=1;i<=M;i++)
		for (j=1;j<=MaxL;j++)
			Mat[i][j]=-1;
}
inline int Min(int a,int b){return a<b?a:b;}
int dynamic()
{
	int i,j,k,p;
	for (p=0;p<=1;p++)
		for (i=0;i<4;i++)
			for (j=0;j<=M;j++)
			F[j][i][p]=IMP;
	F[0][0][0]=0;
	for (k=p=1;k<=M;k++,p=!p)
	{
		for (i=1;i<=M;i++)
		{
			F[i][0][p]=F[i][1][p]=F[i][2][p]=F[i][3][p]=IMP;
			for (j=i-1;j>=i-MaxL && j>=0;j--)
			{
				if (Mat[i][i-j]==-1)
					Mat[i][i-j]=Trie.find(Trie.root,P+j+1,i-j);
				int Wm=Mat[i][i-j];
				if (Wm&1)
				{
					F[i][0][p]=Min(F[i][0][p],F[j][1][p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][3][p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][0][!p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][1][!p]+1);
				}
				if (Wm&2)
				{
					F[i][1][p]=Min(F[i][1][p],F[j][0][p]+1);
					F[i][1][p]=Min(F[i][1][p],F[j][2][p]+1);
				}
				if (Wm&4)
				{
					F[i][2][p]=Min(F[i][2][p],F[j][0][p]+1);
					F[i][2][p]=Min(F[i][2][p],F[j][2][p]+1);
					
					F[i][3][p]=Min(F[i][3][p],F[j][1][p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][3][p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][0][!p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][1][!p]+1);
				}
			}
		}
		Ans2=Min(F[M][0][p],F[M][1][p]);
		if (Ans2<IMP)
			return k;
	}
}
int main()
{
	init();
	Ans1=dynamic();
	printf("%dn%dn",Ans1,Ans2);
	return 0;
}

[算符破譯]

相當變態的搜索題，目前還沒能在1s內AC。

基本思路是先確定等號的位置，然後搜索+*的位置，最後往空檔中填數。我寫了400多行的程序，最大的數據還是5s才能過。繼續研究。

/* 
 * Problem: NOI2000 equation
 * Author: Guo Jiabao
 * Time: 2009.3.11 21:12
 * State: half-done
 * Memo: 搜索優化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=12,MAXN=1001,LETTER=15,LT=13;
const int EQUAL=-1,PLUS=-2,MULTIPLY=-3,NO=-4,UND=-5;
using namespace std;
struct equation
{
	int len;
	int s[MAXL];
}E[MAXN];
int adjl[LETTER][LETTER];
bool adjm[LETTER][LETTER];
bool ce[LETTER];//可以爲等號的字母
bool op[LETTER],appear[100],ava[LETTER],Noway=true;
bool used[LETTER],opu[2];
int Mapp[LETTER],Sp[LETTER];
int P[2][MAXL],L[2];
int N;
void print();
inline int cmp(const void *a,const void *b)
{
	return ((equation *)a)->len-((equation *)b)->len;
}
inline int Max(int a,int b)
{
	return a>b?a:b;
}
void init()
{
	int i,j;
	int te[LETTER];
	char W[MAXL];
	memset(adjm,0,sizeof(adjm));
	freopen("equation.in","r",stdin);
	freopen("equation.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=LT;i++)
		ce[i]=true;
	for (i=1;i<=N;i++)
	{
		scanf("%s",W);
		E[i].len=strlen(W);
		memset(te,0,sizeof(te));
		for (j=1;j<=E[i].len;j++)
		{
			E[i].s[j]=W[j-1]-'a'+1;
			ava[E[i].s[j]]=true;
			if (j!=1 && j!=E[i].len)
				te[E[i].s[j]]++;
			if (j>1)
				adjm[E[i].s[j]][E[i].s[j-1]]=adjm[E[i].s[j-1]][E[i].s[j]]=true;
		}
		adjm[E[i].s[1]][0]=adjm[0][E[i].s[1]]=true;
		adjm[E[i].s[E[i].s[j]]][0]=adjm[0][E[i].s[E[i].s[j]]]=true;
		for (j=1;j<=LT;j++)
			if (te[j]!=1)
			ce[j]=false;
	}
	for (i=0;i<=LT+1;i++)
	{
		for (j=0;j<=LT+1;j++)
			if (adjm[i][j])
				adjl[i][ ++adjl[i][0] ]=j;
		Mapp[i]=Sp[i]=UND;
	}
	op[0]=true;
	qsort(E+1,N,sizeof(E[0]),cmp);
}
void debug()
{
	int i,j,c;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=E[i].len;j++)
		{
			c=Mapp[E[i].s[j]];
			if (c>=0) c+='0';
			else if (c==EQUAL) c='=';
			else if (c==PLUS) c='+';
			else if (c==MULTIPLY) c='*';
			printf("%c",c);
		}
		printf("n");
	}
	printf("n");
}
void solution()
{
	int i;
	//debug();
	if (Sp[1]==UND)
		for (i=1;i<=LT;i++)
		{
			Sp[i]=Mapp[i];
			appear[Sp[i]+10]=true;
		}
	else
		for (i=1;i<=LT;i++)
			if (Sp[i]!=Mapp[i])
			{
				Sp[i]=NO;
				appear[Sp[i]+10]=true;
			}
}
int compute(int *P,int L)
{
	int stack[MAXL],top=0,i;
	for (i=1;i<=L;i++)
	{
		if (P[i]>=0)
			stack[++top]=P[i];
		else if (P[i]==MULTIPLY)
			stack[top]=stack[top]*P[++i];
	}
	for (;top>1;top--)
		stack[top-1]+=stack[top];
	return stack[1];
}
void makeequation(int p)
{
	int i,k=0,v;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;
			continue;
		}
		if (v>=0)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]*10+v;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
}
bool check(int p)
{
	int R[2];
	makeequation(p);
	R[0]=compute(P[0],L[0]);
	R[1]=compute(P[1],L[1]);
	return (R[0]==R[1]);
}
void fillequation(int p,int f)
{
	int i,k=0,v;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;f=10-f;
			continue;
		}
		if (v>=0)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]*10+f;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
}
bool limit()
{
	int i;
	int R[2];
	for (i=1;i<=N;i++)
	{
		fillequation(i,1);//左小右大
		R[0]=compute(P[0],L[0]);
		R[1]=compute(P[1],L[1]);
		if (R[0]>R[1])
			return false;
		fillequation(i,9);//左大右小
		R[0]=compute(P[0],L[0]);
		R[1]=compute(P[1],L[1]);
		if (R[0]<R[1])
			return false;
	}
	return true;
}
void computelen(int *P,int L,int &a,int &b)
{
	int stacka[MAXL],stackb[MAXL],top=0,i;
	for (i=1;i<=L;i++)
	{
		if (P[i]>=0)
		{
			stacka[++top]=P[i];
			stackb[top]=P[i];
		}
		else if (P[i]==MULTIPLY)
		{
			stacka[top]=stacka[top]+P[++i]-1;
			stackb[top]=stackb[top]+P[i];
		}
	}
	for (;top>1;top--)
	{
		stacka[top-1]=Max(stacka[top-1],stacka[top]);
		stackb[top-1]=Max(stackb[top-1],stackb[top])+1;
	}
	a=stacka[1];b=stackb[1];
}
bool lenequation(int p)
{
	int i,k=0,v,l0,l1,r0,r1;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;
			continue;
		}
		if (v>=0 || v==UND)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]+1;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
	computelen(P[0],L[0],l0,r0);
	computelen(P[1],L[1],l1,r1);
	return !(r0<l1 || r1<l0);
}
bool possible()
{
	int i;
	for (i=1;i<=N;i++)
	{
		if (!lenequation(i))
			return false;
	}
	return true;
}
void search_number(int p,int k)//第p個等式 第k個字符
{
	int i,C=E[p].s[k];
	bool rfs,lfs;

	for (i=1;i<=LT;i++)
		if (ava[i])
			if (!(Mapp[i]==Sp[i] || Sp[i]==NO))
				break;
	if (i>LT)
		return;

	if (p>N)
	{
		Noway=false;
		solution();
		return;
	}
	rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
	lfs= k==1 || Mapp[E[p].s[k-1]]<0;
	if (Mapp[C]==0 && !rfs && lfs)
		return;
	while (Mapp[C]!=UND && k<=E[p].len)
	{
		C=E[p].s[--k];
		rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
		lfs= k==1 || Mapp[E[p].s[k-1]]<0;
		if (Mapp[C]==0 && !rfs && lfs)
			return;
	}
	if (k==0)
	{
		if (check(p))
			search_number(p+1,E[p+1].len);
		return;
	}
	for (i=0;i<=9;i++)
	{
		if (used[i])
			continue;
		rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
		lfs= k==1 || Mapp[E[p].s[k-1]]!=UND;
		if (i==0 && !rfs && lfs)
			continue;
		Mapp[C]=i;
		used[i]=true;
		search_number(p,k-1);
		used[i]=false;
	}
	Mapp[C]=UND;
}
void search_operator(int k)
{
	int i,j;
	while ((!ava[k] || Mapp[k]!=UND) && k<=LT) k++;
	if (k>LT)
	{
		if (possible() && limit())
			search_number(1,E[1].len);
		return;
	}
	for (i=1;i<=adjl[k][0];i++)
	{
		j=adjl[k][i];
		if (op[j])
			break;
	}
	if (i>adjl[k][0])
	{
			op[k]=true;
			if (!opu[0])
			{
				opu[0]=true;
				Mapp[k]=PLUS;
				search_operator(k+1);
				opu[0]=false;
			}
			if (!opu[1])
			{
				opu[1]=true;
				Mapp[k]=MULTIPLY;
				search_operator(k+1);
				opu[1]=false;
			}
			op[k]=false;
			Mapp[k]=UND;
	}
	search_operator(k+1);
}
void solve()
{
	int i;
	for (i=1;i<=LT;i++)
	{
		if (ce[i] && !adjm[i][0])
		{
			op[i]=true;
			Mapp[i]=EQUAL;
			search_operator(1);
			Mapp[i]=UND;
			op[i]=false;
		}
	}
}
void print()
{
	int i,ud=0,j,other;
	for (i=1;i<=LT;i++)
	{
		if (Sp[i]==UND)
		{
			ud++;
			j=i;
		}
		if (!appear[i])
			other=i;
	}
	for (i=1;i<=LT;i++)
	{
		if (ud==1 && i==j)
		{
			int c=other-10;
			if (c==EQUAL) c='=';
			else if (c==PLUS) c='+';
			else if (c==MULTIPLY) c='*';
			else c-='+';
			printf("%c%cn",i+'a'-1,c);
			continue;
		}
		if (Sp[i]==UND || Sp[i]==NO )
			continue;
		if (Sp[i]==EQUAL) printf("%c=n",i+'a'-1);
		else if (Sp[i]==PLUS) printf("%c+n",i+'a'-1);
		else if (Sp[i]==MULTIPLY) printf("%c*n",i+'a'-1);
		else printf("%c%dn",i+'a'-1,Sp[i]);
	}
	if (Noway)
		printf("nowayn");
	exit(0);
}
int main()
{
	init();
	solve();
	print();
	return 0;
}

<h2><span class="mw-headline">瓷片項鍊 </span></h2>

原始部落用一種稀有的泥土燒製直徑相同的圓瓷片並串成項鍊，串的時候沿瓷片的直徑方向順次連接，瓷片之間沒有空隙也不重疊，一條項鍊至少由一個瓷片構成。

每個燒製的瓷片厚度是一定的，直徑D和所用泥土的體積V有以下關係：

D=0.3*(V-V0)^0.5 (V&gt;V0)

其中V0爲燒製每一片的損耗，單位與V相同。當用料小於等於V0時，不能燒製成瓷片。

例： V總 = 10，V0 = 1，若燒製成一片瓷片，V = V總= 10，D = 0.9。如果把泥土均分成2份，每份泥土的體積爲V = V總/2 = 5，單個瓷片的直徑爲 ,串起來的總長爲1.2。

給定了泥土的總體積和燒製單個瓷片的損耗，燒製的瓷片數不同，能夠得到的項鍊總長度也不相同，請計算燒製多少個瓷片能使所得到的項鍊最長。

[輸入文件]

文件僅有兩行，每一行僅包含一個整數和一個換行/回車符。第一行的數字爲泥土總體積V總 (0&lt;V總&lt;60000)，第二行爲燒製單個瓷片的損耗V0(0&lt; V0&lt;600)。

[輸出文件]

文件中僅包含一個數字和一個換行/回車符。該數字爲能獲得最長項鍊而燒製的瓷片數。如果不能燒製成瓷片或者最優解不唯一（存在兩個或者兩個以上方案均能獲得最長項鍊），輸出數字0。

[輸入輸出文件樣例1]

Input
<pre>10
1</pre>
Output
<pre>5</pre>
[輸入輸出文件樣例2]

Input
<pre>10
2</pre>
Output
<pre>0</pre>

<h2><span class="mw-headline">單詞查找樹 </span></h2>

在進行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表裏。爲了提高查找和定位的速度，通常都要畫出與單詞列表所對應的單詞查找樹，其特點如下：

根節點不包含字母，除根節點外每一個節點都僅包含一個大寫英文字母；
從根節點到某一節點，路徑上經過的字母依次連起來所構成的字母序列，稱爲該節點對應的單詞。單詞列表中的每個詞，都是該單詞查找樹某個節點所對應的單詞；

在滿足上述條件下，該單詞查找樹的節點數最少。

單詞列表對應的單詞查找樹

A
  AN
  ASP
  AS
  ASC
  ASCII
  BAS
  BASIC

對一個確定的單詞列表，請統計對應的單詞查找樹的節點數（包括根節點）

[輸入文件]

該文件爲一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。每個單詞僅由大寫的英文字符組成，長度不超過63個字符。文件總長度不超過32K，至少有一行數據。

[輸出文件]

該文件中僅包含一個整數和一個換行/回車符。該整數爲單詞列表對應的單詞查找樹的節點數。

[輸入輸出文件樣例]

Input

A
  AN
  ASP
  AS
  ASC
  ASCII
  BAS
  BASIC

Output

青蛙過河

大小各不相同的一隊青蛙站在河左岸的石墩（記爲A）上，要過到對岸的石墩(記爲D)上去。河心有幾片菏葉(分別記爲Y1…Ym)和幾個石墩(分別記爲S1…Sn)。圖示如下：

青蛙的站隊和移動方法規則如下：

每隻青蛙只能站在荷葉、石墩，或者僅比它大一號的青蛙背上（統稱爲合法的落腳點）；
一隻青蛙只有背上沒有其它青蛙的時候才能夠從一個落腳點跳到另一個落腳點；
青蛙允許從左岸A直接跳到河心的石墩、荷葉和右岸的石墩D上，允許從河心的石墩和荷葉跳到右岸的石墩D上；
青蛙在河心的石墩之間、荷葉之間以及石墩和荷葉之間可以來回跳動；
青蛙在離開左岸石墩後，不能再返回左岸；到達右岸後，不能再跳回；
假定石墩承重能力很大，允許無論多少隻青蛙都可呆在上面。但是，由於石墩的面積不大，至多隻能有一隻青蛙直接站在上面，而其他的青蛙只能依規則1落在比它大一號的青蛙的背上。
荷葉不僅面積不大，而且負重能力也有限，至多隻能有一隻青蛙站在上面。
每一步只能移動一隻青蛙，並且移動後需要滿足站隊規則；
在一開始的時候，青蛙均站在A上，最大的一隻青蛙直接站在石墩上，而其它的青蛙依規則6站在比其大一號的青蛙的背上。

青蛙希望最終能夠全部移動到D上，並完成站隊。

設河心有m片荷葉和n個石墩，請求出這隊青蛙至多有多少隻，在滿足站隊和移動規則的前提下，能從A過到D。

例如，在m=1且 n=1時，河心有一片荷葉（Y1）和一個石墩（S1），此時至多有4只青蛙能夠過河（由小到大稱爲1、2、3、4），過河的一種方法爲：

開始		1 2 3 4 A S₁ Y₁ D
Step 1	1 from A to Y₁	2 3 4 1 A S₁ Y₁ D
Step 2	2 from A to S₁	3 4 2 1 A S₁ Y₁ D
Step 3	1 from Y₁ to S₁	3 1 4 2 A S₁ Y₁ D
Step 4	3 from A to Y₁	1 4 2 3 A S₁ Y₁ D
Step 5	4 from A to D	1 2 3 4 A S₁ Y₁ D
Step 6	3 from Y₁ to D	1 3 2 4 A S₁ Y₁ D
Step 7	1 from S₁ to Y₁	3 2 1 4 A S₁ Y₁ D
Step 8	2 from S₁ to D	2 3 1 4 A S₁ Y₁ D
Step 9	1 from Y₁ to D	1 2 3 4 A S₁ Y₁ D

此例中，當河心有一片荷葉和一個石墩時，4只青蛙能夠跳動9步過河。

[輸入文件]

文件僅有兩行，每一行僅包含一個整數和一個換行/回車符。第一行的數字爲河心的石墩數n（0<=n<=25），第二行爲荷葉數m（0<=m<=25）。

[輸出文件]

文件中僅包含一個數字和一個換行/回車符。該數字爲在河心有n個石墩和m片荷葉時，最多能夠過河的青蛙的只數。

[輸入輸出文件樣例]

Input

1
  1

Output

程序分析器

Tiny Basm語言(簡稱爲TB語言)的巴科斯-瑙爾範式(BNF)爲：

<程序> ::= <語句> [CrLf] { <語句> [CrLf] }
<語句> ::= <行號> [Space] <語句體>
<語句體> ::= <累加語句> | <輸出語句> | <轉移語句> | <條件語句> | <結束語句>
<累加語句> ::= <變量> + <整數>
<輸出語句> ::= <變量> ?
<轉移語句> ::= GO [Space] <行號>
<條件語句> ::= IF [Space] <變量> = <整數> [Space] <轉移語句>
<結束語句> ::= END
<變量> ::= <字母>
<行號> ::= <整數>
<整數> ::= <數字> { <數字> }
<字母> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<數字> ::= 0|1|2|3|4|5|6|7|8|9

注：其中“::=”表示定義爲，“|”表示或，{}內的項可以重複任意多次或不出現，“[Space]”表示空格(一個字符，ASCII碼爲32)，“[CrLf]”表示回車/換行(兩個字符，ASCII碼分別爲13和10)。

錯誤語句示例(在輸入文件中不會出現任何錯誤語句)： 10[Space]A+1.5 （不符合累加語句的定義，所加的不是整數） 20[Space]A[Space]? （不符合輸出語句的定義，多加了一個空格） 30[Space]IF[Space]A=B[Space]GO[Space]10 （不符合條件語句的定義，不應變量=變量）

TB程序的執行：
程序從行號最小的一條語句開始執行，在未遇到條件語句時按行號由小至大順序執行。
所有變量在程序執行前被自動初始化爲0。
累加語句將語句中變量的值加上語句中的整數送回該變量。
輸出語句將語句中變量的值在監視器上顯示出來。
執行條件語句時，當且僅當該語句中的變量與緊跟在等號後面的整數值相等，後面的轉移語句才被執行。該語句中的所有整數值至多爲4位。
轉移語句被執行後，程序將轉去執行GO後面指定的行號的語句。
當程序執行結束語句後，結束整個程序的執行。
假設該系統能處理任意大小的整數，而不會發生溢出。

請編程，對於給定的TB語言程序P，求該程序所執行的語句數(執行條件語句不論是否成功轉移，僅記爲執行一條語句)。

[輸入文件]
輸入文件爲一個TB語言程序P，語句數不超過100行。
P中每條語句的長度不超過20個字符。
P中轉移語句裏GO後面的行號一定有對應的語句。
P中可能有多個不同行號的結束語句。
P中行號最大的語句一定是結束語句。
P中的行號都不大於3000。
輸入文件不一定是按行號遞增順序給出P的。

[輸出文件]
輸出文件有且僅有一行：
如果程序能夠正常結束，輸出該程序所執行的語句數；
如果程序不能正常結束，輸出-1。

[輸入輸出文件樣例] Input
```
10 A+1
  20 IF A=5 GO 60
  60 END
  30 A+2
  40 A?
  50 GO 20
```
Output
```
11
```
[樣例說明] 執行語句行號按順序爲 10->20->30->40->50->20->30->40->50->20->60 共11條語句被執行。

古城之謎

著名的考古學家石教授在雲夢高原上發現了一處古代城市遺址。讓教授欣喜的是在這個他稱爲冰峯城(Ice-Peak City)的城市中有12塊巨大石碑，上面刻着用某種文字書寫的資料，他稱這種文字爲冰峯文。然而當教授試圖再次找到冰峯城時，卻屢屢無功而返。

幸好當時教授把石碑上的文字都拍攝了下來，爲了解開冰峯城的祕密，教授和他的助手牛博士開始研究冰峯文，發現冰峯文只有陳述句這一種句型和名詞(n)、動詞(v)、輔詞(a)這三類單詞，且其文法很簡單：
<文章> ::= <句子> { <句子> }
<句子> ::= <陳述句>
<陳述句> ::= <名詞短語> { <動詞短語> <名詞短語> } [ <動詞短語> ]
<名詞短語> ::= <名詞> | [ <輔詞> ] <名詞短語>
<動詞短語> ::= <動詞> | [ <輔詞> ] <動詞短語>
<單詞> ::= <名詞> | <動詞> | <輔詞>

注：其中<名詞>、<動詞>和<輔詞>由詞典給出，“::=”表示定義爲，“|”表示或，{}內的項可以重複任意多次或不出現，[]內的項可以出現一次或不出現。

在研究了大量資料後，他們總結了一部冰峯文詞典，由於冰峯文恰好有26個字母，爲了研究方便，用字母a到z表示它們。

冰峯文在句子和句子之間以及單詞和單詞之間沒有任何分隔符，因此劃分單詞和句子令石教授和牛博士感到非常麻煩，於是他們想到了使用計算機來幫助解決這個問題。假設你接受了這份工作，你的第一個任務是寫一個程序，將一篇冰峯文文章劃分爲最少的句子，在這個前提下，將文章劃分爲最少的單詞。

[輸入文件]
輸入文件第1行爲詞典中的單詞數n（n<=1000）。
輸入文件第2行至第(n+1)行每行表示一個單詞，形爲“α.mot”， α表示詞性，可能是n(名詞),v（動詞）,a（輔詞）中的一個，mot爲單詞，單詞的長度不超過20。拼寫相同而詞性不同的單詞視爲不同的單詞，如輸入示例中的n.kick與v.kick是兩個不同的單詞。
輸入文件第(n+2)行爲需要劃分的文章，以“.”結束。
輸入文件中的文章確保爲冰峯文。文章是由有限個句子組成的，每個句子只包含有限個單詞。文章長度不超過5KB。

[輸出文件]
輸出文件爲兩行，每行一個整數。
輸出文件第1行爲劃分出來的句子數。
輸出文件第2行爲劃分出來的單詞數。

[輸入輸出文件樣例]

Input
```
11
  n.table
  n.baleine
  a.silly
  n.snoopy
  n.sillysnoopy
  v.is
  v.isnot
  n.kick
  v.kick
  a.big
  v.cry
  sillysnoopyisnotbigtablebaleinekicksnoopysillycry.
```
Output
```
2
  9
```
[樣例說明]

（爲了閱讀方便，劃分的單詞用空格分隔，在單詞右標出它的詞性，每行寫一個句子，用句號表示句子結束。）

輸出對應的劃分：
```
sillysnoopy[n] isnot[v] big[a] table[n].
  baleine[n] kick[v] snoopy[n] silly[a] cry[v].
```
如果用下面的劃分：
```
silly[a] snoopy[n] isnot[v] big[a] table[n].
  baleine[n] kick[v] snoopy[n] silly[a] cry[v].
```
則劃分的句子數仍爲2個，但單詞數卻多了1個，爲10個，顯然應該按前者而不是後者劃分。

算符破譯

考古學發現，幾千年前古梅文明時期的數學非常的發達，他們懂得多位數的加法和乘法，其表達式和運算規則等都與現在通常所用的方式完全相同（如整數是十進制，左邊是高位，最高位不能爲零；表達式爲中綴運算，先乘後加等），唯一的區別是其符號的寫法與現在不同。有充分的證據表明，古梅文明的數學文字一共有13個符號，與 0,1,2,3,4,5,6,7,8,9,+,*,= 這13個數字和符號（稱爲現代算符）一一對應。爲了便於標記，我們用13個小寫英文字母a,b,…m代替這些符號（稱爲古梅算符）。但是，還沒有人知道這些古梅算符和現代算符之間的具體對應關係。在一個石壁上，考古學家發現了一組用古梅算符表示的等式，根據推斷，每行有且僅有一個等號，等號左右兩邊爲運算表達式（只含有數字和符號），並且等號兩邊的計算結果相等。

假設這組等式是成立的，請編程序破譯古梅算符和現代算符之間的對應關係。

[輸入文件]
輸入文件的第一行爲等式的個數N（1<=N<=1000），以下N行每行爲一個等式。
每個等式的長度爲5個字符到11個字符。

[輸出文件]
如果不存在對應關係能夠滿足這組等式，輸出“noway”和一個換行/回車符。
如果有對應關係能夠滿足這組等式，輸出所有能夠確定的古梅算符和現代算符的對應關係。每一行有兩個字符，其中第一個字符是古梅算符，第二個字符是對應的現代算符。輸出按照字典順序排序。

[輸入輸出文件樣例]

Input
```
2
  abcdec
  cdefe
```
Output
```
a6
  b*
  d=
  f+
```
[樣例說明]

在上例中，可能對應的現代表達式爲{62=12，2=1+1}，{64=24，4=2+2}，{68=48，8=4+4}。可見，能夠確定的對應關係只有a對應6，b對應，d對應=，f對應+，應該輸出；而{c,e}雖然能夠找到對應的現代算符使得等式成立，但沒有唯一的對應關係，不能輸出。其他古梅算符{g,h…m}完全不能確定，也不能輸出。

上次修改時間 2017-05-22

青蛙過河

程序分析器

古城之謎

算符破譯

相關日誌