TopCoder SRM 464 Div1 Easy ColorfulStrings
問題
数字からなる文字列の積を、その各桁の積とする。
数字からなる文字列がcolorfulであるとは、
(空でない)連続する部分文字列の積が、全て互いに異なることを言う。
n桁のcolorfulな文字列のうち、k番目に小さいものを求めよ。
n桁のcolorfulな文字列がk個未満の場合は空文字列を出力せよ。
制約条件
n≦50
k≦10^9
方針
同じ数字が2度出てきたらその時点でcolorfulではなくなるため、9桁以上のcolorfulな文字列は存在しない。
8桁以下のcolorfulである文字列は全探索により求められる。
総数はそんなに多くないので愚直に探索して間に合う。
1桁の場合だけ0と1が使えることに注意する。
ソースコード
vector<string> v; void rec(string s,int n){ if(s.size()==n){ v.pb(s); return; } for(char c='2';c<='9';c++){ string t=s+c; set<int> S; rep(i,t.size()){ int p=1; for(int j=i;j<t.size();j++){ p*=t[j]-'0'; if(S.count(p))goto FAIL; S.insert(p); } } rec(t,n); FAIL:; } } class ColorfulStrings { public: string getKth(int n, int k) { if(n>8)return ""; if(n==1)return k<11?string(1,'0'+k-1):""; v.clear(); rec("",n); return v.size()>=k?v[k-1]:""; } };