中学入試から：数字の個数

はじめに

本記事はNabetani様がCodeIQに出題した問題 「中学入試から：数字の個数」 の回答です。

回答例(C++11)

Boostライブラリを使ってしまったが、実際にCodeIQ上で提出する場合、標準外のライブラリを使って良いのだろうか？

count_number.cpp

// g++ -g -Wall -std=c++11 count_number.cpp
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>

using LL = long long;

LL solve(LL n, int target)
{
    LL res = 0;

    for(LL i = 1; i <= n; i *= 10) {
        const LL div = static_cast<LL>(n / (i * 10));
        const LL mod = n % (i * 10);
        if(target == 0) {
            res += ((div - 1) * i) + (i <= mod ? i : mod + 1); 
        } else {
            res += (div * i) +
                [&]() {
                    if(target * i <= mod - i) {
                        return i;
                    }   
                    if(target * i <= mod) {
                        return mod - (target * i - 1); 
                    }   
                    return 0LL;
                }();
        }   
    }   

    return res;
}

void print_result()
{
    std::ifstream ifs("./data.txt");

    if(ifs.fail()) {
        std::cerr << "Failed to read file." << std::endl;
        return;
    }

    using namespace boost;
    using namespace boost::algorithm;

    std::string line;
    std::vector<std::string> wrong_no;
    while(std::getline(ifs, line)) {
        std::vector<std::string> v1, v2;
        split(v1, line, is_any_of("\t")); split(v2, v1[1], is_any_of(","));
        const LL actual =
            solve(lexical_cast<LL>(v2[1]), lexical_cast<int>(v2[2])) -
            solve(lexical_cast<LL>(v2[0]) - 1, lexical_cast<int>(v2[2]));
        if(actual != lexical_cast<LL>(v1[2])) {
            wrong_no.push_back(v1[0]);
        }
    }

    std::cout << join(wrong_no, ",") << std::endl;
}

int main()
{
    print_result();
    return 0;
}

実装リンク集

Nabetani様のブログ に他の方の実装リンク集が載っています。興味のある方は見てみると良いかと思います。