• <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
            国产精品久久久久影视不卡| 少妇人妻88久久中文字幕| 国内精品久久久久久野外| 久久91精品久久91综合| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 狠狠色丁香婷综合久久| 91精品婷婷国产综合久久| 久久精品国产亚洲AV忘忧草18| 久久亚洲精品成人av无码网站| 色成年激情久久综合| A级毛片无码久久精品免费| 久久不射电影网| 国产美女亚洲精品久久久综合| 国产精品久久久久久影院| 日本精品久久久久影院日本 | 久久精品夜色噜噜亚洲A∨| 久久久亚洲裙底偷窥综合| 94久久国产乱子伦精品免费| 久久亚洲日韩看片无码| 久久精品国产99国产精品| 久久99国产精一区二区三区| 久久亚洲精品国产亚洲老地址| 天天久久狠狠色综合| 亚洲午夜久久久久久久久久 | 久久91综合国产91久久精品 | 狠狠狠色丁香婷婷综合久久俺| 亚洲国产精品无码久久九九| 国产叼嘿久久精品久久| 2020久久精品国产免费| 无码精品久久久天天影视| 欧美大战日韩91综合一区婷婷久久青草| 激情伊人五月天久久综合| 久久精品水蜜桃av综合天堂| 久久久久亚洲AV片无码下载蜜桃| 精品久久国产一区二区三区香蕉| 99久久精品国产一区二区| 国产成人精品综合久久久| 97精品伊人久久久大香线蕉| 偷偷做久久久久网站| 久久久久久久97| 蜜臀久久99精品久久久久久小说 |