Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

題目描述

只係用電阻為 $1\,[\Omega]$ 嘅電阻器,構造一個電阻為 $\sqrt{D}\,[\Omega]$ 嘅電阻器。

俾定一個正整數 $D$。請構造一個滿足以下所有條件嘅連通無向圖。喺題目俾定嘅約束之下,可以證明咁樣嘅圖一定存在。

  • 頂點數 $N$ 喺 $2$ 到 $300$ 之間(包含 $2$ 同 $300$),每個頂點都有由 $1$ 到 $N$ 嘅唔同編號。
  • 邊數 $M$ 最多係 $300$,允許存在自環同重邊。
  • 「由頂點 $1$ 到頂點 $N$ 嘅等效電阻」(定義如下)同 $\sqrt{D}$ 嘅絕對誤差喺 $\pm 10^{-6}$ 以內。

設 $G$ 係一個有 $n$ 個頂點同 $m$ 條邊嘅連通無向圖($n \ge 2$),假設第 $j$ 條邊連接頂點 $a_j, b_j$。考慮為圖 $G$ 嘅每個頂點分配一個實數 $V_i$($i = 1, 2, \dots, n$),同埋為每條邊分配一個實數 $I_j$($j = 1, 2, \dots, m$),令以下所有方程成立:

  • $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
  • $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
  • $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

可以證明咁樣嘅賦值一定存在,而且 $V_1 - V_n$ 嘅值係唯一確定嘅。我哋將呢個值定義為「由頂點 $1$ 到頂點 $n$ 嘅等效電阻」。

輸入格式

輸入為一個正整數 $D$。($1 \le D \le 5000$)

輸出格式

第一行輸出構造出嚟嘅圖嘅頂點數 $N$ 同邊數 $M$,用空格隔開。

接住落嚟嘅 $M$ 行入面,第 $i$ 行($i = 1, 2, \dots, M$)應該包含第 $i$ 條邊嘅兩個端點,用空格隔開。

如果存在多個滿足條件嘅圖,輸出其中任何一個就得。

範例

範例輸入 1

1

範例輸出 1

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

備註

以下係範例 1 輸出嘅示意圖。

problem_17723_8.png

由頂點 $1$ 到頂點 $n$ 嘅等效電阻係 $1\,[\Omega]$,解釋如下:

  • 因為所有電阻器嘅電阻都係 $1\,[\Omega]$,而且根據對稱性,頂點 $2$ 同 $3$ 嘅電勢相等,所以佢哋之間嘅電阻器可以當做唔存在。
  • 結果電路簡化為兩個並聯嘅分支,每個分支由兩個串聯嘅 $1\,[\Omega]$ 電阻器組成。
  • 兩個 $1\,[\Omega]$ 電阻器串聯嘅等效電阻係 $2\,[\Omega]$,兩個 $2\,[\Omega]$ 電阻器並聯嘅等效電阻係 $1\,[\Omega]$。

以下輸出亦都被視為正確:

2 1
1 2

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1532EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.