مسابقات برنامه نویسی ACM (هم اکنون)

لینک خبر مسابقه امروز در وب سایت دانشگاه 👆👆

سوالات و راه حل های مسابقه ACM تاریخ ۲۰ اسفند ۹۴

رده بندی نهایی

توضیحات کلی درمورد سوالات:
۱- باید یک معمای سخت را حل میکردید.
۲- کار با رشته ها و کدهای اسکی کاراکترها یا توابع کتابخانه sstream یا...
۳- برای هر بیت ۸ حالت وجود داشت که بعضی از آنها غیر ممکن بودند در کل هر بیت حداکثر می توانست دو حالت برای بیت های اعداد x و y داشته باشد پس جواب یا صفر بود یا دو به توان k
۴- راه حل سوال ارائه یک الگوریتم حریصانه (greedy) بر حسب di ها و سپس wi ها بود. ایده های متنوعی برای پیاده سازی nlogn وجود داشت در غیر این صورت راه حل تایم میشد.
۵- باید اثبات میکردید که اگر از راست به چپ یک sweep line میزدید به هر نقطه که میرسیدید یا شیب بیشتری ایجاد نمیکرد یا با یکی از دو نقطه ای که تا به اینجا شیب بیشینه دارند شیب بیشینه ایجاد میکرد پس کافی بود که نقاط را بر حسب x مرتب کرده و سپس از راست به چپ حرکت کرده و در هر مرحله دو نطقه ای که شیب بیشینه دارند را ذخیره کرد.
nlogn
موفق باشید!
@kermancs

کلاس ACM فردا ساعت ۹:۳۰ در سایت W تشکیل می شود کسانی که حضورشان برای شرکت در کلاس ها قطعی می باشد فردا حضور داشته باشند.
با تشکر
انجمن علمی علوم کامپیوتر
@kermancs
kermancs.ir

⬅️ لیست کانال انجمن های علمی دانشگاه شهید باهنر کرمان

📗انجمن علمی نانو
👉 @shahidbahonar_nano
📗انجمن علمی مهندسی کامپیوتر
👉 @ce_uk
📗انجمن علمی مهندسی برق
👉 @elecukir
📗انجمن علمی بازیگری و کارگردانی
👉 @NAMAYESHbu
📗انجمن علمی فیزیک
👉 @bahonar_physics_academic
📗انجمن علمی مهندسی خاک
👉 @soillll
📗انجمن علمی مهندسی مکانیک
👉 @bahonarmech
📗انجمن علمی رباتیک
👉 @Brobotic
📗انجمن علمی مهندسی معدن
👉 @miningbahonar
📗انجمن علمی علوم کامپیوتر
👉 @kermancs

🔹🔷فراخوان همکاری با انجمن🔶🔸
انجمن علمی علوم کامپیوتر از تمامي دانشجويان رشته علوم كامپیوتر جهت همکاری و ارائه پیشنهادات جهت برگزاری جشن پایان ترم دانشجویان علوم کامپیوتر دعوت به عمل می آورد.
جهت کسب اطلاعات بیشتر به دفتر انجمن مراجعه نمایید.

🔺انجمن علمی علوم کامپیوتر🔻
@kermancs

🔹🔸انجمن علمی علوم کامپیوتر با همکاری انجمن علمى-تخصصى رباتيك و مكاترونيك:
آغاز مراحل آماده سازى اولين تيم هاى شبيه ساز دوبعدى دانشگاه شهيد باهنر كرمان جهت حضور در مسابقات ملى و بين المللى رباتيك در ليگ هاى شبيه ساز
اين توافقنامه روز بيست و سوم فروردين ماه جارى به امضاى دبيران دو انجمن رسيد. 🔹🔸
@kermancs

🎈☁️💡
ثبت نام مسابقه نهایی لیگ ACM صبا آغاز شد...
مسابقه در تاریخ 9 اردیبهشت راس ساعت 15 آغاز خواهد شد.
مدت زمان این مسابقه 2 ساعت می باشد.
امتیاز این مرحله دو برابر مراحل قبلی برای رده بندی نهایی لیگ می باشد.
برای ثبت نام به لینک زیر مراجعه نمایید:
http://kermancs.ir/?page_id=971
لطفا قبل از ثبت نام نکات ذکر شده در صفحه ثبت نام را مطالعه نمایید.

