Muzip

تا حالا کاغذ نت‌های یک موسیقی را دیده‌اید؟ متون موسیقی از چپ به راست خوانده می‌شوند و می‌توان آن‌ها را دنباله‌ای از نت‌ها در نظر گرفت.

یکی از ایده‌های معروف برای کوتاه ساختن این متون، استفاده از ارجاع است. می‌دانیم یک موسیقی معمولا دارای قطعات تکراری است. پس اگر به جای نوشتن مجدد تکرارهای یک تکه، به جایی که آن تکه قبلا نوشته شده اشاره کنیم توانسته‌ایم این متن را تاحدی فشرده کنیم. مثلا در شکل بالا، قسمتی که در آن ‎$<A-B>$‎ نوشته شده، به قسمتی از نت‌ها اشاره می‌کند که شروع و پایانش با حروف ‎$A$‎ و ‎$B$‎ نشان داده شده است.

‎ نت‌های موسیقی در این مسئله با اعداد صحیح مدل شده‌اند. در عین حال، نت‌ها از چپ به راست به ترتیب با ۱، ۲ و ‎$\ldots$‎ شماره‌گذاری شده‌اند. برای ارجاع به جاهای دیگر موسیقی از همین شماره‌گذاری استفاده می‌شود. در این مسئله، قرار است یک متن موسیقی را از حالت فشرده درآورید. شکل ارجاعات در موسیقی های فشرده‌ی این مسئله، کمی تعمیم یافته‌تر از نسخه‌های واقعی آن است:

• تکه‌ای از موسیقی می‌تواند به بخشی دیگر از موسیقی ارجاع دهد که بعد از خودش است.
• یک قسمت از موسیقی می‌تواند به تکه‌ای دیگر اشاره کند، و تکه‌ی اشاره شده، خود ساخته شده یک یا چند ارجاع دیگر باشد.
• بازه‌ی مربوط به بخش اشاره دهنده می‌تواند با بخش اشاره‌شده اشتراک داشته باشد.
• ممکن است با دنبال کردن ارجاعات برای یافتن مقدار واقعی یک نت، حتی در دور هم بیفتیم و مقدار واقعی نت غیر قابل محاسبه باشد. ولی از همین اطلاعات می‌توان فهمید که مقدار آن نت با مقدار چند نت دیگر همیشه برابر است.

برنامه‌ای بنویسید که:

• موسیقی فشرده را از ورودی بخواند؛
• موسیقی را از حالت فشرده خارج کند؛
• موسیقی غیر فشرده را در خروجی چاپ کند.

• متن موسیقی فشرده شده، از چپ به راست در یک سطر آمده و از تعدادی کلمه درست شده است که با یک فاصله از هم جدا شده‌اند.‎
• به ازای هر مقدار واقعی نت، یک کلمه در ورودی نوشته شده که عدد آن نت است.‎
• به ازای هر ارجاع، ‎۵ کلمه در ورودی بصورت ‎$<a–b>$ نوشته شده است. ‎
  • کلمه های اول، سوم، و پنجم، به ترتیب کارکتر های ‎'>'‎ و '-'‎ و ‎'<'‎ هستند. کلمه دوم ‎($a$)‎، ابتدا، و کلمه چهارم ‎($b$)‎، انتهای بازه‌ای از نت‌ها است که این ارجاع به آن اشاره می کند (‎$a \leq b$‎). بدیهی است این ارجاع به تنهایی ‎$b-a+1$‎ نت را در دل خود دارد و این نکته در شماره‌گذاری نت‌های بعدی تاثیر دارد. اگر ‎$a=b$‎ بود، ممکن است ارجاع با ‎۳‎ کلمه هم در ورودی بصورت $<a>$‎ نوشته شود.
• ورودی به گونه‌ای است که هیچ ارجاعی به بیرون آهنگ ندارد. پایان ورودی با کلمه '\$'‎ مشخص می‌شود.
• طول آهنگ فشرده نشده حداکثر ‎$100000$‎ است. اعداد ورودی در محدوده‌ی اعداد صحیح علامت‌دار ‎$32$‎ بیتی هستند.‎

• در تنها سطر خروجی، مقدار واقعی نت‌های آهنگ را از چپ به راست با یک فاصله از هم بنویسید.
• برای نت‌هایی که مقدار واقع‌شان قابل محاسبه نیست، از $0?$، $1?$، $2?$‎ و ‎$\ldots$‎ استفاده کنید.‎
• برای نت‌های نامعینی که لزوما با هم برابرند از $i?$‎ های یکسان استفاده کنید. خروجی باید از نظر الفبایی کوچک‌ترین باشد.‎

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل