fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double
  5. #define vi vector<int>
  6. #define vl vector<ll>
  7. #define vld vector<ld>
  8. #define all(a) a.begin(), a.end()
  9. #define ull unsigned long long
  10. #define endl '\n'
  11. #define loop(i, n) for (int i = 0; i < (n); i++)
  12. const ll MOD = 1e9 + 7;
  13. #pragma GCC optimize("Ofast")
  14. #pragma GCC optimize("unroll-loops")
  15. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  16.  
  17. void fileio() {
  18.     freopen("input.txt", "r", stdin);
  19.     freopen("output.txt", "w", stdout);
  20. }
  21. void read2d(vector<vector<int>>&arr,int n,int m) {
  22.     for (int i =0;i<n;i++) {
  23.         for (int j =0;j<m;j++) {
  24.             cin>>arr[i][j];
  25.         }
  26.     }
  27. }
  28. void print2d(vector<vector<int>>&arr,int n,int m) {
  29.     for (int i =0;i<n;i++) {
  30.         for (int j =0;j<m;j++) {
  31.             cout<<arr[i][j]<<" ";
  32.         }
  33.         cout<<'\n';
  34.     }
  35. }
  36. void read1d(vector<int>&arr) {
  37.     for (int i =0;i<arr.size();i++) {
  38.         cin>>arr[i];
  39.     }
  40. }
  41. void read1d(vector<ll>&arr) {
  42.     for (int i =0;i<arr.size();i++) {
  43.         cin>>arr[i];
  44.     }
  45. }
  46. void print1d(vector<int>&arr) {
  47.     for (int i =0;i<arr.size();i++) {
  48.         cout<<arr[i]<<" ";
  49.     }
  50.     cout<<endl;
  51. }
  52. bool ispowerof2(ll n ) {
  53.     return log2(n)-static_cast<long long>(log2(n))==0;
  54. }
  55. ll isafactorial(ll n) {
  56.     ll i =2 ;
  57.     long double m = static_cast<long double>(n);
  58.     while (m>1) {
  59.       m/=i;
  60.         i++;
  61.     }
  62.     return  m==1 ? i : 0;
  63.  
  64. }
  65.  
  66. bool LinearSearch(vector<ll>& nums, ll val) {
  67.     ll n = nums.size();
  68.     for (ll i =0;i<n;i++) {
  69.         if (nums[i]==val) {
  70.             return 1 ;
  71.         }
  72.     }
  73.     return 0;
  74. }
  75. ll cnt = LLONG_MAX;vector<ll>factorials;
  76. int factorial(int n ) {
  77.     if (n==1||n==0) {
  78.         return 1 ;
  79.     }
  80.     return n * factorial(n-1);
  81. }
  82.  
  83. void preprocessing() {
  84.     for (ll i =1 ;i<=15;i++) {
  85.         ll fact=factorial(i);
  86.         factorials.push_back(fact);
  87.     }
  88.     for (ll i = 1 ;i<=39;i++) {
  89.         factorials.push_back(pow(2,i));
  90.     }
  91.     factorials.erase(unique(all(factorials)),factorials.end());
  92. }
  93. void gen(ll i ,ll sum,ll op, ll n ) {
  94.     if (i==factorials.size()) {
  95.         return;
  96.     }
  97.     if (sum>n) {
  98.         return;
  99.     }
  100.     if (sum==n) {
  101.         cnt=min(cnt, op);
  102.         return;
  103.     }
  104.     gen(i+1,sum,op,n);
  105.     if (LinearSearch(factorials,factorials[i])) {
  106.        gen(i+1,sum+factorials[i],op+1,n);
  107.     }
  108. }
  109.  
  110. void solve() {
  111.   cnt = LLONG_MAX  ;  ll n ; cin>>n ;
  112.     if (LinearSearch(factorials,n)) {
  113.         cout<<1<<endl;
  114.         return;
  115.     }
  116.     gen(0,0,0,n);
  117.     cout<<cnt<<endl;
  118.  
  119. }
  120.  
  121. int main()
  122. {
  123.     ios::sync_with_stdio(false);
  124.     cin.tie(nullptr);
  125.    fileio();
  126.     preprocessing();
  127.     int t = 1;
  128.     cin >> t;
  129.     while (t--)
  130.     {
  131.         solve();
  132.     }
  133. }
  134.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vt5dkV
language:
C++ (gcc 8.3)
created:
16 hours 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!