logoChat01.ai

give solution in cpp C. Coloring Game time limit ...

Créé le : 23 juin 2025

Répondu en utilisant O4 Mini High par Chat01

Question

give solution in cpp

C. Coloring Game
time limit per test2.5 seconds
memory limit per test256 megabytes
Alice and Bob are playing a game using an integer array a of size n.

Initially, all elements of the array are colorless. First, Alice chooses 3 elements and colors them red. Then Bob chooses any element and colors it blue (if it was red — recolor it). Alice wins if the sum of the red elements is strictly greater than the value of the blue element.

Your task is to calculate the number of ways that Alice can choose 3 elements in order to win regardless of Bob's actions.

Input
The first line contains a single integer t (1 \le t \le 1000) — the number of test cases.

The first line of each test case contains a single integer n (3 \le n \le 5000).

The second line contains n integers a_1, a_2, \dots, a_n (1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^5).

Additional constraint on the input: the sum of n over all test cases doesn't exceed 5000.

Output
For each test case, print a single integer — the number of ways that Alice can choose 3 elements in order to win regardless of Bob's actions.

Example
InputCopy
6
3
1 2 3
4
1 1 2 4
5
7 7 7 7 7
5
1 1 2 2 4
6
2 3 3 4 5 5
5
1 1 1 1 3
OutputCopy
0
0
10
2
16
0
Note
In the first two test cases, no matter which three elements Alice chooses, Bob will be able to paint one element blue so that Alice does not win.

In the third test case, Alice can choose any three elements. If Bob colors one of the red elements, the sum of red elements will be 14, and the sum of blue elements will be 7. If Bob chooses an uncolored element, the sum of red elements will be 21, and the sum of blue elements will be 7.

In the fourth test case, Alice can choose either the 1-st, 3-rd and 4-th element, or the 2-nd, 3-rd and 4-th element.

Réflexion

Analyzing game solution

The user asks for a solution in C++ for a game involving Alice and Bob, based on an integer array. Alice colors 3 elements red, and Bob colors 1 element blue. Alice wins if the sum of the red elements is strictly greater than the blue element, regardless of Bob's choice. You want to calculate how many ways Alice can choose her 3 red elements to ensure a win. The input involves multiple test cases, with n the size of the array (between 3 and 5000). I'll need to devise an efficient algorithm to manage multiple test cases.

Clarifying Alice vs. Bob's game mechanics

In this game setup, Alice picks three elements in the array to color red, and Bob picks one to color blue. The key is that Alice wins if the sum of the red elements is strictly greater than the blue element afterward — even if Bob chooses one of Alice's red elements. If Bob picks a red element, it loses its red color, leaving two red ones. The task is to count how many triples Alice can choose that guarantee her victory regardless of Bob's selection. I’ll need to carefully analyze the different scenarios that can arise here.

Clarifying strategy for Alice's winning triples

In this problem, I need to identify the conditions where Alice wins regardless of Bob’s choice. We have to find triples that ensure the sum of the red elements is never beaten by Bob’s blue element choice, whether it's one of Alice's red elements or an outside element. Alice wins if both S > 2a[k] and S > M_out, where S is the sum of Alice’s chosen red elements, a[k] is the largest in the triple, and M_out is the largest outside the triple. I'll need to calculate these conditions efficiently.

Counting valid triples

I’m thinking through counting the valid triples where certain conditions on sums hold. For cases when k < n, the key condition is that the sum of two chosen elements should exceed certain values like a[n] and 2*a[k]. Using a two-pointer approach, I need to count pairs in the array satisfying these conditions. The final approach will consider both cases for k < n and k = n to check all possible triples efficiently, with an O(n^2) complexity per test, which seems manageable given the constraints.

Thought for 40 seconds

Réponse

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        // Ensure the array is sorted (though input guarantees non-decreasing order)
        sort(a.begin(), a.end());

        ll ans = 0;
        // For each k as the index of the third red element (0-based)
        for (int k = 2; k < n; k++) {
            // T = max(a[k], a[n-1] - a[k])
            int T = max(a[k], a[n-1] - a[k]);
            // Count pairs (i, j) with 0 <= i < j < k and a[i] + a[j] > T
            int l = 0, r = k - 1;
            while (l < r) {
                if (a[l] + a[r] > T) {
                    // All pairs (l, l+1), (l, l+2), ..., (l, r-1) with r fixed
                    ans += (r - l);
                    r--;
                } else {
                    l++;
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

Explanation of the approach:

  1. Reformulating the win conditions
    Alice picks three indices i<j<ki<j<k. Let S=ai+aj+akS = a_i + a_j + a_k.

    • If Bob picks one of Alice's chosen indices (say kk), he removes that red element and colors it blue, leaving red sum S−akS - a_k. Alice needs S−ak>ak⟺S>2 ak. S - a_k > a_k \quad\Longleftrightarrow\quad S > 2\,a_k.
    • If Bob picks an element outside Alice's triple, say at index mm, the red sum remains SS, and Alice needs S>am. S > a_m. Bob will choose the largest outside element, which is an−1a_{n-1} if k=n−1k = n-1 or ana_{n} otherwise.

    Combining both, the necessary and sufficient condition for the triple (i,j,k)(i,j,k) to be safe is

    S>max⁡ ⁣(2 ak,  max⁡m∉{i,j,k}am). S > \max\!\bigl(2\,a_k,\;\max_{m \not\in\{i,j,k\}} a_m\bigr).

    One can show this reduces to

    ai+aj>max⁡(ak,  an−1−ak)(using 0-based indexing with n−1 as the last index). a_i + a_j > \max\bigl(a_k,\;a_{n-1} - a_k\bigr) \quad (\text{using 0-based indexing with }n-1\text{ as the last index}).

  2. Two-pointer counting

    • For each choice of the largest red index kk (from 2 to n−1n-1 in 0-based), compute
      T=max⁡(a[k], a[n−1]−a[k]).\displaystyle T = \max\bigl(a[k],\,a[n-1] - a[k]\bigr).
    • Count the number of pairs (i,j)(i,j) with 0≤i<j<k0 \le i < j < k such that a[i]+a[j]>Ta[i] + a[j] > T.
    • This is done in O(k)O(k) time per kk using the classic two-pointer technique on the sorted prefix a[0…k−1]a[0 \dots k-1].

  3. Complexity

    • Sorting each test is O(nlog⁡n)O(n\log n) (though input is already sorted).
    • The double loop with two-pointers is O(n2)O(n^2).
    • Since the sum of nn across all test cases is at most 5000, the overall time remains well within the 2.5 s limit.

This yields a total runtime of roughly O(∑n2)≤25×106O\bigl(\sum n^2\bigr)\le 25\times 10^6 operations, which is efficient enough under the given constraints.

Partager cette Q&R