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.
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