codeforces-scrape

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

1907.md (6472B)


      1 Source: https://codeforces.com/blog/entry/123012
      2 
      3 [1907A - Rook](/contest/1907/problem/A "Codeforces Round 913 (Div. 3)")
      4 
      5 Idea: [pashka](/profile/pashka "International Grandmaster pashka")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     s = input()
     16     for c in "abcdefgh":
     17         if c != s[0]:
     18             print(c + s[1], end=' ')
     19     for c in "12345678":
     20         if c != s[1]:
     21             print(s[0] + c, end=' ')
     22     print()
     23 ```
     24 
     25 [1907B - YetnotherrokenKeoard](/contest/1907/problem/B "Codeforces Round 913 (Div. 3)")
     26 
     27 Idea: [pashka](/profile/pashka "International Grandmaster pashka"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution**
     34 
     35 ```
     36 for _ in range(int(input())):
     37     s = list(input())
     38     n = len(s)
     39     upper = []
     40     lower = []
     41     for i in range(n):
     42         if s[i] == 'b':
     43             s[i] = ''
     44             if lower:
     45                 s[lower.pop()] = ''
     46             continue
     47         if s[i] == 'B':
     48             s[i] = ''
     49             if upper:
     50                 s[upper.pop()] = ''
     51             continue
     52         if 'a' <= s[i] <= 'z':
     53             lower += [i]
     54         else:
     55             upper += [i]
     56     print(''.join(s))
     57 ```
     58 
     59 [1907C - Removal of Unattractive Pairs](/contest/1907/problem/C "Codeforces Round 913 (Div. 3)")
     60 
     61 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution**
     68 
     69 ```
     70 orda = ord('a')
     71 
     72 def solve():
     73     n = int(input())
     74     cnt = [0] * 26
     75     for c in input():
     76         cnt[ord(c) - orda] += 1
     77     mx = max(cnt)
     78     print(max(n % 2, 2 * mx - n))
     79 
     80 for _ in range(int(input())):
     81     solve()
     82 ```
     83 
     84 [1907D - Jumping Through Segments](/contest/1907/problem/D "Codeforces Round 913 (Div. 3)")
     85 
     86 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution**
     93 
     94 ```
     95 def solve():
     96     n = int(input())
     97     seg = [list(map(int, input().split())) for x in range(n)]
     98 
     99     def check(k):
    100         ll, rr = 0, 0
    101         for e in seg:
    102             ll = max(ll - k, e[0])
    103             rr = min(rr + k, e[1])
    104             if ll > rr:
    105                 return False
    106         return True
    107 
    108     l, r = -1, 10 ** 9
    109     while r - l > 1:
    110         mid = (r + l) // 2
    111         if check(mid):
    112             r = mid
    113         else:
    114             l = mid
    115     print(r)
    116 
    117 for _ in range(int(input())):
    118     solve()
    119 ```
    120 
    121 [1907E - Good Triples](/contest/1907/problem/E "Codeforces Round 913 (Div. 3)")
    122 
    123 Idea: [pashka](/profile/pashka "International Grandmaster pashka")
    124 
    125 **Tutorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Solution**
    130 
    131 ```
    132 t = int(input())
    133 for _ in range(t):
    134     n = int(input())
    135     cnt = 1
    136     while n > 0:
    137         d = n % 10
    138         n //= 10
    139         mul = 0
    140         for i in range(d + 1):
    141             for j in range(d + 1):
    142                 if d - i - j >= 0:
    143                     mul += 1
    144         cnt *= mul
    145     print(cnt)
    146 ```
    147 
    148 [1907F - Shift and Reverse](/contest/1907/problem/F "Codeforces Round 913 (Div. 3)")
    149 
    150 Idea: [pashka](/profile/pashka "International Grandmaster pashka")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution**
    157 
    158 ```
    159 t = int(input())
    160 for _ in range(t):
    161     n = int(input())
    162     a = list(map(int, input().split()))
    163     a = list(reversed(a))*2
    164     p = [0]
    165     q = [0]
    166     for i in range(n*2-1):
    167         p.append(p[-1]+1 if a[i]>=a[i+1] else 0)
    168         q.append(q[-1]+1 if a[i]<=a[i+1] else 0)
    169     minn = 1000000
    170     for i in range(n-1,len(p)):
    171         if p[i] == n-1:
    172             minn = min(minn, i-n+1, len(p)-i+1)
    173         if q[i] == n-1:
    174             minn = min(minn, len(p)-i, i-n+2)
    175     print(-1 if minn == 1000000 else minn)
    176 ```
    177 
    178 [1907G - Lights](/contest/1907/problem/G "Codeforces Round 913 (Div. 3)")
    179 
    180 Idea: [pashka](/profile/pashka "International Grandmaster pashka")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 #define long long long int
    192 #define DEBUG
    193 using namespace std;
    194 
    195 // @author: pashka
    196 
    197 void solve(){
    198     int n;
    199     cin >> n;
    200     vector<bool> s(n);
    201     {
    202         string ss;
    203         cin >> ss;
    204         for (int i = 0; i < n; i++) {
    205             s[i] = ss[i] == '1';
    206         }
    207     }
    208     vector<int> a(n);
    209     for (int i = 0; i < n; i++) {
    210         cin >> a[i];
    211         a[i]--;
    212     }
    213 
    214     vector<int> res;
    215     vector<int> d(n);
    216     for (int i = 0; i < n; i++) {
    217         d[a[i]]++;
    218     }
    219     vector<int> z;
    220     for (int i = 0; i < n; i++) {
    221         if (d[i] == 0) z.push_back(i);
    222     }
    223 
    224     for (int i = 0; i < (int)z.size(); i++) {
    225         int x = z[i];
    226         int y = a[x];
    227         if (s[x]) {
    228             res.push_back(x);
    229             s[x] = !s[x];
    230             s[y] = !s[y];
    231         }
    232         d[y]--;
    233         if (d[y] == 0) {
    234             z.push_back(y);
    235         }
    236     }
    237 
    238     vector<bool> u(n);
    239     for (int i = 0; i < n; i++) {
    240         if (s[i] && !u[i]) {
    241             int x = i;
    242             vector<int> p;
    243             vector<bool> ps;
    244             int c = 0;
    245             while (!u[x]) {
    246                 p.push_back(x);
    247                 ps.push_back(s[x]);
    248                 c += s[x];
    249                 u[x] = true;
    250                 x = a[x];
    251             }
    252             int k = p.size();
    253             p.push_back(x);
    254             ps.push_back(s[x]);
    255             if (c % 2 == 1) {
    256                 cout << -1;
    257                 return;
    258             }
    259             vector<int> v1;
    260             vector<bool> ps1 = ps;
    261             for (int j = 0; j < k; j++) {
    262                 if (j == 0 || ps1[j]) {
    263                     v1.push_back(p[j]);
    264                     ps1[j] = !ps1[j];
    265                     ps1[j + 1] = !ps1[j + 1];
    266                 }
    267             }
    268             vector<int> v2;
    269             vector<bool> ps2 = ps;
    270             for (int j = 0; j < k; j++) {
    271                 if (j != 0 && ps2[j]) {
    272                     v2.push_back(p[j]);
    273                     ps2[j] = !ps2[j];
    274                     ps2[j + 1] = !ps2[j + 1];
    275                 }
    276             }
    277             if (v1.size() < v2.size()) {
    278                 for (auto x : v1) {
    279                     res.push_back(x);
    280                 }
    281             } else {
    282                 for (auto x : v2) {
    283                     res.push_back(x);
    284                 }
    285             }
    286         }
    287     }
    288     cout << res.size() << "\n";
    289     for (auto x : res) cout << x + 1 << " ";
    290 }
    291 
    292 int main() {
    293     int t;
    294     cin >> t;
    295     for(int _ = 0; _ < t; ++_){
    296         solve();
    297         cout << "\n";
    298     }
    299     return 0;
    300 }
    301 ```