CodeForces Round #101 Div.2

سوال A. Amusing Joke

سوال میگه تو یه شهری زمان کریسمس ، هر دو نفر که همدیگه رو می بینن ، حروف اسمشون رو روی کارت می نویسن و اونها رو تو ورودی خونه آویزون می کنن .

زمانی که می خوابن ، یه نفر میاد و این حروف رو میاره پایین و جا به جا می کنه ( ممکنه یه کاراکتر حذف بشه و چیزه دیگه ای به جاش بیاد ) و دوباره اونها رو آویزون می کنه .

صبح که بیدار میشن می بینن که حروف به هم ریخته !

اون ها می خوان بدونن با حروفی که الان آویزون شده میشه اسمشون رو دوباره درست کنند یا نه ؟

سوال به عنوان ورودی 3 رشته به شما میده ، رشته اول اسم صاحب خونه ، رشته دوم اسم مهمان و رشته سوم ، حروفی هستند که صبح آویزون هستند .

طول رشته ها حداکثر 100 هستند .

به عنوان خروجی اگر میشه با حروف رشته سوم ، رشته اول و دوم رو ساخت ( با هم ) YES و در غیر این صورت NO رو چاپ کنید .

سوال B. Hopscotch

سوال میگه یه نفر خواب می بینه که داره "لی لی" بازی می کنه .

زمان بازی براش این سوال پیش میاد که اگر سنگ رو پرت کنه تو خونه (x , y ) ، شماره خونه ای که سنگ توش افتاده چنده ؟

همه مربع ها طول برابر a دارند .

اگر سنگ تو یه خونه افتاده بود ، شماره اون خونه چنده ؟

اگر سنگ رو مرز یه خونه باشه ، بیرون خونه فرض میشه .

سوال به عنوان ورودی اعداد صحیح x , y , a رو میده .

x| , y <= 1000000| و a < 100 خواهد بود .

به عنوان خروجی اگر سنگ تو یه خونه افتاده ، شماره اون خونه ، در غیر این صورت -1 رو چاپ کنید .

سوال C. Queue

سوال میگه n نفر تو یه بانک تو صف وایسادن و هر کسی می دونه Ai نفر بلندتر از خودش توی صف جلوتر ازش وایسادن .

کارمند بانک میره ناهار بخوره ، برای همین همه افراد از صف خارج میشن .

زمانی که دوباره کارمند شروع به کار می کنه ، افراد می خوان برگردند سر جای خودشون اما همه افراد یادشون رفته که کجا وایساده بودن . فقط مقدار Ai یادشون میاد .

سوال به عنوان ورودی اسم هر فرد و مقدار Ai رو برای اون فرد میده .

باید به هر نفر یه "قد" نسبت بدید که شرایط مساله حفظ بشه .

n < 3000 , Ai < n-1

به هر نفر باید قد Hi رو نسبت بدید .

Hi باید بین 1 تا 1,000,000,000 باشه .

Hi ها می تونن برابر باشن .

به عنوان خروجی n خط شامل اسم و قد اون فرد رو چاپ کنید .

اگر نمیشه این کار رو کرد ، -1 رو چاپ کنید .

سوال : D. Take-off Ramps

یه مسابقه اسکی برگزار شده که مسیر مسابقه یه خط مستقیم و موازی محور x هاست .

طول مسیر L متر و از 0 تا L تو جهت مثبت محور x خواهد بود .

یه نفر تو مسابقه شرکت کرده که می تونه هر متر رو تو 1 ثانیه طی کنه .

در طول مسیر n تا ramp وجود داره .

i امین ramp تو محل x قرار گرفته .

اگر از Pi متر قبل از i امید ramp دور خیز کنیم ، می تونیم به اندازه Di متر رو بپریم ، این پرش Ti ثانیه طول می کشه .

ramp ها فقط تو جهت مثبت محور x کارایی دارن ، یعنی از X-Pi باید شروع به دورخیز کنیم و از محل X تا X+Di رو بپریم .

سوال میگه کمترین زمانی که میشه کل مسیر رو پیمایش کرد .

در طول مسیر نمیشه به قبل از نقطه شروع رفت .

برای هر ramp می دونیم که X+Di از L بیشتر نخواهد شد .

به عنوان ورودی n , L و مشخصات ramp هارو بگیرید .

به عنوان خروجی کمترین زمان برای طی کردن مسیر و همچنین تعداد ramp هایی که استفاده کردید و شماره ramp هارو چاپ کنید .

سوال E. Clearing Up

سوال میگه 2 نفر میرن مسافرت نوروزی و وقتی بر می گردن به شهرشون ، می بینن که برف اومده و همه جاده ها بسته شده .

تو شهر n تا کلبه وجود داره ، این 2 نفر تصمیم می گیرن برف یه تعداد از این جاده هارو پاک کنن ، به طوری که از هر کلبه فقط بشه با یه مسیر ساده به هر کلبه دیگه ای رفت .

تو شهر 2 نوع جاده وجود داره ، باریک و پهن .

نفر اول فقط می تونه جاده های پهن رو تمیز کنه و نفر دوم جاده های باریک .

این دو نفر می خوان ببینن که میشه این کار رو کرد ، به طوری که تعداد جاده هایی که هر کسی تمیز می کنه ، برابر باشه .

به عنوان ورودی n و m تعداد کلبه ها و تعداد جاده ها رو میده .

تو m خط بعدی ، مشخصات هر جاده رو میده .

n < 1000 , m < 100,000

به عنوان خروجی اگه میشه این کار رو کرد تعداد جاده ها و همچنین شماره جاده ها رو چاپ کنید ، در غیر این صورت -1 رو چاپ کنید .

حل سوالات

سوال اول

