Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Beskrivning

Med hjälp av enbart resistorer med resistansen $1\,[\Omega]$, konstruera en resistor med resistansen $\sqrt{D}\,[\Omega]$.

Du får ett positivt heltal $D$. Konstruera en sammanhängande oriktad graf som uppfyller alla följande villkor. Under begränsningarna i detta problem kan det bevisas att en sådan graf alltid existerar.

  • Antalet hörn $N$ är mellan $2$ och $300$ ($2$ och $300$ inklusive), och varje hörn har en unik etikett från $1$ till $N$.
  • Antalet kanter $M$ är högst $300$, och öglor (self-loops) samt multipelkanter är tillåtna.
  • Den "effektiva resistansen från hörn $1$ till hörn $N$", definierad nedan, ligger inom ett absolut fel på $\pm 10^{-6}$ från $\sqrt{D}$.

Låt $G$ vara en sammanhängande oriktad graf med $n$ hörn och $m$ kanter ($n \ge 2$), och anta att den $j$-te kanten förbinder hörnen $a_j, b_j$. Betrakta att tilldela ett reellt tal $V_i$ ($i = 1, 2, \dots, n$) till varje hörn i grafen $G$, och ett reellt tal $I_j$ ($j = 1, 2, \dots, m$) till varje kant, så att alla följande ekvationer är uppfyllda:

  • $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$

Det kan bevisas att en sådan tilldelning alltid existerar, och dessutom att värdet på $V_1 - V_n$ är entydigt bestämt. Vi definierar detta värde som den "effektiva resistansen från hörn $1$ till hörn $n$".

Indata

Indata består av ett enda positivt heltal $D$. ($1 \le D \le 5000$)

Utdata

På den första raden, skriv ut antalet hörn $N$ och antalet kanter $M$ i den konstruerade grafen, i denna ordning, separerade med mellanslag.

På var och en av de följande $M$ raderna ska den $i$-te raden ($i = 1, 2, \dots, M$) innehålla de två ändpunkterna för den $i$-te kanten, separerade med ett mellanslag.

Om det finns flera grafer som uppfyller villkoren kan vilken som helst av dem skrivas ut.

Exempel

Indata 1

1

Utdata 1

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

Anmärkning

Följande är en illustration av utdata för Exempel 1.

problem_17723_8.png

Att den effektiva resistansen från hörn $1$ till hörn $n$ är $1\,[\Omega]$ kan förklaras på följande sätt:

  • Eftersom alla resistorer har resistansen $1\,[\Omega]$, och potentialerna vid hörnen $2$ och $3$ på grund av symmetri är lika, kan resistorn mellan dem behandlas som om den inte existerar.
  • Som ett resultat reduceras kretsen till två parallella grenar, där varje gren består av två seriekopplade $1\,[\Omega]$-resistorer.
  • Den effektiva resistansen för två seriekopplade $1\,[\Omega]$-resistorer är $2\,[\Omega]$, och den effektiva resistansen för två parallellkopplade $2\,[\Omega]$-resistorer är $1\,[\Omega]$.

Följande utdata betraktas också som korrekt:

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.