האם אתם מכירים את חברת Just Ordinary Inventions? עיסוקה של החברה הוא ליצור ״המצאות רגילות בלבד״.

JOI משחק במשחק החדש ביותר שפותח בחברת Just Ordinary Inventions.

במשחק חוקרים מבוך המורכב מכמה חדרים וכמה דרכים. כל דרך מחברת שני חדרים שונים במבוך ואפשר לנוע בה בשני הכיוונים. בין כל שני חדרים שונים יש לכל היותר דרך אחת, ואין דרך ששני קצותיה באותו חדר. ידוע גם שאפשר להגיע מכל חדר לכל חדר אחר באמצעות כמה דרכים. החדרים דומים מאוד זה לזה: אי אפשר להבחין כלל בין חדרים שמספר הדרכים היוצאות מהם זהה רק על סמך מראם.

כדי לסייע לשחקן, בכל חדר יש סימן וכן שעליו אבן חן. בעזרת הסימן אפשר למנות את הדרכים היוצאות מהחדר: הראשונה, השנייה וכן הלאה. מבנה המבוך אינו משתנה במהלך המשחק. לכן, יציאה מאותו חדר באותה דרך ממוספרת תמיד תוביל לאותו חדר. על הכן יש אבן חן אחת שהשחקן יכול לשנות את צבעה. צבעה הוא אחד מהצבעים $1,2,\ldots,X$, ובתחילת המשחק צבע אבני החן בכל החדרים הוא צבע $1$. הצבע אינו משתנה אלא אם השחקן משנה אותו.

JOI הבין שאם יכיר את מבנה המבוך, כלומר אילו חדרים מחוברים בדרכים, יוכל להשלים את המשחק בקלות. אולם למרות ניסיונותיו השונים, לא הצליח לקבוע את המבנה. לכן החלטתם לכתוב במקומו תוכנית שתקבע את מבנה המבוך.

המשימה

כתבו תוכנית שחוקרת את המבוך וקובעת את מבנהו. עם זאת, JOI אינו רוצה שיחשפו בפניו את המבנה כולו. לכן, במקום לדווח ישירות על המבנה, התוכנית צריכה לדווח לכל מספר שלם $i$ בין $1$ ל-$R$ את מספר זוגות החדרים שהמספר המזערי של דרכים שיש לעבור כדי לנוע ביניהם הוא בדיוק $i$. זוגות הנבדלים רק בסדר החדרים נחשבים לאותו זוג.

לצורך חקירת המבוך תקבלו ספרייה המאפשרת את הפעולות הבאות:

• לדעת כמה דרכים יוצאות מהחדר הנוכחי.
• לדעת מה צבע אבן החן שעל הכן בחדר הנוכחי.
• לשנות את צבע אבן החן שעל הכן בחדר הנוכחי לצבע נתון (אפשר לבחור גם בצבע הנוכחי). לאחר מכן לבחור דרך אחת היוצאת מהחדר ולנוע בה לחדר אחר.
• לדעת מה מספרה של הדרך האחרונה שבה עברתם, מתוך הדרכים היוצאות מהחדר הנוכחי.

פרטי המימוש

עליכם לכתוב תוכנית אחת המממשת את אופן הדיווח ל-JOI. התוכנית חייבת לכלול את dungeon2.h באמצעות include.

על התוכנית לממש את השגרה הבאה.

void Inspect(int R)

שגרה זו נקראת פעם אחת בלבד, בתחילת הריצה.

• הפרמטר R מציין שיש לדווח לכל מספר שלם $i$ בין $1$ ל-$R$ את מספר זוגות החדרים שהמספר המזערי של דרכים שיש לעבור ביניהם הוא בדיוק $i$ (החלפת סדר החדרים אינה יוצרת זוג חדש).

עליכם לדווח את התשובות באמצעות קריאה לשגרה הבאה.

void Answer(int D, int A)

• הפרמטרים D, A מציינים שבקריאה זו מדווחים כי יש $A$ זוגות חדרים שהמספר המזערי של דרכים שיש לעבור ביניהם הוא בדיוק $D$.

הקריאות ל-Answer חייבות לעמוד בתנאים הבאים:

