سجاد در یک مسابقه‌ شرکت کرده است. مسابقه به این صورت است که هر کس یک رقم (از ۰ تا ۹) انتخاب می‌کند و بایستی بگوید رقمی که انتخاب کرده در فاکتوریل روز تولدش چند بار تکرار شده است. مثلا سجاد رقم ۶ را انتخاب می‌کند و اگر روز تولدش ۵ مرداد باشد (که برابر با ۱۲۹ امین روز سال است) بایستی بگوید رقم ۶ چند بار در $129!$ تکرار شده است. برای این کار به سجاد کمک کنید.

محدودیت‌ها🔗

• زبان C و C++
  • محدودیت زمان: ۵۰۰ میلی‌ثانیه
  • محدودیت حافظه: ۱۵۰ مگابایت
• زبان پایتون و جاوا
  • محدودیت زمان: ۱۲۵۰ میلی‌ثانیه
  • محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

در سطر اول دو عدد می‌آید. عدد اول، روزی از سال است که سجاد به دنیا آمده است و عدد دوم رقم انتخابی اوست.

خروجی🔗

تعداد تکرار رقم انتخابی سجاد در فاکتوریل روزی از سال که به دنیا آمده است را در یک خط چاپ کنید.

مثال🔗

نمونه ورودی ۱🔗

5 2

نمونه خروجی ۱🔗

1

توضیح نمونه ۱: مقدار $5!$ برابر ۱۲۰ است که رقم ۲ در آن تنها ۱ بار تکرار شده است.

نمونه ورودی ۲🔗

7 0

نمونه خروجی ۲🔗

2

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

کیانوش متقاضی عضویت در سازمان OC است. در روز دوم مصاحبه، سازمان خلاقیت او را مورد بررسی قرار داده است.

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

کیانوش تصمیم گرفت که طوری بسته‌ها را جابجا کند که آن‌ها به شکل زیرمستطیلی با ابعاد دلخواه از جدول قرار بگیرند. روی هر خانه‌ی آن زیرمستطیل باید دقیقاً یک بسته کاه قرارگیرد و همچنین روی خانه‌‌های خارج از این مستطیل باید بسته‌ی کاهی نباشد. کیانوش میتواند در یک حرکت یک بسته‌ی کاه را از روی یک خانه‌ی جدول برداشته و روی خانه‌ی دیگری از آن بگذارد. او قصد دارد از این مستطیل بعنوان پس‌زمینه استفاده کند و با چوب و سنگ‌هایی که پیدا میکند علامت حق تکثیر (یا copyright) را روی آن حک کند.

حال با ورودی گرفتن $n$ و موقعیت بسته‌های کاه، بگویید کیانوش حداقل چند حرکت لازم دارد تا به شکل دلخواهش برسد. تضمین میشود که در ورودی داده شده، کیانوش میتواند شکل دلخواهش را طراحی کند.

ورودی🔗

سطر اول ورودی شامل دو عدد $n$ و $m$ است که نمایانگر طول مزرعه و تعداد بسته‌های کاه است.

سپس در هریک از $m$ سطر بعدی دو عدد آمده است که به ترتیب بیانگر شماره سطر و ستون یک بسته‌ی کاه است. سطر‌های جدول را از بالا به پایین و ستون‌‌های آن را از چپ به راست با اعداد ۱ تا $n$ شماره گذاری میکنیم.

توجه داشته باشید که ممکن است دو بسته‌ی کاه در یک خانه از جدول باشند.

$1 \le n \le 100$ $1 \le m \le n^2$

خروجی🔗

در تنها سطر خروجی یک عدد چاپ کنید که برابر حداقل تعداد جابجایی‌های لازم در شکل داده‌شده است.

ورودی نمونه ۱🔗

3 2
2 2
2 2

خروجی نمونه ۱🔗

1

ورودی نمونه ۲🔗

4 6
1 1
1 2
1 3
2 1
4 3
4 4

خروجی نمونه ۲🔗

2

در این مثال کافیست دو بسته‌ی کاه انتهایی را به ستون‌های دوم و سوم از سطر دوم انتقال دهیم بطوری که بسته‌های کاه مستطیلی با ۲ سطر و ۳ ستون در جدول تشکیل دهند.

سامانه Quera دارای $n$ صفحه است و آدرس (URL) هرکدام از این صفحات، از الگوی مشخصی پیروی می‌کند. به عنوان مثال آدرس صفحه معرفی یک شرکت (در بخش شرکت‌ها و فرصت‌های شغلی)، الگوی زیر را دارد:

