ProtyayMnd50 / variantsCount.cpp

#include <bits/stdc++.h> using namespace std; vector<vector<string>> getProductSuggestions(vector<string>& products, const string& search) { // Sort products lexicographically sort(products.begin(), products.end()); vector<vector<string>> results; string prefix = ""; // Build up the prefix from each character in 'search' for (char ch : search) { prefix += ch; vector<string> matches; // Using binary search to optimize finding the start of matching products auto it = lower_bound(products.begin(), products.end(), prefix); // Collect up to 3 matches that start with the current prefix for (int i = 0; i < 3 && it + i != products.end(); i++) { string& product = *(it + i); if (product.find(prefix) == 0) { // starts with 'prefix' matches.push_back(product); } else { break; } } // Add matches for this prefix to results results.push_back(matches); } return results; } int main() { vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"}; string search = "mouse"; vector<vector<string>> result = getProductSuggestions(products, search); // Display results for (const auto& suggestions : result) { for (const auto& suggestion : suggestions) { cout << suggestion << " "; } cout << endl; } return 0; }

#include <bits/stdc++.h> using namespace std; #define ll long long long variantsCount(int n, long long s0, long long k, long long b, long long m, long long a) { // Generate all n side lengths vector<long long> sides(n); sides[0] = s0; for (int i = 1; i < n; i++) { sides[i] = ((k * sides[i - 1] + b) % m) + 1 + sides[i - 1]; } // Sort sides for binary search sort(sides.begin(), sides.end()); int count = 0; // Use binary search to count pairs for (int i = 0; i < n; i++) { long long max_side = a / sides[i]; // Find the position where sides[j] exceeds max_side auto j = upper_bound(sides.begin(), sides.end(), max_side) - sides.begin(); count += j; // All elements in sides[0:j] are valid for sides[i] * sides[j] <= a } return count; } int main() { int n = 5; long long s0 = 3, k = 2, b = 1, m = 100, a = 100; int result = variantsCount(n, s0, k, b, m, a); cout << result << endl; return 0; }