• <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
            久久成人国产精品二三区| 国内精品久久国产| 99久久无码一区人妻| 免费一级做a爰片久久毛片潮| 久久久久亚洲AV无码专区网站| 精品久久久久久久久免费影院| 国内精品久久久久久99| 久久精品国产精品亚洲人人 | 999久久久免费精品国产| 99热精品久久只有精品| 无码久久精品国产亚洲Av影片| 精品综合久久久久久88小说| 囯产极品美女高潮无套久久久| 国产成人精品综合久久久| 久久久久久精品免费免费自慰| 亚洲狠狠久久综合一区77777 | 国产AⅤ精品一区二区三区久久 | 2019久久久高清456| 久久国产V一级毛多内射| 精品久久一区二区| 久久精品欧美日韩精品| 97久久国产露脸精品国产| 久久精品国产亚洲Aⅴ蜜臀色欲| 精品无码久久久久久午夜| 久久AV高潮AV无码AV| 欧洲国产伦久久久久久久| 国产亚洲精午夜久久久久久| 亚洲国产精品久久久久| 久久免费小视频| 亚洲国产成人久久综合野外| 国产精品免费久久| 久久AⅤ人妻少妇嫩草影院| 欧美久久精品一级c片片| 国产精品久久久久无码av| 国产精品9999久久久久| 99久久久国产精品免费无卡顿| 久久综合狠狠综合久久综合88| 奇米影视7777久久精品| 国产成人久久AV免费| 色综合久久最新中文字幕| 狠狠久久综合伊人不卡|