Statistics

Problem Statement for "PerfectlyFairGame"

Problem Statement

Dick and Jane are playing a simple game with darts and a board displaying a grid of squares, represented by the String[] board. Each square contains a number from 0 to 9. They each take turns (starting with Dick) tossing a dart at the board. They earn as many points as the number they hit, or 0 points if they miss the board. After each has thrown darts times, the player with the most points wins. If the points end up tied, a fair coin is flipped to determine the winner.


Dick and Jane are equally skilled players, but they are not perfect. If they are aiming at a particular grid square, they actually have a uniform chance of hitting any number in the 3x3 block surrounding it. (They will never aim at a grid square on the edge of the board, since missing is counterproductive.)


Both players play to maximize their odds of winning. Calculate the chance that Jane will win. Since the game is fair and the players are equally skilled, this shouldn't be too hard... right?

Definition

Class:
PerfectlyFairGame
Method:
winChance
Parameters:
String[], int
Returns:
double
Method signature:
double winChance(String[] board, int darts)
(be sure your method is public)

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • board will contain between 3 and 20 elements, inclusive.
  • Each character in board will be a digit between '0' and '9', inclusive.
  • Each element of board will contain between 3 and 20 digits, inclusive.
  • Each element of board will contain the same number of digits.
  • darts will be between 1 and 20, inclusive.

