مجموعه سوالات برنامه نویسی

الان که می‌نویسم فرودگاه مسکوییم و تا چند ساعت دیگه برمی‌گردیم ایران به امید خدا. رفته بودیم دانشگاه MIPT مسکو برای شرکت در Moscow Workshops Pre-Finals که هر سال قبل از World Finals برگزار می‌شه و تیم‌های دانشگاه‌های مطرح دنیا درش شرکت می‌کنن. امسال هم جور شد و با کمک دانشگاه عازم این کمپ شدیم.

ادامه مطلب

صورت سوال رو خوندید و به اندازه کافی به سوال فکر کردید؟ اگه آره و می‌خواید حالا ایده‌های حل رو ببینید ادامهٔ مطلب رو بخونید:

• فرض کنیم قراره فقط یه دونه چند ضلعی با ضلع‌های داده شده بسازیم. اگه بتونیم این مسئله رو در O(n) حل کنیم بلافاصله یه راه حل O(n^3) با استفاده از dp داریم. بیاید این مسئله رو حل کنیم. ظاهرا یک چند ضلعی منعطف (یعنی می‌شه مثل این سوال زاویه‌هاش رو عوض کرد) وقتی مساحت بیشینه رو داره که همهٔ رئوسش روی یک دایره باشن. اینجا دو تا اثبات برای این قضیه اومده که اولیش بر پایهٔ اینه که با محیط ثابت دایرست که مساحت بیشینه رو داره و دومی هم بر پایهٔ درست بودن این قضیه برای چهارضلعی (بر اساس

  Bretschneider's formula) اون رو برای n-ضلعی‌ها اثبات می‌کنه. این رو هم اثبات می‌کنه به سادگی که ترتیب ضلع‌ها اهمیتی نداره چون می‌شه هر دو یال مجاوری رو جابجا کرد. بنابراین می‌تونیم روی شعاع دایره باینری سرچ بزنیم و ببینیم می‌تونیم یال‌ها رو روی دایره بچینیم به طوری که خودش رو قطع نکنه؟ اینجا یه سری ظرافت داره البته! باید دو حالت اینکه مرکز دایرهٔ محیطی داخل چند ضلعی بیفته یا خارجش رو جداگونه در نظر گرفت. بهترین راه برای بررسی این امکان هم احتمالا پرداختن به زاویه‌هاست که

  اینجا قشنگ توضیح داده.

•  
• هنوز تموم نشده! الان یه راه O(n^3 log R) داریم که خوب نیست و تایم می‌شه. اینجا یه فکتی میاد وسط که نمی‌دونم چرا درسته اینکه اگه جواب این نباشه که همه رو بکنیم یه چند ضلعی اون وقت بلند ترین یال قطعا استفاده نمی‌شه. بنابراین هر بار جواب رو حساب می‌کنیم برای یک چند ضلعی ساختن، بزرگترین رو می‌اندازیم دور و بازگشتی برای باقی مونده‌ها حل می‌کنیم و بیشینه می‌گیریم. اینطوری O(n^2 log R) داریم! :) اگه اون فکت دور انداختن بزرگترین یال رو اثبات کردید ممنون می‌شم تو نظرات بگید!

در این مطلب دربارهٔ World Finals 2011 نوشتم. اگر فکر می‌کنید روزی برای تمرین مسابقهٔ جهانی یا به بهانهٔ دیگری این مسابقه رو می‌دید خوندن این مطلب رو به بعد از اون موکول کنید تا بدون پیش‌فرض به سراغ مسابقه و سوالات بروید.

ادامه مطلب

سلام :)

هفت سال از عمر این بلاگ می‌گذره، خیلی جالبه برام!

۳۰ آذر که مسابقهٔ منطقه‌ای رو به لطف خدا اول شدیم، روزشمار پایان عمر ACMی ما شروع شد. از اون روز دقیقا ۱۰۰ روز تا World Finals باقی مونده بود و الان که دارم این مطلب رو می‌نویسم فقط ۷۸ روز مونده. تصمیم گرفتم تو این مدت باقی‌مونده که آخرین ماجراجویی‌هامون رو به این شکل داریم می‌کنیم بعضی وقتا بیام اینجا و بنویسم.

سلام، پاییزتون مبارک!:)

مسئله 25 ام از سوال های UVa

در دسته سوالای آسان!

ترجمه از : امیر آذرمهر

10970 – Big Chocolate

محدودیت زمانی : 3 ثانیه

شکلات بزرگ

محمد اخیرا از سوئیس بازدید کرده . از اونجایی که دوستانش رو خیلی دوست داره تصمیم گرفت که براشون شکلات بخره. ولی از اونجایی که شکلات خیلی گرونه اون می تونست فقط یک شکلات بخره. البته یه شکلات خیلی بزرگ برای همه ی اون ها به عنوان یه سوغاتی. اون می خواد به همه ی دوستانش به اندازه ی مساوی شکلات بده و اون بر این باوره که همه ی انسان ها با هم برابرن.

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

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

وظیفه ی شما اینه که بهش بگید حداقل با چه تعدادی می تونه شکلات رو به قطعات ریز تبدیل کنه.

ورودی

ورودی از تعدادی خط تشکیل می شه در هر خط دو عدد صحیح به ترتیب نشان دهنده تعداد ردیف ها و سطون ها هستند. شما با ید تا وقتی ورودی بگیرید که با انتهای فایل رو به رو شود . اعداد از 300 بیشتر نیستند.

(لینک راهنما :

http://acm-problems.blog.ir/1390/11/23/Input-Output)

خروجی

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

نمونه ها و لینک ها در ادامه مطلب .

ادامه مطلب