• + 0 comments

    Here is my simple solution:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    string ltrim(const string &);
    string rtrim(const string &);
    vector<string> split(const string &);
    
    /*
     * Complete the 'gameWithCells' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER m
     */
    
    int gameWithCells(int n, int m) {
        // a single drop can get 1 cell (min), 2 cells, 4 cells (max) in the 2D grid
        // return min of drops to fill all the cells of the grid
        // since each drop covers up to 2*2 area => the grid can being divided into the segments of size 2*2? But what if the gird has only 1D?
        // we need to calculate the min drop to fill all the 1D of the size n first (row) then multiply with the col. We know that a drop and cover up to 2 cell in 1D grid
        // So the min drops to cover col with size n is (n/2), and the min drops to cover the row with size m is (m/2)
        // What if n and m is odd, we need to round up, e.g., 5 cells need at least 3 drops
        // ceil(a/b) = (a+b-1)/b https://codeforces.com/blog/entry/78852
        // the final solution is [(n+2-1)/2] * [(m+2-1)/2] = [(n+1)/2] * [(m+1)/2]
        return ((n+1)/2)*((m+1)/2);
    }
    
    int main()
    {
        ofstream fout(getenv("OUTPUT_PATH"));
    
        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 m = stoi(first_multiple_input[1]);
    
        int result = gameWithCells(n, m);
    
        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;
    }