fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define nl "\n"
  5. #define OO 0x3f3f3f3f
  6. using namespace std;
  7.  
  8. void ta2to2a()
  9. {
  10.     ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr);
  11. #ifndef ONLINE_JUDGE
  12.     freopen("input.txt", "r", stdin);
  13.     freopen("output.txt", "w", stdout);
  14. #endif
  15. }
  16. ll n;
  17. vector<ll> v(55);
  18. set<ll> powerfulNumbers()
  19. {
  20.     set<ll> st;
  21.     for (int i = 0; i <= 41; i++)
  22.     {
  23.         st.insert(1LL << i);
  24.     }
  25.     ll x = 1LL;
  26.     for (int i = 1; i <= 15; i++)
  27.     {
  28.         x *= i;
  29.         st.insert(x);
  30.     }
  31.  
  32.     return st;
  33. }
  34. ll powerfulSum(int i, ll sum, ll nums)
  35. {
  36.     if (sum == n)
  37.     {
  38.         return nums;
  39.     }
  40.     if (i == 55 || sum + v[i] > n)
  41.     {
  42.         return LONG_LONG_MAX;
  43.     }
  44.     ll ans1 = powerfulSum(i + 1, sum + v[i], nums + 1);
  45.     ll ans2 = powerfulSum(i + 1, sum, nums);
  46.     return min(ans1, ans2);
  47. }
  48. void solve()
  49. {
  50.     cin >> n;
  51.     ll ans = powerfulSum(0, 0, 0);
  52.     cout << ((ans == LONG_LONG_MAX) ? -1 : ans) << nl;
  53. }
  54. int main()
  55. {
  56.     ta2to2a();
  57.     int t = 1;
  58.     cin >> t;
  59.     int i = 0;
  60.     for (auto it : powerfulNumbers())
  61.     {
  62.         v[i] = it;
  63.         i++;
  64.     }
  65.     while (t--)
  66.     {
  67.         solve();
  68.     }
  69. }
Success #stdin #stdout 0s 5336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MdcEgp
language:
C++14 (gcc 8.3)
created:
58 minutes ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!