fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int P_th_power (int n, int m, int p) {
  5.    // Write your code here
  6.    vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));
  7.    vector<int> power(n + 1);
  8.    power[1] = 1;
  9.    for(int i = 2; i <= n; ++i) {
  10.        power[i] = 1;
  11.        for(int j = 1; j <= p; ++j) {
  12.            power[i] *= i;
  13.        }
  14.    }
  15.  
  16.    auto func = [&](int cur, int n, int m, auto& func) -> int {
  17.        if(n == 0 and m == 0) {
  18.            return 0;
  19.        }
  20.  
  21.        if((cur > n) or (n > m) or (power[cur] > m)) {
  22.            return 1e9;
  23.        }
  24.        int& val = dp[n][cur];
  25.        if(val != -1) {
  26.            return val;
  27.        }
  28.  
  29.        // not include
  30.        val = func(cur + 1, n, m, func);
  31.  
  32.        int cur_n = n, cur_m = m;
  33.        auto isValid = [&](int n, int m, int val) -> bool {
  34.            int term_a = val;
  35.            int term_b = power[val];
  36.            return term_a <= n and term_b <= m;
  37.        };
  38.  
  39.       // number of times to include 'i' in sequence
  40.        int times = 0;
  41.        while(isValid(cur_n, cur_m, cur)) {
  42.            ++times;
  43.            cur_n -= cur;
  44.            cur_m -= power[cur];
  45.            val = min(val, times + func(cur + 1, cur_n, cur_m, func));
  46.        }
  47.  
  48.        return val;
  49.    };
  50.    int ans = func(1, n, m, func);
  51.    if(ans == 1e9) ans = -1;
  52.    return ans;
  53. }
  54.  
  55. int main() {
  56.  
  57.     ios::sync_with_stdio(0);
  58.     cin.tie(0);
  59.     int T;
  60.     cin >> T;
  61.     for(int t_i = 0; t_i < T; t_i++)
  62.     {
  63.         int N;
  64.         cin >> N;
  65.         int M;
  66.         cin >> M;
  67.         int P;
  68.         cin >> P;
  69.  
  70.         int out_;
  71.         out_ = P_th_power(N, M, P);
  72.         cout << out_;
  73.         cout << "\n";
  74.     }
  75. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
3
3 5 2
4 10 3
3 1 2
stdout
copy 
2
3
-1
https://ideone.com/9clm2R
language:
C++14 (gcc 8.3)
created:
2 years 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!