codeforces-scrape

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

2074.md (6210B)


      1 Source: https://codeforces.com/blog/entry/140540
      2 
      3 Well, that was a blast, certainly. I hope that you... learned a lot from the contest. I wouldn't say "enjoy the contest", I know most of you hate geometry, I get you. But please do remember that, at least I did try my best to make every problem as high quality as possible. Like, if you don't get familiar with thinking about geometry now, you might never get familiar with it in the future. Though I apologize that E was quite hard, I suggest you to upsolve or read the editorials of the tasks you could not solve. I am telling you, it will be an experience that will make you improve much more from now.
      4 
      5 Solution codes will be posted after the open hack phase. They are now added.
      6 
      7 **Spoiler**
      8 
      9 ![ ](/predownloaded/ff/73/ff73b05d3e02d7606b66f2213c0c846aa7d26988.png)
     10 
     11 ## [2074A - Draw a Square](/contest/2074/problem/A "Codeforces Round 1009 (Div. 3)")
     12 
     13 **Editorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Code**
     18 
     19 ```
     20 for i in range(int(input())):
     21     l,r,d,u=map(int,input().split())
     22     if l==r==d==u:
     23         print("Yes")
     24     else:
     25         print("No")
     26 ```
     27 
     28 ## [2074B - The Third Side](/contest/2074/problem/B "Codeforces Round 1009 (Div. 3)")
     29 
     30 **Editorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Code**
     35 
     36 ```
     37 t = int(input())
     38 for _ in range(t):
     39     n = int(input())
     40     sm = sum(map(int, input().split()))
     41     print(sm - n + 1)
     42 ```
     43 
     44 ## [2074C - XOR and Triangle](/contest/2074/problem/C "Codeforces Round 1009 (Div. 3)")
     45 
     46 **Editorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Code**
     51 
     52 ```
     53 t = int(input())
     54 for _ in range(t):
     55     x = int(input())
     56     ans = -1
     57     for i in range(30):
     58         for j in range(30):
     59             y = (1 << i) | (1 << j)
     60             if y < x and x + y > (x ^ y) and y + (x ^ y) > x:
     61                 ans = y
     62     print(ans)
     63 ```
     64 
     65 ## [2074D - Counting Points](/contest/2074/problem/D "Codeforces Round 1009 (Div. 3)")
     66 
     67 **Editorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Code**
     72 
     73 ```
     74 #include<bits/stdc++.h>
     75 using namespace std;
     76 using ll=long long;
     77  
     78 int main()
     79 {
     80     int t;cin>>t;
     81     for(int i=0;i<t;i++)
     82     {
     83         int n,m;cin>>n>>m;
     84         map<ll,ll>cnt;
     85         auto isqrt=[&](ll x)
     86         {
     87             ll val=sqrtl(x)+5;
     88             while(val*val>x)val--;
     89             return val;
     90         };
     91         vector<ll>a(n),r(n);
     92         for(ll&i:a)cin>>i;
     93         for(ll&i:r)cin>>i;
     94         for(int i=0;i<n;i++)
     95         {
     96             ll aa=a[i],rr=r[i];
     97             for(ll x=aa-rr;x<=aa+rr;x++)
     98             {
     99                 cnt[x]=max(cnt[x],2*isqrt(rr*rr-(x-aa)*(x-aa))+1);
    100             }
    101         }
    102         ll ans=0;
    103         for(auto[x,c]:cnt)ans+=c;
    104         cout<<ans<<"\n";
    105     }
    106 }
    107 ```
    108 
    109 ## [2074E - Empty Triangle](/contest/2074/problem/E "Codeforces Round 1009 (Div. 3)")
    110 
    111 **Editorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Code**
    116 
    117 ```
    118 #include<bits/stdc++.h>
    119 using namespace std;
    120  
    121 int main()
    122 {
    123     mt19937 mt(727);
    124     uniform_int_distribution uni(1,3);
    125     int tc;cin>>tc;
    126     while(tc--)
    127     {
    128         int n;cin>>n;
    129         if(n<0)return 0;
    130         vector<int>vec(n);
    131         for(int i=0;i<n;i++)vec[i]=i+1;
    132         shuffle(begin(vec),end(vec),mt);
    133         int ii=vec[0],jj=vec[1],kk=vec[2];
    134         cerr<<n<<endl;
    135         while(1)
    136         {
    137             cout<<"? "<<ii<<" "<<jj<<" "<<kk<<endl;
    138             int id;cin>>id;
    139             if(id<0)return 0;
    140             if(id==0)break;
    141             int sw=uni(mt);
    142             if(sw==1)ii=id;
    143             else if(sw==2)jj=id;
    144             else kk=id;
    145         }
    146         cout<<"! "<<ii<<" "<<jj<<" "<<kk<<endl;
    147     }
    148 }
    149 ```
    150 
    151 ## [2074F - Counting Necessary Nodes](/contest/2074/problem/F "Codeforces Round 1009 (Div. 3)")
    152 
    153 **Editorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Code**
    158 
    159 ```
    160 #include<bits/stdc++.h>
    161 using namespace std;
    162 using ll=long long;
    163  
    164 int main()
    165 {
    166     int t;cin>>t;
    167     for(int i=0;i<t;i++)
    168     {
    169         int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
    170         vector<pair<ll,ll>>it1,it2;
    171         auto rec=[&](auto rec,int L,int R,int l,int r,vector<pair<ll,ll>>&v)->void
    172         {
    173             if(r<=L||l>=R)return;
    174             if(l<=L&&R<=r)
    175             {
    176                 v.emplace_back(L,R);
    177                 return;
    178             }
    179             rec(rec,L,(L+R)/2,l,r,v);
    180             rec(rec,(L+R)/2,R,l,r,v);
    181         };
    182         rec(rec,0,1<<25,l1,r1,it1);
    183         rec(rec,0,1<<25,l2,r2,it2);
    184         ll ans=0;
    185         for(auto[al,ar]:it1)
    186         {
    187             for(auto[bl,br]:it2)
    188             {
    189                 ll a=ar-al,b=br-bl;
    190                 if(a<b)swap(a,b);
    191                 ans+=a/b;
    192             }
    193         }
    194         cout<<ans<<"\n";
    195     }
    196 }
    197 ```
    198 
    199 ## [2074G - Game With Triangles: Season 2](/contest/2074/problem/G "Codeforces Round 1009 (Div. 3)")
    200 
    201 **Editorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Code**
    206 
    207 ```
    208 #include<bits/stdc++.h>
    209 using namespace std;
    210 using ll=long long;
    211  
    212 ll dp[505][505];
    213  
    214 int main()
    215 {
    216     cin.tie(0)->sync_with_stdio(0);
    217     int t;cin>>t;
    218     for(int tc=0;tc<t;tc++)
    219     {
    220         ll n;cin>>n;
    221         vector<ll>vec(n);
    222         for(ll&i:vec)cin>>i;
    223         for(int i=0;i<n;i++)
    224         {
    225             for(int j=0;j<n;j++)dp[i][j]=-1e18;
    226         }
    227         auto value=[&](ll i,ll j,ll k)
    228         {
    229             return i*j*k;
    230         };
    231         for(int len=1;len<=n;len++)
    232         {
    233             for(int L=0;L<n;L++)
    234             {
    235                 ll ans=0;
    236                 ll R=(L+len-1)%n;
    237                 if(len<=2)
    238                 {
    239                     dp[L][R]=0;
    240                     continue;
    241                 }
    242                 if(len==3)
    243                 {
    244                     dp[L][R]=max(0LL,value(vec[L],vec[(L+1)%n],vec[R]));
    245                     continue;
    246                 }
    247                 for(int i=(L+1)%n;i!=R;i=(i+1)%n)
    248                 {
    249                     ll val=value(vec[L],vec[i],vec[R]);
    250                     if(i!=(L+1)%n)val+=dp[(L+1)%n][(i+n-1)%n];
    251                     if(i!=(R+n-1)%n)val+=dp[(i+1)%n][(R+n-1)%n];
    252                     ans=max(ans,val);
    253                 }
    254                 for(int i=L;i!=R;i=(i+1)%n)
    255                 {
    256                     ans=max(ans,dp[L][i]+dp[(i+1)%n][R]);
    257                 }
    258                 dp[L][R]=ans;
    259             }
    260         }
    261         ll ans=0;
    262         for(int i=0;i<n;i++)
    263         {
    264             ans=max(ans,dp[i][(i+n-1)%n]);
    265         }
    266         cout<<ans<<"\n";
    267     }
    268 }
    269 ```