VK Cup 2022 — Отбор (Engine) и Codeforces Round #844 (Div. 1 + Div. 2)

Привет!

VK Cup 2022 - Отборочный раунд (Engine) начнётся уже скоро: 15.01.2023 15:05 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 6 задач из 8 в квалификационном раунде VK Cup 2022. Раунд будет рейтинговым.

Остальных приглашаем на открытый для всех Codeforces Round #844 (Div. 1 + Div. 2, основан на Отборочном раунде VK Cup 2022), который начнётся в то же время и тоже будет рейтинговым.

Все задачи придуманы и подготовлены мной. Также этот раунд стал лучше благодаря KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa.

Участникам будет предложено 8 задач и 3 часа на их решение.

64 лучших участника закрытого отборочного раунда получат фирменные футболки VK Cup, а 16 лучших пройдут в финал и смогут побороться за призы 4-5 февраля очно в офисе VK или онлайн:

1-е место — 300 000 рублей;
2-е место — 250 000 рублей;
3-е место — 150 000 рублей;
4-е место — 100 000 рублей.

UPD: Разбор

Поздравляем победителей отборочного раунда:

и остальных участников, попавших в число сильнейших.

Также поздравляем победителей открытого для всех раунда:

и отдельно maroonrk как автора единственного принятого решения по задаче H2.

#include <bits/stdc++.h> using namespace std; #define nl '\n' #define sp ' ' #define ll long long #define vi vector<int> #define vl vector<ll> #define vvi vector<vi> #define vvl vector<vl> #define si unordered_set<int> #define sl unordered_set<ll> #define tsi set<int> #define tsl set<ll> #define pii pair<int,int> #define pll pair<ll,ll> #define vpii vector<pii> #define vpll vector<pll> #define tmii map<int,int> #define tmll map<ll,ll> #define mii unordered_map<int,int> #define mll unordered_map<ll,ll> #define pqi priority_queue<int> #define pqig priority_queue<int,vi,less<int>> #define pql priority_queue<ll> #define pqlg priority_queue<ll,vl,less<ll>> #define pqpii priority_queue<pii> #define pqpll priority_queue<pll> #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define yesno(a) cout<<((a)?"YES\n":"NO\n"); #define outrange(x,min,max) ((x)<(min) || (x)>(max)) #define nano (chrono::system_clock::now().time_since_epoch().count()) #define init_rng mt19937 rng(nano) template<typename L,typename R> ostream& operator<<(ostream& out,pair<L,R>& p){ out<<'('<<p.first<<','<<p.second<<')'; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T>& v){ for(auto &i:v) out<<i<<' '; out<<nl; return out; } template<typename K,typename V> ostream& operator<<(ostream& out,map<K,V>& m){ out<<'['; for(auto &[k,v]:m) { out<<k<<':'<<v<<sp; } out<<"]\n"; return out; } template<typename K,typename V> ostream& operator<<(ostream& out,unordered_map<K,V>& m){ out<<'['; for(auto &[k,v]:m) { out<<k<<':'<<v<<sp; } out<<"]\n"; return out; } #ifdef adj8 int dx[8]={1,1,0,-1,-1,-1,0,1}; int dy[8]={0,1,1,1,0,-1,-1,-1}; #endif #ifdef adj4 int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; #endif const int MAX=55; int a[MAX]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; //cin>>t; t=50; while(t--){ int n; n=50;//cin>>n; for(int i=0;i<n;i++){ //cin>>a[i]; a[i]=1+20408160*i; } int count=0; mll m; for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ int p=a[i]; int q=a[j]; if((3&(q-p))==2) continue; int k=2; if((q-p)&1) k--; for(;k*k<=q-p;k+=2){ count++; if((q-p)%k) continue; int l=(q-p)/k; if((k+l)&1) continue; ll n=(k+l)>>1; ll x=n*n-q; if(x>=0) m[x]++; } } } if(m.empty()) cout<<1<<nl; else{ ll max=0; for(auto [k,v]:m){ if(v>max) max=v; } max=1+(ll)sqrt(2*max); cout<<max<<nl; } cout<<count<<nl; } }