من فقط الف رو چند وقت پیش به دست آوردم ولی نمی دونم درست باشه یا نه ... ب و ج رو هم هنوز نگاه نکردم!
2015-04-13 13:31:35 -0600 تهی نامآمار پرسش:
- پرسیده شده: 2015-01-21 16:26:08 -0600
- مشاهده شده: 1,502 بار
- بروز شده: 2015-07-17 11:11:06 -0600
پرسش‌های مشابه:
یافتن کوتاه ترین دور در گراف ساده
کد مساله هشت وزیر با استفاده از الگوریتم ژنتیک
مرجع فارسی برای الگوریتم های هندسی و 2sat
برای مرحله سوم، تا چه سطحی باید برنامه نویسی بلد باشیم؟
اولین جمله از دنباله ی فیبوناچی که 1000رقم داشته باشد چیست؟
گذاشتن n وزیر در صفحه ی شطرنج بطوری که همدیگر را تهدید نکنند
کسی جزوه یا سوال خوب برای segment tree داره؟
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
سوال دوم مرحله سوم دوره 24: عبور از سد دفاعی ایران (حل شد + کد)
کسی می تونه حلش کنه؟ مخصوصا قسمت آخرشو
2015-01-21 16:26:08 -0600
دیوی 293 ● 4 ● 7 ● 14
نظرات
2 پاسخ
ببین برای قسمت ج اش میدونیم که ۱۰۰۰۰ ^ ۲۰۰0۰(ده هزار به توان بیست هزار) سیستم مختلف داریم. حالا بیا فرض کن تمام سیستم هارو ، هر کدومشون رو با ۲۰۰۰۰ مستطیل پر کردیم(برای هر ستون یه مستطیل گذاشتیم که اون ستون رو تا بالا پر کرده) . حالا میایم حساب میکنیم کدوم مستطیل هارو اضافه گذاشتیم. در حقیقت توی هر سیستم برای هر دو ستون با ارتفاع برابر (ارتفاعشون رو با h نشون میدیم) اگر بینشون هیچ ستونی با ارتفاع بزرگتر مساوی h وجود نداشته باشه میتونیم به جای دو تا مستطیل برای هر کدوم از این دو ستون ، یک مستطیل بذاریم، (اینطوری که با یه سری مستطیل ارتفاع ستون های بینشون رو به h برسونیم و بعد یه مستطیل روی این دوتا ستون و همه ی ستون های بینشون بذاریم). بنابراین اگر بتونیم تعداد جفت ستون هایی رو که هم ارتفاع اند و ارتفاع ستون های بینشون از ارتفاع اون دو کمتر هست رو بشمریم و به ازای هر جفت یکی از تعداد مستطیل هایی که در اول کار گذاشته بودیم کم کنیم، به جواب میرسیم. حالا تعداد این جفت هارو چطور بشمریم؟ یه فور میزنیم روی مقدار d (فاصله ی دو ستون) و برای هر مقدار d تعداد جفت هارو میشمریم (برای هر مقدار d جواب جدا باید حساب کنیم و با جواب کل جمع کنیم) . حالا یه فور میزنیم برای مقدار h . برای هر مقدار h ، ارتفاع ستون های بین ستون i و j به اندازه ی h ^ d حالت داره و بقیه ی ستون ها هم (۱۰۰۰۰ به توان (20000 - d - 2) ) حالت داره که ضرب این دو مقدار با جوابمون جمع میشه و در نهایت این جوابی که برای هر مقدار d بدست میاریم رو در تعداد حالت های انتخاب ستون i ام ضرب میکنیم ، با جواب کل جمع میکنیم.(البته تا جایی که یادمه میتونستیم برای هر d جواب رو (1)o هم حساب کنیم حالا فرمولشو بنویس ببین میشه یانه) مقدار ۱۰۰۰۰ ^ ۲۰۰0۰ رو هم حساب میکنیم و جواب بدست اومده رو ازش کم میکنیم و مقدار حاصل میشه جواب مساله! بیشتر از یه ثانیه طول میکشه ولی جواب میده.
2015-07-16 11:18:38 -0600
تتتت 81 ● 1 ● 4
نظرات
Rahet eshtebahe ha :)) chonke age 4 ta barabar bashan to 6 ta kam mikoni na?
2015-07-17 00:48:42 -0600 آرش خان@آرش خان " اگر بینشون هیچ ستونی با ارتفاع بزرگتر مساوی h وجود نداشته باشه میتونیم به جای دو تا مستطیل برای هر کدوم از این دو ستون ، یک مستطیل بذاریم " گفتم بزرگتر مساوی نه بزرگتر برای همین اگر چهار ستون (به ترتیب از چپ به راست) s1,s2,s3,s4 ارتفاعشون برابر باشه، و بین هیچ دوتای متوالیشون ستون دیگه
2015-07-17 02:59:08 -0600 تتتتستون دیگه ای با ارتفاع بیشتر مساویشون وجود نداشته باشه به ازای هر جفت متوالی اینا (s1,s2 وs2,s3 وs3,s4) یه مستطیل اضافه گذاشتم پس سه تا از مستطیلامو کم میکنم و به جای گذاشتن ۴ تا مستطیل از یه مستطبل استفاده میکنم.
2015-07-17 03:09:10 -0600 تتتتاین کدش: http://paste.ubuntu.com/11893021/ توضیح هم کسی میخواد بگه که بگم. ...........................................................................
2015-07-17 09:31:51 -0600
فارسی 99 ● 4
نظرات
@غلیظ ، وقت نمی کنم الان توضیح کامل و با اثبات بنویسم :( ، ولی خلاصش اینه: dp[i] q رو تعریف کردم جواب مساله برای حالتی که تعداد ستون ها i تا باشه. اگه یه ستون باشه که جواب واضحه. اگه نباشه، 100۰0 * dp[i - 1] q تا حرکت لازمه تا توی همه حالت ها، i - 1 تا ستون اول رو درست کنیم(تعریف درست واضحه دیگه؟)
2015-07-17 16:53:22 -0600 فارسی