Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Similarity of necklaces 2
Description The background knowledge of this problem comes from "Similarity of necklaces". Do not worry. I will bring you all the information you need.
The little cat thinks about the problem he met again, and turns that problem into a fair new one, by putting N * (N + 1) / 2 elements into a linear list, with M = N * (N + 1) / 2 elements: (The above table denotes Table and Pairs in description of One more array named "Multi" appears here. Suppose Pairs and Multi are given, the little cat's purpose is to determine an array Table with M integers that obey: (this condition is similar with the condition that appears in the problem "Similarity of necklaces") and make as large as possible. What is more, we must have Low[i] <= Table[i] <= Up[i] for any 1 <= i <= M. Here Low and Up are two more arrays with M integers given to you. Input The input contains a number of test cases. Each of the following blocks denotes a single test case. A test case starts by an integer M (1 <= M <= 200) and M lines followed. The i-th line followed contains four integers: Pairs[i], Multi[i], Low[i], Up[i].
Restrictions: -25 <= Low[i] < Up[i] <= 25, 0 <= Pairs[i] <= 100000, 1 <= Multi[i] <= 20. From the input given, you may assume that there is always a solution. Output For each test case, output a single line with a single number, which is the largest
Sample Input 10 7 1 1 10 0 2 -10 10 2 2 -10 10 0 2 -10 10 0 1 1 10 0 2 -10 10 0 2 -10 10 0 1 1 10 0 2 -10 10 0 1 1 10 10 0 1 1 10 2 2 -10 10 2 2 -10 10 2 2 -10 10 0 1 1 10 2 2 -10 10 2 2 -10 10 0 1 1 10 2 2 -10 10 0 1 1 10 Sample Output 90 -4 Source POJ Monthly--2006.01.22,Zeyuan Zhu |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator