USACO 2.2 Preface Numbering

Simple brutal force approach can pass the tests. We iterate through the numbers, for each number converting the numerical value of the number to Roman number representation and then counting.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <unordered_map>

using namespace std;

int N;

string intToRoman(int num) {
    int numbers[13] = {1000, 900, 500, 400, 100, 90, 50, 40,
        10, 9, 5, 4, 1};
    const char *roman[13] = {"M", "CM", "D", "CD", "C", "XC",
        "L", "XL", "X", "IX", "V", "IV", "I"};
    string result = "";
    for (int i = 0; i < 13; ++i) {
        while (num >= numbers[i]) {
            num -= numbers[i];
            result += roman[i];
        }
    }

    return result;
}

struct cmp {
    cmp() {
        char nums[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        for (int i = 0; i < 7; ++i) {
            map[nums[i]] = i;
        }
    }
    bool operator()(char a, char b) {
        return map[a] < map[b];
    }

    unordered_map<char, int> map;
};

int main() {
    ifstream fin("preface.in");
    ofstream fout("preface.out");

    fin >> N;
    map<char, int, cmp> mp;
    for (int i = 1; i <= N; ++i) {
        string num = intToRoman(i);
        for (auto &c : num) {
            mp[c]++;
        }
    }

    for (map<char, int>::iterator iter = mp.begin(); iter != mp.end(); ++iter) {
        fout << iter->first << " " << iter->second << endl;
    }
}