Back to Category
d246: [12.08] B - Integer Collapse Game

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 4 Times | Submit :39 Times | Clicks : 553
Accepted : 2 Users | Submit : 3 Users | Accepted rate : 67%
Time Limit :2000 ms | Memory Limit : 64000 KBytes
Update : 2012-11-01 19:38


There is a novel game called “integer collapse”, which can be played by two players. The game begins by two sequences of integers with the same length, (a1,a2,...,an) and (b1,b2, ..., bn). In each turn, a player can collapse two integers from the head of a chosen sequence and the two integers are removed from the sequence. In the meantime, the product of the two integers is the points the player can get from this move. Once two integers are removed, the head integer of the “unchosen” sequence must be removed and becomes the head integer of the chosen sequence. This rule complicates the game so
that a player cannot play by a simple greedy strategy.
For example, two sequences are (−1, 3, 5) and (10,−2, 4). In the first move, player 1 chooses to collapse (−1, 3), gets −3 points, and then the two sequences become (10, 5) and (−2, 4), respectively. In the second move, player 2 chooses to collapse (10, 5), gets 50 points and the two sequence become (−2) and (4), respectively. When the length of each sequence is 1, the game stops.
One day, two players, Mike and Nancy, decide to cooperate to find a sequence of moves in which the the sum of points is maximum. Please help them to solve this puzzle. 
Technical Specifications
  • The number of test cases is less than 20.
  • The length of a sequence is less than 35. 
  • The integers xi in a sequence are in the range −10 ≤ xi ≤ 10


The first line of the input file contains an integer indicating the number of test cases to follow. Each test case begins with an integer n, which is the length of two sequences. Following n there are n lines of two integers (ai,bi) which are the i-th integers in the two sequences.


For each test case, please output the maximum total points that a best sequence of moves can produce.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
-1 10
3 -2
5 4

Sample Output :


Hint :

click here to download the problem solving hint

Author :

  Solve it!   Status Forum

50342. dieter
(2ms, 196KB, 1093B)
50372. rabbit125
(0ms, 738KB, 2492B)

Program running time may be affected by various factors. Check server system environment information here