• <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
            色综合久久久久无码专区| 久久噜噜电影你懂的| 亚洲七七久久精品中文国产| 久久久久女教师免费一区| 香蕉久久久久久狠狠色| 色综合久久久久久久久五月| 久久亚洲欧美日本精品| 伊人伊成久久人综合网777| 日韩精品久久无码人妻中文字幕| 久久ZYZ资源站无码中文动漫| 狠狠色婷婷综合天天久久丁香| 久久久精品视频免费观看| 久久久一本精品99久久精品88| 国产精品一久久香蕉产线看| 久久国产成人| 国产精品一久久香蕉国产线看| 色婷婷综合久久久久中文字幕| 久久国产精品99精品国产| 人人狠狠综合88综合久久| 99精品国产综合久久久久五月天| 久久精品18| 91精品国产91久久久久久蜜臀 | 国产呻吟久久久久久久92| 久久精品国产久精国产一老狼| 国产香蕉97碰碰久久人人| 国产Av激情久久无码天堂 | 中文字幕乱码人妻无码久久| 久久电影网一区| 久久人人爽人人爽人人片av高请| 久久受www免费人成_看片中文| 青青青伊人色综合久久| 久久人人爽人人爽人人AV | 热久久视久久精品18| 久久国产精品国语对白| 国产高清国内精品福利99久久| 久久久久久无码Av成人影院| 亚洲精品无码久久一线| 人妻无码αv中文字幕久久琪琪布| 久久久受www免费人成| 日韩久久无码免费毛片软件| 久久一区二区免费播放|