Background

CTT2021 D1T1

Problem Description

For given $n,k$, you need to construct a matrix $A_{i,j}$ that contains only $0,1$, where $0\le i,j\le n$, satisfying:

1. $A_{i,i}=1$.
2. $A_{i,i+1}=1$.
3. For $i>j$, $A_{i,j}=0$.
4. If $A_{i,j}=1$ and $j-i>1$, then there exists $i<t<j$ such that $A_{i,t}=A_{t,j}=1$.
5. For $i\le j$, $(A^k)_{i,j}>0$.

You need to output every $(i,j)$ such that $A_{i,j}=1$ and $j-i>1$. Let the number of such pairs be $m$.

If your output does not meet the requirements, you will get no score for that test point. If your output meets the requirements, then you will be scored based on $m$.

Input Format

One line with two integers $n,k$.

Output Format

The first line contains an integer $m$. The next $m$ lines each contain two integers $i,j$, which represent each pair $(i,j)$ satisfying $A_{i,j}=1$ and $j-i>1$.

3 2

1
0 2

Hint

• $1900\le n\le 2000$.
• $2\le k\le 15$.

Each $2\le k\le 15$ corresponds to a subtask with total score $s(k)$. The score of each subtask is the minimum score among all test points in that subtask.

The score of each test point equals the total score of its subtask multiplied by $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$.

Translated by ChatGPT 5