`Algorithm-Solution` `AcWing` 4726. 寻找数字

link

Solution

It is obvious that

• If $A$ has odd decimal-count, answer is $\mathrm{4...47...7}$
• Otherwise $A$ (even decimal-count) if greater then $\mathrm{7...74...4}$, answer is also $\mathrm{4...47...7}$
• Otherwise the answer has the same decimal-count with $a$.
  + A greedy-approach is wrong that iterate from the highest decimal if $A[i]\le 4$ then choose $4$.
  A example is $4478$, you will get the answer $4477$ using this algorithm.
  + The correct approach resembles the greedy with a additional check. For example, now you have the answer $ab?...?$ ($?$ denotes un-determined) and have $F:4s,S:7s$ unused ($F+S$ equals the count of $?$), let $Answer$ be $ab$.
  ++ If F > 0, let $T=\mathrm{7...74...4}$ where contains $S:7s$ and $(F-1):4s$, if $ab4T>A$, then let $Answer=ab4?...?$
  ++ Otherwise, $Answer=ab7?...?$

Code

void __Solve( int _test_id){
    ( void)_test_id;
    //--
    long long a;
    cin >> a;
    vector< int> bits;
    for( auto i = a; i > 0; i /= 10){
        bits.push_back( i % 10);
    }
    reverse( bits.begin(), bits.end());
    long long ans = -1;
    if( bits.size() & 1){
        ans = Form( bits.size() / 2 + 1, false);
    }
    else{
        if( a > Form( bits.size() / 2, true)){
            ans = Form( bits.size() / 2 + 1, false);
        }
        else{
            int f = bits.size() / 2, s = bits.size() / 2;
            ans = 0;
            for( auto i : bits){
                ans *= 10;
                bool choose_four = false;
                if( f > 0){
                    long long suf = 0, power = 1;
                    {
                        for(int ii = 1; ii < (s + f); ++ii){
                            power *= 10;
                        }
                        for( int ii = 0; ii < s; ++ii){
                            suf *= 10;
                            suf += 7;
                        }
                        for( int ii = 0; ii < f - 1; ++ii){
                            suf *= 10;
                            suf += 4;
                        }
                    }
                    if( (ans + 4) * power + suf >= a){
                        choose_four = true;
                    }
                }
                if( choose_four){
                    assert( f > 0);
                    -- f;
                    ans += 4;
                }
                else{
                    assert( s > 0);
                    -- s;
                    ans += 7;
                }
            }
        }
    }
    assert( ans >= a);
    cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59