codeforces-scrape

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

1862.md (8790B)


      1 Source: https://codeforces.com/blog/entry/119715
      2 
      3 **We would like to thank all the participants who helped us and Codeforces to overcome the 40.000 registered users for the first time**
      4 
      5 [1862A - Gift Carpet](/contest/1862/problem/A "Codeforces Round 894 (Div. 3)")
      6 
      7 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17  
     18 using namespace std;
     19  
     20 #define int long long
     21  
     22 int32_t main() {
     23     int q;
     24     cin >> q;
     25     while (q--) {
     26         int n, m;
     27         cin >> n >> m;
     28         vector<string> carpet(n);
     29         for (int i = 0; i < n; ++i) {
     30             cin >> carpet[i];
     31         }
     32         string vika = "vika";
     33         int fnd = 0;
     34         for (int i = 0; i < m; ++i) {
     35             bool check = false;
     36             for (int j = 0; j < n; ++j) {
     37                 if (carpet[j][i] == vika[fnd]) {
     38                     check = true;
     39                 }
     40             }
     41             if (check) {
     42                 ++fnd;
     43                 if (fnd == 4) {
     44                     break;
     45                 }
     46             }
     47         }
     48         if (fnd == 4) {
     49             cout << "YES\n";
     50         } else {
     51             cout << "NO\n";
     52         }
     53     }
     54     return 0;
     55 }
     56 ```
     57 
     58 **Rate the problem**
     59 
     60 * Didn't solve
     61 * Good task
     62 * Average task
     63 * Bad task
     64 
     65 [1862B - Sequence Game](/contest/1862/problem/B "Codeforces Round 894 (Div. 3)")
     66 
     67 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Solution**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77  
     78 using namespace std;
     79  
     80 #define int long long
     81  
     82 int32_t main() {
     83     int q;
     84     cin >> q;
     85     while (q--) {
     86         int n;
     87         cin >> n;
     88         vector<int> a;
     89         for (int i = 0; i < n; ++i) {
     90             int x;
     91             cin >> x;
     92             if (i && a.back() > x) {
     93                 a.push_back(1);
     94             }
     95             a.push_back(x);
     96         }
     97         cout << a.size() << "\n";
     98         for (int el : a)
     99             cout << el << " ";
    100         cout << "\n";
    101     }
    102     return 0;
    103 }
    104 ```
    105 
    106 **Rate the problem**
    107 
    108 * Didn't solve
    109 * Good task
    110 * Average task
    111 * Bad task
    112 
    113 [1862C - Flower City Fence](/contest/1862/problem/C "Codeforces Round 894 (Div. 3)")
    114 
    115 Idea: [playerr17](/profile/playerr17 "Expert playerr17")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution**
    122 
    123 ```
    124 #include <iostream>
    125 #include <vector>
    126  
    127 using namespace std;
    128  
    129 int main() {
    130     int t;
    131     cin >> t;
    132     while (t--) {
    133         int n;
    134         cin >> n;
    135         vector<int> a(n + 1);
    136         for (int i = 1; i <= n; i++) {
    137             cin >> a[i];
    138         }
    139         if (a[1] != n) {
    140             cout << "NO" << '\n';
    141             continue;
    142         }
    143         vector<int> b;
    144         for (int i = n; i >= 1; i--) {
    145             while (b.size() < a[i]) {
    146                 b.push_back(i);
    147             }
    148         }
    149         bool meow = true;
    150         for (int i = 1; i <= n; i++) {
    151             if (a[i] != b[i - 1]) {
    152                 cout << "NO" << '\n';
    153                 meow = false;
    154                 break;
    155             }
    156         }
    157         if (meow) {
    158             cout << "YES" << '\n';
    159         }
    160     }
    161     return 0;
    162 }
    163 ```
    164 
    165 **Rate the problem**
    166 
    167 * Didn't solve
    168 * Good task
    169 * Average task
    170 * Bad task
    171 
    172 [1862D - Ice Cream Balls](/contest/1862/problem/D "Codeforces Round 894 (Div. 3)")
    173 
    174 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), [Ivang](/profile/Ivang "Master Ivang")
    175 
    176 **Tutorial**
    177 
    178 Tutorial is loading...
    179 
    180 **Solution**
    181 
    182 ```
    183 #include <bits/stdc++.h>
    184  
    185 using namespace std;
    186  
    187 #define int long long
    188  
    189 int32_t main() {
    190     int q;
    191     cin >> q;
    192     while (q--) {
    193         int n;
    194         cin >> n;
    195         int l = 0, r = min<int>(2e9, 2 * n);
    196         while (r - l > 1) {
    197             int m = (l + r) >> 1;
    198             // m = x + y, answer = x + 2 * y
    199             if (m * (m - 1) / 2 + m < n) {
    200                 l = m;
    201             } else {
    202                 r = m;
    203             }
    204         }
    205         int y = n - r * (r - 1) / 2;
    206         if ((r + 1) * r / 2 <= n) {
    207             cout << min(r + y, r + 1 + n - (r + 1) * r / 2) << "\n";
    208         } else {
    209             cout << r + y << "\n";
    210         }
    211     }
    212     return 0;
    213 }
    214 ```
    215 
    216 **Rate the problem**
    217 
    218 * Didn't solve
    219 * Good task
    220 * Average task
    221 * Bad task
    222 
    223 [1862E - Kolya and Movie Theatre](/contest/1862/problem/E "Codeforces Round 894 (Div. 3)")
    224 
    225 Idea: [pavlekn](/profile/pavlekn "Master pavlekn")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235  
    236 using namespace std;
    237  
    238 #define int long long
    239  
    240 int32_t main() {
    241     int t;
    242     cin >> t;
    243     for (int _ = 0; _ < t; ++_) {
    244         int n, m, d;
    245         cin >> n >> m >> d;
    246         vector<int> a(n);
    247         for (int i = 0; i < n; ++i) {
    248             cin >> a[i];
    249         }
    250         int ans = 0;
    251         set<pair<int, int>> s;
    252         int sum = 0;
    253         for (int i = 0; i < n; ++i) {
    254             int cur = sum + a[i] - d * (i + 1);
    255             ans = max(ans, cur);
    256             if (a[i] > 0) {
    257                 s.insert({a[i], i});
    258                 sum += a[i];
    259                 if (s.size() >= m) {
    260                     sum -= (s.begin()->first);
    261                     s.erase(s.begin());
    262                 }
    263             }
    264         }
    265         cout << ans << endl;
    266     }
    267     return 0;
    268 }
    269 ```
    270 
    271 **Rate the problem**
    272 
    273 * Didn't solve
    274 * Good task
    275 * Average task
    276 * Bad task
    277 
    278 [1862F - Magic Will Save the World](/contest/1862/problem/F "Codeforces Round 894 (Div. 3)")
    279 
    280 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
    281 
    282 **Tutorial**
    283 
    284 Tutorial is loading...
    285 
    286 **Solution**
    287 
    288 ```
    289 #include <bits/stdc++.h>
    290  
    291 using namespace std;
    292  
    293 #define int long long
    294  
    295 int32_t main() {
    296     int q;
    297     cin >> q;
    298     while (q--) {
    299         int w, f, n;
    300         cin >> w >> f >> n;
    301         vector<int> s(n);
    302         int sum_s = 0;
    303         for (int i = 0; i < n; ++i) {
    304             cin >> s[i];
    305             sum_s += s[i];
    306         }
    307         vector<bool> dp(sum_s + 1);
    308         dp[0] = true;
    309         for (int i = 0; i < n; ++i) {
    310             for (int w = sum_s; w - s[i] >= 0; --w) {
    311                 dp[w] = dp[w] || dp[w - s[i]];
    312             }
    313         }
    314         int ans = 2e9;
    315         for (int i = 0; i <= sum_s; ++i) {
    316             if (dp[i]) {
    317                 ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));
    318             }
    319         }
    320         cout << ans << "\n";
    321     }
    322     return 0;
    323 }
    324 ```
    325 
    326 **Rate the problem**
    327 
    328 * Didn't solve
    329 * Good task
    330 * Average task
    331 * Bad task
    332 
    333 [1862G - The Great Equalizer](/contest/1862/problem/G "Codeforces Round 894 (Div. 3)")
    334 
    335 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
    336 
    337 **Tutorial**
    338 
    339 Tutorial is loading...
    340 
    341 **Solution**
    342 
    343 ```
    344 #include <bits/stdc++.h>
    345  
    346 using namespace std;
    347  
    348 int main() {
    349     int t;
    350     cin >> t;
    351     while (t--) {
    352         int n;
    353         scanf("%d", &n);
    354         vector<int> a(n);
    355         for (int i = 0; i < n; ++i) {
    356             scanf("%d", &a[i]);
    357         }
    358         if (n == 1) {
    359             int q;
    360             scanf("%d", &q);
    361             while (q--) {
    362                 int pos, val;
    363                 scanf("%d %d", &pos, &val);
    364                 cout << val << " ";
    365             }
    366             cout << "\n";
    367             continue;
    368         }
    369         multiset<int> aset;
    370         for (int i = 0; i < n; ++i) {
    371             aset.insert(a[i]);
    372         }
    373         multiset<int> deltas;
    374         for (auto it = ++aset.begin(); it != aset.end(); ++it) {
    375             auto prev = it;
    376             --prev;
    377             deltas.insert(*it - *prev);
    378         }
    379         int q;
    380         scanf("%d", &q);
    381         while (q--) {
    382             int pos, val;
    383             scanf("%d %d", &pos, &val);
    384             auto it = aset.find(a[pos - 1]);
    385             auto nxt = it, prev = it;
    386             ++nxt; --prev;
    387             if (it == aset.begin()) {
    388                 deltas.erase(deltas.find(*nxt - *it));
    389             } else if (it == --aset.end()) {
    390                 deltas.erase(deltas.find(*it - *prev));
    391             } else {
    392                 deltas.erase(deltas.find(*nxt - *it));
    393                 deltas.erase(deltas.find(*it - *prev));
    394                 deltas.insert(*nxt - *prev);
    395             }
    396             aset.erase(it);
    397             aset.insert(val);
    398             it = aset.find(val);
    399             nxt = it, prev = it;
    400             ++nxt; --prev;
    401             if (it == aset.begin()) {
    402                 deltas.insert(*nxt - *it);
    403             } else if (it == --aset.end()) {
    404                 deltas.insert(*it - *prev);
    405             } else {
    406                 deltas.insert(*nxt - *it);
    407                 deltas.insert(*it - *prev);
    408                 deltas.erase(deltas.find(*nxt - *prev));
    409             }
    410             a[pos - 1] = val;
    411             cout << *--aset.end() + *--deltas.end() << " ";
    412         }
    413         cout << "\n";
    414     }
    415     return 0;
    416 }
    417 ```
    418 
    419 **Rate the problem**
    420 
    421 * Didn't solve
    422 * Good task
    423 * Average task
    424 * Bad task