Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۸:تئوری نهایی سوم:سوال ۳

عظمت سلطان

به یک بردار در صفحه سلطانی گوییم، اگر Δx و Δy آن اعداد طبیعی باشند. می‌خواهیم تعدادی بردار سلطانی دو به دو ناموازی انتخاب کنیم، طوری که جمع‌شان برداری با Δx=n و Δy=n شود. تعداد روش‌های انجام این کار را Sn در نظر بگیرید. ثابت کنید SnCn است که در آن Cn عدد کاتالان n ام را نشان می‌دهد.

در صورتی که موفق به حل سوال نشدید، می‌توانید با ارائه‌ی الگوریتمی از O(n4) برای یافتن مقدار f(n)، تا حداکثر ۳۰ امتیاز بگیرید.


ابزار صفحه