GCJ 2019 Qual A - Foregone Solution

面白かった

問題へのリンク

問題概要

100 桁以下の整数 が与えられる (文字列型で受け取るのがよさそう)。

• 
• も も十進法表記で '4' が登場しない

を満たすような整数 の組を 1 つ求めよ。

制約

• < <

考えたこと

繰り上がりを考えると面倒なので、繰り上がりがないように各桁ごとに独立に考えられる状態にしたい。

各桁について、

• なら、 側を 、 側に
• それ以外なら、 側を 、 側に全部

という風にして構成することにした。ただし が leading zeros を含む可能性があるので、それを除く処理を最後に行った。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

int case_num;
string N;

void solve() {
    string A = "", B = "";
    for (int i = 0; i < N.size(); ++i) {
        if (N[i] != '4') A += "0", B += N[i];
        else A += "1", B += "3";
    }
    int num = 0;
    for (int i = 0; i < A.size(); ++i) if (A[i] != '0') {
        num = i;
        break;
    }
    A = A.substr(num);
    cout << A << " " << B << endl;
}

int main() {
    cin >> case_num;
    for (int CASE = 0; CASE < case_num; ++CASE) {
        cin >> N;
 
        cout << "Case #" << CASE + 1 << ": ";
        solve();
    }
}