# f637. DF-expression
##### link: https://zerojudge.tw/ShowProblem?problemid=f637
###### tags: `APCS` `recursion`

* 根據題目敘述，遇到一個二就要分割成四塊，馬上想到遞迴
* 遞迴終點：切割到不能再切割的時候。例如：範例測資中給了 8*8 的大小，那最多切割三次就不能再切了 ( 不過題目輸入讓我們不用考慮這個問題 )
* 每次切割必定只有四塊，因此，當尋訪到最多 4 個元素時，代表這一層就結束，需要 return ( *第14行*：紀錄尋訪幾個元素；*第19行*：如果超過，就將目前尋訪到的 $i$ 回傳，讓上一層繼續還沒完成的尋訪)
* (*第15行*) 每一層需要加上的像素數量不同，最後一層邊長為 1 ，加 1 即可，往上類推。
---
Code：

#include <bits/stdc++.h>

using namespace std;

string s;
int n;
long long int ans=0;
int power;

int backtrack(int layer ,int start){
    int a=0;
    for (int i=start ;i<s.size();i++){
        a++;
        if (s[i]=='1') ans+= pow(2,abs(power-layer))*pow(2,abs(power-layer));
        if (s[i]=='2'){
            i=backtrack(layer+1, i+1);
        }
        if (a>=4) return i;
        
    }
    return s.size()-1;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin>>s>>n;
    power = log10(n)/log10(2);
    backtrack(0,0);
    cout<<ans;
    return 0;
}