• D חייב להיות מספר שלם בין $1$ ל-$R$. אחרת התשובה תיחשב שגויה [1].
• אסור לקרוא ל-Answer פעמיים או יותר עם אותו פרמטר D. אחרת התשובה תיחשב שגויה [2].
• יש לקרוא ל-Answer בדיוק $R$ פעמים. אחרת התשובה תיחשב שגויה [3].
• A חייב להיות מספר זוגות החדרים שהמספר המזערי של דרכים שיש לעבור ביניהם הוא בדיוק $D$. אחרת התשובה תיחשב שגויה [4].

אם קריאה ל-Answer נחשבת שגויה, אין הבטחה שהמשך התוכנית ירוץ.

בנוסף, התוכנית רשאית לקרוא לשגרות הבאות.

void Move(int I, int C)

• הפרמטר I הוא מספר הדרך שבה בוחר השחקן לנוע. מיד לאחר הקריאה, השחקן עובר מהחדר הנוכחי לחדר אחר בדרך שמספרה $I$ מתוך הדרכים היוצאות מהחדר הנוכחי.
• הפרמטר C מציין שלפני המעבר יש לשנות את צבע אבן החן שעל הכן בחדר הנוכחי לצבע $C$.

הקריאות ל-Move חייבות לעמוד בתנאים הבאים:

• אם $K$ הוא מספר הדרכים היוצאות מהחדר הנוכחי, I חייב להיות מספר שלם בין $1$ ל-$K$. אחרת התשובה תיחשב שגויה [5].
• אם $X$ הוא מספר צבעי אבני החן האפשריים, C חייב להיות מספר שלם בין $1$ ל-$X$. ערך $X$ נקבע לפי תת-המשימה. אחרת התשובה תיחשב שגויה [6].
• אסור לקרוא ל-Move יותר מ-$1\,500\,000$ פעמים. אחרת התשובה תיחשב שגויה [7].

int NumberOfRoads()

• פונקציה זו מחזירה את מספר הדרכים היוצאות מהחדר הנוכחי של השחקן.

int LastRoad()

• פונקציה זו מחזירה את מספרה של הדרך האחרונה שבה עבר השחקן מתוך הדרכים היוצאות מהחדר הנוכחי. אם הפונקציה נקראת לפני הקריאה הראשונה ל-Move, היא מחזירה $-1$.

int Color()

• פונקציה זו מחזירה את צבע אבן החן שעל הכן בחדר הנוכחי של השחקן.

לאחר הקריאה לשגרה Inspect, התשובות נבדקות.

מותר לממש שגרות נוספות לשימוש פנימי ולהכריז על משתנים גלובליים. אולם אסור לתוכנית המוגשת לתקשר בשום דרך עם הקלט הסטנדרטי, הפלט הסטנדרטי או קבצים אחרים.

הידור והרצה

ארכיון שניתן להוריד מאתר התחרות מכיל בודק לדוגמה לבדיקת התוכנית שכתבתם. הארכיון מכיל גם דוגמאות לקבצים שיש להגיש.

הבודק לדוגמה מורכב מקובץ אחד, grader.c או grader.cpp. כדי לבדוק את התוכנית, הריצו את הפקודות הבאות.

• עבור C:

gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• עבור C++:

g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

אם ההידור מצליח, נוצר קובץ הרצה בשם grader.

שימו לב שהבודק האמיתי שונה מהבודק לדוגמה. הבודק לדוגמה רץ כתהליך יחיד, קורא נתונים מהקלט הסטנדרטי וכותב את התוצאות לפלט הסטנדרטי.

קלט לבודק לדוגמה

הבודק לדוגמה קורא מהקלט הסטנדרטי את הנתונים הבאים.

