Pagini recente » Cod sursa (job #1596339) | Cod sursa (job #1041614) | Cod sursa (job #2643065) | Cod sursa (job #2138444) | Cod sursa (job #2753604)
#include <fstream>
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int 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)
int getMaxNrOfCombinations (int n) {
return n * (n - 1) / 2;
}
int main () {
f >> N >> K;
int 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.
int remaining = N - maxNeeded;
for (int i = 1; i <= remaining; i++) {
g << i << ' ';
}
// At this point, with `maxNeeded` we can determine a number of `x > y` cases
// that is >= K
int 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`
int exceedingCasesCount = casesCount - K;
int leftmost = N - exceedingCasesCount;
g << leftmost << ' ';
for (int i = N; i > remaining; i--) {
if (i == leftmost) {
continue;
}
g << i << ' ';
}
f.close();
g.close();
}