• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ایران‌سرور (IranServer) تصمیم گرفته که برای رونمایی از خدمات جدید خود، یک جلسه مهم میزگردی با حضور مشتری‌های کلیدی‌اش برگزار کند. هدف این جلسه، بحث و بررسی درباره نیازها و تجربه‌های مشتریان است تا تیم ایران‌سرور بتواند خدماتش را بهینه‌تر کند.

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

ایران‌سرور می‌خواهد مشتری‌ها را به شکلی روی دو میز تقسیم کند که:

تصویر

  1. هیچ دو نفری که آشنا هستند، روی یک میز نباشند.
  2. تعداد افراد روی دو میز باید تا حد امکان متعادل باشد تا هر دو میز فرصت برابری برای بحث‌های مفید داشته باشند. (منظور از متعادل این است که اختلاف تعداد افراد روی دو میز کمترین مقدار ممکن باشد!)

جزئیات پروژه

پروژه‌ی اولیه را از این لینک دانلود کنید.

تابع iranServerRoundTable را طوری کامل کنید که خروجی خواسته شده را برگرداند:

<?php

function iranServerRoundTable(int $n, int $m, array $connections): string {
    // TODO
}
PHP
solution.php

ورودی تابع:

  • مقدار n، نشان‌دهنده تعداد افراد حاضر در مهمانی است.
  • مقدار m، نشان‌دهنده تعداد آشنایی‌های قبلی که میان افراد وجود دارد، است.
  • مقدار connections، لیستی از m آشنایی‌ که هر یک به صورت یک جفت مانند [A, B] است که نشان دهنده وجود آشنایی قبلی میان دو فرد A و B است.

خروجی تابع:

  • در صورتی که امکان تقسیم‌بندی افراد بین دو میز مطابق شرایط داده شده وجود داشته باشد، یک آرایه که در آن مقدار کلید possible برابر با "YES" و دو کلید table_1 و table_2 که نشان‌دهنده لیستی از افراد دور هر میز هستند را بازگرداندید.
  • در غیر این صورت، آرایه‌ای شامل کلید possible با مقدار "NO" بازگرداندید.
  • در نهایت خروجی برنامه‌ی شما باید به فرمت JSON باشد.

نکته

مقدار کلید possible در هر یک از شرایط ذکر شده، باید دقیقا به شکلی که نوشته شده است باشد. (بزرگی و کوچکی حروف مهم است!)

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

مثال‌ها

نمونه ورودی ۱:

>>  iranServerRoundTable(6, 6, [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [6, 1],
    ]);
PHP

نمونه خروجی ۱:

{
    "possible": "YES",
    "table_1": [1, 3, 5],
    "table_2": [2, 4, 6],
}
JSON

توضیحات نمونه

این مثال شامل ۶ نفر است که هر یک از آن‌ها دقیقا با دو فرد دیگر آشنایی قبلی دارد؛ به شکل زیر توجه کنید:

تصویر

حال می‌توانیم آن‌ها را به صوزت زیر به دو گروه مجزا تقسیم بندی کرد:

تصویر ۲

Table1:[1,3,5],Table2:[2,4,6] Table_1 : [1, 3, 5], Table_2 : [2, 4, 6]

نمونه ورودی ۲:

>>  iranServerRoundTable(6, 5, [
        [1, 2],
        [3, 4],
        [3, 5],
        [4, 5],
        [1, 6],
    ]);
PHP

نمونه خروجی ۲:

{
    "possible": "NO"
}
JSON

توضیحات نمونه

این مثال شامل ۶ نفر است و رابط آشنایی میان‌ آن‌ها به شکل زیر است:

تصویر

در این مثال نمی‌توان افراد را طوری برا سر دو میز نشاند که شرایط خواسته شده را حفظ کند؛ چرا که در تصویر زیر فرد شماره ۵ را نمی‌توان دور هیچ‌یک از میزها نشاند!

تصویر ۲

نمونه ورودی ۳:

>>  iranServerRoundTable(6, 3, [
        [1, 2],
        [3, 4],
        [3, 5],
    ]);
PHP

نمونه خروجی ۳:

{
    "possible": "YES",
    "table_1": [1, 4, 5],
    "table_2": [2, 3, 6],
}
JSON

توضیحات نمونه

این مثال شامل ۶ نفر است و رابط آشنایی میان‌ آن‌ها به شکل زیر است:

تصویر

یکی از حالات مطلوب جهت تقسیم افراد به دو میز موجود به شکل زیر است:

تصویر ۲

حالت دیگری هم وجود دارد که می‌توان این کار را انجام داد اما با شرط دوم (متعادل بودن میز‌ها) را ندارد!

تصویر زیر یکی از حالاتی است که برای این مسئله موردقبول نیست:

تصویر ۳

آن‌چه باید آپلود کنید

یک فایل PHP با نام solution.php که تابع iranServerRoundTable در آن پیاده‌سازی شده است آپلود کنید.


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.