Автор задачи: 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 - Another Problem About Dividing Numbers
Автор задачи: 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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;
ll calcPref(ll n, ll suff, int remainLen, int suffLen, bool isZero) {
if (suff >= n) {
return 0;
} else if (remainLen == 0) {
return suff < n;
} else if (suff == 0 && n <= 10) {
return 0;
}
ll l = suff == 0 ? 1 : 0, r = 1;
for (int i = 0; i < remainLen; i++) {
r *= 10;
}
ll pw = 1;
for (int i = 0; i < suffLen; i++) {
pw *= 10;
}
if (l * pw + suff >= n) {
return 0;
}
while (r - l > 1) {
ll m = (l + r) / 2;
ll x = m * pw + suff;
if (x >= n) {
r = m;
} else {
l = m;
}
}
return suff == 0 ? l : l + 1;
}
ll calc(ll n) {
if (n <= 1) {
return 0;
}
ll res = 0;
ll suff = 0;
ll pw = 1;
for (int len = 0; len <= 9; len++) {
for (int d = 0; d <= 9; d++) {
res += calcPref(n, suff + pw * d, 8 - len, len + 1, d == 0);
}
suff = 10 * suff + 9;
pw *= 10;
}
return res;
}
void solve() {
ll l, r;
cin >> l >> r;
cout << calc(r) - calc(l) << 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() {
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();
}
}