Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

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.

problem_17723_8.png

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

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.