הפרות, שלא היו מרוצות מהנהגת Farmer John, פרשו מהחווה והקימו את Continental Cowngress הראשון. לפי העיקרון ״כל פרה מקבלת משהו שהיא רוצה״, בחרו שיטת הצבעה זו:
$M$ הפרות הנוכחות ($1 \leq M \leq 4{,}000$) מצביעות על $N$ הצעות חוק ($1 \leq N \leq 1{,}000$). כל פרה מצביעה כן או לא (בקלט '$Y$' או '$N$') על בדיוק שתי הצעות שונות $B_i$, $C_i$ ($1 \leq B_i, C_i \leq N$). הקולות הם $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$), $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
ההחלטות חייבות להתאים לפחות לקול אחד של כל פרה. אם Bessie אומרת כן להצעה 1 ולא להצעה 2, בכל פתרון חוקי 1 מתקבלת או 2 נדחית (או שתיהן).
בהינתן הקולות, קבעו את התוצאות לפי הכללים. אם אין פתרון, הדפיסו "IMPOSSIBLE". אם יש לפחות אחד, הציגו לכל הצעה:
- $Y$ אם היא מתקבלת בכל פתרון.
- $N$ אם היא נדחית בכל פתרון.
?אם יש פתרונות שבהם היא מתקבלת וגם פתרונות שבהם אינה מתקבלת.
התבוננו בקולות הבאים (שניים לכל פרה):
הצעות חוק
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| פרה $1$ | כן | לא | |
| פרה $2$ | לא | לא | |
| פרה $3$ | כן | כן | |
| פרה $4$ | כן | כן |
שני פתרונות מרצים את כל הפרות:
- הצעה 1 מתקבלת (מרצה את פרות 1, 3 ו־4).
- הצעה 2 נדחית (מרצה את פרה 2).
- הצעה 3 יכולה להתקבל או להידחות (לכן יש שני פתרונות).
אלה אכן שני הפתרונות היחידים, ולכן התשובה היא המחרוזת הבאה בת שלושה תווים:
YN?
קלט
קראו מהקלט התקני.
- שורה $1$: שני שלמים $N$, $M$, מופרדים ברווחים.
- שורות $2 \ldots M+1$: השורה $i+1$ מתארת את קולות פרה $i$ בארבעה שדות מופרדים ברווחים: שלם, קול, שלם נוסף, קול נוסף, $B_i$, $VB_i$, $C_i$, $VC_i$.
פלט
כתבו לפלט התקני.
- שורה $1$: מחרוזת בת $N$ תווים; התו $i$ הוא "$Y$" אם הצעה $i$ חייבת להתקבל, "$N$" אם חייבת להידחות, או "?" אם הקולות אינם קובעים את תוצאתה.
אם אין פתרון שמרצה כל פרה, הדפיסו שורה יחידה "IMPOSSIBLE".
דוגמאות
קלט 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
פלט 1
YN?
מחבר הבעיה: Louis Wasserman, 2010