Problems in your to-do list

editorial
, , , , , , ,
1

Problems in your to-do list
Difficulty: 580

CodeChef recently revamped its practice page to make it easier for users to identify the next problems they should solve by introducing some new features:

  • Recent Contest Problems - contains only problems from the last 2 contests
  • Separate Un-Attempted, Attempted, and All tabs
  • Problem Difficulty Rating - the Recommended dropdown menu has various difficulty ranges so that you can attempt the problems most suited to your experience
  • Popular Topics and Tags

Like most users, Chef didn’t know that he could add problems to a personal to-do list by clicking on the magic ‘+’ symbol on the top-right of each problem page. But once he found out about it, he went crazy and added loads of problems to his to-do list without looking at their difficulty rating.

Chef is a beginner and should ideally try and solve only problems with difficulty rating strictly less than 10001000. Given a list of difficulty ratings for problems in the Chef’s to-do list, please help him identify how many of those problems Chef should remove from his to-do list, so that he is only left with problems of difficulty rating less than 10001000.

Input Format

  • The first line of input will contain a single integer TT, the number of test cases. Then the testcases follow.
  • Each testcase consists of 2 lines of input.
  • The first line of input of each test case contains a single integer, NN, which is the total number of problems that the Chef has added to his to-do list.
  • The second line of input of each test case contains NN space-separated integers D1,D2,…,DND1​,D2​,…,DN​, which are the difficulty ratings for each problem in the to-do list.

Output Format

For each test case, output in a single line the number of problems that Chef will have to remove so that all remaining problems have a difficulty rating strictly less than 10001000.

Constraints

  • 1≤T≤10001≤T≤1000
  • 1≤N≤10001≤N≤1000
  • 1≤Di≤50001≤Di​≤5000

Subtasks

  • Subtask 1 (100 points):
    • Original constraints

Sample 1:

Input

5
3
800 1200 900
4
999 1000 1001 1002
5
1 2 2 2 5000
5
1000 1000 1000 1000 1000
3
900 700 800

Output

1
3
1
5
0

Explanation:

Test case 11: Among the three difficulty ratings, Chef only needs to remove the problem with difficulty rating 12001200, since it is ≥1000≥1000. So, the answer is 11.

Test case 22: Among the four difficulty ratings, Chef needs to remove the problems with difficulty ratings of 10001000, 10011001, and 10021002, since they are ≥1000≥1000. So, the answer is 33.

Test case 33: Among the five difficulty ratings, Chef needs to remove the problem with a difficulty rating of 50005000, since it is ≥1000≥1000. So, the answer is 11.

Test case 44: Chef needs to remove all the five problems, since they are all rated ≥1000≥1000. So, the answer is 55.

Test case 55: Chef does not need to remove any problem, since they are all rated <1000<1000. So, the answer is 00.

Solution :

T = int(input())
for _ in range(T):
N = int(input())
D = list(map(int, input().split()))
count = sum(1 for d in D if d >= 1000)
print(count)

Explanation of the Solution:

This code helps Chef filter out problems from his to-do list based on their difficulty ratings. Chef is a beginner and should only try solving problems with a difficulty rating less than 1000.

Here’s how the code works step-by-step:

  1. Input the number of test cases (T):
  • The first line of input contains an integer T, which represents the number of test cases. We store this value in the variable T.
  1. Loop through each test case:
  • For each test case, the code performs the following operations. The loop for _ in range(T): ensures that we process each test case one by one.
  1. Input the number of problems (N):
  • The first line inside the loop reads an integer N, which represents how many problems Chef has added to his to-do list for the current test case.
  1. Input the difficulty ratings of the problems:
  • The next line contains N space-separated integers, which are the difficulty ratings of the problems. These are stored in a list called D.
  1. Count the problems Chef should remove:
  • The code uses the following line to count how many problems have a difficulty rating of 1000 or more:

python

Copy

count = sum(1 for d in D if d >= 1000)
  • This line works by checking each difficulty rating d in the list D. If d is greater than or equal to 1000, it adds 1 to the sum. The result is the number of problems Chef needs to remove.
  1. Output the result:
  • Finally, the program prints the value of count, which is the number of problems Chef should remove for the current test case.

Example:

Input:

yaml

Copy

5
3
800 1200 900
4
999 1000 1001 1002
5
1 2 2 2 5000
5
1000 1000 1000 1000 1000
3
900 700 800

Output:

Copy

1
3
1
5
0

Explanation of the Example:

  • Test Case 1: Chef has 3 problems with difficulty ratings: [800, 1200, 900]. Only one problem (1200) has difficulty >= 1000. So, Chef needs to remove 1 problem.
  • Test Case 2: Chef has 4 problems with difficulty ratings: [999, 1000, 1001, 1002]. Three problems have difficulty >= 1000. So, Chef needs to remove 3 problems.
  • Test Case 3: Chef has 5 problems with difficulty ratings: [1, 2, 2, 2, 5000]. Only one problem (5000) has difficulty >= 1000. So, Chef needs to remove 1 problem.
  • Test Case 4: Chef has 5 problems, all with difficulty 1000. So, Chef needs to remove all 5 problems.
  • Test Case 5: All the problems have difficulty <= 1000. Chef doesn’t need to remove any problems.

Time Complexity:

  • For each test case, the program checks the difficulty of each problem. This takes O(N) time for each test case, where N is the number of problems in the current test case.
  • The overall time complexity for T test cases is O(T * N).

Conclusion:

This solution processes each test case efficiently and provides the correct number of problems Chef needs to remove, based on their difficulty ratings.