صلح به زبان الگوريتم

Nنفر ديگر هم در حال گفتگو هستند، اما شما نمي‌دانيد كدام‌يك از آنها متعلق به كدام كشور است. تنها مي‌توانيد مردمي را كه در حال صحبت هستند، ببينيد و با مشاهده رفتار آنها در طي اين گفتگوهاي نفربه‌نفر، مي‌توان حدس زد که آنها دوست هستند يا دشمن؟

همچنين کشور فرد C بايد بداند اين جفت افرادي كه با هم صحبت مي‌كنند هر دو از يك كشور هستند يا دشمن هم هستند. در حالي‌كه صحبت‌هاي آنها شنيده مي‌شود، بايد با توجه به مشاهدات‌تان سوالاتي را كه دولت كشورتان از شما مي‌پرسد پاسخ دهيد.

حالا به‌صورت رسمي‌تر، جعبه سياهي را با عملكرد زير در نظر بگيريد:

setFriends(x,y)

نشان مي‌دهد كه x و y از يك كشور هستند.

setEnemies(x,y)  

نشان مي‌دهد كه x و y از كشورهاي مختلف هستند.

areFriends(x,y)

اگر مطمئن هستيد كه x وy دوست هستند true را برمي‌گرداند.

areEnemies(x,y)

اگر مطمئن هستيد كه x وy دشمن هستند true را برمي‌گرداند.

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

چند نکته وجود دارد که دقت به آنها شما را در حل مساله کمک خواهد کرد.

1- اگر x و y دوست باشند و y و z نيز دوست باشند نتيجه مي‌شود که x و z نيز دوست هستند.

2- اگر x و y دوست باشند، نتيجه مي‌شود که y و x نيز دوست هستند.

3- هر کس با خودش دوست است.

4- هيچ کس با خودش دشمن نيست.

5- اگر x با y دشمن بود و y هم با z دشمن، نتيجه مي‌شود که x و z با هم دوست هستند.

6- اگر x و y با هم دوست باشند و x با z دشمن باشد، نتيجه مي‌شود که y و z نيز دشمن هستند.

7- هيچ‌کس با خودش دشمن نيست.

8- رابطه ? براي دشمن بودن نيز صادق است.

بسيار خب، ورودي‌هاي برنامه ما به‌صورت يك عدد صحيح پشت سرهم است، اولين عدد نشان‌دهنده کد عملياتي است که رابطه بين افراد را مشخص مي‌کند و مي‌تواند يکي از سه عدد زير باشد.

c = 1,setFriends

c = 2,setEnemies

c = 3,areFriends

c = 4,areEnemies

و دو عدد بعدي کد افرادي است که ما بايد رابطه آنها را بررسي کنيم. ورودي‌ها با وارد کردن عبارت

خروجي برنامه بايد براي هر خط ورودي يکي از اعداد

ورودي نمونه:

1 0 1

1 1 2

2 0 5

3 0 2

3 8 9

4 1 5

4 1 2

4 8 9

1 8 9

1 5 2

3 5 2

0 0 0

خروجي نمونه:

1

0

1

0

0

-1

حال بايد روشي بيان کنيم كه بتوان رابطه بين افراد را تشخيص داد، برنامه ما شامل يک ساختار داده به‌شکل زير:

struct person{

int id;

person[] friends;

person[] enemies;

};

و يک آرايه از person با نام people که افرادي که در ورودي آورده شده‌اند را در خود ذخيره مي‌کند، تشکيل شده است.

حال براي هر خط ورودي اولين رقم چک مي‌شود، اگر setFriends يا setEnemies بود دو عدد بعدي در آرايه people جستجو مي‌شوند. اگر وجود داشته‌ باشند رابطه بين آنها چک مي‌شود، اگر با کد عمليات در تناقض بود، عدد

اما اگر عمليات areFriends در فهرست دوست‌هاي اولي فرد دوم را جستجو مي‌کنيم، اگر پيدا شد نتيجه

نمونه کد برنامه را از طريق لينک زير دريافت کنيد: