يدخل 小 W، وهو من قسم هندسة البرمجيات، امتحان الرسم الهندسي، لكنه لم يُحضر سوى مسطرة محا الزمن تدريجاتها وفرجار. لم يجد بدًّا من طلب مساعدتك، فأنت تتمتع بقدرة مذهلة على الإنشاءات الهندسية. استخدم المسطرة غير المدرجة والفرجار لمساعدته على إنجاز الرسم بسرعة ودقة.

لنبسّط المسألة: افترض أن 小 W يمتلك بالفعل جهاز إحداثيات وطول وحدة. يريد منك إنشاء الطول $L_0$ بالمسطرة والفرجار، أي الحصول على النقطة $(L_0,0)$.

يمكنك استخدام العمليات الثلاث الآتية:

1. $line(A,B)$: ارسم المستقيم المار بالنقطتين $A$ و$B$.
2. $circle(O,A,B)$: ارسم دائرة مركزها $O$ ونصف قطرها المسافة بين $A$ و$B$.
3. $intersect(i,j)$: علّم جميع نقاط تقاطع الشكل ذي الرقم $i$ والشكل ذي الرقم $j$. إن وُجدت عدة نقاط، فعلّمها جميعًا.

في البداية، يزوّدك 小 W بنقطة الأصل $O(0,0)$ ذات الرقم $0$، وبالنقطة $(1,0)$ ذات الرقم $1$ التي تحدد طول الوحدة. كما يزوّدك بمحور $x$، وهو الشكل رقم $0$، ومحور $y$، وهو الشكل رقم $1$.

تُرقّم النقاط والأشكال الجديدة الناتجة عن العمليات بالأرقام التالية تباعًا.

إذا كان الرقم الحالي $n$، فإن النقطة التي تنتج عن عملية $intersect$ تُعطى الرقم $n+1$.

إذا لم يتقاطع الشكلان، فلا تنتج أي نقطة جديدة.

إذا وُجدت نقطتا تقاطع، فإن النقطة ذات الإحداثي $x$ الأصغر، أو ذات $y$ الأصغر عند تساوي $x$، تُعطى الرقم $n+1$، والأخرى الرقم $n+2$.

احصل على النقطة $(L_0,0)$ وحدّد رقمها. لا يلزم الحصول على القيمة الدقيقة، لكن فرق نتيجتك عن القيمة الدقيقة وعدد العمليات المستخدمة يؤثران في درجتك.

الإدخال

هذه مسألة تُسلَّم فيها ملفات الإجابات فقط. جميع ملفات الإدخال draw1.in إلى draw10.in موجودة في مجلد المسألة.

كل قيمة إدخال $x_0$ هي تعبير حسابي بلغة Python. يرمز ** إلى الأس؛ فمثلًا 3 ** 2 يمثل $3^2$، و2 ** 0.5 يمثل $\sqrt2$.

لتوفير دقة أعلى، تُحوَّل الأعداد في التعبير إلى النوع decimal، أي أعداد عشرية عالية الدقة. فمثلًا Decimal(2) يمثل $2$.

يُضمن وجود مسافة واحدة بين الأعداد والرموز، وكذلك بين الرموز بعضها وبعض.

ناتج شيفرة Python هو العدد المطلوب إنشاؤه.

انتبه إلى أن حسابه مباشرة باستخدام Python يعطي قيمة تقريبية، بينما المطلوب فعليًّا هو القيمة الدقيقة؛ أي إن القيمة التي تُقارَن بنتيجة المتسابق هي القيمة الدقيقة.

نوفر أيضًا الملف draw.pdf الذي يعرض تعبير كل مجموعة بيانات بصيغة سهلة القراءة.

الإخراج

لكل واحد من ملفات الإدخال العشرة draw1.in إلى draw10.in، سلّم ملف الإخراج الموافق، من draw1.out إلى draw10.out.

يحتوي السطر الأول من ملف الإخراج على عدد صحيح $n$ يمثّل عدد العمليات. تليه $n$ أسطر، في كل سطر عملية واحدة. صيغ العمليات الثلاث هي:

line: L A B
circle: C O A B
intersect: I i j

معاني المعاملات كما وردت في وصف المسألة.

يحتوي السطر الأخير من ملف الإخراج على عدد صحيح يحدّد رقم النقطة التي حصلت عليها في النهاية.

أمثلة

الإدخال 1

Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) )

الإخراج 1

5
C 0 0 1
I 1 2
C 0 1 3
L 1 3
I 0 3
5

ملاحظة

معاني العمليات الخمس في المثال هي:

1. ارسم دائرة مركزها $O$ ونصف قطرها طول الوحدة؛ وهي الشكل رقم $2$.
2. خذ نقطتي تقاطع الشكل رقم $2$، أي الدائرة، مع محور $y$: النقطة رقم $2$ عند $(0,-1)$ والنقطة رقم $3$ عند $(0,1)$.
3. ارسم دائرة مركزها $O$ ونصف قطرها المسافة بين النقطتين رقم $1$ ورقم $3$؛ وهي الشكل رقم $3$.
4. صِل النقطتين $(1,0)$ و$(0,1)$، فيكون المستقيم الناتج هو الشكل رقم $4$.
5. خذ نقطتي تقاطع الشكل رقم $3$، أي الدائرة، مع محور $x$: النقطة رقم $4$ عند $(-\sqrt2,0)$ والنقطة رقم $5$ عند $(\sqrt2,0)$.

