لینکهای مفید برای شرکت در مسابقه:
میتوانید سوالات خود را از قسمت "سوال بپرسید" مطرح کنید.
سری چهارم راهنماییها به سوالات اضافه شد.
آقا فیروز که بهدلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپنپ کار کند. شهری که آقا فیروز در آن زندگی میکند شامل میدان است که در یک خط راست قرار دارند و به ترتیب از چپ به راست با شمارههای ۱ تا شمارهگذاری شدهاند و در وسط میدان شماره ، مجسمهای با ارتفاع متر وجود دارد.
هر مسافر در برنامه تپنپ درخواستی به صورت میدهد و به این معنی است که میخواهد از میدان به میدان که است، برود.
متاسفانه برنامهی مسیریاب آقا فیروز خراب شده و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد به آقا فیروز میگوید و او به سمت چپ حرکت میکند تا به اولین میدانی برسد که ارتفاع مجسمهاش دقیقا متر باشد. مسافر طوری عدد را میگوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان وجود داشته باشد.
در نهایت وقتی مسافر به مقصد رسید، آقا فیروز به تعداد عددهایی که مسافر به او گفته، از او پول میگیرد و میدانیم مسافرها به گونهای آدرس میدهند که کمترین پول را به آقا فیروز بدهند.
همچنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمیکند و در هر زمان دقیقا یک مسافر میتواند سوار ماشین شود.
آقا فیروز که به پول نیاز دارد، میخواهد ببیند اگر به ازای هر و که است، درخواست را قبول کند، در مجموع چقدر پول بدست میآورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی میگیرد، او از شما درخواست کرده تا شما برایش این مقدار را حساب کنید.
از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده خروجی دهید.
در خط اول ورودی عدد میآید که بیانگر تعداد میدانهای شهر است.
در خط دوم به ترتیب عدد میآیند که برابر با ارتفاع مجسمهای است که در میدان ام قرار دارد.
در تنها خط خروجی، مجموع پولی که آقا فیروز میتواند کسب کند را بگوید.
درآمدی که آقا فیروز به ازای هر درخواست دارد به اینصورت است:
درآمدی که آقا فیروز به ازای هر درخواست دارد به اینصورت است:
مسئله را به شکل زیر به یک گراف راسی تبدیل میکنیم که هر راس نماینده یک میدان است.
راس یالی مستقیم به راس دارد، اگر و تنها اگر و هیچ وجود نداشته باشد به صورتی که و باشد.
در این صورت جواب مسئله برابر با جمع فاصله هر دو راس است. حال سعی میکنیم این مقدار را در گراف ساخته شده محاسبه کنیم.
یالها را برعکس نگاه میکنیم.
اگر کوچکترین عددی باشد که و راسهای تا به راس یال دارند و اگر وجود نداشته باشد راسهای تا به راس یال دارند و اگر یالها را برعکس کنیم راس به همه آنها یال خواهد داشت.
پس یعنی راس به تعدادی از راسهای جلوی خود یال دارد.
تعریف میکنیم: یعنی جلوترین راسی که راس به آن یال دارد.
در اصل راس به تمامی راسهای تا فاصله یک دارد.
ادعا میکنیم مسیر راس به راسهای بزرگتر از از راس میگذرد به صورتی که و بیشینه است.
اولا که ها در واقع اولین مقدار بعد است که $a_r_i = a_i$ است.
بعد از آن طبق ادعای بالا میتوانیم اندیسی که در بالا گفته شده را با استفاده از سگمنتتری به دست آوریم.
سپس از روی مجموع فاصلههای آن اندیس، میتوان فاصلههای جدید را هم به دست آورد.