Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Опис

Використовуючи лише резистори з опором $1\,[\Omega]$, сконструюйте резистор з опором $\sqrt{D}\,[\Omega]$.

Задано додатне ціле число $D$. Побудуйте один зв'язний неорієнтований граф, який задовольняє всі наведені нижче умови. За обмежень цієї задачі можна довести, що такий граф завжди існує.

  • Кількість вершин $N$ лежить у межах від $2$ до $300$ (включно з $2$ та $300$), і кожна вершина має унікальний номер від $1$ до $N$.
  • Кількість ребер $M$ не перевищує $300$, дозволяються петлі та кратні ребра.
  • «Еквівалентний опір між вершиною $1$ і вершиною $N$», визначений нижче, відрізняється від $\sqrt{D}$ за абсолютною похибкою не більше ніж на $\pm 10^{-6}$.

Нехай $G$ — зв'язний неорієнтований граф із $n$ вершинами та $m$ ребрами ($n \ge 2$), і нехай $j$-те ребро з'єднує вершини $a_j, b_j$. Розглянемо зіставлення кожній вершині графа $G$ дійсного числа $V_i$ ($i = 1, 2, \dots, n$), а кожному ребру — дійсного числа $I_j$ ($j = 1, 2, \dots, m$) так, щоб виконувалися всі такі рівняння:

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

Можна довести, що таке зіставлення завжди існує, і ба більше, значення $V_1 - V_n$ визначається однозначно. Ми визначаємо це значення як «еквівалентний опір між вершиною $1$ і вершиною $n$».

Вхідні дані

Вхідні дані складаються з одного додатного цілого числа $D$. ($1 \le D \le 5000$)

Вихідні дані

У першому рядку виведіть кількість вершин $N$ і кількість ребер $M$ побудованого графа в цьому порядку через пробіл.

У кожному з наступних $M$ рядків $i$-й рядок ($i = 1, 2, \dots, M$) має містити два кінці $i$-го ребра через пробіл.

Якщо існує декілька графів, що задовольняють умови, дозволяється вивести будь-який із них.

Приклади

Вхідні дані 1

1

Вихідні дані 1

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

Примітка

Нижче наведено ілюстрацію вихідних даних для Прикладу 1.

problem_17723_8.png

Те, що еквівалентний опір між вершиною $1$ і вершиною $n$ дорівнює $1\,[\Omega]$, можна пояснити так:

  • Оскільки всі резистори мають опір $1\,[\Omega]$, а через симетрію потенціали у вершинах $2$ і $3$ рівні, резистор між ними можна вважати відсутнім.
  • У результаті коло спрощується до двох паралельних гілок, кожна з яких складається з двох послідовно з'єднаних резисторів по $1\,[\Omega]$.
  • Еквівалентний опір двох послідовно з'єднаних резисторів по $1\,[\Omega]$ дорівнює $2\,[\Omega]$, а еквівалентний опір двох паралельно з'єднаних резисторів по $2\,[\Omega]$ дорівнює $1\,[\Omega]$.

Наведені нижче вихідні дані також вважаються правильними:

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.