{"trustable":true,"prependHtml":"\u003cstyle\u003e.statText pre { font-size: 12px; }\ntable {display:block !important; width:100%; }\ntable tbody {display:block !important; width:100%; }\ntable tbody tr { width:100% !important;display: block;}\ntable tbody tr td.statText { margin-left: 5px; display: inline-block; width: fit-content; }\ntable tbody tr td.statText br { display: block; content: \" \";line-height: 12px;margin: 12px 0;}\ntable tbody tr td.statText table table pre {\n white-space: pre-wrap;\n text-overflow: ellipsis;\n word-break: break-all;\n}\ntd { padding: 0 !important; border: none !important; }\npre { line-height: normal; margin: 0; }\n\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\n \n \t\t\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eProblem Statement\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cp\u003e\nThere are \u003cb\u003eN\u003c/b\u003e cats sitting around a circle.\nThe cats are numbered 0 through \u003cb\u003eN\u003c/b\u003e-1 in clockwise order.\nNote that as they sit around a circle, cat \u003cb\u003eN\u003c/b\u003e-1 is adjacent to cat 0.\nThe cats are playing a game and the winner will get a prize!\n\u003c/p\u003e\n\n\u003cp\u003e\nThe game looks as follows:\n\u003c/p\u003e\u003cul\u003e\n\u003cli\u003eThere is a single ball. Initially, cat 0 holds the ball.\u003c/li\u003e\n\u003cli\u003eIn each round of the game, the cat who currently holds a ball flips a biased coin. The coin will come up heads with probability \u003cb\u003ep\u003c/b\u003e/1,000,000,000 and tails with probability 1-(\u003cb\u003ep\u003c/b\u003e/1,000,000,000).\u003c/li\u003e\n\u003cli\u003eIf the coin came up heads, the current cat will hand the ball to the next cat clockwise, otherwise the current cat will hand the ball to the next cat counterclockwise. Formally, if the current cat is cat j, heads means that the ball goes to cat (j+1) mod \u003cb\u003eN\u003c/b\u003e and tails means that it goes to cat (j-1) mod \u003cb\u003eN\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eThe game is played until each cat held the ball at least once. The cat who holds the ball at the end of the game is the winner.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\nIn other words, the winner is the last cat to touch the ball.\nNote that cat 0 holds the ball at the beginning, and this does count as holding the ball.\nHence, if there is more than one cat, cat 0 can never win the game.\n\u003c/p\u003e\n\n\u003cp\u003e\nCat \u003cb\u003eK\u003c/b\u003e wonders what is the probability that she will win the prize.\nYou are given the ints \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eK\u003c/b\u003e, and \u003cb\u003ep\u003c/b\u003e.\nReturn the probability that cat \u003cb\u003eK\u003c/b\u003e wins.\n\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eDefinition\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eClass:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eCatsOnTheCircle\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eMethod:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003egetProb\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eParameters:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eint, int, int\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eReturns:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003edouble\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eMethod signature:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003edouble getProb(int N, int K, int p)\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e(be sure your method is public)\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eNotes\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eYour return value must have an absolute or relative error smaller than or equal to 1e-6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eConstraints\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cb\u003eN\u003c/b\u003e will be between 3 and 1,000,000,000, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cb\u003eK\u003c/b\u003e will be between 1 and \u003cb\u003eN\u003c/b\u003e-1, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cb\u003ep\u003c/b\u003e will be between 1 and 999,999,999, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eExamples\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e0)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e300000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.6999999999999985\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eThis game has \u003cb\u003eN\u003c/b\u003e\u003d3 cats, labeled 0, 1, 2.\nWe have \u003cb\u003ep\u003c/b\u003e\u003d30,000,000, hence the coin will come up heads with probability 30,000,000/1,000,000,000 \u003d 0.3 and tails with probability 0.7.\nThe game can look as follows:\n\u003col\u003e\n\u003cli\u003eCat 0 is given the ball.\u003c/li\u003e\n\u003cli\u003eCat 0 flips the coin. The coin comes up tails.\u003c/li\u003e\n\u003cli\u003eCat 0 hands the ball to cat (0-1) mod 3 \u003d cat 2.\u003c/li\u003e\n\u003cli\u003eCat 2 flips the coin. The comes up tails again. \u003c/li\u003e\n\u003cli\u003eCat 2 hands the ball to cat (2-1) mod 3 \u003d cat 1.\u003c/li\u003e\n\u003cli\u003eAt this moment, each cat has held the ball. The game ends and cat 1 gets the prize.\u003c/li\u003e\n\u003c/ol\u003e\nThis particular sequence of events has probability 0.7*0.7 of occuring.\nIt can be shown that the probability that cat 1 wins the game is 0.7.\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e1)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e500000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.2\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eThe coin that is flipped will come up heads with probability 1/2, and tails with probability 1/2. \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e2)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e500000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.2\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e3)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e666666666\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.00391389439551009\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e4)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e999999999\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e999999996\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e777777777\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.05830903870125612\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e5)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e1000000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e300000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 0.044981259448371\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e6)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e534428790\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e459947197\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e500000000\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: 1.871156682766205E-9\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003chr\u003e\u003cp\u003eThis 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. \u003c/p\u003e\n \n "}}]}