ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

حل های من برای مسابقه مرحله اول بیان

يكشنبه, ۷ آبان ۱۳۹۱، ۰۹:۵۴ ب.ظ

سلام

بدون هیچ مقدمه ای میرم سراغ سوالات کانتست .

سوال اول :

سوال می گفت یه رشته عددی بین 3 تا 5 رقم بهتون میدم ، مقلوب ( reverse ) این رشته رو تو ورودی چاپ کنید .

ّبرای حل یه string در نظر گرفتم که با تابع reverse از کتابخونه algorithm از مجموعه STL های سی پلاس پلاس این رشته رو مقلوب کردم و ...


سوال دوم :

این سوال دو رشته به عنوان ورودی می داد که رشته اول "دوری" فرض شده بود ؛ یعنی اینکه بعد از کاراکتر آخر به کاراکتر اول میشه رفت و همین طور از اول به آخر .

سوال می پرسید که آیا رشته دوم یا reverse اون به صورت یه زیر رشته ( SubString ) از رشته اول هست یا نه ؟

برای این کار من رشته اول رو به آخر خودش اضافه می کردم ( با این کار دوری بودن رشته رو مهار می کردم ) ، بعد چک می کردم که رشته اول یا reverse اون تو این رشته هست یا نه .


سوال سوم :

سوال یه آرایه دو بعدی از اعداد می داد که برابر ارتفاع یه سری خونه بودن و سوال تعداد خونه های بد رو می خواست .

منظور از یه خونه بد اینه که نشه از اونجا دریا رو دید یا به عبارت دیگه در تمام جهات شمال ، جنوب ، شرق و غرب حداقل یه خونه وجود داشته باشه که ارتفاعش از این خونه بیشتر باشه .

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

با توجه به اندازه داده های ورودی این روش مشکلی نداره ولی اگر اندازه جدول بزرگتر می بود این روش از نظر زمانی کارایی نداشت .


سوال چهارم :

این سوال دو مثلث می داد و مساحت ناحیه مشترک ( در صورت وجود ) رو می خواست .

به وضوح مجموعه رئوس ناحیه مشترک از یکی از دو مجموعه زیر باید باشن .

الف : راسی از مثلث اول که درون مثلث دوم قرار داره یا برعکس .

ب : نقطه تلاقی پاره خطی از مثلث اول با پاره خطی از مثلث دوم .


برای تشخیص مجموعه نقاط "الف" ، از ضرب خارجی استفاده می کردم .

برای تشخیص مجموعه نقاط "ب" ، برای هر مثلث سه پاره خط می ساختم و نقطه تقاطع ( در صورت وجود ) رو بدست می آوردم .


بعد از این کار convex-hull نقاط بدست اومده رو بدست می آوردم ولی بعد از حل اثبات کردم این کار لازم نیست .


در آخر مساحت چند ضلعی بدست اومده رو از طریق روش مثلث بندی بدست می آوردم .


کد هایی که سر کانتست ارسال کردم رو می تونید از اینجا دانلود کنید .

سوال اول

سوال دوم

سوال دوم - پایتون

سوال سوم

سوال چهارم


تو سوال آخر از همه توابعی که import شدن استفاده نشده .


با آرزوی موفقیت همه در مرحله دوم مسابقه

موافقین ۷ مخالفین ۰ ۹۱/۰۸/۰۷
رضا حسینی آشتیانی

نظرات  (۱۸)

سلام
مرسی خیلی خوب بود
include هات منو کشته 
مرسی
mishe esmetono begin
ya begin chandom dbirestan ya asan daneshga ...
پاسخ:
سلام
اسم من : رضا حسینی آشتیانی
دانشگاه : صنعتی امیرکبیر
رشته : ریاضی محض

من یه مقداری بدشانس بودم سر سوال چهار!

چون به راحتی حلش کردم اما به دلیل استفاده از راه حل غیربرداری و عدم دقت اعشار، نشد که بشه :)

