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  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 ```