Revision of variantsCount.cpp

1 file changed, 50 insertions

taxiDriver.cpp(file created)

		@@ -0,0 +1,50 @@
1	+	#include<bits/stdc++.h>
2	+	using namespace std;
3	+
4	+	struct Passenger {
5	+	long long pickup;
6	+	long long drop;
7	+	long long value;
8	+	};
9	+
10	+	long long taxiDriver(vector<long long> pickup, vector<long long> drop, vector<int> tip){
11	+	int n = pickup.size();
12	+	if(n == 0) return 0;
13	+	vector<Passenger> passengers(n);
14	+	for(int i = 0; i < n; i++) {
15	+	passengers[i] = Passenger{pickup[i], drop[i], drop[i] - pickup[i] + static_cast<long long>(tip[i])};
16	+	}
17	+	sort(passengers.begin(), passengers.end(), [&](const Passenger &a, const Passenger &b) -> bool{
18	+	if(a.drop != b.drop) return a.drop < b.drop;
19	+	return a.pickup < b.pickup;
20	+	});
21	+	vector<long long> dp(n + 1, 0);
22	+	for(int i = 1; i <= n; i++){
23	+	int j = -1;
24	+	int low = 0, high = i - 2;
25	+	while(low <= high){
26	+	int mid = low + (high - low) / 2;
27	+	if(passengers[mid].drop <= passengers[i-1].pickup){
28	+	j = mid;
29	+	low = mid + 1;
30	+	}
31	+	else high = mid - 1;
32	+	}
33	+	dp[i] = max(dp[i-1], (j != -1 ? dp[j+1] : 0) + passengers[i-1].value);
34	+	}
35	+	return dp[n];
36	+	}
37	+
38	+	int main(){
39	+	ios::sync_with_stdio(false);
40	+	cin.tie(0);
41	+	int n;
42	+	cin >> n;
43	+	vector<long long> pickup(n);
44	+	for(auto &x: pickup) cin >> x;
45	+	vector<long long> drop(n);
46	+	for(auto &x: drop) cin >> x;
47	+	vector<int> tip(n);
48	+	for(auto &x: tip) cin >> x;
49	+	cout << taxiDriver(pickup, drop, tip);
50	+	}

1 file changed, 33 insertions

countPairs.cpp(file created)

		@@ -0,0 +1,33 @@
1	+	#include <bits/stdc++.h>
2	+	using namespace std;
3	+
4	+	int countPairs(const vector<int>& projectCosts, int target) {
5	+	// Using an unordered set to keep track of visited numbers
6	+	unordered_set<int> visited;
7	+	int count = 0;
8	+
9	+	// Iterate through each number in the list
10	+	for (int cost : projectCosts) {
11	+	// Check if there exists a number with the required difference
12	+	if (visited.count(cost + target)) {
13	+	count++;
14	+	}
15	+	if (visited.count(cost - target)) {
16	+	count++;
17	+	}
18	+	// Add the current number to the visited set
19	+	visited.insert(cost);
20	+	}
21	+
22	+	return count;
23	+	}
24	+
25	+	int main() {
26	+	vector<int> projectCosts = {1, 3, 5};
27	+	int target = 2;
28	+
29	+	int result = countPairs(projectCosts, target);
30	+	cout << result << endl; // Output should be 2
31	+
32	+	return 0;
33	+	}

1 file changed, 50 insertions

getProductSuggestions.cpp(file created)

		@@ -0,0 +1,50 @@
1	+	#include <bits/stdc++.h>
2	+	using namespace std;
3	+
4	+	vector<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	+
35	+	int 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	+	}

1 file changed, 1 insertion, 1 deletion

variantsCount.cpp

			@@ -2,7 +2,7 @@
2	2		using namespace std;
3	3		#define ll long long
4	4
5		-	int variantsCount(int n, long long s0, long long k, long long b, long long m, long long a) {
	5	+	long variantsCount(int n, long long s0, long long k, long long b, long long m, long long a) {
6	6		// Generate all n side lengths
7	7		vector<long long> sides(n);
8	8		sides[0] = s0;

1 file changed, 36 insertions

variantsCount.cpp(file created)

		@@ -0,0 +1,36 @@
1	+	#include <bits/stdc++.h>
2	+	using namespace std;
3	+	#define ll long long
4	+
5	+	int 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	+
28	+	int 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	+	}

Newer Older