X-( X-( X-( X-(
منظریم فکر کردن senator77 تموم شهبه نقل از m.m.r :آغا چرا اینجا مگس هم نمیپره؟
)
اول رفع ابهام: مسیری به طول 3، از 2 یال و 3 رأس تشکیل شده است.به نقل از صبهان :من یه سوال بگم
یه گراف جهت دار داریم که حداقل درجه راس های اون n / 2 ه. ثابت کنید این گراف یه مسیر به طول ۳ داره .
یه نمونه ی ورودی بده .به نقل از daneshvar.a :
فقط یه مشکلی هستبه نقل از daneshvar.a :
کف سمت راستش. اگر زوج بود که دقیقا باید از i/2 سمت راستش بیشتر باشه. اگر هم فرد بود همون i/2 تو سی پلاس پلاس جواب میده چون کف میگیره فکر کنم. یعنی مثلا اگر نفر پتجم باشه، باید حداقل از 2 نفر بیشتر باشه.به نقل از صبهان :فقط یه مشکلی هست
این عدد یکی مونده به آخر
از چند تا عدد باید بزرگتر باشه ؟ ۱دونه یا هیچی ؟
ینی اگه فرد تا عدد سمت راستش بود ، از سقف نصفشون بیشتر باشه یا کف نصفشون ؟
طبق حرف توبه نقل از daneshvar.a :
صورت سوالی که من دارم نگفته کف یا سقف. ولی چون تست کیس خود سوال با ورودی نمونه ۲، جواب ۱ رو داده، پس احتمالا باید سقف منظورش باشه. یعنی مثال ۲ ۱ غلط بشه. که سقف یک دوم بشه ۱ و نفر دوم نتونسته باشه از ۱ نفر قبلی خود بهتر باشه.به نقل از صبهان :
من تست کیس ۳ رو اطمینان خیلی خیلی کامل ندارم ولی چون با کدی که اکسپت گرفته، اون خروجی رو میده گذاشتم. یه رابطه براش زده ولی نمی دونم چجوری بهش رسیده...به نقل از صبهان :دارم سعی میکنم حلش کنم.
دو تا راه حل دارم که یکیش برای یه سریش درست جواب میده
یکیش برای یه سری دیگع
یک کم فکر می کنم بعد دوباره یه پاسخ خواهم گذاشتبه نقل از صبهان :رابطه :
اثباتش رو مطمعن نیستم اصلا.
ولی
توی جایگاه آخر همیشه ۱ هست، چون کوچکترین عدده.
و عدد ۲ هم یا توی خونه ی آخره یا یکی مونده به آخر.
و توی جایگاه اول و دوم ، همیشه عددای بزرگتر مساوی سقف n / 2.
چون اگه غیر از این باشه ، یه عدد کوچیک تر از اون توی خونه ی اول و دوم قرار بگیره ، حتما از نصف اعداد بعدش بزرگتر نیست (چون نصف عددا بزرگتر از n / 2 هستن.)
جایگاه اول رو در نظر نگیر، میشه An-1 و برای اولین خونه هم سقف n / 2 حالت داریم که میشه فرمولی که دادم.
ینی Ai = Ai-1 * n/2 :)
سلام به همگیبه نقل از mhjh :