Hello everyone , I'm a bubble , The purpose of bringing you a daily question is to better practice the algorithm , Our daily question is to let you practice all kinds of questions , Familiar with various question types , A year later , Transform into a different self ！

Welcome to focus on the likes collection ️ Leaving a message.

️ ： love C/C++ And algorithm learning , Cloud computing, etc , Looking forward to communication ！

The author's level is limited , If an error is found , Please let me know , Thank you very much ！

University algorithm learning community ： University algorithm learning community -CSDN Community cloud

Join the army of brushing questions together , You can also join an exclusive inner volume group , There are a lot of benefits and a lot of big guys ！

Catalog

Today's topic ：  Three Kingdoms game

Title Description

Input format

Output format

Topic analysis

Problem solving report ：

1. Ideas

2. Code

Today's topic ：  Three Kingdoms game

Title Description

Xiao Han likes computer games very much , These days he is playing a game called 《 three countries 》 The game of .

In the game , Xiaohan and the computer have their own side , Set up their own armies to fight . The game has  N  Military generals （N Be even and not less than 4）, Between any two generals there is one “ Tacit agreement ”, If the two generals fight together as a pair , How powerful the combination is . Before the game begins , All generals are free （ It's called a free general , Once a freearm is selected as a member of a certain army , Then he's no longer a free general ）, let me put it another way , The so-called liberal generals do not belong to either side .

Game begins , Xiaohan and the computer want to choose from the free generals to form their own army , The following rules ： Xiao Han chooses one of the free generals to join his army , And then the computer chooses one of the free forces to join the computer side . And then I've been following “ Xiaohan → Computer → Xiaohan →……” The order of the choice of generals , Until all the generals are divided equally . then , The program automatically selects a pair of military generals with the highest tacit understanding value from each army of both sides to conduct a two-to-two competition on behalf of their own army , A pair of generals with a higher tacit understanding wins , It means that the two armies are at war , The party with the winning generals wins .

It is known that the principle for the computer side to choose a general is to destroy as much as possible the strongest combination that the opponent will form in the next step , Its specific strategy is as follows ： Any time , It's the computer's turn to pick , It will try to match each of the generals in the opponent's army with each of the current free generals , Find out the pair of generals with the highest tacit understanding among all the matches , And select the freedom generals in this group into their own army . The following is an example of a computer's selection strategy , for example , There are altogether in the game 66 A general , The tacit understanding between them is shown in the table below ：

The selection process is as follows ：

Xiao Han wants to know , If the computer sticks to the above strategy in a game , Is it possible for you to win ？ If there is , In all the possible victories , What is the maximum tacit understanding value of their own pair of generals used for martial arts competition ？

Suppose the whole game , At any time, both sides of the war can see the generals of the free forces and those of the other army . To simplify the problem , Guarantee for different combinations of generals , Their tacit agreement values are not the same .

Input format

common N That's ok .

The first line is an even number  N, The number of generals .

The first  2 Go to the first place  N line , The first i+1 Yes Ni​ Nonnegative integers , Every two numbers are separated by a space , Express i No. 1 general and i+1,i+2,…,N The tacit understanding between No （0≤ Tacit agreement ≤1,000,000,000）.

Output format

common  1  or  2 That's ok .

If for a given game input , There is a selection order for Xiao Han to win , The output 1, And another line will output all winning cases , The maximum tacit understanding value of the military general combination finally selected by Xiaohan . If there is no general order that can make Xiao Han win , The output  0.

Topic analysis

questions ：️️

The topic involves algorithms ： greedy , Sort .

ps： Capable partners can try to optimize their own code or solve more than one problem , This can comprehensively improve their algorithm ability

Problem solving report ：

1. Ideas

The optimal solution is always every line （ After finishing ） The second largest one , According to greed , People can choose the biggest element in each line , At this time, it can also prevent the computer from selecting larger elements . At the same time, people will not lose .

2. Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[510][510];
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cin>>a[i][j];
            a[j][i] = a[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sort(a[i]+1,a[i]+1+n);
        if(a[i][n-1]>sum)
        {
            sum = a[i][n-1];
        }
    }
    cout<<"1"<<endl<<sum;
    return 0;
}