SRM385 Div2 500

問題

ワープロで、その行にある文字列をなるべく等間隔で並べる処理をする。
その行の幅widthとその行にある文字列wordsが与えられる。
文字列の間にはgapと呼ばれるいくつかのスペースが与えられる。その行のすべてのgapは最大のスペース数と最小のスペース数が1以下でなければならない。
ここでは、スペースの代わりに"_"を用いて確認する。
文字数がwidthであるような、wordsの間にgapを含む文字列の中で辞書順で最初のものを返す。

考え方

gapの組み合わせは差が1以下で、全体でwidthの長さにならないといけないので、

int s1 = a/(words.size()-1);
int n1 = (words.size()-1) - a%(words.size()-1);
int s2 = a/(words.size()-1) + 1;
int n2 = a%(words.size()-1);

スペース数がs1なものがn1個とスペース数がs2(=s1+1)なものがn2個いれなければならない。
このs1とs2をどこにいれるかについて9!すべての組み合わせを(next_permutationなどで)試して辞書順が最小となるものを探せばよい。