g500 - 109北二2.金庫的密碼
題目描述
題目描述了金庫密碼的計算方式。密碼由五個正整數 n1, n2, n3, n4, n5 運算得到，這些數字滿足 0 < n1 < n2 < n3 < n4 < n5 ≤ 30。運算公式為：a1 = n1 * 20, a2 = n2 * n2, a3 = n3 * 3, a4 = (n3 + n4) * 4, a5 = (n5 - n4) * 5。如果 a1 + a2 + a3 + a4 + a5 等於給定的數字 N，則找到一組解。如果找到 c 組解，則密碼為 c 的立方。如果沒有找到解，則密碼為 N * 5 - 3。
解題思路
題目給定的範圍較小 (n1 到 n5 都在 1 到 30 之間)，因此可以使用暴力法，枚舉所有可能的 n1, n2, n3, n4, n5 的組合，並檢查它們是否滿足條件。如果找到一組解，則計數器 ans 加一。最後，根據找到的解的數量計算密碼。
複雜度分析
- 時間複雜度: O(30^5)。由於使用了五層嵌套迴圈，每層迴圈的迭代次數最多為 30，因此時間複雜度為 O(30 * 30 * 30 * 30 * 30) = O(30^5)。
- 空間複雜度: O(1)。程式只使用了少數幾個變數來存儲中間結果和計數器，因此空間複雜度為常數級別。
程式碼
#include <iostream>
using namespace std;
int n,ans;
int main(){
cin >> n;
for(int a=1;a<=30;++a){
int n1=a*20;
for(int b=a+1;b<=30;++b){
int n2=b*b;
for(int c=b+1;c<=30;++c){
int n3=c*3;
for(int d=c+1;d<=30;++d){
int n4=(c+d)*4;
for(int e=d+1;e<=30;++e){
int n5=(e-d)*5;
if(n1+n2+n3+n4+n5==n){
//cout << a << " " << b << " " << c << " " << d << " " << e << "\n";
//cout << n1 << " " << n2 << " " << n3 << " " << n4 << " " << n5 << "\n";
++ans;
}
}
}
}
}
}
if(ans==0){
cout << n*5-3;
}
else{
cout << ans*ans*ans;
}
}