codeforces-scrape

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

1690.md (6621B)


      1 Source: https://codeforces.com/blog/entry/103658
      2 
      3 [1690A - Print a Pedestal (Codeforces logo?)](/contest/1690/problem/A "Codeforces Round 797 (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 <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 #define sz(v) (int)v.size()
     20 #define all(v) v.begin(),v.end()
     21 #define eb emplace_back
     22  
     23  
     24  
     25 void solve() {
     26     int n; 
     27     cin >> n;
     28     for (int a = 3; a < n; a++) {
     29         int c = (n - a) / 2;
     30         int b = n - a - c;
     31         if (c > 1 && b+1 < a) {
     32             c--;
     33             b++;
     34         }
     35         if (a > b && b > c) {
     36             cout << b << ' ' << a << ' ' << c << endl;
     37             return;
     38         }
     39     }
     40 }
     41  
     42 int main() {
     43     int t;
     44     cin >> t;
     45  
     46     forn(tt, t) {
     47         solve();
     48     }
     49 }
     50 ```
     51 
     52 [1690B - Array Decrements](/contest/1690/problem/B "Codeforces Round 797 (Div. 3)")
     53 
     54 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution**
     61 
     62 ```
     63 #include<bits/stdc++.h>
     64  
     65 #define forn(i, n) for (int i = 0; i < int(n); i++)
     66  
     67 using namespace std;
     68 const int inf = 1e9 + 7;
     69  
     70 bool equals(vector<int>&a, vector<int>&b, int n){
     71     int dif = inf;
     72     forn(i, n){
     73         if(b[i] != 0) dif = min(dif, a[i] - b[i]);
     74     }
     75     if(dif < 0) return false; 
     76     if(dif == inf) return true;
     77     forn(i, n){
     78         if(a[i] - b[i] > dif) return false;
     79         if(b[i] != 0 && a[i] - b[i] < dif) return false;
     80     }
     81     return true;
     82 }
     83  
     84 void solve(){
     85     int n;
     86     cin >> n;
     87     vector<int>a(n), b(n);
     88     forn(i, n) cin >> a[i];
     89     forn(i, n) cin >> b[i];
     90     cout << (equals(a, b, n) ? "YES\n" : "NO\n");
     91  
     92 }
     93  
     94 int main(){
     95     int t;
     96     cin >> t;
     97     while(t--){
     98         solve();
     99     }
    100 }
    101 ```
    102 
    103 [1690C - Restoring the Duration of Tasks](/contest/1690/problem/C "Codeforces Round 797 (Div. 3)")
    104 
    105 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution**
    112 
    113 ```
    114 #include <bits/stdc++.h>
    115  
    116 using namespace std;
    117  
    118 typedef long long ll;
    119  
    120 #define forn(i, n) for (int i = 0; i < int(n); i++)
    121  
    122  
    123 void solve() {
    124     int n;
    125     cin >> n;
    126     int s[n];
    127     int f[n];
    128     for (int i = 0; i < n; ++i) {
    129         cin >> s[i];
    130     }
    131  
    132     for (int i = 0; i < n; ++i) {
    133         cin >> f[i];
    134     }
    135     int curTime = 0;
    136     int d[n];
    137     for (int i = 0; i < n; ++i) {
    138         curTime = max(curTime, s[i]);
    139         d[i] = f[i] - curTime;
    140         curTime = f[i];
    141     }
    142     for (auto now: d) {
    143         cout << now << " ";
    144     }
    145     cout << '\n';
    146 }
    147 int main() {
    148     int tests;
    149     cin >> tests;
    150     forn(tt, tests) {
    151         solve();
    152     }
    153 }
    154 ```
    155 
    156 [1690D - Black and White Stripe](/contest/1690/problem/D "Codeforces Round 797 (Div. 3)")
    157 
    158 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution**
    165 
    166 ```
    167 #include <bits/stdc++.h>
    168  
    169 using namespace std;
    170  
    171 #define forn(i, n) for (int i = 0; i < int(n); i++)
    172  
    173 int main() {
    174     int t;
    175     cin >> t;
    176     forn(tt, t) {
    177         int n, k;
    178         cin >> n >> k;
    179         string s;
    180         cin >> s;
    181         vector<int> w(n + 1);
    182         for (int i = 1; i <= n; i++)
    183             w[i] = w[i - 1] + int(s[i - 1] == 'W');
    184         int result = INT_MAX;
    185         for (int i = k; i <= n; i++)
    186             result = min(result, w[i] - w[i - k]);
    187         cout << result << endl;
    188     }
    189 }
    190 ```
    191 
    192 [1690E - Price Maximization](/contest/1690/problem/E "Codeforces Round 797 (Div. 3)")
    193 
    194 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), [Aris](/profile/Aris "Expert Aris")
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution**
    201 
    202 ```
    203 #include<bits/stdc++.h>
    204 #define len(s) (int)s.size()
    205 using namespace std;
    206 using ll = long long;
    207  
    208 void solve(){
    209     int n, k;
    210     cin >> n >> k;
    211     vector<ll>a(n);
    212     ll sum = 0;
    213     for(int i = 0; i < n; i++) {
    214         cin >> a[i];
    215         sum += a[i] / k;
    216         a[i] = a[i] % k;
    217     }
    218     sort(a.begin(), a.end(), [] (int x, int y){
    219         return x > y;
    220     });
    221  
    222     for(int i = 0, j = n - 1; i < j; i++, j--){
    223         while(a[i] + a[j] < k && i < j) j--;
    224         if(i == j) break;
    225         sum++;
    226     }
    227     cout << sum << endl;
    228 }
    229  
    230 int main(){
    231     int t;
    232     cin >> t;
    233     while(t--){
    234         solve();
    235     }
    236     return 0;
    237 }
    238 ```
    239 
    240 [1690F - Shifting String](/contest/1690/problem/F "Codeforces Round 797 (Div. 3)")
    241 
    242 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    243 
    244 **Tutorial**
    245 
    246 Tutorial is loading...
    247 
    248 **Solution**
    249 
    250 ```
    251 def gcd(a, b):
    252     if b == 0:
    253         return a;
    254     return gcd(b, a % b)
    255     
    256     
    257 def shift(s):
    258     for i in range(1, len(s) + 1):
    259         if s == s[i:] + s[:i]:
    260             return i
    261     
    262  
    263 def solve():
    264     n = int(input())
    265     s = input()
    266     p = [int(x)-1 for x in input().split()]
    267     used = [False] * n
    268     ans = 1
    269     i = 0
    270     while i < n:
    271         ss = ''
    272         while not used[i]:
    273             ss += s[i]
    274             used[i] = True
    275             i = p[i];
    276         i += 1
    277         if len(ss) == 0:
    278             continue
    279         ln = shift(ss)
    280         ans = ans * ln // gcd(ans, ln)
    281     print(ans)
    282     
    283  
    284 t = int(input())
    285 for _ in range(t):
    286     solve()
    287 ```
    288 
    289 [1690G - Count the Trains](/contest/1690/problem/G "Codeforces Round 797 (Div. 3)")
    290 
    291 Idea: [Aris](/profile/Aris "Expert Aris")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution**
    298 
    299 ```
    300 #include<bits/stdc++.h>
    301  
    302 using namespace std;
    303  
    304 int main() {
    305     ios_base::sync_with_stdio(0);
    306     cin.tie(0);
    307     cout.tie(0);
    308     int t;
    309     cin >> t;
    310     while (t--) {
    311         int n, m;
    312         cin >> n >> m;
    313         vector<int> a(n);
    314         set<int> tmp;
    315         for (int i = 0; i < n; i++) {
    316             cin >> a[i];
    317             if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {
    318                 tmp.insert(i);
    319             }
    320         }
    321         for (int i = 0; i < m; i++) {
    322             int j, d;
    323             cin >> j >> d;
    324             j--;
    325             a[j] -= d;
    326             auto it = tmp.upper_bound(j);
    327             if (it != tmp.begin()) {
    328                 it = prev(it);
    329                 if (*it == j || a[*it] > a[j]) {
    330                     tmp.insert(j);
    331                 }
    332             } else {
    333                 tmp.insert(j);
    334             }
    335             while (1) {
    336                 it = tmp.upper_bound(j);
    337                 if (it != tmp.end() && a[*it] >= a[j]) {
    338                     tmp.erase(it);
    339                 } else {
    340                     break;
    341                 }
    342             }
    343             cout << (int) tmp.size() << " ";
    344         }
    345         cout << '\n';
    346     }
    347 }
    348 ```