P1199 {{[NOIP 2010 Junior] Three Kingdoms Game}}

{{}}

{{Xiaohan loves computer games, and these days he is playing a game called "Three Kingdoms." In the game, Xiaohan and the computer control opposing sides, each assembling their own army to battle. There are $ N $ generals in total (where $ N $ is even and at least $ 4 $). Between any two generals there is a "synergy value," indicating how powerful a pair would be if they fight together. Before the game starts, all generals are free (called free generals; once a free general is chosen as a member of a side's army, he is no longer a free general). In other words, free generals do not belong to any side. When the game begins, Xiaohan and the computer take turns selecting generals from the free generals to form their armies, following these rules: Xiaohan first selects one free general to join his army, then the computer selects one free general to join the computer's army. They continue selecting in the order "Xiaohan → computer → Xiaohan → …" until all generals are evenly split between the two sides. Then, the program automatically selects from each army the pair of generals with the highest synergy value to represent that army in a two-on-two duel. The side whose pair has the higher synergy value wins the duel; that side wins the battle. It is known that the computer's principle for choosing is to disrupt the opponent's strongest possible pair on the opponent's next move as much as possible. Its specific strategy is as follows: whenever it is the computer's turn, it tries pairing each general already in the opponent's army with each current free general, finds the pair with the highest synergy value among all such pairings, and then picks the free general from that pair into its own army. For example, suppose there are $ 6 $ generals in total, and their pairwise synergy values are as shown below: | General ID | 1 | 2 | 3 | 4 | 5 | 6 | | :--------: | :--: | :--: | :--: | :--: | :--: | :--: | | **1** | | $5$ | $28$ | $16$ | $29$ | $27$ | | **2** | $5$ | | $23$ | $3$ | $20$ | $1$ | | **3** | $28$ | $23$ | | $8$ | $32$ | $26$ | | **4** | $16$ | $3$ | $8$ | | $33$ | $11$ | | **5** | $29$ | $20$ | $32$ | $33$ | | $12$ | | **6** | $27$ | $1$ | $26$ | $11$ | $12$ | | The selection process is as follows: | | Xiaohan | Free generals available to the computer on its turn | Computer | Computer's choice explanation | | :----: | :-----: | :-------------------------------------------------: | :------: | :---------------------------: | | Round 1 | $5$ | $1,2,3,4,6$ | $\color{magenta}4$ | The synergy value between Xiaohan's $5$ and $4$ is the highest, so the computer selects $4$. | | Round 2 | $5,3$ | $1,2,6$ | $4,\color{magenta}1$ | The maximum synergy value that can be formed by pairing Xiaohan's $5$ and $3$ with a free general is $29$, produced by pairing $5$ with $1$, so the computer selects $1$. | | Round 3 | $5,3,6$ | $2$ | $4,1,\color{magenta}2$ | | Xiaohan wants to know: if the computer always sticks to the above strategy in a game, is it possible for him to force a win? If yes, among all possible winning outcomes, what is the maximum synergy value of the pair of generals he finally uses for the duel? Assume that throughout the game, both sides can always see the free generals and the opponent's chosen generals. To simplify the problem, it is guaranteed that for different pairs of generals, their synergy values are all distinct.}}

{{A total of $ N $ lines. The first line contains an even integer $ N $, the number of generals. From the $ 2 $-nd line to the $ N $-th line, line $ i+1 $ contains $ N-i $ non-negative integers separated by single spaces, representing the synergy values between general $ i $ and generals $ i+1,i+2,\dots,N $ ($0 \le \text{默契值} \le 10^9$).}}

{{One or two lines in total. If there exists a selection sequence that allows Xiaohan to win for the given input, output $ 1$, and on the next line output the maximum synergy value of Xiaohan's final chosen pair among all winning cases. If no such selection sequence exists, output $0$.}}

{{Constraints For $ 40\% $ of the testdata, $N≤10$. For $ 70\% $ of the testdata, $ N≤18$. For $ 100\% $ of the testdata, $4\le N≤500$. It is guaranteed that for different pairs of generals, their synergy values are all distinct. NOIP 2010 Junior Problem 4.}} Translated by ChatGPT 5