می
ﺧﻮاﻫﯿﻢ یک ﺷبکه
ی اﺟﺘﻤﺎعی ﺷﺎﻣﻞ n ﻧﻔﺮ ﮐﻪ از ٠ ﺗﺎ n − ١ ﺷﻤﺎره
ﮔﺬاری ﺷﺪه
اﻧﺪ اﯾﺠﺎد ﮐﻨﯿﻢ. ﺑﺮخی از اﻓﺮاد اﯾﻦ ﺷبکه ﺑﺎ یکدیگر دوﺳﺖ ﻫﺴﺘﻨﺪ. اﮔﺮ ﺷﺨﺺ x ﺑﺎ ﺷﺨﺺ y دوﺳﺖ ﺑﺎﺷﺪ، ﺷﺨﺺ y ﻧﯿﺰ ﺑﺎ x دوﺳﺖ ﺧﻮاﻫﺪ ﺑﻮد.

اﻓﺮاد در n ﻣﺮﺣﻠﻪ ﺑﻪ ﺷبکه اﺿﺎﻓﻪ می ﺷﻮﻧﺪ، ﮐﻪ اﯾﻦ ﻣﺮاﺣﻞ ﻧﯿﺰ ﺑﻪ ﺗﺮﺗﯿﺐ از ٠ ﺗﺎ n − ١ ﺷﻤﺎره
ﮔﺬاری ﺷﺪه
اﻧﺪ. ﺷﺨﺺ i در ﻣﺮﺣﻠﻪ
ی i اﺿﺎﻓﻪ می
ﺷﻮد. در ﻣﺮﺣﻠﻪ
ی ٠، ﺷﺨﺺ ٠ ﺑﻪ ﻋﻨﻮان ﺗﻨﻬﺎ ﻓﺮد ﺷﺒکه اﺿﺎﻓﻪ می
ﺷﻮد. در ﻫﺮ یک از n − ١ ﻣﺮﺣﻠﻪ
ی ﺑﻌﺪی، یک ﻓﺮد ﺗﻮﺳﻂ یک ﻣﯿﺰﺑﺎن ﺑﻪ ﺷﺒکه اﺿﺎﻓﻪ می
ﺷﻮد، ﮐﻪ اﯾﻦ ﻣﯿﺰﺑﺎن می
ﺗﻮاﻧﺪ ﻫﺮ ﺷﺨﺺ از اﻋﻀﺎی ﻓﻌلی ﺷﺒکه ﺑﺎﺷﺪ. در ﻣﺮﺣﻠﻪ
ی ٠ < i < n) i)، ﻣﯿﺰﺑﺎن آن ﻣﺮﺣﻠﻪ می ﺗﻮاﻧﺪ ﺷﺨﺺ ﺗﺎزه
وارد iرا با یکی از ﺳﻪ ﭘﺮوﺗکل زﯾﺮ ﺑﻪ ﺷﺒکه اﺿﺎﻓﻪ ﮐﻨﺪ: • IAmYourFriend: ﺷﺨﺺ i را ﺑﺎ ﺷﺨﺺ ﻣﯿﺰﺑﺎن دوﺳﺖ می ﮐﻨﺪ.

• MyFriendsAreYourFriends: ﺷﺨﺺiرا ﺑﺎ ﺗﻤﺎم اﺷﺨﺎصی ﮐﻪ در آن ﻟﺤﻈﻪ ﺑﺎ ﻣﯿﺰﺑﺎن دوﺳﺖ
اﻧﺪ، دوﺳﺖ می ﮐﻨﺪ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ اﯾﻦ ﭘﺮوﺗکل ﺷﺨﺺ i را ﺑﺎ ﺧﻮد ﻣﯿﺰﺑﺎن دوﺳﺖ نمی
ﮐﻨﺪ.

• WeAreYourFriends: ﺷﺨﺺ i را ﺑﺎ ﻣﯿﺰﺑﺎن و ﺗﻤﺎم اﺷﺨﺎصی ﮐﻪ در آن ﻟﺤﻈﻪ ﺑﺎ ﻣﯿﺰﺑﺎن دوﺳﺖ
اﻧﺪ، دوﺳﺖ می
ﮐﻨﺪ.

ﺑﻌﺪ از ﺳﺎﺧﺖ ﺷﺒکه می
ﺧﻮاﻫﯿﻢ ﯾک ﻧﻤﻮﻧﻪ از اﻓﺮاد را ﺑﺮای ﻧﻈﺮﺳﻨجی اﻧﺘﺨﺎب ﮐﻨﯿﻢ، اﯾﻦ ﻧﻤﻮﻧﻪ ﯾک زﯾﺮﻣﺠﻤﻮﻋﻪ از ﮐﻞ اﻋﻀﺎی ﺷﺒکه اﺳﺖ. از آن
ﺟﺎیی ﮐﻪ دوﺳﺘﺎن ﻣﻌﻤﻮﻻ ﻋﻼﺋﻖ ﻣﺸﺘﺮکی دارﻧﺪ، در اﯾﻦ ﻧﻤﻮﻧﻪ ﻧﺒﺎﯾﺪ ﻫﯿﭻ دو ﻓﺮدی ﮐﻪ ﺑﺎ ﯾکدﯾگر دوﺳﺖ
اﻧﺪ، اﻧﺘﺨﺎب ﺷﻮﻧﺪ. ﻫﺮ ﻓﺮد یک ﺿﺮﯾﺐ اﻃﻤﯿﻨﺎن دارد ﮐﻪ ﺑﻪ ﺻﻮرت یک ﻋﺪد ﺻﺤﯿﺢ ﻣﺜﺒﺖ ﻧﺸﺎن داده می
ﺷﻮد. می
ﺧﻮاﻫﯿﻢ ﻧﻤﻮﻧﻪ
ای را ﺑﯿﺎﺑﯿﻢ ﮐﻪ ﺑﯿﺶ
ﺗﺮﯾﻦ ﻣﺠﻤﻮع ﺿﺮﯾﺐ اﻃﻤﯿﻨﺎن را داﺷﺘﻪ ﺑﺎﺷﺪ.

متن کامل سوال