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

۳۴ مطلب توسط «سیّد پارسا میرطاهری» ثبت شده است

World Finals 2018 - Problem G

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

 

  • فرض کنیم قراره فقط یه دونه چند ضلعی با ضلع‌های داده شده بسازیم. اگه بتونیم این مسئله رو در O(n) حل کنیم بلافاصله یه راه حل O(n^3) با استفاده از dp داریم. بیاید این مسئله رو حل کنیم. ظاهرا یک چند ضلعی منعطف (یعنی می‌شه مثل این سوال زاویه‌هاش رو عوض کرد) وقتی مساحت بیشینه رو داره که همهٔ رئوسش روی یک دایره باشن. اینجا دو تا اثبات برای این قضیه اومده که اولیش بر پایهٔ اینه که با محیط ثابت دایرست که مساحت بیشینه رو داره و دومی هم بر پایهٔ درست بودن این قضیه برای چهارضلعی (بر اساس Bretschneider's formula) اون رو برای n-ضلعی‌ها اثبات می‌کنه. این رو هم اثبات می‌کنه به سادگی که ترتیب ضلع‌ها اهمیتی نداره چون می‌شه هر دو یال مجاوری رو جابجا کرد. بنابراین می‌تونیم روی شعاع دایره باینری سرچ بزنیم و ببینیم می‌تونیم یال‌ها رو روی دایره بچینیم به طوری که خودش رو قطع نکنه؟ اینجا یه سری ظرافت داره البته! باید دو حالت اینکه مرکز دایرهٔ محیطی داخل چند ضلعی بیفته یا خارجش رو جداگونه در نظر گرفت. بهترین راه برای بررسی این امکان هم احتمالا پرداختن به زاویه‌هاست که اینجا قشنگ توضیح داده.
  •  
  • هنوز تموم نشده! الان یه راه O(n^3 log R) داریم که خوب نیست و تایم می‌شه. اینجا یه فکتی میاد وسط که نمی‌دونم چرا درسته.. اینکه اگه جواب این نباشه که همه رو بکنیم یه چند ضلعی اون وقت بلند ترین یال قطعا استفاده نمی‌شه. بنابراین هر بار جواب رو حساب می‌کنیم برای یک چند ضلعی ساختن، بزرگترین رو می‌اندازیم دور و بازگشتی برای باقی مونده‌ها حل می‌کنیم و بیشینه می‌گیریم. اینطوری O(n^2 log R) داریم! :) اگه اون فکت دور انداختن بزرگترین یال رو اثبات کردید ممنون می‌شم تو نظرات بگید!
۲۲ دی ۹۷ ، ۱۴:۵۰ ۰ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری
شنبه, ۲۲ دی ۱۳۹۷، ۰۲:۲۸ ب.ظ سیّد پارسا میرطاهری
World Finals 2011

World Finals 2011

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

ادامه مطلب...
۲۲ دی ۹۷ ، ۱۴:۲۸ ۰ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

بعد از ۷ سال

سلام :)

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

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

۲۲ دی ۹۷ ، ۱۴:۰۳ ۱ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

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

سلام!

دور دوم مسابقات برنامه نویسی بیان!

حتما شرکت کنید.

سایت مسابقه : http://contest.bayan.ir/

بلاگ مسابقه : http://contest.blog.ir/

۰۲ آبان ۹۱ ، ۲۳:۱۵ ۰ نظر موافقین ۲ مخالفین ۰
سیّد پارسا میرطاهری

Big Chocolate - شکلات بزرگ

 

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

 

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

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

 

 

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

 

10970 – Big Chocolate

 

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

 

شکلات بزرگ

 

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

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

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

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

 

ورودی

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

(لینک راهنما : http://acm-problems.blog.ir/1390/11/23/Input-Output)

 

خروجی

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

 

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

ادامه مطلب...
۰۳ مهر ۹۱ ، ۱۷:۵۸ ۴ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

Odd Sum

 

سلام، بعد از مدت ها، مسئله 24 ام از سوال های UVa

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

و البته نویسنده جدید!;)

 

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

10783 - Odd Sum

 

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

 

جمع فرد

یک محدوده [A,B] داده شده و وظیفه ی شما بدست آوردن مجموع تمامی اعداد صحیح فرد در این محدوده است. برای مثال جمع تمامی اعداد صحیح فرد محدوده ی  [3,9]، 24 =  3 + 5 + 7 + 9 است .

 

ورودی

خط اول T نشان دهنده ی تعداد تست هاست (1 < T < 100) .

هر تست شامل دو عدد صحیح A وB است (0 < A < B < 100) که باید در دو خط جدا باشد.

 

خروجی

برای هر تست شما باید یک خط خروجی بدهید کلمه ی "Case" + یک فاصله + شماره ی تست + علامت ":"  و یک فاصله + جمع اعداد فرد داخل محدوده ی [A, B]

 

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

