Zuletzt aktiv 1731076325

Änderung 3c7ba48d8de4bf9162d59fa83e9ee49ccec11ec2

getProductSuggestions.cpp Orginalformat
1#include <bits/stdc++.h>
2using namespace std;
3
4vector<vector<string>> getProductSuggestions(vector<string>& products, const string& search) {
5 // Sort products lexicographically
6 sort(products.begin(), products.end());
7 vector<vector<string>> results;
8 string prefix = "";
9
10 // Build up the prefix from each character in 'search'
11 for (char ch : search) {
12 prefix += ch;
13 vector<string> matches;
14
15 // Using binary search to optimize finding the start of matching products
16 auto it = lower_bound(products.begin(), products.end(), prefix);
17
18 // Collect up to 3 matches that start with the current prefix
19 for (int i = 0; i < 3 && it + i != products.end(); i++) {
20 string& product = *(it + i);
21 if (product.find(prefix) == 0) { // starts with 'prefix'
22 matches.push_back(product);
23 } else {
24 break;
25 }
26 }
27
28 // Add matches for this prefix to results
29 results.push_back(matches);
30 }
31
32 return results;
33}
34
35int main() {
36 vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
37 string search = "mouse";
38
39 vector<vector<string>> result = getProductSuggestions(products, search);
40
41 // Display results
42 for (const auto& suggestions : result) {
43 for (const auto& suggestion : suggestions) {
44 cout << suggestion << " ";
45 }
46 cout << endl;
47 }
48
49 return 0;
50}
51
variantsCount.cpp Orginalformat
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4
5long variantsCount(int n, long long s0, long long k, long long b, long long m, long long a) {
6 // Generate all n side lengths
7 vector<long long> sides(n);
8 sides[0] = s0;
9 for (int i = 1; i < n; i++) {
10 sides[i] = ((k * sides[i - 1] + b) % m) + 1 + sides[i - 1];
11 }
12
13 // Sort sides for binary search
14 sort(sides.begin(), sides.end());
15 int count = 0;
16
17 // Use binary search to count pairs
18 for (int i = 0; i < n; i++) {
19 long long max_side = a / sides[i];
20 // Find the position where sides[j] exceeds max_side
21 auto j = upper_bound(sides.begin(), sides.end(), max_side) - sides.begin();
22 count += j; // All elements in sides[0:j] are valid for sides[i] * sides[j] <= a
23 }
24
25 return count;
26}
27
28int main() {
29 int n = 5;
30 long long s0 = 3, k = 2, b = 1, m = 100, a = 100;
31
32 int result = variantsCount(n, s0, k, b, m, a);
33 cout << result << endl;
34
35 return 0;
36}
37