codeforces-scrape

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

1155.md (7329B)


      1 Source: https://codeforces.com/blog/entry/66687
      2 
      3 [1155A - Reverse a Substring](/contest/1155/problem/A "Educational Codeforces Round 63 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int n;
     23 	string s;
     24 	cin >> n >> s;
     25 	
     26 	for (int i = 1; i < int(s.size()); ++i) {
     27 		if (s[i] < s[i - 1]) {
     28 			cout << "YES" << endl;
     29 			cout << i << " " << i + 1 << endl;
     30 			return 0;
     31 		}
     32 	}
     33 	
     34 	cout << "NO" << endl;
     35 
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1155B - Game with Telephone Numbers](/contest/1155/problem/B "Educational Codeforces Round 63 (Rated for Div. 2)")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution (Roms)**
     47 
     48 ```
     49 #include<bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int n;
     54 string s;
     55 
     56 int main(){
     57     cin >> n >> s;
     58     int cnt1 = (n - 11) / 2;
     59     int cnt2 = cnt1;
     60     string res = "";
     61     for(int i = 0; i < n; ++i){
     62         if(s[i] == '8'){
     63             if(cnt1 > 0) --cnt1;
     64             else res += s[i];
     65         }
     66         else{
     67             if(cnt2 > 0) --cnt2;
     68             else res += s[i];
     69         }
     70     }
     71     
     72     if(res[0] == '8') cout << "YES\n";
     73     else cout << "NO\n";
     74 	return 0;
     75 }
     76 ```
     77 
     78 [1155C - Alarm Clocks Everywhere](/contest/1155/problem/C "Educational Codeforces Round 63 (Rated for Div. 2)")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution (Vovuh)**
     85 
     86 ```
     87 #include <bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 int main() {
     92 #ifdef _DEBUG
     93 	freopen("input.txt", "r", stdin);
     94 //	freopen("output.txt", "w", stdout);
     95 #endif
     96 	
     97 	int n, m;
     98 	cin >> n >> m;
     99 	vector<long long> x(n), p(m);
    100 	for (int i = 0; i < n; ++i) {
    101 		cin >> x[i];
    102 	}
    103 	for (int i = 0; i < m; ++i) {
    104 		cin >> p[i];
    105 	}
    106 	
    107 	long long g = x[1] - x[0];
    108 	for (int i = 2; i < n; ++i) {
    109 		g = __gcd(g, x[i] - x[i - 1]);
    110 	}
    111 	
    112 	for (int i = 0; i < m; ++i) {
    113 		if (g % p[i] == 0) {
    114 			cout << "YES" << endl;
    115 			cout << x[0] << " " << i + 1 << endl;
    116 			return 0;
    117 		}
    118 	}
    119 	
    120 	cout << "NO" << endl;
    121 	
    122 	return 0;
    123 }
    124 ```
    125 
    126 [1155D - Beautiful Array](/contest/1155/problem/D "Educational Codeforces Round 63 (Rated for Div. 2)")
    127 
    128 **Tutorial**
    129 
    130 Tutorial is loading...
    131 
    132 **Solution (PikMike)**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136 
    137 using namespace std;
    138 
    139 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    140 
    141 typedef long long li;
    142 
    143 const int N = 300 * 1000 + 13;
    144 const li INF64 = 1e18;
    145 
    146 int n, x;
    147 int a[N];
    148 
    149 li dp[N][3][3];
    150 
    151 int main() {
    152 	scanf("%d%d", &n, &x);
    153 	forn(i, n) scanf("%d", &a[i]);
    154 	
    155 	forn(i, n + 1) forn(j, 3) forn(k, 3)
    156 		dp[i][j][k] = -INF64;
    157 	
    158 	dp[0][0][0] = 0;
    159 	forn(i, n + 1) forn(j, 3) forn(k, 3){
    160 		if (k < 2)
    161 			dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]);
    162 		if (j < 2)
    163 			dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
    164 		if (i < n)
    165 			dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1));
    166 	}
    167 	
    168 	printf("%lld\n", dp[n][2][2]);
    169 }
    170 ```
    171 
    172 [1155E - Guess the Root](/contest/1155/problem/E "Educational Codeforces Round 63 (Rated for Div. 2)")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution (adedalic)**
    179 
    180 ```
    181 #include<bits/stdc++.h>
    182 using namespace std;
    183 
    184 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    185 #define sz(a) int((a).size())
    186 
    187 #define x first
    188 #define y second
    189 
    190 typedef long long li;
    191 typedef long double ld;
    192 typedef pair<int, int> pt;
    193 
    194 const int MOD = 1000 * 1000 + 3;
    195 
    196 int norm(int a) {
    197 	while(a >= MOD) a -= MOD;
    198 	while(a < 0) a += MOD;
    199 	return a;
    200 }
    201 int mul(int a, int b) {
    202 	return int(a * 1ll * b % MOD);
    203 }
    204 int binPow(int a, int k) {
    205 	int ans = 1;
    206 	while(k > 0) {
    207 		if(k & 1)
    208 			ans = mul(ans, a);
    209 		a = mul(a, a);
    210 		k >>= 1;
    211 	}
    212 	return ans;
    213 }
    214 int inv(int a) {
    215 	return binPow(a, MOD - 2);
    216 }
    217 
    218 int k = 10;
    219 vector<int> f;
    220 
    221 int main() {
    222 	f.resize(k + 1);
    223 	fore(i, 0, sz(f)) {
    224 		cout << "? " << i << endl;
    225 		cout.flush();
    226 		cin >> f[i];
    227 	}
    228 	
    229 	vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1));
    230 	fore(i, 0, sz(mat)) {
    231 		mat[i][0] = 1;
    232 		mat[i][sz(f)] = f[i];
    233 		
    234 		fore(j, 1, sz(mat[i]) - 1)
    235 			mat[i][j] = mul(mat[i][j - 1], i);
    236 	}
    237 	
    238 	/*
    239 	fore(i, 0, sz(mat)) {
    240 		fore(j, 0, sz(mat[i]))
    241 			cerr << mat[i][j] << " ";
    242 		cerr << endl;
    243 	}
    244 	*/
    245 	
    246 	fore(j, 0, sz(mat)) {
    247 		int nid = -1;
    248 		fore(i, j, sz(mat)) {
    249 			if(mat[i][j] != 0) {
    250 				nid = i;
    251 				break;
    252 			}
    253 		}
    254 		if(nid == -1)
    255 			continue;
    256 		
    257 		swap(mat[j], mat[nid]);
    258 		fore(i, 0, sz(mat)) {
    259 			if(i == j) continue;
    260 			int cf = mul(mat[i][j], inv(mat[j][j]));
    261 			
    262 			fore(cj, j, sz(mat[i]))
    263 				mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj]));
    264 		}
    265 	}
    266 	
    267 	vector<int> a(sz(f), 0);
    268 	fore(i, 0, sz(a)) {
    269 		if(mat[i][i] == 0)
    270 			continue;
    271 		a[i] = mul(mat[i][sz(a)], inv(mat[i][i]));
    272 	}
    273 	
    274 	fore(x0, 0, MOD) {
    275 		int val = 0;
    276 		for(int i = sz(a) - 1; i >= 0; i--)
    277 			val = norm(mul(val, x0) + a[i]);
    278 			
    279 		if(val == 0) {
    280 			cout << "! " << x0 << endl;
    281 			return 0;
    282 		}
    283 	}
    284 	
    285 	cout << "! -1" << endl;
    286 	return 0;
    287 }
    288 ```
    289 
    290 [1155F - Delivery Oligopoly](/contest/1155/problem/F "Educational Codeforces Round 63 (Rated for Div. 2)")
    291 
    292 **Tutorial**
    293 
    294 Tutorial is loading...
    295 
    296 **Solution (BledDest)**
    297 
    298 ```
    299 #include<bits/stdc++.h>
    300 using namespace std;
    301 
    302 const int N = 14;
    303 const int INF = int(1e9);
    304 
    305 int dp[1 << N];
    306 int par[1 << N];
    307 int last[1 << N];
    308 pair<int, int> last_pair[1 << N];
    309 int dp2[N][N][1 << N];
    310 int lastv[N][N][1 << N];
    311 vector<int> bits[1 << N];
    312 
    313 int n;
    314 int m;
    315 vector<int> g[N];
    316 
    317 int main()
    318 {
    319 	cin >> n >> m;
    320 	for(int i = 0; i < m; i++)
    321 	{
    322 		int x, y;
    323 		cin >> x >> y;
    324 		--x;
    325 		--y;
    326 		g[x].push_back(y);
    327 		g[y].push_back(x);
    328 	}
    329 	for(int i = 0; i < (1 << n); i++)
    330 		dp[i] = INF;
    331 	for(int i = 0; i < n; i++)
    332 		for(int j = 0; j < n; j++)
    333 			for(int z = 0; z < (1 << n); z++)
    334 				dp2[i][j][z] = INF;
    335 	for(int i = 0; i < n; i++)
    336 		for(auto x : g[i])
    337 		{
    338 			dp2[i][x][0] = 1;
    339 			lastv[i][x][0] = i;
    340 		}
    341 	for(int mask = 0; mask < (1 << n); mask++)
    342 		for(int i = 0; i < n; i++)
    343 			for(int j = 0; j < n; j++)
    344 			{
    345 				if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF))
    346 					continue;
    347 				for(auto z : g[j])
    348 				{
    349 					if(mask & (1 << z)) continue;
    350 					if(z == lastv[i][j][mask]) continue;
    351 					int nmask = mask ^ (1 << j);
    352 					if(dp2[i][z][nmask] == INF)
    353 					{
    354 						dp2[i][z][nmask] = 1;
    355 						lastv[i][z][nmask] = j;
    356 					}
    357 				}
    358 			}
    359 	for(int mask = 0; mask < (1 << n); mask++)
    360 		for(int j = 0; j < n; j++)
    361 			if(mask & (1 << j))
    362 				bits[mask].push_back(j);
    363 	dp[1] = 0;
    364 	for(int mask = 0; mask < (1 << n); mask++)
    365 		for(int addmask = mask; addmask; addmask = (addmask - 1) & mask)
    366 		{
    367 			int lastmask = mask ^ addmask;
    368 			int cnt = __builtin_popcount(addmask) + 1;
    369 			if(dp[lastmask] + cnt >= dp[mask])
    370 				continue;
    371 			bool f = false;
    372 			for(auto x : bits[lastmask])
    373 			{
    374 				for(auto y : bits[lastmask])
    375 				{
    376 					if(dp2[x][y][addmask] == 1)
    377 					{
    378 						dp[mask] = dp[lastmask] + cnt;
    379 						last_pair[mask] = make_pair(x, y);
    380 						last[mask] = addmask;
    381 					}
    382 					if(f) break;
    383 				}
    384 				if(f) break;
    385 			}
    386 		}
    387 	if(dp[(1 << n) - 1] == INF)
    388 		cout << -1 << endl;
    389 	else
    390 	{
    391 		cout << dp[(1 << n) - 1] << endl;
    392 		int cur = (1 << n) - 1;
    393 		while(cur != 1)
    394 		{
    395 			int lst = last[cur];
    396 			int x = last_pair[cur].first;
    397 			int y = last_pair[cur].second;
    398 			cur ^= lst;
    399 			while(lst)
    400 			{
    401 				int ny = lastv[x][y][lst];
    402 				cout << y + 1 << " " << ny + 1 << endl;
    403 				lst ^= (1 << ny);
    404 				y = ny;
    405 			}
    406 			cout << x + 1 << " " << y + 1 << endl;
    407 		}
    408 	}
    409 }
    410 ```