狂野飙车 הוא המשחק האהוב ביותר על 小 L. בניגוד לשחקנים חובבים אחרים, מלבד המשחק עצמו הוא מצטיין גם בחקר עיצוב המשחק, ולכן יש לו אסטרטגיה יוצאת דופן.
תיאור הבעיה
小 L מתכנן לשחק $n$ משחקים. בכל משחק משתמשים במפה אחת, והוא יבחר מכונית שבה ישלים את המשחק באותה מפה.
ל־小 L יש שלוש מכוניות מרוץ, המסומנות באותיות הגדולות A, B, C. יש ארבעה סוגי מפות, המסומנים באותיות הקטנות x, a, b, c. מכונית A אינה מתאימה למפה a, מכונית B אינה מתאימה למפה b, ומכונית C אינה מתאימה למפה c. מפה x מתאימה לכל המכוניות. מפות המתאימות לכל המכוניות אינן נפוצות, ויהיו לכל היותר $d$ מפות כאלה.
אפשר לתאר את המפות של $n$ המשחקים במחרוזת של אותיות קטנות. לדוגמה, S=xaabxcbc מתארת שמונה משחקים: המפות במשחקים הראשון והחמישי הן מסוג x ומתאימות לכל המכוניות; המפות במשחקים השני והשלישי הן מסוג a ואינן מתאימות למכונית A; המפות במשחקים הרביעי והשביעי הן מסוג b ואינן מתאימות למכונית B; והמפות במשחקים השישי והשמיני הן מסוג c ואינן מתאימות למכונית C.
ל־小 L יש כמה דרישות מיוחדות למשחקים. כל דרישה ניתנת לתיאור כרביעייה $(i,h_i,j,h_j)$: אם במשחק ה־$i$ משתמשים במכונית מסוג $h_i$, במשחק ה־$j$ יש להשתמש במכונית מסוג $h_j$.
האם תוכלו לעזור לו לבחור מכונית לכל משחק? אם יש כמה אפשרויות, הדפיסו אחת כלשהי. אם אין פתרון, הדפיסו -1 ללא מירכאות.
קלט
יש לקרוא את הנתונים מהקובץ game.in.
השורה הראשונה מכילה שני מספרים שלמים אי־שליליים $n,d$.
השורה השנייה מכילה מחרוזת $S$.
משמעותם של $n,d,S$ מוסברת בתיאור הבעיה. המחרוזת $S$ מכילה $n$ תווים, ובדיוק $d$ מהם הם האות הקטנה x.
השורה השלישית מכילה מספר שלם חיובי $m$, המציין את מספר כללי השימוש במכוניות. כל אחת מ־$m$ השורות הבאות מכילה רביעייה $i,h_i,j,h_j$, כאשר $i,j$ הם מספרים שלמים ו־$h_i,h_j$ הם התווים a, b או c, במשמעות המתוארת בבעיה.
פלט
יש לכתוב את הפלט לקובץ game.out.
יש להדפיס שורה אחת.
אם אין פתרון, הדפיסו -1 ללא מירכאות.
אם יש פתרון, השורה תכיל מחרוזת באורך $n$ המורכבת רק מהאותיות הגדולות A, B, C, ומתארת באיזו מכונית ישתמש 小 L בכל אחד מ־$n$ המשחקים. אם יש כמה פתרונות, אפשר להדפיס כל אחד מהם.
דוגמאות
קלט 1
3 1 xcc 1 1 A 2 B
פלט 1
ABA
דוגמה 2
ראו את הקבצים game/game2.in ו־game/game2.ans בתיקיית המתחרה.
הערה לדוגמה 1
小 L מתכנן שלושה משחקים. מפת המשחק הראשון היא מסוג x ומתאימה לכל המכוניות; המפות של המשחקים השני והשלישי הן מסוג c ואינן מתאימות למכונית C.
הוא דורש שאם במשחק הראשון משתמשים במכונית A, במשחק השני יש להשתמש במכונית B.
לכן בחירת המכוניות A, B, A לשלושת המשחקים, בהתאמה, מקיימת את כל התנאים.
גם הבחירות BBB ו־BAA לשלושת המשחקים מקיימות את כל התנאים ונחשבות תשובות נכונות. לעומתן, AAB ו־ABC אינן מקיימות את כל התנאים ולכן אינן נחשבות תשובות נכונות.
תתי־משימות
| מספר מקרה הבדיקה | $n$ | $d$ | $m$ | תכונות נוספות |
|---|---|---|---|---|
| $1$ | $\leq 2$ | $0$ | $\leq 4$ | אין |
| $2$ | $\leq 2$ | $\leq n$ | $\leq 4$ | אין |
| $3$ | $\leq 5$ | $0$ | $\leq 10$ | אין |
| $4$ | $\leq 5$ | $\leq n$ | $\leq 10$ | אין |
| $5$ | $\leq 10$ | $0$ | $\leq 20$ | אין |
| $6$ | $\leq 10$ | $\leq8$ | $\leq 20$ | אין |
| $7$ | $\leq 20$ | $0$ | $\leq 40$ | $S$ מכילה רק c |
| $8$ | $\leq 20$ | $0$ | $\leq 40$ | אין |
| $9$ | $\leq 20$ | $\leq8$ | $\leq 40$ | $S$ מכילה רק x או c |
| $10$ | $\leq 20$ | $\leq8$ | $\leq 40$ | אין |
| $11$ | $\leq 100$ | $0$ | $\leq 200$ | $S$ מכילה רק c |
| $12$ | $\leq 100$ | $0$ | $\leq 200$ | אין |
| $13$ | $\leq 100$ | $\leq8$ | $\leq 200$ | $S$ מכילה רק x או c |
| $14$ | $\leq 100$ | $\leq8$ | $\leq 200$ | אין |
| $15$ | $\leq 5000$ | $0$ | $\leq 10000$ | אין |
| $16$ | $\leq 5000$ | $\leq8$ | $\leq 10000$ | $S$ מכילה רק x או c |
| $17$ | $\leq 5000$ | $\leq8$ | $\leq 10000$ | אין |
| $18$ | $\leq 50000$ | $0$ | $\leq 100000$ | אין |
| $19$ | $\leq 50000$ | $\leq8$ | $\leq 100000$ | $S$ מכילה רק x או c |
| $20$ | $\leq 50000$ | $\leq8$ | $\leq 100000$ | אין |