• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 21, comments - 2, trackbacks - 0, articles - 0

            ZOJ Monthly, May 2011 .Problem B

            Posted on 2011-05-01 17:21 acpeng 閱讀(425) 評論(0)  編輯 收藏 引用 所屬分類: ACM程序
            ZOJ Monthly, May 2011 .Problem B:Roman Order:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3501


            Roman numerals are based on seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000.

            Symbols are iterated to produce multiples of the decimal (1, 10, 100, 1,000) values, with V, L, D substituted for a multiple of five, and the iteration continuing: I "1", II "2", III "3", V "5", VI "6", VII "7", etc., and the same for other bases: X "10", XX "20", XXX "30", L "50", LXXX "80"; CC "200", DCC "700", etc. At the fourth iteration, a subtractive principle is employed, with the base placed before the higher base: IV for "4", IX for "9", XL for "40", XC for "90", CD for "400", CM for "900".

            The basic multiples of Roman numerals thus follow a pattern:

            ×1 ×2 ×3 ×4 ×5 ×6 ×7 ×8 ×9
            Ones I II III IV V VI VII VIII IX
            Tens X XX XXX XL L LX LXX LXXX XC
            Hundreds C CC CCC CD D DC DCC DCCC CM
            Thousands M MM MMM

            A practical way to write a Roman number is to consider the modern Arabic numeral system, and separately convert the thousands, hundreds, tens, and ones as given in the chart above. So, for instance, 1234 may be thought of as "one thousand and two hundreds and three tens and four", obtaining M (one thousand) + CC (two hundreds) + XXX (thirty) + IV (four), for MCCXXXIV. Thus eleven is XI (ten and one), 29 is XXIX (twenty and nine), and 2011 is MMXI (two thousand and ten and one). Note that the subtractive principle is not extended beyond the chart: for example, IL is not used for 49, rather this should be written as forty (XL) and nine (IX), or XLIX.

            Given a list of numbers, you are to rearrange them so that if we write them as Roman numbers, they are in lexicographical order.

            Input

            There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.

            Each test case starts with an integer 1 ≤ n ≤ 10000. Then n numbers 0 < ai < 4000.

            Output

            For each test case, output the n numbers in specified order.

            Sample Input

            3
            3
            1 2 3
            7
            1 5 10 50 100 500 1000
            11
            4 5 6 7 8 9 10 11 12 13 14
            

            Sample Output

            1 2 3
            100 500 1 50 1000 5 10
            4 9 5 6 7 8 10 11 12 13 14
            代碼:
             1#include<stdio.h>
             2#include<string.h>
             3#include<algorithm>
             4using namespace std;
             5char strHundreds[10][5]={"C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
             6char strTens[10][5]={"X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
             7char strOnes[10][5]={"I","II","III","IV","V","VI","VII","VIII","IX"};
             8char strThousands[4][4]={"M","MM","MMM"};
             9typedef struct node
            10{
            11    char str[20];
            12    int flg;
            13}
            NODE;
            14NODE data[10005];
            15int num[10005]={0};
            16int cmp(NODE b, NODE c)
            17{
            18    if(strcmp(b.str,c.str)<0)
            19        return 1;
            20    else
            21        return 0;
            22}

            23int main()
            24{
            25    int i,T,n,num_temp_a;
            26    char tmp[20]="\0";
            27    scanf("%d",&T);
            28    while(T--)
            29    {
            30        scanf("%d",&n);
            31        for(i=0;i<n;i++)
            32        {
            33            scanf("%d",&num[i]);
            34            num_temp_a=num[i];
            35            if(num_temp_a/1000!=0)
            36            {
            37                strcat(tmp,strThousands[num_temp_a/1000-1]);
            38                num_temp_a=num_temp_a%1000;
            39            }

            40            if(num_temp_a/100!=0)
            41            {
            42                strcat(tmp,strHundreds[num_temp_a/100-1]);
            43                num_temp_a=num_temp_a%100;
            44            }

            45            if(num_temp_a/10!=0)
            46            {
            47                strcat(tmp,strTens[num_temp_a/10-1]);
            48                num_temp_a=num_temp_a%10;
            49            }

            50            if(num_temp_a!=0)
            51            {
            52                strcat(tmp,strOnes[num_temp_a-1]);
            53            }

            54            strcpy(data[i].str,tmp);
            55            data[i].flg=i;
            56            memset(tmp,0,sizeof(tmp));
            57        }

            58        sort(data,data+n,cmp);
            59        printf("%d",num[data[0].flg]);
            60        for(i=1;i<n;i++)
            61            printf(" %d",num[data[i].flg]);
            62        printf("\n");
            63    }

            64    return 0;
            65}

            66
            精品久久久久中文字| 国产精品久久久久久吹潮| 老男人久久青草av高清| 无码任你躁久久久久久久| 日本加勒比久久精品| 四虎国产精品免费久久| 三级三级久久三级久久| 久久久久亚洲av无码专区喷水| 国产精品一久久香蕉产线看| 久久久精品视频免费观看| 久久久精品2019免费观看| 2020最新久久久视精品爱 | 色欲综合久久躁天天躁蜜桃| 久久精品麻豆日日躁夜夜躁| 大美女久久久久久j久久| 亚洲午夜无码久久久久| 亚洲午夜久久久| 91久久精品国产免费直播| 久久中文字幕人妻熟av女| 秋霞久久国产精品电影院| 97久久精品人妻人人搡人人玩| 久久久久久av无码免费看大片| 人妻精品久久无码区| 伊人久久综合精品无码AV专区 | 国产精品99久久久久久www| 久久久久久精品无码人妻| 日日狠狠久久偷偷色综合0| 久久福利青草精品资源站| 亚洲AV日韩AV永久无码久久| 久久国产乱子伦精品免费午夜| 国产精品久久久久久久| 久久这里只有精品首页| 一级做a爰片久久毛片免费陪| 亚洲精品高清久久| 94久久国产乱子伦精品免费| 国产欧美一区二区久久| 精品国产乱码久久久久久郑州公司| 亚洲中文字幕无码久久精品1| 精品国产日韩久久亚洲| 亚洲国产综合久久天堂 | 色综合合久久天天综合绕视看 |