# 題目: UVa 12627 - Erratic Expansion
# 題目說明
一開始有一顆紅氣球，每過1小時，紅氣球會變成3顆紅氣球與1顆藍氣球、藍氣球會變成4顆藍氣球
求過了k小時後，從第a行到第b行的氣球數和
INPUT:
第一行輸入一個整數t，代表測資數
每筆測資輸入三個整數k、a、b，代表過了k小時，行數a與b
OUTPUT:
輸出過了k小時後，從第a行到第b行的氣球數和
# 解題方法
假設以下公式dfs(k, i)為過了k小時後，最下面i行的氣球數和
第a行到第b行的氣球數和可視為第a行到最後一行的氣球數和 - 第b + 1行到最後一行的氣球數和
所以可以寫成 dfs(k, n - a + 1) - dfs(k, n - b)
n為總行數
假設k = 3、a = 3、b = 7
n則為2^3 = 8
上述的算式可以寫成 dfs(3, 8 - 3 + 1) - dfs(k, 8 - 7)
化簡為dfs(3, 6) - dfs(3, 1)
再由以下關係，計算出紅氣球的總數
當i >= 2^(k - 1)時，dfs(k, i) = dfs(k - 1, i - 2^(k - 1)) * 2 + 3^(k - 1)
當i < 2^(k - 1)時，dfs(k, i) = dfs(k -1, i)
寫成recursive後即可求出答案
同樣以假設k = 3、a = 3、b = 7為例
上面步驟做到dfs(3, 6) - dfs(3, 1)
首先先處理dfs(3, 6)
由於i = 6 >= 2^(k - 1) = 4，所以dfs(3, 6) = dfs(3 - 1, 6 - 2^(3 - 1)) * 2 + 3^(3 - 1) = dfs(2, 2) * 2 + 3^2
這時候recursive呼叫dfs(2, 2)，由於i = 2 >= 2^(k - 1) = 2，所以dfs(2, 2) = dfs(2 - 1, 2 - 2^(2 - 1)) * 2 + 3^(2 - 1) = dfs(1, 0) * 2 + 3
這時候recursive呼叫dfs(1, 0)，dfs(1, 0)回傳0，所以dfs(2, 2)回傳0 * 2 + 3 = 3
最後dfs(3, 6)回傳3 * 2 + 9 = 15
再處理dfs(3, 1)
由於i = 1 < 2^(k - 1) = 4，所以dfs(3, 1) = dfs(2, 1)
這時候recursive呼叫dfs(2, 1)，由於i = 1 < 2^(k - 1) = 2，所以dfs(2, 1) = dfs(1, 1)
這時候recursive呼叫dfs(1, 1)，回傳1，dfs(2, 1)回傳1，所以最後dfs(3, 1)也回傳1
dfs(3, 6) - dfs(3, 1)結果為15 - 1 = 14
需要使用long long不然會爆
# 參考程式碼
#include <iostream>
#include <math.h>
using namespace std;
static auto fast_io = []
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
return 0;
}();
long long dfs(int k, long long i)
{
if (i == 0) return 0;
if (k == 0) return 1;
long long n = 1 << (k - 1);
return (i >= n ? 2 * dfs(k - 1, i - n) + pow(3, k - 1) : dfs(k - 1, i));
}
int main()
{
int t, k, a, b, Case = 0;
cin >> t;
while (t--)
{
cin >> k >> a >> b;
long long n = 1 << k;
cout << "Case " << ++Case << ": " << dfs(k, n - a + 1) - dfs(k, n - b) << "\n";
}
}