https://quera.ir/careers/company/<company_name>

که به جای <company_name> نام شرکت قرار می‌گیرد. مثلاً آدرس صفحه معرفی تیم هدهد در Quera به این صورت است:

https://quera.ir/careers/company/hodhod

الگوی آدرس یک سؤال در بانک سؤالات دارای بیش از یک پارامتر است:

https://quera.ir/problemset/<category>/<problem_id>

بنابراین آدرس سؤالی با شناسه ۷۲۵ در دسته سؤالات المپیاد برابر این مقدار است:

https://quera.ir/problemset/olympiad/725

ممکن است در الگوی آدرس یک صفحه، هیچ پارامتری وجود نداشته باشد. مانند صفحه کلاس‌ها (شامل لیست کلاس‌هایی که کاربر در آن‌ها عضو است) که الگوی زیر را دارد:

https://quera.ir/overview

روشن است که با هر پارامتری، آدرس تولیدشده از این الگو برابر با https://quera.ir/overview است.

می‌خواهیم با داشتن نام صفحات و مقادیر پارامترهای موجود در الگوی آدرس صفحات، آدرس دقیق صفحات را به دست آوریم.

ورودی🔗

در خط اول ورودی، عدد $n$ می‌آید ($1 \leq n \leq 20$). در $n$ خط بعد، در هر خط نام یک صفحه (با طول حداکثر ۱۰) و الگوی آدرس آن صفحه (با طول حداکثر ۱۰۰) با یک فاصله می‌آیند. نام صفحات از حروف کوچک انگلیسی تشکیل شده‌اند.

سپس در خط بعدی عدد $t$ می‌آید ($1 \leq t \leq 50$). در $t$ خط بعدی، در هر خط نام یک صفحه و مقادیر پارامترها به شکل parameter=value می‌آیند. توجه کنید که ممکن است یک یا چند تا از پارامترهای موردنیاز برای ساختن آدرس دقیق، داده نشده باشد. همچنین ممکن است یک یا چند پارامتر اضافی (که موردنیاز نیست) داده شده باشد.

نام پارامترها، از حروف کوچک و بزرگ انگلیسی و _ (underline) تشکیل شده است. نام و مقادیر پارامترها حداکثر ۱۰۰ حرف هستند.

خروجی🔗

در $t$ خط، مقادیر دقیق آدرس‌های خواسته‌شده را بنویسید.

در هر مورد، اگر نام صفحه خواسته‌شده در لیست صفحات وجود ندارد، خطای زیر را بنویسید:

[Error] url not found

همچنین اگر مقدار یک یا چند پارامتر موردنیاز داده نشده است، خطای زیر را بنویسید:

[Error] missing parameter(s)

و اگر پارامتری اضافه داده شده (جزء پارامترهای مورد نیاز نیست)، آن را نادیده بگیرید.

مثال ورودی🔗

4
company https://quera.ir/careers/company/<company_name>
problemset_problem https://quera.ir/problemset/<category>/<problem_id>
overview https://quera.ir/overview
test a/<b>/c
9
company company_name=torob
company company_name=!@#
problemset_problem category=olympiad problem_id=725
problemset_problem category=university problem_id=719
problemset_problem problem_id=719
overview
overview a=b
test b=z
TEST

خروجی نمونه🔗

https://quera.ir/careers/company/torob
https://quera.ir/careers/company/!@#
https://quera.ir/problemset/olympiad/725
https://quera.ir/problemset/university/719
[Error] missing parameter(s)
https://quera.ir/overview
https://quera.ir/overview
a/z/c
[Error] url not found

دانشکده‌ی هوافضا به تازگی از فضاپیمای «شریف نورد» رونمایی کرده است. این فضاپیما دارای $n$ صندلی است که به صورت دوری چیده شده‌اند و به صورت ساعت‌گرد روی آنها شماره‌های ١ تا $n$ نوشته شده است. قرار است در پروازی آزمایشی همه‌ی $n$ دانشجوی دانشکده‌ی هوافضا با این فضاپیما سفر کنند.

