Universal Cup Judging System

Universal Cup

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

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.

problem_17723_8.png

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

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.