משחק קלפים אחד, הנחשב למבחן של תבונה, נקרא "קאנג". במשחק זה, לכל קלף יש ניקוד שהוא מספר שלם חיובי. בתחילת המשחק תקבלו $N$ קלפים להחזיק בידכם, וישנם עוד $M$ קלפים המונחים גלויים על השולחן בשורה משמאל לימין, כאשר אתם רואים את הניקוד של כל הקלפים — הן אלו שקיבלתם ליד והן אלו המונחים על השולחן. לאחר מכן, תוכלו למשוך קלפים נוספים מהשולחן במשך $k$ סיבובים, כאשר עליכם למשוך קלף אחד בכל פעם לפי הסדר משמאל לימין. לאחר משיכת קלף בכל סיבוב, באפשרותכם להשליך קלפים מהיד פעם אחת (1) — כל מספר של קלפים ביד שיש להם אותו ניקוד. עליכם לתכנן את המשחק כך שלאחר משיכת קלפים מהשולחן והשלכת קלפים מהיד במשך $k$ סיבובים מלאים, סכום הניקוד של הקלפים שנותרו ביד יהיה הקטן ביותר האפשרי.
נתבונן בדוגמה הבאה:
אם בהתחלה יש לכם חמישה קלפים עם ניקוד $6, 3, 9, 6, 3$, והקלפים המונחים על השולחן משמאל לימין הם בעלי ניקוד $4, 6, 9, 6$:
מקרה $k = 1$: אם באפשרותכם למשוך רק קלף אחד (1) מהשולחן, כאשר תמשכו את הקלף הראשון, ניקוד הקלפים שברשותכם יהיה $6, 3, 9, 6, 3, 4$. לאחר מכן תוכלו לבחור להשליך קלפים בעלי אותו ניקוד פעם אחת (1). הדרך הטובה ביותר היא לבחור להשליך 2 קלפים שהניקוד שלהם שווה ל-$6$, כדי שסכום הניקוד של הקלפים הנותרים יהיה הקטן ביותר ויעמוד על $3 + 9 + 3 + 4 = 19$.
מקרה $k = 2$: אם באפשרותכם למשוך 2 קלפים מהשולחן, הדרך הטובה ביותר היא: לאחר משיכת הקלף הראשון שהניקוד שלו שווה ל-$4$, תבחרו להשליך קלף אחד שהניקוד שלו שווה ל-$9$. הקלפים שנותרו ביד הם בעלי ניקוד $6, 3, 6, 3, 4$. לאחר מכן, כאשר תמשכו את הקלף ה-2 שהניקוד שלו שווה ל-$6$, תוכלו להשליך 3 קלפים שהניקוד שלהם שווה ל-$6$, מה שיגרום לכך שלקלפים הנותרים יהיה סכום הניקוד הקטן ביותר השווה ל-$3 + 3 + 4 = 10$.
מקרה $k = 3$: אם באפשרותכם למשוך 3 קלפים מהשולחן, הדרך הטובה ביותר היא: כאשר תמשכו את הקלף הראשון, ניקוד הקלפים ביד יהיה $6, 3, 9, 6, 3, 4$. לאחר מכן ניתן לבחור להשליך קלפים בעלי אותו ניקוד פעם אחת (1), והדרך הטובה ביותר היא להשליך את שני (2) הקלפים שהניקוד שלהם שווה ל-$3$, כך שיישארו ביד הקלפים $6, 9, 6, 4$. לאחר מכן, כאשר תמשכו את הקלף ה-2 שהניקוד שלו שווה ל-$6$, תוכלו להשליך 3 קלפים שהניקוד שלהם שווה ל-$6$, ויישארו ביד הקלפים $9, 4$. וכאשר תמשכו בפעם ה-3 קלף שהניקוד שלו שווה ל-$9$, תוכלו להשליך את שני (2) הקלפים שהניקוד שלהם שווה ל-$9$, מה שיגרום לכך שסכום הניקוד של הקלפים הנותרים יהיה $4$.
מקרה $k = 4$: אם באפשרותכם למשוך 4 קלפים מהשולחן, הדרך הטובה ביותר היא: לאחר משיכת הקלף הראשון שהניקוד שלו שווה ל-$4$, בחרו להשליך קלף אחד שהניקוד שלו שווה ל-$4$, כך שיישארו ביד קלפים עם ניקוד $6, 3, 9, 6, 3$. לאחר מכן, במשיכה ה-2 הקלף הוא בעל ניקוד השווה ל-$6$; הדרך הטובה ביותר היא להשליך את שני (2) הקלפים שהניקוד שלהם שווה ל-$3$, כך שיישארו ביד הקלפים $6, 9, 6, 6$. במשיכה ה-3 הקלף הוא בעל ניקוד השווה ל-$9$; בחרו להשליך את שני (2) הקלפים שהניקוד שלהם שווה ל-$9$. ובמשיכת הקלף האחרון שהניקוד שלו שווה ל-$6$, תוכלו להשליך 4 קלפים שהניקוד שלהם שווה ל-$6$. השלכה זו גורמת לכך שלא נותרים קלפים ביד, כלומר סכום הניקוד של הקלפים הוא $0$.
המשימה שלכם (Your Task)
מצאו את "סכום הניקוד הקטן ביותר של הקלפים שנותרו ביד" לאחר סיום $k$ סיבובים עבור $k = 1, 2, 3, \ldots, M$.
לשאלה זו יש פורמט כתיבת תוכנית השונה מהפורמט הרגיל, אשר ישמש בתחרות בפועל. אנא עיינו בסוף שאלה זו לגבי אופן השימוש.
פרטי מימוש
עליכם לממש את הפונקציה הבאה:
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)עם הפרמטרים הבאים:
- $A$ הוא מערך באורך $N$ המציין את מספרי הקלפים ביד בהתחלה.
- $B$ הוא מערך באורך $M$ המציין את מספרי הקלפים המונחים על השולחן, מסודרים משמאל לימין.
- הפונקציה תחזיר מערך $C$ באורך $M$ המייצג את סכום הניקוד הקטן ביותר האפשרי של הקלפים ביד לאחר $k$ סיבובים עבור $k = 1, 2, 3, \ldots, M$.
לדוגמה, אם $A = [6, 3, 9, 6, 3]$ ו-$B = [4, 6, 9, 6]$, על הפונקציה להחזיר את המערך $[19, 10, 4, 0]$.
מגבלות
- $1 \le N, M \le 10^6$
- $1 \le A[i] \le 10^9$ לכל $i$ המקיים $1 \le i \le N$
- $1 \le B[i] \le 10^9$ לכל $i$ המקיים $1 \le i \le M$
תתי-משימות
| קבוצת מבחנים | ניקוד מרבי לקבוצת מבחנים זו | תנאים |
|---|---|---|
| 1 | 5% | $N, M \le 5$ |
| 2 | 7% | $N \le 1\,000$ ו-$M = 1$ |
| 3 | 8% | $N, M \le 1\,000$, לכל הקלפים (הן הקלפים שביד והן הקלפים המוצגים על השולחן) יש מספרים שונים זה מזה |
| 4 | 12% | $N, M \le 1\,000$, לכל הקלפים שמתקבלים בנוסף יש אותו ערך |
| 5 | 16% | $N, M \le 1\,000$ |
| 6 | 28% | $N, M \le 100\,000$ |
| 7 | 24% | ללא תנאים נוספים |
הערות
הנחיות לכתיבת התוכנית
עבור שאלה זו, אופן כתיבת התוכנית והגשתה למערכת הבדיקה (Grader) שונה מהפורמט הכללי של כתיבת תוכניות, שבו המתחרה נדרש לכתוב את חלק קליטת הקלט ואת חלק הדפסת הפלט. בשאלה זו, על המתחרה לכתוב רק את חלק החישוב הנדרש בתוך הפונקציה הנתונה. נתוני הקלט השונים יהיו זמינים דרך פרמטרי הפונקציה, ותוצאות החישוב יוחזרו אף הן דרך הפונקציה, כך שהמתחרה אינו צריך לכתוב את חלק קליטת הקלט ואינו צריך לכתוב את חלק הדפסת הפלט.
המתחרה יקבל מספר קבצים כמפורט להלן; על המתחרה לערוך קובץ אחד בלבד כפי שמוגדר בשאלה ולהגיש קובץ זה למערכת:
grader.cppהוא הקובץ הראשי האחראי על קליטת הקלט והוצאת הפלט.kang.cppהוא הקובץ שבו על המתחרה לכתוב את חישובי התוכנית השונים והוא הקובץ שהמתחרה מגיש למערכת (בקובץkang.cppאסור שתהיה פונקצייתmain(), אך מותר שיהיו פונקציות אחרות).run_cpp.shהוא קובץ שהמתחרה יכול להפעיל כדי להריץ את התוכנית כולה.compile_cpp.shהוא קובץ שהמתחרה יכול להפעיל כדי להדר (לקמפל) את התוכנית.
המתחרה יקבל קובץ .zip הניתן להורדה מהמערכת, וכאשר מחלצים (extract) אותו נמצאים בו כל 4 הקבצים. מומלץ למתחרה להשתמש בעורך טקסט (text editor) או ב-IDE כדי לערוך את הקובץ kang.cpp, ולהדר או להריץ את התוכנית באמצעות הפעלת compile_cpp.sh או run_cpp.sh.
כאשר המתחרה מפעיל את הקובץ run_cpp.sh כדי להריץ את התוכנית, התוכנית תפעל כפי שמפורט בקובץ grader.cpp, והסעיף "תיאור קובץ הבודק" מסביר את אופן פעולתו של קובץ זה.