---
# System prepended metadata

title: a470. 12406 - Help Dexter
tags: [recursion]

---

# a470. 12406 - Help Dexter
##### link: https://zerojudge.tw/ShowProblem?problemid=a470
###### tags: `recursion`
* 遞迴枚舉所有可能選項
* 進入一次遞迴就計算一次餘數，如果最後為零，則為合法答案，在決定他是否為最大或最小的可能值。
```C++=

#include <bits/stdc++.h>

using namespace std;

int t,p,q;
int divider;
long long int maxs = -9e18;
long long int mins = 9e18;

void backtrack(int layer, int r, long long int ans){
    if (layer == p){
        if (r==0){
            maxs = max(ans,maxs);
            mins = min(ans , mins);
        }
        return ;
    }
    backtrack(layer+1 , (10*ans+1)%divider, 10*ans + 1);
    backtrack(layer+1 , (10*ans+2)%divider, 10*ans + 2);
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    for (int i=1;i<=t;i++){
        cin>>p>>q;
        divider = pow(2,q);
        mins = 9e18;
        maxs = -9e18;
        backtrack(0,0,0);
        if (mins == 9e18 && maxs == -9e18) cout<<"Case "<<i<<": impossible\n";
        else if (mins == maxs) cout<<"Case "<<i<<": "<<mins<<"\n";
        else cout<<"Case "<<i<<": "<<mins<<" "<<maxs<<"\n";
    }

    return 0;
}
```