Спасибо за участие в самом исекайнутом контесте на NyaForces!
Мы честно-честно старались над задачами.
2072A - Новый мир, новый я, новый массив
Идея: ne_justlm
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k, p;
cin >> n >> k >> p;
if (-n * p <= k && k <= n * p) {
cout << (abs(k) + p - 1) / p << '\n';
} else {
cout << "-1\n";
}
}
int main() {
int tt;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
2072B - Будучи казначеем в прошлом, я помогаю гоблинам обманывать людей
Идея: ne_justlm
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int64_t dash = count(s.begin(), s.end(), '-');
int64_t under = n - dash;
int64_t ans = (dash / 2) * (dash - dash / 2) * under;
cout << ans << '\n';
}
int main() {
int tt;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
2072C - Создание ключей от хранИЛИщ стало моим основным навыком
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
using namespace std;
void Solve() {
int len, val;
cin >> len >> val;
vector<int> ans(len, val);
int or_val = 0;
bool flag = true;
for (int i = 0; i < len - 1; ++i) {
if (((or_val | i) & val) == (or_val | i)) {
or_val |= i;
ans[i] = i;
} else {
flag = false;
break;
}
}
if (flag && (or_val | (len - 1)) == val) {
ans[len - 1] = len - 1;
}
for (auto it : ans) cout << it << ' ';
cout << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int test_count = 1;
cin >> test_count;
while (test_count --> 0) Solve();
}
2072D - Для магов нет ничего сложного в экзамене, но я его не осилил
Идея: ne_justlm
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int best_diff = 0, L = 0, R = 0;
for (int i = 0; i < n; ++i) {
int cnt_greater = 0, cnt_less = 0;
for (int j = i + 1; j < n; ++j) {
cnt_greater += a[j] > a[i];
cnt_less += a[j] < a[i];
if (best_diff > cnt_greater - cnt_less) {
best_diff = cnt_greater - cnt_less;
L = i, R = j;
}
}
}
cout << L + 1 << ' ' << R + 1 << '\n';
}
int main() {
int tt = 1;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
2072E - Тебе же нравится герой, который бьёт по площади двойным уроном?
Идея: ne_justlm
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
vector<pair<int64_t, int64_t>> rec(int64_t k, int64_t x0 = 0, int64_t y0 = 0) {
if (!k) {
return {};
}
int64_t delta = 0;
while (delta * (delta - 1) / 2 <= k) {
delta++;
}
delta--;
auto remaining = rec(k - delta * (delta - 1) / 2, x0 + delta + 1, y0 + 1);
vector<pair<int64_t, int64_t>> ans;
for (int x = x0; x < x0 + delta; ++x) {
ans.push_back({x, y0});
}
ans.insert(ans.end(), remaining.begin(), remaining.end());
return ans;
}
void solve() {
int64_t k;
cin >> k;
if (!k) {
cout << "1\n69 52\n";
return;
}
auto ans = rec(k, 0, 0);
cout << ans.size() << '\n';
for (auto [x, y] : ans) {
cout << x << ' ' << y << '\n';
}
}
int main() {
int tt = 1;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
2072F - Прощай, жизнь банкира, здравствуй, жизнь мага
Идея: itz_pabloo
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
constexpr int64_t kMaxN = 1e6 + 69;
vector<int64_t> c(kMaxN);
void precalc() {
c[0] = c[1] = 0;
for (int i = 2; i < kMaxN; ++i) {
c[i] = c[i - 1];
int x = i;
while (x % 2 == 0) {
x /= 2, c[i]++;
}
}
}
void solve() {
int n, k;
cin >> n >> k;
--n;
for (int i = 0; i <= n; ++i) {
cout << k * (c[n] == c[i] + c[n - i]) << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
precalc();
int tt = 1;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
2072G - Переворачивая числа 300 лет, сам того не заметив, посчитал сумму
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
constexpr int64_t mod = 1e9 + 7;
constexpr int64_t twoInv = 500'000'004;
constexpr int64_t sixInv = 166'666'668;
int64_t add(int64_t a, int64_t b) {
return (a % mod + b % mod) % mod;
}
int64_t mns(int64_t a, int64_t b) {
return (a % mod - b % mod + mod) % mod;
}
int64_t mul(int64_t a, int64_t b) {
return (a % mod) * (b % mod) % mod;
}
int64_t rev(int64_t n, int64_t p) {
int64_t res = 0;
while (n) {
res = add(mul(res, p), n % p);
n /= p;
}
return res;
}
int64_t stupid(int64_t n, int64_t k) {
int64_t res = 0;
for (int64_t p = 2; p <= k; ++p) {
res = add(res, rev(n, p));
}
return res;
}
int64_t sum1(int64_t r) {
return mul(mul(r, r + 1), twoInv);
}
int64_t sum1(int64_t l, int64_t r) {
return mns(sum1(r), sum1(l - 1));
}
int64_t sum2(int64_t r) {
return mul(mul(mul(r, r + 1), 2 * r + 1), sixInv);
}
int64_t sum2(int64_t l, int64_t r) {
return mns(sum2(r), sum2(l - 1));
}
int64_t get(int64_t n, int64_t l, int64_t r) {
if (l > r) {
return 0;
}
int64_t res = mul(sum1(l, r), n);
int64_t minus = 0, plus = 0;
int64_t L = l;
while (L <= r) {
int64_t value = n / L;
int64_t R = min(r, n / value);
minus = add(minus, mul(sum2(L, R), value));
plus = add(plus, mul(R - L + 1, value));
L = R + 1;
}
return add(mns(res, minus), plus);
}
void solve() {
int64_t n, k;
cin >> n >> k;
int64_t sq = (int64_t)sqrtl((long double)n);
int64_t ans = mul(max<int64_t>(0, k - n), n);
ans = add(ans, stupid(n, min(sq, k)));
ans = add(ans, get(n, sq + 1, min(n, k)));
cout << ans << '\n';
}
int main() {
int tt = 1;
cin >> tt;
while (tt --> 0) {
solve();
}
return 0;
}
F was so good!
Apart from the Pascal's triangle solution, You can do it by recursion and I learned that the self-similar repeating fractal pattern formed by F is called a Sierpinski's triangle!
It also corresponds exactly to Pascal's triangle, taken modulo 2, a beautiful problem.
Thanks to the authors for a good round
constructive contest
lol,I feel like I did a combinatorical maths competiton instead of a codeforces round
Thanks for a balanced and well-paced contest with interesting problems!
Good contest, help to learn and enhance problem-solving skills.
For the F, if we use Lucas' Theorem, we can actually deduce that $$$\binom{n}{k}\mod 2$$$ is 1 only if $$$k$$$ in binary is a submask of $$$n$$$, in other words if $$$k$$$&$$$n$$$ equals $$$k$$$
With this there's an elegant two-line solution in $$$O(n)$$$:
Many thanks to the creators of the round for the original names for the problems, I laughed heartily
иначе говоря, лишь посмотрев все исекаи мира мы обретаем силу писать раунды на кф
some how deepseek solved G on first try
ne_justlm In fact, the first part of the problem G is not $$$O(\sqrt{n} \log n)$$$. The reason is that the total time is equal to $$$\sum\limits_{i=2}^{\sqrt{n}} \frac{\ln n}{\ln i}$$$, and since the logarithmic integration yields a complexity of $$$\int\limits_{x=2}^\sqrt{n} \frac{1}{\ln x} dx=O(\frac{\sqrt n}{\ln n})$$$ for the latter part, the total complexity is $$$O(\sqrt{n})$$$