هرکدام از دانشجویان این دانشکده یک شماره دانشجویی یکتا از ١ تا $n$ دارد. مسئول این پرواز آزمایشی، به هر یک از دانشجویان یک کارت داده که روی هر کدام از آنها یک شماره از ١ تا $n$ نوشته شده است. در هنگام پرواز همه‌ی دانشجویان به ترتیب شماره دانشجویی وارد «شریف نورد» شده و هر کس کارتی که در دستش هست را نگاه می‌کند و به سراغ صندلی با آن شماره می‌رود. اگر آن صندلی خالی بود روی آن می‌نشیند وگرنه $c$ صندلی در جهت ساعت‌گرد جلو می‌رود. اگر صندلی جدید خالی بود می‌نشیند و اگر خالی نبود باز $c$ صندلی در جهت ساعت‌گرد جلو می‌رود. او آن قدر این کار را تکرار می‌کند تا به یک صندلی خالی برسد. سپس آنجا می‌نشیند.

مثللاً اگر $c$ برابر ٣ باشد و $n$ برابر ٧ باشد و صندلی ۵ و ١ پر باشند، کسی که بخواهد روی صندلی ۵ بنشیند به جای این که روی ۵ بنشیند روی ۴ مینشیند.

مسئول پرواز پس از اینکه همه نشستند برای اینکه به همه نشان دهد باهوش است تصمیم گرفته است بدون این که به صندلی‌ها نگاه کند بگوید هر دانشجویی روی کدام صندلی نشسته است. اما او دید این کار سخت است و آن قدر هم باهوش نیست. لذا از شما درخواست کمک کرده است.

ورودی🔗

در خط اول به ترتیب $n$ و $m$ و $c$ می‌آید. ($m,n \leq 100$ و $1 \leq c \leq n-1$ و $m \leq n$)

سپس در خط بعد $n$ عدد می‌آید که عدد $i$ ام، عدد کارت دانشجو با شماره دانشجویی $i$ را مشخص می‌کند. در خط بعد $m$ شماره‌ی دانشجویی از میان $n$ شماره‌ی دانشجویی موجود آمده است که شما باید بگویید هر یک بر روی چه صندلی ای نشسته‌اند (به همان ترتیبی که این $m$ عدد آمده اند.) در این $m$ عدد ممکن است اعداد تکراری نیز وجود داشته باشد.

خروجی🔗

اگر امکان نشستن همه‌ی افراد وجود نداشت، در خروجی تنها کلمه‌ی Impossibe را چاپ کنید. در غیر این صورت شما باید $m$ عدد چاپ کنید که شماره صندلی‌های افرادی است که سوال شده‌اند.

ورودی نمونه ۱🔗

5 4 2
5 1 5 2 5
4 1 3 5

خروجی نمونه ۱🔗

4 5 2 3 

ورودی نمونه ۲🔗

6 2 2
3 5 1 1 1 1
1 2

خروجی نمونه ۲🔗

Impossible

در آخرین اکتشافات باستان
‌شناسان در سرزمین «کهن»، یک دفترچه بسیار مرموز پیدا شده است. طی تحقیقات بسیار مشخص شد که این دفترچه، دفترچه خاطرات رستم است. پس از ناکام ماندن تلاش باستان‌شناسان برای خواندن خاطرات رستم، مشخص شد که رستم از بیم خوانده شدن خاطراتش، متن این دفترچه را با الگوریتم
های بسیار پیچیده رمزنگاری کرده است و کلید این رمز را در یکی از اهرام «دور» قرار داده است.

این کلید امروزه تحت تدابیر شدید امنیتی در موزه «دور باستان» نگهداری می‌شود و این موزه به هیچ وجه حاضر نیست این کلید را در اختیار باستان‌
شناسان سرزمین «کهن» قرار دهد.

پس از اصرارهای زیاد باستان
‌شناسان «کهن»، موزه «دور باستان» حاضر شد این کلید را در اختیار آن
ها بگذارد. بنابراین درب سالن محل نگه
داری این کلید را باز کرد تا بروند و این کلید را بردارند. اما باستان‌
شناسان باهوش «کهن» متوجه شدند در مسیر درب سالن تا خود کلید تعدادی تله قرار داده شده است. آنها با تجهیزات پیشرفته‌ی خود، مکان این تله‌ها را پیدا کرده‌اند و اکنون می‌خواهند همه مسیر
های ممکن برای رسیدن به کلید را بررسی کنند و بهترین مسیر را انتخاب کنند.

