codeforces-scrape

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

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