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