2022 robocom world robot developer competition - undergraduate group (provincial competition) rc-u4 strategy team (completed)

Other topics

subject

RC-u4 Strategic team

Copy is a feature of the game , It mainly brings equipment to players 、 The props 、 Output of game resources , Meet the players' game progress .

stay MMORPG《 Final fantasy 14》 in , There is a strategy with a maximum number of 56 Copies of people “ Valdsion Bingwu tower ”, Because death cannot be revived in the copy 、 The mechanism is relatively tricky , Once regarded as a beast by players .

At the beginning of the copy , We will encounter the first difficulty ： The players of the strategy should be divided into two groups , At the same time, crusade against the copy BOSS “ Owen ” and “ Art ”.

The following information is known ：

1. Players will form 6 Teams enter the dungeon , Among them the first i Team has Vi Players （i=1,⋯,6）.
2. Each team may have some special roles ：MT（ Main tank ）、 engineers （ Responsible for detecting traps ） And command （ Be responsible for commanding players ）.

Our task is to reasonably arrange the grouping of players , To maximize the probability of copy passing . The principle of grouping is as follows ：

1. Divide all teams into 2 Group , Each team must belong to only one group ;
2. Each group must There is at least one MT（ Main tank ）.

If the grouping scheme meeting the above principles is not unique , Then the unique solution is determined according to the following rules ：

1. Give priority to the scheme with at least one commander and at least one engineer in each group ;
2. If the rules 1 Unable to meet , Then the scheme with at least one commander in each group is preferred ;
3. If all schemes do not meet the rules 2, Or before passing 2 After filtering by rules , The grouping scheme is still not unique , Choose the number of people on both sides as close as possible （ That is, the difference in the number of people on both sides should be as small as possible ） The plan ;
4. If the rules are met 3 Our plan is not unique , Choose to crusade “ Owen ” There are more people than Crusades “ Art ” The number of more programs ;
5. If the rules are met 4 Our plan is not unique , Choose to crusade “ Owen ” The smallest of the team Numbering schemes .

notes : A team numbering scheme A = {a1 < ··· < am} Than B = {b1 < ··· bn} Small , If and only if there is 1 <= k <= min(m, n) bring ai = bi, For all 0 < i < k establish , And ak < bk.
In this question, please give the allocation scheme that meets all grouping principles .

Input format :
The first line of input is given 6 Number of players in each team , namely 6 Nonnegative integers V i(0≤Vi≤8,1≤i≤6). The number of people in the team is 0 Time means that the team does not exist .

And then 6 That's ok , In the order of team number , Each line gives a special role for a team , The format is ABC, among A Corresponding MT,B Corresponding to engineers ,C Corresponding command . The corresponding values of the three roles 0 or 1,0 Indicates that there is no such role ,1 Express .

notes ： Because there may be a situation where one person concurrently holds multiple special roles , Therefore, the number of special characters in a team may be greater than the number of players in the team .

Output format :
The output is divided into two lines , The first line outputs Crusade “ Owen ” Team number of , The second line outputs Crusade “ Art ” Team number of . The numbers in the same row are output in ascending order , With 1 Space separation , There must be no extra space at the beginning and end of the line .

If there is no legal solution , Output GG.

sample input 1:

6 8 7 5 3 0
010
101
110
001
111
000

sample output 1:

2 3
1 4 5

sample input 2:

6 8 7 5 3 0
010
101
010
001
011
000

sample output 2:

GG

Answer key

summary
The idea of this problem is very simple , But the logic processing is very complex .
The basic idea is violent search , We enumerate each scheme , Compare the scheme with the best one at present , Update the optimal scheme to the best of the two

enumeration
Put a set of sequences （1~6） In two parts , We can use dfs+ Backtracking to achieve
Suppose the two groups to be divided are t1, t2
For each number in the sequence , There are two options : Get into t1 Or enter t2. So let's put the current numbers into t1 and t2, Then continue to enumerate the next number , When the six numbers are enumerated, we get a combination , At this point, we will judge the current combination and the optimal combination

vector<int> tmp1, tmp2;// Store the members of two groups 

void dfs(int i)//i Number the team 
{
    
    if(i > 6)// Enumeration done ,  Judge 
    {
    
        judge();
        return;
    }
    if(num[i] == 0)// The current team is empty ,  Just skip 
    {
    
        dfs(i+1);
        return;
    }
    
    // When i Join in t1
    tmp1.push_back(i);
    dfs(i+1);
    tmp1.pop_back();

    // When i Join in t2
    tmp2.push_back(i);
    dfs(i+1);
    tmp2.pop_back();
}

Judge
Too long and complex , Please jump to the program comment
To avoid multiple nested loops , It is widely used in the program return, Every time return All represent the end of the current judgment

AC Code ( With comments )

Although it's long, it's easy to understand

#include <bits/stdc++.h>

