Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Сипаттамасы

Кедергісі $1\,[\Omega]$ болатын резисторларды ғана пайдаланып, кедергісі $\sqrt{D}\,[\Omega]$ болатын резистор құрастырыңыз.

Сізге оң бүтін $D$ саны берілген. Төмендегі шарттардың барлығын қанағаттандыратын бір байланысқан бағытталмаған граф құрастырыңыз. Осы есептің шектеулерінде мұндай графтың әрқашан табылатынын дәлелдеуге болады.

  • Төбелер саны $N$ мәні $2$ мен $300$ аралығында ($2$ мен $300$ қоса алғанда) болады және әрбір төбенің $1$-ден $N$-ге дейінгі әртүрлі нөмірі бар.
  • Қырлар саны $M$ көп дегенде $300$ болады, ілмектерге (self-loops) және еселі қырларға (multiple edges) рұқсат етіледі.
  • Төменде анықталған «$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.