במקומות רבים ברוסיה יורד שלג בחורף. ברוסיה יש $N$ ערים, הממוספרות מ-$0$ עד $N-1$, ו-$N-1$ כבישים, הממוספרים מ-$0$ עד $N-2$. כביש $i$ ($0\le i\le N-2$) מחבר בשני הכיוונים שתי ערים שונות $A_i,B_i$ ($0\le A_i<B_i\le N-1$). אפשר להגיע בין כל שתי ערים שונות ברוסיה באמצעות כמה כבישים.

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

Anya ו-Boris עובדים ברשות התחבורה של רוסיה. Anya עובדת במחלקה לניהול מידע על הכבישים, ו-Boris במחלקה העונה לשאלות התושבים. התושבים שואלים מהו המספר המינימלי של כבישים שיורד בהם שלג שיש לעבור כדי להגיע מעיר $0$, בירת רוסיה, לעיר מסוימת אחרת. בדרך כלל, אחרי קבלת שאלה Boris מתקשר עם Anya ומשיב לתושב.

הפעם תתקיים ברוסיה אליפות עולם בתכנות במשך $Q$ ימים. צפוי שקווי התקשורת יהיו עמוסים בזמן התחרות, ויהיה קשה ל-Anya ול-Boris לתקשר ישירות. לכן הם החליטו לתקשר כך:

• בתחילת כל יום Anya מקבלת את מידע השלג של אותו היום ושולחת נתונים לשרת ממסר.
• כש-Boris מקבל שאלה מתושב, הוא משיב באמצעות תקשורת עם שרת הממסר.

עם זאת, על התקשורת שלהם חלות המגבלות הבאות:

• קיבולת שרת הממסר היא $L=1\,000$ סיביות. Anya יכולה לאחסן בו מידע באורך של לכל היותר $L$ סיביות.
• כל הנתונים המאוחסנים בשרת הממסר מאותחלים ל-$0$ בתחילת כל יום.
• בפעולת תקשורת אחת עם השרת, Boris יכול לקרוא סיבית אחת במיקום שהוא בוחר.
• כדי להשיב לשאלה אחת, Boris רשאי לתקשר עם שרת הממסר לכל היותר $20$ פעמים.

אתם מכירים את מנהל רשות התחבורה, והתבקשתם לתכנן אסטרטגיות עבור Anya ו-Boris.

המשימה

כתבו תוכנית המממשת אסטרטגיות עבור Anya ו-Boris המאפשרות לענות נכון על שאלות התושבים.

פרטי המימוש

עליכם להגיש שני קבצים באותה שפת תכנות.

שם הקובץ הראשון הוא Anya.c או Anya.cpp. קובץ זה מממש את האסטרטגיה של Anya, ועליו לממש את שתי השגרות הבאות. התוכנית צריכה לכלול את Anyalib.h.

• void InitAnya(int N, int A[], int B[])

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

• הפרמטר N מציין את מספר הערים.

• הפרמטרים A[] ו-B[] הם סדרות באורך $N-1$ המתארות את חיבורי הכבישים. האיברים A[i] ו-B[i] ($0\le i\le N-2$) הם מספרים שלמים המציינים שכביש $i$ מחבר בשני הכיוונים את הערים A[i] ו-B[i], ומקיימים $0\le A[i]<B[i]\le N-1$.

• void Anya(int C[])

פונקציה זו נקראת $Q$ פעמים לאחר הקריאה ל-InitAnya. היא מייצגת את בחירת רצף הסיביות ש-Anya תשמור בשרת הממסר לאחר עדכון מידע השלג בתחילת היום.

• הפרמטר C[] הוא סדרה באורך $N-1$ המתארת את מידע השלג בכבישים. האיבר C[i] ($0\le i\le N-2$) הוא מספר שלם, $0$ או $1$, המתאר את מצב כביש $i$: אם $C[i]=1$ יורד בו שלג, ואם $C[i]=0$ לא יורד בו שלג.

בתוך Anya אפשר לקרוא לפונקציה הבאה:

• void Save(int place, int bit)

פונקציה זו מייצגת פעולה שבה Anya שומרת סיבית בשרת הממסר.

• הפרמטר place מציין את מיקום הכתיבה. עליו להיות מספר שלם בין $0$ ל-$L-1$, כולל. קריאה עם ערך מחוץ לטווח תיחשב לתשובה שגויה [1]. בכל קריאה ל-Anya, אין לקרוא לפונקציה פעמיים או יותר עם אותו place. קריאה פעמיים עם אותו ערך תיחשב לתשובה שגויה [2].
• הפרמטר bit הוא הסיבית שנכתבת, ועליו להיות $0$ או $1$. כל ערך אחר יגרום לתשובה שגויה [3].

