Description
在数字界有一类被叫做幸运数的数，其实幸运数的组成很简单。如果一个数所有位数上的数字都是4或7的话就叫做幸运数。比如444444, 44747是幸运数而57774747就不是。

现在mwy遇到了一个小问题，他只知道一个幸运数所有位数上数字之和，他想知道这个数最小会是多少，聪明如你，快来帮帮我们的mwy吧。

Input
输入一个数n（n<=300）。

Output
如果可以找到这样的幸运数，就输出这个幸运数，否则就输出-1。

Samples
input
12
output
444

设4的数目为x，7的数目为y，
则有 4x + 7y = n

根据“中国剩余定理”
4x + 7y = n
4(x+y) + 3y = n
(x+y) + 3(x+y+y) = n
故而 { x+y=n, x+y+y=0 } 是其一组解
化简 { x+y=n, x+y+y=0 } 得 { x=2n, y=-n }

写直观些：
x = 2n-0*7, 2n-1*7, 2n-2*7, 2n-3*7, ……, 2n-i*7
y = -n+0*4, -n+1*4, -n+2*4, -n+3*4, ……, -n+i*4

根据题目要求，x与y必须是非负数，x尽可能的小。
即 2n-i*7 >= 0
化简为 i <= 2n/7

分析完毕后，代码就简单了

#include <stdio.h>

int main( void )
{
    unsigned n;
    scanf( "%u", &n );

    const unsigned i = 2*n/7;
    for( size_t j=0; j!=2*n-i*7; ++j )
        putchar( '4' );
    for( size_t j=0; j!=i*4-n; ++j )
        putchar( '7' );
    putchar( '\n' );
}

当然，我就是这么一分析，是不是有什么细节遗漏不管我的事，你上交作业时自己检查。

当然，上面的输出代码比较丑，可以改为

#include <stdio.h>

int main( void )
{
    unsigned n;
    scanf( "%u", &n );

    const unsigned i = 2*n/7;
    printf( "%.*s\n", n-i*3, "444444777777777777777777777777777777777777777777"+6-2*n+i*7 );
}

#include <stdio.h>
#define N        300
int array[N+1] = {0};
void init()
{
    int i, j, k, m;
    for (i=0,j=0; i<=N; i+=7,j++)
    {
        array[i] = j;
        for (k=4,m=1; i+k<=N; k+=4,m++)
        {
            if (k%7)
            {
                array[i+k] = (m<<16) | j;
            }
        }
    }
}

int main()
{
    int n = -1;
    int i, j, k;
    scanf("%d", &n);
    if (n<0 || n>300)
    {
        printf("error\n");
        return 1;
    }
    init();
    i = array[n];
    if (!i)
    {
        printf("%d\n", -1);
        return 0;
    }
    j = i>>16;
    k = i&0xFFFF;
    for (i=0; i<j; i++)
    {
        putchar('4');
    }
    for (i=0; i<k; i++)
    {
        putchar('7');
    }
    putchar('\n');

    return 0;
}

可以这样分析 因为要最小 所以4的个数+7的个数要最小
对于某个数字 能用最多7 就能个数最小
直接 n/7 得到最多能有多少个7
然后余数用4拼凑
余数只有7个可能 0-6
0 直接全用7
1 减少1个7 加2个4凑出来
2 减少2个7 加4个4凑出来
3 减少3个7 加6个4凑出来
4 直接加1个4
5 在4的基础上按照1处理
6 在4的基础上按照2处理
7的个数不够减少 输出-1

#include <stdio.h>
int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int seven = n/7 - n%7%4;
    int four = n%7%4*2 + (n%7>=4);
    if(seven < 0)
        puts("-1");
    else
    {
        printf( "%.*s", four, "444444");
        printf( "%.*s\n", seven, "777777777777777777777777777777777777777777");
    }
    return 0;
}

收到的鲜花

• rjsp 于 2021-12-24 08:16 送鲜花  7朵  

谢谢谢谢谢谢！