codeforces-scrape

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

1102.md (6995B)


      1 Source: https://codeforces.com/blog/entry/64439
      2 
      3 [1102A - Integer Sequence Dividing](/contest/1102/problem/A "Codeforces Round 531 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution 1**
     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 	cin >> n;
     24 	n %= 4;
     25 	if (n == 0 || n == 3) {
     26 		cout << 0 << endl;
     27 	} else {
     28 		cout << 1 << endl;
     29 	}
     30 	
     31 	return 0;
     32 }
     33 ```
     34 
     35 **Solution 2**
     36 
     37 ```
     38 #include <bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 int main() {
     43 #ifdef _DEBUG
     44 	freopen("input.txt", "r", stdin);
     45 //	freopen("output.txt", "w", stdout);
     46 #endif
     47 	
     48 	int n;
     49 	cin >> n;
     50 	long long sum = n * 1ll * (n + 1) / 2;
     51 	cout << (sum & 1) << endl;
     52 	
     53 	return 0;
     54 }
     55 ```
     56 
     57 [1102B - Array K-Coloring](/contest/1102/problem/B "Codeforces Round 531 (Div. 3)")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 
     68 using namespace std;
     69 
     70 int main() {
     71 #ifdef _DEBUG
     72 	freopen("input.txt", "r", stdin);
     73 //	freopen("output.txt", "w", stdout);
     74 #endif
     75 	
     76 	int n, k;
     77 	cin >> n >> k;
     78 	vector<pair<int, int>> a(n);
     79 	for (int i = 0; i < n; ++i) {
     80 		cin >> a[i].first;
     81 		a[i].second = i;	
     82 	}
     83 	
     84 	sort(a.begin(), a.end());
     85 	
     86 	vector<vector<int>> buckets(k);
     87 	vector<int> res(n);
     88 	for (int i = 0; i < n; ++i) {
     89 		buckets[i % k].push_back(a[i].first);
     90 		res[a[i].second] = i % k;
     91 	}
     92 	
     93 	for (int i = 0; i < k; ++i) {
     94 		for (int j = 0; j < int(buckets[i].size()) - 1; ++j) {
     95 			if (buckets[i][j] == buckets[i][j + 1]) {
     96 				cout << "NO" << endl;
     97 				return 0;
     98 			}
     99 		}
    100 	}
    101 	
    102 	cout << "YES" << endl;
    103 	for (int i = 0; i < n; ++i) {
    104 		cout << res[i] + 1 << " ";
    105 	}
    106 	cout << endl;
    107 	
    108 	return 0;
    109 }
    110 ```
    111 
    112 [1102C - Doors Breaking and Repairing](/contest/1102/problem/C "Codeforces Round 531 (Div. 3)")
    113 
    114 **Tutorial**
    115 
    116 Tutorial is loading...
    117 
    118 **Solution**
    119 
    120 ```
    121 #include <bits/stdc++.h>
    122 
    123 using namespace std;
    124 
    125 int main() {
    126 #ifdef _DEBUG
    127 	freopen("input.txt", "r", stdin);
    128 //	freopen("output.txt", "w", stdout);
    129 #endif
    130 	
    131 	int n, x, y;
    132 	cin >> n >> x >> y;
    133 	int cnt = 0;
    134 	for (int i = 0; i < n; ++i) {
    135 		int cur;
    136 		cin >> cur;
    137 		if (cur <= x) {
    138 			++cnt;
    139 		}
    140 	}
    141 	
    142 	if (x > y) {
    143 		cout << n << endl;
    144 	} else {
    145 		cout << (cnt + 1) / 2 << endl;
    146 	}
    147 	
    148 	return 0;
    149 }
    150 ```
    151 
    152 [1102D - Balanced Ternary String](/contest/1102/problem/D "Codeforces Round 531 (Div. 3)")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (Vovuh)**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 
    163 using namespace std;
    164 
    165 int n;
    166 
    167 int needRep(const vector<int> &cnt, const vector<int> &need) {
    168 	int res = 0;
    169 	for (int i = 0; i < 3; ++i) {
    170 		res += abs(cnt[i] - need[i]);
    171 	}
    172 	assert(res % 2 == 0);
    173 	return res / 2;
    174 }
    175 
    176 int main() {
    177 #ifdef _DEBUG
    178 	freopen("input.txt", "r", stdin);
    179 //	freopen("output.txt", "w", stdout);
    180 #endif
    181 	
    182 	string s;
    183 	cin >> n >> s;
    184 	
    185 	vector<int> cnt(3), cur(3, n / 3);
    186 	for (auto c : s) {
    187 		++cnt[c - '0'];
    188 	}
    189 	
    190 	int need = needRep(cnt, cur);
    191 		
    192 	int curRep = 0;
    193 	for (int i = 0; i < n; ++i) {
    194 		--cnt[s[i] - '0'];
    195 		for (int j = 0; j < 3; ++j) {
    196 			if (cur[j] == 0) continue;
    197 			int rep = j != s[i] - '0';
    198 			--cur[j];
    199 			if (curRep + rep + needRep(cnt, cur) == need) {
    200 				s[i] = j + '0';
    201 				curRep += rep;
    202 				break;
    203 			}
    204 			++cur[j];
    205 		}
    206 	}
    207 	
    208 	cout << s << endl;
    209 	
    210 	return 0;
    211 }
    212 ```
    213 
    214 **Solution (PikMike)**
    215 
    216 ```
    217 n = int(input())
    218 s = [ord(x) - ord('0') for x in input()]
    219 cnt = [s.count(x) for x in [0, 1, 2]]
    220 def forw(x):
    221 	for i in range(n):
    222 		if (cnt[x] < n // 3 and s[i] > x and cnt[s[i]] > n // 3):
    223 			cnt[x] += 1
    224 			cnt[s[i]] -= 1
    225 			s[i] = x
    226 def back(x):
    227 	for i in range(n - 1, -1, -1):
    228 		if (cnt[x] < n // 3 and s[i] < x and cnt[s[i]] > n // 3):
    229 			cnt[x] += 1
    230 			cnt[s[i]] -= 1
    231 			s[i] = x
    232 forw(0)
    233 forw(1)
    234 back(2)
    235 back(1)
    236 print(''.join([str(x) for x in s]))
    237 ```
    238 
    239 [1102E - Monotonic Renumeration](/contest/1102/problem/E "Codeforces Round 531 (Div. 3)")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution**
    246 
    247 ```
    248 #include <bits/stdc++.h>
    249 
    250 using namespace std;
    251 
    252 const int MOD = 998244353;
    253 
    254 int main()
    255 {
    256  	int n;
    257  	scanf("%d", &n);
    258  	vector<int> a(n);
    259  	for(int i = 0; i < n; i++)
    260  		scanf("%d", &a[i]);
    261  	map<int, int> lst;
    262  	vector<int> last_pos(n);
    263  	for(int i = n - 1; i >= 0; i--)
    264  	{
    265  		if(!lst.count(a[i]))
    266  			lst[a[i]] = i;
    267  		last_pos[i] = lst[a[i]];
    268  	}
    269  	int ans = 1;
    270  	int cur_max = -1;
    271  	for(int i = 0; i < n - 1; i++)
    272  	{
    273  		cur_max = max(cur_max, last_pos[i]);
    274  		if(cur_max == i)
    275  			ans = (2 * ans) % MOD;
    276  	}	
    277  	printf("%d\n", ans);
    278  	return 0;
    279 }
    280 ```
    281 
    282 [1102F - Elongated Matrix](/contest/1102/problem/F "Codeforces Round 531 (Div. 3)")
    283 
    284 **Tutorial**
    285 
    286 Tutorial is loading...
    287 
    288 **Solution 1**
    289 
    290 ```
    291 #include <bits/stdc++.h>
    292 
    293 #define forn(i, n) for (int i = 0; i < int(n); i++)
    294 
    295 using namespace std;
    296 
    297 typedef long long li;
    298 
    299 const int N = 18;
    300 const int M = 100 * 1000 + 13;
    301 const int INF = 1e9;
    302 
    303 int dp[1 << N][N];
    304 
    305 int n, m;
    306 int a[N][M];
    307 int mn1[N][N], mn2[N][N];
    308 
    309 int calc(int mask, int v){
    310 	if (dp[mask][v] != -1)
    311 		return dp[mask][v];
    312 	dp[mask][v] = 0;
    313 	forn(u, n) if (v != u && ((mask >> u) & 1))
    314 		dp[mask][v] = max(dp[mask][v], min(mn1[u][v], calc(mask ^ (1 << v), u)));
    315 	return dp[mask][v];
    316 }
    317 
    318 int main() {
    319 	scanf("%d%d", &n, &m);
    320 	forn(i, n) forn(j, m)
    321 		scanf("%d", &a[i][j]);
    322 	
    323 	forn(i, n) forn(j, n){
    324 		int val = INF;
    325 		forn(k, m)
    326 			val = min(val, abs(a[i][k] - a[j][k]));
    327 		mn1[i][j] = val;
    328 		val = INF;
    329 		forn(k, m - 1)
    330 			val = min(val, abs(a[i][k] - a[j][k + 1]));
    331 		mn2[i][j] = val;
    332 	}
    333 	
    334 	int ans = 0;
    335 	forn(i, n){
    336 		memset(dp, -1, sizeof(dp));
    337 		forn(j, n)
    338 			dp[1 << j][j] = (j == i ? INF : 0);
    339 		forn(j, n)
    340 			ans = max(ans, min(mn2[j][i], calc((1 << n) - 1, j)));
    341 	}
    342 	
    343 	printf("%d\n", ans);
    344 }
    345 ```
    346 
    347 **Solution 2**
    348 
    349 ```
    350 #include <bits/stdc++.h>
    351 
    352 #define forn(i, n) for (int i = 0; i < int(n); i++)
    353 
    354 using namespace std;
    355 
    356 const int N = 18;
    357 const int M = 100 * 1000 + 13;
    358 const int INF = 1e9;
    359 
    360 int used[1 << N];
    361 char dp[1 << N];
    362 int g[1 << N];
    363 
    364 int n, m;
    365 int a[N][M];
    366 int mn1[N][N], mn2[N][N];
    367 
    368 bool calc(int mask){
    369 	if (dp[mask] != -1)
    370 		return dp[mask];
    371 	used[mask] = 0;
    372 	dp[mask] = 0;
    373 	forn(i, n){
    374 		if (!((mask >> i) & 1))
    375 			continue;
    376 		if (!calc(mask ^ (1 << i)))
    377 			continue;
    378 		if (!(used[mask ^ (1 << i)] & g[i]))
    379 			continue;
    380 		used[mask] |= (1 << i);
    381 		dp[mask] = 1;
    382 	}
    383 	return dp[mask];
    384 }
    385 
    386 bool check(int k){
    387 	forn(i, n){
    388 		g[i] = 0;
    389 		forn(j, n)
    390 			g[i] |= (1 << j) * (mn1[j][i] >= k);
    391 	}
    392 	forn(i, n){
    393 		memset(dp, -1, sizeof(dp));
    394 		forn(j, n){
    395 			dp[1 << j] = (j == i);
    396 			used[1 << j] = (1 << j);
    397 		}
    398 		calc((1 << n) - 1);
    399 		forn(j, n) if (mn2[j][i] >= k && ((used[(1 << n) - 1] >> j) & 1))
    400 			return true;
    401 	}
    402 	return false;
    403 }
    404 
    405 int main() {
    406 	scanf("%d%d", &n, &m);
    407 	forn(i, n) forn(j, m)
    408 		scanf("%d", &a[i][j]);
    409 	
    410 	forn(i, n) forn(j, n){
    411 		int val = INF;
    412 		forn(k, m)
    413 			val = min(val, abs(a[i][k] - a[j][k]));
    414 		mn1[i][j] = val;
    415 		val = INF;
    416 		forn(k, m - 1)
    417 			val = min(val, abs(a[i][k] - a[j][k + 1]));
    418 		mn2[i][j] = val;
    419 	}
    420 	
    421 	int l = 0, r = INF;
    422 	while (l < r - 1){
    423 		int m = (l + r) / 2;
    424 		if (check(m))
    425 			l = m;
    426 		else
    427 			r = m;
    428 	}
    429 	
    430 	printf("%d\n", check(r) ? r : l);
    431 }
    432 ```