ProtyayMnd50 / variantsCount.cpp

#include <bits/stdc++.h> using namespace std; int countPairs(const vector<int>& projectCosts, int target) { // Using an unordered set to keep track of visited numbers unordered_set<int> visited; int count = 0; // Iterate through each number in the list for (int cost : projectCosts) { // Check if there exists a number with the required difference if (visited.count(cost + target)) { count++; } if (visited.count(cost - target)) { count++; } // Add the current number to the visited set visited.insert(cost); } return count; } int main() { vector<int> projectCosts = {1, 3, 5}; int target = 2; int result = countPairs(projectCosts, target); cout << result << endl; // Output should be 2 return 0; }

#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; struct Passenger { long long pickup; long long drop; long long value; }; long long taxiDriver(vector<long long> pickup, vector<long long> drop, vector<int> tip){ int n = pickup.size(); if(n == 0) return 0; vector<Passenger> passengers(n); for(int i = 0; i < n; i++) { passengers[i] = Passenger{pickup[i], drop[i], drop[i] - pickup[i] + static_cast<long long>(tip[i])}; } sort(passengers.begin(), passengers.end(), [&](const Passenger &a, const Passenger &b) -> bool{ if(a.drop != b.drop) return a.drop < b.drop; return a.pickup < b.pickup; }); vector<long long> dp(n + 1, 0); for(int i = 1; i <= n; i++){ int j = -1; int low = 0, high = i - 2; while(low <= high){ int mid = low + (high - low) / 2; if(passengers[mid].drop <= passengers[i-1].pickup){ j = mid; low = mid + 1; } else high = mid - 1; } dp[i] = max(dp[i-1], (j != -1 ? dp[j+1] : 0) + passengers[i-1].value); } return dp[n]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> pickup(n); for(auto &x: pickup) cin >> x; vector<long long> drop(n); for(auto &x: drop) cin >> x; vector<int> tip(n); for(auto &x: tip) cin >> x; cout << taxiDriver(pickup, drop, tip); }

#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; }