Sonning toq yoki juftligini tekshirish uchun ikkala sonning ham 2 ga bo'lgandagi qoldig'i bir xil bo'lishi kerak. 2 ga qoldiq olish uchun sonning eng oxirgi raqami yetarli.
a=int(input()[-1])
b=int(input()[-1])
print("toq" if a%2 == b%2 else "juft")
#include <iostream>
using namespace std;
int main(){
string a, b;
cin >> a >> b;
cout << (a.back() % 2 == b.back() % 2 ? "juft" : "toq");
}Time complexity: \(O(1)\)
Masala greedy (ochko'z algoritm) usulda ishlanadi. Har bir ipni toki uzunligi w dan kichik bo'lsa, yonidagi ipni qo'shish kerak.
n, w = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
cur = 0
for x in a:
cur += x
if cur >= w:
ans += 1
cur = 0
print(ans)
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, w; cin >> n >> w;
int cur = 0, ans = 0;
for(int i = 0, x; i < n; ++i){
cin >> x;
cur += x;
if(cur >= w){
++ans;
cur = 0;
}
}
cout << ans;
}Time complexity: \(O(n)\)
Stolning bo'yidan \(n/k\) ta va enidan \(m/k\) ta stul joylashtirish mumkin. 4 ta burchakda ikkitadan stol bo'lib qolishini inobatga olgan holda, 4 ta burchakdagi ustma-ust tushgan stullar bittadan hisoblanadi. Quyidagi holatlar hisobga olinsa masala hal: \(min(n/k, m/k) = 0\), \(min(n/k, m/k) = 1\).
n, m, k = map(int, input().split())
mn = min(n//k, m//k)
mx = max(n//k, m//k)
if mn == 0:
print(0)
elif mn == 1:
print(mx)
else:
print((mn+mx)*2-4)
#include <iostream>
using namespace std;
int main(){
int n, m, k;
cin >> n >> m >> k;
int mn = min(n/k, m/k);
int mx = max(n/k, m/k);
if(mn == 0) cout << 0;
else if(mn == 1) cout << mx;
else cout << (mn+mx)*2 - 4;
}Time complexity: \(O(1)\)
Har bir kation uchun mos keluvchi eng yuqori va eng chapdagi anion turgan joyni aytish kifoya. Har bir turdagi anionni massivda saqlash orqali har bir kationga \(O(1)\) da javob berish mumkin.
from random import randint, shuffle, choice
n, m = map(int, input().split())
a = []
for i in range(int(2e5+5)):
a.append([])
for i in range(n):
s = list(map(int, input().split()))
for j in range(m):
if s[j] != 0:
a[-s[j]].append([i, j])
for i in range(len(a)):
a[i].reverse()
# pprint(a)
q = int(input())
t = list(map(int, input().split()))
for x in t:
print(*a[x][-1])
a[x].pop()
// author: rshohruh
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define with_testcases
void t_main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<queue<pair<int, int>>> ans(2e5+5);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j){
int x; cin >> x;
// cout << -x << endl;
if(x != 0)
ans[-x].emplace(i, j);
}
int q; cin >> q;
while(q--){
int x; cin >> x;
auto [i, j] = ans[x].front();
ans[x].pop();
cout << i << ' ' << j << endl;
}
}
signed main(){
signed t = 1;
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef with_testcases
cin >> t;
#endif
while(t--){
t_main();
cout << '\n';
}
return 0;
}Time complexity: \(O(n\times m)\)
Qaysidir [l, r] oraliqni shunday tanlab olish kerakki, oraliqdagi takrorlanmas testlar beradigan kayfiyat miqdori maksimal bo'lsin.
Shunday qilib oraliqda birinchi marta uchragan \(i\) test uchun \(b_i\) qiymat, ikkinchisi uchun \(-b_i\) qiymat, qolganlariga 0 qiymati beriladi. Oraliqdagi maksimum prefiks sumni hisoblash yetarli. Oddiy holatda yechim \(O(n^2)\), data structure (e.g. segment tree) yordamida har bir yangilashni \(O(logn)\) da bajarish mumkin.
// author: rshohruh
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define with_testcases
struct node{
ll pref, cur;
node() : pref(0), cur(0) {}
node(ll x) : pref(max(0ll, x)), cur(x) {}
};
node merge(node l, node r) {
l.pref = max(l.pref, l.cur + r.pref);
l.cur = l.cur + r.cur;
return l;
}
struct segtree{
int n;
vector<node> t;
vector<ll> a;
void build(int v, int l, int r){
if(l == r){
t[v] = node(a[l]);
return;
}
int m = (l + r) / 2;
build(v*2, l, m);
build(v*2+1, m+1, r);
t[v] = merge(t[v*2], t[v*2+1]);
}
void update(int v, int l, int r, int id, ll val){
if(l == r){
t[v] = node(val);
return;
}
int m = (l + r) / 2;
if(id <= m) update(v*2, l, m, id, val);
else update(v*2+1, m+1, r, id, val);
t[v] = merge(t[v*2], t[v*2+1]);
}
void update(int id, ll val){
update(1, 1, n, id, val);
}
ll get(){
return t[1].pref;
}
segtree(vector<ll> &a) : a(a) {
n = a.size()-1;
t.resize(4*n);
build(1, 1, n);
}
};
void t_main(){
int n, k; cin >> n >> k;
vector<ll> a(n+1), b(k+1);
vector<vector<int>> id(k+1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
id[a[i]].push_back(i);
}
for(int i = 1; i <= k; ++i)
cin >> b[i];
vector<ll> d(n+1);
for(int i = 1; i <= k; ++i){
reverse(id[i].begin(), id[i].end());
if(id[i].size()){
d[id[i].back()] = b[i];
id[i].pop_back();
}
if(id[i].size())
d[id[i].back()] = -b[i];
}
segtree st(d);
ll ans = st.get();
for(int i = 1; i <= n; ++i){
st.update(i, 0);
d[i] = 0;
if(id[a[i]].size()){
st.update(id[a[i]].back(), b[a[i]]);
id[a[i]].pop_back();
}
if(id[a[i]].size()) {
st.update(id[a[i]].back(), -b[a[i]]);
}
ans = max(ans, st.get());
}
cout << ans;
}
signed main(){
signed t = 1;
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef with_testcases
cin >> t;
#endif
while(t--){
t_main();
cout << '\n';
}
return 0;
}Time complexity: \(O(n*logn)\)
Telegram kanalimizga obuna bo'ling