المپیاد سوالات ترکیبیات و مباحث ویژه !

[daneshvar.amrollahi]

پاسخ : سوالات ترکیبیات

نمونه ورودی اول: 2 خروجی نمون هاول: 1
نمونه ورودی دوم: 5 خروجی نمونه دوم: 12
نمونه ورودی سوم: 6 خروجی نمونه سوم: 36

اگر درست حل کردید، بگید رابطه رو چجوری به دست آوردید. اصلش همونه. چون با چاپ باقی مانده جواب بر 1e9+7 میشه جواب رو ساده کرد.
میگید بازگشتیه یعنی باید n رو کوچیک کنیم دیگه؟ خوب چجوری میشه؟ یعنی از رو کوچک تر ها چجوری بزگرتره رو پیدا کنیم...

 

[The Smith]

پاسخ : سوالات ترکیبیات

نمونه ورودی اول: 2 خروجی نمون هاول: 1
نمونه ورودی دوم: 5 خروجی نمونه دوم: 12
نمونه ورودی سوم: 6 خروجی نمونه سوم: 36

اگر درست حل کردید، بگید رابطه رو چجوری به دست آوردید. اصلش همونه. چون با چاپ باقی مانده جواب بر 1e9+7 میشه جواب رو ساده کرد.
میگید بازگشتیه یعنی باید n رو کوچیک کنیم دیگه؟ خوب چجوری میشه؟ یعنی از رو کوچک تر ها چجوری بزگرتره رو پیدا کنیم...

فقط یه مشکلی هست
این عدد یکی مونده به آخر
از چند تا عدد باید بزرگتر باشه ؟ ۱دونه یا هیچی ؟
ینی اگه فرد تا عدد سمت راستش بود ، از سقف نصفشون بیشتر باشه یا کف نصفشون ؟

 

[daneshvar.amrollahi]

پاسخ : سوالات ترکیبیات

فقط یه مشکلی هست
این عدد یکی مونده به آخر
از چند تا عدد باید بزرگتر باشه ؟ ۱دونه یا هیچی ؟
ینی اگه فرد تا عدد سمت راستش بود ، از سقف نصفشون بیشتر باشه یا کف نصفشون ؟

کف سمت راستش. اگر زوج بود که دقیقا باید از i/2 سمت راستش بیشتر باشه. اگر هم فرد بود همون i/2 تو سی پلاس پلاس جواب میده چون کف میگیره فکر کنم. یعنی مثلا اگر نفر پتجم باشه، باید حداقل از 2 نفر بیشتر باشه.
عدد یکی مونده به آخر تو موقعیت دوم قرار داره. پس باید از حداقل یکی از قبلیاش که اولی هستش، بیشتر باشه. شماره ها از 1 تا N هستند نه 0 تا n-1. فقط عدد آخر میتونه هرچی باشه چون باید از 0/2 بیشتر باشه که میشه صفر.

 

[The Smith]

پاسخ : سوالات ترکیبیات

کف سمت راستش. اگر زوج بود که دقیقا باید از i/2 سمت راستش بیشتر باشه. اگر هم فرد بود همون i/2 تو سی پلاس پلاس جواب میده چون کف میگیره فکر کنم. یعنی مثلا اگر نفر پتجم باشه، باید حداقل از 2 نفر بیشتر باشه.
عدد یکی مونده به آخر تو موقعیت دوم قرار داره. پس باید از حداقل یکی از قبلیاش که اولی هستش، بیشتر باشه. شماره ها از 1 تا N هستند نه 0 تا n-1. فقط عدد آخر میتونه هرچی باشه چون باید از 0/2 بیشتر باشه که میشه صفر.

طبق حرف تو
خروجی اول باید جوابش بشه ۲. نه ۱

 

[daneshvar.amrollahi]

پاسخ : سوالات ترکیبیات

طبق حرف تو
خروجی اول باید جوابش بشه ۲. نه ۱

