Problem 1: Apple Planting

Problem Description

There is an n-row by m-column farmland in front of Taotao's house. Some grids can grow apples (represented by 1), while others cannot (represented by 0). Additionally, adjacent grids cannot both grow apples. Taotao wants to know how many possible planting schemes exist (planting no apples is also a valid scheme).

Input Format

The first line contains two integers, n and m, separated by a space. The next n lines each contain m numbers, either 1 or 0, indicating weather planting is possible.

Output Format

Output a single integer, representing the number of valid schemes.

Sample Input 1

1 5
1 1 1 1 1

Sample Output 1

13

Sample Input 2

1 10
1 1 1 1 0 1 1 0 1 1

Sample Output 2

72

Sample Input 3

2 10
1 1 0 1 1 1 0 1 1 1
1 0 1 1 1 1 0 0 1 0

Sample Output 3

1305

Data Constraints

• For the first 30% of the data: n = 1, and all grids can grow apples.
• For another 20% of the data: n = 1.
• For another 20% of the data: There is only one position per row that can grow apples.
• For 100% of the data: n <= 2, m <= 10.

Solution Approach

Since the maximum grid size is 2x10 (20 cells), we can use a bitmask brute-force approach. We iterate through all possible subsets of the valid planting cells. For each subset, we check if any two chosen cells are adjacent. If no adjacent cell are chosen, the scheme is valid.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<pair<int, int>> valid_cells;
    
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            int val;
            cin >> val;
            if (val == 1) {
                valid_cells.push_back({r, c});
            }
        }
    }

    int num_cells = valid_cells.size();
    int valid_schemes = 0;

    for (int mask = 0; mask < (1 << num_cells); ++mask) {
        bool is_valid = true;
        for (int i = 0; i < num_cells && is_valid; ++i) {
            if ((mask >> i) & 1) {
                for (int j = i + 1; j < num_cells && is_valid; ++j) {
                    if ((mask >> j) & 1) {
                        int r1 = valid_cells[i].first, c1 = valid_cells[i].second;
                        int r2 = valid_cells[j].first, c2 = valid_cells[j].second;
                        if (abs(r1 - r2) + abs(c1 - c2) == 1) {
                            is_valid = false;
                        }
                    }
                }
            }
        }
        if (is_valid) {
            valid_schemes++;
        }
    }
    
    cout << valid_schemes << endl;
    return 0;
}

---

Problem 2: Singing Notes

Problem Description

A sequence of n musical notes is sung, where each note lasts for a duration of b[i]. For instance, the first note is sung from time 0 to time b[1]-1. The second note is sung from time b[1] to time b[1]+b[2]-1, and so on. Given q queries, each containing a time t, determine the note being sung by the singer at each queried time t.

Input Format

The first line contains two integers, n and q. The next n lines each contain an integer representing the duration of each note.

Output Format

Output q lines, each containing the corresponding note number.

Sample Input 1

3 5 
2 
1 
3 
2 
3 
4 
0 
1

Sample Output 1

2
3
3
1
1

Data Constraints

• For 30% of the data: n <= 1000, b[i] <= 1000, q = 1.
• For another 30% of the data: n <= 1000, b[i] <= 10000, q <= 10000.
• For 100% of the data: n <= 10000, b[i] <= 10000, q <= 100000.

Solution Approach

We can use a prefix sum array to store the end time of each note. For a given query time t, we can use binary search (lower_bound) to find the first note whose end time is greater than or equal to t. This allows us to answer each query in O(log n) time.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int note_count, query_count;
    if (!(cin >> note_count >> query_count)) return 0;

    vector<long long> end_times(note_count);
    long long current_end = -1;
    for (int i = 0; i < note_count; ++i) {
        long long duration;
        cin >> duration;
        current_end += duration;
        end_times[i] = current_end;
    }

    for (int q = 0; q < query_count; ++q) {
        long long t;
        cin >> t;
        auto it = lower_bound(end_times.begin(), end_times.end(), t);
        cout << (distance(end_times.begin(), it) + 1) << "\n";
    }

    return 0;
}