من از دوران دبیرستان خیلی فاصله گرفتم برای همین بحث برداری که شما استفاده کردید (و مطمئنا بهتر و راحت تره) یادم نبود لذا از توابع ساده‌ای که در خصوص خط یادم بود استفاده کردم.
تمام نقاط تلاقی اون 6 پاره‌خط رو پیدا کردم (دو معادله دو مجهول) که میشه 15 نقطه
بعد هر کدوم از این 15 تا نقطه که داخل یا روی «هر دو مثلث» بود رو به عنوان رئوس چندضلعی نهایی درنظر گرفتم. مساحت چند ضلعی‌ها رو هم که بقول شما با مثلث بندی و قانون هرون (که ته ذهنم مونده بود و با سرچ پیداش کردم) بدست آوردم.
سوال سوم رو با الگوریتم بهتری میشد حل کرد
یک ارایه دو بعدی میساختی بعد تو هر سطر و ستون یه بار از اول و یه بار از اخرش پیمایش میکردی
تو پیمایش اگه ارتفاع هر خونه بیشترین ارتفاعی باشه که تو این پیمایش دیدی باشه یعنی دید داره
اینطوری هر خونه فقط چهار بار پیمایش میشه
یعنی شما تک تک این مثلث ها رو دستی وارد می کردید
پس چرا از فایل ها استفاده نکردید؟؟؟؟؟؟
پاسخ:
"cs" جان ، من از GCC استفاده می کنم ؛ می تونم ورودی رو از فایل بدم و خروجی رو تو فایل ذخیره کنم .
اینکه تو کد اسمی از فایل نیومده دلیل بر استفاده نکردن از فایل نیست .
والا ما که هنوز درسمون نرسیده بفهمیم شما چی نوشتی من فقط سوال 1 و 2 رو حل کردم
ایشالا سال ها بعد جوابا رو نگاه می کنیم تو کفش می مونیم
از طرف یک اول دبیرستانی المپیاد کامپیوتری
پاسخ:
"bb" جان ، همین که از حالا با برنامه نویسی آشنا هستی خیلی خوبه و می تونی به جا های خوبی برسی .
اینکه نتونستی تمام سوالات رو حل کنی نا امیدت نکنه .
پیشنهاد من بهت اینه که تا می تونی سوال حل کنی ، اگه تو سوالی هم مشکل داشتی می تونی رو من حساب کنی ( اگه بلد باشم حل کنم ) .

موفق و پیروز باشی
۰۹ آبان ۹۱ ، ۲۲:۳۶ عنکبوت حیوان نجیبی است!
مقلوب درست تره نه مغلوب!
نفهمیدم منظورتون چیه که فرمودید از gcc استفاده می کنید؟! کلا gcc کامپایلره!
احتمالا منظورتون اینه که با استفاده از gcc کدتون رو کامپایل می کنید بعد با استفاده از I/O redirection فایل رو به برنامه کامپایل شده می دید! کلا به هر برنامه اجرایی میشه اینطوری ورودی داد و gcc این وسط فقط کد شما رو کامپایل می کنه!
پاسخ:
سلام
ممنون از غلط املایی ای که از من گرفتید .
من هم می دونم که GCC یه کامپایلره .
قصدم از اون صحبت این بود که برای ورودی دادن و خروجی گرفتن کد رو تغییر ندادم ، از این روشی که شما نام بردید استفاده کردم .

۱۰ آبان ۹۱ ، ۲۲:۵۰ آیدین نصیری‌شرق
سلام رضا جان
خسته نباشی و ممنون بابت کار قشنگت. من کد سوال سه شما رو دیدم. به نظرم اگه به جای استفاده از flag های متوالی یه goto راحت می ذاشتین کدتون ساده تر و خواناتر می شد. قبول دارین؟
ضمن این که به نظرم راه حل او(ان^۲) هم داره این سوال ولی خب ان^۳ش هم می گرفت.

شاد باشی،
--آیدین
پاسخ:
سلام آیدین جان .
نمی دونم خوبه یا بد ولی کلا من از goto استفاده نمی کنم .

در مورد راه حل هم درست میگی !
من تو کانتست به این فکر کردم که 100 تا تست داریم و ماکزیمم سایز هم 100 می تونه باشه ، با یه حساب کلی میشه 10^8 که کمتر از 1 ثانیه به جواب می رسه و اینکه برای ارسال جواب ها 10 دقیقه وقت داشتیم .

