codeforces 146D Lucky Number 2 (找规律)-蒲公英云

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya loves long lucky numbers very much. He is interested in the minimum lucky number d that meets some condition. Let cnt(x) be the number of occurrences of number x in number d as a substring. For example, if d = 747747, then cnt(4) = 2, cnt(7) = 4, cnt(47) = 2, cnt(74) = 2. Petya wants the following condition to fulfil simultaneously: cnt(4) = a1, cnt(7) = a2, cnt(47) = a3, cnt(74) = a4. Petya is not interested in the occurrences of other numbers. Help him cope with this task.

Input

The single line contains four integers a1, a2, a3 and a4 (1 ≤ a1, a2, a3, a4 ≤ 106).

Output

On the single line print without leading zeroes the answer to the problem — the minimum lucky number d such, that cnt(4) = a1, cnt(7) = a2, cnt(47) = a3, cnt(74) = a4. If such number does not exist, print the single number “-1” (without the quotes).

Example

Input

2 2 1 1

Output

Input

4 7 3 1

Output

-1

题意：有一长串数字只由4和7组成，现在告诉你这串数字有a1个4，a2个7，a3个47，a4个74，(比如4774有2个4，2个7，1个47，1个74。)要求让你写出一个满足条件的最小的数字。

思路：我们首先在纸上随便写出几串由4和7组成的数字，很容易发现一个特点，以4开头以7结尾，那么47一定比74多1，以7开头以4结尾，那么74一定比47多1，如果开头结尾都是4或都是7，那么47一定等于74。所以说我们一开始就可以判断出当abs(47-74)>1时，一定是输出-1的。

现在我们再分类讨论：

①当47>74时：

输出的格式一定是444…4747474747…777。这样可以保证数字最小。那么我们就要找出多余的4和多余的7的个数，它们分别是a1-a3和a2-a3，接下来循环输出即可。

②当74>47时：

输出的格式一定是7444…47474747…777。这样可以保证数字最小。那么同理，依然要找出多余的4和多余的7的个数，它们分别是a1-a4和a2-a4，接下来循环输出即可。

③当47=74时：

这个需要再分类讨论一下，首先如果a1<2&&a2<2的话肯定是输出-1。如果a1 - 1 >= a3&&a2 >= a3，那么就可以满足4放在两边的情况，那么输出格式一定是444…444747…474777…7774。多余的4和多余的7的个数分别是a1-a3-1和a2-a3。如果不满足这个条件的话，那么至少要满足a2 - 1 >= a3&&a1 >= a3，这是把7放在两边所需满足的条件，这时的输出格式是74747….474777….777。这时是不会有多余的4的，不然就可以满足4放两边的情况。所以多余的7的个数为a2-a3-1。如果这两个条件都不满足，那么就输出-1。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9 + 5;
const int MAXN = 1005;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)    res *= a; return res; }
LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
int main()
{
    int a1, a2, a3, a4;
    while (scanf("%d%d%d%d", &a1, &a2, &a3, &a4) != EOF)
    {
        if (abs(a3 - a4) >= 2){printf("-1\n"); continue;}
        else if (a3 == a4)
        {
            if (a1 < 2 && a2 < 2){printf("-1\n");continue;}
            if (a1 - 1 >= a3&&a2 >= a3)
            {
                a1 = a1 - a3 - 1;
                a2 = a2 - a3;
                for (int i = 1; i <= a1; i++)    printf("4");
                for (int i = 1; i <= a3; i++)    printf("47");
                for (int i = 1; i <= a2; i++)    printf("7");
                printf("4\n");
                continue;
            }
            else if (a2 - 1 >= a3&&a1 >= a3)
            {
                a2 = a2 - 1 - a3;
                printf("7");
                for (int i = 1; i <= a3; i++)    printf("47");
                for (int i = 1; i <= a2; i++)    printf("7");
                printf("\n");
                continue;
            }
            else{printf("-1\n");continue;}
        }
        else if (a3 > a4)
        {
            a1 = a1 - a3;
            a2 = a2 - a3;
            if (a1 < 0 || a2 < 0){printf("-1\n");continue;}
            for (int i = 1; i <= a1; i++)    printf("4");
            for (int i = 1; i <= a3; i++)    printf("47");
            for (int i = 1; i <= a2; i++)    printf("7");
            printf("\n");
        }
        else
        {
            a1 = a1 - a4;
            a2 = a2 - a4;
            if (a1 < 0 || a2 < 0){printf("-1\n");continue;}
            printf("7");
            for (int i = 1; i <= a1; i++)    printf("4");
            for (int i = 1; i <= a3; i++)    printf("47");
            for (int i = 1; i <= a2; i++)    printf("7");
            printf("4\n");
        }
    }
}