BOKAM143SOU.cpp

#include<iostream>
using namespace std;
 
int N;          // Số đầu vào
int Answer;     // Số lượng cách
int A[51];      // Mảng lưu các số lập phương <= N
int Leng;       // Lưu số lượng các số lập phương <= N
 
/*
* num : số phần tử đã chọn, khi num = 5 thì sẽ được một cách
* sum : là tổng của các số đã chọn
* oldpos : lưu vị trí của số đã chọn lúc trước
* số chọn sau phải có vị trí lớn hơn hoặc bằng vị trí số chọn trước
* => các cách sẽ không bị lặp lại
*/
void Check(int num, int sum, int oldpos)
{
    // Khi chọn đủ 5 số mà tổng các số đã chọn == N thì được 1 cách mới
    if(num == 5)
    {
        if(sum == N) Answer++;
        return;
    }
 
    // Duyệt mảng các số lập phương <= N để thử các số
    for(int i = 0; i < Leng; i++)
        if(i >= oldpos)
            Check(num + 1, sum + A[i], i);
}
 
int main()
{
    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);
    
    cin >> N;
    Leng   = 0;
    Answer = 0;
 
    // Tìm ra tất cả các số lập phương <= N và lưu vào 1 mảng
    while(true)
    {
        int temp = (Leng * Leng * Leng);
        if(temp > N) break;
        A[Leng++] = temp;
    }
    
    // Bắt đầu backtrack để thử tất cả các trường hợp xảy ra
    Check(0, 0, -1);
 
    cout << Answer << endl;
 
    return 0;
}