Statistics

Problem Statement for "BrownieGame"

Problem Statement

Alice and Maya play the Brownie Game. The game is played on a tray that holds a collection of brownies Each brownie is a rectangle with integer dimensions. All brownies are aligned with the coordinate axes and have a fixed orientation (i.e., they cannot be rotated).


During the game the girls will cut the brownies. For the cut a girl always has to choose a single brownie and cut it to obtain two new valid brownies: the new dimensions of each of the two pieces must again be positive integers. Additionally, Alice can only make vertical cuts (parallel to the y axis) and Maya can only make horizontal cuts. In other words, suppose we have a brownie with r rows and c columns ("an r*c brownie" for short). Alice can cut it into an r*c1 brownie and an r*c2 brownie such that c1+c2 = c, while Maya can cut the r*c brownie into an r1*c brownie and an r2*c brownie such that r1+r2 = r.


For example, given a single 2*4 brownie Alice has three ways to make a cut. One of those ways is to cut it into a 2*1 brownie and a 2*3 brownie. In the same situation Maya only has one possibility: she has to cut this brownie into two 1*4 brownies. Given a single 47*1 brownie, Alice has no valid ways to make a cut.


Alice and Maya take alternating turns. The game ends when the current player cannot make any valid cut. In other words, Alice loses if it's her turn and each brownie only has one column, while Maya loses when it's her turn and each brownie only has one row.


Maya really wants to win the game, so she brought a large supply of 2*1 brownies and she plans to add some of them to the tray before they start playing the game. Clearly, if Maya adds enough 2*1 brownies she will win the game, as Maya is the only one who can cut the 2*1 brownies and Alice will sooner or later run out of moves. However, adding too many brownies increases the risk that Alice will notice it. Therefore Maya wants to add as few of the 2*1 brownies as possible.


You are given the int n and the int[]s r and c with n elements each. Currently there are n brownies on the tray: for each valid i, there is an r[i]*c[i] brownie.


Consider two scenarios. In both of them both Alice and Maya play the game optimally. In the first scenario Alice makes the first cut, while in the second scenario Maya is the one to start cutting. For each scenario, determine the smallest number of 2*1 brownies Maya should add to the tray before they start the game. Return a int[] containing those two numbers.

Definition

Class:
BrownieGame
Method:
HowToCheat
Parameters:
int, int[], int[]
Returns:
int[]
Method signature:
int[] HowToCheat(int n, int[] r, int[] c)
(be sure your method is public)

Constraints

  • n will be between 1 and 50, inclusive.
  • r will contain exactly n elements.
  • Each element of r will be between 2 and 1,000,000,000, inclusive.
  • c will contain exactly n elements.
  • Each element of c will be between 2 and 1,000,000,000, inclusive.

