תיאור
באמצעות נגדים בעלי התנגדות $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.
את העובדה שההתנגדות השקולה מצומת $1$ לצומת $n$ היא $1\,[\Omega]$ ניתן להסביר באופן הבא:
- מכיוון שלכל הנגדים יש התנגדות $1\,[\Omega]$, ומתוך סימטריה הפוטנציאלים בצמתים $2$ ו-$3$ שווים, ניתן להתייחס לנגד שביניהם כאילו אינו קיים.
- כתוצאה מכך, המעגל מצטמצם לשני ענפים במקביל, כאשר כל ענף מורכב משני נגדים של $1\,[\Omega]$ בטור.
- ההתנגדות השקולה של שני נגדים של $1\,[\Omega]$ בטור היא $2\,[\Omega]$, וההתנגדות השקולה של שני נגדים של $2\,[\Omega]$ במקביל היא $1\,[\Omega]$.
גם הפלט הבא נחשב נכון:
2 1 1 2