There are N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith problem has estimated difficulty level i. You have also assigned a rating vi to each problem. Problems with similar vi values are similar in nature. On each day, you will choose a subset of the problems and solve them. You've decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Also, to make it less boring, consecutive problems you solve should differ in their vi rating by at least K. What is the least number of days in which you can solve all problems? Input Format The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line. Constraints 1 <= T <= 100 1 <= N <= 300 1 <= vi <= 1000 1 <= K <= 1000 Output Format Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved. Sample Input 2 3 2 5 4 7 5 1 5 3 4 5 6 Sample Output 2 1 Explanation For the first example, you can solve the problems with rating 5 and 7 on the first day and the problem with rating 4 on the next day. Note that the problems with rating 5 and 4 cannot be completed consecutively because the ratings should differ by at least K (which is 2). Also, the problems cannot be completed in order 5,7,4 in one day because the problems solved on a day should be in increasing difficulty level. For the second example, all problems can be solved on the same day.     #include  using namespace std; string ltrim(const string &); string rtrim(const string &); vector split(const string &); /*  * Complete the 'problemSolving' function below.  *  * The function is expected to return an INTEGER.  * The function accepts following parameters:  *  1. INTEGER k  *  2. INTEGER_ARRAY v  */ int problemSolving(int k, vector v) { } int main() {     ofstream fout(getenv("OUTPUT_PATH"));     string t_temp;     getline(cin, t_temp);     int t = stoi(ltrim(rtrim(t_temp)));     string first_multiple_input_temp;     getline(cin, first_multiple_input_temp);     vector first_multiple_input = split(rtrim(first_multiple_input_temp));     int n = stoi(first_multiple_input[0]);     int k = stoi(first_multiple_input[1]);     string v_temp_temp;     getline(cin, v_temp_temp);     vector v_temp = split(rtrim(v_temp_temp));     vector v(n);     for (int i = 0; i < n; i++) {         int v_item = stoi(v_temp[i]);         v[i] = v_item;     }     int result = problemSolving(k, v);     fout << result << "\n";     fout.close();     return 0; } string ltrim(const string &str) {     string s(str);     s.erase(         s.begin(),         find_if(s.begin(), s.end(), not1(ptr_fun(isspace)))     );     return s; } string rtrim(const string &str) {     string s(str);     s.erase(         find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base(),         s.end()     );     return s; } vector split(const string &str) {     vector tokens;     string::size_type start = 0;     string::size_type end = 0;     while ((end = str.find(" ", start)) != string::npos) {         tokens.push_back(str.substr(start, end - start));         start = end + 1;     }     tokens.push_back(str.substr(start));     return tokens; }

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

There are N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith problem has estimated difficulty level i. You have also assigned a rating vi to each problem. Problems with similar vi values are similar in nature. On each day, you will choose a subset of the problems and solve them. You've decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Also, to make it less boring, consecutive problems you solve should differ in their vi rating by at least K. What is the least number of days in which you can solve all problems?

Input Format

The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line.

Constraints

1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

Output Format

Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved.

Sample Input

2 3 2 5 4 7 5 1 5 3 4 5 6

Sample Output

2 1

Explanation

For the first example, you can solve the problems with rating 5 and 7 on the first day and the problem with rating 4 on the next day. Note that the problems with rating 5 and 4 cannot be completed consecutively because the ratings should differ by at least K (which is 2). Also, the problems cannot be completed in order 5,7,4 in one day because the problems solved on a day should be in increasing difficulty level.

For the second example, all problems can be solved on the same day.

 

 

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'problemSolving' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY v
 */

int problemSolving(int k, vector<int> v) {

}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    getline(cin, t_temp);

    int t = stoi(ltrim(rtrim(t_temp)));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int k = stoi(first_multiple_input[1]);

    string v_temp_temp;
    getline(cin, v_temp_temp);

    vector<string> v_temp = split(rtrim(v_temp_temp));

    vector<int> v(n);

    for (int i = 0; i < n; i++) {
        int v_item = stoi(v_temp[i]);

        v[i] = v_item;
    }

    int result = problemSolving(k, v);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 1 images

Blurred answer
Knowledge Booster
Troubleshooting
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education