[difficulty]
3.5/103.5/103.5/10
In fact, the very simple interval dp
But I didn't have time to think about it at that time//
[title]
Let SSS be an infinite string "1145141919" spliced together to become "114514191911451419114514191919..." "11451419114514191145141919 \ cdots" "11451419114514191145141911451419114514191145141919..."
Select a prefix TTT of SSS. You can insert '(') '+' * '(' \ quad ')'\quad '+'\quad '*' '(') '+' * '' ')' + '*' in TTT to form a new string T'T'T '
The value of val(T')val(T') val(T ') conforms to the general operation rules of decimal system
Now give you a number NNN, let you find the minimum length T, s.t.val(T ') = NT, s.t.\quad val(T')=NT, s.t.val(T ') = N
If there is no such string TTT, output - 1
[data range]
1≤N≤50001\le N\le 50001≤N≤5000
[sample input]
T
N
3
520
1
2
[sample output]
6
1
2
[interpretation]
When N=520:
T=114514,T′=1+1+4+514,val(T′)=520T=114514,T'=1+1+4+514,val(T')=520T=114514,T′=1+1+4+514,val(T′)=520
[ideas]
Generally, we can see that questions with a particularly small range of data can be processed by typing tables.
Since it is thought that the inner parentheses can be added arbitrarily, for two adjacent strings S[i,k] and S[k+1,j]S[i,k] and S[k+1,j]S[i,k] and S[k+1,j]
If S[i,k]S[i,k]S[i,k] can calculate the answer Vals [I, k] ∈ Aval_{S[i,k]}\in\mathbb{A}valS[i,k]∈A
If S[k+1,j]S[k+1,j]S[k+1,j] can calculate the answer Vals [K + 1, J] ∈ Bval_{S[k+1,j]}\in\mathbb{B}valS[k+1,j]∈B
So easy to get
S[i,j]={val∣val=p+qorval=p × Q where p ∈ a and Q ∈ B}S[i,j]=\{val \mid val=p+q \quad or\quad val=p\times q \, where p\in\mathbb{A} \, and \, q\in \mathbb{B}\}S[i,j]={val ∣ Val = P + qorval = P × q. Where p ∈ A and Q ∈ B}
Other details:
Note that for an interval [i,j][i,j][i,j], there will be multiple different values, which are stored with set \ pmb{set} SetSet.
Note that when the number is greater than 5000, because there is no minus sign operation, the number will not become smaller, so do not insert it into the set
[preprocessing code]
Here NNN represents the length of the enumerated S array, not the NNN given by the title
Time complexity O (N3) × ∑∣S∣)O(n^3\times\sum|S|)O(n3 × ∑∣S∣)
I choose n=20n=20n=20 here. I can run it in one minute
/* _ __ __ _ _ | | \ \ / / | | (_) | |__ _ _ \ V /__ _ _ __ | | ___ _ | '_ \| | | | \ // _` | '_ \| | / _ \ | | |_) | |_| | | | (_| | | | | |___| __/ | |_.__/ \__, | \_/\__,_|_| |_\_____/\___|_| __/ | |___/ */ const int MAX = 20; ///In fact, just enumerate the S string with a length of 12 and open it slightly wider set<int>S[MAX][MAX]; ///set of interval DP int fir[5050]; ///Answer array int tmp[MAX]; ///Stinky S array void init(){ for(int i=1;i<=5000;++i)fir[i]=INF; tmp[1]=tmp[2]=tmp[5]=tmp[7]=tmp[9]=1; tmp[3]=tmp[6]=4; tmp[4]=5; tmp[8]=tmp[10]=9; for(int i=11;i<MAX;++i)tmp[i] = tmp[i-10]; ///The stinky S array loops for(int L=1;L<=4;++L){ ///First, deal with the value of interval S[i,j] without operator for(int i=1;i<MAX-L+1;++i){ int j = i + L - 1; int t = 0; for(int k=i;k<=j;++k){ t*=10; t+=tmp[k]; } if(t>5000)continue; S[i][j].insert(t); if(i==1)fir[t]=min(fir[t],j); } } } int main(void){ init(); for(int L=2;L<MAX;++L){ ///Interval DP enumeration interval length for(int i=1;i<MAX-L+1;++i){ ///Interval DP enumeration interval starting point int j = i + L - 1; ///Key points for(int k=i;k<j;++k){ ///Enumerate the boundaries of two intervals for(auto &It_i : S[i][k]){ for(auto &It_j : S[k+1][j]){ int add = It_i + It_j; int mul = It_i * It_j; if(add<=5000){ ///Pay attention to pruning S[i][j].insert(add); if(i==1)fir[add]=min(fir[add],j); ///Only i=1 is the prefix answer } if(mul<=5000){ ///Pay attention to pruning S[i][j].insert(mul); if(i==1)fir[mul]=min(fir[mul],j); } } } } } } for(int i=1;i<=5000;++i){ ///No solution should be output - 1. The output can be completed in the file printf("%d,",fir[i]==INF ? -1 : fir[i]); } }