Statistics

Problem Statement for "SlotMachineHacking"

Problem Statement

A slot machine (also known as a fruit machine, a one-armed bandit, and under many other names) is a gambling device. You play the game by inserting a coin and pulling a lever. Once you do so, the machine will spin several reels. On each of the reels there are pictures of various pieces of fruit. When the reel stops spinning, exactly one of these fruits is shown to the player.

Thus, once all reels stopped spinning, the player now sees a sequence of fruits. If these form some special pattern (e.g., all of the same kind), the machine pays out a corresponding prize.

In this problem we are only interested in the biggest prize, called the jackpot. The jackpot is paid out if the player gets a cherry on all reels at once. There is exactly one cherry on each of the reels.


Majk has been observing one such slot machine for some time.

For each of its reels he has written down the sequence in which fruit appears on the reel. You are given this information in the String[] reels. Each element of reels is a string that describes one of the reels. The individual characters of that string represent the various fruits, in the order in which they appear on the display as the reel rotates. (Obviously, the reel is cyclic, so when it spins, after the last fruit comes the first one again.)

The character 'c' represents the cherry, other characters are other fruits.


After observing the machine for some time, Majk came up with an important observation: it's actually completely deterministic! Whenever a player pulls the lever, each of the reels rotates by a pre-determined number of steps. This number may be different for different reels but for each individual reel it remains the same for all pulls of the lever.

Majk has determined these numbers of steps. You can access them in the int[] steps. Each time the lever is pulled, the reel described by reels[i] is rotated by steps[i] steps.


The slot machine currently isn't being played. Its reels are currently rotated so that for each reel the character at index 0 is the one currently shown on the display.

Majk would like to win the jackpot. He does not want to waste his money to play other games, so his plan is to wait until the jackpot should appear and only play that one game on the slot machine.

Calculate and return X: the smallest possible non-negative integer such that if Majk waits for X games (i.e., lets other people play the slot machine X times) and then plays one game, he will win the jackpot. Return -1 if such an X does not exist.

Definition

Class:
SlotMachineHacking
Method:
win
Parameters:
String[], int[]
Returns:
int
Method signature:
int win(String[] reels, int[] steps)
(be sure your method is public)

Constraints

  • reels will have between 1 and 5 elements, inclusive.
  • Each element of reels will have between 1 and 10 characters, inclusive.
  • Each character in reels will be a lowercase English letter ('a'-'z').
  • Each element of reels will contain exactly one 'c'.
  • steps will have the same number of elements as reels.
  • Each element of steps will be between 1 and 10^9, inclusive.

