首页 > ACM题库 > HDU-杭电 > HDU 2772-HOJ-Matchsticks-模拟-[解题报告]C++
2014
02-14

HDU 2772-HOJ-Matchsticks-模拟-[解题报告]C++

Matchsticks

问题描述 :

Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:

This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have.

样例输入:

4
3
6
7
15

样例输出:

7 7
6 111
8 711
108 7111111

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2772

题目大意: 用火柴拼出0到9的数字:

                   

                    数字: 1    2    3    4    5    6    7    8    9    0

                火柴数: 2    5    5    4    5    6    3    7    6    6

                 给出n条火柴,问能够拼出的数字中最小和最大分别是多少? 

解题思路: 简单的模拟题(由于数字太大,打表不了):

                  1.拼出的数字最小,就要使用 需要火柴数较多 的数字,使得这串数字总位数最小;

                  2.拼出的数字最大,则使用 需要火柴数较少 的数字,使得这串数字总位数最大:

                     看数字7和数字1,他们所需的火柴数最小,并且2和3相差1,可以凑成任意的n (n>=2) ;

                  把n=22之前的都打印出来就可以很容易的找到规律了:

                   n=2 1 1
                   n=3 7 7
                   n=4 4 11
                   n=5 2 71
                   n=6 6 111
                   n=7 8 711
                   n=8 10 1111
                   n=9 18 7111
                   n=10 22 11111
                   n=11 20 71111
                   n=12 28 111111
                   n=13 68 711111
                   n=14 88 1111111
                   n=15 108 7111111
                   n=16 188 11111111
                   n=17 200 71111111
                   n=18 208 111111111
                   n=19 288 711111111
                   n=20 688 1111111111
                   n=21 888 7111111111
                   n=22 1088 11111111111
                   n=23 1888 71111111111
                   n=24 2008 111111111111
                   n=25 2088 711111111111
                   n=26 2888 1111111111111
                   n=27 6888 7111111111111
                   n=28 8888 11111111111111
                   n=29 10888 71111111111111
                   n=30 18888 111111111111111
                   n=31 20088 711111111111111
                   n=32 20888 1111111111111111
                   n=33 28888 7111111111111111
                   n=34 68888 11111111111111111
                   n=35 88888 71111111111111111
                   n=36 108888 111111111111111111
                   n=37 188888 711111111111111111
                   n=38 200888 1111111111111111111
                   n=39 208888 7111111111111111111
                   n=40 288888 11111111111111111111
                   n=41 688888 71111111111111111111
                   n=42 888888 111111111111111111111

         最小的数:

                从15开始周期T=7,每个元素分别是108  188  200  208  288  688  888,每加一个周期多一个8;

         最大的数:

                从2开始 周期T=2,每个元素分别是1 7,每加一个周期多一个1;

代码:

#include <stdio.h>
int main()
{
    int t,n,m,i,j,temp,bs1,ys1,bs2,ys2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n<=1)
            return 0;
        if(n==2)
            printf("1 1\n");
        else if(n==3)
            printf("7 7\n");
        else if(n==4)
            printf("4 11\n");
        else if(n==5)
            printf("2 71\n");
        else if(n==6)
            printf("6 111\n");
        else if(n==7)
            printf("8 711\n");
        else if(n==8)
            printf("10 1111\n");
        else if(n==9)
            printf("18 7111\n");
        else if(n==10)
            printf("22 11111\n");
        else if(n==11)
            printf("20 71111\n");
        else if(n==12)
            printf("28 111111\n");
        else if(n==13)
            printf("68 711111\n");
        else if(n==14)
            printf("88 1111111\n");
        else
        {
            bs1=(n-15)/7;   //最大数的周期数
            ys1=(n-14)%7;   //最大数的周期中第几个元素
            if(ys1==1)
                printf("108");
            else if(ys1==2)
                printf("188");
            else if(ys1==3)
                printf("200");
            else if(ys1==4)
                printf("208");
            else if(ys1==5)
                printf("288");
            else if(ys1==6)
                printf("688");
            else if(ys1==0)
                printf("888");
            if(bs1!=0)
            while(bs1--)     //每加一个周期数多一个8
                printf("8");
            bs2=(n-2)/2;    //最小数的周期数
            ys2=n%2;        //最小数的周期中第几个元素
            printf(" ");
            if(ys2==0)
                printf("1");
            else
                printf("7");
            while(bs2--)     //梅加一个周期数多一个1
                printf("1");
            printf("\n");
        }
    }
    return 0;
}

注:原创文章,转载请注明出处

解题参考:http://blog.csdn.net/qq7366020/article/details/8619380


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