صورت سوالی که من دارم نگفته کف یا سقف. ولی چون تست کیس خود سوال با ورودی نمونه ۲، جواب ۱ رو داده، پس احتمالا باید سقف منظورش باشه. یعنی مثال ۲ ۱ غلط بشه. که سقف یک دوم بشه ۱ و نفر دوم نتونسته باشه از ۱ نفر قبلی خود بهتر باشه.

 

[The Smith]

پاسخ : سوالات ترکیبیات

دارم سعی میکنم حلش کنم.
دو تا راه حل دارم که یکیش برای یه سریش درست جواب میده
یکیش برای یه سری دیگع

 

[daneshvar.amrollahi]

پاسخ : سوالات ترکیبیات

دارم سعی میکنم حلش کنم.
دو تا راه حل دارم که یکیش برای یه سریش درست جواب میده
یکیش برای یه سری دیگع

من تست کیس ۳ رو اطمینان خیلی خیلی کامل ندارم ولی چون با کدی که اکسپت گرفته، اون خروجی رو میده گذاشتم. یه رابطه براش زده ولی نمی دونم چجوری بهش رسیده...
کدش خیلی اهمیت نداره. بیشتر همون راه حلشه. اصلا فرض کتیم به جای n عدد ۵ گذاشتیم و میخوایم سوال ترکیبیات حل کنیم...
مثال ورودی و خروجی بیشتر بذارم؟

 

[The Smith]

پاسخ : سوالات ترکیبیات

رابطه :

اثباتش رو مطمعن نیستم اصلا.
ولی
توی جایگاه آخر همیشه ۱ هست، چون کوچکترین عدده.
و عدد ۲ هم یا توی خونه ی آخره یا یکی مونده به آخر.
و توی جایگاه اول و دوم ، همیشه عددای بزرگتر مساوی سقف n / 2.
چون اگه غیر از این باشه ، یه عدد کوچیک تر از اون توی خونه ی اول و دوم قرار بگیره ، حتما از نصف اعداد بعدش بزرگتر نیست (چون نصف عددا بزرگتر از n / 2 هستن.)
جایگاه اول رو در نظر نگیر، میشه An-1 و برای اولین خونه هم سقف n / 2 حالت داریم که میشه فرمولی که دادم.
ینی Ai = Ai-1 * n/2 :)

 

[daneshvar.amrollahi]

پاسخ : سوالات ترکیبیات

رابطه :

اثباتش رو مطمعن نیستم اصلا.
ولی
توی جایگاه آخر همیشه ۱ هست، چون کوچکترین عدده.
و عدد ۲ هم یا توی خونه ی آخره یا یکی مونده به آخر.
و توی جایگاه اول و دوم ، همیشه عددای بزرگتر مساوی سقف n / 2.
چون اگه غیر از این باشه ، یه عدد کوچیک تر از اون توی خونه ی اول و دوم قرار بگیره ، حتما از نصف اعداد بعدش بزرگتر نیست (چون نصف عددا بزرگتر از n / 2 هستن.)
جایگاه اول رو در نظر نگیر، میشه An-1 و برای اولین خونه هم سقف n / 2 حالت داریم که میشه فرمولی که دادم.
ینی Ai = Ai-1 * n/2 :)

یک کم فکر می کنم بعد دوباره یه پاسخ خواهم گذاشت

 

[kavian77]

پاسخ : مسابقه ترکیبیات

من چون خودم سوالو تازه فهمیدم ، الآن برات توضیح میدم . سوال میگه یه شکلی که شبیه پله است رو چجوری میشه به مربع هایی افراز کرد . (کمترین مربع )
یعنی این مربع ها فقط 2*2 نیستند ، 1*1 و 3*3 و ... هم میتونن باشن .
[]

سلام به همگی
دوستان نیازی نیست انقدر خودتون رو اذیت کنید .
هر پله ی n*n با یک مربع n-1*n-1 و دو مربع 1*1 پر میشه .
در واقع کمینه جواب 3 می شود .
موفق و سلامت باشید
نظر شخصی ام بود اگه اشتباه کردم خوشحال میشم بفرمائید .