Examples

  1. {"123","456","789"}

    10

    Returns: 0.5

    The odds are even, of course.

  2. {"55555","55555","55555","55555","55555"}

    20

    Returns: 0.5

    Everyone scores 5 points each throw. Still even. Duh.

  3. {"0909","9090","0909","9090"}

    20

    Returns: 0.5

    Yawn. Still even. Have you moved on to the Medium yet?

  4. {"888","808","888","000","000","999","999"}

    1

    Returns: 0.537037037037037

    Still ev- ... wait a second. That can't be right, can it?

  5. {"29368","65609","67539","57982","71709"}

    5

    Returns: 0.5440401329247544

    admins: Hi, could you please fix the 250's example output?

  6. {"4225271513","8352579454","1582795371","3365182453","7374843700","3262631490","5261771017","5124728129","1537793032","1147236439"}

    20

    Returns: 0.5055321764007881

    Sigh.

  7. {"38781255087057389229","71818099848135169739","70158439879609782870","37482761692403900498","28620532624108926764","68882982602801208544","09509647302012032178","11812043887075071645","76789733023131583913","70355547284173182633","86639132068891549933","99482787310376868410","09092561614810657542","64563623053044291028","19641429963839465817","46702114144532146358","01630217244603937070","43595761239447961054","41277104494022071883","30889761027659323567"}

    20

    Returns: 0.5080271708145212

  8. {"43568","59536","01646","39155","99723"}

    1

    Returns: 0.5925925925925926

  9. {"43568","59536","01646","39155","99723"}

    20

    Returns: 0.5241473083667294

  10. {"29368","65609","67539","57982","71709"}

    1

    Returns: 0.5802469135802468

  11. {"29368","65609","67539","57982","71709"}

    20

    Returns: 0.5246589132188183

  12. {"444444","555555","666666","888888","888888","888888","999999","000000","999999","666666","555555","666666","999999","000000","888888"}

    2

    Returns: 0.5432098765432098

  13. {"41168472940887861066","86898128667817118646","24188767796881186981","80106848161288639236","67669683146876696711","67901846679924216199","92489616734866717631","36649649714173966626","93798861142094806497","61649690064810118269","97997841166679168134","17998106086610361494","01816991626976947167","89176716264164696796","26111214776246392899","79741776189699660187","67864862991167149299","69799882169118960146"}

    2

    Returns: 0.5114311842706903

  14. {"7997334722347452917","4299797897989991775","7448288732718391323","1998979722297899997","8432777339959577933","5942458822292828253","9837887419733721455","3847449732347278934","7745223211972298241","4443777929812739141","3499919993137279294","4999977597791892251","4294949211452492947","2719452775521479371","7593737743995529899","7711393477479297578","3273432979424242971","7377473239989998294","2724742449429497739","2929982818929979237"}

    19

    Returns: 0.5034737119025441

  15. {"36612261834280918613","81184884141606688802","28072637421671872761","06403008617390381011","91162761800346718781","06941042071041203770","90071138223900684218","82118020488688628170","78307028911401088660","70029166002127171728","82148147920121841016","11114121689802840770","72218649171880042430","11601094008161490010","98988049420991127998","90169810334181807270","82681660610241669006","02816670114706931281","00188966878410188078"}

    15

    Returns: 0.511271970489545

  16. {"88980177052824650908","08590325088289529899","45809599670055566328","58888195460896585085","88495855805968949517","97958992826999882350","88880689738952992795","34218558504970060380","59650829979806020979","39908220781585180212","25478260952068260229","02640505284915879288","42995974275687999095","46098430584529688245","79405049170008876269","89920882088880809990","38968288850850646557","98497907516660048235"}

    13

    Returns: 0.5052151203825985

  17. {"7413411422051724935","4940733132808973459","1942257575511752745","5492449986630077275","7479002184557929719","3415491972577844757","5245297947204270195","5537254577512285595","2591734025304544178","2542442112729172950","3712292547277718644","0502454274299520737","7251179440777559791","0449576522452996128","7446529903979047557","7772992470172334597","5271418279944754019","4949447910791717425"}

    18

    Returns: 0.519609418807921

  18. {"020220206320207062","700022922012026907","322266609220730279","737010316996710232","622073247207623272","432134204023687130","622233707061673077","302666260223322273","227926294762209909","232007724107721760","729192022606781092","932422002222070473","233002222727732336","722220209920672643","761892036212219776","302267222240011782","332921222326292282","636704121209727613","622287227972137022"}

    20

    Returns: 0.5117478268809392

  19. {"833383386826836326","662823336333866862","223322668663363323","233323688833322632","328838238832332233","233326663232363636","862388226363288283","263688383323288823","322363863263632663","868268383823338328","663882323228322286","823283223382286328","363333328888238322","668383838623233863","386233268332333662","223332363232363682","362833633683633333","332366332888633263","333326682833383236"}

    18

    Returns: 0.4999999999999998

  20. {"10011106111011160661","11616611610660011011","01111111111111601016","11111111101011101601","11011111016061616001","16061111661000611166","11006006110010000116","61611061101011011611","61000611100101100116","61111111111161111111","61061161116060011110","10111606006011011116","10111101601001066601","01111111116111111001","11111011111011100066","16100016610011110016","01111111611110111611","60100111110111001000"}

    13

    Returns: 0.4999999999999998

  21. {"7157793599979759157","5313719133315397577","3517371553737353971","3577733173715199157","7953517355111311773","3713597779797973713","1911755515197115157","7715979797133919193","1933977731315371715","1137191913553511173","9135553735751373519","7757755797913155753","9597573317539377537","1737593775355373713","7975599935755919155","3777335753531375337","1553351791557351315","5379779915971931791","5371799931373555913","7393731531559339151"}

    15

    Returns: 0.5090469942658762

  22. {"00000","03450","05340","03340","00000","00000","00080","00000","08000","00000","00000","00666","00060","00000","00000","07770","00000","00000","00090"}

    20

    Returns: 0.5412185540570573

  23. {"00000","03450","05340","03340","00000","00000","00080","00000","08000","00000","00000","00666","00060","00000","00000","07770","00000","00000","00050"}

    20

    Returns: 0.540946981165757

  24. {"00000","03450","05340","03340","00000","00000","00080","00000","08000","00000","00000","00666","00060","00000","00000","07670","00000","00000","00090"}

    20

    Returns: 0.5388421758688373

  25. {"00000","03450","05340","03340","00000","00000","00080","00000","08000","00000","00000","00656","00060","00000","00000","07770","00000","00000","00090"}

    20

    Returns: 0.5362094894371761

  26. {"00000","03450","05340","03340","00000","00000","00080","00000","07000","00000","00000","00666","00060","00000","00000","07770","00000","00000","00090"}

    20

    Returns: 0.5391848720930439

  27. {"000","000","900"}

    20

    Returns: 0.5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: