Beskrivelse
Ved kun å bruke motstander med resistans $1\,[\Omega]$, konstruer en motstand med resistans $\sqrt{D}\,[\Omega]$.
Du får gitt et positivt heltall $D$. Konstruer én sammenhengende urettet graf som oppfyller alle følgende betingelser. Under begrensningene i denne oppgaven kan det bevises at en slik graf alltid eksisterer.
- Antallet noder $N$ er mellom $2$ og $300$ ($2$ og $300$ inkludert), og hver node har en unik merkelapp fra $1$ til $N$.
- Antallet kanter $M$ er høyst $300$, og løkker (self-loops) og parallelle kanter er tillatt.
- Den «effektive resistansen fra node $1$ til node $N$», definert nedenfor, er innenfor en absolutt feil på $\pm 10^{-6}$ fra $\sqrt{D}$.
La $G$ være en sammenhengende urettet graf med $n$ noder og $m$ kanter ($n \ge 2$), og anta at den $j$-te kanten forbinder nodene $a_j, b_j$. Betrakt å tilordne et reelt tall $V_i$ ($i = 1, 2, \dots, n$) til hver node i grafen $G$, og et reelt tall $I_j$ ($j = 1, 2, \dots, m$) til hver kant, slik at alle følgende ligninger er oppfylt:
- $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 bevises at en slik tilordning alltid eksisterer, og videre at verdien av $V_1 - V_n$ er entydig bestemt. Vi definerer denne verdien som den «effektive resistansen fra node $1$ til node $n$».
Inndata
Inndata består av ett enkelt positivt heltall $D$. ($1 \le D \le 5000$)
Utdata
På den første linjen skal du skrive ut antallet noder $N$ og antallet kanter $M$ i den konstruerte grafen, i denne rekkefølgen, adskilt med mellomrom.
På hver av de følgende $M$ linjene skal den $i$-te linjen ($i = 1, 2, \dots, M$) inneholde de to endepunktene til den $i$-te kanten, adskilt med et mellomrom.
Hvis det finnes flere grafer som oppfyller betingelsene, kan hvilken som helst av dem skrives ut.
Eksempler
Inndata 1
1
Utdata 1
4 5 1 2 1 3 2 3 2 4 3 4
Merk
Følgende er en illustrasjon av utdataene for Eksempel 1.
At den effektive resistansen fra node $1$ til node $n$ er $1\,[\Omega]$, kan forklares slik:
- Siden alle motstander har resistans $1\,[\Omega]$, og potensialene ved nodene $2$ og $3$ på grunn av symmetri er like, kan motstanden mellom dem behandles som om den ikke eksisterer.
- Som et resultat reduseres kretsen til to grener i parallell, der hver gren består av to $1\,[\Omega]$-motstander i serie.
- Den effektive resistansen til to $1\,[\Omega]$-motstander i serie er $2\,[\Omega]$, og den effektive resistansen til två $2\,[\Omega]$-motstander i parallell er $1\,[\Omega]$.
Følgende utdata regnes også som riktig:
2 1 1 2