JOIN
Get Time

   Problem Statement  

 Problem Statement for ElectronicPet

Problem Statement

    

Kirino has found a game in which she has to feed electronic pets. There are two pets in the game. To win the game, Kirino must satisfy the following rules:

  • There must be at least 1 second between any two feedings.
  • There must be at least p1 seconds between any two feedings of the first pet.
  • She must feed the first pet at least t1 times.
  • There must be at least p2 seconds between any two feedings of the second pet.
  • She must feed the second pet at least t2 times.

Let T(p1,t1,p2,t2) be the shortest time in which Kirino can win the game. (In other words, T(p1,t1,p2,t2) is the smallest possible difference between the times of the first and last feeding.)

You are given multiple queries (p1,t1,p2,t2) and you have to process all of them. More precisely, you are given int[]s period1, time1, period2, and time2, each with Q elements. For each valid i, you must answer the query with p1=period1[i], t1=time1[i], p2=period2[i], and t2=time2[i].

Return a long[] with Q elements: the answers to the queries, in the same order.

 

Definition

    
Class:ElectronicPet
Method:minimumSec
Parameters:int[], int[], int[], int[]
Returns:long[]
Method signature:long[] minimumSec(int[] period1, int[] time1, int[] period2, int[] time2)
(be sure your method is public)
    
 

Constraints

-Q will be between 1 and 100, inclusive.
-period1, time1, period2, and time2 will contain Q elements each.
-Each element of period1, time1, period2, and time2 will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{2}
{2}
{2}
{3}
Returns: {4 }
Kirino can win the game in 4 seconds. The optimal solution is to feed the first pet at times 1 and 3, and to feed the second pet at times 0, 2, and 4.
1)
    
{1}
{10}
{2}
{4}
Returns: {13 }
We need to feed an animal 10+4 = 14 times, so we will surely need at least 13 seconds. In this case, it is possible to win the game in 13 seconds. For example, we can feed the second pet at the times 1, 3, 6, and 10.
2)
    
{7357,10,2}
{7356,50,1000000}
{7356,3,3}
{7357,167,900000}
Returns: {54110737, 510, 2799998 }
3)
    
{407682800,484877059,830674177,227281073,19285523,560937767,919297611,23531788,
316159340,674806519,329433665,738538481,641235893,765181213,174785202,336152284,
570921683,400867251,774285402,943390771,837295831,294507056,493790893,522227203,
497924687,598834705,475831075,475114141,905813209,170832752,641484603,289813259,
862545694,178944781,755931661,620338556,970867185,83941427,135674814,895365643,
473440918,718282949,499031452,245406771,472643639,857414603,969063773,78465926,
1,7,2,8,7,7,3,8,1,2,8,6,1,7,10,5,3,10,1,5,5,7,1,1,10,9,3,8,5,6,7,3,7,7,5,3,1,4,
9,8,1,5,9,7,4,7,9,1}
{685321887,561847762,364868210,867285301,914945601,118787805,548332607,31355359,
803650261,960301524,266477641,39110673,474718169,71340489,687134789,493401968,
653058743,55748625,509077445,269937973,742890796,52585495,726357125,68477490,
4,7,9,9,7,6,1,7,3,8,6,9,1,9,9,6,10,6,8,8,10,9,6,5,781250147,170878774,855135226,
549059143,654877349,801427166,673830906,386629440,851395517,900791233,449728383,
250397037,69109668,512878462,27237926,285837889,66688537,91054902,717783650,388278693,
228914249,989188885,502709264,663817744,6,5,7,6,8,7,8,9,8,4,4,8,8,8,6,8,5,3,6,2,7,2,6,1}
{986705763,927574445,892948254,704066415,535436162,590308252,178891220,743922325,
856566021,518519690,225440136,785919924,5,5,5,9,9,4,7,10,7,9,4,4,818956627,417135379,
248892046,146009149,739277785,109423195,440198141,605525655,728478703,626172069,
630370468,130076349,4,1,5,4,9,10,3,1,4,9,3,1,583089191,388870099,453827819,111516603,
844765437,521615016,829962743,292223139,131621553,188850119,791754731,848542169,10,8,
1,9,10,3,9,4,3,4,4,4,278700059,895269545,67783376,711864145,956734152,422403629,
81840569,351747691,160762278,343337051,756026313,407474198,3,1,2,5,6,7,8,9,7,8,1,9}
{682390001,180499376,576561187,900180870,848774944,346873906,2,8,3,10,6,5,699143960,
814962202,251766107,732807531,131595022,598147784,3,2,3,3,7,10,637954336,380997052,
636675367,968908554,354172494,436377372,1,8,7,7,8,3,419710297,126884289,571143414,
264634798,264801163,157605826,4,4,6,8,5,5,485199156,117420995,773034099,419801566,
687631343,469269453,4,6,6,7,5,9,456349996,696828998,843725003,829027352,369267156,
515309802,7,6,8,2,10,6,75700282,191511000,510072386,297737413,817129266,664602545,
8,6,10,2,6,2,325802862,171214036,503091306,72109356,917444714,754965240,1,2,10,9,5,8}
Returns: 
{673318145613570000, 272427089959414899, 514839304362869244, 633787117288414635, 454464797881688766, 204762528524964060, 504080854729204266, 737847637120104, 254081535792428400, 648017727926028437, 87786705585750600, 28884736289769232, 304406328380804024, 54588401143851944, 120100992721807176, 165858198137142628, 372845396080502786, 22347797649912624, 394171233376672488, 254656991527256412, 622019365541775645, 15486799026245664, 358668532896871732, 35760807548933267, 522456930371628045, 158927349266767329, 158463434481538836, 141469513282351397, 261831856132968005, 47749806160520345, 1, 4238679585, 4370872218, 3757032414, 4412593276, 4962708448, 1678841184, 671531416, 2855717065, 4476828215, 4260968262, 3591414745, 3493220164, 1717847397, 4253792751, 6859316824, 4845318865, 313863704, 282914382762833605, 45661513561458406, 350824378707972262, 46814844462883695, 580887191119526454, 244777992713291232, 2489888229, 3093035512, 851395522, 1801582464, 3597827056, 6788337352, 4563499950, 5574631976, 870962928, 7461246159, 3692671550, 1545929403, 717783656, 1941393460, 1144571240, 6924322188, 502709273, 663817749, 21097672781016579, 171453964937225455, 34574428259671760, 211948588227892740, 781775474424158280, 280730526428232176, 572883983, 1758738455, 1446860502, 343337051, 3780131565, 407474198, 977408583, 171214043, 1006182610, 360546775, 5504668278, 5284756673, 45, 9, 63, 64, 45, 63 }

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 639 Round 1 - Division I, Level Three