a470 - 12406 - Help Dexter
題目描述
題目要求找出最小和最大的 p 位數，這些數字僅由 1 和 2 組成，並且能被 2<sup>q</sup> 整除。如果找不到符合條件的數字，則輸出 "impossible"。
解題思路
這題使用深度優先搜尋 (DFS) 來產生所有可能的 p 位數，這些數字僅由 1 和 2 組成。對於每個產生的數字，檢查它是否能被 2<sup>q</sup> 整除。如果能，則更新最小和最大的符合條件的數字。
DFS 的起始點是 0，每次遞迴時，將數字乘以 10，然後加上 1 或 2。遞迴的終止條件是數字的位數達到 p。
在 main 函數中，讀取輸入的 p 和 q，初始化最小和最大值，然後呼叫 DFS 函數。最後，根據找到的最小和最大值輸出結果。如果最小和最大值相同，則輸出該值。如果最小和最大值都為 0，則輸出 "impossible"。
複雜度分析
- 時間複雜度: O(2<sup>p</sup>) 因為 DFS 遍歷所有可能的 p 位數，每個位數有 2 種選擇 (1 或 2)。
- 空間複雜度: O(p) DFS 的最大遞迴深度為 p，因此空間複雜度與 p 成正比。
程式碼
#include <iostream>
#define ll long long
using namespace std;
ll int t,mi,ma,p,q;
void dfs(ll int v,int c){
if(c==p){
if(v%q==0){
if(mi==0)mi=v;
if(ma==0)ma=v;
mi=min(v,mi);
ma=max(v,ma);
}
return;
}
v*=10;
dfs(v+1,c+1);
dfs(v+2,c+1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> p >> q;
q=1<<q;
mi=0;
ma=0;
dfs(0,0);
cout << "Case " << ca << ": ";
if(mi==ma){
if(mi==0){
cout << "impossible\n";
}
else{
cout << mi << "\n";
}
}
else{
cout << mi << " " << ma << "\n";
}
}
}