96B - Lucky Numbers (easy) - CodeForces Solution

#include <bits/stdc++.h>
#include <ctype.h>
using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
typedef long long int ll;
#define pii pair<ll, ll>
#define pb push_back
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define lld long double
#define ull unsigned long long

const ll M = 1e18;
const ll INF = 1e6 + 5;
const int MAXN = 2e5 + 5;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << "\n";
#else
#define debug(x)
#endif
void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }

struct SCC {
    int N, ti = 0; vector<vector<int>> adj;
    vector<int> disc, comp, st, comps;
    void init(int _N) {
        N = _N;
        adj.resize(N), disc.resize(N), comp = vector<int>(N, -1);
    }
    void ae(int x, int y) {
        adj[x].push_back(y);
    }
    int dfs(int x) {
        int low = disc[x] = ++ti; st.push_back(x); // disc[y] != 0 -> in stack
        for (int y : adj[x]) if (comp[y] == -1) low = min(low, disc[y] ? : dfs(y));
        if (low == disc[x]) { // make new SCC, pop off stack until you find x
            comps.push_back(x); for (int y = -1; y != x;)
                comp[y = st.back()] = x, st.pop_back();
        }
        return low;
    }
    void gen() {
        for (int i = 0; i < N; i++) if (!disc[i]) dfs(i);
        reverse(begin(comps), end(comps));
    }
};
struct DSU {
    vector<int> e;
    void init(int n) { e = vector<int>(n, -1); }
    int get(int x) { return (e[x] < 0 ? x : e[x] = get(e[x])); }
    bool sameSet(int x, int y) { return get(x) == get(y); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return 0;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return 1;
    }
};

