## Intuition The problem requires pairing names and surnames such that the number of pairs starting with the same letter is maximized. If multiple configurations achieve this maximum, the lexicographically smallest configuration should be chosen. This suggests a greedy approach where we first attempt to match names and surnames by their starting letters, and then sort the remaining unmatched names and surnames to ensure the lexicographically smallest result. ## Approach 1. **Input Parsing:** Read the number of names and surnames, followed by the lists of names and surnames. 2. **Initial Matching:** Create two lists: one for names and one for surnames. Use a greedy approach to pair names and surnames that start with the same letter. Maintain a list of these matched pairs. 3. **Sort Remaining:** For unmatched names and surnames, sort them lexicographically. 4. **Pair Remaining:** Pair the remaining names and surnames in sorted order to ensure the lexicographically smallest result. 5. **Output Formatting:** Construct the output string by concatenating the pairs with the required format: "Name1 Surname1, Name2 Surname2, ...". ## Complexity - **Time Complexity:** O(n^2) due to the potential need to check each name against each surname for initial matching. - **Space Complexity:** O(n) for storing names, surnames, and pairs. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector names(n), surnames(n); for (int i = 0; i < n; ++i) { cin >> names[i]; } for (int i = 0; i < n; ++i) { cin >> surnames[i]; } vector> matchedPairs; vector unmatchedNames, unmatchedSurnames; // Try to match names and surnames by the first letter vector surnameUsed(n, false); for (int i = 0; i < n; ++i) { bool matched = false; for (int j = 0; j < n; ++j) { if (!surnameUsed[j] && names[i][0] == surnames[j][0]) { matchedPairs.emplace_back(names[i], surnames[j]); surnameUsed[j] = true; matched = true; break; } } if (!matched) { unmatchedNames.push_back(names[i]); } } // Collect unmatched surnames for (int j = 0; j < n; ++j) { if (!surnameUsed[j]) { unmatchedSurnames.push_back(surnames[j]); } } // Sort unmatched names and surnames sort(unmatchedNames.begin(), unmatchedNames.end()); sort(unmatchedSurnames.begin(), unmatchedSurnames.end()); // Pair unmatched names and surnames for (int i = 0; i < unmatchedNames.size(); ++i) { matchedPairs.emplace_back(unmatchedNames[i], unmatchedSurnames[i]); } // Sort matched pairs lexicographically sort(matchedPairs.begin(), matchedPairs.end()); // Construct the output stringstream result; for (int i = 0; i < matchedPairs.size(); ++i) { if (i > 0) result << ", "; result << matchedPairs[i].first << " " << matchedPairs[i].second; } cout << result.str() << endl; return 0; } ``` This solution efficiently pairs names and surnames to maximize the desired criteria and ensures the output is formatted correctly. It uses sorting to handle the lexicographical order requirement, ensuring correctness and optimality.

Director

Problem Details