Scribd
Upload
23 views2 pages

Python Contest 1: Array Removal Challenge

The document describes a programming contest problem where participants must determine how many additional elements can be removed from an array after removing a specified element and setting the score to that element's value. The input consists of multiple test cases, each with an array of positive integers, and the output is the maximum number of additional elements removable for each element in the array. The problem emphasizes the need for efficient computation given constraints on the number of test cases and the size of the arrays.

Uploaded by

Antonio Zapata Solis
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views2 pages

Python Contest 1: Array Removal Challenge

The document describes a programming contest problem where participants must determine how many additional elements can be removed from an array after removing a specified element and setting the score to that element's value. The input consists of multiple test cases, each with an array of positive integers, and the output is the maximum number of additional elements removable for each element in the array. The problem emphasizes the need for efficient computation given constraints on the number of test cases and the size of the arrays.

Uploaded by

Antonio Zapata Solis
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Contest 1 - Curso de Python Oct 12, 2025

Problem A. Collecting Game


Time Limit 1000 ms
Mem Limit 262144 kB

You are given an array a of n positive integers and a score. If your score is greater than or
equal to ai , then you can increase your score by ai and remove ai from the array.
​ ​ ​

For each index i, output the maximum number of additional array elements that you can
remove if you remove ai and then set your score to ai . Note that the removal of ai should
​ ​ ​

not be counted in the answer.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 5000
) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 105 ) — the length of
the array.

The second line of each test case contains n integers a1 , a2 , … , an (1


​ ​ ​
≤ ai ≤ 109 ) — the
​

elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 105 .

Output

For each test case, output n integers, the i-th of which denotes the maximum number of
additional array elements that you can remove if you remove ai from the array and then
​

set your score to ai .


​

Examples

-
Contest 1 - Curso de Python Oct 12, 2025

Input Output

4 4 3 0 3 1
5 1 0 2
20 5 1 4 2 0
3 4 4 4 4 4
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000
1000000000

Note

In the first test case, the answers are as follows:

If we start with i = 4, our initial score is a4 = 4 and a = [20, 5, 1, 2]. We can remove 3
​

additional elements in the following order:

1. Since 4 ≥ 1, we can remove 1 and our score becomes 5. After this, a = [20, 5, 2].
2. Since 5 ≥ 5, we can remove 5 and our score becomes 10. After this, a = [20, 2].
3. Since 10 ≥ 2, we can remove 2 and our score becomes 12. After this, a = [20].

If we start with i = 1 we can remove all remaining elements in the array, so the answer is
4.

If we start with i = 2, we can remove 3 additional elements in the following order: 1, 4, 2.

If we start with i = 3, we can remove no additional elements.

If we start with i = 5, we can remove 1 additional element: 1.

You might also like