1426: 2.2.1 Preface Numbering 序言页码

题目描述

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

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

最多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

This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).
像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).

给定N(1 <= N < 3,500)， 序言的页码数，请统计在第1页到第N页中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出并没有出现过的字符。
比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。

输入

一个整数N。

输出

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

样例输入

5

样例输出

I 7
V 2

参考代码

#include <stdio.h>
#include <string.h>
#define MAX 3500
int orgin_num[7]={1,5,10,50,100,500,1000};
int minus_num[6]={4,9,40,90,400,900};
int num[MAX][7];
int orgin(int a,int cnt,int n) 
{
    int i;
    for (i=0;i<7;i++) 
    {
        if(a==orgin_num[i]) 
        {
            num[n][i]+=cnt;
            return 1;
        }
    }
    return 0;
}
int minus(int a,int cnt,int n) 
{
    int i;
    for (i=0;i<6;i++) 
    {
        if(a==minus_num[i]) 
        {
            if(i==0 || i==1) 
            {
                num[n][0]+=cnt;
                if(i==0)
                                    num[n][1]+=cnt; else
                                    num[n][2]+=cnt;
            }
            if(i==2 || i==3) 
            {
                num[n][2]+=cnt;
                if(i==2)
                                    num[n][3]+=cnt; else
                                    num[n][4]+=cnt;
            }
            if(i==4 || i==5) 
            {
                num[n][4]+=cnt;
                if(i==4)
                                    num[n][5]+=cnt; else
                                    num[n][6]+=cnt;
            }
            return 1;
        }
    }
    return 0;
}
int highest(int a) 
{
    int t=0;
    while(a/10) 
    {
        a/=10;
        t++;
    }
    while(t) 
    {
        a*=10;
        t--;
    }
    return a;
}
void play(int n) 
{
    int i,t,a=n,start;
    for (i=6;i>=0;i--) 
    {
        if(a>=orgin_num[i]) 
        {
            start=highest(a);
            if(minus(start,1,n))
                            a-=start;
            t=a/orgin_num[i];
            a%=orgin_num[i];
            orgin(orgin_num[i],t,n);
        }
    }
}
int main() 
{
    int n,i,j;
    for (i=1;i<=MAX;i++) 
    {
        play(i);
        for (j=0;j<7;j++)
                    num[i][j]+=num[i-1][j];
    }
    while(scanf("%d",&n)!=EOF) 
    {
        for (i=0;i<7;i++) 
        {
            if(num[n][i]!=0) 
            {
                if(i==0)
                                    printf("I ");
                if(i==1)
                                    printf("V ");
                if(i==2)
                                    printf("X ");
                if(i==3)
                                    printf("L ");
                if(i==4)
                                    printf("C ");
                if(i==5)
                                    printf("D ");
                if(i==6)
                                    printf("M ");
                printf("%dn",num[n][i]);
            }
        }
    }
    return 0;
}

解析

暂无