الوصف
باستخدام مقاومات ذات مقاومة $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