今日题目：3 div 1

You are given a board with nn rows and nn columns, numbered from 11 to nn. The intersection of the aa-th row and bb-th column is denoted by (a,b)(a,b).

A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on (a,b)(a,b) attacks the cell (c,d)(c,d) if a=ca=c or b=db=d or a−b=c−da−b=c−d.

The blue cells are under attack.

What is the minimum number of half-queens that can be placed on that board so as to ensure that each square is attacked by at least one half-queen?

Construct an optimal solution.

Input

The first line contains a single integer nn (1≤n≤105) — the size of the board.

Output

In the first line print a single integer kk — the minimum number of half-queens.

In each of the next kk lines print two integers ai, bi (1≤ai,bi≤n) — the position of the ii-th half-queen.

If there are multiple solutions, print any.

题目分析

题目难度：⭐️⭐️⭐️

题目涉及算法：数论，dp，暴力。

ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力

题解报告：

1.思路

解决无填充 对角线 斜线 挨着对角线的斜线，debug的过程中就AC了，可以等p佬完美题解。

2.代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int m = (n-1)*2/3+1;
  cout<<m<<endl;
  if(m&1)
  {
    int num = m/2,num1 = m-num;
    int sum = num1+1;
    for(int i=1;i<=num1;i++)
    {
      cout<<i<<" "<<sum-i<<endl;
    }
    sum = 2*m-num+1;
    for(int i=m;i>=m-num+1;i--)
    {
      cout<<i<<" "<<sum-i<<endl;
    }
  }
  else
  {
    int num = m/2,num1 = m-num+1;
    int sum = num1+1;
    for(int i=2;i<num1;i++)
    {
      cout<<i<<" "<<sum-i<<endl;
    }
    sum = 2*m-num+1;
    for(int i=m;i>=m-num+1;i--)
    {
      cout<<i<<" "<<sum-i<<endl;
    }
    cout<<1<<" "<<1<<endl;
  }
  return 0;
}