Sort by

recency

|

352 Discussions

|

  • + 0 comments
    def h(i,S,X,N):
        e=0
        for j in range(i+1,int(X**1/N)+1):
            if S+j**N<X:
                e=e+h(j,S+j**N,X,N)
            elif S+j**N==X:
                e+=1
            else:
                continue
        return e
    
    
    
    def powerSum(X, N):
        a=0
        for i in range(1,int(X**1/N)+1):
            S=i**N
            if S < X:
                a += h(i, S, X, N)
            elif S == X:
                a += 1
        return a
    
  • + 0 comments

    The most intuitive solution you will ever find in this entire discussion. Plus, the run time speed surpassed editorial solution.

    include

    using namespace std;

    int ipow(const int& b, const int& e){ if(e == 0) return 1; return b * pow(b, e - 1); }

    int recursion_ans(const vector& vec, const int& index, const int& remaining){ if(remaining == 0) return 1; if(index < 0 || remaining < 0) return 0;

    return recursion_ans(vec, index - 1, remaining - vec[index]) + 
            recursion_ans(vec, index - 1, remaining);
    

    }

    int main(){ int X, N; cin >> X >> N;

    vector<int> vec;
    
    int i = 1;
    while(i){
        int value = ipow(i, N); ++i;
        if(value > X) break;
        vec.push_back(value);
    }
    
    cout << recursion_ans(vec, vec.size() - 1, X);
    
    return 0;
    

    }

  • + 0 comments

    Haskell

    Function wwo -- "with or without"

    module Main where
    
    vals :: Int -> Int -> [Int]
    vals n k = reverse $ takeWhile (<= n) [x ^ k | x <- [1 ..]]
    
    wwo :: Int -> [Int] -> Int
    wwo n xs
      | n == 0 = 1
      | n < 0 = 0
      | null xs = 0
      | otherwise = wwo n (tail xs) + wwo (n - head xs) (tail xs)
    
    main :: IO ()
    main = do
      n <- readLn :: IO Int
      k <- readLn :: IO Int
      print $ wwo n (vals n k)
    
  • + 1 comment

    int findPows(int X, int num, int N) {

    int val = X - pow(num, N);
    if (val < 0) {
        return 0;  
    }
    if (val == 0) {
        return 1;  
    }
    
    return findPows(val, num + 1, N) + findPows(X, num + 1, N); 
    

    }

    int powerSum(int X, int N) { return findPows(X, 1, N); }

  • + 0 comments

    knapsack, O(X * X^(1/N))

    int powerSum(int X, int N) {
        int L = pow(X, 1.0/N);
        vector<vector<int>> cache(X+1, vector<int>(L+1));
        for (int j=0; j <= L; j++) cache[0][j] = 1;
        for (int i=1; i <= X; i++) {
            for (int j=1; j <= L; j++) {
                if (i < pow(j, N)) cache[i][j] = cache[i][j-1];
                else cache[i][j] = cache[i][j-1] + cache[i - pow(j, N)][j-1];
            }
        }
        return cache[X][L];
    }