codeforces 146D Lucky Number 2 (找规律)

￡神魔★判官ぃ 2022-06-04 06:45 224阅读 0赞

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) = *a*1, *cnt*(7) = *a*2, *cnt*(47) = *a*3, *cnt*(74) = *a*4. Petya is not interested in the occurrences of other numbers. Help him cope with this task.

Input

The single line contains four integers *a*1, *a*2, *a*3 and *a*4 (1 ≤ *a*1, *a*2, *a*3, *a*4 ≤ 106).

Output

On the single line print without leading zeroes the answer to the problem — the minimum lucky number *d* such, that *cnt*(4) = *a*1, *cnt*(7) = *a*2, *cnt*(47) = *a*3, *cnt*(74) = *a*4. If such number does not exist, print the single number "-1" (without the quotes).

Example

Input

2 2 1 1

Output

4774

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");
    		}
    	}
    }