AtCoder Beginner Contest 357-C

发表于 阅读次数： 本文字数： 563 阅读时长 ≈ 2 分钟

Problem

For a non-negative integer \(K\), we define a level-\(K\) carpet as follows:

  • A level-\(0\) carpet is a \(1 \times 1\) grid consisting of a single black cell.
  • For \(K>0\), a level-\(K\) carpet is a \(3^K \times 3^K\) grid. When this grid is divided into nine \(3^{K-1} \times 3^{K-1}\) blocks:
    • The central block consists entirely of white cells.
    • The other eight blocks are level-\((K-1)\) carpets.

You are given a non-negative integer \(N\). Print a level-\(N\) carpet according to the specified format.

Translations

对于一个非负整数 \(K\) ，我们定义\(K\)级地毯如下：

  • \(0\)级地毯是由一个黑色单元格组成的 \(1 \times 1\) 网格。
  • \(K(K>0)\)级地毯是一个 \(3^K \times 3^K\) 网格。当这个网格被划分为九个 \(3^{K-1} \times 3^{K-1}\) 块时：
    • 中央区块完全由白色单元格组成。
    • 其他八个区块是 \((K-1)\) 级地毯。

给你一个非负整数\(N\)。请按照指定格式打印 \(N\) 级地毯。

Constraints

  • \(0 \leq N \leq 6\)
  • \(N\)是整数。

Sample

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N=1
###
#.#
###

N=2
#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

Solution

容易想到递归解决这个问题。

由于\(N\)比较小，我们可以直接对于\(3^N\times3^N\)内所有位置\((x,y)\)逐个进行判断。

对于单元格\((x,y)\)，我们需要找到会包含它且大小最小的\(k\)级地毯，即 \[ st. x,y\le 3^k\\ \min{k} \] 将该\(k\)级地毯划分为九宫格。如果\((x,y)\)处于中间宫格，即\(x,y\in[3^{k-1}+1,2\times3^{k-1}]\)，则\((x,y)\)一定是白色的。

否则，考虑\((x,y)\)在\(k-1\)级地毯中的相对位置\((x\bmod 3^{k-1},y\bmod3^{k-1})\)，递归判断即可。

我认为我的写法还是复杂了点，应该还有优化空间，但是考虑\(N\le6\)，应该无伤大雅了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define N 1010

int n;
int pow3[100];



bool calc(int x,int y)
{
    int k=10;
    while(pow3[k-1]>=x&&pow3[k-1]>=y&&k>=2) k--;
    //cout<<"size="<<pow3[k]<<endl;
    if(pow3[k-1]+1<=x&&x<=2*pow3[k-1]&&pow3[k-1]+1<=y&&y<=2*pow3[k-1]) return 0;
    if(k==1) return 1;
    return calc(x%pow3[k-1],y%pow3[k-1]);
}

int main()
{
    cin>>n;
    pow3[0]=1;
    for(int i=1;i<16;i++){
        pow3[i]=pow3[i-1]*3;
    }
    
    for(int i=1;i<=pow3[n];i++)
    {
        for(int j=1;j<=pow3[n];j++)
        {
            if(calc(i,j)) cout<<'#';
            else cout<<'.';
        }
        cout<<endl;
    }
    
    return 0;
}

Attention

代码很丑，很久没写题了，有点不适应。