אליס טיפסה בסולם התאגידי במשך שנים רבות ולבסוף הגיעה לפסגה. היא מונתה זה עתה למנכ"לית (CEO) של חברה ציבורית גדולה. המנכ"ל הקודם פוטר עקב תוצאות כספיות גרועות, אך אליס יודעת היטב כיצד להזניק את הרווחים. הגיע הזמן לבחור שם חדש לחברה!
משקיעים אוהבים כל אזכור של בינה מלאכותית, במיוחד בשם החברה. הערך הבסיסי של החברה שווה לאורך שמה, וכל מופע של תת-המחרוזת "AI" מכפיל את ערך החברה ב-5. לדוגמה, לשם "AAICPCAIIA" יש אורך 10 ושני מופעים (מסומנים בקו תחתון) של "AI":
- $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$
דוגמאות נוספות:
- $\operatorname{value}(\texttt{AXI}) = 3$ (אפס מופעים של "
AI") - $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (ארבעה מופעים של "
AI") - $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (מופע אחד של "
AI")
החוזה של אליס מבטיח לה בונוס נדיב במיוחד אם ערך החברה יהיה בדיוק $n$. היא גם רוצה שהשם יהיה קצר ככל האפשר.
אליס כבר עסוקה במשימה הבאה שלה – עיצוב הלוגו המחודש. האם תוכלו להציע שם חדש לחברה בינתיים? מצאו את המילה הקצרה ביותר האפשרית שערכה $n$, המורכבת מאותיות אנגליות גדולות A-Z.
קלט
השורה היחידה מכילה מספר שלם $n$ ($1 \le n \le 100\,000$) – ערך החברה הרצוי.
פלט
הדפיסו מילה המורכבת מהאותיות A-Z – שם בעל ערך $n$ והאורך הקטן ביותר האפשרי. אם קיימים פתרונות רבים, הדפיסו אחד מהם.
דוגמאות
קלט 1
30
פלט 1
AIMPPZ
קלט 2
250
פלט 2
AAICPCAIIA
הערה
במבחן הראשון, אנו מחפשים את השם הקצר ביותר האפשרי שערכו 30. למילים אופטימליות יש אורך 6 ומופע אחד של "AI", לדוגמה "AIMPPZ", "HUAWAI", "BRAINS" ו-"AAAIII". לאף מילה קצרה יותר אין ערך 30.
במבחן השני, לא ניתן להשיג ערך 250 עם שם הקצר מ-10 תווים.