首頁 Uva Problems

# 題目: 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";
	}
}
# 參考資料
https://www.twblogs.net/a/5e505f33bd9eee2117beb0b7