Problem Statement
You and your friends have recently started playing the game of Mafia. In this game, play goes as follows:
- The players are divided into two groups at the start of the game: the Mafia, and villagers. The identities of the Mafia are unknown to the villagers.
- When there are an even number of players, it is the "night". During the night, the Mafia secretly select a person who is removed from the game.
- When there are an odd number of players, it is the "day". During the day, the players select the most guilty person and remove that person from the game.
- If at any time, there are no Mafia remaining in the game, the game is over, and the villager team wins.
- If at any time, there are no villagers remaining in the game, the game is over, and the Mafia team wins.
- During the night, the Mafia selects a person to remove from the game. This causes all of the players' guilts to change. If player i was removed, then the j-th character in responses[i] corresponds to the change in guilt for player j. Specifically, if this is a lowercase letter ('a'-'z'), the guilt is decreased by 1-26, respectively. If this character is an uppercase letter ('A'-'Z'), the guilt is increased by 1-26, respectively. See example 0 for clarification.
- During the day, the players select the player with the highest guilt among those players still in the game. This player is removed from the game. If there is a tie among guilty people, the player with the lowest index is removed from the game. Players removed from the game during the day do not change the players' guilts.
Definition
- Class:
- Mafia
- Method:
- play
- Parameters:
- int[], String[], int
- Returns:
- int
- Method signature:
- int play(int[] guilt, String[] responses, int playerIndex)
- (be sure your method is public)
Constraints
- guilt will contain between 1 and 16 elements, inclusive.
- Each element of guilt will be between 300 and 800, inclusive.
- responses will contain the same number of elements as guilt.
- Each element of responses will contain exactly N characters, where N is the number of elements in guilt.
- Each character in responses will be a letter ('A'-'Z', 'a'-'z').
- playerIndex will be between 0 and N-1, inclusive, where N is the number of elements in guilt.
Examples
{500,500,500,500}
{"ADCb", "bADC", "CbAD", "DCbA"}
1
Returns: 2
With 4 players, this game starts out at night. If you remove player 0 from the game, the guilts of the living players will now be: Player | Guilt -------+------ 1 | 504 2 | 503 3 | 498 The villagers will remove player 1 (you) from the game, causing you to lose. Alternatively, by removing player 2 from the game first, the guilts will be: Player | Guilt -------+------ 0 | 503 1 | 498 3 | 504 The villagers will remove player 3 from the game, and during the next night the Mafia will remove player 0 from the game to win. Thus, there are two nights in the game.
{500,500,500,500,501}
{"ADCbE", "bADCE", "CbADE", "DCbAE", "EDCbA"}
1
Returns: 2
With an odd number of players, the game starts during the day. The most guilty player is player 4, so he is removed from the game. Play then proceeds as in example 0.
{500,500,500,500,500,500}
{"cccccc", "BBBBBB", "dddddd", "FFFFFF", "GGGGGG", "hhhhhh"}
0
Returns: 1
Due to tie-breaks, you will be removed from the game during the first day, with only 1 night.
{501, 499, 499, 499}
{"ABCD", "zfAg", "ESAS", "atsm"}
0
Returns: 2
{800}
{"E"}
0
Returns: 0
{643,457,642,710,595,631,566,634}
{"APOSIfjf", "ewFOJWeJ", "jElLLoSS", "GeOSSmff", "zWSTsOuu", "fmfOPPsa", "MSoPPWXn", "FeojwFAM"}
5
Returns: 3
{643,457,642,710,595,631,566,635}
{"APOSIfjf", "ewFOJWeJ", "jElLLoSS", "GeOSSmff", "zWSTsOuu", "fmfOPPsa", "MSoPPWXn", "FeojwFAM"}
5
Returns: 3
{547,393,781,790,416,765,705}
{"eBwTTIm","PYPwjcJ","fEeJYNe","KzaxVFU","rjUckkx","EOWvFjh","AZvbtdd"}
1
Returns: 3
{554,460,715,702,761,670}
{"SarsvS","NhIizk","WVBxrB","ZLYXVL","EjgycP","LmRslJ"}
1
Returns: 3
{356}
{"l"}
0
Returns: 0
{751}
{"Z"}
0
Returns: 0
{428,790,450}
{"mRb","vGn","aeV"}
2
Returns: 1
{627,529,733,356,600,330,405}
{"ZuUkYDJ","krAoSLI","yOFKbhV","QllkKHB","kHEkJIL","vvAynMC","LbBxiLD"}
1
Returns: 3
{750,606,637,419,329,486,488,601,446}
{"ZfgGKNVet","kpaKsOXWV","YyWqHcVqc","oCXvgBjTP","vMqYxVAhT","WBVDRINRF","CYmluNwBu","JhyLxLwWa","lXgMajIyZ"}
8
Returns: 4
{683,746,534,670,499,436,605,459,756,542,357,670,324,645}
{"iXIfpiSVyjgbiE","ouImHKfHiKHBhO","ZZLIBWvNrAofeN","gNkVsMdboieNCX","JHHDCvXXTjyusA","jeRMgPsXPoCfbV","dhRdfNPgHWPNqC","UjwwKZRaFClgTF","pqQkIFfqVmvPWH","xPBKIpEQUJUjxN","XgxNZvAdGfuSoY","xYmpNlhqCOoILQ","xOXaxUYizVTlue","vFmhaqVjhVsoPv"}
9
Returns: 7
{660}
{"r"}
0
Returns: 0
{366,314,377,494,780,734,763,571,410,795,640,318,531,638,662}
{"siweefbDkmhWknV","VsomDfjvXfQjJDc","wpEmPpIGuEwJpWz","xEQFmTmIsblEmhL","klJuTbYPkOhpwts","DvqaSAlVPGoWQqi","rXxrGmrffvLOdKi","spLGkVMnVphOzZj","jPMTXbylHFgIzYI","DEWMEkvOaRWOecv","bfZDCyMerxeonXK","KztPyHtOYakHGqK","kMWxDGTOwQUFSGU","RDzVnpFfPfAnYJw","hGOtXcMdEnkgeqB"}
8
Returns: 7
{329,582,521,389,358,676,561,793,348,310,566,699,301,594,515,723}
{"oeBdfwhLuNyBrnkd","YOJBPgZqTJYzIRKh","LWDfrkSWgfoycweU","vqdfpHHurxgmCFCc","QCXPKTBXhKBbyVOu","BdYawCkvBuqoLtBE","VPbYkFksBBNADbco","zivzpIwWQyVYFLAH","SNxQKqbkuZFlSIxF","OrbuxZIPYJRisicb","nORWuhtFPeyoiFEX","WSaXPjJuYgekLyBN","UnheqJNctkydBnSI","DvyQVLbjqafFlhpq","uUGAPmLSbyRQUeUp","KSenbwyGywlnooOw"}
9
Returns: 8
{640,446,434,446,750,760}
{"ULnTvp","tcjIbD","YjAWKI","aRSWcF","uufCoO","POxhCL"}
0
Returns: 3
{403,779,725,301}
{"lqXO","CvTl","MStm","DKEL"}
2
Returns: 2
{503,551,323}
{"GBO","LRg","Qsy"}
0
Returns: 1
{777,440,385,364,497,475}
{"fqSvLz","ZdyWaq","FaiJgk","WIUUjz","mpUszn","EXzPln"}
5
Returns: 3
{671, 456, 724}
{"teB","FGZ","abc"}
0
Returns: 1
{403,320,592,369,498,443,518}
{"pXcVGEC","XEApDeG","wgWUihL","zrAayUv","uelDQSe","WEKrofH","hrmsqIg"}
4
Returns: 2
{515,393,529,395,425,649,590,517,753,553,334}
{"mqRAdbHULUN","yjTIpouwruN","OTCzQjxzwGA","EiNLcHshYbp","lJrjsMDRSSu","UbRXquWFHDx","hYvJjKQpYDh","RLAsoHgljYE","KfsXVfdgXfZ","wLIXpgdNuzO","pEebffRiiEm"}
10
Returns: 5
{580,778,473,774,608,434,592,739,503,371,421,406,389}
{"PZgLUnZyZLFVF","RzxLGkNYUqQKu","qaFZaTyTxQBeT","UpdhoulbGzben","wJXEQaOjDvhUj","QmAZoLucyRRbT","CRkNYjhbIqtRN","qBNFfKaOpVxJg","DatAsZaggcYRM","afVFWGFprGiiR","JjaRaGORLWGQb","MRhVwjyHFCdOR","MsXOKAlGtaebH"}
4
Returns: 5
{685,357,417,570,335}
{"yrIme","kwCxZ","esttA","WDVDo","nxcPP"}
4
Returns: 2
{475}
{"m"}
0
Returns: 0
{693,683,734,572,411,793,397,577,702,376}
{"QeBQlAEKkn","RYxvSkIAMx","EgmuUKlmpQ","kUAoRfbtXL","lrYcteVnKh","rZhGtnURRk","iKcWMxabDf","RjfCEeeUDP","SaSloHYDtn","uYUNNOwhmu"}
9
Returns: 5
{432,442,401,664,388,325,423,462,729,444,523,359}
{"qQjPRJwZcdNl","tLJiSPsYsLFz","gbLuTPTNIFOR","npWiAIiVhoNV","DDcTklmJpuhZ","BhHfPyazLeTS","ROqvVSKEoqlt","MUyEQwSwXUCd","kRcQUXzACelB","GnPQdqdjxybn","ZDJHcIcESjfp","IzfquYipHOYs"}
1
Returns: 6
{686,605,793}
{"DQv","LNj","pSs"}
0
Returns: 1
{569,570,528,480,420}
{"lNxwA","Bepsl","EzQon","zsKkP","tRjuS"}
4
Returns: 2
{319,580,676,349,633}
{"MxyPc","WYwDH","bqKOD","PQCgj","jeWxZ"}
2
Returns: 0
{798,793,759,630,581,694,472,568,696,470,779,313,326,597,686,332}
{"NIWLRRCurjiAkypT","miezcEvtIZbacBAr","iZEYtcSgFNAuDmyA","ffYGwlMfiswRgBrx","VUVuTRErXEzncGYG","vhkApWknabllOXwn","iPDMefAZfqsDcFZH","EFTucXrRQHWBkxwR","gzOwYzbEXqbyalHd","IjJBVHCaMJdmOHFV","ZOjKNfElRdwlqNxG","uJmCNGSHbWMMiynu","pdrNMsyVnofZmpLh","RmuvkDjeknFQyWyl","jCmtQMKGkpKUZvXL","MbubuwtTjbDBQWtF"}
2
Returns: 5
{478,588,669,759,345,794,516,342,654,306,332,465,554,633,387}
{"puPwxDPDTxZbmNP","IvRHZHFLHponuGj","SlilWnFUTYiCZrF","inrwBKoLVzqTOFp","YdGZhCyFmOJPgPE","nDLvXowZGLcPKwa","AARTailcpUqyvbQ","WxVKbiGfumrSZyl","szfxJIdHRqgmheA","yrxiISymwdVdKXS","NhJTEnBVOrpKQCs","QbnoDBIUOtdPpsn","EwiTgqCMTstabXP","HhxEUNPNNDpVvry","CNLaNLWPsRDhIBR"}
1
Returns: 7
{740,561,575,456}
{"NcCP","HBTO","LrqH","GSUd"}
3
Returns: 2
{399,575,775,310,460,625,705,689}
{"hgjuHsSO","CTmdTTzF","MfuMUERj","SihrSetp","acFDkWBb","HEfJiFdB","KnOzDigq","OVRbCUcp"}
6
Returns: 4
{346,342,695,557,559,605,379,759,392,594,553,674,695}
{"tAzOTjADWSzoc","sfhKMgIiHpQfz","pZpDsPxbDMGah","rdpWfhKdOWFXa","flWOVqHVXvGCZ","ssmtyxfulygxQ","EOGcoDQocbKHr","yBoVTIvxAOEJF","xcrSlIkdMtRCr","YBGKvGpOfTzaC","JYjPiuZYYnbTC","rOKOasChMuMEp","sPyCiXIqlzimf"}
12
Returns: 3
{624,593,349,307,749,464,735,563,311,530,705,345,513,352,724}
{"fQxZqRmUtdrMveb","AhdcbzMqQRTFrsE","nhVYTdjwOGyJvgj","lEFisazNnEJSUxa","wdmjewNanrmOMGn","oTDxzSDykRWSiFC","yzXBVmvPUvyjCqR","fAPwBgUFDCIwujJ","khpktOtHGpcgicB","ouJUHgLQkOtlZjP","KuvnJqSujwJQrtD","kgDNUqMLRcexTGX","pwzACqPgRdFDYmI","RSUjFBoUjyYUhxD","pORHAKQtcqsrJGo"}
3
Returns: 7
{569,554,494,526,670,552,479,515,313,545,677,303}
{"vusviBhVLqpB","EAgKUeqxhtSs","yrXYFROybgPk","LGUofpjIocRR","apxWdNzsCpft","ZoOzvpwqVFhf","jmlDQKzBihAR","LqkmbNdrdzwz","GkVsZnYpWPFR","yIeudjTKXyTL","VqgUNeJXWzvN","VpJlzJNbohAA"}
0
Returns: 5
{704,537,538,692,668,537,626}
{"iGHkxBo","DJxDemk","sBzYCvo","QiIOCWQ","FhIVfYd","LqjCwoA","wfGwznA"}
4
Returns: 2
{487,727}
{"SP","XR"}
1
Returns: 1
{377,407,498,310,677,652,608,670,498,381,611,429,625,421,600,375}
{"ErXwBQbwYrCLlkIZ","iwFMNjkwQXNEdQFM","FnXHESthgwCmecKD","LJzaMemIiPXSvRzo","cfsPRwRcurtKzpqy","KrglEEjgwPZRmlCm","uwpCNhEcnLjWYZSw","KHYrCkouwvXpFhuR","aQWxmGUZvxjZWnau","VKVUznxSgHUVSiKH","eNLtlRvEidNTzAPV","FOmSHFYNnVvztjVs","qioUYcujJNnGYuMZ","gFlMjKBARhmzzWdl","JdpsDUJiXKjtaxTq","DHoJDDyjnDXLVOwv"}
2
Returns: 8
{525,352,734,518,775,562,483,318,511,492,316,495,458,332,615}
{"vOTKXjfoASVTYMY","dafDJeNUhFFxCMm","ZqtFAeGyLzjhstg","dHankeHLTdLbNQK","gRnJozhyQOkXWzD","VTfhIVcMvNCVctC","CqurLZFllcCPQkz","qKNqzeelCLzZzyK","WFHfCHAnEHgDbAq","LNDtcMLsuLIkuPv","WBiFzdcuDvjjvNO","EslhbLDMMSGifnz","zsxZrCcKLSCmNir","kUAxdNzByHeKLMS","canczUTMBqkHBBA"}
14
Returns: 6
{486,692,456,724,408,546,565,532,337,659,307,799,763,371,493,644}
{"hTGRGMbhGnMiJLQa","eZIijWnYeVzAFvcd","zNUJBpUWQpholgAJ","mzdCwJTDthLEAFBV","cLhwAdEecxwdBTqv","QtNldYlzDnqzmmUS","nfCmZUgFFHYwozqK","sXJHLIMbOfYGOEHD","qrrcKoPbFInVVDHB","ImblLGBRKONxKkvG","hMQCUaUqqOPUypvU","geUEoWTjORaAgLdI","lVCJqFeCiFucSWmW","jZahVLAmCkQExDlX","zKShmVzrrUgGOrCI","eVmvBeUFfNBcasNP"}
4
Returns: 8
{407,327,355,469,622,313}
{"JEMmJG","nYaPBc","xGbTit","egIVlC","RRWWVt","MArNrV"}
1
Returns: 3
{586,394,427,713,419,693,707,641}
{"FLGrKOes","QMUJtdNW","GpcQBrdi","xcTtYRUC","Ephbcquo","mLfifhbq","oqrfzOjR","IcXFyybx"}
3
Returns: 3
{300,300,300,700,700,700}
{"fgfaZZ","fgfZZa","fgfZaZ","aaaZaa","zzzZzz","zzzZzz"}
4
Returns: 3
{300,300,300,300,300,300}
{"ZZaZzz","ZZaZZZ","ZZaaAA","eeeeee","ffffff","gggggg"}
3
Returns: 3
{800,800,800,800,800,800,800,800}
{"zzzzzzzZ","zzzzzzzZ","aaaaaZZa","aaaaaaZZ","aaaaaZaZ", "zzzzzzzZ","zzzzzzzZ","aaaaaaZZ"}
7
Returns: 3
{800,800,800,800,800,800,800,800}
{"ZZaZzzzD","aZZGzYzz","ZaZZzzzz","eeeeeeee","eeeeeeee","eeeeeeee","eeeeeeee","eeeeeeee"}
3
Returns: 4
{800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800}
{"AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA"}
7
Returns: 8
{800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800}
{"AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA"}
6
Returns: 7
{800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800}
{"AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","AAAAAAAAAAAAAAAA","zzzzzzzYAAAAAAAA","zzzzzzYCAAAAAAAA","zzzzzZACAAAAAAAA","zzzzZAACAAAAAAAA","zzzZAAACAAAAAAAA","zzZAAAACAAAAAAAA","zZAAAAACAAAAAAAA","AAAAAAAAAAAAAAAA"}
7
Returns: 8
{643, 457, 642, 710, 595, 631, 566, 634 }
{"APOSIfjf", "ewFOJWeJ", "jElLLoSS", "GeOSSmff", "zWSTsOuu", "fmfOPPsa", "MSoPPWXn", "FeojwFAM" }
5
Returns: 3
{800 }
{"E" }
0
Returns: 0
{399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399, 399 }
{"AaBbCcDdEeFfGgHh", "ZzXxVvDdFfGgHhYy", "RrTtHhUuJjIiOoPp", "kKuUiIlLfFnNdDeE", "AaBbCcDdEeFfGgHh", "ZzXxVvDdFfGgHhYy", "RrTtHhUuJjIiOoPp", "kKuUiIlLfFnNdDeE", "AaBbCcDdEeFfGgHh", "ZzXxVvDdFfGgHhYy", "RrTtHhUuJjIiOoPp", "kKuUiIlLfFnNdDeE", "AaBbCcDdEeFfGgHh", "ZzXxVvDdFfGgHhYy", "RrTtHhUuJjIiOoPp", "kKuUiIlLfFnNdDeE" }
1
Returns: 8
{643, 457, 642, 710, 595, 631, 566, 634, 643, 457, 642, 710, 596, 631, 566, 632 }
{"APOSASKjklsawIoA", "APOSASKjklsawIoA", "AbsakluauiyqwAQu", "mdkslajkalwAKJsH", "ASsamdnjkaHKJAhQ", "fmfOPPsafmfOPPsa", "MSoPPWXnMSoPPWXn", "FeojwFAMFeojwFAM", "APOSIfjfAPOSIfjf", "ewFOJWeJewFOJWeJ", "jElLLoSSjElLLoSS", "GeOSSmffGeOSSmff", "zWSTsOuuzWSTsOuu", "fmfTPPsafmfOPPsa", "MSoQPWXnMSoPPWXn", "FeoSwFsaFeojwFAM" }
5
Returns: 8
{642, 710, 595, 631, 566, 634, 457, 642, 710, 595, 631, 467, 563, 666, 555, 456 }
{"aposLFJFaposLFJF", "EWfojwEjaposLFJF", "JeillOssaposLFJF", "ZwstsOUUaposLFJF", "fmfoppSAaposLFJF", "msOPPWXnaposLFJF", "fEOJwFamaposLFJF", "gEosswffaposLFJF", "ZwstsOUUaposLFJF", "fmfoppSAaposLFJF", "msOPPWXnaposLFJF", "fEOJwFamaposLFJF", "aposLFJFaposLFJF", "EWfojwEjaposLFJF", "JeillOssaposLFJF", "gEosswffaposLFJF" }
4
Returns: 8
{501, 499, 499, 499 }
{"ABCD", "zfAg", "ESAS", "atsm" }
0
Returns: 2
{300, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800 }
{"zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ", "zZZZZZZZZZZZZZZZ" }
0
Returns: 8
{400, 300, 800, 341, 398, 678, 734, 398, 543, 333, 763, 333, 444, 555, 666, 543 }
{"ADCbLLLLLLLLLLLL", "bADCLLLLLLLLLLLL", "CbADLLLLLLLLLLLL", "DCbALLLLLLLLLLLL", "kacdLLLLLLLLLLLL", "AEDFLLLLLLLLLLLL", "DFDFLLLLLLLLLLLL", "QWERLLLLLLLLLLLL", "DFDDLLLLLLLLLLLL", "CVBNLLLLLLLLLLLL", "IOERLLLLLLLLLLLL", "POIULLLLLLLLLLLL", "FGJKLLLLLLLLLLLL", "LKASLLLLLLLLLLLL", "FDFDLLLLLLLLLLLL", "ASaaLLLLLLLLLLLL" }
7
Returns: 8
{300, 400, 500, 600, 700, 800, 301, 302, 303, 304, 302, 401, 304, 400, 312, 333 }
{"aNgUlDliDyemxpgD", "aNgUlDliDyemxpgD", "aguguDliDyemxpgD", "aNgUlDliDyqexpgD", "aguUlDliDyemxfgD", "aNgUlDliDlllxpgD", "aNgUlDliDyedxpgD", "LPLUlSliDyemxpgD", "aNgUlDliDyemxpgD", "aNgUlDliDyFmxpgD", "aNgUlDliDyemxpgD", "aNgUlDliDyemxpgD", "TTttlDliDyemxpgD", "aNgUlKlopyelxpgD", "alkRTggiDyemxpgD", "wNgUlDliDyemcpgD" }
7
Returns: 8
{500, 500, 500, 500 }
{"Aaaa", "aAAA", "aaaA", "AAaa" }
1
Returns: 2