codeforces-scrape

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

1660.md (6109B)


      1 Source: https://codeforces.com/blog/entry/101526
      2 
      3 [1660A - Vasya and Coins](/contest/1660/problem/A "Codeforces Round 780 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <iostream>
     15 #include <vector>
     16 #include <algorithm>
     17 #include <set>
     18  
     19 using namespace std;
     20  
     21 int main() {
     22     int t;
     23     cin >> t;
     24     for (int it = 0; it < t; ++it) {
     25         int a, b;
     26         cin >> a >> b;
     27         cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n';
     28     }
     29     return 0;
     30 }
     31 ```
     32 
     33 [1660B - Vlad and Candies](/contest/1660/problem/B "Codeforces Round 780 (Div. 3)")
     34 
     35 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution**
     42 
     43 ```
     44 t = int(input())
     45 for _ in range(t):
     46     n = int(input())
     47     a = [int(x) for x in input().split()]
     48     a.sort()
     49     if n == 1:
     50         if a[0] > 1:
     51             print("NO")
     52         else:
     53             print("YES")
     54         continue
     55     if a[-2] + 1 < a[-1]:
     56         print("NO")
     57     else:
     58         print("YES")
     59 ```
     60 
     61 [1660C - Get an Even String](/contest/1660/problem/C "Codeforces Round 780 (Div. 3)")
     62 
     63 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution**
     70 
     71 ```
     72 #include<bits/stdc++.h>
     73 using namespace std;
     74 int sz = 26;
     75  
     76 void solve(){
     77     string s;
     78     cin >> s;
     79     int m = 0, n = (int)s.size();
     80     vector<bool>prev(sz, false);
     81     for(auto &i : s){
     82         if(prev[i - 'a']){
     83             m += 2;
     84             for(int j = 0; j < sz; j++) prev[j] = false;
     85         }
     86         else prev[i - 'a'] = true;
     87     }
     88  
     89     cout << n - m << endl;
     90 }
     91  
     92 int main(){
     93     int t;
     94     cin >> t;
     95     while (t--){
     96         solve();
     97     }
     98 }
     99 ```
    100 
    101 [1660D - Maximum Product Strikes Back](/contest/1660/problem/D "Codeforces Round 780 (Div. 3)")
    102 
    103 Idea: [Aris](/profile/Aris "Candidate Master Aris")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113  
    114 using namespace std;
    115  
    116 #define forn(i, n) for (int i = 0; i < int(n); i++)
    117 #define sz(v) (int)v.size()
    118  
    119  
    120 void solve() {
    121     int n; cin >> n;
    122     vector<int> a(n);
    123  
    124     forn(i, n) 
    125         cin >> a[i];
    126     int ans = 0;
    127     int ap = n, as = 0;
    128     for(int i = 0, l = -1; i <= n; i++) {
    129         if (i == n || a[i] == 0) {
    130             int cnt = 0;
    131             bool neg = false;
    132             int left = -1, right = -1;
    133             int cl = 0, cr = 0;
    134             for (int j = l+1; j < i; j++) {
    135                 neg ^= a[j] < 0;
    136                 if (a[j] < 0) {
    137                     right = j;
    138                     cr = 0;
    139                 }
    140  
    141                 if (abs(a[j]) == 2) {
    142                     cnt++, cr++;
    143                     if (left == -1) cl++;
    144                 }
    145  
    146                 if (a[j] < 0 && left == -1) {
    147                     left = j;
    148                 }
    149             }
    150             if (neg) {
    151                 if (cnt - cl > cnt - cr) {
    152                     right = i;
    153                     cnt -= cl;
    154                 } else {
    155                     left = l;
    156                     cnt -= cr;
    157                 }
    158             } else {
    159                 left = l, right = i;
    160             }
    161             if (ans < cnt) {
    162                 ans = cnt;
    163                 ap = left + 1, as = n - right;
    164             }
    165  
    166             l = i;
    167         }
    168     }
    169     cout << ap << ' ' << as << endl;
    170 }
    171  
    172 int main() {
    173     int t;
    174     cin >> t;
    175  
    176     forn(tt, t) {
    177         solve();
    178     }
    179 }
    180 ```
    181 
    182 [1660E - Matrix and Shifts](/contest/1660/problem/E "Codeforces Round 780 (Div. 3)")
    183 
    184 Idea: [myav](/profile/myav "Pupil myav"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    185 
    186 **Tutorial**
    187 
    188 Tutorial is loading...
    189 
    190 **Solution**
    191 
    192 ```
    193 #include <bits/stdc++.h>
    194  
    195 using namespace std;
    196  
    197 #define forn(i, n) for (int i = 0; i < int(n); i++)
    198 #define sz(v) (int)v.size()
    199 #define all(v) v.begin(),v.end()
    200 #define eb emplace_back
    201  
    202 const int INF = INT_MAX >> 1;
    203  
    204 void solve() {
    205     int n; cin >> n;
    206     int cnt1 = 0;
    207     vector<int> cnt (n, 0);
    208     for (int i = 0; i < n; i++) {
    209         string s; cin >> s;
    210         for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') {
    211             cnt1++;
    212             cnt[k]++;
    213         }
    214     }
    215     int ans = INF;
    216     for (int i = 0; i < sz(cnt); i++) {
    217         ans = min(ans, cnt1 - cnt[i] + (n - cnt[i]));
    218     }
    219     cout << ans << endl;
    220 }
    221  
    222 int main() {
    223     int t;
    224     cin >> t;
    225  
    226     forn(tt, t) {
    227         solve();
    228     }
    229 }
    230 ```
    231 
    232 [1660F1 - Promising String (easy version)](/contest/1660/problem/F1 "Codeforces Round 780 (Div. 3)")
    233 
    234 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    235 
    236 **Tutorial**
    237 
    238 Tutorial is loading...
    239 
    240 **Solution**
    241 
    242 ```
    243 tst = int(input())
    244 for _ in range(tst):
    245     n = int(input())
    246     s = input()
    247     b = [0 for i in range(n+1)]
    248     bal = n
    249     b[0] = bal
    250     ans = 0
    251     for i in range(1,n+1):
    252         if s[i-1] == '+':
    253             bal += 1
    254         else:
    255             bal -= 1
    256         b[i] = bal
    257         for j in range(i):
    258             if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
    259                 ans += 1
    260     print(ans)
    261 ```
    262 
    263 [1660F2 - Promising String (hard version)](/contest/1660/problem/F2 "Codeforces Round 780 (Div. 3)")
    264 
    265 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    266 
    267 **Tutorial**
    268 
    269 Tutorial is loading...
    270 
    271 **Solution**
    272 
    273 ```
    274 tst = int(input())
    275 for _ in range(tst):
    276     n = int(input())
    277     s = input()
    278     f = [0 for i in range(3)]
    279     cur_bal = n
    280     cnt_bal = [0 for i in range(2 * n + 1)]
    281     cnt_bal[cur_bal] += 1
    282     f[cur_bal % 3] += 1
    283     ans = 0
    284     for i in range(n):
    285         #print(f)
    286         #print(cur_bal, ans)
    287         new_bal = cur_bal
    288         if s[i] == '-':
    289             new_bal -= 1
    290             f[new_bal % 3] += cnt_bal[new_bal]
    291             ans += f[new_bal % 3]
    292             cnt_bal[new_bal] += 1
    293             f[new_bal % 3] += 1
    294         else:
    295             f[new_bal % 3] -= cnt_bal[new_bal]
    296             new_bal += 1
    297             ans += f[new_bal % 3]
    298             cnt_bal[new_bal] += 1
    299             f[new_bal % 3] += 1
    300         cur_bal = new_bal
    301     print(ans)
    302 ```