A. Komiljon va shokolad
Komiljon uchchala jiyanlariga bir xil sondagi shokolad olib borishi kerak. Bundan Komiljon olib boradigan shokoladlar soni 3 ga bo`linishi zarurligi kelib chiqadi. Demak u ko`pi bilan
\(\lfloor \frac{n}{3} \rfloor \cdot 3\) ta shokolad olib boroladi.
Time complexity: \(O(1)\)
print(int(input()) // 3 * 3)
B. Komiljon va uning do'stlari
Komiljon va uning do`stining uylari \(N\) ta uyning aynan qaysisi ekanligi no'malum. Ammo minimal va maksimal masofani topish kerak. \(N\) ning soni kichik bo`lganligi uchun, barcha holatlarni ko`rib chiqish mumkindir. Komiljonning uyini \(i\), do`stining uyini \(j\) deb belgilasak
manhettan masofani \(|x_i - x_j| + |y_i - y_j|\) ko`rinishida ifodalash mumkin. Bularning barchasidan minimal va maksimalini topish yetarli.
Time complexity: \(O(N^2)\)
n = int(input())
coor = [list(map(int, input().split())) for _ in range(n)]
min_ans, max_ans = 10 ** 10, -10 ** 10
for i in range(n):
xi, yi = coor[i]
for j in range(n):
if i == j: continue
xj, yj = coor[j]
min_ans = min(min_ans, abs(xi - xj) + abs(yi - yj))
max_ans = max(max_ans, abs(xi - xj) + abs(yi - yj))
print(min_ans, max_ans)
C. Banknotalar
Observation 1: Banktonalar bir-biriga bo`linadi, demak istalgan miqdordagi summani minimal sondagi banknotalar bilan yig`ish uchun har doim iloji boricha eng katta banknotalardan foydalanish lozim.
Observation 2: Banktonalar bir-biriga bo`linadi, qiymati turli xil banknotalar soni ko`p emas, va aniqrog`i xilma-xil banknotalar soni 60 tadan ko`p bo`la olmaydi. Isboti: banknotalarni saralasak, istalgan banknota keyingi banknotaga bo`linadi. Demak ular bir biriga teng, yoki biri ikkinchisidan kamida 2 marta katta. Bundan turli xil banknotalar soni ko`pi bilan\(\log_2(10^{18}) \approx 60\) ekanligi kelib chiqadi.
Xilma-xil banknotalarni va ularning nechtadan ekanligini saqlaymiz. Har bir so`rovd uchun banknotalarni kattasidan kichigiga ko`rib chiqamiz va
har bir banknotdan iloji boricha ko`p ishlatamiz. Summani yasab bo`lmaydigan holatlarga ehtiyot bo`ling.
Time complexity: \(O(N\log{N} + QC)\). Bu yerda \(C\) bu turli banknotalar soni yoki \(C \approx \log_2(\max{A}) \approx 60\).
n = int(input())
a = sorted(list(map(int, input().split())), reverse = True)
banknotes = []
count = []
i = 0
while i < n:
c = 1
while i + c < n and a[i + c] == a[i]:
c += 1
banknotes.append(a[i])
count.append(c)
i += c
m = len(banknotes)
q = int(input())
queries = list(map(int, input().split()))
for y in queries:
cur = 0
for i in range(m):
k = min(count[i], y // banknotes[i])
cur += k
y -= k * banknotes[i]
print([-1, cur][y == 0], end = ' ')
D. Shifuning topshirig`i
Observation 1: \((i, j)\) juftlik uchun \(|A_i - A_j| = 1\) bajarilishi kerak, demak \(A_i\) va \(A_j\) sonlarini 2 ga bo`lingandagi qoldiqlari har xil.
Demak tugunlarni massiv elementlari va qirralarni \((X_i, Y_i)\) cheklovlardan iborat grafni olsak, ushbu graf bipartite bo`lishi lozim. Aks holda natija \(-1\). Agar bipartitelik sharti qanoatlantirsa, grafdagi birinchi bo`lak elementlarini 1 qilib va ikkinchi bo`lak elementlarini 2 qilib o`rnatsak, masalada so`ralgan massivni
qura olamiz.
Time complexity: \(O(N + M)\)
import sys
# python tilida rekursiyaga chegara qo`yilgan
# mana shu qator yordamida bu chegarani oshirsa bo`ladi
sys.setrecursionlimit(10 ** 9)
n, m = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
x, y = map(int, input().split())
g[x].append(y)
g[y].append(x)
ans = [0 for _ in range(n + 1)]
def dfs(i, c):
ans[i] = c
for j in g[i]:
if ans[j] == 0:
if not dfs(j, 1 + (c % 2)):
return False
elif ans[i] == ans[j]:
return False
return True
for i in range(1, n+1):
if ans[i] == 0:
if not dfs(i, 1):
exit(print(-1))
for i in range(1, n+1):
if ans[i] == -1:
ans[i] = 0
print(ans[i], end = ' ')E. Asilbek va g'aroyib oraliqlar
Observation: Ixtiyoriy \(l, r\) uchun \(F(l, r) \le F(l,r+1)\) shart bajariladi.
Isbot: Agar \(F(l, r) > F(l, r+1)\) bo'lsa, u holda \(r+1\)-elementni yo'q deb tasavvur qilib \(F(l,r+1)\) qiymatga (ya'ni kichikroq qiymatga) erishishimiz mumkin. Ziddiyat.
Bu turdagi masalalarda ikkita ko'rsatkich (two-pointers) usuli yordam berishi mumkin. Aytaylik \(l\) va \(r\) ko'rsatkichlarimiz bor. Agar shu oraliqdagi sonlarni STL Multiset yoki Segment Treeda saqlasak, \(r \rightarrow r+1\) siljishni \(O(\log{N})\)da bajarish mumkin. Jami siljishlar soni esa \(O(N)\), chunki har bir \(l\) va \(r\) faqat \(N\) marta o'zgaradi.
Complexity: \(O(N \log{N})\).
STL yordamida (by Dilyorbek):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct split_set {
multiset<int> a{}, b{};
ll sa{}, sb{};
void check() {
if (a.size() > b.size()+1) {
int x = *a.rbegin();
b.insert(x), sb += x;
a.erase(a.find(x)), sa -= x;
} else if (a.size() < b.size()) {
int x = *b.begin();
a.insert(x), sa += x;
b.erase(b.begin()), sb -= x;
}
}
void insert(int x) {
if (a.empty() || x < *a.rbegin()) {
a.insert(x), sa += x;
} else {
b.insert(x), sb += x;
}
check();
}
void erase(int x) {
if (auto it = a.find(x); it != a.end()) {
a.erase(it), sa -= x;
} else {
b.erase(b.find(x)), sb -= x;
}
check();
}
ll calc() {
if (a.empty())
return 0;
ll med = *a.rbegin();
return med * (ll) a.size() - sa
+ sb - med * (ll) b.size();
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
ll n, t;
cin >> n >> t;
split_set st{};
vector<int> arr(n);
for (int& i : arr) cin >> i;
ll res = 0;
for (int l = 0, r = 0; l < n; l++) {
while (r < n) {
st.insert(arr[r]);
if (st.calc() > t) {
st.erase(arr[r]);
break;
} else {
r++;
}
}
res += r - l;
st.erase(arr[l]);
}
cout << res << endl;
return 0;
}
Segment Tree yordamida (by Dilshodbek):
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 20;
#define all(x) (x).begin(), (x).end()
using pii = pair<int, long long>;
int a[N], b[N], orig_val[N];
pii t[4 * N];
pii operator+ (pii x, pii y){
return make_pair(x.first + y.first, x.second + y.second);
}
void update(int v, int tl, int tr, int pos, pair<int, long long> val){
if (tl == tr){
t[v] = t[v] + val;
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm){
update(v << 1, tl, tm, pos, val);
} else {
update(v << 1 | 1, tm + 1, tr, pos, val);
}
t[v] = t[v << 1] + t[v << 1 | 1];
}
pii get(int v, int tl, int tr, int l, int r){
if (l <= tl && tr <= r) return t[v];
if (tl > r || tr < l) return make_pair(0, 0);
int tm = (tl + tr) >> 1;
return get(v << 1, tl, tm, l, r) + get(v << 1 | 1, tm + 1, tr, l, r);
}
int find(int v, int tl, int tr, int k){
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
if (t[v << 1].first >= k){
return find(v << 1, tl, tm, k);
} else {
return find(v << 1 | 1, tm + 1, tr, k - t[v << 1].first);
}
}
int n;
void add(int i){
update(1, 0, n - 1, b[i], make_pair(1, a[i]));
}
void del(int i){
update(1, 0, n - 1, b[i], make_pair(-1, -a[i]));
}
long long cost(){
int k = t[1].first;
if (k <= 1) return 0;
int mid = find(1, 0, n - 1, (k + 1) / 2);
long long ans = 0;
{
auto [cnt, sum] = get(1, 0, n - 1, 0, mid - 1);
ans += 1LL * orig_val[mid] * cnt - sum;
}
{
auto [cnt, sum] = get(1, 0, n - 1, mid + 1, n - 1);
ans += sum - 1LL * orig_val[mid] * cnt;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
fill(t, t + 4 * N, make_pair(0, 0));
long long T;
cin >> n >> T;
vector<int> values(n);
for (int i = 0; i < n; i++){
cin >> a[i];
values[i] = a[i];
}
sort(all(values));
values.erase(unique(all(values)), values.end());
for (int i = 0; i < values.size(); i++) orig_val[i] = values[i];
for (int i = 0; i < n; i++){
b[i] = lower_bound(all(values), a[i]) - values.begin();
}
long long ans = 0;
int j = 0;
for (int i = 0; i < n; i++){
while (j < n){
add(j);
if (cost() > T){
del(j);
break;
}
j++;
}
ans += j - i;
del(i);
}
cout << ans << endl;
return 0;
}.
Telegram kanalimizga obuna bo'ling