לאחר הקריאה ל-Save, תוכן הסיבית במקום place בשרת יהיה bit.

אם קריאה ל-Save נחשבת לתשובה שגויה, התוכנית מסתיימת מיד.

ממש לפני כל קריאה ל-Anya, כל הסיביות בשרת הממסר מאותחלות בהכרח ל-$0$. כלומר, במיקום שלא בוצעה בו שמירה באמצעות Save, יהיה $0$ בסיום Anya.

שם הקובץ השני הוא Boris.c או Boris.cpp. קובץ זה מממש את האסטרטגיה של Boris, ועליו לממש את שתי השגרות הבאות. התוכנית צריכה לכלול את Borislib.h.

• void InitBoris(int N, int A[], int B[])

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

• הפרמטר N מציין את מספר הערים.

• הפרמטרים A[] ו-B[] הם סדרות באורך $N-1$ המתארות את חיבורי הכבישים. האיברים A[i] ו-B[i] ($0\le i\le N-2$) הם מספרים שלמים המציינים שכביש $i$ מחבר בשני הכיוונים את הערים A[i] ו-B[i], ומקיימים $0\le A[i]<B[i]\le N-1$.

• int Boris(int city)

פונקציה זו נקראת כמה פעמים לאחר הקריאה ל-InitBoris. היא מייצגת את פעולתו של Boris בתגובה לשאלה מתושב.

• הפרמטר city מתאר את שאלת התושב. זהו מספר שלם בין $1$ ל-$N-1$, כולל. התושב שואל מהו המספר המינימלי של כבישים שיורד בהם שלג שיש לעבור כדי להגיע מעיר $0$ לעיר city.
• הפונקציה Boris צריכה להחזיר מספר שלם בין $0$ ל-$N-1$, כולל, שהוא התשובה לשאלת התושב. החזרת מספר מחוץ לטווח תיחשב לתשובה שגויה [4]. תשובה לא נכונה תיחשב לתשובה שגויה [7].

בתוך Boris אפשר לקרוא לפונקציה הבאה:

• int Ask(int place)

פונקציה זו מייצגת פעולה שבה Boris קורא סיבית משרת הממסר.

• הפרמטר place מציין את מיקום הקריאה. עליו להיות מספר שלם בין $0$ ל-$L-1$, כולל. ערך מחוץ לטווח יגרום לתשובה שגויה [5].

הערך המוחזר מ-Ask הוא תוכן הסיבית במקום place בשרת, כלומר $0$ או $1$. בכל קריאה ל-Boris אפשר לקרוא ל-Ask לכל היותר $20$ פעמים. יותר מ-$20$ קריאות יגרמו לתשובה שגויה [6].

אם קריאה ל-Ask נחשבת לתשובה שגויה, התוכנית מסתיימת מיד.

תהליך השיפוט

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

1. InitAnya ו-InitBoris נקראות פעם אחת כל אחת, בסדר זה, כדי לספק את מידע הכבישים.

2. עבור $i=1,\ldots,Q$, מבצעים לפי הסדר את הפעולות הבאות:

   • (a) קוראים ל-Anya פעם אחת. הדבר מייצג את בחירת רצף הסיביות ש-Anya תשמור בשרת לאחר עדכון מידע השלג בתחילת היום.
   • (b) קוראים ל-Boris בדיוק $D_i$ פעמים, כאשר $D_i$ הוא מספר שאלות התושבים ביום $i$. הפרמטר בקריאה ה-$j$ ($1\le j\le D_i$) הוא $R_{ij}$ ($1\le R_{ij}\le N-1$). אם הערך המוחזר בקריאה זו אינו שווה למספר המינימלי של כבישים שיורד בהם שלג שיש לעבור בדרך מעיר $0$ לעיר $R_{ij}$, נקבעת תשובה שגויה.

3. אם לא נקבעה תשובה שגויה באף שלב, התשובה נחשבת לנכונה.

הערות חשובות

• מדידת זמן הריצה והשימוש בזיכרון חלה על שלבים (1) ו-(2) ב״תהליך השיפוט״. במקרה של תשובה נכונה, בשלב (2) יהיו בסך הכול $Q$ קריאות ל-Anya ו-$D_1+\cdots+D_Q$ קריאות ל-Boris.
• Anya ו-Boris אינם יכולים לדעת את הערכים $D_1,\ldots,D_Q$.
• Boris אינה מקבלת מידע המציין מתי Anya עדכנה את הנתונים המאוחסנים בשרת הממסר.
• אפשר לממש שגרות נוספות לשימוש פנימי או להצהיר על משתנים גלובליים. אולם שתי התוכניות המוגשות מקושרות יחד עם תוכנית השיפוט לקובץ הרצה אחד. לכן יש להצהיר עם static על כל המשתנים הגלובליים והשגרות הפנימיות בכל קובץ, מלבד InitAnya, Anya, InitBoris ו-Boris, כדי למנוע התנגשויות עם קבצים אחרים. בזמן השיפוט התוכנית מופעלת כשני תהליכים, אחד עבור Anya ואחד עבור Boris, ולכן אין אפשרות לשתף ביניהם משתנים גלובליים.
• אסור להגשה שלכם לתקשר בדרך כלשהי עם הקלט הסטנדרטי, הפלט הסטנדרטי או קבצים אחרים.

