خوش آمدید

پليس، دوربين را در پررفت‌وآمدترين شهرها قرار داده است، حال شما بايد شهر يا شهرهايي را پيدا کنيد که بيشترين رفت‌وآمد را دارند. اين شهرها بيشترين ورودي/خروجي را در اتوبان‌ها دارند. مثلا شهر 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));

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