country_of_fools.cpp

#include <iostream>

using namespace std;

// region Debug

// Если верен - на каждой итерации выводится не только её результат, но ещё и состояния всех бинов
bool debug = true;

/**
 * Выводит текущее состояние ведер
 *
 * @param bins
 * @param size
 */
void printBins(int bins[], int size) {
  if (!debug) {
    return;
  }

  cout << endl << "{ ";
  for (int i = 0; i < size; i++) {
    cout << bins[i] << ' ';
  }
  cout << "}\t";
}

// endregion

// region Helpers

/**
 * Короче, нам нужен reverse quickSort, а не вот это.
 * В интернетах можно почитать, куда нужно вставить условие для инвертирования
 *
 * @param arr
 * @param left
 * @param right
 */
void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }

    while (arr[j] > pivot) {
      j--;
    }

    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  };

  if (left < j) {
    quickSort(arr, left, j);
  }

  if (i < right) {
    quickSort(arr, i, right);
  }
}

/**
 * Выводит индекс элемента
 *
 * @param index
 */
void printIndex(int index) {
  cout << ++index << ' ';
}

// endregion

/**
 * Штука, которая инвертирует массив
 *
 * @param arr
 * @param arrSize
 */
void inverse_reorder (int * arr, int arrSize){
  int i;
  int temp = 0;
  for ( i = 0; i < arrSize ; i++ ){
    temp = *(arr+i);
    *(arr+i) = *(arr + arrSize - i);
    *(arr + arrSize - i) = temp;
  }
}

/**
 * Алгоритм состоит из 4х путей развития на каждой итерации%
 * 1) max_bin_lengths_amount > 1                                            - выводим всех первых жирняков
 * 2) max_bin_lengths_amount == 1 && second_max_bin_lengths_amount > 1      - чередуем первого жирняка с вторыми жирняками (на каждой итерации выводится первый жирняк и последний второй жирняк [ max_bin_index, 1 + second_max_bin_lengths_amount - 1 ], чтобы не было сложных условий)
 * 3) max_bin_lengths_amount == 1 && second_max_bin_lengths_amount == 1     - выводим первого и второго жирняка
 * 4) max_bin_lengths_amount == 1 && second_max_bin_lengths_amount == 0     - выводим только первого жирняка (граничный случай)
 *
 * nshkaruba: ez clap
 *
 * @param bins
 * @param size
 */
void solveCountryOfFools(int bins[], int size) {
//  quickSort(bins, 0, size -1);
//  inverse_reorder(bins, size);

  while (bins[0] != 0) {
    printBins(bins, size);

    int max_bin_length = bins[0];
    int max_bin_lengths_amount = 1;

    int second_max_bin_length = 0;
    int second_max_bin_lengths_amount = 0;

    // Считаем, сколько у нас max_bin_lengths_amount
    for (int i = 1; i < size; i++) {
      if (bins[i] < max_bin_length) {
        second_max_bin_length = bins[i];
        second_max_bin_lengths_amount = 1;

        // Считаем, сколько у нас second_max_bin_lengths_amount
        for (int j = i + 1; j < size; j++) {
          if (bins[j] != second_max_bin_length) {
            break;
          }
          second_max_bin_lengths_amount++;
        }

        break;
      } else {
        max_bin_lengths_amount++;
      }
    }

    // Путь 1
    if (max_bin_lengths_amount > 1) {
      for (int i = 0; i < max_bin_lengths_amount; i++) {
        printIndex(i);
        bins[i]--;
      }
    } else {
      int max_bin_index = 0;

      // Путь 4
      if (second_max_bin_lengths_amount == 0) {
        printIndex(max_bin_index);
        bins[max_bin_index]--;

      // Путь 2
      } else if (second_max_bin_lengths_amount > 1) {
        printIndex(max_bin_index);
        bins[max_bin_index]--;

        int last_second_bin_index = 1 + second_max_bin_lengths_amount - 1;
        printIndex(last_second_bin_index);
        bins[last_second_bin_index]--;

      // Путь 3 - здесь second_max_bin_lengths_amount == 1
      } else {
        printIndex(max_bin_index);
        bins[max_bin_index]--;

        int second_max_bin_index = 1;
        printIndex(second_max_bin_index);
        bins[second_max_bin_index]--;
      }
    }
  }
}

bool test() {
  const int bins_size = 3;
  int bins[bins_size] = { 20, 17, 5 };

  solveCountryOfFools(bins, bins_size);
}

int main() {
  test();

  return 0;
}