codeforces-scrape

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

2114.md (9132B)


      1 Source: https://codeforces.com/blog/entry/143268
      2 
      3 [2114A - Square Year](/contest/2114/problem/A "Codeforces Round 1027 (Div. 3)")
      4 
      5 Idea: [myav](/profile/myav "Pupil myav")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 void solve() {
     19     int n;
     20     cin >> n;
     21     int sq = ceil(sqrt(n));
     22     if (sq * sq == n) {
     23         cout << 0 << ' ' << sq << "\n";
     24     } else {
     25         cout << "-1\n";
     26     }
     27 }
     28 
     29 int main() {
     30     int t;
     31     cin >> t;
     32     while (t--) solve();
     33 }
     34 ```
     35 
     36 **Rate the problem**
     37 
     38 * Didn't solve
     39 * Good task
     40 * Average task
     41 * Bad task
     42 
     43 [2114B - Not Quite a Palindromic String](/contest/2114/problem/B "Codeforces Round 1027 (Div. 3)")
     44 
     45 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 #define int long long
     57 #define pb emplace_back
     58 #define mp make_pair
     59 #define x first
     60 #define y second
     61 #define all(a) a.begin(), a.end()
     62 #define rall(a) a.rbegin(), a.rend()
     63 
     64 typedef long double ld;
     65 typedef long long ll;
     66 
     67 using namespace std;
     68 
     69 mt19937 rnd(time(nullptr));
     70 
     71 const int inf = 1e9;
     72 const int M = 1e9 + 7;
     73 const ld pi = atan2(0, -1);
     74 const ld eps = 1e-6;
     75 
     76 void solve(int tc){
     77     int n, k;
     78     cin >> n >> k;
     79     string s;
     80     cin >> s;
     81     vector<int> cnt(2);
     82     for(char c: s){
     83         cnt[c - '0']++;
     84     }
     85     int mn = max(cnt[0], cnt[1]) - n / 2;
     86     int mx = cnt[0] / 2 + cnt[1] / 2;
     87     if(k >= mn && (k - mn) % 2 == 0 && k <= mx) cout << "YES";
     88     else cout << "NO";
     89 }
     90 
     91 bool multi = true;
     92 
     93 signed main() {
     94     int t = 1;
     95     if (multi)cin >> t;
     96     for (int i = 1; i <= t; ++i) {
     97         solve(i);
     98         cout << "\n";
     99     }
    100     return 0;
    101 }
    102 ```
    103 
    104 **Rate the problem**
    105 
    106 * Didn't solve
    107 * Good task
    108 * Average task
    109 * Bad task
    110 
    111 [2114C - Need More Arrays](/contest/2114/problem/C "Codeforces Round 1027 (Div. 3)")
    112 
    113 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 void solve(int tc){
    127     int n;
    128     cin >> n;
    129     int last = -1, ans = 0;
    130     for(int i = 0; i < n; ++i){
    131         int a;
    132         cin >> a;
    133         if(a - last > 1){
    134             ans++;
    135             last = a;
    136         }
    137     }
    138     cout << ans;
    139 }
    140 
    141 bool multi = true;
    142 
    143 signed main() {
    144     int t = 1;
    145     if (multi)cin >> t;
    146     for (int i = 1; i <= t; ++i) {
    147         solve(i);
    148         cout << "\n";
    149     }
    150     return 0;
    151 }
    152 ```
    153 
    154 **Rate the problem**
    155 
    156 * Didn't solve
    157 * Good task
    158 * Average task
    159 * Bad task
    160 
    161 [2114D - Come a Little Closer](/contest/2114/problem/D "Codeforces Round 1027 (Div. 3)")
    162 
    163 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    164 
    165 **Tutorial**
    166 
    167 Tutorial is loading...
    168 
    169 **Solution**
    170 
    171 ```
    172 #include <bits/stdc++.h>
    173 
    174 #define int long long
    175 #define pb emplace_back
    176 #define mp make_pair
    177 #define x first
    178 #define y second
    179 #define all(a) a.begin(), a.end()
    180 #define rall(a) a.rbegin(), a.rend()
    181 
    182 typedef long double ld;
    183 typedef long long ll;
    184 
    185 using namespace std;
    186 
    187 mt19937 rnd(time(nullptr));
    188 
    189 const int inf = 1e9;
    190 const int M = 1e9 + 7;
    191 const ld pi = atan2(0, -1);
    192 const ld eps = 1e-6;
    193 
    194 struct min_max{
    195     int mx1, mx2, mn1, mn2;
    196 
    197     void fix_mx(){
    198         if(mx1 < mx2){
    199             swap(mx1, mx2);
    200         }
    201     }
    202     void fix_mn(){
    203         if(mn1 > mn2){
    204             swap(mn1, mn2);
    205         }
    206     }
    207 
    208     min_max(int a, int b){
    209         mx1 = mn1 = a;
    210         mx2 = mn2 = b;
    211         fix_mx();
    212         fix_mn();
    213     }
    214 
    215     void add(int x){
    216         mx2 = max(mx2, x);
    217         mn2 = min(mn2, x);
    218         fix_mx();
    219         fix_mn();
    220     }
    221 
    222     int get_seg(int x){
    223         pair<int, int> res = {mn1, mx1};
    224         if(x == mn1) res.x = mn2;
    225         if(x == mx1) res.y = mx2;
    226         return res.y - res.x + 1;
    227     }
    228 };
    229 
    230 void solve(int tc){
    231     int n;
    232     cin >> n;
    233     vector<pair<int, int>> coord(n);
    234     for(auto &e: coord){
    235         cin >> e.x >> e.y;
    236     }
    237     if(n <= 2){
    238         cout << n;
    239         return;
    240     }
    241 
    242     min_max xc(coord[0].x, coord[1].x), yc(coord[0].y, coord[1].y);
    243     for(int i = 2; i < n; ++i){
    244         xc.add(coord[i].x);
    245         yc.add(coord[i].y);
    246     }
    247 
    248     int ans = xc.get_seg(-1) * yc.get_seg(-1);
    249     for(int i = 0; i < n; ++i){
    250         int x = xc.get_seg(coord[i].x);
    251         int y = yc.get_seg(coord[i].y);
    252         if(x * y == n - 1){
    253             ans = min(ans, min((x + 1) * y, x * (y + 1)));
    254         }
    255         else{
    256             ans = min(ans, x * y);
    257         }
    258     }
    259     cout << ans;
    260 }
    261 
    262 bool multi = true;
    263 
    264 signed main() {
    265     int t = 1;
    266     if (multi)cin >> t;
    267     for (int i = 1; i <= t; ++i) {
    268         solve(i);
    269         cout << "\n";
    270     }
    271     return 0;
    272 }
    273 ```
    274 
    275 **Rate the problem**
    276 
    277 * Didn't solve
    278 * Good task
    279 * Average task
    280 * Bad task
    281 
    282 [2114E - Kirei Attacks the Estate](/contest/2114/problem/E "Codeforces Round 1027 (Div. 3)")
    283 
    284 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    285 
    286 **Tutorial**
    287 
    288 Tutorial is loading...
    289 
    290 **Solution**
    291 
    292 ```
    293 from math import inf
    294 from sys import setrecursionlimit
    295 
    296 def solve(v, p, mini, maxi):
    297     global res
    298     res[v] = max(arr[v], mini * -1 + arr[v])
    299     mini = min(arr[v], maxi * -1 + arr[v])
    300     for u in gr[v]:
    301         if u == p:
    302             continue
    303         solve(u, v, mini, res[v])
    304 
    305 setrecursionlimit(400_000)
    306 t = int(input())
    307 for _ in range(t):
    308     n = int(input())
    309     arr = list(map(int, input().split()))
    310     gr = [[] for _ in range(n)]
    311     for j in range(n - 1):
    312         v, u = map(int, input().split())
    313         gr[v - 1].append(u - 1)
    314         gr[u - 1].append(v - 1)
    315     res = [0] * n
    316     solve(0, -1, 0, 0)
    317     print(*res)
    318 ```
    319 
    320 **Rate the problem**
    321 
    322 * Didn't solve
    323 * Good task
    324 * Average task
    325 * Bad task
    326 
    327 [2114F - Small Operations](/contest/2114/problem/F "Codeforces Round 1027 (Div. 3)")
    328 
    329 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    330 
    331 **Tutorial**
    332 
    333 Tutorial is loading...
    334 
    335 **Solution**
    336 
    337 ```
    338 #include <bits/stdc++.h>
    339  
    340 #define int long long
    341 #define pb emplace_back
    342 #define mp make_pair
    343 #define x first
    344 #define y second
    345 #define all(a) a.begin(), a.end()
    346 #define rall(a) a.rbegin(), a.rend()
    347  
    348 typedef long double ld;
    349 typedef long long ll;
    350  
    351 using namespace std;
    352  
    353 mt19937 rnd(time(nullptr));
    354  
    355 const int inf = 1e9;
    356 const int M = 1e9 + 7;
    357 const ld pi = atan2(0, -1);
    358 const ld eps = 1e-6;
    359 
    360 int gcd(int a, int b) {
    361     return b == 0 ? a : gcd(b, a % b);
    362 }
    363 
    364 int get_ans(int x, int k){
    365     if(x == 1) return 0;
    366     vector<int> divs;
    367     for(int i = 1; i * i <= x; i++){
    368         if(x % i == 0){
    369             divs.push_back(i);
    370             divs.push_back(x / i);
    371         }
    372     }
    373     sort(all(divs));
    374     int n = divs.size();
    375     vector<int> dp(n, 100);
    376     dp[0] = 0;
    377     for(int i = 1; i < n; i++){
    378         for(int j = i - 1; j >= 0; j--){
    379             if(divs[i] / divs[j] > k){
    380                 break;
    381             }
    382             if(divs[i] % divs[j] == 0) {
    383                 dp[i] = min(dp[i], dp[j] + 1);
    384             }
    385         }
    386     }
    387     return dp[n - 1] == 100 ? -1 : dp[n - 1];
    388 }
    389 
    390 void solve(int tc){
    391     int x, y, k;
    392     cin >> x >> y >> k;
    393     int g = gcd(x, y);
    394     x /= g;
    395     y /= g;
    396     int ax = get_ans(x, k);
    397     int ay = get_ans(y, k);
    398     if(ax == -1 || ay == -1) cout << -1;
    399     else cout << ax + ay;
    400 }
    401 
    402 bool multi = true;
    403 
    404 signed main() {
    405     int t = 1;
    406     if (multi) cin >> t;
    407     for (int i = 1; i <= t; ++i) {
    408         solve(i);
    409         cout << "\n";
    410     }
    411     return 0;
    412 }
    413 ```
    414 
    415 **Rate the problem**
    416 
    417 * Didn't solve
    418 * Good task
    419 * Average task
    420 * Bad task
    421 
    422 [2114G - Build an Array](/contest/2114/problem/G "Codeforces Round 1027 (Div. 3)")
    423 
    424 Idea: [myav](/profile/myav "Pupil myav")
    425 
    426 **Tutorial**
    427 
    428 Tutorial is loading...
    429 
    430 **Solution**
    431 
    432 ```
    433 #include <bits/stdc++.h>
    434 
    435 #define int long long
    436 #define pb emplace_back
    437 #define mp make_pair
    438 #define x first
    439 #define y second
    440 #define all(a) a.begin(), a.end()
    441 #define rall(a) a.rbegin(), a.rend()
    442 
    443 typedef long double ld;
    444 typedef long long ll;
    445 
    446 using namespace std;
    447 
    448 mt19937 rnd(time(nullptr));
    449 
    450 const int inf = 1e9;
    451 const int M = 1e9 + 7;
    452 const ld pi = atan2(0, -1);
    453 const ld eps = 1e-6;
    454 
    455 int max_op(int a, int b) {
    456     int min_part = a;
    457     while (min_part % 2 == 0 && min_part / 2 != b) {
    458         min_part /= 2;
    459     }
    460     if (min_part % 2 == 1) {
    461         return a / min_part;
    462     }
    463     int true_min = min_part;
    464     while (true_min % 2 == 0) {
    465         true_min /= 2;
    466     }
    467     return 1 + (a - min_part) / true_min;
    468 }
    469 
    470 void solve(int tc){
    471     int n, k;
    472     cin >> n >> k;
    473     vector<int> a(n);
    474     for (int &e: a) cin >> e;
    475     vector<int> pre(n, 0);
    476     for (int j = 1; j < n; ++j) {
    477         pre[j] = pre[j - 1] + max_op(a[j - 1], a[j]);
    478     }
    479     vector<int> suf(n, 0);
    480     for (int j = n - 2; j >= 0; --j) {
    481         suf[j] = suf[j + 1] + max_op(a[j + 1], a[j]);
    482     }
    483     for (int i = 0; i < n; i++) {
    484         int res = max_op(a[i], 0) + pre[i] + suf[i];
    485         if (res >= k) {
    486             cout << "YES";
    487             return;
    488         }
    489     }
    490     cout << "NO";
    491 }
    492 
    493 bool multi = true;
    494 
    495 signed main() {
    496 
    497     int t = 1;
    498     if (multi) cin >> t;
    499     for (int i = 1; i <= t; ++i) {
    500         solve(i);
    501         cout << "\n";
    502     }
    503     return 0;
    504 }
    505 ```
    506 
    507 **Rate the problem**
    508 
    509 * Didn't solve
    510 * Good task
    511 * Average task
    512 * Bad task