CuteWisp

[C++] AtCoder Beginner Contest 192 C번 Kaprekar Number

05 Mar 2021 | PS

AtCoder Beginner Contest 192 C번 Kaprekar Number

문제

https://atcoder.jp/contests/abc190/tasks/abc192_c abc192_c

풀이

g1(x)는 x의 각 자리수를 내림차순으로 재배치한 것

g2(x)는 x의 각 자리수를 오름차순으로 재배치한 것

f(x) = g1(x) - g2(x)라고 한다.

a0=N이고 ai+1 = f(ai)일때 ak를 구하는 문제

f(x)를 구하고 이를 k번 반복하면 된다. k <= 10^5이고 n < 10^9 이기 때문에 단순한 방법으로 풀어도 시간초과는 나오지 않는다.

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc192/tasks/abc192_c
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n,k;
    cin >> n >> k;
    ll a = n;
    rep(i,k){
        vll g;
        while(a){
            ll temp = a%10;
            g.push_back(temp);
            a /= 10;
        }
        sort(all(g));
        ll g1 = 0, g2 = 0;
        for(int j = 0;j<g.size();j++){
            g1 += g[j] * pow(10,j);
        }
        reverse(all(g));
        for(int j = 0;j<g.size();j++){
            g2 += g[j] * pow(10,j);
        }
        a = g1 - g2;
        if(a == 0) break;
    }
    cout << a;

    return 0;
}

Related posts