USACO 2.2.1 Preface Numbering 羅馬數字轉換 preface
本文正體字版由OpenCC轉換
相信許多人遇到這道題都暈了，羅馬數字的規則的確太複雜了。想了解羅馬數字的看這裏： 羅馬數字介紹
理解簡單的（題目上3500以內）羅馬數字轉化規則後再看這道題會發現它並不難，就是將1..n的每個十進制阿拉伯數字轉化成相應的羅馬數字串，然後統計每個字母出現的次數就可以了。
關鍵在於轉化阿拉伯數字（其實較大的羅馬數字轉化很複雜，而題中3500以內的羅馬數字轉化還是比較簡單的，所以只討論如何轉化3500以內的羅馬數字）。
轉化有以下規則： 1、數較大部分在前，較小部分在後 2、表示10整倍數的字母(I X C M)最多可以累加三次 3、要累加4次的數應該將比該數的字母稍大的表示5整倍數或是10的整倍數的字母在後，累加的字母在前(例如IV XL CD CM)
瞭解以上規則後發現並不需要實際“轉化”出羅馬數字，而只用統計每個字母出現的次數。可以用遞歸解決問題了。
/*
ID: cmykrgb1
PROG: preface
LANG: C++
*/
#include <stdio.h>
#include <string.h>
FILE *fi,*fo;
static char ch[7]={'I','V','X','L','C','D','M'};
long int t[100];
void getrome(int n)
{
if (n>=1000) //M
{
t['M']++;
getrome(n-1000);
}else
if (n>=900) //CM
{
t['C']++;
t['M']++;
getrome(n-900);
}
else
if (n>=500)
{
t['D']++;
getrome(n-500);
}
else
if (n>=400)
{
t['C']++;
t['D']++;
getrome(n-400);
}
else
if (n>=100)
{
t['C']++;
getrome(n-100);
}
else
if (n>=90)
{
t['X']++;
t['C']++;
getrome(n-90);
}
else
if (n>=50)
{
t['L']++;
getrome(n-50);
}
else
if (n>=40)
{
t['X']++;
t['L']++;
getrome(n-40);
}
else
if (n>=10)
{
t['X']++;
getrome(n-10);
}
else
if (n>=9)
{
t['I']++;
t['X']++;
getrome(n-9);
}
else
if (n>=5)
{
t['V']++;
getrome(n-5);
}
else
if (n>=4)
{
t['I']++;
t['V']++;
getrome(n-4);
}
else
if (n>=1)
{
t['I']++;
getrome(n-1);
}
}
int main(void)
{
int n,i;char c;
fi=fopen("preface.in","r");
fo=fopen("preface.out","w");
fscanf(fi,"%d",&n);
fclose(fi);
for (i=1;i<=n;i++)
getrome(i);
for (i=0;i<=6;i++)
if (t[ch[i]]>0)
fprintf(fo,"%c %ldn",ch[i],t[ch[i]]);
fclose(fo);
return 0;
}
上次修改時間 2017-05-17