1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <stdio.h>
using namespace std;

  const int MAX = 40;

  void solveSquadRecursively(
      int armySize, int squadSize,
      int nRecruits, int recruits[],
      int foes, int areFoes[][MAX],
      int result[]) {
    if (foes > result[0]) {
      return;
    }
    if (nRecruits == squadSize) {
      if (foes < result[0]) {
        result[0] = foes;
        result[1] = 1;
      } else if (foes == result[0]) {
        result[1] += 1;
      }
      return;
    }

    // possible candidates for next recruit
    int firstCandidate = nRecruits == 0 ? 0 : recruits[nRecruits - 1] + 1;
    int lastCandidate = armySize - squadSize + nRecruits;
    for (int candidate = firstCandidate; candidate <= lastCandidate; candidate++) {
      int candidateFoes = 0;
      for (int recruit = 0; recruit < nRecruits; recruit++) {
        candidateFoes += areFoes[candidate][recruits[recruit]];
      }
      recruits[nRecruits] = candidate;
      solveSquadRecursively(
          armySize, squadSize,
          nRecruits + 1, recruits,
          foes + candidateFoes, areFoes,
          result);
    }
  }

  void solveSquad(int armySize, int squadSize, int areFoes[][MAX]) {
    int recruits[squadSize];
    int result[2];
    result[0] = 1000000;
    result[1] = 0;
    solveSquadRecursively(
        armySize, squadSize,
        0, recruits,
        0, areFoes,
        result);

    printf("%d %d\n", result[0], result[1]);
  }

  void solveArmy(int armySize, int areFoes[][MAX]) {
    for (int squadSize = 1; squadSize <= armySize; squadSize++) {
      solveSquad(armySize, squadSize, areFoes);
    }
  }

  void orderSoldiersByFoes(int armySize, int areFoes[][MAX]) {
    int numberOfFoes[armySize];
    for (int soldier = 0; soldier < armySize; soldier++) {
      numberOfFoes[soldier] = 0;
    }
    for (int soldierA = 0; soldierA < armySize; soldierA++) {
      for (int soldierB = 0; soldierB < armySize; soldierB++) {
        numberOfFoes[soldierA] += areFoes[soldierA][soldierB];
      }
    }

    int ranking[armySize];
    for (int slot = 0; slot < armySize; slot++) {
      int leastFoes = 1000;
      int soldierWithLeastFoes = -1;
      for (int soldier = 0; soldier < armySize; soldier++) {
        if (numberOfFoes[soldier] < leastFoes) {
          soldierWithLeastFoes = soldier;
          leastFoes = numberOfFoes[soldier];
        }
      }
      ranking[slot] = soldierWithLeastFoes;
      // destroys numberOfFoes array
      numberOfFoes[soldierWithLeastFoes] = 1000;
    }

    int areFoesByRank[armySize][armySize];
    for (int rank = 0; rank < armySize; rank++) {
      areFoesByRank[rank][rank] = 0;
      for (int partner = 0; partner < rank; partner++) {
        areFoesByRank[rank][partner] = areFoesByRank[partner][rank] = areFoes[ranking[rank]][ranking[partner]];
      }
    }
    for (int soldierA = 0; soldierA < armySize; soldierA++) {
      for (int soldierB = 0; soldierB < armySize; soldierB++) {
        areFoes[soldierA][soldierB] = areFoesByRank[soldierA][soldierB];
      }
    }
  }

  int main() {
    int armySize;
    cin >> armySize;

    int skills[armySize];
    for (int soldier = 0; soldier < armySize; soldier++) {
      cin >> skills[soldier];
    }

    int areFoes[MAX][MAX];
    for (int soldierA = 0; soldierA < armySize; soldierA++) {
      for (int soldierB = 0; soldierB < armySize; soldierB++) {
        if ((soldierA - soldierB) * ((skills[soldierA] - skills[soldierB])) < 0) {
          areFoes[soldierA][soldierB] = 1;
        } else {
          areFoes[soldierA][soldierB] = 0;
        }
      }
    }

    orderSoldiersByFoes(armySize, areFoes);
    solveArmy(armySize, areFoes);
    return 0;
  }