پاسخ - SGU 269
متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=269
ترجمه :
یک board را اینگونه تعریف می کنیم - مجموعه ای از ردیف های از چپ به راست که هر ردیف تعدادی خانه از 1 تا 250 تا دارد و تعداد ردیف ها و اندازه هر ردیف در ورودی داده می شود ....
به عنوان مثال - boardی با تعداد 4 ردیف و اندازه ردیف های به صورت (1, 4, 3, 5) شکل زیر است :
می خواهیم تعداد k سنگ را در خانه های این board داده شد در ورودی قرار دهیم به صورتی که شرایط زیر حفظ شود :
1) در هیچ خانه ای بیش از 1 سنگ قرار نمی گیرد
2) هیچ دو سنگی نباید در یک ردیف یا در یک ستون قرار بگیرند (توجه داشته باشید که وجود خانه های خالی تاثیری در شرط مسله ندارد )
وظیفه شما این است که به ازای ورودی داده شده بگویید به چند طریق این کار قابل انجام است ؟
ورودی :
در خط اول n تعداد ردیف های board و بعد k تعداد مهره ها می آید
در خط بعدی b1 b2 b3 ... bn می آیند که هر کدام نشان دهنده ی اندازه ردیف i ام board است .
1<= n,k,bi
n,k,bi<=250
خروجی :
در تنها خط خروجی باید تعداد چیدمان های مختلف به ازای ورودی داده شده که همان جواب پرسش هست را چاپ کنید .
شرح راه حل :
واضح است که برای پاسخ دادن به همه ی ورودی ها باید Bignum بنویسیم(چرا؟) . ولی از این موضوع صرف نظر و فقط به شرح الگوریتم می پردازیم .
همان طور که از صورت سوال بر می آید ترتیب در ردیف های یک board تاثیری ندارد و می توان آنها را با هر ترتیب دلخواه در نظر گرفت پس می توانیم آنها را مرتب بکنیم .(به ترتیب تعداد خانه های هر ردیف)
بعد از مرتب کردن واضح است وجود هر مهره در یک ردیف با شماره کمتر (بالاتر) باعث می شود دیگر نتوانیم در ردیف های با شماره بیشتر (پایین تر) در آن ستون مهره قرار بدهیم .
با توجه به این موضوع می توانیم پرسش را با بهره گیری از برنامه ریزی پویا حل کنیم .
آرایه B را اینگونه تعریف می کنیم : هر خانه i برابر است با تعداد خانه های ردیف i ام
آرایه Ans را اینگونه تعریف می کنیم :
هر خانه i,j از آرایه تعداد راه های قرار دادن j مهره در i ردیف اول را در خود نگه می دارد (توجه کنید ردیف ها مرتب شده اند)
حالات پایه را به ازای هر 1,i برابر با تعداد خانه های ردیف های 1 تا i قرار می دهیم (چرا ؟)
رابطه بازگشتی روی i,j اینگونه تعریف می شود
(Ans [i][j] = Ans[i-1][j]+ Ans[i-1][j-1] * (B[i]-j+1 (چرا؟)
کد راه حل : http://snipt.net/JahanaraCo/sgu269/
سلام!
حرفی برایگفتن ندارم :-" فقط
:-ابراز وجود!