Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
using namespace std;
using ll = long long;
void solve() {
ll single, poly, uni;
cin >> single >> poly >> uni;
ll needPoly = (3 - poly % 3) % 3;
if (poly > 0 && needPoly > uni) {
cout << "-1\n";
return;
}
uni -= needPoly;
poly += needPoly;
ll mn = single + uni / 3 + (uni % 3 + 1) / 2 + poly / 3;
cout << mn << '\n';
}
int32_t main() {
ll T;
cin >> T;
while(T--){
solve();
}
return 0;
}
Разбор
Tutorial is loading...
Решение
t = int(input())
for qi in range(t):
a, b, m = [int(x) for x in input().split()]
ans = m // a + m // b + 2
print(ans)
Разбор
Tutorial is loading...
Решение
for case in range(int(input())):
n = int(input())
a = input()
suf_cnt = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1')
pref_cnt = 0
opt_ans = -1
opt_dist = n * 2
threshold = (n + 1) // 2
for i in range(n + 1):
if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist:
opt_dist = abs(n - 2 * i)
opt_ans = i
if i != n:
pref_cnt += (a[i] == '0')
print(opt_ans)
Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
void solve() {
ll n, k;
cin >> n >> k;
vector<ll> A(n);
for (auto& item : A) {
cin >> item;
}
reverse(A.begin(), A.end());
vector<ll> B(n);
for (auto& item : B) {
cin >> item;
}
reverse(B.begin(), B.end());
ll bSum = 0;
ll pref = 0;
for (ll i = 0; i < n - k; ++i) {
if (A[i] < B[i]) {
pref += bSum;
pref += A[i];
bSum = 0;
} else {
bSum += B[i];
}
}
ll res = 1e18;
for (ll i = n - k; i < n; ++i) {
res = min(res, pref + bSum + A[i]);
bSum += B[i];
}
cout << res << '\n';
}
int32_t main() {
ll testN;
cin >> testN;
while (testN--) {
solve();
}
return 0;
}
Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n, x;
cin >> n >> x;
vector<int> src(n);
int P = 0;
for (int i = 0; i < n; ++i) {
cin >> src[i];
if (src[i] == x) {
P = i;
}
}
int l = 0;
int r = n;
while (r - l > 1) {
int m = (l + r) / 2;
if (src[m] <= x) {
l = m;
} else {
r = m;
}
}
cout << "1\n";
cout << P + 1 << ' ' << l + 1 << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;
void solve() {
ll n;
cin >> n;
vector<ll> src(n);
vector<pair<ll, ll>> can(n);
for (ll i = 0; i < n; ++i) {
cin >> src[i];
can[i] = {src[i], i};
}
vector<ll> ord(n);
for (auto& item : ord) {
cin >> item;
--item;
}
sort(can.rbegin(), can.rend());
ll best = can[0].first;
ll take = 1;
ll cur;
ll P = 1;
vector<bool> burn(n);
vector<bool> used(n);
used[can[0].second] = true;
for (ll k = 0; k + 1 < n && P < n; ++k) {
while (P < n && burn[can[P].second]) {
++P;
}
if (P == n) {
break;
}
used[can[P].second] = true;
cur = can[P].first;
++P;
burn[ord[k]] = true;
if (used[ord[k]]) {
while (P < n && burn[can[P].second]) {
++P;
}
if (P == n) {
break;
}
used[can[P].second] = true;
cur = can[P].first;
++P;
}
if (best < cur * (k + 2)) {
take = k + 2;
best = cur * (k + 2);
}
}
cout << best << ' ' << take << '\n';
}
int32_t main() {
ll testN;
cin >> testN;
while (testN--) {
solve();
}
return 0;
}
Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
const int MAX_N = 2e5;
const int MAX_D = 3e5;
struct Student {
int k;
int s;
int tin = 0;
bool operator<(const Student& other) const {
if (k == other.k) {
if (tin == other.tin) {
return s > other.s;
}
return tin > other.tin;
}
return k < other.k;
}
};
int n, D, x;
Student qu1[MAX_N];
int sufMax[MAX_N];
vector<Student> eat[MAX_D];
int check() {
int origPos = 0;
priority_queue<Student> qu2;
for (int i = 0; i < D && origPos < n; ++i) {
if (qu2.empty() || qu2.top().k <= sufMax[origPos]) {
ll nxtTime = ll(i) + ll(x) * ll(qu1[origPos].s);
if (nxtTime < D) {
eat[nxtTime].push_back(qu1[origPos]);
}
++origPos;
if (origPos == n) {
for (int tm = 0; tm < D; ++tm) {
eat[tm].clear();
}
return i + 1;
}
} else {
ll nxtTime = ll(i) + ll(x) * ll(qu2.top().s);
if (nxtTime < D) {
eat[nxtTime].push_back(qu2.top());
}
qu2.pop();
}
for (const auto& student : eat[i]) {
qu2.push({student.k, student.s, i});
}
}
for (int i = 0; i < D; ++i) {
eat[i].clear();
}
return -1;
}
void solve() {
cin >> n >> D;
x = 1;
for (int i = 0; i < n; ++i) {
cin >> qu1[i].k >> qu1[i].s;
}
sufMax[n - 1] = qu1[n - 1].k;
for (int i = n - 2; i >= 0; --i) {
sufMax[i] = max(qu1[i].k, sufMax[i + 1]);
}
cout << check() << '\n';
}
int32_t main() {
ll testN;
cin >> testN;
while (testN--) {
solve();
}
return 0;
}
Идея: Kirill_Maglysh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int BITS = 20;
const int MAX_N = 4e5 + 10;
int n;
int x;
int src[MAX_N];
void coutYES(int fId, int sId) {
cout << "YES\n";
cout << "2 " << src[fId] << ' ' << src[sId] << '\n';
cout << n - 2 << ' ';
for (int i = 0; i < n; i++) {
if (i == fId || i == sId) {
continue;
}
cout << src[i] << ' ';
}
cout << '\n';
}
void solve() {
cin >> n >> x;
vector<int> bitCnt[BITS];
int maxA = 1;
for (int i = 0; i < n; i++) {
cin >> src[i];
maxA = max(maxA, src[i] + 1);
for (int bit = 0; bit < BITS; bit++) {
if ((1 << bit) & src[i]) {
continue;
}
bitCnt[bit].push_back(i);
}
}
bool incr[n];
int cnt[maxA];
int divBy[maxA];
for (int i = 0; i < maxA; ++i) {
cnt[i] = 0;
divBy[i] = 0;
}
int pref[n];
int suf[n];
for (int i = 0; i < n; i++) {
incr[i] = false;
pref[i] = src[i];
if (i) {
pref[i] = pref[i - 1] & src[i];
}
}
for (int i = n - 2; i >= 0; i--) {
suf[n - 1] = src[n - 1];
if (i < n - 1) {
suf[i] = suf[i + 1] & src[i];
}
}
for (const auto& item : bitCnt) {
if (item.size() <= 2) {
for (const int& id : item) {
incr[id] = true;
int myAnd = -1;
for (int j = id + 1; j < n; j++) {
int curAND = (1 << BITS) - 1;
if (j + 1 < n) curAND &= suf[j + 1];
if (id - 1 >= 0) curAND &= pref[id - 1];
if (myAnd != -1) curAND &= myAnd;
if (curAND + x < __gcd(src[id], src[j])) {
coutYES(id, j);
return;
}
if (myAnd == -1) {
myAnd = src[j];
} else {
myAnd &= src[j];
}
}
myAnd = -1;
for (int j = id - 1; j >= 0; j--) {
int curAND = (1 << BITS) - 1;
if (j - 1 >= 0) curAND &= pref[j - 1];
if (id + 1 < n) curAND &= suf[id + 1];
if (myAnd != -1) curAND &= myAnd;
if (curAND + x < __gcd(src[id], src[j])) {
coutYES(id, j);
return;
}
if (myAnd == -1) {
myAnd = src[j];
} else {
myAnd &= src[j];
}
}
}
}
}
int AND = (1 << BITS) - 1;
for (int i = 0; i < BITS; i++) {
if (!bitCnt[i].empty()) {
AND ^= (1 << i);
}
}
for (int i = 0; i < n; i++) {
if (!incr[i]) {
++cnt[src[i]];
}
}
for (int i = 1; i < maxA; i++) {
for (int j = i; j < maxA; j += i) {
divBy[i] += cnt[j];
}
}
for (int g = maxA - 1; g > AND + x; g--) {
if (divBy[g] < 2) {
continue;
}
int fId = -1;
int sId = -1;
for (int i = 0; i < n; i++) {
if (!incr[i]) {
if (src[i] % g == 0) {
if (fId == -1) {
fId = i;
} else {
sId = i;
}
}
}
}
coutYES(fId, sId);
return;
}
cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int testN;
cin >> testN;
while (testN--) {
solve();
}
return 0;
}