#P18041. Square Resistance Value

Square Resistance Value

Square Resistance Value

题目描述

给定一个正整数 DD,请仅使用阻值为 1 Ω1\,\Omega 的电阻,构造一个等效电阻近似为 D Ω\sqrt D\,\Omega 的电路。

电路用一个连通无向图表示,必须满足:

  • 顶点数 NN 满足 2≤N≤3002\le N\le300,编号为 1,…,N1,\ldots,N;
  • 边数 M≤300M\le300,允许自环和重边;每条边表示一个 1 Ω1\,\Omega 电阻;
  • 顶点 11 与顶点 NN 之间的等效电阻 RR 满足 ∣R−D∣≤10−6|R-\sqrt D|\le10^{-6}。

等效电阻的严格定义如下。设第 jj 条边的端点为 aj,bja_j,b_j。为每个顶点指定电势 ViV_i,为每条边指定按 aja_j 到 bjb_j 定向的电流 IjI_j,使

Ij=Vaj−Vbj(1≤j≤M),I_j=V_{a_j}-V_{b_j}\quad(1\le j\le M), $$\sum_{b_j=i}I_j-\sum_{a_j=i}I_j=0\quad(2\le i\le N-1),$$∑bj=NIj−∑aj=NIj=1.\sum_{b_j=N}I_j-\sum_{a_j=N}I_j=1.

对于连通图,这样的赋值总是存在,且 V1−VNV_1-V_N 唯一确定。定义 R=V1−VNR=V_1-V_N。

在本题数据范围内,保证总存在满足要求的构造。

输入格式

输入一个正整数 DD,1≤D≤50001\le D\le5000。

输出格式

第一行输出顶点数 NN 和边数 MM。

接下来 MM 行,每行输出一条边的两个端点。

满足条件的任意连通无向图均可,不要求具有特定的串并联形式。误差使用绝对误差 10−610^{-6}。

样例 1

输入:

1

输出:

4 5
1 2
1 3
2 3
2 4
3 4