ممنون از اینکه به وبلاگ سر زدی .
راجع به حل مجموعه نقاط الف و ب کمب بیشتر توضیح دهید.
ممنون
سلام
مرسی که وقتتون رو اینجا برای ما میذارید
لطفا برای مرحله حذفی هم این کار رو بکنید
پاسخ:
سلام s.a جان .
متاسفانه مشکلاتی برام پیش اومد که نتونستم تمام کانتست رو باشم و به همین دلیل نتیجه خوبی نگرفتم .
فقط سوال اول و دوم و آخر رو خوندم و تونستم دو تای اول رو بزنم .
بزارید کانتست رو برای تمرین بزارن ، حتما سوالاش رو حل می کنم و تو یه پست در موردش صحبت می کنم .
اگه مطلبی در مورد سوال خاصی داری می تونی بپرسی تا من یا یکی از دوستان به سوالت جواب بدیم .

موفق و پیروز باشی
میشه لطف کنید جواب سوال 2 رو با برنامه پایتون هم بگید لطفا
پاسخ:
سلام
حل سوال دوم با پایتون هم به پست اضافه شد .

ممنونم :)
سلام
اینجا کسی با سی شارپ کار نمیکنه؟ کلا وارد دنیای دات نت نمیشید؟ 
پاسخ:
سلام
تو مسابقه ای سی ام نمیشه از سی شارپ استفاده کرد .
فقط تو مسابقات آزاد و انفرادی میشه ازش استفاده کرد مثل : TopCoder , CodeForces , ...

سلام
چرا تو بعضی سوالات مثل سوال اول این همه فایل سرآیند رو فراخوانی کردید ؟
اصن نیاز به ایک کار و ی سری دستورات دیگه بود ؟

پاسخ:
سلام
تعداد کتابخانه ها تاثیری روی کار کامپایلر نداره .
برای راحتی همه کتابخانه هایی که بلد هستید رو تو یه فایل داشته باشید .
زمان کد زدن فقط کپی کنیدش و از هر چیزی که بلدید استفاده کنید ؛ صرف نظر از اینکه include شده یا نه .


سلام چرا نمیشه از سی شارپ استفاده کرد؟
دادا این همه الگوریتمی که گفتی من اصلا نشنیدم یعنی چنین چیزی یا مبحثی رو تو ریاضی نگفتن؟

به نظر خودت من برای اینکه برنامه نویسیم قوی بشه چیکار کنم من ترم اول نرم افزارم و فقط c++
بلدم اونم تا حد دانشگاهی من فقط از c++ خوشم میاد حوصله هیچ زبونیم ندارم
پاسخ:
سلام
تو مسابقات ای سی ام فقط زبان های C و C++ و Java و Pascal ساپورت میشه .

برای یادگیری می تونی کتاب های الگوریتمی بخونی و سعی کنی ازشون سوال حل کنی .
منبع اصلی CLRS ه اما کتاب های دیگه ای هم هستن که خوندشون بد نیست مثل Creative یا Vazirani .
اگر با کلیات مسابقه برنامه نویسی هم آشنا نیستی می تونی Art o Programming Contest رو بخونی و مسائلش رو حل کنی .

برای مسابقه ی ای سی ام فقط یه مقدار اطلاعات پایه در مورد برنامه نویسی لازم داری و تسلط به برنامه نویسی .

در مورد قوی شدن برنامه نویسی هم نظری ندارم ، چون اساسا صاحب نظر نیستم تو این مقوله .

موفق و پیروز باشی
۲۴ مهر ۹۳ ، ۱۹:۰۷ محمد جواد پیشوایی
سلام 
برای تشخیص مجموعه نقاط "الف" در مسئله چهارم ، چگونه از ضرب خارجی دو بردار استفاده کرده‌اید . اگر ممکن است بیشتر توضیح دهید .
پیشاپیش تشکر میشود
پاسخ:
سلام
برای اینکه ببینیم یه نقطه داخل یه چندضلعی محدب قرار داره یا نه، رئوس چندضلعی رو به صورت پادساعتگرد شماره گذاری می کنیم و بعد به ازای هر دو نقطه متوالی از روی چندضلعی(مثلا a,b) با نقطه موردنظرمون(مثلا x) میایم علامت ضرب خارجی بردارهای ab و bx رو بدست میاریم.
اگه به ازای تمام زوج نقاط a,b علامت مثبت باشه، نقطه داخل چندضلعی قرار داره.

سلام
میشه بپرسم convex-hull چیه؟
پاسخ:
منظور از convex hull با پوش محدب یه مجموعه از نقاط، کوچکترین چندضلعی محدبی است که همه نقاط رو شامل میشه.
اینجا رو نگاه کن کامل توضیح داده.

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی