logoChat01.ai

Alice and Bob are playing a game using an integer ...

Criado em: 23 de junho de 2025

Respondido usando O4 Mini High por Chat01

Pergunta

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≤t≤1000
) — the number of test cases.

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

The second line contains n
integers a1,a2,…,an
(1≤a1≤a2≤⋯≤an≤105
).

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.

code in java

Pensamento

Creating Java code

The user asks for a Java solution to a game problem. Specifically, Alice needs to select 3 elements that will guarantee her win against Bob. Since there's no request for an explanation, I'll focus on delivering the Java code directly. Being mindful of the task at hand, it seems a good idea to create a clean code file within the canvas. I'll produce the solution with the required logic and structure, avoiding extra explanation. Let's go ahead and write the code!

Defining conditions for Alice's winning strategy

For Alice to guarantee her win, we need two conditions:

  1. If any element is outside the triple, the sum of red elements (S) must be greater than the largest element outside the triple.
  2. If the element is inside the triple, the sum should be greater than twice the largest element inside the triple.

For these conditions, we define two values:

  • The maximum outside the triple, denoted M_out.
  • The largest element inside the triple, represented as m.

The final condition becomes: S>max⁡(Mout,2×m)S > \max(M_{out}, 2 \times m). We also need to account for sorting and index behavior in the code.

Refining condition checks for Alice's winning strategy

The conditions for Alice’s winning strategy involve checking two key aspects:

  1. Inside the triple: Alice needs S>2×a[k]S > 2 \times a[k], where a[k]a[k] is the maximum element in the triple.
  2. Outside the triple: Alice needs S>a[p]S > a[p], where pp is any element not in the triple, and a[p]a[p] is the maximum among those.

For the triple elements, the worst-case scenario occurs when the largest element is used, and for outside elements, the sum must exceed the largest non-selected element.

Thought for 39 seconds

Resposta

java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] a = new int[n];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }
            // Input is guaranteed sorted non-decreasing; no need to sort.

            long ans = 0;
            int max1 = a[n - 1];
            int max2 = (n >= 2 ? a[n - 2] : 0);

            // Iterate over k, the index of the largest red element
            for (int k = 2; k < n; k++) {
                int ak = a[k];
                // Determine Bob's best outside choice
                int mout = (k == n - 1 ? max2 : max1);
                int threshold = Math.max(mout, 2 * ak);
                // We need a[i] + a[j] + a[k] > threshold
                // Equivalently, a[i] + a[j] > threshold - a[k]
                int target = threshold - ak;

                // Two-pointer count of pairs (i < j < k) with a[i] + a[j] > target
                int left = 0, right = k - 1;
                while (left < right) {
                    if (a[left] + a[right] > target) {
                        // All pairs (left, left+1 ... right-1) with this right are valid
                        ans += (right - left);
                        right--;
                    } else {
                        left++;
                    }
                }
            }

            sb.append(ans).append('\n');
        }

        System.out.print(sb.toString());
    }
}

Compartilhar esta Q&A