הידור והרצה

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

תוכנית השיפוט לדוגמה מורכבת מקובץ יחיד, grader.c או grader.cpp. אם הקבצים שכתבתם הם Anya.c ו-Boris.c, או Anya.cpp ו-Boris.cpp, הריצו את הפקודות הבאות כדי לבדוק אותם.

• עבור C:

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• עבור C++:

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

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

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

סקירת תוכנית השיפוט לדוגמה

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

שימו לב להבדל הבא לעומת תוכנית השיפוט בפועל:

• תוכנית השיפוט לדוגמה אינה בודקת תשובה שגויה [7], ובמקום זאת מדפיסה את הערך המוחזר מ-Boris לכל שאלה.

הקלט של תוכנית השיפוט לדוגמה

תוכנית השיפוט לדוגמה קוראת מהקלט הסטנדרטי את הנתונים הבאים:

• השורה הראשונה מכילה את המספר השלם $N$, המציין שיש $N$ ערים.
• השורה ה-$(i+1)$ ($0\le i\le N-2$) מבין $N-1$ השורות הבאות מכילה את המספרים השלמים $A_i,B_i$, מופרדים ברווח. הם מציינים שכביש $i$ מחבר בשני הכיוונים את הערים $A_i$ ו-$B_i$.
• השורה הבאה מכילה את המספר השלם $Q$, המציין שהתחרות נמשכת $Q$ ימים.
• השורה ה-$i$ ($1\le i\le Q$) מבין $Q$ השורות הבאות מכילה מחרוזת $S_i$ באורך $N-1$ ולאחריה $D_i+1$ מספרים שלמים, מופרדים ברווחים. $S_i$ מתארת את מצב השלג ביום $i$: אם התו ה-$(j+1)$ משמאל ($0\le j\le N-2$) הוא 1, יורד שלג בכביש $j$; אם הוא 0, לא יורד שם שלג. הראשון מבין $D_i+1$ המספרים הוא $D_i$. $D_i$ המספרים הבאים הם $R_{i1},\ldots,R_{iD_i}$. כלומר, השאלה ה-$j$ ($1\le j\le D_i$) ביום $i$ עוסקת במספר המינימלי של כבישים שיורד בהם שלג שיש לעבור בדרך מעיר $0$ לעיר $R_{ij}$.

הפלט של תוכנית השיפוט לדוגמה

תוכנית השיפוט לדוגמה כותבת לפלט הסטנדרטי את המידע הבא (המירכאות אינן מודפסות בפועל):

• אם במהלך הריצה נקבעת תשובה שגויה, סוג השגיאה מודפס, למשל Wrong Answer [1], וההרצה מסתיימת.
• אם בכל $D_i$ הקריאות ל-Boris שלאחר הקריאה ה-$i$ ל-Anya ($1\le i\le Q$) לא נקבעה תשובה שגויה, מודפסת באותו שלב שורה אחת ובה $D_i$ מספרים שלמים מופרדים ברווחים. המספר ה-$j$ ($1\le j\le D_i$) הוא הערך שהחזירה Boris בקריאה עם הפרמטר $R_{ij}$.

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

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים:

• $2\le N\le500$.
• $1\le Q\le500$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• $1\le D_j$ ($1\le j\le Q$).
• $D_1+\cdots+D_Q\le500$.
• אפשר להגיע בין כל שתי ערים שונות באמצעות כמה כבישים.

תתי־משימות

תת־משימה 1 [15 נקודות]

• מתקיים $N\le20$.

תת־משימה 2 [5 נקודות]

• מתקיים $N\le100$.

תת־משימה 3 [35 נקודות]

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

• $A_i=i$ ($0\le i\le N-2$).
• $B_i=i+1$ ($0\le i\le N-2$).

תת־משימה 4 [45 נקודות]

אין מגבלות נוספות.

דוגמאות

להלן דוגמה לקלט שתוכנית השיפוט לדוגמה קוראת, ולקריאות הפונקציות המתאימות לו.

קלט 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

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

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

במקרה זה, הפרמטרים הנמסרים ל-InitAnya(...), ל-InitBoris(...) ולקריאה הראשונה והשנייה ל-Anya(...) הם כדלקמן: