Anna ו-Bruno הם ארכאולוגים. הם חוקרים עתיקות באיראן.

תפקידיהם הם כדלקמן: Anna מבקרת באתרים ומגלה ממצאים, ו-Bruno מנתח את התוצאות במחנה הבסיס.

המחקר שלהם מתוכנן להימשך $Q(=1\,000)$ ימים. בכל יום Anna שולחת את התוצאות ל-Bruno באמצעות מכשיר תקשורת. התוצאות של כל יום מיוצגות במספר שלם $X$.

Anna יכולה להשתמש במכשיר התקשורת פעם אחת בלבד בכל יום. הוא יכול לשלוח סדרה באורך $N(=150)$ המורכבת מאפסים ואחדים.

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

יש סכנה שהמחקר יתעכב. מכיוון שאתם מועמדים להשתתף בתחרות תכנות בין-לאומית באיראן, Anna ו-Bruno מבקשים מכם לכתוב תוכנית שתשלח את תוצאות המחקר שלהם.

המשימה

כתבו שתי תוכניות שיאפשרו תקשורת בין Anna ל-Bruno.

• בהינתן אורך הסדרה $N$, המספר השלם שיש לשלוח $X$, מספר המקומות הפגומים $K$ ומיקומיהם $P$, התוכנית הראשונה קובעת את הסדרה $S$ שתשלח Anna.
• בהינתן הסדרה $A$ שקיבל Bruno, התוכנית השנייה משחזרת את המספר השלם $X$.

במקום שבו מכשיר התקשורת תקין, לסדרות $S$ ו-$A$ יש אותו ערך. במקום פגום, הערך בסדרה $A$ הוא תמיד 0, ללא קשר לערך בסדרה $S$.

פרטי מימוש

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

הקובץ הראשון הוא Anna.c או Anna.cpp. קובץ זה קובע סדרה שתשלח Anna ומממש את הפונקציה הבאה. על התוכנית לכלול את Annalib.h.

void Anna( int N, long long X, int K, int P[] )

בכל מקרה בדיקה פונקציה זו נקראת $Q=1\,000$ פעמים.

• הפרמטר $N$ הוא אורך הסדרה שתישלח.
• הפרמטר $X$ הוא המספר השלם שיש לשלוח.
• הפרמטר $K$ הוא מספר המקומות הפגומים.
• הפרמטר P[] הוא סדרה באורך $K$ המתארת את מיקומי המקומות הפגומים.

בתוך הפונקציה Anna יש לקרוא לפונקציה הבאה.

void Set( int pos, int bit )

פונקציה זו קובעת סיבית בסדרה $S$ שמכשיר התקשורת ישלח.

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

יש לקרוא ל-Set בדיוק $N$ פעמים בתוך Anna. כאשר Anna מסתיימת, אם מספר הקריאות ל-Set שונה מ-$N$, התוכנית תקבל Wrong Answer[4].

התוכנית תופסק אם הקריאה לפונקציה של Anna נחשבת בלתי תקינה.

הקובץ השני הוא Bruno.c או Bruno.cpp. קובץ זה משחזר את המספר השלם המייצג את תוצאות המחקר ומממש את הפונקציה הבאה. על התוכנית לכלול את Brunolib.h.

long long Bruno( int N, int A[] )

בכל מקרה בדיקה פונקציה זו נקראת $Q=1\,000$ פעמים.

• הפרמטר $N$ הוא אורך הסדרה שקיבל Bruno.
• הפרמטר $A$ הוא סדרת מספרים שלמים באורך $N$. זו הסדרה שקיבל Bruno.
• על הפונקציה Bruno לשחזר את ערכו של $X$ ולהחזירו.

תהליך הבדיקה

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

1. קובעים $\mathrm{cnt}=0$.
2. קוראים לפונקציה Anna פעם אחת.
3. תהי $S$ הסדרה שקבעה Anna. קובעים בסדרה $S$ את הערך 0 במיקומים שב-$P$ ומקבלים את הסדרה $A$. קוראים לפונקציה Bruno פעם אחת עם הפרמטר $A$.
4. קובעים $\mathrm{cnt}=\mathrm{cnt}+1$. אם $\mathrm{cnt}<Q$, חוזרים לשלב (2). אם $\mathrm{cnt}=Q$, עוברים לשלב (5).
5. התוכנית מקבלת ניקוד.

