آرش با دوستش
قرار است به يک مسافرت بروند، دوست آرش
راننده خوبي نيست و هيچوقت سرعت مجاز در اتوبانها را رعايت نميکند و
هميشه جريمه ميشود. در طول سفر آنها چند دوربين سرعتسنج پليس قرار دارد.
آرش به دوستش توصيه کرده طوري رانندگي کند که کمتر جريمه شود و به او گفته
بهخاطر اينکه نميتواند سرعت مجاز را رعايت کند، بكوشد از مسيرهايي که
احتمال دارد دوربين سرعتسنج پليس وجود داشته باشد، حرکت نکند. حالا ما
بايد به آرش و دوستش کمک کنيم تا از مسيري حرکت کنند که احتمال وجود دوربين
پليس کمتر باشد!
اما دوربين کجاست؟
پليس، دوربين را در
پررفتوآمدترين شهرها قرار داده است، حال شما بايد شهر يا شهرهايي را پيدا
کنيد که بيشترين رفتوآمد را دارند. اين شهرها بيشترين ورودي/خروجي را در
اتوبانها دارند. مثلا شهر 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));
اميربهاالدين سبط
الشيخ