Lucky Numbers (easy)

Problem description

Petya loves lucky numbers. Everybody knows that positive integers arelucky if their decimal representation doesn't contain digits other than4 and7. For example, numbers47,744,4 are lucky and5,17,467 are not.

Lucky number issuper lucky if it's decimal representation contains equal amount of digits4 and7. For example, numbers47,7744,474477 are super lucky and4,744,467 are not.

One day Petya came across a positive integern. Help him to find the least super lucky number which is not less thann.

Input

The only line contains a positive integern (1 ≤ n ≤ 10⁹). This number doesn't have leading zeroes.

Output

Output the least super lucky number that is more than or equal ton.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

4500

47

Output

4747

47

解题思路：题目要求输出不小于n的最小整数，这个整数要求只含有4和7这两个数字，并且4出现的次数等于7出现的次数。暴力打表（大概2分钟），水过！打表代码：

1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 bool judge(LL x){
 5     int t1 = 0, t2 = 0;
 6     while (x){
 7         int a = x % 10;
 8         if (a != 4 && a != 7)return false;
 9         if (a == 4)t1++;
10         if (a == 7)t2++;
11         x /= 10;
12     }
13     if (t1 == t2)return true;
14     else return false;
15 }
16 int main(){
17     for (LL i = 47; i < 10000000000; ++i)
18         if (judge(i)){ cout << i << ','; }
19     return 0;
20 }

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,obj[]={47,74,4477,4747,4774,7447,7474,7744,
 5         444777,447477,447747,447774,474477,474747,474774,
 6         477447,477474,477744,744477,744747,744774,747447,
 7         747474,747744,774447,774474,774744,777444,44447777,
 8         44474777,44477477,44477747,44477774,44744777,44747477,
 9         44747747,44747774,44774477,44774747,44774774,44777447,
10         44777474,44777744,47444777,47447477,47447747,47447774,
11         47474477,47474747,47474774,47477447,47477474,47477744,
12         47744477,47744747,47744774,47747447,47747474,47747744,
13         47774447,47774474,47774744,47777444,74444777,74447477,
14         74447747,74447774,74474477,74474747,74474774,74477447,
15         74477474,74477744,74744477,74744747,74744774,74747447,
16         74747474,74747744,74774447,74774474,74774744,74777444,
17         77444477,77444747,77444774,77447447,77447474,77447744,
18         77474447,77474474,77474744,77477444,77744447,77744474,
19         77744744,77747444,77774444,4444477777};
20 int main(){
21     cin>>n;
22     for(int i=0;;++i)
23         if(obj[i]>=n){cout<<obj[i]<<endl;break;}
24     return 0;
25 }

再贴一种很好理解的递归写法（反正我没想到QAQ，值得学习一下）AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,ans=1LL <<60;
 5 void f(LL x,int y,int z){//通过x构造答案，y是4的个数，z是7点个数
 6     if(x>=n && y==z)ans=min(ans,x);//答案ans满足要求:1.大于等于n  2.只存在7和4，且7的个数等于4的个数
 7     if(x>n*100)return;//答案肯定在n和n*100之间，所以x>n*100的时候退出；
 8     f(x*10+4,y+1,z);//当前答案x加一位数4
 9     f(x*10+7,y,z+1);//当前答案x加一位数7
10 }
11 int main(){
12     cin>>n;
13     f(0,0,0);
14     cout<<ans<<endl;
15     return 0;
16 }

原文链接: https://www.cnblogs.com/acgoto/p/9123222.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