• <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 閱讀(424) 評論(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精品成人片| 久久综合久久性久99毛片| 欧美久久久久久精选9999| 99久久香蕉国产线看观香| 免费久久人人爽人人爽av| 久久精品人人做人人爽97 | 久久久艹| 色婷婷久久综合中文久久蜜桃av| 久久国产精品一区二区| 久久毛片一区二区| 久久91亚洲人成电影网站| 久久夜色撩人精品国产| 久久久久久人妻无码| 蜜臀久久99精品久久久久久| 亚洲国产另类久久久精品| 精品久久久久久久久久久久久久久| 久久精品一区二区三区AV| 中文字幕久久欲求不满| 国产色综合久久无码有码| 国产精品久久久久久久久久免费| 久久天天躁狠狠躁夜夜avapp| 国产精品久久自在自线观看| 久久99热这里只有精品66| 国产亚州精品女人久久久久久 | 国产AⅤ精品一区二区三区久久| 亚洲级αV无码毛片久久精品| 18禁黄久久久AAA片| 久久国产热这里只有精品| 99久久精品毛片免费播放| 久久天堂AV综合合色蜜桃网| 伊人色综合九久久天天蜜桃| 久久国产高清一区二区三区| 嫩草影院久久国产精品| 久久福利青草精品资源站免费| 中文精品久久久久人妻不卡| 久久精品国产精品亚洲精品 | 精品久久人人妻人人做精品| 久久se精品一区精品二区| 国内精品久久久久久久97牛牛|