【Tyvj1070】罗马数字

2014-05-15
竞赛题解 / 模拟
TYVJ

描述 Description

一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，以下是标准数字表:

I 1 V 5 X 10 L 50 C 100 D 500 M 1000

最多 3 个同样的可以表示为 10n 的数字 (I,X,C,M) 可以连续放在一起，表示它们的和:

III=3。CCC=300。

可表示为 5x10n 的字符 (V,L,D) 从不连续出现。

除了下一个规则，一般来说，字符以递减的顺序接连出现:

CCLXVIII = 100+100+50+10+5+1+1+1 = 268

有时，一个可表示为 10n 的数出现在一个比它大 1 级或 2 级的数前(I 在 V 或 X 前面，X 在 L 或 C 前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:

IV = 4。IX = 9。XL = 40。

一个数 用罗马数字来表示 有且仅有一种 而且不能复合嵌套使用（比如 I 是 1 X 是 10 有人可能要说 IXL 就能表示 50-10-1 但是 IXL 绝对不能用来表达 39 ） （那么 39 用什么来表示呢 XXXIX 是唯一 而且正确的选择 - -）

像 XD, IC, 和 XM 这样的表达是非法的，因为前面的数比后面的数小太多。对于 XD(490 的错误表达)，可以写成 CDXC; 对于 IC(99 的错误表达)，可以写成 XCIX; 对于 XM(990 的错误表达)，可以写成 CMXC。 90 写成 XC 而不是 LXL, 因为 L 后面的 X 意味着后继标记是 X 或者更小 (不管怎样，可能吧)（等同于阿拉伯数字 每位 数字分别表示）。

给定 N(1 <= N < 3,500)， 序言的页码数，请统计在第 1 页到第 N 页中，有几个 I 出现，几个 V 出现，等等 (从小到大的顺序)。不要输出没有出现过的字符。

比如 N = 5, 那么页码数为: I, II, III, IV, V. 总共有 7 个 I 出现，2 个 V 出现。

输入格式 InputFormat

一个整数 N。

输出格式 OutputFormat

每行一个字符和一个数字 k，表示这个字符出现了 k 次。字符必须按数字表中的递增顺序输出。

样例输入 SampleInput

2974

样例输出 SampleOutput

I 4165
V 1486
X 4447
L 1485
C 4465
D 1500
M 3225

Tyvj 1070

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct roma
{
    int s;
    char c;
}a[10000];
int i,j,t,n,m,l,r,k,z,y,x;
void tho(int x)
{
    int i,j,t;
    switch (x)
    {
        case 1:
        case 2:
        case 3:
            a[1000].s+=x;
            break;
    }
}
void hun(int x)
{
    int i,j,t;
    switch (x)
    {
        case 1:
        case 2:
        case 3:
            a[100].s+=x;
            break;
        case 4:
            a[100].s++;
        case 5:
            a[500].s++;
            break;
        case 6:
            a[100].s++;
            a[500].s++;
            break;
        case 7:
            a[100].s++;
            a[100].s++;
            a[500].s++;
            break;
        case 8:
            a[100].s++;
            a[100].s++;
            a[100].s++;
            a[500].s++;
            break;
        case 9:
            a[100].s++;
            a[1000].s++;
            break;
    }
}
void ten(int x)
{
    int i,j,t;
    switch (x)
    {
        case 1:
        case 2:
        case 3:
            a[10].s+=x;
            break;
        case 4:
            a[10].s++;
        case 5:
            a[50].s++;
            break;
        case 6:
            a[10].s++;
            a[50].s++;
            break;
        case 7:
            a[10].s++;
            a[10].s++;
            a[50].s++;
            break;
        case 8:
            a[10].s++;
            a[10].s++;
            a[10].s++;
            a[50].s++;
            break;
        case 9:
            a[10].s++;
            a[100].s++;
            break;
    }
}
void one(int x)
{
    int i,j,t;
    switch (x)
    {
        case 1:
        case 2:
        case 3:
            a[1].s+=x;
            break;
        case 4:
            a[1].s++;
        case 5:
            a[5].s++;
            break;
        case 6:
            a[1].s++;
            a[5].s++;
            break;
        case 7:
            a[1].s++;
            a[1].s++;
            a[5].s++;
            break;
        case 8:
            a[1].s++;
            a[1].s++;
            a[1].s++;
            a[5].s++;
            break;
        case 9:
            a[1].s++;
            a[10].s++;
            break;
    }
}
bool comp(roma a,roma b)
{
    return a.s>b.s;
}
int main()
{
    a[1].c='I';a[5].c='V';a[10].c='X';a[50].c='L';
    a[100].c='C';a[500].c='D';a[1000].c='M';
    scanf("%d",&n);
    for (i=1;i<=n;i++) 
    {
        tho(i/1000);
        hun((i/100)%10);
        ten((i/10)%10);
        one(i%10);
    }
    for (i=0;i<=1000;i++) if (a[i].s>0) printf("%c %d\n",a[i].c,a[i].s);
    return 0;
}