تیم برنامه نویسی گروه تمدن

به نام خدا

یک صفحه m در n در نظر بگیرید که خانه های آن مانند صفحه ی بازی مار و پله با اعداد 1 تا mn شماره گذاری شده اند. فردی در ابتدا در خانه ی 1 ایستاده است و می خواهد با تعدادی حرکت به خانه ی mn برود. k نردبان نیز وجود دارند که هر نردبان میان دو خانه ی متفاوت جدول قرار دارد.. در هر حرکت فرد می تواند یکی از این دو کار را بکند:

1-   اگر نردبانی وجود دارد که یک سرآن در خانه ی فعلی است به سر دیگر برود ، به شرط اینکه شماره ی خانه ی مقصد بزرگتر از شماره ی خانه ی فعلی وی باشد.
2-     به خانه ای که شماره اش دقیقا یکی بیشتر از خانه ی فعلی است برود.

تعداد راه های متفاوت برای پیمودن جدول چقدر است؟

(سایر توضیحات+دانلود سوال+ دانلود جواب در ادامه مطلب)

ورودی
ورودی شامل چندین نمونه از مسئله است.
هر نمونه شامل تعدادی خط است. در اولین خط ، 3 عدد طبیعی m ،  n و k به ترتیب آمده اند.
( m<=10   &   n<=10   &   k<=20  ). در k خط بعدی در هر خط یک جفت عدد طبیعی آمده است که دو سر یک نردبان را نشان می دهند، هر دو از mn کمترند و اختلافشان حداقل 2 است. پس از آخرین نمونه ورودی خطی شامل "0 0 0" آمده است. دو سر هیچ نردبانی از جدول یکی نیستند، به عبارت دیگر تمام اعدادی که بعد از خط اول می آیند ، متمایزند. بدین ترتیب نردبان تکراری هم در ورودی وجود ندارد.
خروجی
به ازای هر نمونه مسئله ی ورودی ، یک خط در خروجی بنویسید که شامل تعداد راه های پیمودن جدول است.

(برای مشاهده خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)

دانلود فایل PDF سوال مسابقه ACM برنامه پله بازی با لینک مستقیم

دانلود سورس کد و برنامه جواب مسابقه ACM برنامه پله بازی با لینک مستقیم