با تشکر
انجمن علمی علوم کامپیوتر

@kermancs
kermancs.ir

🎈چند نکته و قانون در مورد مرحله نهایی 🎈
- پرداخت هزینه به صورت حضوری می باشد.
- آوردن تا ۲۵ صفحه a4 یادداشت مجاز می باشد.
- کسانی ک تمایل به شرکت با کامپیوتر شخصی دارند باید راس ۱۴:۳۰ در سایت حضور داشته باشند و سایر شرکت کنندگان راس ساعت۱۴:۴۵
- امتیاز این مرحله در رده بندی نهایی دو برابر مراحل قبلی است
- مدت زمان مسابقه ۲ ساعت می باشد
- هر گونه تقلب می تواند موجب حذف شرکت کننده متقلب شود.
- لازم به ذکر است انجمن علوم کامپیوتر تصمیم گرفته است در نهایت یک جایزه به نفر اول لیگ در بخش دانش آموزی و یک جایزه به نفر اول لیگ در بخش دانشجویی تعلق گیرد.
- ظرفیت محدود
با تشکر
انجمن علمی علوم کامپیوتر
@kermancs
kermancs.ir

راه حل ها و ایده های سوالات مسابقه نهایی ACM
۱- نصفش کن! 😐
۲- جواب برابر است با (c(p+k-1,k-1
#combinatorics
۳- صرفا یک مرتب سازی که می توانستید این کار را با (O(n^2 انجام دهید.
#sorting
۴- راه های متنوعی برای این سوال وجود دارد می توانید [dp[i][j را به این صورت تعریف کنید که برابر باشد با مجموعه خانه های [mat[k][l که k<i و l<j باشد که :
dp[i][j] = dp[i-1][j]+dp[i][j-1]- dp[i-1][j-1]+mat[i][j]
که عناصر جدول اصلی در mat‌ ذخیره شده اند.
حال جواب برابر است با:
max{dp[i][j]-dp[i][l]-dp[k][l]+dp[k][l]} (k<i,l<j,i<=n,j<=n)
که برای به دست آوردن جواب می توانستید با یک الگوریتم (O(n^4 به جواب برسید.
#Dynamic_Programming
۵- مسئله در واقع یافتن یک چند ضلعی غیر محدب و ساده است با ضلع های موازی محور های مختصات حال به با توجه به شرایط مسئله هر نقطه دقیقا یک ضلع افقی و دقیقا یک ضلع عمودی متصل به آن نقطه دارد پس تمام نقاطی که روی یک خط افقی هستند (عرض های برابر دارد) را که در نظر بگیرید و آن ها را از ۱ تا k به ترتیب شماره گذاری کنید حتما باید راس های با شماره فرد به راس های با شماره زوج سمت راست خود وصل باشند. و همین طور برای نقاط روی خط های عمودی (طول های برابر دارند) پس با مرتب کردن همه نقاط ابتدا بر اساس x و سپس بر اساس y تمام ضلع های افقی و عمودی تعیین می شود حال باید مشخص کنید که شکل حاصل یک n-ضلعی هست یا نه که این کار با یک DFS امکان پذیر است و طول چند ضلعی هم با این DFS قابل محاسبه است همچنین در صورت وجود جواب n-ضلعی به وضوح یکتا خواهد بود پس قبل از آن باید بررسی کنید که ضلع هایی که مشخص کرده اید یک دیگر را قطع نمی کنند چرا که در غیر این صورت مسئله جواب ندارد. پس این کار با (O(n^2 امکان پذیر است که این در واقع زمان مصرفی برای بررسی غیر متقاطع بودن دو به دوی ضلع های تعیین شده می باشد.
#geometry #greedy #sorting #graph #dfs #data_structure
موفق باشد
انجمن علمی علوم کامپیوتر
@kermancs
kermancs.ir

کسب رتبه 27 در رشته علوم کامپیوتر و رتبه 65 در رشته ریاضي توسط اقای محمدمهدی طاهری مقدر دانشجوی ترم چهارم علوم کامپیوتر، از دانشجویان ممتاز دانشکده ریاضی و کامپیوتر دانشگاه شهید باهنر کرمان در کنکور ارشد را به ایشان تبریک عرض می کنیم .

انجمن علمي علوم كامپیوتر