Задача предложена пользователем Ali Ibrahim C137.
Заметим, что если есть пара соседних не взаимнопростых чисел, то мы обязаны между ними вставить какое-нибудь число. С другой стороны мы всегда можем вставить число 1.
Решение на С++const int N = 1010;
int n, a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };
vector<int> ans;
forn(i, n) {
ans.pb(a[i]);
if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
ans.pb(1);
}
cout << sz(ans) - n << endl;
forn(i, sz(ans)) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
Сложность: O(nlogn).
Задача предложена пользователем Srikanth Bhat bharsi.
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и подвохов.
Решение на C++int n, m;
bool read() {
return !!(cin >> n >> m);
}
const int N = 111;
int a[N][4];
void solve() {
forn(i, n) {
a[i][0] = 2 * i;
a[i][1] = 2 * (n + i);
a[i][2] = 2 * (n + i) + 1;
a[i][3] = 2 * i + 1;
}
vector<int> ans;
forn(i, n) {
ans.pb(a[i][1]);
ans.pb(a[i][0]);
ans.pb(a[i][2]);
ans.pb(a[i][3]);
}
nfor(i, sz(ans)) // inverse order
if (ans[i] >= m)
ans.erase(ans.begin() + i);
forn(i, m) {
if (i) putchar(' ');
printf("%d", ans[i] + 1);
}
puts("");
}
Сложность: O(n).
Задача предложена пользователем Mohammad Amin Raeisi Smaug.
Назовём отрезок [l, r] хорошим если в нём не более k ноликов. Заметим, что если отрезок [l, r] хороший, то отрезок [l + 1, r] тоже хороший. Таким образом, можно воспользоваться методом двух указателей: один указатель это l, а второй это r. Будем перебирать l слева направо и двигать r пока можем (для этого нужно просто поддерживать количество ноликов в текущем отрезке).
Решение на C++const int N = 1200300;
int n, k;
int a[N];
bool read() {
if (!(cin >> n >> k)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
int ansl = 0, ansr = 0;
int j = 0, cnt = 0;
forn(i, n) {
if (j < i) {
j = i;
cnt = 0;
}
while (j < n) {
int ncnt = cnt + !a[j];
if (ncnt > k) break;
cnt += !a[j];
j++;
}
if (j - i > ansr - ansl)
ansl = i, ansr = j;
if (cnt > 0) cnt -= !a[i];
}
cout << ansr - ansl << endl;
fore(i, ansl, ansr) a[i] = 1;
forn(i, n) {
if (i) putchar(' ');
printf("%d", a[i]);
}
puts("");
}
Сложность: O(n + k).
Задачу предложена участником Sadegh Mahdavi smahdavi4.
Как известно диагонали параллелограмма делят друг друга пополам. Переберём пару точек a, b и рассмотрим середину отрезка 
: c = (a + b) / 2. Для всех середин отрезков посчитаем число cntc — количество пар точек, с этой серединой. Легко видеть, что ответ это 
.
Решение на C++const int N = 2020;
int n;
int x[N], y[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n)
assert(scanf("%d%d", &x[i], &y[i]) == 2);
return true;
}
inline li C2(li n) { return n * (n - 1) / 2; }
void solve() {
map<pti, int> cnt;
forn(i, n)
forn(j, i) {
int cx = x[i] + x[j];
int cy = y[i] + y[j];
cnt[{cx, cy}]++;
}
li ans = 0;
for (const auto& p : cnt)
ans += C2(p.y);
cout << ans << endl;
}
Сложность: O(n2logn).
