Proficient.
Put your skills to the test.

Problem summary

Count integers X from 0 through N whose decimal digits, in their original order, can form K using concatenation, parentheses, unary minus and +, −, *, /. Every division must have an integer result.

Constraints

0 ≤ N < 100000; |K| ≤ 100000.

Worked example

An independently prepared example for this explanation.

20 6

4

Solution analysis

1. For every digit substring compute the set of all attainable integer values. A leaf may be the entire substring interpreted as a decimal integer, with either sign. Every other expression has a final binary operation splitting the substring into two nonempty consecutive parts.
2. Combine cached substring values with addition, subtraction, multiplication and exact division by a nonzero denominator. Sort and deduplicate each result set. To test a whole ticket, avoid materializing its full set: at each final split and each left value a, binary-search the required right values K−a, a−K, K/a and a/K, checking divisibility and nonzero denominators. If a=K=0, multiplication by any right expression succeeds. Only proper substrings, of at most four digits, need caching. Leading zeros in an internal concatenation have their ordinary numeric value.
3. Unary negation needs no separate closure pass: leaf sets are symmetric, and each binary combination preserves symmetry. For the example, 6, 15, 16 and 17 attain 6 through 6, 1+5, 1*6 and (−1)−(−7). Each ticket is counted only once regardless of its number of expressions.

Why it works

Induct on the number of digits. A single signed concatenation is inserted. Otherwise the root operation splits the digits into two consecutive substrings; by induction both operand values occur in their sets, and the corresponding legal operation inserts the result. Conversely each insertion is a legal expression with the correct digit order and exact divisions. Symmetry covers a minus outside any expression. Thus membership is equivalent to luck.

Watch out. Do not permit noninteger divisions, divide by zero, reorder digits, or pad a ticket with leading zeros. Internal concatenated substrings may start with zero.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
// Algorithm: For every digit substring compute the set of all attainable integer values.
using namespace std;
unordered_map<string,vector<int>>cache;
vector<int>values(const string&s){
    auto found=cache.find(s);
    if(found!=cache.end()){
        return found->second;
    }
    vector<int>result;
    int number=stoi(s);
    result.push_back(number);
    result.push_back(-number);
    for(int split=1;split<static_cast<int>(s.size());++split){
        string leftText=s.substr(0,split);
        const auto&left=values(leftText);
        string rightText=s.substr(split);
        const auto&right=values(rightText);
        for(int a:left){
            for(int b:right){
                result.push_back(a+b);
                result.push_back(a-b);
                result.push_back(a*b);
                if(b!=0&&a%b==0){
                    result.push_back(a/b);
                }
            }
        }
    }
    sort(result.begin(),result.end());
    result.erase(unique(result.begin(),result.end()),result.end());
    if(s.size()<=4){
        cache.emplace(s,result);
    }
    return result;
}
bool lucky(const string&text,int target){
    int number=stoi(text);
    if(number==target||-number==target){
        return true;
    }
    for(int split=1;split<static_cast<int>(text.size());++split){
        auto left=values(text.substr(0,split));
        auto right=values(text.substr(split));
        auto contains=[&](int value){
            return binary_search(right.begin(),right.end(),value);
        };
        for(int a:left){
            if(contains(target-a)||contains(a-target)){
                return true;
            }
            if(a==0&&target==0){
                return true;
            }
            if(a!=0&&target%a==0&&contains(target/a)){
                return true;
            }
            if(target!=0&&a%target==0&&a/target!=0&&contains(a/target)){
                return true;
            }
        }
    }
    return false;
}
int main(){
    int limit,target;
    cin>>limit>>target;
    int answer=0;
    for(int number=0;number<=limit;++number){
        string text=to_string(number);
        answer+=lucky(text,target);
    }
    cout<<answer<<'\n';
}