Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

נתון לכם מערך של $n$ מספרים שלמים מ-$1$ עד $n+1$. ייתכן שחלק מהמספרים השלמים מופיעים מספר פעמים במערך. עם זאת, ברור שלפחות אחד מהמספרים השלמים מ-$1$ עד $n+1$ חסר במערך. משימתכם היא למצוא מספר שלם כלשהו כזה. בדרך כלל זה היה קל, אך ישנה בעיה מצערת: אין מספיק זיכרון במחשב שלכם כדי לייצג את המערך כולו.

לכן, אתם מתבקשים ליצור במקום זאת אלגוריתם זרימה (streaming algorithm). באופן לא פורמלי, איברי המערך ניתנים לכם אחד-אחד ללא שום דרך לגשת אליהם בגישה אקראית. עם זאת, ישנה נחמה אחת: לאחר קבלת האיבר האחרון של המערך, תוכלו להתחיל לקרוא אותו מחדש מההתחלה. באופן אידיאלי, הייתם רוצים להימנע ממצב כזה ולפתור את הבעיה כולה במעבר אחד (one pass). אולם, לעיתים (כולל בבעיה זו ממש) מספר מעברים על הקלט עשויים להיות הכרחיים כדי להימנע משימוש בזיכרון רב מדי. עליכם לאזן בין שני השיקולים ובמקביל לא להשתמש ביותר מדי זיכרון ולא לבצע יותר מדי מעברים על המערך (הבעיה טריוויאלית אם מותר לכם לשמור $n$ ביטים של זיכרון או להשתמש ב-$n$ מעברים).

עם זאת, ישנו עדיין מלכוד אחד. מסיבות טכניות, עליכם לייצר אוטומט סופי דטרמיניסטי (DFA) מעל האלף-בית $\{0, 1, \dots, n + 1\}$ המממש את הלוגיקה של האלגוריתם שלכם. תווי האלף-בית מתאימים למידע שאתם מקבלים בעת קריאת הזרם: מספרים מ-$1$ עד $n+1$ מייצגים קריאה של המספר השלם המתאים מהמערך, בעוד שהמספר $0$ מייצג את העובדה שהגעתם לסוף המערך. לאחר 7 הפעמים הראשונות שבהן הגעתם לסוף המערך, המערך יינתן לכם שוב באותו סדר כמו קודם, ותמיד יסתיים בתו $0$ המייצג את סוף המערך. לפיכך, ה-DFA שלכם יוזן במחרוזת $a_1, a_2, \dots, a_n, 0$ בסך הכל 8 פעמים (כאן, $a_1, a_2, \dots, a_n$ הוא המערך הנסתר). לבסוף, בכל רגע במהלך הריצה, האוטומט שלכם יכול "לומר" שהוא כבר יודע תשובה נכונה כלשהי לבעיה; במקרה זה, הריצה נעצרת. אם ה-DFA שלכם לא עשה זאת עד לרגע שבו הוא קרא את הזרם כולו (כולל התו $0$ בסוף) 8 פעמים, הוא אינו מתקבל כפתרון. באופן דומה, אם הוא עוצר, אך עם תשובה שגויה, הוא אינו מתקבל כפתרון גם כן.

ננסח את הבעיה באופן פורמלי. ישנו מערך נסתר $a_1, a_2, \dots, a_n$ של $n$ מספרים שלמים מ-$1$ עד $n+1$. בדוגמה, $n = 4$, ובכל שאר הטסטים $n = 250$. עליכם להגדיר מכונת מצבים סופית עם לכל היותר 4000 מצבים, הממוספרים מ-$0$ עד $q - 1$, כאשר $q \le 4000$ הוא מספר המצבים. עבור המצב $i$ ($0 \le i \le q - 1$), עליכם לציין $n + 2$ מספרים $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. המספר $\delta(i, j)$ מייצג את ההתנהגות של ה-DFA שלכם כאשר הוא נמצא במצב $i$ וקורא את המספר $j$ מהקלט. עליו להיות מספר שלם מ-$-(n + 1)$ עד $q - 1$ כולל. מספרים שלמים שליליים מתאימים לעובדה שהריצה נעצרת וניתנת תשובה;ליתר דיוק, $-s$ מתאים לכך שה-DFA שלכם טוען ש-$+s$ הוא תשובה נכונה לבעיה. מספרים שלמים אי-שליליים מתאימים לעובדה שהריצה נמשכת ומצב האוטומט משתנה מ-$i$ ל-$\delta(i, j)$. ריצת האוטומט מתחילה במצב $0$.

