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

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

يكشنبه, ۲۶ اسفند ۱۳۹۷، ۱۰:۳۷ ب.ظ سیّد پارسا میرطاهری
۱۰ روز بعد، ۱۴ روز قبل

۱۰ روز بعد، ۱۴ روز قبل

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

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

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

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