CodeJam 2019 Q. - Forgeone Solution

CodeJam 2019 Q. - Forgeone Solution

四月 07, 2019

題目簡述

給你一個至少一位數是4的正整數 n，要你輸出兩個裡面都沒有4的正整數 a,b ，使得 \(a+b=n\)。

Test setn
Test set1\(1 < n < 10^5 \)
Test set2\(1 < n < 10^9 \)
Test set3\(1 < n < 10^{100} \)

題目傳送門

初步想法

$$
a+b = n \wedge a>0 \wedge b>0 \\
\begin{aligned}
\Rightarrow &\quad a \in [1, n/2] \wedge b \in [n/2, n) \\
or & \quad a \in [n/2, n) \wedge b \in [1, n/2]
\end{aligned}
$$
暴力窮舉 \([n/2, n)\) 內的所有 a，判斷 a 和 n-a 都沒有4就輸出答案。
時間複雜度 \( O(n)\)

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
/*
 * CodeJam 2019 Qulification Round - ForgeoneSolution
 * Author: ifTNT
 */
#include <iostream>
#include <cstdio>
using namespace std;

bool testNo4(unsigned int x){
    while(x!=0){
        if(x%10==4) return false;
        x /= 10;
    }
    return true;
}

int main(){
    int t;
    cin >> t;
    for(int it=1; it<=t; it++){
        unsigned int n;
        cin >> n;
        for(unsigned i=n/2; i<n; i++){
            if(testNo4(i)&&testNo4(n-i)){
                printf("Case #%d: %d %d\n", it, i, n-i);
                break;
            }
        }
    }
    return 0;
}

這個方法 set1 會過，set2 會 TLE，set3 超過 int 的範圍根本不用考慮。

AC 之路

仔細想一想後，發現有4的部分可以單獨抽出來，
然後再拆成 \(2 \cdot 10^k+2 \cdot 10^k\)，把前面那一項加回去抽完4的數字即可得 a,b。

e.g.
$$
\begin{aligned}
12341234 &= 12301230+40004 \\
&= 12301230+2002+2002 \\
&= 12321232+2002 \\
\end{aligned}
$$

時間複雜度 \( O(log_{10}(n))\)

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
/*
 * CodeJam 2019 Qulification Round - ForgeoneSolution
 * Author: ifTNT
 */
#include <iostream>
#include <string>
using namespace std;

int main(){
    int t;
    cin >> t;
    for(int it=1; it<=t; it++){
        string n;
        string a;
        string b;
        cin >> n;
        for(auto i:n){
            if(i-'0'==4){
                a += "2";
                b += "2";
            }else{
                a += i;
                if(b!="") b+="0";
            }
        }
        cout << "Case #" << it << ": " << a << " " << (b=="" ? "0" : b) << endl;
    }
    return 0;
}