إذن النقطة رقم $5$ هي النقطة المطلوبة في النهاية.

المهام الفرعية

لكل واحد من ملفات الإدخال العشرة draw1.in إلى draw10.in، نوفر ملف معاملات تقييم موافقًا، من draw1.ans إلى draw10.ans.

يتكوّن ملف معاملات التقييم من عشرة أسطر، في كل سطر عددان $c_i,x_i$. إذا كان القيمة المطلقة للفرق بين الإحداثي الأفقي $x$ للنقطة النهائية $(x,0)$ والقيمة $L_0$ لا يتجاوز $10^{-x_i}$، وكان عدد العمليات المستخدمة $n\le c_i$، فإنك تحصل على $i$ نقاط.

يُمنح أعلى تقييم تتحقق شروطه. وإذا لم يتحقق أي شرط، تكون الدرجة $0$.

كيفية اختبار الإخراج

نوفر الأداة checker لاختبار ما إذا كان ملف الإخراج مقبولًا. لاستخدامها، افتح الطرفية أولًا ثم نفّذ الأمر التالي للدخول إلى مجلد المسألة:

cd draw

ثم نفّذ:

./checker <case_no>

حيث case_no هو رقم حالة الاختبار. مثلًا:

./checker 3

يختبر ما إذا كان draw3.out مقبولًا.

بعد استدعاء البرنامج، يعطي checker نتيجة الاختبار بناءً على ملف الإخراج الذي قدمته، وتشمل النتائج:

1. خروج غير طبيعي: خطأ غير معروف.
2. Invalid parameters for checker.: المعاملات الممررة إلى checker غير صالحة.
3. Input/Output file does not exist.: ملف الإدخال أو الإخراج غير موجود.
4. Output invalid: ملف الإخراج غير صحيح؛ وقد تتضمن الرسالة معلومات تفصيلية عن الخطأ.
5. Correct! Your answer is n. Your score is s.: الإخراج مقبول، وعدد العمليات المستخدمة $n$، والدرجة لهذه الحالة $s$.

ميزات إضافية

يمكن لـchecker أيضًا فحص أي ملفات إدخال وإخراج. نفّذ في الطرفية:

cd draw
./checker <input_file> <output_file> <ans_file>

حيث input_file وoutput_file وans_file هي أسماء ملف الإدخال وملف الإخراج وملف مرجع التقييم، على الترتيب.

مثلًا:

./checker draw3.in draw3.out draw3.ans

يختبر ما إذا كان draw3.out مقبولًا.

يمكن استخدام -w لطباعة إحداثيات كل نقطة ناتجة. تكون صيغة كل سطر:

id x y

وتمثل رقم النقطة والإحداثي $x$ والإحداثي $y$، على الترتيب. طريقة الاستخدام:

./checker -w <input_file> <output_file> <ans_file>

أو:

./checker -w <case_no>

مثلًا:

./checker -w draw3.in draw3.out draw3.ans

يمكن استخدام -i لطباعة إخراج المتسابق أيضًا لتسهيل التنقيح. طريقة الاستخدام:

./checker -i <input_file> <output_file> <ans_file>

أو:

./checker -i <case_no>

مثلًا:

./checker -i draw3.in draw3.out draw3.ans

يمكن استخدام -e prec لتحديد دقة حسابات checker، أي عدد الأرقام المعنوية. من دون هذا الخيار، تكون قيمة $prec$ الافتراضية $200$. طريقة الاستخدام:

./checker -e <prec> <input_file> <output_file> <ans_file>

أو:

./checker -e <prec> <case_no>

مثلًا:

./checker -e 50 draw3.in draw3.out draw3.ans

يمكن الجمع بين الخيارات -e prec و-w و-i بأي ترتيب، مثل:

./checker -w -i -e 50 draw3.in draw3.out draw3.ans

ملاحظة

يمكن استخدام Python للحصول على قيمة تقريبية للتعبير. بعد تشغيل Python في الطرفية، أدخل:

from math import *
from decimal import *
getcontext().prec = 100

ثم انسخ التعبير من ملف الإدخال، وهو شيفرة Python، إلى نافذة الطرفية واضغط مفتاح الإدخال للحصول على قيمته التقريبية. يمكن استبدال العدد 100 في الشيفرة أعلاه بالدقة المطلوبة.

تنبيه خاص

إذا استخدمت ملفات إدخال أنشأتها بنفسك للتنقيح، فقد يتسبب كبر حجمها في خطأ داخل checker. إذا حدث ذلك، فجرّب بيانات أصغر حجمًا.

احتفظ بعناية بملفات الإدخال draw*.in وملفات إخراجك draw*.out وملفات معاملات التقييم draw*.ans، وأنشئ نسخًا احتياطية في الوقت المناسب لتجنب حذفها بالخطأ.