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

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.

problem_17723_8.png

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

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.