2020年10月27日提高组 B 数字

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/U137456

---

D e s c r i p t i o n Description Description

T T T组数据
给定一个数 n n n，要求输出一个最小的只由相等个数的4和7组成的数使得其大于等于 n n n

数据范围： n ≤ 1 0 100000 n\leq 10^{100000} n≤10100000

---

S o l u t i o n Solution Solution

搜索即可，很快就能得到一组解的

---

C o d e Code Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;char s[100010],ans[100010];
int n;
inline bool dfs(int dep,int tot4,int tot7,bool tag)
{
	if(dep>=n) return true;
	if(tag)
	{
		for(register int i=0;i<tot4;i++) ans[i+dep]='4';
		for(register int i=0;i<tot7;i++) ans[i+dep+tot4]='7';
		return true;
	}
	if(s[dep]<='4'&&tot4&&dfs(dep+1,tot4-1,tot7,s[dep]<'4')) return ans[dep]='4';
	if(s[dep]<='7'&&tot7&&dfs(dep+1,tot4,tot7-1,s[dep]<'7')) return ans[dep]='7';
	return false;
}
signed main()
{
	while(cin>>s)
	{
		n=strlen(s);
		if(n&1)//奇数位数的话显然前一半4，后一半7
		{
			for(register int i=1;i<=(n+1)/2;i++) putchar(52);
			for(register int i=1;i<=(n+1)/2;i++) putchar(55);
			putchar(10);
			continue;
		}
		else
		{
			memset(ans,0,sizeof(ans));
			if(dfs(0,n/2,n/2,0)==0)//没有解说明这个位数不行，则令位数+2，然后同上
			{
				n+=2;
				for(register int i=0;i<n/2;i++) ans[i]='4';
				for(register int i=n/2;i<n;i++) ans[i]='7';
			}
			cout<<ans<<endl;
		}
	}
}