Cod sursa(job #2753606)

Utilizator andrei.gatejAndrei Gatej andrei.gatej Data 23 mai 2021 17:17:26
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>

using namespace std;

ifstream f("farfurii.in");
ofstream g("farfurii.out");

long N, K;

// It is known that if D(p1) > D(p2)(where D(p) = the dimension of a plate),
// then we add a cutlery item
// So the problem boils down to determining the maximum number of `x > y` cases
// from a total number of `1...N` cases
// For example, if N = 4, the maximum number of `x > y` cases can be achieved with this permutation:
// 4 3 2 1, because we have these pairs: (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1) = 6 cases
// It can be noticed that this number can be computed as: `1 + 2 + ... + N - 1`(N - 1 because there is no greater number than N)
long getMaxNrOfCombinations (long n) {
  return n * (n - 1) / 2;
}

int main () {
  f >> N >> K;

  long maxNeeded = 1;
  while (getMaxNrOfCombinations(maxNeeded) < K) {
    maxNeeded++;
  }

  // Suppose `N = 7` and `maxNeeded = 5`. Because the lexicographic order is important,
  // we only want to deal with the last `maxNeeded` numbers.
  long remaining = N - maxNeeded;
  for (long i = 1; i <= remaining; i++) {
    g << i << ' ';
  }

  // At this point, with `maxNeeded` we can determine a number of `x > y` cases
  // that is >= K
  long casesCount = getMaxNrOfCombinations(maxNeeded);

  // At this point, we need to find the proper way to display the numbers
  // The numbers we're dealing with are within the `remaning...N` range
  // If `exceedingCasesCount == 0`, then we can display the remaning numbers in descending order
  // Otherwise, we must change some positions. Continuing with the above example,
  // we'd need to adjust these numbers: `7 6 5 4 3`(if exceedingCasesCount is 0, that would be the order)
  // `getMaxNrOfCombinations(5)` returns `10`, so `7 6 5 4 3` covers 10 cases(or pairs) when `x > y`.
  // But if we had `6 7 5 4 3`(exceedingCasesCount = 1), there would be 9.
  // If we had `5 7 6 4 3` (exceedingCasesCount = 2), 8.
  // So, the leftmost element is given by `N - exceedingCasesCount`
  long exceedingCasesCount = casesCount - K;
  long leftmost = N - exceedingCasesCount;
  g << leftmost << ' ';

  for (long i = N; i > remaining; i--) {
    if (i == leftmost) {
      continue;
    }

    g << i << ' ';
  }

  f.close();
  g.close();
}