کدام تیم روی کدام میز ؟

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

اولین خط مساله شامل دو عدد صحیح است که با کاراکتر فاصله (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 باید با یک فاصله از هم چاپ شوند. به‌ همان صورت که بالا در خروجی مساله توضیح داده شده است.

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