وبسایت مسابقه‌های برنامه نویسی
یافتن کوتاه ترین دور در گراف ساده
کد مساله هشت وزیر با استفاده از الگوریتم ژنتیک
مرجع فارسی برای الگوریتم های هندسی و 2sat
نظریه اعداد لازم برای المپیاد کامپیوتری ها
برای مرحله سوم، تا چه سطحی باید برنامه نویسی بلد باشیم؟
اولین جمله از دنباله ی فیبوناچی که 1000رقم داشته باشد چیست؟
چه جاج‌هایی برای المپیاد کامپیوتر خوب هستند؟
یه جنگل n *n داریم !(سطرها از 1 تا n و ستون ها 1 تا n )
تو خونه ی (i,j) درخت میکاریم اگر که i و j نسبت به هم اول باشند !!
حالا به یه مستطیل می گیم باغ اگر که چهار گوشه اش درخت باشد !
تعداد باغ های جدول n*n را بیابید .( mod 10499)
الف) n=88
ب) n=800
ج) n=3000
بچه راستشو بخواین سوال رو خودم طرح کردم :) ! راه حلاتون جالبه !! ولی من انتظار n^3 نداشتم و اونم این راه حل ها :) ! خیلی خلاقید !
د) برای n=10000 رو حساب کنید :p !!! (حداکثر 3 دقیقه)
راستی خوشحال میشم نظرتون رو در مورد سوال بدونم :)!
جواب http://paste.ubuntu.com/11300257/ که قسمت آخر رو حداکثر 3 دقیقه طول میکشه !!
اما خوب آرش خان یه جواب با بیت ست گذاشته که جالب بوود !! در کل مهم جواب آخره !
امیدوارم از سوال خوشتون اومده باشه !!! جواب آخر ها هم آخر کدم هست !
چرا این چند روزه همه سوالا این جوری شده؟؟الان کانتسته،،،بعدش اگه خوابم نبرد حلشو میزارم!!(درسته خنگم ولی بلدم کد بزنم)
2015-05-22 11:28:41 -0500 کنکورییکی از مزخرف ترین کانتست های عمرم!!فقط امتحان سرعت بود انگار!!الف)۸۴۴۶. ب)۱۲۹۶. ج)۱۱۶۵. راه حلشم اقا حمیدرضا میزاره(اصا معلوم نی عددام درس باشه!!مثلا خنگم دیگه!!)
2015-05-22 13:33:09 -0500 کنکورینمیدونم قرار بوده کد تو چند ثانیه تموم شه ولی فکر کنم اگه محدودیت های سوال بیشتر بود اینقدر گلابی حل نمیشد در هر صورت:
اول میایم جدولو میسازیم که میشه اردرش : $$ o(log(n)*n^2) $$
که log n اردر gcd می باشد
بعد از اون میام با اردره $n^3$ تعداد مستطیل ها رو در میاریم به این صورت که هر بار دو تا سطر رو میگیریم مانند i, j و تعداد ستون هایی مانند k رومیشمریم که $$ a[i][k]==1 && a[j][k]==1 $$ این تعداد رو c بنامید
و جواب را با انتخاب 2 از c جمع میکنیم (چرا؟!)
اینم کد فقط n رو عوض کنید کافیه برای 10000 هم سه دقیقه و نیم طول میکشه (بیت ست زدیم تنگش ضریب کم شه)
اگه درخت های هر سطر رو نگه داری لازم نیست همشو چک کنی و اردرش یکم کمتر میشه.ولی n3 یا حتی همون ne برای 3000 زیاد نیست؟ شاید منطورش n2 بوده؟
2015-05-23 00:27:51 -0500 روبیکنه دیگه n^3 برای 3000= 9000000000 که میشه 90*1e8 که بستگی داره کامپیوترت چیباشه خیلی هم بد باشه میشه 90 ثانیه = 1.5 دقیقه
2015-05-23 01:09:59 -0500 حمیدرضاهجواب اصلی همینتوریه ولی بهینه تره که اردرش n^2 ولی با ضریب مثلا 500 !
2015-05-23 01:17:05 -0500 طوفانمن نظریه اعدادم هیچ وقت خوب نبوده تو ازمایشی هم خودم تعجب کردم که یکو حل کردم !!
2015-05-23 01:18:16 -0500 حمیدرضاه:) شبیه 3 بیشتر !! ولی اره باید نظریه ات خوب باشه ! در حد کامپیوتر !
2015-05-23 01:19:14 -0500 طوفانخب این سوال رو با الگوریتم داینامیک و با o(n^3)I حل میکنیم.
میایم یک آرایه دو بعدی در نظر میگیریم مثل b که توی این آرایه تعداد در خانه b[i][j]I عدد k رو مینویسم در صورتی که k سطر پیدا کنیم که در خانه ها i و j آن درخت باشد.
نکته اول: در تمام خانه های سطر اول درخت کاشته شده است.
پس در ابتدا مقدار b[i][j]I برای هر i, j که i < j عدد ۱ هست.
و برای پر کردن خانه های آرایه b از ۳ حلقه استفاده میکنیم (سطر و ستون i و ستون j) .
واضح است که جواب مساله برابر است :
ترکیب ۲ از b[i][j]I برای هر i, j که i < j
اینم لینک کد:
http://paste.ubuntu.com/11294768
برای پاسخ به قسمت ج حدود ۴۰ ثانیه وقت میبره
پاسخ ها:
الف: ۸۴۴۶
ب: 1296
ج: ۱۱۶۵
یه قسمت د هم اضافه میکنم : n = 10000
یه ذره بهینه تر کد بزنید!!!جنگ نیست که،،،بعد امتحان دینی اگه کسی حل حل نکرد جواب میزارم،،،البته فکر کنم با حضور حمیدرضا جان وقت به ما نرسه!!
2015-05-22 19:44:06 -0500 کنکوریاین چه سوالیه اخه میپرسی بهترین اینکلود چیه یعنی چی ادم هر نیازی داشته باشه از همون استفاده میکنه :)
2015-05-22 23:57:49 -0500 حمیدرضاه