• השורה הראשונה מכילה את המספרים השלמים $N,X,R$, מופרדים ברווחים. הם מציינים שבמבוך יש $N$ חדרים, חדר $1$, חדר $2$, וכן הלאה עד חדר $N$, שיש $X$ צבעי אבני חן, ושהתוכנית צריכה לדווח $R$ ערכים.
• בשורה שמספרה $2i-1$ ($1\le i\le N$) מתוך $2N$ השורות הבאות מופיע מספר שלם $D_i$, המציין שמהחדר $i$ יוצאות $D_i$ דרכים. בשורה שמספרה $2i$ ($1\le i\le N$) מופיעים $D_i$ המספרים השלמים $T_{i1},T_{i2},\ldots,T_{iD_i}$, מופרדים ברווחים. פירושם שמעבר בדרך שמספרה $j$ ($1\le j\le D_i$) מתוך הדרכים היוצאות מהחדר $i$ מוביל לחדר $T_{ij}$.
• בשורה שמספרה $j$ ($1\le j\le R$) מתוך $R$ השורות הבאות מופיע מספר שלם $A_j$. הוא מציין שיש $A_j$ זוגות חדרים שהמספר המזערי של דרכים שיש לעבור ביניהם הוא בדיוק $j$. כלומר, לכל $j$ ($1\le j\le R$), הבודק לדוגמה יחשיב קריאה ל-Answer עם D השווה ל-$j$ ו-A השווה ל-$A_j$ כנכונה, וכל תשובה אחרת כשגויה.

הבודק לדוגמה קורא לשגרה שלכם כאשר מיקומו ההתחלתי של השחקן הוא חדר 1.

פלט הבודק לדוגמה

אם התוכנית מסיימת את ריצתה כרגיל, הבודק לדוגמה כותב לפלט הסטנדרטי את המידע הבא בשורה אחת (המירכאות עצמן אינן מודפסות).

• אם התשובה נכונה, מודפס מספר הקריאות לפונקציה Move, למשל Accepted : #move = 8.
• אם התשובה שגויה, מודפס סוג השגיאה, למשל Wrong Answer [1].

מגבלות

כל נתוני הקלט עומדים בתנאים הבאים. למשמעות $N,D_i,T_{ij}$, ראו את הסעיף ״קלט לבודק לדוגמה״.

• $2\le N\le200$.
• $3\le X\le100$.
• $1\le R\le200$.
• $1\le D_i\le N-1$ ($1\le i\le N$).
• $1\le T_{ij}\le N$ וגם $T_{ij}\ne i$ ($1\le i\le N$, $1\le j\le D_i$).
• המספרים $T_{i1},T_{i2},\ldots,T_{iD_i}$ שונים זה מזה ($1\le i\le N$).
• לכל $i,j$ ($1\le i\le N$, $1\le j\le D_i$), קיים $k$ ($1\le k\le D_{T_{ij}}$) שעבורו $T_{T_{ij}k}=i$.
• אפשר להגיע מכל חדר לכל חדר אחר באמצעות כמה דרכים.

תתי-משימות

להלן, $N$ הוא מספר החדרים במבוך שבקלט ו-$M$ הוא מספר הדרכים.

תת-משימה 1 [17 נקודות]

מתקיימים התנאים הבאים.

• $N\le50$.
• $M\le100$.
• $X=100$.

תת-משימה 2 [27 נקודות]

מתקיימים התנאים הבאים.

• $N\le50$.
• $M\le100$.
• $X=3$.

תת-משימה 3 [56 נקודות]

• $X=3$.

בתת-משימה זו הניקוד נקבע באופן הבא.

• נסמן ב-$L$ את הערך המרבי של הגודל הבא על פני כל מקרי הבדיקה בתת-המשימה:

  • $\frac{C}{M}$, כאשר $C$ הוא מספר הקריאות ל-Move.

• הניקוד בתת-המשימה הוא:

  • אם $L\le14$: 56 נקודות.
  • אם $14<L\le32$: $\lfloor70-L\rfloor$ נקודות.
  • אם $32<L\le64$: $\left\lfloor54-\frac{L}{2}\right\rfloor$ נקודות.
  • אם $64<L$: אפס נקודות.

כאן, $\lfloor x\rfloor$ הוא המספר השלם הגדול ביותר שאינו גדול מ-$x$.

במערכת השיפוט, אם התוכנית מסתיימת כראוי והתשובה נחשבת נכונה, מוצג Accepted בשדה הפרטים. עם זאת, שימו לב שבניקוד תת-משימה 3, במקרי בדיקה שבהם $64<\frac{C}{M}$ עבור $C,M$ שהוגדרו לעיל, בשדה התוצאה מוצגת תשובה שגויה.

דוגמה

להלן דוגמה לקלט שהבודק לדוגמה קורא ולקריאות לשגרות המתאימות לו.

קלט 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

דוגמה לקריאות לשגרות

שימו לב שקריאות הפונקציות בדוגמה זו אינן בהכרח בעלות משמעות.