Alice ไต่เต้าในสายอาชีพมาหลายปีและในที่สุดก็มาถึงจุดสูงสุด เธอเพิ่งก้าวขึ้นเป็นประธานเจ้าหน้าที่บริหาร (CEO) ของบริษัทมหาชนขนาดใหญ่แห่งหนึ่ง CEO คนก่อนถูกไล่ออกเนื่องจากผลประกอบการทางการเงินที่ย่ำแย่ แต่ Alice รู้ดีว่าจะเพิ่มผลกำไรได้อย่างไร ได้เวลาเลือกชื่อบริษัทใหม่แล้ว!
นักลงทุนชื่นชอบการกล่าวถึงปัญญาประดิษฐ์เป็นอย่างมาก โดยเฉพาะในชื่อบริษัท มูลค่าพื้นฐานของบริษัทจะเท่ากับความยาวของชื่อบริษัท และทุกครั้งที่ปรากฏสตริงย่อย "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" หนึ่งครั้ง)
สัญญาของ Alice รับประกันว่าเธอจะได้รับโบนัสก้อนโตเป็นพิเศษหากมูลค่าของบริษัทเท่ากับ $n$ พอดี นอกจากนี้เธอยังต้องการให้ชื่อบริษัทสั้นที่สุดเท่าที่จะเป็นไปได้
ตอนนี้ Alice กำลังยุ่งอยู่กับงานถัดไปของเธอ นั่นคือการออกแบบโลโก้โฉมใหม่ คุณช่วยเสนอชื่อบริษัทใหม่ในระหว่างนี้ได้ไหม? จงหาคำที่สั้นที่สุดเท่าที่เป็นไปได้ที่มีมูลค่า $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 ตัวอักษร