ה-DFA שלכם נחשב כפועל נכון על המערך $a_1, a_2, \dots, a_n$ אם הוא עוצר עם תשובה נכונה בנקודה כלשהי במהלך קריאת המחרוזת $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$, שבה המערך חוזר 8 פעמים. ה-DFA שלכם נחשב כפועל נכון באופן כללי אם הוא פועל נכון על כל המערכים האפשריים $a_1, a_2, \dots, a_n$ של מספרים שלמים מ-$1$ עד $n+1$ (לכן, פתרונות הסתברותיים אינם מומלצים).

עבור $n = 4$, נבדוק את ה-DFA שלכם על כל המערכים האפשריים. עבור $n = 250$, אין לנו אמצעים לבדוק אותו על כל המערכים, ולכן נבדוק אותו על פחות מ-5000 מערכים שנבחרו במיוחד. ישנם שני טסטים בבעיה; שני הטסטים בודקים למעשה שהגישה שלכם פועלת נכון על מערכים רבים בו-זמנית.

קלט

מספר שלם אחד $n$, השווה ל-$4$ או ל-$250$.

פלט

בשורה הראשונה, הדפיסו מספר שלם יחיד $q$ ($1 \le q \le 4000$) המציין את מספר המצבים ב-DFA שלכם.

בשורה ה-$i$ מתוך $q$ השורות הבאות, הדפיסו $n + 2$ מספרים שלמים $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. כולם צריכים להיות בטווח מ-$-(n + 1)$ עד $q - 1$ כולל ולהתאים למעברים של האוטומט. שימו לב שכל המספרים חייבים להיות בטווח זה: גם אם שילוב כלשהו של המצב $i$ ומספר הקלט $j$ לעולם אינו יכול להיות מושג באף קלט חוקי, הערך של $\delta(i, j)$ שאתם מציינים עדיין חייב להיות בטווח $[-(n + 1), q - 1]$.

דוגמה

קלט 1

4

פלט 1

8
-3 0 0 1 0 0
2 1 1 1 1 1
-1 3 2 2 2 2
4 3 3 3 3 3
-5 4 4 4 4 5
6 5 5 5 5 5
-2 6 7 6 6 6
-4 7 7 7 7 7

הערה

התשובה עבור הדוגמה היא אוטומט משעמם מאוד שמשתמש בארבעה מעברים כדי לבדוק האם המערך כולל את המספרים 3, 1, 5 ו-2 (בסדר זה). כל אחד מהמעברים משתמש למעשה רק בשני מצבים המתאימים לשאלה האם הוא כבר מצא את המספר שהוא מחפש במעבר הנוכחי. אם הוא מגיע לסוף המערך (התו 0) מבלי למצוא את המספר הדרוש, הוא עוצר מיד ואומר שהמספר הדרוש אכן חסר. אחרת, הוא ממשיך למעבר הבא כדי לחפש את המספר הבא. לבסוף, אם הוא מצא את כל ארבעת המספרים השלמים הדרושים, אזי המספר 4 חייב להיות חסר. לכן, הוא אינו מבצע מעבר חמישי בחיפוש אחר המספר 4 (אך הוא יכול היה לעשות זאת מבלי להפר את המגבלות על מספר מצבי האוטומט ומספר המעברים).

כמובן, לגישה נאיבית זו אין שום סיכוי לעבוד עבור $n = 250$, ונדרש משהו טוב בהרבה. הסיבה העיקרית לקיומה של הדוגמה היא להמחיש את פורמט הפלט.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.