Lýsing
Með því að nota eingöngu viðnám með viðnámsgildið $1\,[\Omega]$, smíðaðu viðnám með viðnámsgildið $\sqrt{D}\,[\Omega]$.
Gefin er jákvæð heiltala $D$. Smíðaðu eitt samanhangandi óstefnt net sem uppfyllir öll eftirfarandi skilyrði. Undir skorðum þessa verkefnis má sanna að slíkt net sé alltaf til.
- Fjöldi hnúta $N$ er á bilinu $2$ til $300$ ($2$ og $300$ meðtalin), og hver hnútur hefur einkvæmt merki frá $1$ til $N$.
- Fjöldi leggja $M$ er í mesta lagi $300$, og sjálfslykkjur (self-loops) og margfaldir leggir (multiple edges) eru leyfðir.
- „Virka viðnámið frá hnúti $1$ til hnúts $N$“, sem skilgreint er hér að neðan, er innan algildisskekkju upp á $\pm 10^{-6}$ frá $\sqrt{D}$.
Látum $G$ vera samanhangandi óstefnt net með $n$ hnúta og $m$ leggi ($n \ge 2$), og gerum ráð fyrir að $j$-ti leggurinn tengi hnútana $a_j, b_j$. Íhugum að úthluta rauntölu $V_i$ ($i = 1, 2, \dots, n$) á hvern hnút netsins $G$, og rauntölu $I_j$ ($j = 1, 2, \dots, m$) á hvern legg, þannig að allar eftirfarandi jöfnur séu uppfylltar:
- $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$
Sanna má að slík úthlutun sé alltaf til, og enn fremur að gildið á $V_1 - V_n$ sé ákvarðað á einkvæman hátt. Við skilgreinum þetta gildi sem „virka viðnámið frá hnúti $1$ til hnúts $n$“.
Inntak
Inntakið samanstendur af einni jákvæðri heiltölu $D$. ($1 \le D \le 5000$)
Úttak
Á fyrstu línunni skal prenta fjölda hnúta $N$ og fjölda leggja $M$ í smíðaða netinu, í þessari röð, aðskilið með bili.
Á hverri af næstu $M$ línum á $i$-ta línan ($i = 1, 2, \dots, M$) að innihalda endapunktana tvo á $i$-ta leggnum, aðskilda með bili.
Ef fleiri en eitt net uppfyllir skilyrðin má prenta hvert sem er þeirra.
Dæmi
Inntak 1
1
Úttak 1
4 5 1 2 1 3 2 3 2 4 3 4
Athugasemd
Eftirfarandi er myndskýring á úttakinu fyrir Dæmi 1.
Að virka viðnámið frá hnúti $1$ til hnúts $n$ sé $1\,[\Omega]$ má útskýra á eftirfarandi hátt:
- Þar sem öll viðnám hafa viðnámsgildið $1\,[\Omega]$, og vegna samhverfu eru mættin í hnútum $2$ og $3$ jöfn, má líta svo á að viðnámið á milli þeirra sé ekki til staðar.
- Þar af leiðandi einfaldast rásin í tvær hliðtengdar greinar, þar sem hvor grein samanstendur af tveimur raðtengdum $1\,[\Omega]$ viðnámum.
- Virkt viðnám tveggja raðtengdra $1\,[\Omega]$ viðnáma er $2\,[\Omega]$, og virkt viðnám tveggja hliðtengdra $2\,[\Omega]$ viðnáma er $1\,[\Omega]$.
Eftirfarandi úttak telst einnig rétt:
2 1 1 2