Descrizione
Utilizzando esclusivamente resistori con resistenza $1\,[\Omega]$, costruisci un resistore con resistenza $\sqrt{D}\,[\Omega]$.
Ti viene dato un intero positivo $D$. Costruisci un grafo non orientato connesso che soddisfi tutte le seguenti condizioni. Sotto i vincoli di questo problema, si può dimostrare che un tale grafo esiste sempre.
- Il numero di vertici $N$ è compreso tra $2$ e $300$ ($2$ e $300$ inclusi), e ciascun vertice ha un'etichetta distinta da $1$ a $N$.
- Il numero di archi $M$ è al massimo $300$, e sono ammessi cappi (self-loop) e archi multipli.
- La "resistenza equivalente dal vertice $1$ al vertice $N$", definita come segue, ha un errore assoluto entro $\pm 10^{-6}$ rispetto a $\sqrt{D}$.
Sia $G$ un grafo non orientato connesso con $n$ vertici e $m$ archi ($n \ge 2$), e supponiamo che il $j$-esimo arco colleghi i vertici $a_j, b_j$. Consideriamo l'assegnazione di un numero reale $V_i$ ($i = 1, 2, \dots, n$) a ciascun vertice del grafo $G$ e di un numero reale $I_j$ ($j = 1, 2, \dots, m$) a ciascun arco, in modo che tutte le seguenti equazioni siano soddisfatte:
- $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$
Si può dimostrare che una tale assegnazione esiste sempre e inoltre che il valore di $V_1 - V_n$ è univocamente determinato. Definiamo questo valore come la "resistenza equivalente dal vertice $1$ al vertice $n$".
Input
L'input è costituito da un singolo intero positivo $D$. ($1 \le D \le 5000$)
Output
Sulla prima riga, stampa il numero di vertici $N$ e il numero di archi $M$ del grafo costruito, in quest'ordine, separati da uno spazio.
Su ciascuna delle successive $M$ righe, la $i$-esima riga ($i = 1, 2, \dots, M$) deve contenere i due estremi dell'$i$-esimo arco, separati da uno spazio.
Se esistono più grafi che soddisfano le condizioni, è possibile stamparne uno qualsiasi.
Esempi
Input 1
1
Output 1
4 5 1 2 1 3 2 3 2 4 3 4
Note
Di seguito è riportata un'illustrazione dell'output per l'Esempio 1.
Il fatto che la resistenza equivalente dal vertice $1$ al vertice $n$ sia $1\,[\Omega]$ può essere spiegato come segue:
- Poiché tutti i resistori hanno resistenza $1\,[\Omega]$ e per simmetria i potenziali nei vertici $2$ e $3$ sono uguali, il resistore tra di essi può essere trattato come se non esistesse.
- Di conseguenza, il circuito si riduce a due rami in parallelo, ciascuno costituito da due resistori da $1\,[\Omega]$ in serie.
- La resistenza equivalente di due resistori da $1\,[\Omega]$ in serie è $2\,[\Omega]$, e la resistenza equivalente di due resistori da $2\,[\Omega]$ in parallelo è $1\,[\Omega]$.
Anche il seguente output è considerato corretto:
2 1 1 2