(no subject)
1 message
Nenavath Jeevan <jeevan23@kgpian.iitkgp.ac.in> Wed, 13 Aug 2025 at 18:21
To: Nenavath Jeevan <jeevan23@kgpian.iitkgp.ac.in>
1.
#include <iostream>
using namespace std;
int firstOccurrence(int arr[], int n, int x) {
int low = 0, high = n - 1, ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
ans = mid;
high = mid - 1; // keep searching in left half
}
else if (arr[mid] < x) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
int lastOccurrence(int arr[], int n, int x) {
int low = 0, high = n - 1, ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
ans = mid;
low = mid + 1; // keep searching in right half
}
else if (arr[mid] < x) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
int main() {
int n, x;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) cin >> arr[i];
cin >> x;
int first = firstOccurrence(arr, n, x);
int last = lastOccurrence(arr, n, x);
cout << first << ", " << last;
return 0;
}
2.
#include <iostream>
using namespace std;
bool canFinish(const long long* pages, int n, long long d, long long k) {
long long days = 0;
for (int i = 0; i < n; ++i) {
days += (pages[i] + k - 1) / k; // ceil division
if (days > d) return false; // early exit
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
long long* pages = new long long[n];
long long mx = 0;
for (int i = 0; i < n; ++i) {
cin >> pages[i];
if (pages[i] > mx) mx = pages[i];
}
long long d;
cin >> d;
// If days fewer than number of books, impossible
if (d < n) {
cout << -1 << "\n";
delete[] pages;
return 0;
}
long long lo = 1, hi = mx, ans = -1;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2; // candidate speed k
if (canFinish(pages, n, d, mid)) {
ans = mid;
hi = mid - 1; // try smaller k
} else {
lo = mid + 1; // need faster k
}
}
cout << ans << "\n";
delete[] pages;
return 0;
}
3.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long k, x;
cin >> k >> x;
long long count = 0; // number of messages sent
long long total = 0; // total emotes sent
// First increasing part: 1 to k
for (long long i = 1; i <= k; i++) {
total += i;
count++;
if (total >= x) {
cout << count << "\n";
return 0;
}
}
// Decreasing part: k-1 down to 1
for (long long i = k - 1; i >= 1; i--) {
total += i;
count++;
if (total >= x) {
cout << count << "\n";
return 0;
}
}
// If never banned, send all messages
cout << count << "\n";
return 0;
}
4.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> arr(N);
for (int i = 0; i < N; i++) cin >> arr[i];
// Prefix sums for O(1) range sum queries
vector<long long> pref(N + 1, 0);
for (int i = 0; i < N; i++) pref[i + 1] = pref[i] + arr[i];
vector<int> votes(N, 0);
// Check voters for each member
for (int i = 0; i < N; i++) {
// Left side
for (int j = i - 1; j >= 0; j--) {
long long sum_between = pref[i] - pref[j + 1]; // exclude i and j
if (arr[j] >= sum_between)
votes[i]++;
else
break; // further left won't satisfy
}
// Right side
for (int j = i + 1; j < N; j++) {
long long sum_between = pref[j] - pref[i + 1]; // exclude i and j
if (arr[j] >= sum_between)
votes[i]++;
else
break; // further right won't satisfy
}
}
// Output
for (int i = 0; i < N; i++) {
cout << votes[i] << (i + 1 == N ? '\n' : ' ');
}
return 0;
}
