1316.md (8484B)
1 Source: https://codeforces.com/blog/entry/74493 2 3 ### [1316A - Grade Allocation](/contest/1316/problem/A "CodeCraft-20 (Div. 2)") 4 5 **Author:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172") 6 **Development:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172"), [firebolt](/profile/firebolt "Specialist firebolt"), [night_fury208](/profile/night_fury208 "Candidate Master night_fury208") 7 8 **Tutorial** 9 10 Tutorial is loading... 11 12 **Solution** 13 14 ``` 15 #include <bits/stdc++.h> 16 using namespace std; 17 #define ll long long int 18 int main() 19 { 20 ll test; 21 cin>>test; 22 while(test--) 23 { 24 ll n,m; 25 cin>>n>>m; 26 ll s=0; 27 for(ll i=1;i<=n;i++) 28 { 29 ll x; 30 cin>>x; 31 s=s+x; 32 } 33 cout<<min(s,m)<<"\n"; 34 } 35 return 0; 36 } 37 ``` 38 39 ### [1316B - String Modification](/contest/1316/problem/B "CodeCraft-20 (Div. 2)") 40 41 **Author:** [preet_t](/profile/preet_t "Specialist preet_t") 42 **Development:** [preet_t](/profile/preet_t "Specialist preet_t"), [shaanknight](/profile/shaanknight "Master shaanknight"), [night_fury208](/profile/night_fury208 "Candidate Master night_fury208") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 string modified(string& s, int n, int k) { 56 string result_prefix = s.substr(k - 1, n - k + 1); 57 string result_suffix = s.substr(0, k - 1); 58 if (n % 2 == k % 2) 59 reverse(result_suffix.begin(), result_suffix.end()); 60 return result_prefix + result_suffix; 61 } 62 63 int main () { 64 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 65 string s, best_s, temp; 66 int t, n, best_k; 67 cin >> t; 68 while (t--) { 69 cin >> n >> s; 70 best_s = modified(s, n, 1); 71 best_k = 1; 72 for (int k = 2; k <= n; ++k) { 73 temp = modified(s, n, k); 74 if (temp < best_s) { 75 best_s = temp; 76 best_k = k; 77 } 78 } 79 cout << best_s << '\n' << best_k << '\n'; 80 } 81 return 0; 82 } 83 ``` 84 85 ### [1316C - Primitive Primes](/contest/1316/problem/C "CodeCraft-20 (Div. 2)") 86 87 **Author:** [lazyneuron](/profile/lazyneuron "Specialist lazyneuron") 88 **Development:** [lazyneuron](/profile/lazyneuron "Specialist lazyneuron"), [shaanknight](/profile/shaanknight "Master shaanknight"),[firebolt](/profile/firebolt "Specialist firebolt") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution** 95 96 ``` 97 #include<bits/stdc++.h> 98 using namespace std; 99 100 #define ll long long int 101 int main() 102 { 103 ios_base::sync_with_stdio(false); 104 cin.tie(0);cout.tie(0); 105 106 ll n,i,m,x,a,p,fir,sec; 107 108 cin >> n >> m >> p; 109 a=0; 110 for(i=0;i<n;i++) 111 { 112 cin >> x; 113 if(x%p && !a) 114 { 115 a=1; 116 fir=i; 117 } 118 } 119 a=0; 120 for(i=0;i<m;i++) 121 { 122 cin >> x; 123 if(x%p && !a) 124 { 125 a=1; 126 sec=i; 127 } 128 } 129 cout << fir+sec << endl; 130 return 0; 131 } 132 ``` 133 134 ### [1316D - Nash Matrix](/contest/1316/problem/D "CodeCraft-20 (Div. 2)") 135 136 **Author:** [shaanknight](/profile/shaanknight "Master shaanknight") 137 **Development:** [shaanknight](/profile/shaanknight "Master shaanknight"), [riz_1_](/profile/riz_1_ "Expert riz_1_"), [coder_h](/profile/coder_h "Expert coder_h"),[Altitude](/profile/Altitude "Expert Altitude") 138 139 **Tutorial** 140 141 Tutorial is loading... 142 143 **Solution** 144 145 ``` 146 #include<bits/stdc++.h> 147 using namespace std; 148 149 const int M = (1<<10)+5; 150 char mat[M][M]; 151 int x[M][M],y[M][M]; 152 int n; 153 154 bool connect(int p,int q,int r,int s,char d1,char d2) 155 { 156 if(x[r][s] == -1) 157 { 158 mat[p][q] = d1; 159 if(mat[r][s] == '\0') mat[r][s] = d2; 160 return 1; 161 } 162 else 163 return 0; 164 } 165 166 void dfs(int p,int q,char d) 167 { 168 if(mat[p][q] != '\0') return; 169 mat[p][q] = d; 170 171 if(x[p][q] == x[p+1][q] && y[p][q] == y[p+1][q]) 172 dfs(p+1,q,'U'); 173 if(x[p][q] == x[p-1][q] && y[p][q] == y[p-1][q]) 174 dfs(p-1,q,'D'); 175 if(x[p][q] == x[p][q+1] && y[p][q] == y[p][q+1]) 176 dfs(p,q+1,'L'); 177 if(x[p][q] == x[p][q-1] && y[p][q] == y[p][q-1]) 178 dfs(p,q-1,'R'); 179 } 180 181 int main() 182 { 183 ios::sync_with_stdio(false); 184 cin.tie(0); 185 cout.tie(0); 186 187 int i,j; 188 189 cin >> n; 190 191 for(i=1;i<=n;++i) 192 { 193 for(j=1;j<=n;++j) 194 cin >> x[i][j] >> y[i][j]; 195 } 196 197 for(i=1;i<=n;++i) 198 { 199 for(j=1;j<=n;++j) 200 { 201 if(x[i][j] == -1) 202 { 203 bool res = (mat[i][j] != '\0'); 204 if(res == 0) res = connect(i,j,i+1,j,'D','U'); 205 if(res == 0) res = connect(i,j,i,j+1,'R','L'); 206 if(res == 0) res = connect(i,j,i-1,j,'U','D'); 207 if(res == 0) res = connect(i,j,i,j-1,'L','R'); 208 if(res == 0) 209 { 210 cout << "INVALID" << "\n"; 211 return 0; 212 } 213 } 214 else if(x[i][j] == i && y[i][j] == j) 215 dfs(i,j,'X'); 216 } 217 } 218 219 for(i=1;i<=n;++i) 220 { 221 for(j=1;j<=n;++j) 222 { 223 if(mat[i][j] == '\0') 224 { 225 cout << "INVALID" << "\n"; 226 return 0; 227 } 228 } 229 } 230 231 cout << "VALID" << "\n"; 232 233 for(i=1;i<=n;++i) 234 { 235 for(j=1;j<=n;++j) 236 { 237 cout << mat[i][j]; 238 } 239 cout << "\n"; 240 } 241 242 return 0; 243 } 244 ``` 245 246 ### [1316E - Team Building](/contest/1316/problem/E "CodeCraft-20 (Div. 2)") 247 248 **Author:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172") 249 **Development:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172"), [shaanknight](/profile/shaanknight "Master shaanknight"), [coder_h](/profile/coder_h "Expert coder_h"), [madlad](/profile/madlad "Expert madlad") 250 251 **Tutorial** 252 253 Tutorial is loading... 254 255 **Solution** 256 257 ``` 258 #include <bits/stdc++.h> 259 using namespace std; 260 #define ll long long int 261 const ll M=1e5+5; 262 ll dp[M][(1<<7)+1],skill[M][7]; 263 ll ind[M],a[M]; 264 bool cmp(ll p,ll q) 265 { 266 return a[p]>a[q]; 267 } 268 int main() 269 { 270 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 271 ll n,p,k; 272 cin>>n>>p>>k; 273 memset(dp,-1,sizeof(dp)); 274 for(ll i=1;i<=n;i++) 275 cin>>a[i]; 276 for(ll i=1;i<=n;i++) 277 for(ll j=0;j<p;j++) 278 cin>>skill[i][j]; 279 for(ll i=1;i<=n;i++) 280 ind[i]=i; 281 sort(ind+1,ind+n+1,cmp); 282 dp[0][0]=0; 283 for(ll i=1;i<=n;i++) 284 { 285 ll x=ind[i]; 286 for(ll mask=0;mask<(1<<p);mask++) 287 { 288 ll ct=0; 289 for(ll j=0;j<p;j++) 290 if((mask&(1<<j))) 291 ct++; 292 ll z=(i-1)-ct; 293 if(z<k) 294 { 295 if(dp[i-1][mask]!=-1) 296 dp[i][mask]=dp[i-1][mask]+a[x]; 297 } 298 else 299 { 300 if(dp[i-1][mask]!=-1) 301 dp[i][mask]=dp[i-1][mask]; 302 } 303 for(ll j=0;j<p;j++) 304 { 305 if((mask&(1<<j)) && dp[i-1][(mask^(1<<j))]!=-1) 306 { 307 ll z=dp[i-1][(mask^(1<<j))]+skill[x][j]; 308 if(z>dp[i][mask]) 309 dp[i][mask]=z; 310 } 311 } 312 } 313 } 314 cout<<dp[n][(1<<p)-1]<<"\n"; 315 return 0; 316 } 317 ``` 318 319 ### [1316F - Battalion Strength](/contest/1316/problem/F "CodeCraft-20 (Div. 2)") 320 321 **Author:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172") 322 **Development:** [gaurav172](/profile/gaurav172 "Candidate Master gaurav172"), [shaanknight](/profile/shaanknight "Master shaanknight") 323 324 **Tutorial** 325 326 Tutorial is loading... 327 328 **Solution** 329 330 ``` 331 #include <bits/stdc++.h> 332 using namespace std; 333 #define ll long long int 334 #define ff first 335 #define ss second 336 #define pb push_back 337 #define all(a) a.begin(),a.end() 338 #define sz(a) (ll)(a.size()) 339 const ll M=6e5+6; 340 const ll mod=1e9+7; 341 ll val[4*M],lt[4*M],rt[4*M]; 342 int no[4*M]; 343 ll pw[M],ipw[M]; 344 int P[M],idx[M],qr[M],n,q; 345 vector<pair<int,int> > v; 346 ll power(ll a,ll b) 347 { 348 ll val=1; 349 while(b) 350 { 351 if(b%2) 352 val=(val*a)%mod; 353 b/=2; 354 a=(a*a)%mod; 355 } 356 return val; 357 } 358 void build(int i,int s,int e) 359 { 360 if(s==e) 361 { 362 if(v[s].ss>n) 363 return; 364 val[i]=0; 365 lt[i]=v[s].ff; 366 rt[i]=(v[s].ff*ipw[1])%mod; 367 no[i]=1; 368 return; 369 } 370 int m=(s+e)/2; 371 int lc=2*i,rc=2*i+1; 372 build(lc,s,m); 373 build(rc,m+1,e); 374 ll tp=(ipw[no[lc]]*rt[rc])%mod; 375 tp=(tp*lt[lc])%mod; 376 val[i]=(val[lc]+val[rc]+tp)%mod; 377 lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod; 378 rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod; 379 no[i]=(no[lc]+no[rc]); 380 } 381 void update(int i,int s,int e,int x,int y) 382 { 383 if(s==e) 384 { 385 if(y==-1) 386 { 387 val[i]=0; 388 lt[i]=0; 389 rt[i]=0; 390 no[i]=0; 391 } 392 else 393 { 394 val[i]=0; 395 lt[i]=v[s].ff; 396 rt[i]=(v[s].ff*ipw[1])%mod; 397 no[i]=1; 398 } 399 return; 400 } 401 int m=(s+e)/2; 402 int lc=(i<<1),rc=(lc|1); 403 if(x<=m) 404 update(lc,s,m,x,y); 405 else 406 update(rc,m+1,e,x,y); 407 ll tp=(ipw[no[lc]]*rt[rc])%mod; 408 tp=(tp*lt[lc])%mod; 409 val[i]=(val[lc]+val[rc]+tp)%mod; 410 lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod; 411 rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod; 412 no[i]=(no[lc]+no[rc]); 413 } 414 int main() 415 { 416 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 417 pw[0]=1; 418 ipw[0]=1; 419 ll inv=power(2,mod-2); 420 for(int i=1;i<M;i++) 421 { 422 pw[i]=(pw[i-1]*2)%mod; 423 ipw[i]=(ipw[i-1]*inv)%mod; 424 } 425 cin>>n; 426 v.pb({-1LL,-1}); 427 for(int i=1;i<=n;i++) 428 { 429 cin>>P[i]; 430 v.pb({P[i],i}); 431 } 432 cin>>q; 433 for(int i=1;i<=q;i++) 434 { 435 cin>>idx[i]>>qr[i]; 436 v.pb({qr[i],n+i}); 437 } 438 sort(all(v)); 439 std::vector<int> pos(n+q+1,0); 440 for(int i=1;i<sz(v);i++) 441 pos[v[i].ss]=i; 442 build(1,1,n+q); 443 cout<<val[1]<<"\n"; 444 for(int i=1;i<=q;i++) 445 { 446 update(1,1,n+q,pos[idx[i]],-1); 447 pos[idx[i]]=pos[n+i]; 448 update(1,1,n+q,pos[idx[i]],1); 449 cout<<val[1]<<"\n"; 450 } 451 return 0; 452 } 453 ```