UVA - 12627

Erratic Expansion

原文PDF链接

description：

Piotr found a magical box in heaven. Its magic power is that if you place any red balloon inside it then, after one hour, it will multiply to form 3 red and 1 blue colored balloons. Then in the next hour, each of the red balloons will multiply in the same fashion, but the blue one will multiply to form 4 blue balloons. This trend will continue indefinitely.

The arrangements of the balloons after the 0-th, 1-st, 2-nd and 3-rd hour are depicted in the following diagram.

As you can see, a red balloon in the cell (i, j) (that is i-th row and j-th column) will multiply to produce 3 red balloons in the cells (i ∗ 2 − 1, j ∗ 2 − 1), (i ∗ 2 − 1, j ∗ 2), (i ∗ 2, j ∗ 2 − 1) and a blue balloon in the cell (i ∗ 2, j ∗ 2). Whereas, a blue balloon in the cell (i, j) will multiply to produce 4 blue balloons in the cells (i ∗ 2 − 1, j ∗ 2 − 1), (i ∗ 2 − 1, j ∗ 2), (i ∗ 2, j ∗ 2 − 1) and (i ∗ 2, j ∗ 2). The grid size doubles (in both the direction) after every hour in order to accommodate the extra balloons. In this problem, Piotr is only interested in the count of the red balloons; more specifically, he would like to know the total number of red balloons in all the rows from A to B after K-th hour.

Input

The first line of input is an integer T (T < 1000) that indicates the number of test cases. Each case contains 3 integers K, A and B. The meanings of these variables are mentioned above. K will be in the range [0, 30] and 1 ≤ A ≤ B ≤ 2 K.

Output

For each case, output the case number followed by the total number of red balloons in rows [A, B] after K-th hour.

Sample Input

3
0 1 1
3 1 8
3 3 7

Sample Output

Case 1: 1
Case 2: 27
Case 3: 14

---

题目大意：
按照某个规律依次生成一个气球方阵，简单的说就是，每次增加４倍的大小，其中左上方，右上方，左下方都和上一个的方阵一样，有下方全为蓝色气球。现在告诉我们第ｋ个方阵，让我们求从第Ａ行到第Ｂ行共有几个红色气球。
　　　　　　　　　　　　　　　　　　　　　　　　　　

解题思路：
1.红色气球数量的规律挺好找的，用ｆ(k,i) 表示第ｋ个方阵第ｉ行有几个红色气球。那么有：
方阵的上半区：f(k,i) = 2 * f(k-1,i)
方阵的下半区：f(k,i) = f(k-1,i- 2k−1)
然后就很自然的想到用一个数组记录，以减少递归中的重复计算，但是如果要记录的话需要30 * 2^30 大小的数组，这显然是不现实的。而直接递归求每一行再累加的话肯定会超时。(递归调用的次数太多了)

2.其实我们也很明显的发现在计算的过程中进行了大量的重复计算，那么怎么做减少计算次数呢？

3.第K个方阵的红色气球总数是很好算的，就是 3^K 。（下一个方阵的红色气球总数就是前一方阵的3倍嘛）而大的部分方阵总能化简为几个小的完整方阵的和。那么我们求第A行到第B行红色气球数量可以改为求前B行的气球总数减去前A-1行的气球数量。

核心代码：

long long fun(int K, int n) {
    if (n == 0)        //这个表示前一次计算正好是一个完美的上半方阵
        return 0;
    if (K == 0)       
        return 1;
    int temp = 1 << (K - 1);
    if (n >= temp)    //所求的部分方阵包含了整个上半方阵
        return fun(K - 1, n - temp) + 2 *num[K-1];
    else
        return 2 * fun(K - 1, n);
}

4.这个时候，我们对一开始发现的规律已经做一个修改。此时f(k,i)的含义是第K个方阵前i行的红色气球总数。
方阵的上半区：f(k,i) = 2 * f(k-1,i)
方阵的下半区：f(k,i) = f(k-1,i- 2k−1) + 2*3k−1

---

源代码

#include <iostream>  
#include <stdio.h>    
#include <cstring>  
#include <string>  
using namespace std;

long long num[31];

long long fun(int K, int n) {
    if (n == 0)
        return 0;
    if (K == 0)
        return 1;
    int temp = 1 << (K - 1);
    if (n >= temp) 
        return fun(K - 1, n - temp) + 2 *num[K-1];
    else
        return 2 * fun(K - 1, n);
}

int times;
int k, a, b;
int main() {
    num[0] = 1;
    for (int i = 1; i<30; i++)
        num[i] = 3 * num[i - 1];
    scanf("%d", &times);
    for (int i = 0; i < times; i++) {
        scanf("%d%d%d", &k, &a, &b);
        printf("Case %d: %lld\n", i+1, fun(k,b)-fun(k,a-1));
    }
    system("pause");
    return 0;
}