codeforces-scrape

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

1846.md (10712B)


      1 Source: https://codeforces.com/blog/entry/118044
      2 
      3 [1846A - Rudolph and Cut the Rope](/contest/1846/problem/A "Codeforces Round 883 (Div. 3)")
      4 
      5 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738")
      6 
      7 **Hint 1**
      8 
      9 What if the nail with the rope is the only one?
     10 
     11 **Hint 2**
     12 
     13 How long should be rope to reach the ground?
     14 
     15 **Tutorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Solution**
     20 
     21 ```
     22 #include <iostream>
     23 
     24 using namespace std;
     25 
     26 int main() {
     27 	int test_cases;
     28 	cin >> test_cases;
     29 
     30 	for (int test_case = 0; test_case < test_cases; test_case++) {
     31 		int n;
     32 		cin >> n;
     33 		int ans = 0;
     34 		for (int i = 0; i < n; i++) {
     35 			int a, b;
     36 			cin >> a >> b;
     37 			if (a > b)
     38 				ans++;
     39 		}
     40 		cout << ans << endl;
     41 	}
     42 
     43 	return 0;
     44 }
     45 ```
     46 
     47 **Rate the problem**
     48 
     49 * Didn't solve
     50 * Good task
     51 * Average task
     52 * Bad task
     53 
     54 [1846B - Rudolph and Tic-Tac-Toe](/contest/1846/problem/B "Codeforces Round 883 (Div. 3)")
     55 
     56 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738")
     57 
     58 **Hint 1**
     59 
     60 What is the win condition to be checked?
     61 
     62 **Tutorial**
     63 
     64 Tutorial is loading...
     65 
     66 **Solution**
     67 
     68 ```
     69 #include <iostream>
     70 #include <vector>
     71 #include <string>
     72 
     73 using namespace std;
     74 
     75 int main() {
     76 	int test_cases;
     77 	cin >> test_cases;
     78 	for (int test_case = 0; test_case < test_cases; test_case++) {
     79 		vector<string> v(3);
     80 		for (int i = 0; i < 3; i++)
     81 			cin >> v[i];
     82 		string ans = "DRAW";
     83 		for(int i = 0; i < 3; i++) {
     84 			if (v[i][0] == v[i][1] && v[i][1] == v[i][2] && v[i][0] != '.')
     85 				ans=v[i][0];
     86 		}
     87 		for (int i = 0; i < 3; i++) {
     88 			if (v[0][i] == v[1][i] && v[1][i] == v[2][i] && v[0][i] != '.')
     89 				ans=v[0][i];
     90 		}
     91 		if (v[0][0] == v[1][1] && v[1][1] == v[2][2] && v[0][0] != '.')
     92 			ans=v[0][0];
     93 		if (v[0][2] == v[1][1] && v[1][1] == v[2][0] && v[0][2] != '.')
     94 			ans=v[0][2];
     95 		cout << ans << endl;
     96 	}
     97 	return 0;
     98 }
     99 ```
    100 
    101 **Rate the problem**
    102 
    103 * Didn't solve
    104 * Good task
    105 * Average task
    106 * Bad task
    107 
    108 [1846C - Rudolf and the Another Competition](/contest/1846/problem/C "Codeforces Round 883 (Div. 3)")
    109 
    110 Author: [vladmart](/profile/vladmart "Master vladmart")
    111 
    112 **Hint 1**
    113 
    114 What is the optimal order of task solving?
    115 
    116 **Hint 2**
    117 
    118 t1 ≤ t2 ≤ t3 ≤ ... ≤ tm
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution**
    125 
    126 ```
    127 #include <bits/stdc++.h>
    128 
    129 #define int long long
    130 
    131 using namespace std;
    132 
    133 signed main() {
    134     ios::sync_with_stdio(false);
    135     cin.tie(nullptr);
    136     cout.tie(nullptr);
    137     int ttt;
    138     cin >> ttt;
    139     while(ttt--){
    140         int n, m, h;
    141         cin >> n >> m >> h;
    142         pair<int, long long> rud;
    143         int ans = 1;
    144         for(int i = 0; i < n; i++){
    145             vector<int> cur(m);
    146             for(int j = 0; j < m; j++){
    147                 cin >> cur[j];
    148             }
    149             std::sort(cur.begin(), cur.end());
    150             int task_cnt = 0;
    151             long long penalty = 0, sum = 0;
    152             for(int j = 0; j < m; j++){
    153                 if (sum + cur[j] > h) break;
    154                 sum += cur[j];
    155                 penalty += sum;
    156                 task_cnt++;
    157             }
    158             if (i){
    159                 if (make_pair(-task_cnt, penalty) < rud) ans++;
    160             } else rud = {-task_cnt, penalty};
    161         }
    162         cout << ans << '\n';
    163     }
    164     return 0;
    165 }
    166 ```
    167 
    168 **Rate the problem**
    169 
    170 * Didn't solve
    171 * Good task
    172 * Average task
    173 * Bad task
    174 
    175 [1846D - Rudolph and Christmas Tree](/contest/1846/problem/D "Codeforces Round 883 (Div. 3)")
    176 
    177 Author: [vladmart](/profile/vladmart "Master vladmart")
    178 
    179 **Hint 1**
    180 
    181 Consider all the triangles in order from bottom to top.
    182 
    183 **Hint 2**
    184 
    185 What if the current triangle intersects with the next one?
    186 
    187 **Hint 3**
    188 
    189 Trapezoid
    190 
    191 **Tutorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199 
    200 using namespace std;
    201 
    202 int main() {
    203     ios::sync_with_stdio(false);
    204     cin.tie(nullptr);
    205     cout.tie(nullptr);
    206     cout.precision(10); cout.setf(ios::fixed);
    207     int ttt;
    208     cin >> ttt;
    209     while (ttt--) {
    210         int n, d, h;
    211         cin >> n >> d >> h;
    212         vector<int> y(n);
    213         for(int i = 0; i < n; i++){
    214             cin >> y[i];
    215         }
    216         long double ans = (long double)d * h / 2.0;
    217         for (int i = 0; i + 1 < n; ++i) {
    218             if (y[i + 1] >= y[i] + h) ans += (long double)d * h / 2.0;
    219             else{
    220                 long double d2 = (long double)d * (y[i] + h - y[i + 1]) / h;
    221                 long double nh = y[i + 1] - y[i];
    222                 ans += (d + d2) / 2.0 * nh;
    223             }
    224         }
    225         cout << ans << '\n';
    226     }
    227     return 0;
    228 }
    229 ```
    230 
    231 **Rate the problem**
    232 
    233 * Didn't solve
    234 * Good task
    235 * Average task
    236 * Bad task
    237 
    238 [1846E1 - Rudolf and Snowflakes (simple version)](/contest/1846/problem/E1 "Codeforces Round 883 (Div. 3)")
    239 
    240 Author: [natalina](/profile/natalina "Expert natalina")
    241 
    242 **Hint 1**
    243 
    244 1 + k + k2 + k3 + ... + kp
    245 
    246 **Hint 2**
    247 
    248 What maximum value of k can be reached for the current constrains on n?
    249 
    250 **Hint 3**
    251 
    252 Can we precalculate for each n if there is appropriate k?
    253 
    254 **Tutorial**
    255 
    256 Tutorial is loading...
    257 
    258 **Solution**
    259 
    260 ```
    261 #include<bits/stdc++.h>
    262 
    263 using namespace std;
    264 
    265 using LL = long long;
    266 
    267 set<long long> nums;
    268 
    269 int main() {
    270 
    271     for (long long k = 2; k <= 1000; ++k) {
    272         long long val = 1 + k;
    273         long long p = k*k;
    274         for (int cnt = 2; cnt <= 20; ++cnt) {
    275             val += p;
    276             if (val > 1e6) break;
    277             nums.insert(val);            
    278             p *= k;
    279         }
    280     }
    281 
    282     int _ = 0, __ = 1;
    283     cin >> __;
    284 
    285     for (int _ = 0; _ < __; ++_) {
    286         long long n;
    287         cin >> n;
    288         
    289 
    290         if (nums.count(n)) cout << "YES" << endl;
    291         else cout << "NO" << endl;
    292 
    293     }
    294 
    295     return 0;
    296 }
    297 ```
    298 
    299 **Rate the problem**
    300 
    301 * Didn't solve
    302 * Good task
    303 * Average task
    304 * Bad task
    305 
    306 [1846E2 - Rudolf and Snowflakes (hard version)](/contest/1846/problem/E2 "Codeforces Round 883 (Div. 3)")
    307 
    308 Author: [natalina](/profile/natalina "Expert natalina")
    309 
    310 **Hint 1**
    311 
    312 1 + k + k2 + k3 + ... + kp
    313 
    314 **Hint 2**
    315 
    316 What maximum value of k can be reached for the current constrains on n?
    317 
    318 **Hint 3**
    319 
    320 Can we precalculate for some n and snowflakes with 4 or more levels if there is appropriate k?
    321 
    322 **Hint 4**
    323 
    324 How can we check snowflakes with 3 levels separately?
    325 
    326 **Tutorial**
    327 
    328 Tutorial is loading...
    329 
    330 **Solution**
    331 
    332 ```
    333 #include<bits/stdc++.h>
    334 
    335 using namespace std;
    336 
    337 using LL = long long;
    338 
    339 set<long long> nums;
    340 
    341 int main() {
    342 
    343     for (long long k = 2; k <= 1000000; ++k) {
    344         long long val = 1 + k;
    345         long long p = k*k;
    346         for (int cnt = 3; cnt <= 63; ++cnt) {
    347             val += p;
    348             if (val > 1e18) break;
    349             nums.insert(val);
    350             if (p > (long long)(1e18) / k) break;
    351             p *= k;
    352         }
    353     }
    354 
    355     int _ = 0, __ = 1;
    356     cin >> __;
    357 
    358     for (int _ = 0; _ < __; ++_) {
    359         long long n;
    360         cin >> n;
    361         if (n < 3)
    362         {
    363             cout << "NO" << endl;
    364             continue;
    365         }
    366         long long d = 4*n - 3;
    367         long long sq = sqrt(d);
    368         long long sqd = -1;
    369         for (long long i = max(0ll, sq - 5); i <= sq + 5; ++i) {
    370             if (i*i == d)
    371             {
    372                 sqd = i;
    373                 break;
    374             }
    375         }
    376         if (sqd != -1 && (sqd - 1) % 2 == 0 && (sqd - 1) / 2 > 1)
    377         {
    378             cout << "YES" << endl;
    379             continue;
    380         }
    381 
    382         if (nums.count(n)) cout << "YES" << endl;
    383         else cout << "NO" << endl;
    384 
    385     }
    386 
    387     return 0;
    388 }
    389 ```
    390 
    391 **Rate the problem**
    392 
    393 * Didn't solve
    394 * Good task
    395 * Average task
    396 * Bad task
    397 
    398 [1846F - Rudolph and Mimic](/contest/1846/problem/F "Codeforces Round 883 (Div. 3)")
    399 
    400 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738")
    401 
    402 **Hint 1**
    403 
    404 How number of objects of each type will change after the mimic transformation?
    405 
    406 **Hint 2**
    407 
    408 What if all the current objects have the same value?
    409 
    410 **Tutorial**
    411 
    412 Tutorial is loading...
    413 
    414 **Solution**
    415 
    416 ```
    417 #include <iostream>
    418 #include <vector>
    419 #include <map>
    420 
    421 using namespace std;
    422 
    423 int main() {
    424 	int test_cases;
    425 	cin >> test_cases;
    426 	for (int test_case = 0; test_case < test_cases; test_case++) {
    427 		int n;
    428 		cin >> n;
    429 		vector<int> v(n);
    430 		map<int, int> m;
    431 		for (int i = 0; i < n; i++) {
    432 			cin >> v[i];
    433 			m[v[i]]++;
    434 		}
    435 		vector<int> elements_to_erase;
    436 		int ans;
    437 		for (int i = 0; i < 5; i++) {
    438 			if (v.size() - elements_to_erase.size() == 1) {
    439 				cout << "! " << ans << endl;
    440 				break;
    441 			}
    442 			cout << "- " << elements_to_erase.size() << " ";
    443 			for (int j = 0; j < elements_to_erase.size(); j++) {
    444 				cout << elements_to_erase[j] << " ";
    445 			}
    446 			cout << endl;
    447 			vector<int> new_v;
    448 			map<int, int> new_m;
    449 			for (int j = 0; j < v.size() - elements_to_erase.size(); j++) {
    450 				int x;
    451 				cin >> x;
    452 				new_v.push_back(x);
    453 				new_m[x]++;
    454 			}
    455 			elements_to_erase.clear();
    456 			int tm = -1;
    457 			for (auto& k : new_m) {
    458 				if (k.second > m[k.first]) {
    459 					tm = k.first;
    460 				}
    461 			}
    462 			if (tm != -1) {
    463 				for (int j = 0; j < new_v.size(); j++) {
    464 					if (new_v[j] != tm)
    465 						elements_to_erase.push_back(j + 1);
    466 					else
    467 						ans = j + 1;
    468 				}
    469 				m.clear();
    470 				m[tm] = new_m[tm];
    471 			}
    472 			v = new_v;
    473 		}
    474 	}
    475 	return 0;
    476 }
    477 ```
    478 
    479 **Rate the problem**
    480 
    481 * Didn't solve
    482 * Good task
    483 * Average task
    484 * Bad task
    485 
    486 [1846G - Rudolf and CodeVid-23](/contest/1846/problem/G "Codeforces Round 883 (Div. 3)")
    487 
    488 Author: [vladmart](/profile/vladmart "Master vladmart")
    489 
    490 **Hint 1**
    491 
    492 Bitmasks
    493 
    494 **Hint 2**
    495 
    496 Weighted graph
    497 
    498 **Hint 3**
    499 
    500 Dijkstra's algorithm
    501 
    502 **Tutorial**
    503 
    504 Tutorial is loading...
    505 
    506 **Solution**
    507 
    508 ```
    509 #include <bits/stdc++.h>
    510 
    511 using namespace std;
    512 
    513 int main() {
    514     ios::sync_with_stdio(false);
    515     cin.tie(nullptr);
    516     cout.tie(nullptr);
    517     int ttt;
    518     cin >> ttt;
    519     while (ttt--) {
    520         int n, m;
    521         cin >> n >> m;
    522         bitset<10> tmp;
    523         cin >> tmp;
    524         int s = (int) tmp.to_ulong();
    525         vector<pair<pair<int, int>, int>> edges(m);
    526         for (int i = 0; i < m; i++) {
    527             cin >> edges[i].second;
    528             cin >> tmp;
    529             edges[i].first.first = ((1 << n) - 1) ^ (int) tmp.to_ulong();
    530             cin >> tmp;
    531             edges[i].first.second = (int) tmp.to_ulong();
    532         }
    533         vector<int> dist(1 << n, INT_MAX);
    534         dist[s] = 0;
    535         set<pair<int, int>> q = {{0, s}};
    536         while (!q.empty()) {
    537             auto [d, v] = *q.begin();
    538             q.erase(q.begin());
    539             for (int i = 0; i < m; i++) {
    540                 int to = v & edges[i].first.first;
    541                 to |= edges[i].first.second;
    542                 if (dist[to] > d + edges[i].second) {
    543                     q.erase({dist[to], to});
    544                     dist[to] = d + edges[i].second;
    545                     q.insert({dist[to], to});
    546                 }
    547             }
    548         }
    549         if (dist[0] == INT_MAX) dist[0] = -1;
    550         cout << dist[0] << '\n';
    551     }
    552     return 0;
    553 }
    554 ```
    555 
    556 **Rate the problem**
    557 
    558 * Didn't solve
    559 * Good task
    560 * Average task
    561 * Bad task