سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:49:09 -0500 امیر شکریآمار پرسش:
- پرسیده شده: 2016-03-06 01:29:50 -0500
- مشاهده شده: 737 بار
- بروز شده: 2016-04-08 07:49:30 -0500
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
مستطیل های سیاه - سوال سوم - مرحله دوم - سال ۱۳۸۱
خانه های یک جدول$ n * m $را با دو رنگ سفید و سیاه به طور دلخواه رنگ کردیم یک زیر مجموعه مستطیل شکل به ابعاد$ a,b $از خانه های جدول را یک زیر مستطیل سیاه مینامیم اگر تمامی$ a*b $خانه ی داخل آن سیاه باشند یک زیر مستطیل سیاه را غیر قابل گسترش مینامیم هر گاه یک زیر مستطیل سیاه دیگری شامل تمامی خانه های آن نباشد. ثابت کنید تعداد زیر مستطیل های سیاه غیر قابل گسترش بیشتر از$ m * n $نیست.
2016-03-06 01:29:50 -0500
حمیدرضاه 2979 ● 20 ● 26 ● 52
نظرات
2 پاسخ
یه خونه رو خونه ی خوب یه مستطیلمی گیم اگر که خونه ی پایین چپ این مستطیل باشه فرض کنیم a یه خونه خوب باشه اگر این خونه متعلق به حداقل 2 مستطیل باشه خونه ی بالا راست اشتراک این دومستطیل رو در نظر بگیرید (خونه ی b) خونه ی بالا راستش دیگه خونه ی خوبی نیست چون در غیر این صورت b خونه ی بالا راست اشتراک این دو مستطیل نیست.پس اگر یک خونه به ازای t مستطیل خونه ی خوب باشه حداقل t-1 خونه خونه ی خوب نیستند.پس اگر fi برابر باشه با تعداد مستطیل هایی که خونه ی i براشون خونه ی خوبه جمع fi ها برابر میشه با تعداد مستطیل ها.حالا فرض کنیم که همه ی fi ها برابر با یک باشند الان جمع fi ها برابر با mn هست می خواهیم با اعمال چند تغییر به fi های جدول فعلی برسیم اگر به یک fi>0 یک واحد اضافه کنیم باید یک fj رو صفر کنیم پس هر بار که ما یک تغییری رو میدیم مجموع کمتر مساوی با مرحله ی قبل میشه پس حداکثر مجموع برابر میشه با mn.
2016-03-07 13:01:41 -0500
عطا 1110 ● 7 ● 12 ● 29
نظرات
باگ داره اثباتت. b ممکنه خونه‌ی خوبی باشه مثلا این: الآن a نقطه‌ی پایین چپ مستطیل قرمز-سبز و مستطیل سبز-آبی هست و b نقطه‌ی بالا راست اشتراک این دوتا مستطیل هست و همچنین خونه‌ی خوبی نیز هست! :-)
http://up.vbiran.ir/uploads/22502146012057231931_ans.jpg
2016-04-08 07:43:30 -0500 توفیقیراه حلت اینجوری اصلاح میشه، فرض کن مجموعه مستطیل‌هایی که خونه‌ی پایین سمت چپشون a هستو در نظر بگیر، اینا رو بر حسب xعه خونه‌ی بالا سمت راستشون مرتب کن. بعد هر دوتای متوالی، خونه‌ی بالا سمت راست اشتراکشون رو اگه b بگیری، b خونه‌ی خوبی نیست.
2016-04-08 09:17:29 -0500 توفیقیشکل زیررو ببین، الآن a خونه‌ی خوب برای ۲ مستطیل هست، c هم یه خونه‌ی خوب برای ۲ مستطیل هست.
اثباتی که ارائه کردید میگه چون a برای ۲ تا خوبه، پس b خوب نیست. همچنین چون c برای ۲ تا خوبه، پس b خوب نیست.
اینجا دوتا خونه‌ی حذف نشده بلکه فقط یکی حذف شده.
2016-04-10 07:53:29 -0500 توفیقی
اثبات من اینجوریه: استقرا زدم روی عرض مستطیل، بعد شروع به شمردن کردم، یه اصل شمول و عدم شمول زدم و یه حالت بندی، بعد یه سری از مستطیل غیرقابل گسترشو رو نمی‌شمردم که به ازای هر کدوم، یک یا چندتا مستطیل غیرقابل گسترش دیگه می‌شمارم... (متناظر میکنم باهاش)
البته مطمئن نیستم ۱۰۰در۱۰۰ درست باشه:
2016-04-08 07:49:30 -0500
توفیقی 1621 ● 17 ● 21 ● 42
نظرات