Всем привет! Сегодня я хотел бы сделать разбор на те задачи, которые я мог решить на сегодняшнем контесте:)
Задача А
Идея решения:
Мы имеем произведение вида:
[(a1/a2) * (a2/a3) * (a3/a4) * ... * (an-1/an)]
Большая часть элементов сокращается, и в итоге остается только $$$a1 / an$$$. Чтобы произведение было равно 1, необходимо, чтобы a1 = an.
Алгоритм:
- Считываем массив чисел.
- Проверяем, существует ли пара одинаковых чисел, которые могут стоять в начале и конце.
- Если такие найдены → ответ "YES", иначе → "NO".
Особенности:
- Достаточно найти хотя бы одно совпадение в массиве.
- Решение работает за O(n).
Код решения:
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
bool opt = false;
map<ll,ll> mp;
for (ll i = 0;i<n;i++){
cin >> a[i];
mp[a[i]]++;
if(mp[a[i]]>=2){
opt = 1;
}
}
if(!opt){
cout << "NO" <<endl;
}else{
cout << "YES " << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Задача Б
Идея решения:
Нужно минимизировать итоговую сумму при объединении элементов попарно.
Оптимальная стратегия — всегда соединять два наибольших числа. Это гарантирует минимизацию результата.
Алгоритм:
- Сортируем массив по убыванию.
- Проходим массив парами (i и i+1).
- В ответ добавляем только первый элемент пары (он всегда больше).
Особенности:
- Сортировка гарантирует, что каждое объединение учитывает наибольшие элементы.
- В итоге получится минимальная возможная сумма.
Код решения:
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
bool opt = false;
vector<pair<ll,ll>> ans;
map<ll,ll> mp;
for (ll i = 0;i<n;i++){
cin >> a[i];
ans.pb({a[i],i+1});
}
sort(ans.begin(),ans.end());
vector<bool> vis(n+1,false);
ll sm = 0;
sort(a.begin(),a.end());
if(n%2==1){
for (ll i = 0;i<n;i+=2){
sm+=a[i];
}
}else{
for (ll i = 1;i<n;i+=2){
sm+=a[i];
}
}
cout << sm << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Задача С
Идея решения:
Нужно восстановить цепочку порталов с помощью запросов.
Сначала определяем вершину, из которой выходит максимальный путь. Это и будет начальная точка.
Затем шаг за шагом достраиваем всю цепочку.
Алгоритм:
- Формируем вектор из всех вершин и делаем запрос для каждой вершины i. Сохраняем количество путей
cnt[i]. - Определяем вершину с максимальным значением
cnt[i]→ она будет стартом. - Пусть текущая вершина = cur. Для поиска следующей вершины делаем запрос вида
{cur, x}.
- Если результат = 2 → значит, существует путь cur → x.
- Обновляем cur = x.
- Группируем вершины по длинам путей и проверяем их начиная с наибольшей длины.
- Повторяем, пока не восстановим всю цепочку.
Особенности:
- Начальная вершина — та, у которой максимальная длина пути.
- Для каждой длины может быть несколько кандидатов, поэтому проверяем все.
- Итоговый массив вершин и будет ответом.
Код решения:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll ask(ll x, const vector<ll>& s){
cout << "? " << x << " " << s.size() << " ";
for (ll v : s) cout << v << " ";
cout << endl;
cout.flush();
ll ans;
if (!(cin >> ans)) exit(0);
if (ans == -1) exit(0);
return ans;
}
void bruh(){
ll n;
if (!(cin >> n)) return;
vector<ll> res(n+1);
vector<ll> test(n);
iota(test.begin(), test.end(), 1);
for (ll i = 1; i <= n; ++i){
res[i] = ask(i, test);
}
ll node = 1, mx = res[1];
for (ll i = 2; i <= n; ++i){
if (res[i] > mx){
mx = res[i];
node = i;
}
}
vector<vector<ll>> gra(mx+1);
for (ll i = 1; i <= n; ++i){
gra[res[i]].pb(i);
}
vector<char> vis(n+1, 0);
ll cur = node;
vis[cur] = 1;
vector<ll> ans;
ans.pb(cur);
for (ll x = mx-1;x>=1;x--){
for (ll u: gra[x]){
vector<ll> S = {cur,u};
ll get = ask(cur,S);
if(get == 2){
cur = u;
ans.pb(cur);
break;
}
}
}
cout << "! " << ans.size() << " ";
for (ll v : ans) cout << v << " ";
cout << endl;
cout.flush();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
if (!(cin >> t)) return 0;
while (t--) bruh();
// return 0;
}