Examples

  1. {"abc", "acb", "cab"}

    {32, 31, 30}

    Returns: 0

    This slot machine currently shows "aac" (apple, apple, cherry) on its display. When you pull the handle, the first reel will spin by 32 steps, the second one by 31 steps and the third one by 30 steps. Once that happens, all three reels will show a cherry and the machine will pay out the jackpot. Majk should play it immediately.

  2. {"abc", "acb", "cab"}

    {30, 33, 300000006}

    Returns: -1

    This slot machine is rigged. After each spin it returns to exactly the same position. The jackpot is never paid out.

  3. {"abc", "bac", "abpc"}

    {1, 1, 1}

    Returns: 10

    The slot machine currently shows "aba". After the first game it will show "bab", after the second game "ccp" (cherry-cherry-peach, almost the jackpot but not quite), after the third game the display will show "abc", and so on. Eventually the jackpot will come.

  4. {"aac", "aac", "aaac"}

    {1, 1, 1}

    Returns: 10

    This is the same slot machine as in the previous example. The only difference is that on this one all fruits that are not cherries are apples. This has no influence on the answer.

  5. {"c", "c", "ababcbabab", "c"}

    {470, 4700, 47002, 470000}

    Returns: 1

    Three of the four reels always show a cherry. We win the jackpot as soon as the remaining wheel shows a cherry too.

  6. {"ca", "caba"}

    {1, 2}

    Returns: 1

    The machine just paid out a jackpot and we missed it. The optimal solution is to let someone else play once (they will get "ab") and then to play and win another jackpot.

  7. {"ca", "cab"}

    {2, 3}

    Returns: 0

  8. {"fc","acjddzwfvq","c"}

    {777236131,587001531,9809443}

    Returns: 0

  9. {"fiijjcgiwk","zcklmu","c"}

    {105169865,389595011,621000791}

    Returns: 4

  10. {"kcrxibauh","zscpmik","klwcpl","ncizr"}

    {407879374,521192988,587191333,511648896}

    Returns: -1

  11. {"mwzocz","bxaqlics","chu","tc"}

    {566292667,421294033,116055548,286544299}

    Returns: -1

  12. {"c","esqowcy","hcmhjgllq","tkc"}

    {931030469,942251503,667919251,251793814}

    Returns: -1

  13. {"rcepwkp"}

    {657829699}

    Returns: 3

  14. {"kcm","lelhacwrff","cmhzt","rcxgqfljm","bcjrm"}

    {378160093,854968509,355526282,179226443,496671191}

    Returns: -1

  15. {"cvggoxkvbb"}

    {601508805}

    Returns: 1

  16. {"wmoch","nc"}

    {576767594,799221061}

    Returns: 6

  17. {"pfmvcnxerj","akscezn","wscwdx"}

    {273090582,226141679,311090681}

    Returns: 51

  18. {"vpcmgavw","hcqfgjgzop"}

    {132981065,182265407}

    Returns: -1

  19. {"hfcjlj","kqzvcz","bzczkyvbdw","yzehfwcgyz"}

    {4793408,670493113,149346960,798054734}

    Returns: -1

  20. {"dcdhngxsn"}

    {92381311}

    Returns: 0

  21. {"krzcvhh","ecjjafnuad","bhc","ch"}

    {383493615,31925669,423641320,670770888}

    Returns: 58

  22. {"ijxujobmpc"}

    {67053697}

    Returns: 6

  23. {"hci","hqldzcxksr","cl"}

    {256607957,906858948,929270384}

    Returns: -1

  24. {"cj","eec"}

    {925852343,373997696}

    Returns: 3

  25. {"ckxivsm"}

    {688723785}

    Returns: 6

  26. {"cu","eambcf","lmmvsjjcx"}

    {468195243,726055963,781439378}

    Returns: -1

  27. {"c","c","cm","cf"}

    {358312656,845870446,810271074,201299072}

    Returns: 0

  28. {"cjhbjriu","hatvcmpew","c","sucus"}

    {143462529,480391205,661634890,855177132}

    Returns: 295

  29. {"cpfrffsmho","nbhiodcqdu","jecnzx"}

    {473746334,929842811,898059515}

    Returns: -1

  30. {"co"}

    {219823445}

    Returns: 1

  31. {"hupqrzc","c"}

    {571556810,400151438}

    Returns: 0

  32. {"adwc","csqrqp","ujzqwklcdm","eovc"}

    {547838933,373515541,40598037,952049657}

    Returns: -1

  33. {"zbpcz"}

    {497583524}

    Returns: 1

  34. {"neofsc","dypqclv","ckie","fcbflnt"}

    {774867577,794438710,796228455,914960510}

    Returns: -1

  35. {"xgocxtewl","teqtrjmtzc","fknhzlqyzc","ict"}

    {662212724,520043732,963663276,866417029}

    Returns: -1

  36. {"zpfmgzcq","hnfaskcp","wzmcotg","cv"}

    {881244447,956590931,365287555,727704975}

    Returns: 49

  37. {"cos","wchbatooaf","vyci","gbcj","csr"}

    {989045510,190822316,606252559,993325838,244278499}

    Returns: -1

  38. {"jmaxxcuxiw","myhznnc","dnvc","kkeorc","nlvuozdrc"}

    {572360429,241576537,312392337,269443405,750581443}

    Returns: 574

  39. {"wmcupgmamr","yoaorpuwmc","cvhh"}

    {409898426,696906124,24998315}

    Returns: -1

  40. {"cfp","mceuxxv","ekfpacreb","umrxekvc","wapc"}

    {284356843,822699845,63742694,81519489,541236527}

    Returns: -1

  41. {"jhpafcizv","xulyuimwqc"}

    {914027477,547139921}

    Returns: 18

  42. {"nzpuc","xkcjynmasy","ecdgbgpz","xcapbubf","zcagp"}

    {259903772,195834967,389412331,247206991,991686713}

    Returns: -1

  43. {"c","c","ocfmj"}

    {487591578,487750167,56806494}

    Returns: 3

  44. {"cdg"}

    {266158027}

    Returns: 2

  45. {"vgkjckq"}

    {481412042}

    Returns: 2

  46. {"lyyciova","vcjnogoaj","mciw","cnbg","nkcxxu"}

    {672987831,101020613,850625277,279436855,556755569}

    Returns: -1

  47. {"scnye","c"}

    {648388737,982778185}

    Returns: 2

  48. {"zcpwayego","ucmmhzn","ibcizp","ngqpunqcyo","gqsxcd"}

    {192270658,844502692,189381671,654959071,601999445}

    Returns: -1

  49. {"ipgyykc","pcznwpwv","zdljftddc","jcfbgk"}

    {271125098,430168721,343942784,982086239}

    Returns: -1

  50. {"dftcn","iqocqa","pbuoecwiy"}

    {371797147,89760091,535993289}

    Returns: -1

  51. {"mcsuwoh","rjpydonlcu","cyyatoh"}

    {306762032,745304563,280681363}

    Returns: -1

  52. {"vicmyepj","mcwrvkiu"}

    {536220191,411516943}

    Returns: -1

  53. {"oqacfreaok","nbtcvhkbx","ncqla"}

    {736662057,393837977,906430370}

    Returns: -1

  54. {"hsufcg","iwmfgicmq"}

    {70802935,207625628}

    Returns: -1

  55. {"nqihcq","hapzbcj","nxjdzivcuu","ghdkdtfsc"}

    {364707773,585987425,798255605,114938111}

    Returns: -1

  56. {"jdotcuw","boyscsi","ktcrtswtn","mmcvojez","cgjnbo"}

    {376513443,819631327,275478583,10155155,593916635}

    Returns: -1

  57. {"ogjcgtstv","rwdhc","lyxcswknyk"}

    {517031727,831896542,514805274}

    Returns: -1

  58. {"bcbbb","lacidngtx","ucqljn","gypjxfchk"}

    {926796726,23044475,65053483,650577806}

    Returns: -1

  59. {"cukwkm"}

    {17742397}

    Returns: 5

  60. {"hocmnvr","qolggcro","whbcfxeb"}

    {398039652,777436845,628517517}

    Returns: -1

  61. {"hjnrcm","nvkmrhuwcn"}

    {811870055,277548716}

    Returns: 7

  62. {"scavkst","clavyzmd"}

    {979446764,112322229}

    Returns: 31

  63. {"yvertrcuqy","ckhnq","avctbt","cwdyfk"}

    {77974722,982773216,262086706,726624787}

    Returns: -1

  64. {"jxzecsis","wpcywj","fbawcnx","cyjxyuz","cgiofhqmx"}

    {366298957,81435419,667150431,367121134,367238888}

    Returns: -1

  65. {"tzgdlauco"}

    {268399390}

    Returns: 3

  66. {"cfduwa","ecoihg","rbqlaclwo","syenceh"}

    {650029267,174904829,989003389,316783867}

    Returns: -1

  67. {"clvoinim"}

    {168415525}

    Returns: 7

  68. {"xfciuwb"}

    {622681491}

    Returns: 5

  69. {"cwaotf","ijybc","zrdaoc","jkoncjqxjl","pvfclsaip"}

    {730964528,985398974,741074732,361716933,433132623}

    Returns: -1

  70. {"nutmscqgtk","eeckfjtv","gcusvd"}

    {534360401,751862505,533138315}

    Returns: -1

  71. {"cakud","kcdsir"}

    {214271582,415205170}

    Returns: -1

  72. {"gndfhcytu","mncstbwxw","cywqbsuqjt"}

    {801566119,271586749,324208623}

    Returns: 49

  73. {"tgcgyvyjfq","htfscq","upyojncp","aclskv"}

    {776016599,978868013,226191144,661605763}

    Returns: -1

  74. {"yixoqmcr","clxwg","cavus","iuuyaic"}

    {64354593,124537346,854283121,654989799}

    Returns: 149

  75. {"casghghly","ljkcasfy","fmnwspzc","uchvdl","qaicanlj"}

    {18690800,423912562,760621009,913862323,43585656}

    Returns: -1

  76. {"ckkasxjgz","zymrueclo","vqrjjmcsn","msobthc","cxtzzktpp"}

    {650631619,662473526,416345759,756670185,669749287}

    Returns: -1

  77. {"vgkznqopco","vdyucfbxgw","rjxcbsjk","lecto","euzcpuar"}

    {863914828,985153391,829044725,518430126,836283622}

    Returns: -1

  78. {"cwues","emnckehm"}

    {171645922,183524559}

    Returns: 4

  79. {"uylcvu"}

    {803425310}

    Returns: -1

  80. {"cwkyumkz","aeojcgfihu","jycmdplzy","qcmkkxb","lexfci"}

    {4985773,942241953,968815724,549851588,759451163}

    Returns: -1

  81. {"ejcmmjwz","ndpacdhepp","zlrnajac","wzqqch"}

    {498307750,711057926,594799660,967910399}

    Returns: -1

  82. {"axtcevrs","hcpzsna","uyyucs"}

    {326198463,169139982,893471263}

    Returns: -1

  83. {"aldrrfcqqu","cbvvvh","ivqce","bcilthkg"}

    {171381249,956432548,847122973,332907089}

    Returns: -1

  84. {"fvldpcytvu"}

    {274441803}

    Returns: 4

  85. {"kvcizp"}

    {492145981}

    Returns: 1

  86. {"jgcfrybnkw","zpzvfgcf"}

    {289385849,457429111}

    Returns: 17

  87. {"rnmca","idbwce","ssxfcb","gfbqc","cbwzr"}

    {111687624,586024446,955696975,120150272,954435730}

    Returns: -1

  88. {"caaaaaaaaa", "caaaaaaaa", "caaaaaaa", "caaaaaa"}

    {1, 1, 1, 1}

    Returns: 2519

  89. {"kkafjdkac", "aldkflscd", "adalcdasf", "dcasdsds", "cadadaas" }

    {81, 81, 4782969, 4782969, 4782969 }

    Returns: -1

  90. {"abc", "bac", "abpc" }

    {1, 1, 1 }

    Returns: 10

  91. {"abc", "acb", "cab" }

    {32, 31, 30 }

    Returns: 0

  92. {"c", "c", "ababcbabab", "c" }

    {470, 4700, 1, 470000 }

    Returns: 3

  93. {"abc", "acb", "cab", "aca" }

    {32, 31, 30, 3 }

    Returns: -1

  94. {"ca", "caba" }

    {1, 2 }

    Returns: 1

  95. {"cdefghij", "cdefghijk", "cdefg", "cdefghi", "cde" }

    {1, 1, 1, 1, 1 }

    Returns: 2519

  96. {"bc", "bc" }

    {1, 1 }

    Returns: 0

  97. {"aaac", "aaac" }

    {3, 3 }

    Returns: 0

  98. {"acaa", "acaa" }

    {2, 2 }

    Returns: -1

  99. {"ca", "ac" }

    {1, 1 }

    Returns: -1

  100. {"c", "c", "ababcbabab", "c" }

    {470, 4700, 47002, 470000 }

    Returns: 1

  101. {"c" }

    {1 }

    Returns: 0

  102. {"acbd" }

    {2 }

    Returns: -1

  103. {"caaaaaaaa", "caaaaaaaaa" }

    {1, 1 }

    Returns: 89

  104. {"ac", "ca" }

    {1, 1 }

    Returns: -1

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: