小 W מהמחלקה להנדסת תוכנה נמצא בבחינה בשרטוט הנדסי, אך הביא רק סרגל שסימוניו נשחקו עם השנים ומחוגה. בלית ברירה הוא פונה אליכם, בעלי יכולת מדהימה בבניות גאומטריות. השתמשו בסרגל ללא סימונים ובמחוגה כדי לעזור ל־小 W להשלים את השרטוט במהירות ובדיוק.
נפשט את הבעיה: נניח של־小 W כבר יש מערכת צירים ואורך יחידה. עליכם לבנות בסרגל ובמחוגה את האורך $L_0$, כלומר לקבל את הנקודה $(L_0,0)$.
מותר להשתמש בשלוש הפעולות הבאות:
$line(A,B)$: להעביר ישר דרך הנקודות $A$ ו־$B$.
$circle(O,A,B)$: לצייר מעגל שמרכזו בנקודה $O$ ורדיוסו המרחק בין $A$ ל־$B$.
$intersect(i,j)$: לסמן את כל נקודות החיתוך של הצורה ה־$i$ והצורה ה־$j$. אם יש כמה נקודות, יש לסמן את כולן.
בתחילה 小 W מספק את ראשית הצירים $O(0,0)$, שהיא נקודה מספר $0$. אורך היחידה נתון באמצעות נקודה מספר $1$, שקואורדינטותיה $(1,0)$. כמו כן נתונים ציר $x$ (צורה מספר $0$) וציר $y$ (צורה מספר $1$).
כל הנקודות והצורות החדשות המתקבלות במהלך הפעולות ימוספרו בהמשך הרצף.
נניח שהמספר הנוכחי הוא $n$. הנקודה הנוצרת מפעולת $intersect$ תקבל את המספר $n+1$.
אם לשתי הצורות אין נקודת חיתוך, לא תיווצר נקודה חדשה.
אם יש שתי נקודות חיתוך, הנקודה בעלת ערך $x$ הקטן יותר (ובמקרה של שוויון, ערך $y$ הקטן יותר) תקבל את המספר $n+1$, והאחרת תקבל את המספר $n+2$.
עליכם לקבל את הנקודה $(L_0,0)$ ולציין את מספרה. אין צורך לקבל את הערך המדויק, אך הסטייה מן הערך המדויק ומספר הפעולות שבהן השתמשתם ישפיעו על הניקוד.
קלט
זוהי משימה שבה מגישים קובצי פלט. כל קובצי הקלט, draw1.in עד draw10.in, נמצאים בתיקיית המשימה.
כל נתון קלט $x_0$ הוא ביטוי לחישוב ב־python. הסימון ** מציין העלאה בחזקה; למשל, 3 ** 2 מציין $3^2$, ו־2 ** 0.5 מציין $\sqrt{2}$.
כדי לספק דיוק גבוה יותר, המספרים בביטוי מומרים לטיפוס 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
הסבר
משמעות חמש הפעולות בדוגמה היא:
מציירים מעגל שמרכזו $O$ ורדיוסו אורך היחידה. זהו מעגל מספר $2$.
מוצאים את חיתוך צורה מספר $2$ (המעגל) עם ציר $y$. נקודות החיתוך הן מספר $2$, שקואורדינטותיה $(0,-1)$, ומספר $3$, שקואורדינטותיה $(0,1)$.
מציירים מעגל שמרכזו $O$ ורדיוסו המרחק בין נקודה מספר $1$ לנקודה מספר $3$. זהו מעגל מספר $3$.
מחברים את הנקודות $(1,0)$ ו־$(0,1)$. הישר שנוצר הוא צורה מספר $4$.
מוצאים את חיתוך צורה מספר $3$ (המעגל) עם ציר $x$. נקודות החיתוך הן מספר $4$, שקואורדינטותיה $(-\sqrt{2},0)$, ומספר $5$, שקואורדינטותיה $(\sqrt{2},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 ידווח על תוצאת הבדיקה בהתאם לקובץ הפלט שסיפקתם. התוצאות האפשריות כוללות:
יציאה לא תקינה: שגיאה לא ידועה.
Invalid parameters for checker.: הפרמטרים שנמסרו ל־checkerאינם תקינים.Input/Output file does not exist.: קובץ הקלט או הפלט אינו קיים.Output invalid: קובץ הפלט שגוי. ייתכן שתופיע גם הודעה המפרטת את השגיאה.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) מקובץ הקלט אל חלון המסוף ולחצו על Enter כדי לקבל קירוב לערכו. ניתן להחליף את המספר 100 בקוד שלעיל בדיוק הרצוי לכם.
הערות מיוחדות
אם תשתמשו בקובצי קלט שיצרתם בעצמכם לצורך ניפוי שגיאות, גודל גדול מדי עלול לגרום לשגיאה ב־checker. במקרה כזה נסו נתונים קטנים יותר.
שמרו היטב את קובצי הקלט draw*.in, את קובצי הפלט שלכם draw*.out ואת קובצי פרמטרי הניקוד draw*.ans, וגבו אותם בזמן כדי למנוע מחיקה בטעות.