سلام دوست کوئرایی!
در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۵ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.
در روز k \geq 1ام قورباغه به ارتفاع (k - 1)(a - b) + a از چاه می‌رسد و اگر این ارتفاع بیشتر یا مساوی h باشد، از چاه خارج می‌شود. پس از حل نامساوی زیر خواهیم داشت:
a + (a - b)(k - 1) \geq h \Rightarrow
\\
(a - b)(k - 1) \geq h - a \Rightarrow
\\
k - 1 \geq \frac{h - a}{a - b} \Rightarrow
\\
k \geq 1 + \frac{h-a}{a-b}پس کمینه k برابر \lceil\frac{h-a}{a-b}\rceil + 1 است.
به‌عنوان راه دیگر می‌توانستید با ایجاد یک حلقه روی مقدار k، کوچک‌ترین مقدار ممکن که شرط بالا برقرار شود را پیدا کنید.
می‌توان دید که بهتر است ابتدا با افرادی که دوست کمتری دارند شروع کنیم و آن‌ها را به سینما بفرستیم. برای همین بعد از گرفتن دنباله‌ی a_i آن را به شکل صعودی مرتب می‌کنیم. سپس از ابتدای آن شروع کرده و تا زمانی که سینما جا داشته باشد، کارمند را به همراه تمام دوستانش به سینما می‌فرستیم.
برای حساب کردن حداقل تعداد بخش از روش برنامه نویسی پویا استفاده می‌کنیم. در dp_i امکان افراز‌کردن و خواندن i رقم اول شماره تلفن را ذخیره می‌کنیم. به این صورت که اگر خواندن i رقم اول شماره تلفن ممکن نبود، dp_i برابر با ۰ است و در صورتی که ممکن باشد ، dp_i برابر با ۱ است.
این dp به شکل زیر محاسبه می‌شود:
نمایش کد به صورت LTR
dp[-1] = 1
dp[0] = 0
if s[0] == ‘0’ :
dp[1] = 0
else :
dp[1] = 1
که نقش پایه را دارند و:
نمایش کد به صورت LTR
if (s[i – 1] != ‘0’ and dp[i-2]) or (s[i – 2] != ‘0’ and dp[i-3]):
dp[i] = 1
else:
dp[i] = 0
بعد از محاسبه‌ی dp باید ببینیم که dp به چه نحوی محاسبه شده است و جواب را از روی آن به دست بیاوریم.
بعد از محاسبه‌ی dp باید ببینیم که dp به چه نحوی محاسبه شده است و جواب را از روی آن به دست بیاوریم.
اخرین رقم شماره‌تلفن را در نظر بگیرید. می‌دانیم این رقم باید در یک تکه آمده باشد. در صورتی که بتوانیم رقم آخر را در تکه ای با طول ۲ آورده باشیم و بقییه شماره نیز خوانده شود، باید {dp}_{i-2} برابر ۱ باشد. به این صورت که بعد از حذف دو رقم آخر. باید بتوانیم بقییه شماره‌تلفن را بخوانیم.
به همین ترتیب اگر بتوانیم رقم آخر را در یک روش خواندن درست در تکه ای به طول ۳ خوانده باشیم پس باید {dp}_{i-3} برابر ۱ باشد.
پس می‌توانیم از آخر شماره تلفن شروع کنیم و در تعدادی مرحله، در هر مرحله رقم آخر باقی‌مانده از شماره تلفن را در نظر بگیریم و با توجه به {dp}{i-3} و {dp}{i-2} یکی از آن‌ها که برابر ۱ است را انتخاب کنیم و متناظر با آن طول تکه ای رقم آخر را می‌خوانیم مشخص می‌شود. سپس کافی است این ارقام را از آخر شماره‌تلفن جدا کنیم و در مرحله بعد این گام را تکرار کنیم تا ارقام شماره‌تلفن تمام شود.
برای یافتن کوتاه ترین کافی است ابتدای مسیر را به روش حریصانه حساب کنیم. به طور دقیق‌تر اگر x بیشتر از y بود، باید از x دو تا کم کنیم و از y یکی کم کنیم. اگر y بیشتر بود، از y دو تا کم کنیم و از x یک واحد.
البته توجه کنید که اگر در جایی x یا y منفی شد، با توجه با این که جدول تقارن دارد ابتدا قدر مطلق آن‌ها را با خودشان جایگزین می‌کنیم و بعد ادامه می‌دهیم. وقتی که نزدیک مقصد شدیم، به طور دقیق تر وقتی هم x کمتر از ۷ بود و هم y کمتر از ۷ بود حالات را با استفاده از BFS به شکل بهینه محاسبه می‌کنیم.
همه‌ی کامیون‌ها و جاده‌ها را به ترتیب h آن‌ها را از بزرگ به کوچک مرتب می‌کنیم و روی آن‌ها پیمایش می‌کنیم. در ابتدا یک گراف می‌سازیم که هیچ جاده‌ای ندارد. اگر یک جاده و کامیون هم ارتفاع بودند جاده را در این لیست جلوتر از کامیون قرار دهید.
در این پیمایش اگر یک جاده دیدیم آن را به گراف اضافه می‌کنیم. اگر یک کامیون دیدیم می‌پرسیم آیا مسیری در این گراف بین آن‌ها وجود دارد یا نه. برای این که این پرسش‌ها را سریع جواب دهیم از ساختمان داده‌ی DSU استفاده می‌کنیم.
مثال زیر یکی از روش‌های درست است:
x = 2, y = 4, a_1 = 1, a_i = 3 \times 2^{i-1}, \quad i = 2,3, \dots, n
این روش می‌توانید همه‌ی اعداد از ۱ تا جمع اعداد یعنی 3 \times 2^n + 1 را پرداخت کند، برای اثبات بهینه بودن توجه کنید کل تعداد حالت‌هایی که می‌توانیم زنجیرهای همبند بدهیم برابر 3 \times 2^n + n است و هر طوری که شماره‌گذاری کنیم n - 2 مقدار مختلف پیدا می‌شود که به دو روش می‌توان پرداخت کرد. پس حداکثر حالت ممکن همین 3 \times 2^n + 1 است.
جمع‌بندی
در این مطلب تلاش کردیم تا تمامی نکات مربوط به سوالات این بخش از مسابقات را پوشش دهیم. اگر سوال دیگری دارید، حتما آن را در بخش نظرات با ما به اشتراک بگذارید.
باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «مهلا انتظاری» و «رومینا سحری مقدم» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۵.