using namespace std;
const int N = 7;
int num[N];// The number of each team 
bool A[N], B[N], C[N];// Whether each team has tanks 、 engineers 、 command 
int totalA;// The total number of tanks 

// The best solution at present , 1、2  Corresponding   Owen 、 Art 
vector<int> ans1, ans2;
/* RO, R1, R2 Corresponding to the properties required by the first three rules  * R0:  Is it satisfactory?   Each group must have at least one  MT（ Main tank ）. * R1:  Is it satisfactory?   Each group has at least one commander and at least one engineer  * R2:  Is it satisfactory?   At least one conductor in each group  */
bool R0, R1, R2;


vector<int> tmp1, tmp2;// The current scheme to be judged 

void judge()
{
    
    // Everyone is in a group ,  Does not meet the grouping requirements ,  immediate withdrawal 
    if(tmp1.empty() || tmp2.empty()) return;

    // Of the current scheme r0, r1, r2 nature ,  And temporary variables t1, t2
    bool r0, r1, r2, t1, t2;

    // Judge the solution r0 nature 
    t1 = t2 = false;
    for(int i : tmp1)
        if( A[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( A[i] ) {
    
            t2 = true;
            break;
        }
    r0 = t1 && t2;
    if(!r0) return;//r0 It's hard requirements ,  Don't consider directly if you are not satisfied 

    // Judge the solution r2 nature ,  First judge r2 Because r2 yes r1 Component part 
    t1 = t2 = false;
    for(int i : tmp1)
        if( C[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( C[i] ) {
    
            t2 = true;
            break;
        }
    r2 = t1 && t2;

    // Judge the solution r1 nature 
    t1 = t2 = false;
    for(int i : tmp1)
        if( B[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( B[i] ) {
    
            t2 = true;
            break;
        }
    r1 = r2 && t1 && t2;

    // The rules 0, R0 by false It indicates that the optimal scheme is empty 
    if( !R0 )
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    // The rules 1
    if(R1 && !r1) return;
    if(r1 && !R1)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    // Do not meet the rules 1 Execute rules when 2
    if(!R1 && !r1)
    {
    
        if(R2 && !r2) return;
        if(r2 && !R2)
        {
    
            ans1 = tmp1, ans2 = tmp2;
            R0 = r0, R1 = r1, R2 = r2;
            return;
        }
    }

    // The rules 3
    int an1 = 0, an2 = 0, tn1 = 0, tn2 = 0;// Number of people in each group 
    for(int i : ans1) an1 += num[i];
    for(int i : ans2) an2 += num[i];
    for(int i : tmp1) tn1 += num[i];
    for(int i : tmp2) tn2 += num[i];
    
    int d1 = abs(an1 - an2), d2 = abs(tn1 - tn2);// The number of people is poor 
    if(d1 < d2) return;
    if(d1 > d2)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    // Rule 4 
    t1 = (an1 > an2), t2 = (tn1 > tn2);
    if(t1 && !t2) return;
    if(t2 && !t1)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }
    
    // The rules 5
    for(int k=0; k<ans1.size() && k < tmp1.size(); k++)
    {
    
        if(ans1[k] < tmp1[k]) return;
        else if(ans1[k] > tmp1[k])
        {
    
            ans1 = tmp1, ans2 = tmp2;
            R0 = r0, R1 = r1, R2 = r2;
            return;
        }
    }
    /*  It can be found that although the code is long ,  But it's almost the same   Basically is :  If the optimal scheme satisfies a certain rule and the current scheme does not ,  The judgment is over   If the optimal scheme does not meet a certain rule and the current scheme meets ,  Then the current scheme replaces the optimal scheme ,  The judgment is over   If all is satisfied ,  Execute the next rule  */
}

void dfs(int i)
{
    
    if(i > 6)
    {
    
        judge();
        return;
    }
    if(num[i] == 0)
    {
    
        dfs(i+1);
        return;
    }
    tmp1.push_back(i);
    dfs(i+1);
    tmp1.pop_back();

    tmp2.push_back(i);
    dfs(i+1);
    tmp2.pop_back();
}

int main()
{
    
    for(int i=1; i<=6; i++)
        cin >> num[i];
    string ABC;
    for(int i=1; i<=6; i++)
    {
    
        cin >> ABC;
        if(ABC[0] == '1') A[i] = true, totalA++;
        if(ABC[1] == '1') B[i] = true;
        if(ABC[2] == '1') C[i] = true;
    }
    if(totalA < 2)// appear GG There are and only less than two teams have tanks 
    {
    
        cout << "GG";
        return 0;
    }
    else
    {
    
        dfs(1);
        for(int i=0; i<ans1.size(); i++)
        {
    
            if(i != 0) cout << " ";
            cout << ans1[i];
        }
        cout << endl;
        for(int i=0; i<ans2.size(); i++)
        {
    
            if(i != 0) cout << " ";
            cout << ans2[i];
        }
    }
    return 0;
}

The above code can AC, Welcome to discuss and exchange if you have any questions