Infinite Compression Plan Consortium ‏(ICPC) פיתח שיטה חדשה ומצוינת לדחיסת נתונים בשם ״Don’t Repeat Yourself״ (DRY). השיטה פועלת על מחרוזת תווים, ואם יש במחרוזת שני מופעים רצופים של אותה תת־מחרוזת, היא פשוט מוחקת אחד מהם. למשל, במחרוזת ״alfalfa seeds״ אפשר למחוק אחד משני מופעי ״e״ ב־״seeds״ ואחד משני מופעי ״lfa״ ב־״alfalfa״, ולקבל ״alfa seds״. DRY יכולה גם לנצל מחיקות קודמות: למשל, ב־״seventeenth baggage״ היא תמחק תחילה את ״e״ החוזרת ב־״seventeenth״ ואת ״g״ החוזרת ב־״baggage״, ותקבל ״sevententh bagage״, ואז את ״ent״ החוזרת ב־״sevententh״ ואת ״ag״ החוזרת ב־״bagage״, ותקבל ״seventh bage״.

התמונה עובדה מתוך Wikimedia Commons, נחלת הכלל

אם יש כמה אפשרויות לתת־מחרוזות החוזרות ברצף שאפשר למחוק, על DRY לבחור כך שהמחרוזת הסופית תהיה קצרה ככל האפשר. למשל, במחרוזת ״ABBCDCABCDCD״ יש שתי אפשרויות: למחוק את ״B״ החוזרת סמוך להתחלה, או את ״CD״ החוזרת בסוף. אם מוחקים את ״B״, אפשר לאחר מכן למחוק את ״ABCDC״ החוזרת, לקבל ״ABCDCD״, ולבסוף למחוק את ״CD״ שבסוף ולקבל ״ABCD״. אבל אם מוחקים תחילה את ״CD״ שבסוף, נשארת ״ABBCDCABCD״, וממנה אפשר למחוק רק את ״B״ החוזרת כדי לקבל ״ABCDCABCD״ — וממחרוזת זו אי אפשר למחוק עוד דבר. לכן הבחירה הנכונה היא להתחיל בדחיסת ״B״ הכפולה, ולסיים ב־״ABCD״.

ICPC הבחין ש־DRY משיגה את התוצאות הטובות ביותר במחרוזות בינאריות, כלומר מחרוזות המורכבות רק מאפסים ואחדים. לכן הוטל עליכם לממש את אלגוריתם DRY הטוב ביותר האפשרי עבור מחרוזות בינאריות. לכל מחרוזת בינארית, עליכם להדפיס מחרוזת קצרה ביותר שאפשר לקבל על ידי הפעלה חוזרת של DRY עליה.

קלט

הקלט מורכב משורה אחת המכילה מחרוזת שאינה ריקה באורך לכל היותר $10^5$, המורכבת רק מאפסים ואחדים.

פלט

הדפיסו שורה אחת המכילה תוצאה קצרה ביותר של הפעלת DRY על מחרוזת הקלט. אם יש כמה תוצאות קצרות ביותר, כל אחת מהן תתקבל.

דוגמאות

קלט 1

1111

פלט 1

1

קלט 2

101

פלט 2

101

קלט 3

10110

פלט 3

10