Har bir taksiga qo'yish mumkin bo'lgan minimum yulduzcha 1 ga, maksimum 5 ga teng. Demak agar \(n < m\) yoki \(n > m*5\) bo'lsa javob \("-1 -1"\) ga teng. Aks holda:
- Minimum uchun: har bir taksi uchun 5 dan kichik bo'lgan eng katta reyting berishga harakat qilamiz: bu holatda javob \(max(0, n-m*4)\) ga teng bo'ladi.
- Maksimum holat uchun: avvaliga har bir taksi uchun 1 ta yulduzcha beramiz. Bizda qolgan yulduzchalar \(n-m\). Endi iloji boricha ko'proq taksiga yana 4 tadan yulduzcha berishimiz kerak: \((n-m)/4\).
Yuqoridagi rasmda R=0 va R=1 holat uchun bomba qurshab oladigan hududlar tasvirlangan.
Har bir bomba maydonni \(+\) ko'rinishida \(2*R+1\) kenglikda qoplaydi. Shunday qilib, biz bombalarni yoki qator bo'yicha, yoki ustun bo'yicha joylashtiramiz, bunda bizga kerak bo'ladigan minimum bombalar soni \(\lbrack \frac{min(N, M)} {2*R+1} \rbrack\) ga teng.
Eng optimal usul prefix sum algoritmidan foydalanish. Har bir sayyoh uchun o'zi boradigan eng kichik raqamli bog' (L) ni boshlash, eng katta raqamli bog' (R) ni tugatish deb nomlasak, quyidagi ishni har bir sayyoh uchun bajarishning o'zi yetarli bo'ladi:
i-sayyoh_tugatmasidan_oldin_boshlaganlar_soni - i-sayyoh_boshlashidan_oldin_tugatganlar_soni
Har bir A uchun mumkin bo'lgan B va C sonlarini qidirib chiqamiz, chegara \(B*C > N\) bo'lguncha. Vaqt chegarasi Eyler yaqinlashuviga ko'ra N*log2(N) ga juda ham yaqin natija bo'ladi.
Yechimni avvalo K=1 yoki K=N holati uchun ko'rib chiqamiz. E'tibor bering, birinchi vazadan boshlanganda, agar vaza hozirda undan balandroq vaza topmagan bo'lsa, gullamaydi. Vazalarni kamayish tartibida saqlaydigan stack da saqlash mumkin. Agar bir kun yangi vazaga suv kelsa: Yuqori qavatdagi vaza hali ham yangi vazadan pastroq bo'lsa, stack ochiladi va yuqori qavatdagi vaza gullaydi. Vazalarning ikki chetida cheksiz to'siqlar bor, bu esa eng baland vazaning pop() bo'lishini ta'minlaydi. E'tibor bering, amortizatsiya qilingan vaqt murakkabligi har bir vaza uchun O(1) ga teng.
Umumiy holat yuqoridagiga o'xshab, faqat siz ikki deque yoki linked list ishlatishingiz mumkin. Farqi shundaki, siz kamida 2 ta vazani gullatishingiz kerak. Hozirgi segmentning chap yoki o'ng tomonida suv qayerga oqib ketishini bilish uchun. Implementation yuqoridagi holatga o'xshaydi.
yechim: cpp, python.
C++ dasturlash tilida masalalarning yechimlari:
#include <iostream>
using namespace std;
int main(){
long long n, m;
cin >> n >> m;
if(n < m || n > m*5)
cout << "-1 -1";
else
cout << max((long long)0, n-m*4) << ' ' << (n-m)/4;
return 0;
}#include <iostream>
using namespace std;
int main(){
int n, m, r;
cin >> n >> m >> r;
cout << (min(n, m)+2*r)/(2*r+1);
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, m, l, r;
cin >> n >> m;
vector<int> a(n), b(n);
vector<pair<int, int>> c(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i] >> b[i];
c[i] = {a[i], b[i]};
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i = 0; i < n; ++i)
{
int l = lower_bound(b.begin(), b.end(), c[i].first) - b.begin();
int r = upper_bound(a.begin(), a.end(), c[i].second) - a.begin();
cout << r - l - 1 << endl;
}
}#include <iostream>
using namespace std;
using ll = long long;
int main()
{
ll n;
cin >> n;
ll ans = 0, k = 1;
for (ll i = 1; i < n; ++i)
{
k = 1;
while (k * i < n)
{
if (k == i)
{
++k;
continue;
}
ll m = n - k * i;
if (m != i && m != k)
++ans;
++k;
}
}
cout << ans;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"
const int MAXN = 1000000;
const int INF = MAXN + 3;
int n, k, l, r;
int dp[MAXN + 5];
deque<int> pos;
void t_main()
{
cin >> n >> k;
dp[0] = dp[n + 1] = INF;
dp[n + 1]++;
for (int i = 1; i <= n; i++)
cin >> dp[i];
pos.push_back(k);
bool isRight = (k == 1 || dp[k - 1] > dp[k]);
l = r = pos.back();
vector<int> ans;
while (1 <= l || r <= n)
{
if (isRight)
{
int cur = ++r;
while (pos.size() > 1)
{
if (dp[pos.back()] < dp[cur])
ans.push_back(pos.back()), pos.pop_back();
else
break;
}
if (pos.size() == 1 && dp[pos.back()] < dp[cur])
isRight = !isRight;
pos.push_back(cur);
}
else
{
int cur = --l;
while (pos.size() > 1)
{
if (dp[pos.front()] < dp[cur])
ans.push_back(pos.front()), pos.pop_front();
else
break;
}
if (pos.size() == 1 && dp[pos.front()] < dp[cur])
isRight = !isRight;
pos.push_front(cur);
}
}
for (int i = 0; i < n; i++)
cout << ans[i] << " \n"[i == n - 1];
}
signed main()
{
signed t = 1;
cin.tie(nullptr)->sync_with_stdio(false);
while (t--)
{
t_main();
cout << '\n';
}
return 0;
}Python dasturlash tilidagi yechimlar:
n, m = map(int, input().split())
if n < m or n > m*5:
print('-1 -1')
else:
print(max(0, n-m*4), (n-m)//4)n, m, r = map(int, input().split())
print((min(n, m)+2*r)//(2*r+1))from bisect import bisect_left, bisect_right
n, m = map(int, input().split())
a = []
b = []
c = []
for i in range(n):
x, y = map(int, input().split())
a.append(x)
b.append(y)
c.append((x, y))
a.sort()
b.sort()
for i in range(n):
left = bisect_right(a, c[i][1])
right = bisect_left(b, c[i][0])
print(left - right - 1)n = int(input())
ans = 0
for i in range(1, n):
k = 1
while k * i < n:
if k == i:
k += 1
continue
m = n - k * i
if m != i and m != k:
ans += 1
k += 1
print(ans)print('Learn cpp, please...')
Telegram kanalimizga obuna bo'ling