این سالن به شکل یک جدول $1\times n$ است که در خانه‌ی شماره ۱، باستان‌شناسان «کهن» قرار دارند (با نماد B) و در خانه‌ی شماره $n$، کلید قرار دارد (با نماد K) و در برخی از خانه‌های دیگر تله وجود دارد (با نماد T). اگر باستان‌شناسان وارد خانه‌ی تله‌دار بشوند، به پایین می‌افتند و خوراک کوسه‌ها می‌شوند.

باستان‌شناسان «کهن» در هر حرکت می‌توانند یکی از این سه کار را انجام دهند:

• یک خانه به جلو بروند.
• از خانه جلویی بپرند (مستقیماً به دو خانه جلوتر بروند.)
• از دو خانه جلویی بپرند (مستقیماً به سه خانه جلوتر بروند.)

برنامه شما باید تعداد همه راه‌های ممکن برای رسیدن باستان‌شناسان به کلید را محاسبه کند.

ورودی🔗

در خط اول، عدد n می‌آید و در خط بعدی نقشه‌ی سالن به شکل یک رشته به طول $n$ از حروف B و T و K و . می‌آید. حرف . نماد خانه‌های خالی است. مقدار $n$ حداکثر ٢٠٠ خواهد بود.

خروجی🔗

در خروجی تعداد راه‌های ممکن برای رسیدن باستان‌شناسان به کلید را بنویسید.

ورودی نمونه ۱🔗

21
B..T.T....TT.T.T....K

خروجی نمونه ۱🔗

198

ورودی نمونه ۲🔗

5
B..TK

خروجی نمونه ۲🔗

3

ورودی نمونه ۳🔗

30
B..T.....TT..T.T...TTT..T.T..K

خروجی نمونه ۳🔗

0

ورودی نمونه ۴🔗

50
B..T..T.T..TT...T.T..T.TT.T....T.T...TT.T..T....TK

خروجی نمونه ۴🔗

93312

نردبان کلمات یک دنباله از کلمات است که که هر دو تا کلمه‌ی پشت‌سر‌هم صرفا فقط در یک حرف تفاوت داشته باشند.. یک مثال از این نردبان کلمات (‌البته به صورت افقی نوشته‌ایم!!) می‌تواند $todo, food, wood, word, down$ باشد. توجه کنید که حروف دو کلمه‌ی پشت‌سر‌هم می‌تواند جابه‌جا شود ولی دقیقا یک حرف باید تغییر کند. برای این مسئله به شما یک فرهنگ لغات از کلمات مختلف داده می‌شود که همگی طولشان یکسان است. شما باید یک برنامه بنویسید که کوتاه‌ترین نردبان از کلمات را بیابد که کلمه‌ی اول و کلمه‌ی آخر آن هیچ حرف یکسانی نداشته باشد.

توجه🔗

اگر $s$ و $t$ دو رشته از حروف باشند، که تعداد حروفشان یکسان است و $s_i$ حرف $i$ام رشته‌ی $s$ را نشان دهد آنگاه گوییم $s$ از $t$ به صورت الفبایی کوچکتر است اگر برای یک $i$ داشته باشیم $s_i < t_i$ و برای تمام $j<i$ داشته باشیم $s_j=t_j$

محدودیت‌ها🔗

$1 \leq n \leq 100$ $1 \leq l \leq 20$

• زبان C و C++
  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۱۵۰ مگابایت
• زبان پایتون و جاوا
  • محدودیت زمان: ۲.۵ ثانیه
  • محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

سطر نخست ورودی شامل دو عدد صحیح به ترتیب $n$ و $l$ می‌باشد که نشان‌دهنده‌ی تعداد کلمات فرهنگ لغات و طول هر کدام می‌باشد. در هر کدام از $n$ سطر بعد یک کلمه با حروف $a-z$ به طول $l$ آمده است.

خروجی🔗

در تنها سطر خروجی کوچکترین نردبان الفبایی با شرایط خواسته شده را چاپ کنید و بین هر دو کلمه‌ی پشت سر هم فاصله چاپ کنید. ورودی به گونه‌ای داده می‌شود که تضمین شود حتما نردبان خواسته شده وجود دارد و اگر چندین نردبان با طول یکسان وجود داشت، نردبانی را انتخاب کنید که با توجه به تعریف داده شده به صورت الفبایی کوچکتر باشد.

مثال🔗

نمونه ورودی🔗

9 3
alt
spy
sea
opt
pea
ape
spa
apt
ale

نمونه خروجی🔗

ale alt apt opt