A student takes a multiple-choice test with an n x n answer sheet. Each cell holds one of four options: A, B, C, or D. Unfortunately, the sheet was filled column by column instead of row by row, effectively transposing the intended answers. After the exam, the student comapres notes and marks each position with a comparison symbol: '+' means the recorded answer is correct, '-' means it is wrong but the true answer is unknown, and '?' means the outcome is uncertain.

Given:

• n (the side length)
• The transposed answer grid (as the student submitted it)
• The comparison grid of +, -, and ?

determine the maximum and minimum possible number of corectly answered questoins.

Approach

Let submitted[i][j] be the answer the student actually wrote for the cell at row i, column j. The intended (non-transposed) layout can be recovered by reading the submission column-wise. That is, the intended answer at (i, j) is submitted[j][i].

For each cell, we check the comparison symbol:

• '+' : The student’s submitted answer matches the intended answer (after accounting for the transpose). If indeed submitted[i][j] == submitted[j][i], then this position is definitely correct; it contributes 1 to both the maximum and minimum counts.
• '-' : The student knows the submitted answer is wrong. The intended answer is different, but we don’t know what it is. Since the submission is transposed, the actual comparison should be made against submitted[j][i]. If submitted[i][j] != submitted[j][i], then it is still possible that the original (non-transposed) answer would have been correct before the mistake; hence this position can potentially be correct, adding only to the maximum count.
• '?' : The outcome is unknown. It might be correct regardless of the transposition, so it always adds to the maximum count.

The minimum correct answers come solely from the definite matches ('+' cells where the transposed condition aligns). The maximum is the sum of definite matches plus all '-' cells where the transpose mismatch still allows a possible correct answer, plus every '?' cell.

Implementation

Below is a C++ implementation that reads the grids, performs the transpose-aware evaluation, and prints the maximum and minimum scores.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int side;
    cin >> side;
    
    vector<string> answerGrid(side), comparison(side);
    
    for (int i = 0; i < side; ++i)
        cin >> answerGrid[i];
    for (int i = 0; i < side; ++i)
        cin >> comparison[i];
    
    int maxScore = 0, minScore = 0;
    
    for (int r = 0; r < side; ++r) {
        for (int c = 0; c < side; ++c) {
            char submitted = answerGrid[r][c];
            char intended = answerGrid[c][r];   // transpose correction
            char symbol   = comparison[r][c];
            
            if (symbol == '+') {
                if (submitted == intended) {
                    ++maxScore;
                    ++minScore;
                }
            } else if (symbol == '-') {
                if (submitted != intended)
                    ++maxScore;
            } else if (symbol == '?') {
                ++maxScore;
            }
        }
    }
    
    cout << maxScore << " " << minScore << endl;
    return 0;
}

The algorithm iterates over each cell once, using constant time per cell, resulting in O(n^2) complexity.