میشه مساله رو این طور تغییر داد ، به اندازه حروف رشته اول و دوم ، کاراکتر داریم ، می خوایم رشته سوم رو بسازیم . آیا میشه این کار رو کرد .

در کل وقتی تو یه سوال از شما می خوان که ببینید با یه سری کاراکتر میشه یه چیزی رو ساخت 2 کار می تونید بکنید .

1 - تعداد تکرار های هر حرف رو بشمارید و ببیند که این تعداد تو هر دو رشته یکی هست یا نه .

2 - کاراکتر هارو بریزید تو یه string و هر دو رشته رو sort کنید ، ببینید که 2 رشته یکی هستند یا نه .

بررسی زمان :

تو حالت 1 : هر رشته رو 1 بار پیمایش می کنیم ، در کل میشه O ( N )

تو حالت 2 : رشته اول و دوم رو جمع می کنیم و بعد sort می کنیم ، در کل میشه O ( N log N )

سوال دوم :
چون طول همه مربع ها a فرض شده ، می تونیم بزرگترین عدد k رو پیدا کنیم که k * a < y باشه .
به راحتی میشه دید که k برابر y / a میشه .

این طوری تعیین کردیم که تو کدوم سطح سنگ افتاده .

تو هر سطح 1 یا 2 مربع وجود داره .

اگر K فرد بود یا صفر بود ، 1 مربع و در غیر این صورت 2 مربع داریم .

خیلی راحت می تونیم چک کنیم که سنگ تو مربع (ها) میوفته یا نه ؟

بررسی زمان : O(1)

سوال سوم : 

برای حل افراد رو بر حسب Ai ها مرتب می کنیم .

به هر فرد یه عدد از 1 تا n نسبت میدیم .

افراد رو به ترتیب وارد لیست می کنیم با توجه به اینکه sort کردیم ، افراد به ترتیب قد وارد لیست میشن .

قد فرد i ام رو n - i در نظر می گیریم .

برای اضافه کردن i امین فرد ، عدد n - i رو تو محل Ai از لیست اضافه می کنیم. اگر این محل وجود نداشت ، به تناقض رسیدیم و جواب مساله -1 میشه .

بررسی زمان :

اول ورودی ها رو sort می کنیم و بعد n بار یه عدد رو تو یه لیست اضافه می کنیم .

در کل میشه : O ( N * N )

سوال چهارم :

یه گراف وزن دار از روی مشخصات مساله می سازیم .

در کل بین 0 تا L یه تعداد نقطه برامون مهم هستند ، اسمشون رو event می زاریم .

رئوس گراف این نقاط هستند .

برای هر ramp نقاط x-p و x+d رو به event ها اضافه می کنیم .

همچنین یه یال از x-p به x+d به وزن p+t اضافه می کنیم .( یه طرفه )

در آخر به ازای هر دو event متوالی ، یه یال به گراف اضافه می کنیم ( دو طرفه ) .

به یه الگوریتم shortest path می تونیم جوا مساله رو بدست بیاریم .

مثلا میشه صفر  Dijkstra زد و مسیر رو save کرد .

برای هر یال استفاده می کنیم ، type اون رو هم نگه می داریم .

برای یال های نوع اول ( ramp ها ) type همون شماره ramp می تونه باشه و برای یال های نوع دوم type مهم نیست، می تونیم از -1 استفاده کنیم .

بررسی زمان : ساختن یال های نوع اول و دوم O(E) زمان می بره .

sort کردن event ها ELogE زمان می بره .

Dijkstra رو هم میشه ElogE زد .

در کل میشه : O( E LogE )

سوال پنجم :

اگه خوب توجه کرده باشید ، مساله از شما می خواد ببینید که گراف مساله دارای Minimum Spanning Tree ای هست که تعداد یال های باریک و پهن اون برابر باشه .

چون جواب باید یه درخت باشه که زوج تا یال داره ، n باید فرد باشه .

همچنین حداقل n/2 تا از هر نوع یال نیاز داریم .

یه گراف در نظر می گیریم که توش فقط یال های باریک وجود داره ، سعی می کنیم n/2 تا یال پهن به این گراف اضافه کنیم .

برای این کار از Dis-Joint Set Data Structue استفاده می کنیم .

یال هایی که تو این مرحله اضافه کردیم ،حتما باید توی جواب باشن .

حالا اگه این تعداد کمتر از n/2 بود ، سعی می کنیم یه سری یال پهن دیگه به گراف اضافه کنیم .

برای این کار گراف رو خالی می کنیم ، یال هایی اجباری رو اضافه می کنیم ، تا زمانی که تعداد یال ها n/2 نشده ، به گراف یال پهن اضافه می کنیم .( نباید این یال دور ایجاد کنه )

تا اینجا وضعیت یال های پهن رو معلوم کردیم .

سعی می کنیم به گرافی که تا الان ساختیم ، n/2 تا یال باریک اضافه کنیم ( نباید دور ایجاد بشه ) .

برای این کار هر یال باریک که دور ایجاد نکنه رو به گراف اضافه می کنیم .

در آخر اگر نتونستیم n-1 تا یال انتخاب کنیم ، جواب مساله -1 میشه .

بررسی زمان :

در کل یه بار یال های باریک رو میریزیم تو گراف ، این میشه E log E

بعد یه بار کل یال های پهن چک میشن ، این هم میشه E Log E

بعد گراف حالی میشه و دوباره با یال های پهن پر میشه ، این میشه E log E

حالا یال های پهن رو اضافه می کنیم ، این میشه E log E

تا اینجا وضعیت یال های پهن معلوم شده .

اضافه کردن یال های باریک هم E log E زمان می بره .

در کل میشه : O ( E log E )

کد های من برای سوالات :

سوال اول

سوال دوم

سوال سوم

سوال چهارم

سوال پنجم

موفق باشید