Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#include "random"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int &e : v) {
cin >> e;
}
int maxPos = max_element(v.begin(), v.end()) - v.begin();
int minPos = min_element(v.begin(), v.end()) - v.begin();
cout << min({
max(maxPos, minPos) + 1,
(n - 1) - min(maxPos, minPos) + 1,
(n - 1) - maxPos + minPos + 2,
(n - 1) - minPos + maxPos + 2
}) << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
void solve() {
int n;
cin >> n;
vector<int> a(n);
int s = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
s += a[i];
}
if (s % n != 0) {
cout << "-1" << endl;
return;
}
s /= n;
int res = 0;
for (int i = 0; i < n; i++) {
if (s < a[i]) {
res++;
}
}
cout << res << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#include "random"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
void solve() {
int n, l, r;
cin >> n >> l >> r;
vector<int> v(n);
for (int &e : v) {
cin >> e;
}
sort(v.begin(), v.end());
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += upper_bound(v.begin(), v.end(), r - v[i]) - v.begin();
ans -= lower_bound(v.begin(), v.end(), l - v[i]) - v.begin();
if (l <= 2 * v[i] && 2 * v[i] <= r) {
ans--;
}
}
cout << ans / 2 << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
1538D - Еще одна задача про деление чисел
Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
const int N = 50'000;
bool isPrime[N];
vector<int> primes;
void precalc() {
fill(isPrime + 2, isPrime + N, true);
for (int i = 2; i * i < N; i++) {
for (int j = i * i; j < N; j += i) {
isPrime[j] = false;
}
}
for (int i = 2; i < N; i++) {
if (isPrime[i]) {
primes.push_back(i);
}
}
}
int calcPrime(int n) {
int res = 0;
for (int i : primes) {
if (i * i > n) {
break;
}
while (n % i == 0) {
n /= i;
res++;
}
}
if (n > 1) {
res++;
}
return res;
}
map<int, int> decompose(int n) {
map<int, int> a;
for (int i : primes) {
if (i * i > n) {
break;
}
int p = 0;
while (n % i == 0) {
n /= i;
p++;
}
if (p > 0) {
a[i] = p;
}
}
if (n > 1) {
a[n] = 1;
}
return a;
}
bool check(const map<int, int> &divs,
map<int, int>::const_iterator it,
map<int, int> &divsA,
map<int, int> &divsB,
int low,
int high,
int k) {
if (it == divs.end()) {
return __builtin_popcount(low) <= k && k <= high;
}
for (int p = 0; p <= it->second; p++) {
int pa = divsA[it->first];
int pb = divsB[it->first];
int nextLow = low;
if (p != pa) {
nextLow |= 1;
}
if (p != pb) {
nextLow |= 2;
}
if (check(divs, next(it), divsA, divsB, nextLow, high + pa + pb - 2 * p, k)) {
return true;
}
}
return false;
}
void solve() {
int a, b, k;
cin >> a >> b >> k;
int g = __gcd(a, b);
int low = 0;
int high = 0;
{
int t;
int ta = 1;
while ((t = __gcd(a, g)) != 1) {
a /= t;
ta *= t;
}
high += calcPrime(a);
if (a != 1) {
low |= 1;
}
a = ta;
}
{
int t;
int tb = 1;
while ((t = __gcd(b, g)) != 1) {
b /= t;
tb *= t;
}
high += calcPrime(b);
if (b != 1) {
low |= 2;
}
b = tb;
}
auto divs = decompose(g);
auto divsA = decompose(a);
auto divsB = decompose(b);
cout << (check(divs, divs.begin(), divsA, divsB, low, high, k) ? "YES" : "NO") << endl;
}
int main() {
precalc();
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#include "random"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
vector<string> split(const string& s, char p) {
vector<string> res(1);
for (char c : s) {
if (c == p) {
res.emplace_back();
} else {
res.back() += c;
}
}
return res;
}
struct Word {
ll len;
ll cnt;
string s;
};
string getFirst(string s) {
if (s.size() < 3) {
return s;
}
return s.substr(0, 3);
}
string getLast(string s) {
if (s.size() < 3) {
return s;
}
return s.substr(s.size() - 3, 3);
}
int count(const string& s, const string& p) {
int cnt = 0;
for (int i = 0; i + p.size() <= s.size(); i++) {
if (s.substr(i, p.size()) == p) {
cnt++;
}
}
return cnt;
}
Word merge(const Word& a, const Word& b) {
Word c;
c.len = a.len + b.len;
c.s = a.s + b.s;
c.cnt = a.cnt + b.cnt + count(getLast(a.s) + getFirst(b.s), "haha");
if (c.s.size() >= 7) {
c.s = getFirst(c.s) + "@" + getLast(c.s);
}
return c;
}
void solve() {
int n;
cin >> n;
map<string, Word> vars;
ll ans = 0;
for (int i = 0; i < n; i++) {
string var;
cin >> var;
string opr;
cin >> opr;
if (opr == "=") {
string a, plus, b;
cin >> a >> plus >> b;
vars[var] = merge(vars[a], vars[b]);
} else {
string str;
cin >> str;
Word word;
word.len = str.length();
word.cnt = count(str, "haha");
word.s = str;
vars[var] = word;
}
ans = vars[var].cnt;
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Автор задачи: Supermagzzz, Stepavly
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
int cnt(string s) {
int i = 0, result = 0;
while ((i = s.find("haha", i)) != string::npos)
i++, result++;
return result;
}
string comp(string s) {
return s.length() <= 2 ? s : s.substr(0, 3) + "#" + s.substr(s.length() - 3);
}
int main() {
int tt;
cin >> tt;
forn(t, tt) {
int n;
cin >> n;
map<string, pair<string, li>> vars;
string v, r;
forn(i, n) {
string op;
cin >> v >> op;
if (op == ":=") {
cin >> r;
vars[v] = {comp(r), cnt(r)};
} else {
string a, b;
cin >> a >> op >> b;
r = vars[a].first + vars[b].first;
vars[v] = {comp(r), cnt(r) + vars[a].second + vars[b].second};
}
}
cout << vars[v].second << endl;
}
}
Автор задачи: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#include "random"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
void solve() {
ll x, y, a, b;
cin >> x >> y >> a >> b;
ll l = 0, r = 1e9 + 100;
if (a == b) {
cout << min(x, y) / a << "\n";
return;
}
if (a < b) {
swap(a, b);
}
while (r - l > 1) {
ll m = (l + r) / 2;
ll right = floorl((x - m * b) * 1.0l / (a - b));
ll left = ceill((y - m * a) * 1.0l / (b - a));
if (max(left, 0ll) <= min(right, m)) {
l = m;
} else {
r = m;
}
}
cout << l << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}