codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2195.md (9311B)


      1 Source: https://codeforces.com/blog/entry/151174
      2 
      3 I hope you enjoyed any number of problems in the contest!
      4 
      5 Solution codes will be posted after the open hack phase. They have now been added.
      6 
      7 ## [2195A - Sieve of Erato67henes](/contest/2195/problem/A "Codeforces Round 1080 (Div. 3)")
      8 
      9 **Rate the problem!**
     10 
     11 * Epic
     12 * Good
     13 * Moderate
     14 * Bad
     15 * Horrendous
     16 
     17 **Editorial**
     18 
     19 Tutorial is loading...
     20 
     21 **Code**
     22 
     23 ```
     24 for _ in range(int(input())):
     25   n=int(input())
     26   a=[*map(int,input().split())]
     27   if 67 in a:
     28     print("YES")
     29   else:
     30     print("NO")
     31 ```
     32 
     33 ## [2195B - Heapify 1](/contest/2195/problem/B "Codeforces Round 1080 (Div. 3)")
     34 
     35 **Rate the problem!**
     36 
     37 * Epic
     38 * Good
     39 * Moderate
     40 * Bad
     41 * Horrendous
     42 
     43 **Editorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Code**
     48 
     49 ```
     50 #include<bits/stdc++.h>
     51 using namespace std;
     52 using ll=long long;
     53 
     54 int main()
     55 {
     56   cin.tie(0)->sync_with_stdio(0);
     57   int t;cin>>t;
     58   while(t--)
     59   {
     60     int n;cin>>n;
     61     vector<int>a(n+1);
     62     for(int i=1;i<=n;i++)
     63     {
     64       cin>>a[i];
     65     }
     66     for(int i=1;i<=n;i+=2)
     67     {
     68       for(int j=i;j<=n;j*=2)
     69       {
     70         for(int k=i*2;k<=n;k*=2)
     71         {
     72           if(a[k/2]>a[k])swap(a[k/2],a[k]);
     73         }
     74       }
     75     }
     76     if(is_sorted(begin(a),end(a)))cout<<"YES\n";
     77     else cout<<"NO\n";
     78   }
     79 }
     80 ```
     81 
     82 ## [2195C - Dice Roll Sequence](/contest/2195/problem/C "Codeforces Round 1080 (Div. 3)")
     83 
     84 **Rate the problem!**
     85 
     86 * Epic
     87 * Good
     88 * Moderate
     89 * Bad
     90 * Horrendous
     91 
     92 **Editorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Code**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 using namespace std;
    101  
    102 typedef long long int ll;
    103  
    104 void solve() {
    105     int n;
    106     cin >> n;
    107     vector<int> a(n);
    108     for (int i = 0; i < n; i++) cin >> a[i];
    109  
    110     int ans = 0;
    111     for (int i = 1; i < n; i++) {
    112         if (a[i] + a[i-1] == 7 or a[i] == a[i-1]) ans++, i++;
    113     }
    114  
    115     cout << ans;
    116 }
    117  
    118 int main() {
    119     ios::sync_with_stdio(0); cin.tie(0);
    120     ll tc = 1;
    121     cin >> tc;
    122     for (ll i = 1; i <= tc; i++) {
    123         solve();
    124         cout << '\n';
    125     }
    126 }
    127 ```
    128 
    129 ## [2195D - Absolute Cinema](/contest/2195/problem/D "Codeforces Round 1080 (Div. 3)")
    130 
    131 **Rate the problem!**
    132 
    133 * Epic
    134 * Good
    135 * Moderate
    136 * Bad
    137 * Horrendous
    138 
    139 **Editorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Code**
    144 
    145 ```
    146 #include<bits/stdc++.h>
    147 using namespace std;
    148 using ll=long long;
    149  
    150 vector<ll>solve(ll n,vector<ll>f)
    151 {
    152   vector<ll>vec(n);
    153   for(int i=1;i+1<n;i++)
    154   {
    155     if((f[i+1]+f[i-1]-2*f[i])%2!=0)return {};
    156     vec[i]=(f[i+1]+f[i-1]-2*f[i])/2;
    157     if(abs(vec[i])>1000)return {};
    158   }
    159   auto g=[&](ll j)
    160   {
    161     ll w=f[j];
    162     for(int i=1;i+1<n;i++)
    163     {
    164       w-=vec[i]*abs(i-j);
    165     }
    166     return w;
    167   };
    168   ll g1=g(0),gn=g(n-1);
    169   if(gn%(n-1)!=0)return {};
    170   if(g1%(n-1)!=0)return {};
    171   vec[0]=gn/(n-1);
    172   vec[n-1]=g1/(n-1);
    173   if(abs(vec[0])>1000||abs(vec[n-1])>1000)return {};
    174   return vec;
    175 }
    176 
    177 int main()
    178 {
    179   int t;cin>>t;
    180   while(t--)
    181   {
    182     ll n;cin>>n;
    183     vector<ll>f(n);
    184     for(ll&i:f)cin>>i;
    185     auto a=solve(n,f);
    186     assert(a.size()==n);
    187     for(int i=0;i<n;i++)cout<<a[i]<<" \n"[i+1==n];
    188   }
    189 }
    190 ```
    191 
    192 ## [2195E - Idiot First Search](/contest/2195/problem/E "Codeforces Round 1080 (Div. 3)")
    193 
    194 **Rate the problem!**
    195 
    196 * Epic
    197 * Good
    198 * Moderate
    199 * Bad
    200 * Horrendous
    201 
    202 **Editorial**
    203 
    204 Tutorial is loading...
    205 
    206 **Code**
    207 
    208 ```
    209 #include<bits/stdc++.h>
    210 using namespace std;
    211 using ll=long long;
    212 const ll md=1000000007;
    213  
    214 int main()
    215 {
    216   int t;cin>>t;
    217   while(t--)
    218   {
    219     ll n;cin>>n;
    220     vector<ll>L(n),R(n);
    221     for(int i=0;i<n;i++)
    222     {
    223       cin>>L[i]>>R[i];
    224       L[i]--;R[i]--;
    225     }
    226     vector<ll>dp(n);
    227     auto dfs1=[&](auto dfs1,int x)->ll
    228     {
    229       if(L[x]==-1)return dp[x]=1;
    230       else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3)%md;
    231     };
    232     dfs1(dfs1,0);
    233     auto dfs2=[&](auto dfs2,int x)->void
    234     {
    235       if(L[x]==-1)return;
    236       else
    237       {
    238         dp[L[x]]=(dp[L[x]]+dp[x])%md;
    239         dp[R[x]]=(dp[R[x]]+dp[x])%md;
    240         dfs2(dfs2,L[x]);
    241         dfs2(dfs2,R[x]);
    242       }
    243     };
    244     dfs2(dfs2,0);
    245     for(int i=0;i<n;i++)cout<<dp[i]<<" \n"[i+1==n];
    246   }
    247 }
    248 ```
    249 
    250 ## [2195F - Parabola Independence](/contest/2195/problem/F "Codeforces Round 1080 (Div. 3)")
    251 
    252 **Rate the problem!**
    253 
    254 * Epic
    255 * Good
    256 * Moderate
    257 * Bad
    258 * Horrendous
    259 
    260 **Editorial**
    261 
    262 Tutorial is loading...
    263 
    264 **Code**
    265 
    266 ```
    267 #include<bits/stdc++.h>
    268 using namespace std;
    269 using ll=long long;
    270  
    271 struct Quad{ll a,b,c;}; // ax^2+bx+c
    272  
    273 // f(x) < g(x) for all x
    274 bool comp(Quad f,Quad g)
    275 {
    276   if(f.a>g.a)return false;
    277   else if(f.a==g.a)return f.b==g.b&&f.c<g.c;
    278   else
    279   {
    280     Quad Q{g.a-f.a,g.b-f.b,g.c-f.c};
    281     return Q.b*Q.b-4*Q.a*Q.c<0;
    282   }
    283 }
    284  
    285 int main()
    286 {
    287   cin.tie(0)->sync_with_stdio(0);
    288   int t;cin>>t;
    289   while(t--)
    290   {
    291     int n;cin>>n;
    292     vector<Quad>vec(n);
    293     for(Quad&Q:vec)cin>>Q.a>>Q.b>>Q.c;
    294     vector<vector<int>>adj1(n),adj2(n);
    295     vector<int>id1(n),id2(n),dp1(n,1),dp2(n,1);
    296     for(int i=0;i<n;i++)
    297     {
    298       for(int j=0;j<n;j++)
    299       {
    300         if(comp(vec[i],vec[j]))
    301         {
    302           adj1[i].push_back(j);
    303           id1[j]++;
    304           adj2[j].push_back(i);
    305           id2[i]++;
    306         }
    307       }
    308     }
    309     queue<int>Q;
    310     for(int i=0;i<n;i++)if(id1[i]==0)Q.push(i);
    311     while(!Q.empty())
    312     {
    313       int a=Q.front();Q.pop();
    314       for(int i:adj1[a])
    315       {
    316         id1[i]--;dp1[i]=max(dp1[i],dp1[a]+1);
    317         if(id1[i]==0)Q.push(i);
    318       }
    319     }
    320     for(int i=0;i<n;i++)if(id2[i]==0)Q.push(i);
    321     while(!Q.empty())
    322     {
    323       int a=Q.front();Q.pop();
    324       for(int i:adj2[a])
    325       {
    326         id2[i]--;dp2[i]=max(dp2[i],dp2[a]+1);
    327         if(id2[i]==0)Q.push(i);
    328       }
    329     }
    330     for(int i=0;i<n;i++)cout<<dp1[i]+dp2[i]-1<<" \n"[i+1==n];
    331   }
    332 }
    333 ```
    334 
    335 ## [2195G - Idiot First Search and Queries](/contest/2195/problem/G "Codeforces Round 1080 (Div. 3)")
    336 
    337 **Rate the problem!**
    338 
    339 * Epic
    340 * Good
    341 * Moderate
    342 * Bad
    343 * Horrendous
    344 
    345 **Editorial**
    346 
    347 Tutorial is loading...
    348 
    349 **Code**
    350 
    351 ```
    352 #include<bits/stdc++.h>
    353 using namespace std;
    354 using ll=long long;
    355  
    356 int main()
    357 {
    358   ll t;cin>>t;
    359   while(t--)
    360   {
    361     ll n,q;cin>>n>>q;
    362     vector<ll>L(n),R(n),P(n,-1);
    363     for(int i=0;i<n;i++)P[i]=i;
    364     for(int i=0;i<n;i++)
    365     {
    366       cin>>L[i]>>R[i];
    367       L[i]--;R[i]--;
    368       if(L[i]!=-1)
    369       {
    370         P[L[i]]=i;
    371         P[R[i]]=i;
    372       }
    373     }
    374     vector<ll>dp(n);
    375     vector<array<int,20>>lift(n);
    376     auto dfs1=[&](auto dfs1,int x)->ll
    377     {
    378       if(L[x]==-1)return dp[x]=1;
    379       else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3);
    380     };
    381     dfs1(dfs1,0);
    382     vector<ll>euler,tin(n);
    383     auto dfs2=[&](auto dfs2,int x)->void
    384     {
    385       tin[x]=euler.size();
    386       lift[x][0]=P[x];
    387       for(int j=1;j<20;j++)
    388       {
    389         lift[x][j]=lift[lift[x][j-1]][j-1];
    390       }
    391       if(L[x]==-1)
    392       {
    393         euler.push_back(x);
    394         return;
    395       }
    396       else
    397       {
    398         dp[L[x]]=(dp[L[x]]+dp[x]);
    399         dp[R[x]]=(dp[R[x]]+dp[x]);
    400         euler.push_back(x);
    401         dfs2(dfs2,L[x]);
    402         euler.push_back(x);
    403         dfs2(dfs2,R[x]);
    404         euler.push_back(x);
    405       }
    406     };
    407     dfs2(dfs2,0);
    408     while(q--)
    409     {
    410       ll v,k;cin>>v>>k;
    411       v--;
    412       ll w=v;
    413       for(int j=19;j>=0;j--)
    414       {
    415         if(dp[v]-dp[lift[w][j]]<=k)w=lift[w][j];
    416       }
    417       k-=dp[v]-dp[w];
    418       cout<<euler[tin[w]+k]+1<<" \n"[q==0];
    419     }
    420   }
    421 }
    422 ```
    423 
    424 ## [2195H - Codeforces Heuristic Contest 001](/contest/2195/problem/H "Codeforces Round 1080 (Div. 3)")
    425 
    426 **Rate the problem!**
    427 
    428 * Epic
    429 * Good
    430 * Moderate
    431 * Bad
    432 * Horrendous
    433 
    434 **Editorial**
    435 
    436 Tutorial is loading...
    437 
    438 **Code**
    439 
    440 ```
    441 #include<bits/stdc++.h>
    442 using namespace std;
    443 using ll=long long;
    444  
    445 string base[9]=
    446 {
    447 "AABBCCDEE",
    448 "ABFFCDDGE",
    449 "HHFIJKLLG",
    450 "MHIJJKKLG",
    451 "MMINNOOPP",
    452 "QRNSOTTUP",
    453 "QRRSSTVUU",
    454 "WQXXYVVZ_",
    455 "WWXYYZZ__"
    456 };
    457  
    458 struct Point
    459 {
    460   ll x,y;
    461   Point(ll xx,ll yy):x(xx),y(yy){}
    462 };
    463  
    464 ostream& operator<<(ostream&os,const Point& P)
    465 {
    466   os<<P.x<<" "<<P.y;
    467   return os;
    468 }
    469  
    470 using Pgon=vector<Point>;
    471  
    472 vector<Pgon>basis(string b[],int n)
    473 {
    474   vector<Pgon>res;
    475   map<char,Pgon>mp;
    476   for(int i=0;i<n;i++)
    477   {
    478     for(int j=0;j<n;j++)
    479     {
    480       mp[b[i][j]].emplace_back(i+1,j+1);
    481     }
    482   }
    483   for(auto[c,v]:mp)res.push_back(v);
    484   return res;
    485 }
    486  
    487 void solve(int n)
    488 {
    489   if(n==1)
    490   {
    491     cout<<"2\n";
    492     cout<<"1 1 1 2 2 1\n";
    493     cout<<"2 3 3 2 3 3\n";
    494   }
    495   else if(n%2==0)
    496   {
    497     cout<<3*n*n<<"\n";
    498     int cnt=0;
    499     for(int i=1;i<=3*n;i+=3)
    500     {
    501       for(int j=1;j<=3*n;j+=2)
    502       {
    503         cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
    504         cout<<Point(i+1,j+1)<<" "<<Point(i+2,j+1)<<" "<<Point(i+2,j)<<"\n";
    505         cnt+=2;
    506       }
    507     }
    508     assert(cnt==3*n*n);
    509   }
    510   else
    511   {
    512     cout<<3*n*n<<"\n";
    513     int cnt=0;
    514     for(auto p:basis(base,9))
    515     {
    516       cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<"\n";
    517       cnt++;
    518     }
    519     for(int i=1;i<=9;i+=3)
    520     {
    521       // 3*n-9=3*(n-3)=even
    522       for(int j=10;j<=3*n;j+=2)
    523       {
    524         cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
    525         cout<<Point(i+1,j+1)<<" "<<Point(i+2,j)<<" "<<Point(i+2,j+1)<<"\n";
    526         cnt+=2;
    527       }
    528     }
    529     for(int i=10;i<=3*n;i+=2)
    530     {
    531       for(int j=1;j<=3*n;j+=3)
    532       {
    533         cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
    534         cout<<Point(i+1,j+1)<<" "<<Point(i+1,j+2)<<" "<<Point(i,j+2)<<"\n";
    535         cnt+=2;
    536       }
    537     }
    538     assert(cnt==3*n*n);
    539   }
    540 }
    541  
    542 int main()
    543 {
    544   cin.tie(0)->sync_with_stdio(0);
    545   int t;cin>>t;
    546   while(t--)
    547   {
    548     int n;cin>>n;
    549     solve(n);
    550   }
    551 }
    552 ```
    553 
    554 Thank you for participating, and hope to see you again soon!