# Description

A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The knight initially owns the square he stands, and jumps $N$ times before he gets bored. Recall that a knight can jump in 8 directions. Each direction consists of two squares forward and then one squaure sidways.

After $N$ jumps, how many squares can possibly be claimed as territory of the knight? As $N$ can be really large, this becomes a nightmare to the knight who is not very good at math. Can you help to answer this question?

# input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case contains only one number $N$, indicating how many times the knight jumps. $1 \leq T \leq 10^5$,$0 \leq N \leq 10^9$

# output

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of squares that can possibly be claimed by the knight.

# 2017 CCPC FINAL

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  #include using namespace std; typedef unsigned long long ull; typedef long long ll; // 打表推公式 int a[]={1,9,41,109,205,325,473}; int main() { int t;scanf("%d", &t); for(int kase=1; kase<=t; kase++){ ll n;scanf("%lld", &n); printf("Case #%d: ", kase); if(n<=6) { printf("%d\n",a[n]); continue; } printf("%llu\n",176 * (n-6) + (n-6) * (n-7) * 14 + 473); } return 0; } 

Python打表

# 代码

  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  #include int dir[][2]={{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1},{-2,-1},{-1,-2}}; struct node{ int x, y, steps; }; const int maxn = 1111; int ans[maxn]; bool vis[maxn][maxn]; void bfs() { queue q; q.push(node{500,500,0}); ans[0] = 1; vis[500][500] = 1; while(!q.empty()){ node cur = q.front(); q.pop(); if(cur.steps == 20) continue; for(int i=0; i<8; i++){ node nxt = cur; nxt.x += dir[i][0], nxt.y += dir[i][1]; if(vis[nxt.x][nxt.y]) continue; vis[nxt.x][nxt.y] = 1; ans[++nxt.steps] ++; q.push(nxt); } } } int main() { bfs(); int ret = 0; for(int i=0;i<=20;i++) printf("%d ", ans[i]);puts(""); for(int i=0;i<20;i++) printf("%d ", (ret+=ans[i])); puts(""); for(int i=1;i<20;i++) printf("%d ",ans[i]-ans[i-1]); for(int i=7;i<=20;i++) printf("%d ",176 * (i-6) + (i-6) * (i-7) / 2 * 28 + 473); }