oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

jewels Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

jewels.html

There are N jewels of different mass, power and value, numbered from 1 to N. Jewel i has mass M[i], power P[i] and value V[i]. A magician wishes to string together some of these jewels to form a necklace and imbue it with magical powers. However, the jewels are very different in quality, and the magician has to ensure that the necklace follows some strict quality regulations before it can be imbued with magic.

The quality difference between two jewels, D(i,j), can be calculated from their masses and powers, as follows:

D(i,j) = M[i]*M[j]*(P[i]-P[j]) + P[i]*P[j]*(M[i]-M[j])

Suppose the necklace consists of K ≥ 3 jewels J[0], J[1], ..., J[K-1] aligned in a ring. Then for every consecutive triplet (a,b,c) = (J[i],J[(i+1) mod K],J[(i+2) mod K]) [0 ≤ i < K], if the following triangle inequality holds,

D(a,b) + D(b,c) ≥ D(a,c),

we call the triplet a triangular triplet.

The magic works best when the necklace has the least number of triangular triplets. Thus, the magician wishes to use a subset of the N jewels to construct a necklace with at least 3 jewels that minimises the number of triangular triplets. If there are multiple such necklaces, the magician wishes to find one whose jewels' total value is maximum. Of course, he needs your help!

Input

The first line contains a single integer T (1 ≤ T ≤ 50), the number of test cases. The T test cases are then given consecutively. For each test case:
  • The first line contains a single integer N (3 ≤ N ≤ 120).
  • The ith of the next N lines contains three integers M[i], P[i] and V[i]. (1 ≤ M[i], P[i], V[i] ≤ 1,000).

Output

For each test case, output 2 space-separated integers on a single line: the minimum number of triangular triplets on a necklace and the maximum total value of jewels on such a necklace.

Sample Input

2
3
1 2 3
4 5 6
7 8 9
3
1 2 3
4 5 6
7 8 9

Sample Output

0 18
0 18

Explanation

The D(i,j) values are as follows:

i\j123
10-42-138
2420-204
31382040

J[0] = 2, J[1] = 3, J[2] = 1 is a viable necklace, as no consecutive triplet on the necklace is triangular:

  • D(2,3) + D(3,1) = -204 + 138 = -66 < D(2,1) = 42
  • D(3,1) + D(1,2) = 138 + (-42) = 96 < D(3,2) = 204
  • D(1,2) + D(2,3) = -42 + (-204) = -246 < D(1,3) = -138
The total value of the jewels is 3+6+9 = 18.

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110011s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o jewels -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.