به نام خدا
یک صفحه 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 برنامه پله بازی با لینک مستقیم