codeforces-scrape

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

1927.md (7381B)


      1 Source: https://codeforces.com/blog/entry/125597
      2 
      3 [1927A - Make it White](/contest/1927/problem/A "Codeforces Round 923 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 from collections import deque
     15  
     16 def solve():
     17     n = int(input())
     18     s = deque(input())
     19     while len(s) > 0 and s[0] == 'W':
     20         s.popleft()
     21     while len(s) > 0 and s[-1] == 'W':
     22         s.pop()
     23     print(len(s))
     24     
     25  
     26 for _ in range(int(input())):
     27     solve()
     28 ```
     29 
     30 [1927B - Following the String](/contest/1927/problem/B "Codeforces Round 923 (Div. 3)")
     31 
     32 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution**
     39 
     40 ```
     41 def solve():
     42     n = int(input())
     43     a = [int(x) for x in input().split()]
     44     cnt = [0] * 26
     45     s = ''
     46     for i in range(n):
     47         for j in range(26):
     48             if cnt[j] == a[i]:
     49                 cnt[j] += 1
     50                 s += chr(97 + j)
     51                 break
     52     print(s)
     53  
     54  
     55 for _ in range(int(input())):
     56     solve()
     57 ```
     58 
     59 [1927C - Choose the Different Ones!](/contest/1927/problem/C "Codeforces Round 923 (Div. 3)")
     60 
     61 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution**
     68 
     69 ```
     70 def solve():
     71     n, m, k = map(int, input().split())
     72     a = [int(x) for x in input().split()]
     73     b = [int(x) for x in input().split()]
     74     cnt = [0] * (k + 1)
     75     for e in a:
     76         if e <= k:
     77             cnt[e] |= 1
     78     for e in b:
     79         if e <= k:
     80             cnt[e] |= 2
     81     c = [0] * 4
     82     for e in cnt:
     83         c[e] += 1
     84     if c[1] > k // 2 or c[2] > k // 2 or c[1] + c[2] + c[3] != k:
     85         print("NO")
     86     else:
     87         print("YES")
     88  
     89  
     90 for _ in range(int(input())):
     91     solve()
     92 ```
     93 
     94 [1927D - Find the Different Ones!](/contest/1927/problem/D "Codeforces Round 923 (Div. 3)")
     95 
     96 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution**
    103 
    104 ```
    105 def solve():
    106     n = int(input())
    107     a = [int(x) for x in input().split()]
    108     p = [-1] * n
    109     for i in range(1, n):
    110         p[i] = p[i - 1]
    111         if a[i] != a[i - 1]:
    112             p[i] = i - 1
    113     for i in range(int(input())):
    114         l, r = map(int, input().split())
    115         l -= 1
    116         r -= 1
    117         if p[r] < l:
    118             print("-1 -1")
    119         else:
    120             print(p[r] + 1, r + 1)
    121     
    122     
    123 t = int(input())
    124 for _ in range(t):
    125     solve()
    126     if _ + 1 != t:
    127         print()
    128 ```
    129 
    130 [1927E - Klever Permutation](/contest/1927/problem/E "Codeforces Round 923 (Div. 3)")
    131 
    132 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution**
    139 
    140 ```
    141 def solve():
    142     n, k = map(int, input().split())
    143     l, r = 1, n
    144     ans = [0] * n
    145     for i in range(k):
    146         for j in range(i, n, k):
    147             if i % 2 == 0:
    148                 ans[j] = l
    149                 l += 1
    150             else:
    151                 ans[j] = r
    152                 r -= 1
    153     print(*ans)
    154     
    155     
    156 for _ in range(int(input())):
    157     solve()
    158 ```
    159 
    160 [1927F - Microcycle](/contest/1927/problem/F "Codeforces Round 923 (Div. 3)")
    161 
    162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    163 
    164 **Tutorial**
    165 
    166 Tutorial is loading...
    167 
    168 **Solution**
    169 
    170 ```
    171 #include <bits/stdc++.h>
    172  
    173 #define int long long
    174 #define pb emplace_back
    175 #define mp make_pair
    176 #define x first
    177 #define y second
    178 #define all(a) a.begin(), a.end()
    179 #define rall(a) a.rbegin(), a.rend()
    180  
    181 typedef long double ld;
    182 typedef long long ll;
    183  
    184 using namespace std;
    185  
    186 mt19937 rnd(time(nullptr));
    187  
    188 const ll inf = 1e18;
    189 const ll M = 998244353;
    190 const ld pi = atan2(0, -1);
    191 const ld eps = 1e-6;
    192  
    193 struct dsu{
    194     vector<int> p, lvl;
    195  
    196     dsu(int n){
    197         p.resize(n);
    198         iota(p.begin(), p.end(), 0);
    199         lvl.assign(n, 0);
    200     }
    201  
    202     int get(int i){
    203         if (p[i] == i) return i;
    204         return p[i] = get(p[i]);
    205     }
    206  
    207     bool unite(int a, int b){
    208         a = get(a);
    209         b = get(b);
    210         if(a == b) return false;
    211         if(lvl[a] < lvl[b]) swap(a, b);
    212         p[b] = a;
    213         if(lvl[a] == lvl[b]) lvl[a]++;
    214         return true;
    215     }
    216 };
    217  
    218 bool found;
    219 vector<int> ans, path;
    220  
    221 void dfs(int v, int p, vector<vector<int>> &g, int f){
    222     path.push_back(v);
    223     if(v == f){
    224         ans = path;
    225         found = true;
    226         return;
    227     }
    228     for(int u: g[v]){
    229         if(u != p) dfs(u, v, g, f);
    230         if (found) return;
    231     }
    232     path.pop_back();
    233 }
    234  
    235 void solve(int tc){
    236     int n, m;
    237     cin >> n >> m;
    238     vector<vector<int>> sl(n);
    239     vector<pair<int, pair<int, int>>> edges;
    240     for(int i = 0; i < m; ++i){
    241         int u, v, w;
    242         cin >> u >> v >> w;
    243         --u, --v;
    244         edges.push_back({w, {u, v}});
    245     }
    246     sort(rall(edges));
    247     dsu g(n);
    248     pair<int, int> fin;
    249     int best = INT_MAX;
    250     for(auto e: edges){
    251         if(!g.unite(e.y.x, e.y.y)){
    252             fin = e.y;
    253             best = e.x;
    254         }
    255         else{
    256             sl[e.y.x].push_back(e.y.y);
    257             sl[e.y.y].push_back(e.y.x);
    258         }
    259     }
    260     found = false;
    261     path.resize(0);
    262     dfs(fin.x, -1, sl, fin.y);
    263     cout << best <<  " " << ans.size() << "\n";
    264     for(int e: ans) cout << e + 1 << " ";
    265 }
    266  
    267 bool multi = true;
    268  
    269 signed main() {
    270     int t = 1;
    271     if (multi)cin >> t;
    272     for (int i = 1; i <= t; ++i) {
    273         solve(i);
    274         cout << "\n";
    275     }
    276     return 0;
    277 }
    278 ```
    279 
    280 [1927G - Paint Charges](/contest/1927/problem/G "Codeforces Round 923 (Div. 3)")
    281 
    282 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    283 
    284 **Tutorial**
    285 
    286 Tutorial is loading...
    287 
    288 **Solution**
    289 
    290 ```
    291 #include <bits/stdc++.h>
    292  
    293 using namespace std;
    294  
    295 #define forn(i, n) for (int i = 0; i < int(n); i++)
    296  
    297 int main() {
    298     int t;
    299     cin >> t;
    300     forn(tt, t) {
    301         int n;
    302         cin >> n;
    303         vector<int> a(n);
    304         forn(i, n)
    305             cin >> a[i];
    306  
    307         vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));
    308         d[0][0][0] = 0;
    309  
    310         forn(i, n)
    311             forn(j, n)
    312                 forn(k, n + 1)
    313                     if (d[i][j][k] < INT_MAX) {
    314                         int ai = a[i];
    315  
    316                         // Z
    317                         {
    318                             int ni = i + 1;
    319                             int nj = j > 0 ? j + 1 : (k == 0 ? 1 : 0);
    320                             int nk = max(0, k - 1);
    321                             d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k]);
    322                         }
    323  
    324                         // L
    325                         {
    326                             int ni = i + 1;
    327                             int nj = j > 0 ? j + 1 : 0;
    328                             if (nj <= ai)
    329                                 nj = 0;
    330                             int nk = max(0, k - 1);
    331                             d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
    332                         }
    333  
    334                         // R
    335                         {
    336                             int ni = i + 1;
    337                             int nj = j > 0 ? j + 1 : 0;
    338                             int nk = max(ai - 1, k - 1);
    339                             d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
    340                         }
    341                     }
    342  
    343         cout << *min_element(d[n][0].begin(), d[n][0].end()) << endl;
    344     }
    345 }
    346 ```