چگونه از دست دوربین‌‌های‌سرعت‌سنج فرار کنیم؟!

پلیس، دوربین را در پررفت‌وآمدترین شهرها قرار داده است، حال شما باید شهر یا شهرهایی را پیدا کنید که بیشترین رفت‌وآمد را دارند. این شهرها بیشترین ورودی/خروجی را در اتوبان‌ها دارند. مثلا شهر A پنج ورودی و خروجی دارد و شهر B چهارتا. در این دو مورد می‌توان بااطمینان گفت که دوربین در شهر A وجود دارد و همین‌طور اگر Nشهر دیگر را نیز با هم مقایسه کنیم دوربین در شهری قرار دارد که بیشترین ورودی و خروجی را دارد.

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

پس از آن نام شهرها خط‌به‌خط وارد می‌شود و سپس یک عدد صحیح مثبت که تعداد مسیرها را مشخص می‌کند، بعد از آن نیز برای هر مسیر در ورودی نام دو شهر که مبدا و مقصد مسیر را مشخص می‌کند (که با کاراکتر فاصله از هم جدا شده‌اند، کاراکتر صفر نشان‌دهنده پایان خروجی‌های برنامه است)، وارد می‌شود.

برای هر آزمون ورودی عبارت زیر باید داده شود:

City map «mapnum»: «foundCity» camera(s) found

عبارت mapnum نشان‌‌دهنده شماره آزمون است و عبارت foundedCity نشانگر تعداد شهرهایی است که دوربین در آنها قرار دارد.

پس از این عبارت نام شهر یا شهرهایی که دوربین در آنها وجود دارد، در خروجی چاپ می‌شود.

5

guanabarabay

downtown

botanicgarden

colombo

sambodromo

4

guanabarabay sambodromo

downtown sambodromo

sambodromo botanicgarden

colombo sambodromo

0

City map #1: 1 camera(s) found

sambodromo

روش حل همان‌طور که در بالا توضیح داده شد، به‌صورت یک زوج مرتب از شهرهاست و طبق بیان مساله دوربین در شهری قرار دارد که بیشترین ورودی و خروجی را دارد. حال برای حل مساله یک ساختار داده‌ای به‌صورت زیر تعریف می‌کنیم.

struct City

{

public string CityName;

public IList«string» Input;

public IList«string» Output;

public City()

{

Input = new List«string»();

Output = new List«string»();

}

}

اینک یک آرایه از ساختار بالا تعریف می‌کنیم به‌اسم Cities که شامل شهرهایی است که در صورت مساله ذکر شده است. حال در این آرایه به ازای هر خط ورودی که کاربر وارد می‌کند دنبال شهر مورد نظر می‌گردیم به‌صورت زیر:

if (Cities.Where(c =» c.CityName == cityname).Count() != 0)

{

//TODO Add input/output to city

}

else

{

//TODO Add City to Cities

}

بسیار خب این عمل تا زمانی ادامه پیدا می‌کند که همه ورودی‌های مساله را کاربر وارد کرده‌ باشد.

درنهایت باید اطلاعات ذخیره شده در Cities را مورد بررسی قرار دهیم تا شهری که بیشترین ورودی و خروجی را دارد مشخص شود. اول از همه بیشترین مقدار ورودی و خروجی را حساب می‌کنیم، یعنی برای همه شهرها تعداد ورودی به‌علاوه تعداد خروجی را حساب می‌کنیم. این عدد مشخص می‌کند که بیشترین ورودی و خروجی را چه شهرهایی می‌توانند داشته ‌باشند، یعنی اگر مجموع ورودی و خروجی شهری برابر عدد حاصل بود دوربین در آن شهر قرار دارد و اطلاعات مربوط به آن شهر باید در خروجی ذکر شود. حال برای پیدا کردن شهرهایی که مجموع ورودی و خروجی آنها برابر عدد فوق باشد به‌صورت کد زیر عمل می‌کنیم.

int maxIO = Cities.Max(c =» c.Input.Count + c.Output.Count);

var result = Cities.Where(c =» (c.Input.Count + c.Output.Count) == maxIO);

مقدار result شهرهایی را مشخص می‌کند که بیشترین ورودی و خروجی را دارند و فقط کافیست اطلاعات این result را با توجه به فرمت خروجی که در بالا ذکر شده است نمایش دهیم. اما روشی دیگر و ساده‌تر برای حل این مساله استفاده از Dictionary است. هر عنصر در دیکشنری یک کلید دارد که نام شهر است و یک مقدار که برابر مجموع ورودی و خروجی آن شهر است.

اگر شهر در دیکشنری وجود نداشت آن‌را اضافه کرده و مقدار آن‌را برابر 1 می‌کند و اگر وجود داشت مقدار آن‌را یک واحد می‌افزاید و باز به‌همان روش بالا مقدار شهری که بیشترین ورودی و خروجی را دارد پیدا کرده و در خروجی چاپ می‌کند. کد آن به‌صورت زیر است:

var result = Cities.Where(city =» city.Value == Cities.Max(c =» c.Value));

امیربهاالدین سبط الشیخ