// ll dp[INF];
bool prime[INF];
void SieveOfEratosthenes()
{
    memset(prime, 1, sizeof(prime));
    prime[1] = 0;
    prime[0] = 0;

    for (int p = 2; p * p < INF; p++)
    {
        if (prime[p] == true)
        {

            for (int i = p * p; i < INF; i += p)
            {

                prime[i] = false;
            }
        }
    }
}
ll binpowMod(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int spf[INF];
void sieve()
{
    spf[1] = 1;
    for (int i = 2; i < INF; i++)
        spf[i] = i;
    for (int i = 4; i < INF; i += 2)
        spf[i] = 2;
    for (int i = 3; i * i < INF; i++)
    {
        if (spf[i] == i)
        {
            for (int j = i * i; j < INF; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
//vector<vector<ll>> numways(target+1, vector<ll> (n+1, 0));
ll d[INF] = {};

int dx8[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dy8[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
// 8 directional flow

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
string ds = "RLDU";


bool isqr(ll n)
{
    ll sum = sqrtl(n);
    return (sum * sum) == n;
}
// vector<vector<int>> dp(600, vector<int>(600, 0));

vector<pii> graph_w[MAXN];
vector<ll> graph[MAXN], graph2[MAXN];
int parentJump[MAXN][30];
vector<int> vis(MAXN, 0);
vector<int>stt;
vector<int>dp(MAXN, 0);
// ll vis[MAXN] = { 0 };
// vector<ll> path;
// ll dist[MAXN];
ll parent[MAXN];
// ll color[MAXN];
ll indegree[MAXN];
// ll level[INF];
// int jump[21][INF];
vector<int>Subtree(MAXN, 0);
// vector<int> graph[MAXN];
// vector<int> topo_sort;
// fuck rating do for fun

void print(vector<ll>ans)
{
    for (int i = 0;i < ans.size();i++)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
}
ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll prims(ll node) {
    priority_queue<pii, vector<pii>, greater<pii> > Q;

    ll minimumCost = 0;
    Q.push({ 0,node });
    while (!Q.empty()) {
        ll w = Q.top().first;
        ll u = Q.top().second;
        Q.pop();
        if (vis[u]) continue;
        minimumCost += w;
        vis[u] = 1;
        for (auto it : graph_w[u]) {
            ll v = it.first;
            ll weight = it.second;
            if (!vis[v]) {
                Q.push({ weight,v });
            }
        }
    }
    return minimumCost;

}



ll modInverse(ll A, ll M)
{
    for (ll X = 1; X < M; X++) {

        if (((A % M) * (X % M)) % M == 1)
            return X;
    }
    return -1;
}
bool check(vector<ll> a, int n, ll x) {
    bool ok = true;
    for (int i = 0;i < n;i++)
    {
        for (int j = i + 1;j < n;j++)
        {

            ok = ok & (__gcd(a[i] + x, a[j] + x) == 1);

        }
    }
    return ok;
}
vector<int> longestSubsequence(int a[], int n)
{
    // stores the index of elements
    unordered_map<int, int> mp;

    // stores the length of the longest
    // subsequence that ends with a[i]
    int dp[n];
    memset(dp, 0, sizeof(dp));

    int maximum = INT_MIN;

    // iterate for all element
    int index = -1;
    for (int i = 0; i < n; i++) {

        // if a[i]-1 is present before i-th index
        if (mp.find(a[i] - 1) != mp.end()) {

            // last index of a[i]-1
            int lastIndex = mp[a[i] - 1] - 1;

            // relation
            dp[i] = 1 + dp[lastIndex];
        }
        else
            dp[i] = 1;

        // stores the index as 1-index as we need to
        // check for occurrence, hence 0-th index
        // will not be possible to check
        mp[a[i]] = i + 1;

        // stores the longest length
        if (maximum < dp[i]) {
            maximum = dp[i];
            index = i;
        }
    }
    vector<int>ans;
    // We know last element of sequence is
    // a[index]. We also know that length
    // of subsequence is "maximum". So We
    // print these many consecutive elements
    // starting from "a[index] - maximum + 1"
    // to a[index].
    for (int curr = a[index] - maximum + 1;
        curr <= a[index]; curr++)
        ans.push_back(curr);

    return ans;

}


// const ll MODINV = modInverse(6ll, MOD) % MOD;
/*
* @case if min(a) > max(a)  ans="NO";
* @case if a==b ans="YES";
*/
// you can compare one by one from the lowest to the highest.Write a few numbers :
// 00000000
// 00000001
// 00000010
// 00000011
// 00000100
// 00000101
// 00000110
// 00000111
// ......
// You can see that the last digit is 010101, and the penultimate digit is 00110011, so...it is obvious.

const int N = (1 << 11);
set<ll>luckyNumbers;
bool checkIfCountOf4and7(ll n) {
    ll cnt4 = 0, cnt7 = 0;
    while (n) {
        if (n % 10 == 4) {
            cnt4++;
        }
        else if (n % 10 == 7) {
            cnt7++;
        }
        n /= 10;
    }
    return cnt4 == cnt7;
}
void generate(ll n, ll i, ll num) {
    if (i == n) {
        if (checkIfCountOf4and7(num))
        luckyNumbers.insert(num);
        return;
    }
    else {
        if (checkIfCountOf4and7(num))
        luckyNumbers.insert(num);
    }
    generate(n, i + 1, num * 10 + 4);
    generate(n, i + 1, num * 10 + 7);
}

void solve() {
    ll n;
    cin >> n;
    ll ans = 0;

    generate(12ll, 0ll, 0ll);
    // find smallest number in set which is greater than n
    auto it = luckyNumbers.lower_bound(n); 
    // print set
     
    cout << *it << endl;

}

/*
* a[i], a[i+1]
* @case 1:
* a[i] > a[i+1]
*
*
*/
/*
* x+k,a -> gcd(x+k,a)=1
* find min k such that gcd(x+k,a)!=1
*/



int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif


    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1; 
    for (int i = 1;i <= t;i++)
    {

        solve();
    }
    return 0;
}