Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

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.

problem_17723_8.png

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

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.