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

Kuvaus

Käyttäen vain vastuksia, joiden resistanssi on $1\,[\Omega]$, rakenna vastus, jonka resistanssi on $\sqrt{D}\,[\Omega]$.

Sinulle annetaan positiivinen kokonaisluku $D$. Muodosta yksi yhtenäinen suuntaamaton verkko, joka täyttää kaikki seuraavat ehdot. Tämän tehtävän rajoitusten puitteissa voidaan todistaa, että tällainen verkko on aina olemassa.

  • Solmujen lukumäärä $N$ on välillä $2$ ja $300$ ($2$ ja $300$ mukaan lukien), ja jokaisella solmulla on yksilöllinen tunnus väliltä $1$ – $N$.
  • Kaarien lukumäärä $M$ on enintään $300$, ja silmukat (self-loops) sekä rinnakkaiset kaaret (multiple edges) ovat sallittuja.
  • Alla määritelty ”tehollinen resistanssi solmusta $1$ solmuun $N$” poikkeaa arvosta $\sqrt{D}$ absoluuttiselta virheeltään enintään $\pm 10^{-6}$.

Olkoon $G$ yhtenäinen suuntaamaton verkko, jossa on $n$ solmua ja $m$ kaarta ($n \ge 2$), ja oletetaan, että $j$-s kaari yhdistää solmut $a_j, b_j$. Tarkastellaan reaaliluvun $V_i$ ($i = 1, 2, \dots, n$) asettamista jokaiselle verkon $G$ solmulle ja reaaliluvun $I_j$ ($j = 1, 2, \dots, m$) asettamista jokaiselle kaarelle siten, että kaikki seuraavat yhtälöt toteutuvat:

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

Voidaan todistaa, että tällainen asetus on aina olemassa ja että erotuksen $V_1 - V_n$ arvo on yksikäsitteisesti määrätty. Määrittelemme tämän arvon ”teholliseksi resistanssiksi solmusta $1$ solmuun $n$”.

Syöte

Syöte koostuu yhdestä positiivisesta kokonaisluvusta $D$. ($1 \le D \le 5000$)

Tuloste

Tulosta ensimmäiselle riville muodostetun verkon solmujen lukumäärä $N$ ja kaarien lukumäärä $M$ tässä järjestyksessä välilyönnillä erotettuina.

Seuraavilla $M$ rivillä $i$-nnen rivin ($i = 1, 2, \dots, M$) tulee sisältää $i$-nnen kaaren kaksi päätepistettä välilyönnillä erotettuina.

Jos ehdot täyttäviä verkkoja on useita, voit tulostaa niistä minkä tahansa.

Esimerkit

Syöte 1

1

Tuloste 1

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

Huomautus

Seuraavassa on havainnollistus Esimerkin 1 tulosteesta.

problem_17723_8.png

Se, että tehollinen resistanssi solmusta $1$ solmuun $n$ on $1\,[\Omega]$, voidaan selittää seuraavasti:

  • Koska kaikkien vastusten resistanssi on $1\,[\Omega]$ ja symmetrian perusteella solmujen $2$ ja $3$ potentiaalit ovat yhtä suuret, niiden välistä vastusta voidaan käsitellä kuin sitä ei olisi olemassa.
  • Tämän seurauksena piiri pelkistyy kahdeksi rinnakkaiseksi haaraksi, joista kumpikin koostuu kahdesta sarjaan kytketystä $1\,[\Omega]$ vastuksesta.
  • Kahden sarjaan kytketyn $1\,[\Omega]$ vastuksen tehollinen resistanssi on $2\,[\Omega]$, ja kahden rinnan kytketyn $2\,[\Omega]$ vastuksen tehollinen resistanssi on $1\,[\Omega]$.

Myös seuraava tuloste katsotaan oikeaksi:

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.