+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خشایار شاه -پادشاه اسپادانا- به تازگی **رشته‌ای رمزی** به طول $n$ از کشور دوست و همسایه آپادانا دریافت کرده است. ابتدا دو نوع رشته را تعریف می‌کنیم. رشته‌ای را **بلوک** می‌نامیم اگر از یکی از حروف کوچک الفبا بعلاوه یک عدد طبیعی (بدون صفر در ابتدای آن) تشکیل شده باشد. برای مثال $a123$ و $f4$ بلوک هستند ولی $1a$ و $ab1$ و $a02$ و $a12b$ و $12a$ بلوک نیستند. (دقت کنید که عدد طبیعی باید بعد از حرف بیاید) رشته‌ای را **مولد** می‌نامیم اگر از یک یا چند بلوک تشکیل شده باشد. برای مثال $a12b4d7$ رشته‌ای مولد است. **زیبایی** یک رشته مولد را تعداد ارقام آن منهای تعداد حروف آن تعریف می‌کنیم. برای مثال زیبایی رشته $a12b4d7$ برابر $1$ است و زیبایی رشته $a123b5$ برابر $2$ است. کشور آپادانا برای ارسال رشته رمزی به این شکل عمل می‌کند:‌ آن‌ها در ابتدا رشته‌ای مولد را در نظر می‌گیرند، فرض کنید این رشته از $t$ بلوک تشکیل شده باشد. رشته $res$ که در ابتدا تهی‌ست را در نظر بگیرید. آن‌ها $t$ مرحله عملیات زیر را انجام می‌دهند:‌ در مرحله $i$ ام حرف مربوط به بلوک $i$ را در نظر می‌گیرند و آن‌ حرف را به انتهای $res$ اضافه می‌کنند. سپس رشته $res$ را به اندازه عدد مربوط به بلوک $i$ام تکرار می‌کنند و رشته $res$ جدید ساخته می‌شود. در نهایت پس از انجام $t$ مرحله، رشته $res$ همان رشته رمزی‌ است. برای مثال اگر رشته مولد برابر $a1b2c4$ باشد، آنگاه پس از انجام $t=3$ مرحله: $$\phi \rightarrow a \rightarrow abab \rightarrow ababcababcababcababc$$ رشته رمزی $ababcababcababcababc$ به دست می‌آید. خشایار شاه، رشته رمزی را به کیوان -مشاور اعظم- داده است و از او می‌خواهد تا بیابد که آیا رشته‌ای مولد وجود دارد که زیبایی آن $k$ باشد و رشته رمزی را بسازد‌؟ کیوان پس از بررسی‌‌های فراوان فهمیده‌ است که طول رشته رمزی $n$ است اما تنها $m$ حرف اول این رشته به دست خشایارشاه رسیده‌است و $n - m$ حرف باقی‌مانده مشخص نیستند. اکنون کیوان که کمی گیج شده است از شما می‌خواهد که تعداد رشته‌های مولدی را بیابید که + زیبایی شان $k$ باشد. + رشته رمزی متناظر با آن‌ها طولش $n$ باشد و $m$ حرف اولش برابر با رشته‌ای باشد که به دست خشایارشاه رسیده است. از آنجایی که این عدد ممکن است بزرگ باشد، باقی مانده آن را بر $10^{9} + 7$ بیابید. # ورودی در خط اول ورودی سه عدد $n, m, k$ آماده است. سپس اگر $m > 0$ باشد رشته ای به طول $m$ آمده است که $m$ حرف اول رشته رمزی را مشخص می‌کند. $$1 \le n \le 100\ 000 $$ $$0 \le m \le n$$ $$0 \le k \le 10^{9}$$ رشته ورودی تنها از حروف کوچک الفبای انگلیسی تشکیل شده است. # خروجی در تنها خط خروجی جواب مساله را چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۳۰ | $n \le 1\ 000$| | ۲ | ۲۰ | رشته ورودی تنها از حرف $a$ تشکیل شده است. | | ۳ | ۵۰ | بدون محدودیت اضافی| # ورودی نمونه ۱ ``` 2 2 0 aa ``` # خروجی نمونه ۱ ``` 2 ``` # ورودی نمونه ۲ ``` 4 2 0 ab ``` # خروجی نمونه ۲ ``` 677 ``` # ورودی نمونه ۳ ``` 2 0 0 ``` # خروجی نمونه ۳ ``` 702 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کشور اسپادانا از $n$ شهر تشکیل شده است که $m$ جاده بین برخی از این شهرها وجود دارد. بنابراین این کشور را می‌توانیم به گرافی $n$ راسی با $m$ یال مدل کنیم. راس‌های گراف را از $1$ تا $n$ شماره‌گذاری می‌کنیم. خشایارشاه خیلی از گراف کشور اسپادانا راضی نیست. او که در جوانی به نظریه‌گراف علاقه‌مند بوده است، درختی $n$ راسی را زیر نظر گرفته و آن درخت را **ایده‌آل** می‌نامد. خشایار شاه در مورد درخت ایده‌آل، به کیوان گفته است که قطر این درخت حداکثر $4$ است. در راستای سیاست‌های ایده‌آل‌سازی خشایار شاه، او در گام اول تصمیم گرفته است که نقشه کشورش ایده‌آل شود. بنابراین او به کیوان دستور داده است که نقشه اسپادانا را به شکل درخت ایده‌آل در بیاورد. کیوان تنها می‌تواند بعضی از جاده‌های کشور - معادل یال‌های گراف - را نابود کند. به بیان دقیق‌تر کیوان باید تعدادی از یال‌های گراف اسپادانا را حذف کند به طوری که گراف باقی مانده، درختی یک‌ریخت با درخت ایده‌آل باشد. کیوان که طبیعتا نمی‌تواند این مساله را حل کند... به همین منظور او از شما می‌خواهد که مشخص کنید آیا می‌توان گراف کشور را به درخت ایده‌آل تبدیل کردیا نه‌، سپس اگر می‌توان گراف کشور را به درخت ایده‌آل تبدیل کرد، جایگشتی در خروجی مانند $p_1, p_1, ..., p_{n}$ چاپ کنید که مشخص کند راس $i$ام در گراف اسپادانا به راس $p_i$ در درخت ایده‌آل متناظر شده است. # ورودی در خط اول ورودی دو عدد $n, m$ آمده است که $n$ تعداد شهرهای اسپادانا را معلوم می‌کند و $m$ تعداد جاده‌های میان شهرها را مشخص می‌کند. سپس $n-1$ خط دیگر می‌آید که هر خط شامل دو عدد $c_i, d_i$ است که یال‌های درخت ایده‌آل را مشخص می‌کند. سپس $m$ خط می‌آید که خط $1 \le i \le m$ شامل دو عدد $a_i, b_i$ است که یعنی جاده‌ شماره $i$، دو شهر $a_i$ و $b_i$ را به هم متصل می‌کند. $$1 \le n \le 20$$ $$0 \le m \le {n \choose 2}$$ $$1 \le a_i, b_i, c_i, d_i \le n$$ + گراف اسپادانا یال چندگانه و طوقه ندارد. + قطر درخت ایده‌آل حداکثر ۴ است. # خروجی در خروجی چنان‌چه نمی‌توان گراف اسپادانا را به درخت ایده آل تبدیل کرد فقط $-1$ چاپ کنید. در غیر این‌صورت جایگشتی به طول $n$ چاپ کنید که مشخص کند هر راس گراف کشور اسپادانا به کدام راس درخت متناظر می‌شود.‌(اگر چندین جواب وجود دارد یکی را به دلخواه چاپ کنید.) # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۰ | $n \le 10$| | ۲ | ۳۰ | $n \le 17$| | ۳ | ۵۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ``` 5 6 1 5 4 2 2 1 5 3 1 5 4 1 1 3 3 5 2 1 3 4 ``` ## خروجی نمونه ``` 2 4 5 3 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در اواسط حکومت خشایار شاه بر اسپادانا، یکی از قبایل همسایه- که از بردن نامش چشم‌پوشی می‌کنیم- تصمیم به حمله به اسپادانا گرفت. اما از آن‌جایی که خشایارشاه پادشاهی با کفایت بود، با کمک کیوان خیلی سریع اقدام به تشکیل سپاهی پر قدرت کرد. در اسپادانا، $n$ سرباز با شماره‌های $1$ تا $n$ به ترتیب در یک صف قرار دارند که هوشمندی سرباز $1 \le i \le n$ برابر $a_i$ است. **هوشمندی** یک گروه از سربازها نیز برابر **میانگین هوشمندی** سربازهای آن گروه است. برای مثال هوشمندی یک گروه $3$ نفره از سرباز‌ها با هوشمندی ${1, 3, 4}$ برابر $\frac{8}{3}$ است. از آنجایی که قبیله همسایه در $k$ گروه به اسپادانا حمله می‌کرد، خشایارشاه به کیوان دستور داده بود که سربازها را به حداقل $k$ گروه **افراز** کند. همچنین خشایارشاه دستور داده بود هر گروه از سربازها یک **زیردنباله متوالی** از سربازهای درون صف باشد. به بیان دقیق‌تر کیوان باید سربازها را به حداقل $k$ زیردنباله متوالی افراز کند. **اعتبار** یک گروه بندی توسط کیوان را *مینیمم هوشمندی* بین گروه‌ها تعریف می‌کنیم. برای مثال فرض کنید دنباله $a = <1, 2, 3, 5>$ باشد، و کیوان دنباله را به $2$ زیردنباله متوالی مثل ${1, 2}$ و ${3, 5}$ افراز کند در این‌صورت هوشمندی گروه‌ها برابر $\frac{3}{2}$ و $4$ می‌شود. درنتیجه اعتبار این گروه‌بندی $\frac{3}{2}$ است. از آنجایی که اسپادانا در آن زمان بسیار مقتدر بود، خشایارشاه به کیوان دستور داده بود که اعتبار گروه‌بندی‌اش در بین تمام گروه‌بندی‌های ممکن بیشینه باشد. شما می‌دانید که در آن زمان کیوان حال و روز درست و حسابی نداشته است، به او کمک کنید و بیشینه اعتبار ممکن در بین همه گروه‌بندی‌ها را بیابید. # ورودی در خط اول ورودی دو عدد $n, k$ آماده است. سپس $n$ عدد $a_1, a_2, ..., a_{n}$ آمده است که میزان هوشمندی سرباز‌ها را معین می‌کند. $$1 \le k \le n \le 100\ 000$$ $$0 \le a_i \le 10^{9}$$ # خروجی در تنها خط خروجی, جواب مساله را چاپ کنید. با توجه به اینکه جواب ممکن است اعشاری باشد، جواب شما در صورتی پذیرفته می‌شود که اختلاف آن با جواب بهینه کمتر از $10^{-6}$باشد. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۰ | $k \le 2$| | ۱ | ۲۰ | $n \le 1\ 000$| | ۲ | ۳۰ | $k \le 10$| | ۳ | ۴۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 4 2 2 1 4 3 ``` ## خروجی نمونه ۱ ``` 2.33333333333 ``` ## ورودی نمونه ۲ ``` 4 3 2 1 4 3 ``` ## خروجی نمونه ۲ ``` 2.0000000000 ``` ## ورودی نمونه ۳ ``` 10 4 13 4 7 3 1 17 5 8 7 6 ``` ## خروجی نمونه ۳ ``` 6.499999999 ```