OI Problems   关于

#54w646. Operation Hope

时间限制:10 s       空间限制:512 MiB       标签: 杂题 钉耙编程大学生联赛 2023 

算法难度等级:4       思维难度等级:8       实现难度等级:4

本题来源于:2023 年“钉耙编程”中国大学生算法设计超级联赛第三场 第 9 题(HDUOJ 7308)

在一个游戏中,有 nn 个角色,每个角色有三个属性 ai,bi,cia_i,b_i,c_i

对于每一个角色 ii,你可以将 ai,bi,cia_i,b_i,c_i 变为 (ai,bi,ci)(a'_i,b'_i,c'_i)。你要将角色的差距最小化。

差距定义为 max(maxi=1naimini=1nai,maxi=1nbimini=1nbi,maxi=1ncimini=1nci)\max(\max\limits_{i=1}^na_i-\min\limits_{i=1}^na_i,\max\limits_{i=1}^nb_i-\min\limits_{i=1}^nb_i,\max\limits_{i=1}^nc_i-\min\limits_{i=1}^nc_i)

Problem Description

Little Q is playing an RPG online game. In this game, there are nn characters labeled by 1, 2, , n1,\ 2,\ \cdots,\ n. The ii-th character has three types of quotas:

  • aia_i - The maximum points of damage he can achieve in 1515 seconds.
  • bib_i - The maximum points of damage he can achieve in 4040 seconds.
  • cic_i - The maximum points of damage he can achieve in 120120 seconds.

You are the team leader working for the new balance between these nn characters, aiming at bringing hope to the weak characters. For each character, your teammates have made a plan to strengthen some skills such that the three quotas may be increased as a result. Note that it is not allowed to weaken characters, because it will make their owners upset.

To make a perfect balance, you need to accept some plans and deny others such that the gap between all the nn characters is minimized. Note that a plan can only be entirely accepted or entirely denied. Here, the gap is defined as

max(max1inaimin1inai,max1inbimin1inbi,max1incimin1inci).\max(\max_{1\leq i\leq n}a_i-\min_{1\leq i\leq n}a_i, \max_{1\leq i\leq n}b_i-\min_{1\leq i\leq n}b_i, \max_{1\leq i\leq n}c_i-\min_{1\leq i\leq n}c_i).


The first line contains a single integer TT (1T1001 \leq T \leq 100), the number of test cases. For each test case:

The first line contains a single integer nn (1n1000001 \leq n \leq 100\,000), denoting the number of characters.

In the next nn lines, the ii-th line contains six integers aia_i, bib_i, cic_i, aia_i', bib_i' and cic_i' (1aiai1091\leq a_i\leq a_i'\leq 10^9, 1bibi1091\leq b_i\leq b_i'\leq 10^9, 1cici1091\leq c_i\leq c_i'\leq 10^9), describing the quotas of the ii-th character now and in plan.

It is guaranteed that the sum of all nn is at most 500000500\,000.


For each test case, output a single line containing an integer, denoting the optimal gap.

1 1 1 2 3 5
2 4 3 7 5 8