זו שאלה אינטראקטיבית.
רקע
לאחר חצי שנה, החנות של I 君 כבר אינה יכולה להמשיך לפעול. הוא החליט להעביר אותה לאחר ולהפוך לחוקר שיגלה את העולם הרחב והלא־נודע.
בעקבות תיאור בספר עתיק, הוא מצא בלב מדבר גדול ארמון תת־קרקעי שבנתה תרבות לא־מוכרת. הארמון מורכב מ־$N$ מערות גדולות ומ־$M$ מעברים דו־כיווניים המחברים ביניהן. בעזרת הספר הוא יכול לזהות באיזו מערה הוא נמצא, אך מבנה החיבורים של המעברים אינו מתועד בו. לכן קשה לו לחפש את האוצרות האינסופיים שעל פי האגדה חבויים בארמון.
כעת הוא גילה מנגנון מסתורי המספק מידע על הארמון, והחליט להשתמש בו כדי לגלות את מבנה החיבורים. סייעו לו לעשות זאת.
תיאור הבעיה
אפשר לייצג את הארמון כגרף פשוט לא־מכוון בעל $N$ קודקודים ו־$M$ קשתות. בגרף פשוט יש לכל היותר קשת ישירה אחת בין כל שני קודקודים. המערות ממוספרות מ־$0$ עד $n-1$. כרגע אינכם יודעים אילו קשתות קיימות.
בכל מערה יש מקור אור שיכול להיות דלוק או כבוי. המערה מוארת רק כשהמקור שבה דלוק. בתחילה כל מקורות האור כבויים, ואפשר לשנות את מצבם רק באמצעות המנגנון המסתורי. המנגנון תומך בארבע הפעולות הבאות:
- נותנים למנגנון מספר $x$, והוא הופך את מצב מקור האור במערה $x$ ובכל מערה המחוברת אליה ישירות במעבר: מקורות דלוקים נכבים, וכבויים נדלקים.
- נותנים למנגנון מספר $x$, והוא מציג את מצבו הנוכחי של מקור האור במערה $x$.
- נותנים למנגנון שני מספרים $x,y$, כדי להודיע שאתם בטוחים שקיים מעבר בין המערות האלה ולבקש ממנו לרשום אותו.
- נותנים למנגנון מספר $x$, והוא קובע אם כל המעברים המחוברים למערה $x$ כבר נרשמו.
אפשר לבצע פעולה רק לאחר סיום הפעולה הקודמת. אין להשתמש במנגנון ללא הגבלה: מגבלות מספר השימושים בארבע הפעולות הן $L_m,L_q,M,L_c$, בהתאמה. כתבו תוכנית שתסייע ל־I 君 להשתמש בו כראוי ולגלות נכונה את כל $M$ המעברים.
פרטי מימוש
אינכם צריכים, ואינכם אמורים, לממש פונקציה ראשית. עליכם לממש רק את explore(N, M), כאשר $N,M$ הם מספר המערות ומספר המעברים. אפשר לתקשר עם ספריית האינטראקציה באמצעות ארבע הפונקציות הבאות:
modify(x)
- מפעילה את פעולה 1 עם המספר $x$.
- עליכם להבטיח $0\le x<N$. אין לפונקציה ערך מוחזר.
query(x)
- מפעילה את פעולה 2 עם המספר $x$.
- עליכם להבטיח $0\le x<N$. הפונקציה מחזירה $0$ או $1$: $0$ כאשר מקור האור במערה $x$ כבוי, ו־$1$ כאשר הוא דלוק.
report(x, y)
- מפעילה את פעולה 3 עם המספרים $x,y$.
- עליכם להבטיח $0\le x,y<N$ ו־$x\ne y$. אין לפונקציה ערך מוחזר.
check(x)
- מפעילה את פעולה 4 עם המספר $x$.
- עליכם להבטיח $0\le x<N$. הפונקציה מחזירה $0$ או $1$, והיא מחזירה $1$ אם ורק אם כל המעברים המחוברים למערה $x$ כבר נרשמו באמצעות פעולה 3.
במהלך השיפוט, ספריית האינטראקציה תקרא ל־explore פעם אחת בדיוק.
מובטח שהגרף נקבע במלואו לפני תחילת האינטראקציה, והוא אינו נבנה באופן דינמי לפי האינטראקציה עם התוכנית שלכם. לכן כל פעולות האינטראקציה דטרמיניסטיות, ואין צורך לדעת כיצד הן ממומשות בספרייה.
מובטח שתחת מגבלות מספר הקריאות, זמן הריצה של ספריית האינטראקציה אינו עולה על שנייה אחת. כמות הזיכרון שהיא משתמשת בה קבועה ואינה עולה על $128\,\mathrm{MB}$.
אופן המימוש
בתיקיית העבודה של המתחרה ניתן הקובץ template_explore.cpp/c/pas. העתיקו אותו, שנו את שמו ל־explore.cpp/c/pas, וכתבו את פתרונכם על בסיסו.
למשתמשי C++ / C
- ודאו שהתוכנית מתחילה ב־
#include "explore.h". - ממשק הפונקציה שעליכם לממש הוא:
void explore(int N, int M);- ממשקי פונקציות האינטראקציה הזמינות הם:
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);למשתמשי Pascal
- שימו לב: התחביר למימוש הממשק ב־Pascal מורכב יחסית. כתבו את פתרונכם ישירות על בסיס
template_explore.pasשסופק, במקום לכתוב את הקוד מאפס. - ממשק הפונקציה שעליכם לממש הוא:
procedure _explore(N, M : longint);- שימו לב ששם הפונקציה הוא
_exploreולאexplore. שימוש ב־exploreיגרום לשגיאת הידור. - ממשקי פונקציות האינטראקציה הזמינות הם:
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;בדיקת התוכנית
הקבצים grader.cpp/c ו־graderhelperlib.pas שבתיקיית השאלה הם מימוש לדוגמה של ספריית האינטראקציה שסיפקנו. המימוש בשיפוט הסופי שונה ממנו, ולכן הפתרון שלכם אינו אמור להסתמך על פרטי המימוש של הספרייה.
למשתמשי C/C++
- הידרו בתיקיית השאלה באמצעות הפקודות הבאות כדי ליצור קובץ הרצה:
- עבור C:
gcc grader.c explore.c -o explore -O2 -lm
- עבור C++:
g++ grader.cpp explore.cpp -o explore -O2 -lm
למשתמשי Pascal
- הידרו בתיקיית השאלה באמצעות הפקודה הבאה כדי ליצור קובץ הרצה:
fpc grader.pas -o"explore" -O2
הפעלת קובץ ההרצה
- קובץ ההרצה קורא מהקלט הסטנדרטי נתונים בפורמט הבא:
השורה הראשונה מכילה שלושה מספרים שלמים $L_m,L_q,L_c$, והשנייה שני מספרים שלמים $N,M$, במשמעויות שתוארו לעיל.
כל אחת מ־$M$ השורות הבאות מכילה שני מספרים שלמים $x,y$, המתארים מעבר בין מערה $x$ למערה $y$.
- לאחר הקריאה, הספרייה קוראת ל־
exploreפעם אחת בדיוק, ובודקת את הפונקציה שלכם באמצעות הנתונים שנקראו. לאחר שהפונקציה חוזרת כראוי, הספרייה בודקת אם החישוב נכון. אם כן, היא מדפיסהCorrectומידע על מספר הקריאות לפונקציות האינטראקציה; אחרת היא מדפיסה הודעת שגיאה מתאימה.
דוגמת אינטראקציה
נניח שקובץ ההרצה קורא את הנתונים הבאים:
100 200 300 3 2 0 1 1 2
שלושת המספרים בשורה הראשונה הם מגבלות מספר הקריאות לשלוש פעולות: מותר לקרוא ל־modify(x) לכל היותר $100$ פעמים, ל־query(x) לכל היותר $200$ פעמים ול־check(x) לכל היותר $300$ פעמים.
שני המספרים בשורה השנייה הם מספר המערות ומספר המעברים: $N=3,M=2$.
מספר הקריאות ל־report(x, y) אינו יכול לעלות על $M$, ובדוגמה זו על $2$.
להלן מהלך אינטראקציה תקין:
| תוכנית המתחרה | ספריית האינטראקציה | הסבר |
|---|---|---|
קוראת ל־explore(3, 2) |
תחילת הבדיקה | |
קוראת ל־modify(0) |
מבצעת פעולה 1 על מערה $0$ | |
קוראת ל־query(2) |
מחזירה $0$ | מקור האור במערה $2$ כבוי כעת |
קוראת ל־report(0, 1) |
התגלה המעבר $(0,1)$ והוא נרשם | |
קוראת ל־check(0) |
מחזירה $1$ | כל המעברים המחוברים למערה $0$ נרשמו |
קוראת ל־report(2, 1) |
התגלה המעבר $(2,1)$ והוא נרשם | |
| מסיימת וחוזרת | מדפיסה למסך Correct |
האינטראקציה הסתיימה והתוצאה נכונה |
הקבצים שסופקו
בתיקיית השאלה:
grader.cpp/cו־graderhelperlib.pasהם מימוש לדוגמה של ספריית האינטראקציה שסיפקנו.explore.hו־grader.pasהם קובצי כותרת; אין צורך לעיין בתוכנם.template_explore.cpp/c/pasהם קובצי קוד פתרון לדוגמה שסיפקנו.explore1.in, explore2.in, explore3.inהם קלטי דוגמה לבדיקות.
הקפידו לגבות את כל הקבצים שסופקו. השיפוט אוסף רק את explore.c/cpp/pas מתוך תיקיית שאלה זו; שינויים בקבצים אחרים אינם משפיעים.
ניקוד
השיפוט הסופי אוסף רק את explore.cpp/c/pas. לשינויים בקבצים אחרים בתיקיית המתחרה אין השפעה על השיפוט.
תחילה חלות המגבלות הרגילות של שאלות תכנות: לדוגמה, שגיאת הידור נותנת אפס נקודות בכל השאלה; שגיאת ריצה, חריגה ממגבלת הזמן או הזיכרון וכדומה נותנות אפס בבדיקות המתאימות. מותר לגשת רק למשתנים שהגדרתם ולמשתנים שסיפקה ספריית האינטראקציה, ולזיכרון השייך להם. ניסיון לגשת לאזורים אחרים עלול לגרום לשגיאת הידור או ריצה.
בכפוף לתנאים אלה, תקבלו את מלוא הנקודות בבדיקה אם ורק אם:
- כל קריאה לפונקציה חוקית, ומספר הקריאות ל־
modify, query, checkאינו עולה על $L_m,L_q,L_c$, בהתאמה. - מכיוון שמספר הקריאות ל־
reportמוגבל ל־$M$, כל קריאה חייבת לרשום קשת קיימת וחדשה. כלומר, בעת קריאה ל־report(x, y)חייב להתקיים מעבר בין מערות $x,y$, ואסור שקדמה לה קריאה ל־report(x, y)או ל־report(y, x). - הפונקציה
exploreשמימשתם חוזרת באופן תקין. - כאשר
exploreחוזרת, כל $M$ המעברים כבר נרשמו באמצעותreport.
מגבלות ורמזים
יש $25$ בדיקות, וכל אחת שווה $4$ נקודות. גודל הנתונים והמגבלות לכל בדיקה מופיעים בטבלה:
| בדיקה | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | תכונות מיוחדות |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | ללא |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | ללא |
| $3$ | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | ללא |
| $4$ | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | ללא |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | ללא |
| $6$ | $59998$ | $N/2$ | $17N$ | $17N$ | $2M$ | A |
| $7$ | $99998$ | $N/2$ | $18N$ | $18N$ | $0$ | A |
| $8$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $9$ | $199998$ | $N/2$ | $10^7$ | $10^7$ | $0$ | A |
| $10$ | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| $11$ | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $13$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $15$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $18$ | $1004$ | $2000$ | $10^7$ | $5\times10^4$ | $2M$ | ללא |
| $19$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | ללא |
| $20$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | ללא |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | ללא |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | ללא |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | ללא |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | ללא |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | ללא |
שוב נזכיר: מובטח שהגרף נקבע במלואו לפני תחילת האינטראקציה, והוא אינו נבנה דינמית לפי האינטראקציה עם התוכנית שלכם.
משמעות התכונות המיוחדות בטבלה:
A: דרגתו של כל קודקוד היא בדיוק $1$.
B: לכל $x>0$ קיים בדיוק $y$ אחד המקיים $y<x$, כך שמערה $x$ מחוברת ישירות למערה $y$ במעבר.
C: קיימת תמורה $p_0,p_1,\ldots,p_{N-1}$ של $0\sim N-1$, כך שלכל $1\le i<N$ קיים מעבר המחבר בין המערות $p_{i-1}$ ו־$p_i$.
D: הגרף קשיר.
- רמז: התוכנית יכולה להבחין בין סוגי הנתונים האלה לפי ספרת היחידות של הפרמטר $N$ שנמסר לה.