Пояснение к примеру
В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в k = 2 раза.
Рассмотрим три случая: все три игрока набрали равное число баллов, все три игрока набрали попарно различное число баллов, либо два игрока из трех набрали равное число баллов, а у третьего количество баллов отлично от двух других.
Научимся находить количество вариантов счета в каждом из трех случаев, тогда получившиеся значения необходимо сложить. Отметим, что в подзадаче 1 выполнено условие, что k = 1, и, следовательно, имеет место только первый случай, а в подзадаче 3 все числа различны, и, следовательно, имеет место только второй случай. Этим можно воспользоваться для написания частичных решений для этих подзадач.
Поместим входные данные в массив и отсортируем его. Одним проходом по получившемуся массиву заменим числа на пары (xi, ci), где ci – количество раз, которое значение xi встречается на карточках у Андрея, xi во всех парах различны. Заметим, что массив пар получился отсортированным по по xi.
cin >> n >> k;
vector<long long> x(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
}
sort(x.begin(), x.end());
vector<pair<long long, int>> p;
int pr = -1;
for (int i = 0; i < n; i++) {
if (i == n - 1 || x[i] != x[i + 1]) {
p.push_back({x[i], i - pr});
pr = i;
}
}
int m = p.size();
Андрей может показать счет, в котором все три игрока набрали равное число баллов, в случае, если у него есть, хотя бы три карточки с этим числом баллов. Поэтому число таких вариантов, для которых можно показать счет, равно количеству чисел, которые встречаются хотя бы 3 раза.
Ниже приведен код на Си++, который считает число таких вариантов.
long long ans1 = 0;
for (int i = 0; i < m; i++) {
if (p[i].second >= 3) {
ans1++;
}
}
Для определения числа вариантов в остальных двух случаях требуется применить метод двух указателей. Для определения количества вариантов счета, в котором баллы всех игроков различны, сделаем следующее. Для каждого варианта максимального из баллов трех игроков найдем минимальное значение баллов другого игрока, которое можно показать, и оно не нарушает условия, что баллы различаются не более чем в k раз. Пусть для максимального значения xi соответствующее минимальное значение xj. Тогда два других значения баллов можно выбрать среди значений xj, xj+1,…, xj–1, то есть существует
(i – j)(i – j – 1) / 2 способов это сделать. Поскольку 3 различных числа можно упорядочить 6 способами, это число необходимо умножить на 6.
Просуммируем эти значения по всем i. Заметим, что при увеличении i значение j также может только увеличиваться, поэтому проход занимает O(n).
Приведем код на Си++, который подсчитывает это число вариантов.
long long ans2 = 0;
int j = 0;
for (int i = 0; i < m; i++) {
while (j < i && p[j].first * k < p[i].first) {
j++;
}
ans2 += 6LL * (i - j) * (i - j - 1) / 2;
}
Наконец, аналогичный метод применим для подсчета количества вариантов счета, когда два игрока набрали равное количество баллов, а третий игрок набрал отличное от них количество баллов.
long long ans3 = 0;
j = 0;
for (int i = 1; i < m; i++) {
while (j < i && p[j].first * k < p[i].first) {
j++;
}
if (p[i].second > 1) {
ans3 += 3 * (i - j);
}
}
j = m - 1;
for (int i = m - 2; i >= 0; i--) {
while (j > i && p[i].first * k < p[j].first) {
j--;
}
if (p[i].second > 1) {
ans3 += 3 * (j - i);
}
}
Для решения подзадачи 1 достаточно рассмотреть вариант, что у всех игроков одинаковое число баллов. Отметим, что дополнительное ограничение 1 ≤ xi ≤ 100 000 позволяет обойтись без сортировки пар или сложных структур данных и запоминать количество карточек с каждым числом в массиве.
Для решения подзадачи 2 можно перебрать все тройки карточек, для каждого варианта счета в трехмерном массиве отметить, можно ли получить этот счет, и вывести количество вариантов, которое можно получить.
Для решения подзадачи 3 требуется реализовать описанное выше решение, но не требуется разбирать случай, когда два игрока набрали равное число баллов.
