题目描述
题目要求将一行文本（由单词组成，单词间用一个空格分隔）重新格式化为指定长度（以点dot\texttt{dot}dot为单位）。每个字符有固定宽度（单位：点），空格（即单词间的分隔）宽度可变，用于填充以对齐左右边界。需要输出格式化后的行，其中单词内的字母间隔用固定点数（由规则计算），单词间的间隔用填充点数。输出格式中，字母间的间隔用/(n)表示，单词间的间隔用/后跟点数表示。要求行首行尾不能有空白点。
输入格式
输入包含多组测试用例，每组两行：
- 第一行：目标长度NNN（N≤5000N \le 5000N≤5000）。
- 第二行：原始文本（单词间用单个空格分隔，无首尾空格，至少两个单词，总字符数≤80\le 80≤80）。
最后以一行0 SYMIBAA结束（不处理）。
输出格式
对于每组输入，输出一行格式化后的文本，格式如A/(4)I/(4)M/(18)S/...。
样例
输入
250 AIM SSY ABABA 200 SSSS AAAA 130 AA B AA 0 SYMIBAA输出
A/(4)I/(4)M/(18)S/(4)S/(4)Y/(19)A/(4)B/(4)A/(4)B/(4)A/ S/(7)S/(7)S/(7)S/(22)A/(7)A/(7)A/(7)A A/(5)A/(15)B/(16)A/(5)A题目分析
本题的核心是计算字符宽度，确定字母间隔和单词间隔的填充点数。
字符宽度表
| 字符 | 宽度 |
|---|---|
| A | 18 |
| B | 17 |
| I | 10 |
| M | 20 |
| S | 16 |
| Y | 13 |
| 空格 | 可变 |
字母间隔规则
- 单词内相邻字母的最小间隔为333点。
- 字母间隔点数 =⌊单词间隔点数/3⌋\lfloor \text{单词间隔点数} / 3 \rfloor⌊单词间隔点数/3⌋，但不得小于333？实际规则：字母间隔由单词间隔决定，且至少为333。具体计算时，先确定单词间隔的基准值，再按比例分配。
单词间隔规则
- 单词间的最小间隔为101010点，无上限。
- 总点数NNN减去所有字符宽度之和后，剩余点数用于单词间的间隔填充。这些间隔点数应尽量平均分配，多余的从行末开始逐个加111。
算法步骤
- 计算所有字符的宽度总和（不包括空格），记为charSum\textit{charSum}charSum。
- 设单词数为www，则单词间有w−1w-1w−1个间隔。
- 设字母间隔的总点数为L=(w−1)×letterGapL = (w-1) \times \text{letterGap}L=(w−1)×letterGap，其中letterGap\text{letterGap}letterGap为每个字母间隔的点数。
- 设单词间隔的总点数为S=(w−1)×wordGapS = (w-1) \times \text{wordGap}S=(w−1)×wordGap。
- 总点数N=charSum+L+SN = \textit{charSum} + L + SN=charSum+L+S。
- 已知letterGap=⌊wordGap/3⌋\text{letterGap} = \lfloor \text{wordGap} / 3 \rfloorletterGap=⌊wordGap/3⌋，且letterGap≥3\text{letterGap} \ge 3letterGap≥3，wordGap≥10\text{wordGap} \ge 10wordGap≥10。
- 枚举wordGap\text{wordGap}wordGap从101010开始递增，计算letterGap\text{letterGap}letterGap，检查是否满足等式。由于NNN不大，直接枚举可行。
输出格式
- 字母间：
A/(4)表示在 A 和下一个字母之间有444个点。 - 单词间：
S/后跟点数，但注意单词间的点数已经包含在字母间隔计算中？实际上，输出中单词间的分隔符是/(n)吗？从样例看，单词间直接用/后跟数字表示，没有字母。但A/(4)I/(4)M/(18)S/...中的S/实际上是单词 S 后的间隔？需要仔细分析。
复杂度分析
枚举wordGap\text{wordGap}wordGap至多N/10N/10N/10次，可接受。
代码实现
// Filling the Gaps// UVa ID: 552// Verdict: Accepted// Submission Date: 2017-05-11// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intvisited[65536];voidbacktrack(inti,intv,string&pattern){if(i>=pattern.length())visited[v]=1;else{v*=2;if(pattern[i]=='*'){backtrack(i+1,v,pattern);backtrack(i+1,v+1,pattern);}else{v+=pattern[i]-'0';backtrack(i+1,v,pattern);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intlength,n;while(cin>>length>>n){if(length==0&&n==0){cout<<"YES 0\n";break;}vector<string>words;vector<int>ids;string word;for(inti=1;i<=n;i++){cin>>word;intid=0;for(intj=0;j<word.size();j++){id*=2;if(word[j]=='*')id+=1;}words.push_back(word);ids.push_back(id);}sort(ids.begin(),ids.end());boolduplicated=false;for(inti=0;i<ids.size()-1;i++)if(ids[i]==ids[i+1]){duplicated=true;break;}if(duplicated){cout<<"NO\n";continue;}memset(visited,0,sizeof(visited));for(inti=0;i<words.size();i++)backtrack(0,0,words[i]);inttotal=pow(2,length),appeared=0;for(inti=0;i<total;i++)appeared+=visited[i];cout<<"YES "<<appeared<<'\n';}return0;}