ادامه مطلب...
۱۵ شهریور ۹۱ ، ۲۰:۳۶ ۰ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

11219 - How old are you؟

مسأله شماره23:

 

11219 - How old are you?

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

چند سالته؟

...

  • بفرمایید. این هم فرم ها.
  • ممنون. بذارید ببینم، چند سالتونه؟
  • 20، فراموشم کردم بنویسم؟
  • نه. این جا نوشته شما ماه دیگه به دنیا میاید. سال رو اشتباه نوشتید.
  • ... ببخشید!

می خواهیم پردازشگری خودکار داشته باشیم که با گرفتن تاریخ فعلی و تاریخ تولّد، سن فرد رو محاسبه کند و همچنین از یک سری خطا های انسانی جلوگیری کند.

 

 

ورودی

در خط اول تعداد تست ها T (1 ≤ T ≤ 200) می آید و هر یک از T خط بعد این چنین اند: تست با یک خط خالی آغاز می شود و سپس تاریخ فعلی و تاریخ تولد به ترتیب در دو خط می آیند. قالب تاریخ ها به صورت DD/MM/YYYY است. به طوری که DD روز، MM ماه و YYYY سال را نشان می دهند. همه ی تاریخ ها معتبر خواهند بود.

 

 

خروجی

خروجی از یک خط برای هر تست تشکیل شده است که هر یک چنین خواهند بود:

"Case #N: AGE" در حالی که N شماره تست است و AGE یکی از سه حالت زیر خواهد بود.

"Invalid birth date" : اگر سن غیر ممکن است.(در آینده متولد خواهد شد.)

"Check birth date" : اگر سن به دست آمده بیش از 130 است.

سن محاسبه شده به سال : در سایر موارد

 

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

ادامه مطلب...
۱۸ خرداد ۹۱ ، ۰۱:۲۹ ۰ نظر موافقین ۱ مخالفین ۰
سیّد پارسا میرطاهری
دوشنبه, ۸ خرداد ۱۳۹۱، ۰۱:۳۸ ب.ظ سیّد پارسا میرطاهری
Funky Numbers

Funky Numbers

دومین سوال از CodeForces که سوال نخست مسابقه شماره 121 بود.

 

Codeforces Round #121 (Div. 2)

A. Funky Numbers

 

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

اعداد بد بو

اعداد مثلثی اعدادی به صورت به ازای یک عدد طبیعی برای k ، نمایش داده می شوند .

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

در این سوال برنامه شما باید تشخیص دهد که یک عدد بدبوست یا نه!

ورودی

ورودی عدد صحیح  n (1 ≤ n ≤ 109) را در بر می گیرد.

خروجی

اگر n عددی بدبوست، “Yes” را چاپ کنید و اگر این طور نیست، “No” را چاپ کنید.

 

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

ادامه مطلب...
۰۸ خرداد ۹۱ ، ۱۳:۳۸ ۳ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

امکان جدید

سلام!

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

با تشکر خیلی زیاد از علیرضا!

نشانی صفحه رو در زیر می بینید:

http://helli-3.ir/level.php

Level

۲۷ ارديبهشت ۹۱ ، ۲۲:۴۹ ۰ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری

Vasya and the Bus

سلام!

نخستین سوال از CodeForces ، که ازین به بعد احتمالا بیشتر ازش سوال میذاریم...

Codeforces Round #120 (Div. 2)

A. Vasya and the Bus

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

واسیا و اتوبوس

اتوبوسی در شهر برتون وجود دارد. مسافران این اتوبوس به دو دسته بزرگسالان و کودکان تقسیم می شوند و هر بزرگسال می تواند یکی از بچه هایش را رایگان سوار اتوبوس کند و بابت سایر بچه هایش پول بپردازد. به طور مثال بزرگسالی که k بچه دارد، k واحد پول می پردازد. یک واحد برای خودش و (k-1) واحد برای بچه هایش.

 همچنین می دانیم که در برتون هیچ بچه ای نمی­ تواند بدون یک سرپرست بزرگسال سوار اتوبوس شود.

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

ورودی

ورودی شامل یک خط است که دو عدد صحیح n و m (0 ≤ n, m ≤ 105)  را در بر می گیرد که به ترتیب نشان دهنده ی تعداد افراد بزرگسال و کودکان سوار اتوبوس اند.

خروجی

اگر سوار شدن n بزرگسال همراه با m کودک امکان پذیر بود، به ترتیب حداقل و حداکثر پولی که مسافران جمعا ممکن است پرداخت کنند را با یک فاصله چاپ کنید. اگر چنین چیزی ممکن نبود، واژه ی "Impossible" را چاپ کنید.

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

ادامه مطلب...
۲۷ ارديبهشت ۹۱ ، ۲۲:۳۹ ۰ نظر موافقین ۰ مخالفین ۰
سیّد پارسا میرطاهری