Algorithm

 problem Link :  https://www.codechef.com/problems/WEEDING 

Problem

Chef purchased a new herbicide, and now wants to test its effectiveness.

Initially, there are no weeds in Chef's garden.
For each �=1,2,3,…,�, exactly one new weed will pop up in the garden at the start of day ��.
It is known that �1<�2<…<��.

Chef can spray the herbicide at most once per day.
Any weed that receives the spray � or more times in total will die.

Chef would like to know: is it possible that after � days, all the weeds are gone?

Input Format

  • The first line of input will contain a single integer �, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains three space-separated integers �, �, and � — the number of weeds, the total number of days, and the number of sprays needed to kill a weed, respectively.
    • The second line of each test case contains � space-separated integers �1,�2,…,��: the days on which new weeds show up.

Output Format

For each test case, output on a new line the answer: Yes if all the weeds are gone after � days, and No otherwise.

Each letter of the output may be printed in either uppercase or lowercase, i.e, the strings Yes, YES, yes, and YeS will all be treated as equivalent.

Constraints

  • 1≤�≤105
  • 1≤�≤105
  • 1≤�1<�2<�3<…<��≤�≤109
  • 1≤�≤109
  • The sum of � across all tests won't exceed 2⋅105.

Sample 1:

Input
 
Output
 
3
3 10 1
4 7 10
3 10 2
4 7 10
4 10 5
1 2 3 4

Yes
No
Yes

Explanation:

Test case 1: Each weed needs only one spray to be killed. So, Chef can spray the herbicide whenever a weed pops up and it will die the same day.

Test case 2: Each weed needs two sprays to be killed.
The last weed shows up on day 10, and there's not enough time to kill it by day 10 since it can only be sprayed once.

Test case 3: Chef can spray the herbicide every day; and all the weeds will be dead by day 10.

Code Examples

#1 Code Example with C Programming

Code - C Programming

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

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int weed=0;
    for (int i=0; i  <  n; ++i)
    {
        int x;
        cin >> x;
        weed=max(x,weed);
    }
    if(weed+k<=m+1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

    int TC = 1;
    cin >> TC;
    cin.ignore();
    while (TC--)
        solve(>;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
3 10 1
4 7 10
3 10 2
4 7 10
4 10 5
1 2 3 4

Output

x
–
+
cmd
Yes
No
Yes
Advertisements

Demonstration

CodeChef solution WEEDING  - Weeding Codechef solution in C,C++

Previous
CodeChef solution CS2023_GIFT - The Gift Codechef solution in C,C++
Next
CodeChef solution PILBELLS - Bells of Pilgrimage Codechef solution in C,C++