Algorithm

B. Lucky Numbers (easy)
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/96/B
input
standard input
output
standard output

Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

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

Input

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

Output

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

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
Copy
4500
output
Copy
4747
input
Copy
47
output
Copy
47



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include  <queue>

using namespace std;

struct SuperLucky {
    long long number;
    int fours, sevens;
};

void bfs(int des) {
    queue <SuperLucky> q;
    SuperLucky tmp;

    tmp.number = 4;
    tmp.fours = 1;
    tmp.sevens = 0;
    q.push(tmp);

    tmp.number = 7;
    tmp.fours = 0;
    tmp.sevens = 1;
    q.push(tmp);

    while (!q.empty()) {
        int size = q.size();

        while (size--) {
            SuperLucky fr = q.front();
            q.pop();

            fr.number *= 10;
            fr.number += 4;
            fr.fours++;

            if (fr.number >= des && fr.fours == fr.sevens) {
                cout  < < fr.number  < < endl;
                return;
            }

            q.push(fr);

            fr.number += 3;
            fr.fours--;
            fr.sevens++;

            if (fr.number >= des && fr.fours == fr.sevens) {
                cout  < < fr.number  < < endl;
                return;
            }

            q.push(fr);
        }
    }
}

int main() {
    int des;
    cin >> des;
    bfs(des);

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4500

Output

x
–
+
cmd
4747
Advertisements

Demonstration

Codeforcess Solution  Lucky Numbers (easy), B. Lucky Numbers (easy) C,C++, Java, Js and Python ,ucky Numbers (easy),Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+