قرار است پس از برگزاري يکي از مسابقات ACM ضيافت شامي برگزار شود و همه تيم‌هاي شرکت کننده در اين مسابقات به اين ضيافت دعوت شوند. در اين مهماني تعدادي ميز با ظرفيت‌هاي مشخص وجود دارد و تيم‌ها بايد دور اين ميز‌ها بنشينند.

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

اولين خط مساله شامل دو عدد صحيح است که با کاراکتر فاصله (Space) از هم جدا شده‌اند. عدد اول تعداد ميز‌ها و عدد دوم تعداد تيم‌ها را مشخص مي‌کند. خط بعدي شامل يکسري عدد صحيح است که ظرفيت هر ميز را مشخص مي‌کند و با کاراکتر فاصله از هم جدا شده‌اند. خط بعدي تعداد نفرات تيم‌ها را مشخص مي‌کند. تيم‌ها با کاراکتر فاصله از هم جدا شده‌اند.

ورودي‌ها با وارد کردن 0 0‌ خاتمه مي‌يابند.

مساله براي هر آزمون ورودي (كه شامل تعدادي ميز و تيم است که از ساختار گفته شده براي ورودي پيروي مي‌کند) بايد بگويد که آيا امکان دارد اين تعداد تيم روي اين تعداد ميز با اين ظرفيت بنشينند يا خير، اگر اين امر امکان‌پذير است عدد ? را در خروجي چاپ کند و براي هر تيم مشخص که در ورودي آمده‌ است، در خروجي بگويد اين تيم روي کدام ميزها مي‌تواند بنشيند و شماره هر ميز را در خروجي چاپ کند. براي هر تيم يک خط در خروجي چاپ مي‌شود که نشان‌دهنده ميزهايي است که آن تيم روي آن نشسته است. شماره‌ها با يک فاصله از هم جدا مي‌شوند، مانند شکل پايين و اگر اين امر امکان‌پذير نبود در خروجي عدد صفر را چاپ کند.

براي هر ميز يک ساختار در نظر مي‌گيريم، که يک انديس دارد که شماره ميز را مشخص مي‌کند و يک عدد صحيح که ظرفيت ميز را مشخص مي‌کند.

براي هر تيم نيز همين داده‌ها را به‌علاوه يک آرايه از اعداد صحيح که شماره ميز‌هايي که تيم روي آن نشسته را در خود نگه مي‌دارد، موجود است.

نخست تيم‌ها را به‌ترتيب نزولي مرتب مي‌کنيم. براي مثال بالا که ورودي ميز‌هاي ما به‌صورت

4 5 3 5 است تبديل به 5 5 4 3 ‌ مي‌شود، در مرحله بعد براي هر تيم، اول تعداد ميز‌هايي که خالي نيستند را چک مي‌کنيم (يعني حداقل جايي براي نشستن يک نفر وجود داشته باشد) برابر تعداد افراد تيم هست يا خير؟ اگر جواب مثبت نبود عدد نشان‌دهنده اين است که تيم‌ها نمي‌توانند روي ميز‌ها بنشينند به‌طوري که يک نفر از هر تيم روي هر ميز بنشيند. اگر جواب مثبت بود در يک حلقه که به تعداد ميز‌ها اجرا مي‌شود از ظرفيت هر ميز يکي کم مي‌کنيم و اين‌ کار را براي هر تيم انجام مي‌دهيم، قطعه کد زير را ببينيد:

foreach (Team team in teams){

if (tables.Where(t =» t.Capacity != 0).Count() « team.Capacity){

output.Add("0”);

teams.Clear();

break;

}

for (int i = 0; i « tables.Count; i++){

if (tables[i].Capacity == 0)

continue;

tables[i].Capacity--;

team.SitingTable.Add(tables[i].Index);

}

}

همان‌طور که مشخص است اگر تعداد ميزهايي که ظرفيت خالي ندارند از ظرفيت تيم کمتر باشد امکان نشستن افراد آن تيم روي ميز وجود ندارد و از حلقه خارج مي‌شود و عدد صفر در خروجي آورده مي‌شود، اما اگر اين‌گونه نبود از ظرفيت ميز‌هايي که ظرفيت آنها مخالف صفر است يکي کم مي‌شود (ميزي با ظرفيت منفي معنا ندارد) و شماره ميز در SitingTable‌ اضافه مي‌شود، اين آرايه مشخص مي‌کند که هر تيم در کدام ميزها نشسته است. در نهايت براي هر تيم عناصر SitingTable مربوط به آن در خروجي چاپ مي‌شود، عناصر آرايه SitingTable بايد با يک فاصله از هم چاپ شوند. به‌ همان صورت که بالا در خروجي مساله توضيح داده شده است.

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