+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! به همین دلیل دوست حیدری حال ندارد برای این سوال داستان بنویسد. یک عدد را حیدری-تپه‌ای می‌نامیم اگر ارقام آن از چپ به راست تا یک جایی کوچک نشوند (می‌توانند بزرگ شوند و یا ثابت بمانند) سپس از آن‌جا به بعد بزرگ نشوند (می‌توانند کوچک شوند و یا ثابت بمانند). برای مثال اعداد ۱۲۲۳۴۴۲۱، ۱۲، ۳۵۷، ۵۴۱ و ۱۲۳۲۱ حیدری-تپه‌ای هستند ولی اعداد ۱۲۳۲۱۳، ۱۰۱ و ۳۷۳۵ حیدری-تپه‌ای نیستند. به شما $T$ عدد داده می‌‌شود، به ازای هر عدد اگر آن عدد حیدری-تپه‌ای بود تعداد اعداد طبیعی حیدری-تپه‌ای کمتر یا مساوی آن را چاپ کنید و اگر حیدری-تپه‌ای نبود `-1` را در خروجی چاپ کنید. # ورودی در خط اول ورودی $T$ تعداد اعداد داده می‌شود. سپس در $T$ خط بعدی در هر خط یک عدد حداکثر ۷۰ رقمی به شما داده می‌شود. # خروجی در $T$ خط جواب سوال را چاپ کنید. تضمین می‌شود همیشه جواب در متغیر ۶۴-بیتی جا می‌شود. # مثال ## ورودی نمونه ۱ ``` 5 10 55 101 1000 1234321 ``` ## خروجی نمونه ۱ ``` 10 55 -1 715 94708 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> به کمک برنامه نویسی پویا جواب سوال را پیدا می‌کنیم. `dp[i][j][2]` را تعریف می‌کنیم: چند عدد $i$ رقمی داریم که رقم آخر آن‌ها برابر $j$ است. بعد سوم `dp` نشان‌دهنده آن است که آیا تا به الان کوچک شدن رقم‌های عدد ما آغاز شده است یا خیر. در راهنمایی بعدی، بروز شدن `dp` دقیق‌تر توضیح داده می‌شود. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> برای به‌روز کردن دی‌پی رقم آخر عددمان را فیکس میکنیم. حال اگر در استیتی باشیم که $i$ رقم داشته باشیم و رقم آخر عددمان $j$ تعیین شده باشد با ۲ حالت زیر روبه‌رو هستیم: **حالت اول:** کوچک شدن ارقام عددمان شروع شده است (بعد سوم دی‌پی ۱ باشد) در این صورت دی‌پی ما برابر جمع دی‌پی اعداد $i -1$ رقمی است که رقم آخرشان بزرگ‌تر یا مساوی $j$ باشد. **حالت دوم:** کوچک شدن ارقام اعدادمان شروع نشده است (بعد سوم دی‌پی ۰ باشد) در این صورت دی‌پی ما برابر جمع دی‌پی اعداد $i -1$ رقمی است که رقم آخرشان کوچک‌تر یا مساوی $j$ باشد. در زمان دادن خروجی باید حواسمان باشد تعداد اعدادی که کوچکتر از عدد داده شده هستند را چاپ کنیم! </details>

حل سؤال در بانک سؤالات