سوالات و راه حل های دوره ی قبلی لیگ برنامه نویسی ACM صبا (هر پنج مسابقه) به زبان C++

مطالعه این فایل آموزشی جهت آمادگی و تسلط بیشتر برای مسابقات توصیه میشود.

سوالات و راه حل های کانتست اول
سوال اول: !!!
سوال دوم: با یک حلقه ساده هر دوتای متوالی را بررسی می کنیم
سوال سوم: می توان با استفاده از یک پشته رشته را بررسی کرد اگر براکت باز دیده شد به پشته اضافه کرده و اگر براکت بسته دیده شد عنصر بالای پشته را بررسی نموده در صورت مطلوب بودن این عنصر را حذف نمایید و ادامه دهید در غیر این صورت پرانتزگذاری نامطلوب می باشد.
سوال چهارم: از برنامه نویسی پویا استفاده کنید، هر عدد که شامل ارقام ۱ و ۲ می باشد می تواند با ضرب شدن در ۱۰ و اضافه شدن با ۱ و ۲ دو عدد جدید تولید نماید که باقی مانده آنها به n را هم داریم اولین عددی که موفق به تولید آن شدیم که باقی مانده اش بر n برابر با صفر شد جواب مسئله است و در صورتی که عدد تولید شده از ۳۰ رقم بیشتر داشت باید Impossible برگرداند.
کد ها و سوالات را می توانید دانلود نمایید.
با تشکر و آرزوی موفقیت
انجمن علمی علوم کامپیوتر
kermancs.ir

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

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

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

راه حل ها و ایده های سوالات مسابقه نهایی 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.ir

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

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

سپاس بیکران بر همدلی و همکاری و همگامی تیم اجرایی مجموعه مسابقات برنامه نویسی ACM از لیگ مسابقات صبا که با عاطفه ی سرشار و گرمای امیدبخششان در این سردترین روزگاران بهترین پشتیبان بوده اند.یقیناَ توسعه و پیشرفت انجمن علمی علوم کامپیوتر مرهون تلاش های بی دریغ مسئولین و همکاران خدوم و دلسوزی می باشد که همواره جهت تعالی و ارتقاء این انجمن٬ قدم برداشته و خدمتگذاری را افتخاری بزرگ و پاسخگویی را وظیفه ای مهم برای خویشتن می دانند.
سلامتی وموفقیت روزافزونتان را ازدرگاه خداوند متعال مسألت می نماییم.
تیم جرایی مسابقات برنامه نویسی لیگ صبا :
خانم ها :
مریم زندی
نگار نبی زاده
فاطمه امینی زاده
مهسا کشتکار
اقایان:
عرفان حاج ملک
سامان شجاعی
علی صادقی راد
بنیامین مظهری صفات

و تیم علمی مسابقات :
اقایان:
محمد مهدی طاهری
محمد علی صاحبداد
حسین وحیدی
حسن رستمی

اکنون بعد از برگزاری سه دوره مسابقات برنامه نویسی ACM مفتخریم نفر برگزیده لیگ صبا را به شما دوستان و همراهان همیشگی انجمن علمی علوم کامپیوتر معرفی کنیم :
“جناب اقای محمد مهدی امیری” نفر اول مجموعه مسابقات برنامه نویسی لیگ صبا هستند .
نفرات دوم و سوم نیز به ترتیب آقایان سروش زارع و محمدصادق مهدوی می باشند.
این موفقیت را به ایشان تبریک عرض کرده و از درگاه خداوند منان توفیق روزافزون ایشان را خواهانیم.
شایان ذکر است آقای محمدمهدی امیری با حل چهار سوال از پنج سوال مسابقه پایانی و کسب رتبه ی اول در فینال مسابقات برنامه نویسی لیگ صبا برنده دوره اخر نیز بودند.

قابل ذکر است به دلیل عدم همکاری دانشگاه در ترم گذشته جشن انجمن علمی علوم کامپیوتر و مراسم اختتامیه لیگ صبا به ترم جاری موکول گردید که در ترم جدید نیز به دلیل تاخیر در شروع شدن ترم و هم چنین تداخل با ماه محرم انجمن علمی علوم کامپیوتر از برگزاری جشن و مراسم اختتامیه معذور گردید.