Examples

  1. 1

    {2}

    {2}

    Returns: {0, 1 }

    The tray contains a single 2*2 brownie. In the first scenario Alice has to cut the brownie into two 2*1 brownies, then Maya can cut any one of those into two 1*1 brownies, and then Alice loses the game because she has no valid moves left. As Maya already wins this scenario, she doesn't have to add any 2*1 brownies. In the second scenario Maya would lose the game in the same manner. However, if she adds one extra 2*1 brownie to the tray before the start of the game, she will already have a winning strategy. One such strategy starts with cutting the 2*1 brownie and essentially leaving Alice in the situation from the first scenario.

  2. 2

    {2,2}

    {2,2}

    Returns: {0, 1 }

    Now the tray contains two 2*2 brownies. Suppose we are in the first scenario and suppose that Maya did not add any 2*1 brownies. Alice must cut one of the two 2*2 brownies, producing a tray with three brownies: 2*1, 2*1, and 2*2. Maya can cut one of the two 2*1 brownies and eventually win the game with ease. In the second scenario Alice could use the symmetric strategy to win the game, so Maya needs to add at least one 2*1 brownie before the game starts. It can be shown that adding one 2*1 brownie is enough.

  3. 1

    {2}

    {4}

    Returns: {1, 2 }

    If Alice starts first, her best strategy is to cut it to two 2x2 brownies -- and she wins. If Maya brings one extra 2x1 brownie, Maya can win no matter how Alice begins her turn. If Maya starts first, she needs to bring two extra 2x1 brownies to ensure a win.

  4. 1

    {91}

    {5}

    Returns: {0, 0 }

  5. 2

    {87,36}

    {100,23}

    Returns: {0, 0 }

  6. 1

    {51}

    {94}

    Returns: {1, 2 }

  7. 2

    {37,30}

    {97,62}

    Returns: {4, 5 }

  8. 3

    {83,12,35}

    {94,35,28}

    Returns: {2, 3 }

  9. 8

    {250,381,184,376,854,932,852,929}

    {628,723,257,697,534,382,210,863}

    Returns: {0, 0 }

  10. 8

    {660,151,524,154,100,98,216,628}

    {502,397,830,554,140,623,579,536}

    Returns: {16, 17 }

  11. 8

    {450,427,437,829,454,974,502,804}

    {372,459,622,517,146,649,434,945}

    Returns: {0, 0 }

  12. 13

    {703,657,797,877,457,944,523,652,749,552,764,695,263}

    {662,325,617,327,529,537,533,272,399,912,166,378,915}

    Returns: {0, 0 }

  13. 7

    {630,367,887,770,496,623,833}

    {251,295,591,357,332,174,354}

    Returns: {0, 0 }

  14. 16

    {18434,19933,18700,12563,16063,18090,13928,19460,16986,16149,14105,16766,13504,12013,16750,12254}

    {18534,18477,17298,15919,10837,13882,11772,17547,13464,15482,11198,16671,15739,15539,10113,16386}

    Returns: {0, 0 }

  15. 11

    {12542,16639,19135,15278,19541,18440,15503,16842,19745,15786,17352}

    {12201,15560,18313,12612,18861,13642,16294,19873,17589,15192,13454}

    Returns: {0, 0 }

  16. 19

    {10412,19064,14044,13831,13196,18507,11980,10832,10993,17693,18865,15961,18250,14698,19193,13886,10215,18164,13554}

    {15936,15177,14220,14050,17859,11665,15116,12999,10140,14368,16291,13795,17420,18117,16942,13019,15215,14849,12461}

    Returns: {0, 0 }

  17. 16

    {19947,13627,10560,11215,14086,18826,15609,17497,16863,10852,11549,17912,14198,10011,11170,19284}

    {12345,17704,17669,18406,17324,13620,18570,14040,10019,12126,19837,13850,18381,16901,10564,18846}

    Returns: {3, 4 }

  18. 15

    {15238,18853,10211,14675,12039,11707,12934,16524,18500,16015,14666,15899,12858,16407,16110}

    {15445,19913,10636,15793,17325,12761,16212,14326,12073,17903,17585,10398,15726,13009,17962}

    Returns: {1, 2 }

  19. 10

    {14518,10897,11019,16142,11314,13541,10138,13346,17260,17136}

    {16512,19050,15276,11378,11178,18327,13131,14770,12869,12165}

    Returns: {1, 2 }

  20. 18

    {19618,14575,15860,14348,17380,15971,15860,17065,19746,13395,12746,11926,19673,14773,18028,11945,18055,10112}

    {19206,15618,15320,10840,15696,18233,15891,18841,16433,12889,19746,19523,13671,18456,17547,17444,17342,15084}

    Returns: {3, 4 }

  21. 10

    {17277,19214,13357,10529,17482,17599,18509,11633,16096,13677}

    {16950,19423,17873,11397,13423,19742,14896,10592,10880,17067}

    Returns: {0, 1 }

  22. 13

    {18331,12026,17858,12151,10353,11779,18439,11498,11195,19258,10380,19177,14606}

    {16933,10555,14025,12540,12783,14427,19055,18539,13539,17186,19526,17834,13005}

    Returns: {1, 2 }

  23. 8

    {12631,12476,19279,11643,12510,19764,14687,16002}

    {19837,10907,15946,12073,12929,12068,11801,16464}

    Returns: {0, 1 }

  24. 32

    {551776526,108712918,127133170,567624445,588805464,278579259,619219742,92049546,946189817,920608332,18710572,9290738,854700213,627206831,136636919,855722867,12754180,830992722,755642514,407516523,751845460,250768024,67050307,798048522,350803958,953724574,500377891,645907079,571716454,162086452,284769996,301297803}

    {873651124,422357388,773887584,734615301,241716232,567221941,520416820,326900065,495814672,44525677,728899302,530577371,221293268,615435530,235085273,229169870,197028491,408488602,12894477,597779938,265795432,88192115,71485005,411578251,119477480,430940398,98180545,23369328,996572088,970662528,535723645,145701783}

    Returns: {0, 0 }

  25. 46

    {2705841,165638673,889731713,656646414,345669639,54113038,164883758,213279979,947971918,112698623,715380462,835888281,761192408,937623541,925625091,840138792,389777921,713622158,83483335,132228587,338864913,898159377,286722934,637441685,111835226,3125752,518163114,395563128,453127086,834836735,686093200,556907198,663185742,814577882,300407639,266123998,730143440,875602536,345484344,421777913,74998591,122160823,437489038,284167986,164202302,751663573}

    {379879488,750336987,792232718,337784553,519285698,885175145,947382464,239328370,382815121,45146495,785935317,83770130,800682465,403818289,609331957,300626279,172361286,151407399,235996137,306176995,968889106,495022636,791976029,833934948,566418645,994872724,721234801,413049343,522850300,590305683,328678046,998471320,515566024,402179537,10062736,685047721,592165282,339317820,552516279,125315081,721346307,955513788,41704375,7676162,231569707,710826146}

    Returns: {581, 582 }

  26. 33

    {605725568,397361604,472672198,383568821,111554215,936456721,93212119,524607046,480420323,866230309,299991800,249062341,415434805,224008324,432808507,938988316,966753274,194727856,440288711,989150050,3422847,13795572,665594062,999134667,913973527,957520058,602560571,6198536,995828256,936238134,150749414,468930722,505777760}

    {2579108,929786294,659587921,42716290,138434062,120427372,893433530,295695699,33305978,941126738,463507603,338065344,743397626,369034665,685431148,866755245,153931076,25964152,851168251,766907083,338659219,726872887,190010971,281678765,995469457,590092347,850087581,892507656,545403910,534564729,762147674,53626552,659465654}

    Returns: {112, 113 }

  27. 27

    {498429774,618306428,465388619,684651267,102050076,29649101,938958182,360264883,272171457,425278555,443125299,939875468,992151104,14714749,612236305,252478226,299090509,600730405,57853309,109899648,757110324,292573981,141530275,141129366,821652570,895226867,521365221}

    {922954707,995695722,444005319,716430231,463643415,96200791,5771230,215454077,38437849,831063057,133578885,744733380,666014132,143095198,261391747,121307947,702417172,948220448,323400431,247413904,912573381,700797073,434901085,139274463,194860169,807489175,644917747}

    Returns: {0, 0 }

  28. 20

    {553075132,620241774,724167421,185913389,554376436,15809482,116287384,37021425,204725077,165962977,410441599,810236958,162608242,479861946,563024293,977065434,735286311,609412561,191459448,98689712}

    {17447469,517839468,84945359,850550697,266143678,7881677,231910506,596282381,545533033,551425145,367408389,251675639,357490699,238598326,729271929,524228788,129052300,840328344,928405718,820580488}

    Returns: {0, 0 }

  29. 39

    {261744742,338675634,140891350,635778777,743481327,59869659,555489661,174508086,821330589,606979990,172473094,77079247,856943056,906557178,649232067,789602900,559035674,717207441,381206868,101588409,818244217,433880539,333609873,146900194,741128603,943857500,333354151,943681469,891671802,715679325,359099304,951708032,506631244,97887918,104192445,109625919,410842601,630108147,494480966}

    {97336127,289682477,79384968,802727603,276249155,206978406,3285307,642189636,78292795,758296840,799817444,538231576,616571799,902943340,71867822,199929999,264545453,72678436,77864,732780629,892729767,523203797,48783231,138294667,743244409,744230270,691308993,287682777,980015608,366474816,952920646,691619128,178623941,815654155,401657093,734779666,664598062,778691432,772809831}

    Returns: {0, 0 }

  30. 34

    {206796759,48507974,739143773,625943590,170823284,455212969,771451919,788024785,81871594,315028664,861529909,828859359,77063974,932083817,835680716,532147765,550445172,359741267,648378197,397063807,445337945,21637828,658430100,609402934,664018075,333879299,527859502,172566765,670113639,321889161,29533072,513712475,969813200,98028252}

    {797515827,377183194,743944952,504458636,988748185,73063881,79070206,593838606,64752562,139532382,398398878,60278661,74500037,786957490,742708820,331024759,765382687,4974553,960298489,12641181,607259980,742205241,44385869,678527355,472201225,927536841,479670745,226662294,195652194,272750294,293585035,874234545,249538058,26764047}

    Returns: {0, 0 }

  31. 30

    {653524536,502494332,576920264,451152850,590018546,542969475,90235839,905928296,19482020,194613698,270228636,737978297,360631669,767789924,236486459,29920261,505727741,434506652,448471032,738983498,155656169,996411952,134700988,680192304,994404586,96105321,218360141,509024591,200814283,777235984}

    {555472183,161982432,203139003,908642429,155148935,29916611,263219451,277780030,16762185,47756065,952221883,128620766,730537209,808946004,783135852,151581389,818796320,308866753,577962013,197686674,271078497,411126118,57631310,729528507,33064109,127355663,76787101,394379448,34289456,9608424}

    Returns: {0, 0 }

  32. 18

    {289957021,34685962,33539315,127753365,711267472,704273745,887248254,292721967,779511850,706394261,828694407,172479884,381123186,360304119,332910969,557081016,854939500,209353055}

    {460185064,437301280,847479851,814608591,23867214,591898110,2410247,685992251,250860762,78710400,435414043,913936974,741118137,520371652,832683708,979385028,155060811,811509759}

    Returns: {0, 0 }

  33. 32

    {82346305,224098815,427687440,312407892,848343554,917459967,86641150,108255923,912676793,811196519,279084971,155115506,675385563,799100558,399821769,920496411,385590292,906343757,807537469,565955476,509978471,745685751,182468880,325180481,75808750,122577479,431106985,140812645,344475539,468232780,49236685,860245751}

    {807807627,535395026,515003959,834852088,759107805,817046297,976823543,124538784,30619467,553670066,269750709,774090043,754049335,913278127,121068280,103914849,303319157,610943888,978520602,808578957,600893308,818781324,147784632,755390711,98264862,722838468,5238305,697035452,777399820,208217241,178166983,290391842}

    Returns: {0, 0 }

  34. 23

    {730257577,408649675,240192101,927550614,918390506,201465829,604822097,280793538,421563262,706070452,596739552,83509353,711761471,682450520,406339928,240359906,280168828,457513488,12322067,376789588,584454921,700684919,359613367}

    {570020422,522351007,786835183,759342313,69707865,247404843,204849417,68348868,458121141,724381601,652985362,27802541,91095696,235697401,150100596,312166523,513304361,83181068,938516345,920780549,136584029,758563521,2842900}

    Returns: {0, 0 }

  35. 26

    {130575164,16200759,593486379,720072195,225395219,674003714,23842112,914172021,776599978,247123805,953799603,819722869,776362597,191890427,176051968,442158094,926172351,487093589,113174354,11367811,20378762,58258838,917481180,754723057,702187765,442849414}

    {641422273,703183380,456959697,182996909,849220584,4149661,75346203,391112698,57673817,176383725,691952802,767591938,8456767,374896954,820410646,57633627,217196190,374254347,598306472,518644825,848881221,51197271,173573189,237444329,247092479,939230632}

    Returns: {0, 0 }

  36. 35

    {370397395,762748084,349373171,929421868,110598440,971900149,383036556,220694556,48836518,659034392,84950639,966214400,710748532,232301905,103155499,979587956,658884160,712663152,974463569,492375231,200754668,582026624,95103178,919249074,467887048,307752302,799531471,136198500,426486731,10896236,115511167,346966301,139627641,738046459,100175005}

    {506853271,970087005,487522259,790215357,47554586,758113321,332351145,509110711,249533032,817825154,274654349,687010345,39460871,965775248,508096724,118066751,85837700,6224506,98878550,95981915,179823799,126385643,464207438,821796588,485428581,252284127,713181978,456511729,809524267,596894845,863895040,44485691,315064275,274219501,807057946}

    Returns: {0, 0 }

  37. 31

    {840675507,42534051,584545521,395623021,867044377,689562239,949260338,81939880,721764524,683819705,500289207,982695102,875027170,548740463,83623210,781089393,816473087,483816322,314248782,986805054,865265960,606720469,537663089,494365254,681305734,103442682,701800535,779222737,95341887,439458548,285787836}

    {731260696,550668865,511814581,419670995,383743856,650758050,562453591,64951716,708683001,418231350,962190432,7300274,406559694,386147812,793913492,994822199,835597038,920764472,709919261,216303185,558660395,898532915,39800284,182560123,115593694,246852340,181368810,834189513,388260535,576482363,462691349}

    Returns: {0, 0 }

  38. 40

    {835351108,731274705,81554334,5087529,129551446,847210788,892949613,644691505,753641946,785283140,82989035,805948349,4997008,300293461,839066054,258637827,949805733,46048806,771240620,63387404,407077915,621878438,73119657,528467869,733463182,819593594,575509794,202751815,51618764,675399142,2201454,272265172,537350106,297770830,190437122,170710864,453380492,807891111,181154836,402504801}

    {645438106,277983314,27531035,399682182,970184900,255100695,981348615,68053581,601602804,966689554,79790731,39984526,818741154,445594965,805509765,211985021,138972769,848135910,822735207,200176504,668546222,107963905,147319047,760038450,759532482,949388888,326728058,740656952,120623197,627749711,492581767,820544083,74462296,997408688,926041812,892267015,693915876,479730755,330445365,324668745}

    Returns: {523, 524 }

  39. 32

    {716061433,735962330,703907758,628542718,323146941,316242378,434106708,12158268,946080729,503496223,534257018,396443044,867083181,102590148,936499712,991590007,5521515,304003051,429938583,134126245,771869496,95825775,538558939,768186718,81478380,364170245,608613668,986433171,432318744,205119363,110122182,110339955}

    {346113031,606001749,883205542,445368221,937422283,856548880,822420657,918953742,809856303,175417170,628539807,523933903,35922685,596177054,635938881,180113318,458272172,308610104,488220485,987860295,9357782,516955106,63965705,242450050,105494033,73841925,505273803,408516545,43918996,729846894,840059196,643642607}

    Returns: {110, 111 }

  40. 27

    {323721020,492077138,165125295,734548855,898395957,712548446,601817711,659809353,345866688,890806646,345667729,544782844,118171750,757914904,739085098,694467976,532263136,765598763,346662443,574275857,637142988,259847218,102648770,929172658,115227458,543742069,772107285}

    {996033449,173861929,711927529,472047541,383293630,78360762,102257795,957692799,536120946,324240597,487184328,442438336,837678811,550247560,550755998,142579347,477103386,843846953,25473350,855747141,901663534,417904964,788475237,896710181,183526943,922963858,356388333}

    Returns: {0, 0 }

  41. 41

    {674553218,62551715,88612830,900843059,390644954,8698968,653625793,789059847,579512981,8341504,577327282,982557246,288072077,251855732,432395073,547556319,765228074,59201869,372512432,235502720,347382403,458207703,98080798,97639613,50884166,849764823,139352385,548802911,667296304,316026803,878597864,933714747,674225023,89758884,777558903,428700,118925123,846656852,784390909,32361379,94019986}

    {442690573,187137011,548072722,709547651,712199387,760557111,902776706,810256464,829260682,402148833,601439588,837838128,992185961,41947647,972258622,811592426,701605994,720850110,694541779,281820007,240939187,13434339,116942898,937359314,304614616,231094000,776765748,288227700,882304854,528347150,496709864,280710589,576206378,482449477,787418886,762676347,53156835,535032930,3348667,22740445,231830441}

    Returns: {2713, 2714 }

  42. 29

    {390729667,924188983,856105408,122376580,863885671,233730913,115163632,353772129,198176884,544876665,157792467,786186651,908632475,600097960,163593433,147084775,524626845,160458487,466716644,671356383,910896535,382463914,62411411,491982518,86019126,713457753,74037864,327053484,371016459}

    {135970780,887946689,423123744,286774393,189501518,567830816,672363465,613403596,11719279,664766007,23138861,765091525,422721668,56135569,735726659,300102116,628457492,379258536,496323253,400575903,27110670,652413515,976531329,731067236,52846183,683219859,754276795,22697427,174043684}

    Returns: {0, 0 }

  43. 35

    {84288782,524161180,139462594,940573041,319512269,902216894,881993767,8941164,445062641,280995943,194747464,879617405,294623581,993105038,805836049,515484143,567706091,588616537,168351118,923576035,208732464,809141673,498525947,319782222,946288868,837032183,489044505,515014860,605991639,211688663,546656980,630256822,164441661,222163169,275735989}

    {888241984,391960426,481564764,376902680,333553972,970234150,737076764,97738095,275192946,382240636,148477580,452266275,434164044,666397342,300042073,792925791,959355975,568425666,241243516,530586117,118655058,377611696,37328794,575686749,806042953,981978220,744006626,495620999,533988988,263884121,728787382,129988511,106992775,569769286,817985056}

    Returns: {0, 0 }

  44. 30

    {585400677,995959587,832470060,186170188,63670038,332764547,498150824,535881035,567135719,572447751,443224468,824578016,264671373,478722772,561628468,399607815,737684903,399667105,424353662,649088250,991805431,775248133,910674874,735298338,468556749,279472640,313144133,695168013,64901962,590039803}

    {598841522,997484081,10071950,452545213,214587110,101193816,921893052,380008903,692473022,776481673,26731409,345609996,285383164,812137432,473902286,419432626,239320680,250055095,692674723,383160166,47544538,186954157,138388884,913131103,584616070,91658226,71758270,752623986,259451834,260220911}

    Returns: {0, 0 }

  45. 34

    {633996122,597233107,242608595,393298135,87324497,797873453,940797560,741333316,881769201,109930397,39099291,52824044,201823767,253884625,490441677,328419047,558677082,754715247,33136210,9739266,443801765,621181376,7002079,364015522,774784051,120313777,691602783,207457752,139417334,949317495,612114759,402718942,185453571,600690920}

    {299699776,732132447,973563334,580958655,490604828,346101878,436367235,262791294,651046996,139115134,552521591,462075947,550242531,362754962,185897328,98200229,279462580,835606322,114266987,20820225,140427499,669628455,130455819,201837127,994443486,706407387,961345492,768728873,823207397,897994077,758335473,2672026,294265175,33401628}

    Returns: {0, 0 }

  46. 23

    {972692137,982585715,771587423,459976670,6328256,65995293,220692416,62499543,786896646,23621124,325434671,90466484,945186733,20567616,936875374,344982506,148730033,626053160,343871168,168824125,475438165,691122675,466886205}

    {766094770,542735751,955807865,427497226,524549979,473577689,14911078,868430469,559881186,89625549,480400324,592508248,209134762,493169596,106561104,289000618,592814174,945323557,105960234,142904923,443322404,333621278,425070473}

    Returns: {155, 156 }

  47. 16

    {76690853,830550468,534977780,259049086,57201630,262146582,567911749,152694401,6600085,604173583,95096819,893686593,39413362,388725712,106817586,450015797}

    {826847347,791879352,398252207,280886023,854855291,800893767,850307350,632573178,798212688,417595640,123518215,64810608,554526508,60037500,360708186,351964621}

    Returns: {215, 216 }

  48. 32

    {70693104,552726674,814705142,142652032,97365648,353240275,437465292,285125893,13847932,199208831,519720120,584091219,547164766,651118897,490660158,269764684,139205652,661927892,123773135,232634485,751300275,222771141,776512714,165204917,257015635,815612303,38348199,49093297,856671810,567634171,160946743,605482979}

    {139656787,203686732,934322058,335820947,600021573,639370792,35889052,467117284,188828423,716550680,512314581,65617386,65495798,319370503,561940202,970934347,394570756,449039474,883159739,842421030,440611301,425439241,964930555,276553624,464413418,149591455,646955669,19055966,727610357,480021198,742248118,949777742}

    Returns: {27, 28 }

  49. 16

    {234449735,686718747,623874732,52772212,545943494,856929338,889898017,89103920,641694961,142255881,366758425,517670385,277035404,57198953,989148754,983657799}

    {138073076,497111941,839706160,405690049,997032849,778297074,814723186,148350656,845068029,137542946,223032175,422156788,763357508,809862952,327066226,382382362}

    Returns: {30, 31 }

  50. 43

    {764777412,923466709,52811583,61164060,812990931,121367142,341588288,199326400,17668946,664321440,144677813,460192822,295417102,835514220,446869141,204998881,269919401,468486586,141036714,272277143,828602940,451427738,851864864,517815980,801589862,413589744,769112880,647054375,138192611,233898725,364416022,422398797,469957797,798225814,528337144,31183341,964608805,712977707,689972158,520916363,878160131,30880777,722435174}

    {316586279,232911384,68398445,862042329,23484277,81960120,242818075,545049216,1482226,24695062,40764777,747015682,466910626,465796983,171589318,227292354,442160233,571251090,140220561,415024380,438895521,627001451,560028435,721688306,530762178,338995805,168352957,726425953,732505320,633047155,657454246,49513373,676574249,991646825,458232599,486271495,218384522,431440465,491099442,124353298,105568707,861910202,636163016}

    Returns: {0, 0 }

  51. 35

    {551502596,712830485,139688035,832478314,718118438,414535629,953653506,99940049,439594516,132354939,342677023,755459546,986999420,653417678,665904856,181153386,979707994,549373010,747497005,816526189,159668444,370104844,661335757,847504057,671007856,896039047,170547670,114380852,995262197,490078703,764114536,401943456,847284937,513002309,537986744}

    {106444255,104563958,78911809,148796928,100225061,55615825,758886956,734060765,296153907,237135217,362318043,460137733,727812602,133412564,700499450,36499877,587383699,654849792,943561821,310023368,715332380,614340571,235444763,115524624,567274570,947799340,44754681,959230150,995487672,527844251,62531227,20845266,894606638,256833834,411921713}

    Returns: {0, 0 }

  52. 23

    {536552784,275525152,610340991,389919957,953021802,259807422,712839045,61232953,929392672,193768634,590578592,891782899,538337887,304874524,634125121,120356561,120572181,502565347,806316889,762843365,355360806,242442654,442050541}

    {100540670,151355907,994006840,786979477,896636978,141337293,248431878,39307893,47323762,459091961,725713046,281680255,870131174,504012302,320302322,443858989,771817036,104337113,538390943,23313055,937777871,332076594,789757704}

    Returns: {0, 0 }

  53. 48

    {644915674,140255102,168187473,867864687,177528501,113376905,123146921,652544236,464155274,710028984,658391226,643795937,677883427,655783219,732266339,667611478,834936967,240156353,388764990,224245907,760348858,498624497,318390630,962140803,689841202,200630042,369524040,213995421,210952766,23225097,159417824,369107466,884539506,812128188,509213135,469170157,887867243,120512421,2150528,952595432,760749640,450966669,859506939,748713022,172202979,390083104,943405785,104925078}

    {140016599,38053204,13248434,866733161,258980714,82516621,96799275,485858399,789334304,431241445,138836127,630568748,178260344,237354504,345447792,484788907,519704961,578302248,702801931,441027640,48806845,292980575,35939262,522483287,270741037,813659280,441702332,109284843,528370701,60296176,798129334,32277700,965922898,573129120,996695826,323610651,44242919,915914362,10571273,173087329,342298978,319265710,151364140,887942156,929864719,233023813,341512784,949826410}

    Returns: {0, 0 }

  54. 50

    {861393894,506102535,515120925,672343462,163899040,886289747,400868418,542223953,435919849,953582335,795896684,324200018,112070274,309243691,695121688,165336854,660130762,37852096,422507283,488178121,53083822,541840498,713383440,16934286,582721093,808466674,639401966,191467179,990761812,56003927,927795004,806000940,217401239,708597331,753805229,455902775,813807086,647172550,16450572,189531828,293634851,74325872,36538547,862154535,580643853,719124107,391564610,887823154,325928214,236522599}

    {652162121,256449154,505674593,391484496,951999001,300071412,114169862,759733025,830432316,561715960,333800001,55940177,780051350,922158073,973039712,513399696,309446622,898887136,873837574,814398197,533197499,774836696,808144055,521572573,660229821,145224524,794542150,450624337,686309182,35032878,113605096,504822480,367809501,973388677,590700240,510156105,873080395,565109531,999106878,135434785,577389127,881800972,296905563,551353526,90414578,654770209,528755952,302239097,18578377,783824532}

    Returns: {175, 176 }

  55. 50

    {466468716,757944209,149707437,680766555,212312312,275660250,668123202,927493026,841684551,830006155,16324601,303970839,119765651,132615960,611110154,435246464,870551141,540163010,685652566,429526884,81343347,279143412,432801845,306463831,374745479,368160779,536029971,98176051,681652715,240018743,674846594,20600128,42333292,630033377,170235500,742532139,862422052,812378451,701880176,271149806,935383717,883981284,149547681,843966018,49053886,779859519,867531905,299895915,170505605,819050519}

    {999267437,269195835,988657672,224487845,737559292,274464346,495399587,332228145,109715958,400409909,30395927,515028596,101369208,329147870,54808413,250268856,88673511,481202376,906160696,758051911,897148187,833909611,947365702,464072201,151598078,170075736,735692608,336562911,252657996,395593710,677815641,855353305,70801577,102973058,74699871,85056631,735163536,317467507,913178797,795224244,788704754,156439417,266876752,781245267,355675290,381107367,717117027,580393072,336768227,952629299}

    Returns: {17, 18 }

  56. 50

    {742289998,525794539,808955199,709747117,311077515,70146962,884520503,599207442,555098609,948180106,251073922,230718587,679420937,39222429,547921302,760050952,675405747,583869523,787594777,329376732,57535763,510751402,878287513,56059764,230886202,48833016,269127681,212949035,565742086,856991585,530620884,367345242,679634536,769387468,997880795,755852336,298862434,589634310,396016903,401171796,984381539,59934759,813639881,129495622,885519465,37597385,207349830,523447568,5418025,508796586}

    {310360138,674343304,764929612,987870071,696847897,549582782,629158562,720907001,248228070,110249976,367909875,871558964,232006235,474618310,877313554,318487083,319700963,617159093,556950667,162626494,28177681,98926445,98994334,973485337,542180621,771615934,3243160,701544518,892003308,825482402,19480573,496730905,525997335,488386179,58591316,636689237,390547081,886551002,196516758,918076614,827243221,527533246,210349607,591099193,256224635,80791212,103367465,882507354,241302176,438207724}

    Returns: {0, 0 }

  57. 50

    {610660880,342830351,625364023,250952812,112690406,964389270,498065058,675180754,454585729,27900412,493684847,102789676,695518540,238995955,138203025,877545422,37288716,939870245,818617000,565907442,962340831,104109809,455674549,76711752,894115214,630494985,94897344,967805950,533614196,638493531,96954334,739028878,425992780,555083550,319510121,654077929,571757699,628372416,27377769,781681401,574061560,202085188,740665564,546949552,92562035,104826618,466810300,93053120,712422318,359134734}

    {94794882,624953532,83035318,646762312,447810724,806246156,628907536,1075465,16265013,145658613,25145257,401482434,201480334,402845885,907533418,362089134,20094064,32853204,91545492,542038867,755251150,97740379,969329017,196477754,843573729,419767772,66909183,265709362,103816035,725725194,112137201,186807474,324043538,994131458,689736237,492832886,65679589,104488942,135777775,936707083,149346685,666358899,925785311,725980479,304211907,259247361,315199699,949562000,852816691,940676358}

    Returns: {0, 0 }

  58. 50

    {546808868,528519455,673567221,350482440,374322949,991215275,127867106,100147147,942565489,648594286,138872219,519781199,7204891,313964690,239106407,303498311,500385465,69184611,866227747,173818835,656795986,14767922,62359782,58106106,772526576,646770771,859245052,669850015,231699737,326462760,129700895,130591798,12210655,535502219,386856897,554463191,70594576,219458322,72977647,978644794,703754954,596234740,316546691,594985400,516692924,152618346,880544126,849073890,446334948,138733572}

    {508988138,208985368,632849185,551459095,658451870,699346321,953672717,86654117,252043440,671041806,268775095,539869333,392633455,977957887,111729002,14701442,806417779,389354140,272969991,170269100,79060297,636095739,649570074,24997893,541902246,87996259,44796625,434793706,181877838,579622971,560909736,501930928,605782210,455699332,863118500,306175979,631180338,598846045,880265343,879669561,210317938,150828368,275492108,610626543,174838936,335935879,387564295,729904091,931825801,68637698}

    Returns: {218, 219 }

  59. 50

    {935805583,469718093,464647930,407642289,560492892,66085428,561142199,835662748,542641174,36633370,345559284,219083514,134249705,3649507,670617771,118825596,554217609,397243700,753102859,138043828,76500696,90486638,926325384,696969278,953873649,364714477,763427313,845654141,20919367,966323331,725857153,241375367,214206115,689272614,659075905,990073541,921999093,133377608,625504312,801819535,721993805,805501735,675404448,914106207,634801805,184933555,25426882,110262590,938932535,221714276}

    {454936589,775971855,462088193,145986468,715629277,989476633,908494706,814623432,347896345,908976638,393973875,724518015,851831760,599972123,470947831,500114913,473646599,488941113,505004971,212528526,944226856,764371966,17640959,961713783,163863063,212755576,248792502,254622031,112081357,100754677,167305600,573053162,354451608,470281670,908817845,837575806,337493035,78399364,310769809,95908995,642144260,704618633,464733230,825744147,789047515,161671766,541093757,445696505,321527679,9442922}

    Returns: {286, 287 }

  60. 50

    {351514827,119035508,386429028,679285617,697444349,545671796,712184521,732342795,352211143,877203667,688433959,991763117,116143295,681618788,26364627,947143791,44145144,743348103,123546075,342562992,77045825,271472122,363558542,477517201,254990255,758243043,71070827,226203506,178578655,121920551,704341762,363405297,384856776,599733087,47640486,730036423,198633140,260317136,115311067,905931105,989298152,21760702,708178196,455139871,299420441,603696900,362009799,32436238,402974322,443873167}

    {556053668,697376774,114375158,105166642,373678407,742952772,152129805,631443783,539999359,61663789,241528053,168508581,515838593,664065993,287769357,889153863,440446168,931442612,380310527,593282673,534656285,768938316,112308854,26942103,766209195,996731579,45596307,148520242,729049816,977416070,334381760,683203787,440958644,948107013,240362522,522955225,629846632,118165903,561968125,865758241,690514765,219013174,388818588,572930459,180036141,14299961,19253577,253120379,149360037,191997267}

    Returns: {0, 0 }

  61. 50

    {752497850,11114993,629921668,267353977,145578307,482443823,171018194,393679707,231825703,901249653,285053941,242569240,103714258,708492258,499850092,541090768,88250515,525013954,1256053,284099089,134174290,112803763,382529746,934013787,721738672,599991937,140028932,379619393,82889077,179306995,471976378,64994545,940164804,89982027,81403368,446272723,270015242,851488267,39008267,846464600,986076577,240630453,529121676,283398145,793492636,987097348,107863244,611675317,61079070,53031230}

    {92417857,519343798,372963542,257371090,309846466,75815825,344536047,551588318,134123838,475624855,239439106,312123849,908546579,373291327,398338356,60026467,854939265,273088531,176380037,372110717,767577331,205518176,134754725,404992275,649091223,22012583,382297663,463092090,939563973,85358314,76262204,816494314,705919938,41174036,740056573,885010227,54959918,506149037,21681224,991104562,249975830,106050005,592095481,327763145,731154558,208823936,755213016,963568366,616860875,648283756}

    Returns: {254, 255 }

  62. 50

    {895415036,9571191,88396113,897994158,16510525,326213385,725672562,7722161,350189394,139763905,342822884,257502592,196914659,955528630,422094874,697612090,102345398,103173996,887288928,526914277,611522772,132597421,366600330,618221243,259902706,672916909,102400631,440422913,77121791,38873835,42239434,901218597,204418992,589394260,111250626,90354790,880864504,552148285,793775041,880637582,839471863,600791989,245501043,894959683,886517652,703603495,345711984,981555818,15608658,149146462}

    {215845612,175602788,155521203,613476126,840872388,516480080,193987396,496455757,902821353,205575253,666320223,58765129,646242962,79222234,384930452,29036831,525436675,585162293,912437304,149046132,547228198,17562897,695032243,310797005,743775480,457854551,305254060,185636758,628171371,891385333,640813818,952666664,70032520,130617030,870748382,880131752,311325486,71637398,200949013,959279286,409909827,416720105,212193904,4178683,2368013,811230173,812919128,579990608,899824723,132904520}

    Returns: {0, 0 }

  63. 50

    {901389411,270020881,296551304,743584587,225523363,91293257,666768168,505332048,180600818,749233464,868720357,92801038,990750478,483251585,658123535,711212543,39125018,163012121,151513375,977736061,183480140,37551360,150013543,722892642,871818691,49687150,94114448,45351408,235838350,280582451,448074220,75370142,113059855,944745311,675801448,843429221,854647457,747934787,653773559,281392359,434073313,496333201,301594550,505423276,28852590,178507714,168309902,953473220,342887439,15071464}

    {677053914,149734591,202090817,611061906,603258722,437315616,177798705,191776027,338424090,46076261,382457882,193032594,328954084,766969877,916339870,829100175,818050720,96317811,110422019,805844119,504929624,306249038,672549359,716512190,749685332,261525103,625813434,238288747,3688909,249034321,81618332,104494040,232070041,214225235,694661289,349232676,65047837,693048393,838118151,144120754,842091908,437874349,213064105,726045022,117528729,518363515,922428991,875303802,602812462,276894278}

    Returns: {0, 0 }

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: