Beschreibung
Konstruieren Sie ausschließlich unter Verwendung von Widerständen mit dem Widerstandswert $1\,[\Omega]$ einen Widerstand mit dem Widerstandswert $\sqrt{D}\,[\Omega]$.
Gegeben ist eine positive ganze Zahl $D$. Konstruieren Sie einen zusammenhängenden ungerichteten Graphen, der alle folgenden Bedingungen erfüllt. Unter den Einschränkungen dieser Aufgabe lässt sich zeigen, dass ein solcher Graph immer existiert.
- Die Anzahl der Knoten $N$ liegt zwischen $2$ und $300$ (einschließlich $2$ und $300$), und jeder Knoten hat eine eindeutige Nummer von $1$ bis $N$.
- Die Anzahl der Kanten $M$ beträgt höchstens $300$, wobei Schleifen und Mehrfachkanten erlaubt sind.
- Der unten definierte „effektive Widerstand von Knoten $1$ zu Knoten $N$“ weicht um einen absoluten Fehler von höchstens $\pm 10^{-6}$ von $\sqrt{D}$ ab.
Sei $G$ ein zusammenhängender ungerichteter Graph mit $n$ Knoten und $m$ Kanten ($n \ge 2$), und sei angenommen, dass die $j$-te Kante die Knoten $a_j, b_j$ verbindet. Wir betrachten die Zuordnung einer reellen Zahl $V_i$ ($i = 1, 2, \dots, n$) zu jedem Knoten des Graphen $G$ und einer reellen Zahl $I_j$ ($j = 1, 2, \dots, m$) zu jeder Kante, sodass alle folgenden Gleichungen erfüllt sind:
- $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$
Es lässt sich beweisen, dass eine solche Zuordnung immer existiert und dass darüber hinaus der Wert von $V_1 - V_n$ eindeutig bestimmt ist. Wir definieren diesen Wert als den „effektiven Widerstand von Knoten $1$ zu Knoten $n$“.
Eingabe
Die Eingabe besteht aus einer einzigen positiven ganzen Zahl $D$. ($1 \le D \le 5000$)
Ausgabe
Geben Sie in der ersten Zeile die Anzahl der Knoten $N$ und die Anzahl der Kanten $M$ des konstruierten Graphen in dieser Reihenfolge, getrennt durch ein Leerzeichen, aus.
In jeder der folgenden $M$ Zeilen soll die $i$-te Zeile ($i = 1, 2, \dots, M$) die beiden Endpunkte der $i$-ten Kante, getrennt durch ein Leerzeichen, enthalten.
Falls es mehrere Graphen gibt, die die Bedingungen erfüllen, kann ein beliebiger davon ausgegeben werden.
Beispiele
Eingabe 1
1
Ausgabe 1
4 5 1 2 1 3 2 3 2 4 3 4
Hinweis
Das Folgende ist eine Veranschaulichung der Ausgabe für Beispiel 1.
Dass der effektive Widerstand von Knoten $1$ zu Knoten $n$ gleich $1\,[\Omega]$ ist, lässt sich wie folgt erklären:
- Da alle Widerstände den Wert $1\,[\Omega]$ haben und aus Symmetriegründen die Potenziale an den Knoten $2$ und $3$ gleich sind, kann der Widerstand zwischen ihnen so behandelt werden, als wäre er nicht vorhanden.
- Infolgedessen reduziert sich die Schaltung auf zwei parallele Zweige, wobei jeder Zweig aus zwei in Reihe geschalteten $1\,[\Omega]$-Widerständen besteht.
- Der effektive Widerstand von zwei in Reihe geschalteten $1\,[\Omega]$-Widerständen beträgt $2\,[\Omega]$, und der effektive Widerstand von zwei parallel geschalteten $2\,[\Omega]$-Widerständen beträgt $1\,[\Omega]$.
Die folgende Ausgabe wird ebenfalls als korrekt gewertet:
2 1 1 2