codeforces-scrape

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

1455.md (11299B)


      1 Source: https://codeforces.com/blog/entry/85186
      2 
      3 [1455A - Странные функции](/contest/1455/problem/A "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Ne0n25)**
     12 
     13 ```
     14 for i in range(int(input())):
     15 	print(len(input()))
     16 ```
     17 
     18 [1455B - Прыжки](/contest/1455/problem/B "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
     19 
     20 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic")
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution (adedalic)**
     27 
     28 ```
     29 #include<bits/stdc++.h>
     30 
     31 using namespace std;
     32 
     33 int main() {
     34 	int t; cin >> t;
     35 	while (t--) {
     36 		int x; cin >> x;
     37 		
     38 		int steps = 0;
     39 		while (steps * (steps + 1) < 2 * x)
     40 			steps++;
     41 		
     42 		if (steps * (steps + 1) / 2 == x + 1)
     43 			steps++;
     44 		cout << steps << endl;
     45 	}
     46 }
     47 ```
     48 
     49 [1455C - Пинг-понг](/contest/1455/problem/C "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
     50 
     51 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution (Ne0n25)**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 
     62 using namespace std;
     63 
     64 void solve() {
     65 	int x, y;
     66 	cin >> x >> y;
     67 	cout << x - 1 << " " << y << endl;	
     68 }
     69 
     70 int main() {
     71 	int t;
     72 	cin >> t;
     73 	while (t--) solve();
     74 }
     75 ```
     76 
     77 [1455D - Последовательность и обмены](/contest/1455/problem/D "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
     78 
     79 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution 1 (BledDest)**
     86 
     87 ```
     88 #include<bits/stdc++.h>
     89 
     90 using namespace std;
     91 
     92 int main()
     93 {
     94     int t;
     95     cin >> t;
     96     for(int i = 0; i < t; i++)
     97     {
     98         int n, x;
     99         cin >> n >> x;
    100         vector<int> a(n);
    101         for(int i = 0; i < n; i++)
    102             cin >> a[i];
    103         if(is_sorted(a.begin(), a.end()))
    104         {
    105             cout << 0 << endl;
    106             continue;
    107         }
    108         vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
    109         for(int i = 0; i < n; i++)
    110         {
    111             if(a[i] > x && (i == 0 || a[i - 1] <= x))
    112                 dp[i][x] = 1;
    113             if(i < n - 1 && a[i] > a[i + 1])
    114                 break;
    115         }
    116         int ans = int(1e9);
    117         for(int i = 0; i < n; i++)
    118             for(int j = 0; j <= 500; j++)
    119             {
    120                 if(dp[i][j] == int(1e9))
    121                     continue;
    122                 if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
    123                     ans = min(ans, dp[i][j]);
    124                 bool good = true;
    125                 for(int k = i + 1; k < n; k++)
    126                 {
    127                     int pr = k == i + 1 ? j : a[k - 1];
    128                     if(good && a[i] >= pr && a[i] < a[k])
    129                         dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
    130                     good &= a[k] >= pr;
    131                 }
    132             }
    133         if(ans == int(1e9))
    134             ans = -1;
    135         cout << ans << endl;
    136         
    137     }   
    138 }
    139 ```
    140 
    141 **Solution 2 (adedalic)**
    142 
    143 ```
    144 #include<bits/stdc++.h>
    145 
    146 using namespace std;
    147 
    148 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    149 #define sz(a) int((a).size())
    150 
    151 #define x first
    152 #define y second
    153 
    154 typedef long long li;
    155 typedef long double ld;
    156 typedef pair<int, int> pt;
    157 
    158 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    159 	return out << "(" << p.x << ", " << p.y << ")";
    160 }
    161 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    162 	out << "[";
    163 	fore(i, 0, sz(v)) {
    164 		if(i) out << ", ";
    165 		out << v[i];
    166 	}
    167 	return out << "]";
    168 }
    169 
    170 const int INF = int(1e9);
    171 const li INF64 = li(1e18);
    172 const ld EPS = 1e-9;
    173 
    174 int n, x;
    175 vector<int> a;
    176 
    177 inline bool read() {
    178 	if(!(cin >> n >> x))
    179 		return false;
    180 	a.resize(n);
    181 	fore (i, 0, n)
    182 		cin >> a[i];
    183 	return true;
    184 }
    185 
    186 inline void solve() {
    187 	vector<int> sf(n + 1, 0);
    188 	sf[n] = sf[n - 1] = 1;
    189 	for (int i = n - 2; i >= 0; i--) {
    190 		if (a[i] <= a[i + 1])
    191 			sf[i] = sf[i + 1];
    192 	}
    193 	
    194 	int ans = 0;
    195 	int uk = 0;
    196 	while (true) {
    197 		int np = uk;
    198 		while (np < n && a[np] <= x)
    199 			np++;
    200 		fore (i, uk, np) {
    201 			if (i == 0) continue;
    202 			if (a[i - 1] > a[i]) {
    203 				cout << -1 << endl;
    204 				return;
    205 			}
    206 		}
    207 		if (sf[np])
    208 			break;
    209 		
    210 		assert(a[np] > x);
    211 		swap(a[np], x);
    212 		ans++;
    213 		uk = np;
    214 	}
    215 	cout << ans << endl;
    216 }
    217 
    218 int main() {
    219 #ifdef _DEBUG
    220 	freopen("input.txt", "r", stdin);
    221 	int tt = clock();
    222 #endif
    223 	ios_base::sync_with_stdio(false);
    224 	cin.tie(0), cout.tie(0);
    225 	cout << fixed << setprecision(15);
    226 	
    227 	int t; cin >> t;
    228 	
    229 	while(t--) {
    230 		read();
    231 		solve();
    232 		
    233 #ifdef _DEBUG
    234 		cerr << "TIME = " << clock() - tt << endl;
    235 		tt = clock();
    236 #endif
    237 	}
    238 	return 0;
    239 }
    240 ```
    241 
    242 [1455E - Четыре точки](/contest/1455/problem/E "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
    243 
    244 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic")
    245 
    246 **Tutorial**
    247 
    248 Tutorial is loading...
    249 
    250 **Solution 1 (adedalic)**
    251 
    252 ```
    253 #include<bits/stdc++.h>
    254 
    255 using namespace std;
    256 
    257 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    258 #define sz(a) int((a).size())
    259 
    260 #define x first
    261 #define y second
    262 
    263 typedef long long li;
    264 typedef pair<li, li> pt;
    265 
    266 const li INF64 = li(1e18);
    267 
    268 pt p[4];
    269 
    270 inline bool read() {
    271 	fore (i, 0, 4) {
    272 		if(!(cin >> p[i].x >> p[i].y))
    273 			return false;
    274 	}
    275 	return true;
    276 }
    277 
    278 inline void solve() {
    279 	li ans = INF64;
    280 	fore (st, 0, 2) {
    281 		fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) {
    282 			li x1 = p[idx1].x;
    283 			li x2 = p[idx2].x;
    284 			li y1 = p[idy1].y;
    285 			
    286 			if (x1 > x2)
    287 				continue;
    288 			
    289 			for (int k = -1; k <= 1; k += 2) {
    290 				li y2 = y1 + k * abs(x1 - x2);
    291 				
    292 				vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} };
    293 				sort(fp.begin(), fp.end());
    294 				
    295 				do {
    296 					li cur = 0;
    297 					fore (i, 0, 4)
    298 						cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y);
    299 						
    300 					ans = min(ans, cur);
    301 				} while(next_permutation(fp.begin(), fp.end()));
    302 			}
    303 		}
    304 		
    305 		fore (i, 0, 4)
    306 			swap(p[i].x, p[i].y);
    307 	}
    308 	cout << ans << endl;
    309 }
    310 
    311 int main() {
    312 #ifdef _DEBUG
    313 	freopen("input.txt", "r", stdin);
    314 	int tt = clock();
    315 #endif
    316 	ios_base::sync_with_stdio(false);
    317 	cin.tie(0), cout.tie(0);
    318 	cout << fixed << setprecision(15);
    319 	
    320 	int t;
    321 	cin >> t;
    322 	
    323 	while(t--) {
    324 		assert(read());
    325 		solve();
    326 		
    327 #ifdef _DEBUG
    328 		cerr << "TIME = " << clock() - tt << endl;
    329 		tt = clock();
    330 #endif
    331 	}
    332 	return 0;
    333 }
    334 ```
    335 
    336 **Solution 2 (adedalic)**
    337 
    338 ```
    339 #include<bits/stdc++.h>
    340 
    341 using namespace std;
    342 
    343 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    344 #define sz(a) int((a).size())
    345 
    346 #define x first
    347 #define y second
    348 
    349 typedef long long li;
    350 typedef pair<li, li> pt;
    351 
    352 const li INF64 = li(1e18);
    353 
    354 pt p[4];
    355 
    356 inline bool read() {
    357 	fore (i, 0, 4) {
    358 		if(!(cin >> p[i].x >> p[i].y))
    359 			return false;
    360 	}
    361 	return true;
    362 }
    363 
    364 li len(const pt &a) {
    365 	assert(a.y >= a.x);
    366 	return a.y - a.x;
    367 }
    368 pt getSeg(li a, li b) {
    369 	return { min(a, b), max(a, b) };
    370 }
    371 pt getOpt(const pt &a, const pt &b) {
    372 	return {
    373 		max({ a.x - b.y, b.x - a.y, 0LL }),
    374 		max({ b.y - a.x, a.y - b.x, 0LL })
    375 	};
    376 }
    377 
    378 inline void solve() {
    379 	li ans = INF64;
    380 	
    381 	vector<int> id = { 0, 1, 2, 3 };
    382 	do {
    383 		li cur = 0;
    384 		auto x1 = getSeg(p[id[0]].x, p[id[3]].x);
    385 		auto x2 = getSeg(p[id[1]].x, p[id[2]].x);
    386 		
    387 		cur += len(x1) + len(x2);
    388 		pt xSeg = getOpt(x1, x2);
    389 		
    390 		auto y1 = getSeg(p[id[0]].y, p[id[1]].y);
    391 		auto y2 = getSeg(p[id[2]].y, p[id[3]].y);
    392 		
    393 		cur += len(y1) + len(y2);
    394 		pt ySeg = getOpt(y1, y2);
    395 		
    396 		li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x);
    397 		cur += 2 * max(0LL, -is);
    398 		
    399 		ans = min(ans, cur);
    400 	}
    401 	while (next_permutation(id.begin(), id.end()));
    402 	
    403 	cout << ans << endl;
    404 }
    405 
    406 int main() {
    407 #ifdef _DEBUG
    408 	freopen("input.txt", "r", stdin);
    409 	int tt = clock();
    410 #endif
    411 	ios_base::sync_with_stdio(false);
    412 	cin.tie(0), cout.tie(0);
    413 	cout << fixed << setprecision(15);
    414 	
    415 	int t;
    416 	cin >> t;
    417 	
    418 	while(t--) {
    419 		assert(read());
    420 		solve();
    421 		
    422 #ifdef _DEBUG
    423 		cerr << "TIME = " << clock() - tt << endl;
    424 		tt = clock();
    425 #endif
    426 	}
    427 	return 0;
    428 }
    429 ```
    430 
    431 [1455F - Строка и операции](/contest/1455/problem/F "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
    432 
    433 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon")
    434 
    435 **Tutorial**
    436 
    437 Tutorial is loading...
    438 
    439 **Solution (Ne0n25)**
    440 
    441 ```
    442 #include <bits/stdc++.h>
    443 
    444 using namespace std;
    445 
    446 const int N = 505;
    447 
    448 int n, k;
    449 string s;
    450 string dp[N];
    451 
    452 void solve() {
    453 	cin >> n >> k >> s;
    454 	for (int i = 1; i <= n; i++)
    455 		dp[i] = char('z' + 1);
    456 	for (int i = 0; i < n; i++) {
    457 		int c = s[i] - 'a';
    458 		int nc = min({c, (c + 1) % k, (c + k - 1) % k});
    459 		dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc));
    460 		if (i > 0) {
    461 			dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]);
    462 			dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back());
    463 		}
    464 		if (i > 1) {
    465 			dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]);
    466 		}
    467 	}
    468 	cout << dp[n] << endl;
    469 }
    470 
    471 int main() {
    472 	int t;
    473 	cin >> t;
    474 	while (t--) solve();
    475 }
    476 ```
    477 
    478 [1455G - Запрещенное значение](/contest/1455/problem/G "Educational Codeforces Round 99 (рейтинговый для Див. 2)")
    479 
    480 Idea: [MrPaul_TUser](/profile/MrPaul_TUser "Кандидат в мастера MrPaul_TUser") и [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    481 
    482 **Tutorial**
    483 
    484 Tutorial is loading...
    485 
    486 **Solution (pikmike)**
    487 
    488 ```
    489 #include <bits/stdc++.h>
    490 
    491 #define forn(i, n) for (int i = 0; i < int(n); i++)
    492 #define x first
    493 #define y second
    494 
    495 using namespace std;
    496 
    497 const long long INF = 1e18;
    498 
    499 struct op{
    500 	string tp;
    501 	int y, v, to;
    502 };
    503 
    504 struct addmap{
    505 	long long add;
    506 	map<int, long long> val;
    507 	multiset<long long> mn;
    508 };
    509 
    510 void reset(addmap &a, int x, long long val){
    511 	if (a.val.count(x))
    512 		a.mn.erase(a.mn.find(a.val[x]));
    513 	a.val[x] = val - a.add;
    514 	a.mn.insert(val - a.add);
    515 }
    516 
    517 int main() {
    518 	int n, s;
    519 	scanf("%d%d", &n, &s);
    520 	static char buf[10];
    521 	op a;
    522 	vector<addmap> st;
    523 	st.push_back({});
    524 	st.back().val[0] = 0;
    525 	st.back().add = 0;
    526 	st.back().mn.insert(0);
    527 	forn(i, n){
    528 		scanf("%s", buf);
    529 		a.tp = buf;
    530 		if (a.tp == "set"){
    531 			scanf("%d%d", &a.y, &a.v);
    532 			assert(!st.back().mn.empty());
    533 			long long mn = st.back().add + *st.back().mn.begin();
    534 			st.back().add += a.v;
    535 			if (a.y != s) reset(st.back(), a.y, mn);
    536 		}
    537 		else if (a.tp == "if"){
    538 			scanf("%d", &a.y);
    539 			long long val = INF;
    540 			if (st.back().val.count(a.y)){
    541 				val = st.back().val[a.y] + st.back().add;
    542 				st.back().mn.erase(st.back().mn.find(st.back().val[a.y]));
    543 				st.back().val.erase(a.y);
    544 			}
    545 			st.push_back({});
    546 			reset(st.back(), a.y, val);
    547 			st.back().add = 0;
    548 		}
    549 		else{
    550 			if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size())
    551 				swap(st[int(st.size()) - 1], st[int(st.size()) - 2]);
    552 			addmap& v = st[int(st.size()) - 2];
    553 			for (auto it : st.back().val){
    554 				if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){
    555 					if (v.val.count(it.x))
    556 						v.mn.erase(v.mn.find(v.val[it.x]));
    557 					v.val[it.x] = it.y + st.back().add - v.add;
    558 					v.mn.insert(it.y + st.back().add - v.add);
    559 				}
    560 			}
    561 			st.pop_back();
    562 		}
    563 	}
    564 	printf("%lld\n", *st.back().mn.begin() + st.back().add);
    565 	return 0;
    566 }
    567 ```