הערות חשובות

• זמן הריצה וצריכת הזיכרון מחושבים עבור שלבים (1), (2), (3), (4) של תהליך הבדיקה.
• אסור שהתוכנית תקבל תשובה שגויה בקריאה ל-Anna בשלב (2) או ל-Bruno בשלב (3). התוכנית חייבת לרוץ ללא שגיאת זמן ריצה.
• התוכנית רשאית לממש פונקציות נוספות לשימוש פנימי או להשתמש במשתנים גלובליים. התוכניות המוגשות יקומפלו עם תוכנית הבדיקה לקובץ הרצה יחיד. יש להצהיר על כל המשתנים הגלובליים והפונקציות הפנימיות כ-static כדי למנוע התנגשויות עם קבצים אחרים. מכיוון שהתוכניות של Anna ושל Bruno ירוצו בשני תהליכים נפרדים בעת הבדיקה, הן אינן יכולות לשתף משתנים גלובליים.
• בתהליך, כל אחת מהפונקציות Anna ו-Bruno נקראת $Q=1\,000$ פעמים. יש לאתחל כראוי את המשתנים שבהם משתמשות התוכניות.
• אסור לתוכנית להשתמש בקלט התקני ובפלט התקני. אסור לה לתקשר עם קבצים אחרים בשום דרך.

הידור והרצת בדיקה

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

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

C

gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

C++

g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

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

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

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

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

• השורה הראשונה מכילה מספר שלם $Q$.
• לאחר מכן נתון מידע על $Q$ שאילתות.

• המידע על כל שאילתה מורכב משתי שורות כדלקמן.

  • השורה הראשונה מכילה שלושה מספרים שלמים $N,X,K$ המופרדים ברווחים. פירוש הדבר הוא שאורך הסדרה שיש לשלוח הוא $N$, המספר השלם שעל Anna לשלוח הוא $X$, ויש $K$ מקומות פגומים.
  • השורה השנייה מכילה $K$ מספרים שלמים $P_0,P_1,\ldots,P_{K-1}$ המופרדים ברווחים. פירוש הדבר הוא שלכל $i$ ($0 \le i \le K-1$), המקום $P_i$ בסדרה פגום.

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

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

• אם התוכנית מקבלת תשובה שגויה, תוכנית הבדיקה לדוגמה כותבת את סוגה בצורה „Wrong Answer [1]” והתוכנית שלכם מופסקת.
• אם אף קריאה לפונקציה Anna אינה נחשבת שגויה, תוכנית הבדיקה לדוגמה כותבת „Accepted” ואת הערך $L^*$. להגדרת $L^*$ ראו את סעיף הניקוד.

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

מגבלות

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

• $Q=1000$.
• $N=150$.
• $0 \le X \le 1\,000\,000\,000\,000\,000\,000$.
• $1 \le K \le 40$.
• $0 \le P_i \le N-1$ ($0 \le i \le K-1$).
• $P_i < P_{i+1}$ ($0 \le i \le K-2$).

ניקוד

• יהי $L^*$ המינימום של הערך הבא על פני כל מקרי הבדיקה של המשימה.

  • המספר השלם המרבי $L \le 40$ שעבורו, לכל שאילתה עם $K \le L$, מחזיר Bruno את הערך הנכון של $X$.

• הניקוד במשימה מחושב באופן הבא:

  • אם $L^*=0$, הניקוד הוא 0 נקודות.
  • אם $1 \le L^* \le 14$, הניקוד הוא 8 נקודות.
  • אם $15 \le L^* \le 37$, הניקוד הוא $(L^*-15)\times 2+41$ נקודות.
  • אם $38 \le L^* \le 40$, הניקוד הוא $(L^*-38)\times 5+90$ נקודות.

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

להלן קלט לדוגמה לתוכנית הבדיקה וקריאות הפונקציות המתאימות. שימו לב שהדוגמה הבאה אינה מקיימת את מגבלות המשימה, מכיוון ש-$Q=2$ ו-$N=3$.

קלט 1

2
3 14 1
2
3 9 2
0 1

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

הפרמטרים לקריאות Anna(...), Bruno(...), Anna(...), Bruno(...) הם כדלקמן.