Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

תיאור

באמצעות נגדים בעלי התנגדות $1\,[\Omega]$ בלבד, בנו נגד בעל התנגדות $\sqrt{D}\,[\Omega]$.

נתון מספר שלם חיובי $D$. בנו גרף לא מכוון קשיר אחד המקיים את כל התנאים הבאים. תחת אילוצי בעיה זו, ניתן להוכיח שגרף כזה תמיד קיים.

  • מספר הצמתים $N$ הוא בין $2$ ל-$300$ (כולל $2$ ו-$300$), ולכל צומת יש תווית ייחודית מ-$1$ עד $N$.
  • מספר הקשתות $M$ הוא לכל היותר $300$, ומותרים לולאות עצמיות וקשתות מרובות.
  • "ההתנגדות השקולה מצומת $1$ לצומת $N$", המוגדרת להלן, נמצאת בטווח שגיאה מוחלטת של $\pm 10^{-6}$ מ-$\sqrt{D}$.

יהי $G$ גרף לא מכוון קשיר עם $n$ צמתים ו-$m$ קשתות ($n \ge 2$), ונניח שהקשת ה-$j$ מחברת את הצמתים $a_j, b_j$. נתבונן בהשמת מספר ממשי $V_i$ ($i = 1, 2, \dots, n$) לכל צומת בגרף $G$, ומספר ממשי $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.