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

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 چاپ شود. برای دو رابطه دوم اگر درست باشد 1 و اگر غلط باشد 0 راچاپ کند.

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

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

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

خروجی برنامه باید برای هر خط ورودی یکی از اعداد 0 و 1 و -1 را چاپ کند که نحوه به‌‌دست آوردن آن‌را بالا توضیح داده‌ایم.

ورودی نمونه:

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 جستجو می‌شوند. اگر وجود داشته‌ باشند رابطه بین آنها چک می‌شود، اگر با کد عملیات در تناقض بود، عدد -1 در خروجی چاپ می‌شود (چک کردن این رابطه در پایین توضیح داده خواهد شد)، اگر حداقل یکی از آنها در آرایه وجود نداشت، فردی که وجود نداشته در آرایه قرار می‌گیرد و مقدار friends و enemies براساس کد عملیات مقدار‌دهی می‌شود. برای مثال اگر کد عملیات 1 باشد دو فرد با هم دوست هستند و دوست‌های اولی دوست‌های دومی و دشمن‌های اولی دوست‌های دومی هستند و همین‌طور برعکس.

اما اگر عملیات areFriends در فهرست دوست‌های اولی فرد دوم را جستجو می‌کنیم، اگر پیدا شد نتیجه 1 را بر می‌گرداند و اگر یافت نشد 0 را، برای areEnemies هم به‌ همین طریق عمل می‌کنیم با این تفاوت که به‌ جای گشتن دوست‌ها، دشمن‌ها را جستجو می‌کنیم. برای زمانی‌که دو فرد در فهرست موجود بودند با توجه به کد عملیات مانند بالا عمل خواهیم کرد.

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