codeforces-scrape

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

1772.md (6727B)


      1 Source: https://codeforces.com/blog/entry/110313
      2 
      3 [1772A - A+B?](/contest/1772/problem/A "Codeforces Round 839 (Div. 3)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     print(eval(input()))
     17 ```
     18 
     19 [1772B - Matrix Rotation](/contest/1772/problem/B "Codeforces Round 839 (Div. 3)")
     20 
     21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (BledDest)**
     28 
     29 ```
     30 #include<bits/stdc++.h>
     31 
     32 using namespace std;
     33 
     34 int main()
     35 {
     36     int t;
     37     cin >> t;
     38     for(int _ = 0; _ < t; _++)
     39     {
     40         vector<int> a(4);
     41         for(int i = 0; i < 4; i++)
     42             cin >> a[i];
     43         int maxpos = max_element(a.begin(), a.end()) - a.begin();
     44         int minpos = min_element(a.begin(), a.end()) - a.begin();
     45         if(maxpos + minpos == 3)
     46             puts("YES");
     47         else
     48             puts("NO");
     49     }
     50 }
     51 ```
     52 
     53 [1772C - Different Differences](/contest/1772/problem/C "Codeforces Round 839 (Div. 3)")
     54 
     55 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (BledDest)**
     62 
     63 ```
     64 def construct(f, k):
     65     return [(i + 2 if i < f - 1 else 1) for i in range(k)]
     66 
     67 t = int(input())
     68 for i in range(t):
     69     k, n = map(int, input().split())
     70     ans = 1
     71     for f in range(1, k):
     72         d = construct(f, k - 1)
     73         if sum(d) <= n - 1:
     74             ans = f
     75     res = [1]
     76     d = construct(ans, k - 1)
     77     for x in d:
     78         res.append(res[-1] + x)
     79     print(*res)
     80 ```
     81 
     82 [1772D - Absolute Sorting](/contest/1772/problem/D "Codeforces Round 839 (Div. 3)")
     83 
     84 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution (BledDest)**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94  
     95 using namespace std;
     96 
     97 int main()
     98 {
     99     int t;
    100     cin >> t;
    101     for(int i = 0; i < t; i++)
    102     {
    103         int n;
    104         cin >> n;
    105         vector<int> a(n);
    106         for(int j = 0; j < n; j++)
    107             cin >> a[j];
    108         int mn = 0, mx = int(1e9);
    109         for(int j = 0; j + 1 < n; j++)
    110         {
    111             int x = a[j];
    112             int y = a[j + 1];
    113             int midL = (x + y) / 2;
    114             int midR = (x + y + 1) / 2;
    115             if(x < y)
    116                 mx = min(mx, midL);
    117             if(x > y)
    118                 mn = max(mn, midR);
    119         }
    120         if(mn <= mx) cout << mn << endl;
    121         else cout << -1 << endl;
    122     }
    123 }
    124 ```
    125 
    126 [1772E - Permutation Game](/contest/1772/problem/E "Codeforces Round 839 (Div. 3)")
    127 
    128 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    129 
    130 **Tutorial**
    131 
    132 Tutorial is loading...
    133 
    134 **Solution (Neon)**
    135 
    136 ```
    137 for tc in range(int(input())):
    138   n = int(input())
    139   p = list(map(int, input().split()))
    140   a, b, c = 0, 0, 0
    141   for i in range(n):
    142     if p[i] != i + 1 and p[i] != n - i:
    143       c += 1
    144     elif p[i] != i + 1:
    145       a += 1
    146     elif p[i] != n - i:
    147       b += 1
    148   if a + c <= b:
    149     print("First")
    150   elif b + c < a:
    151     print("Second")
    152   else:
    153     print("Tie")
    154 ```
    155 
    156 [1772F - Copy of a Copy of a Copy](/contest/1772/problem/F "Codeforces Round 839 (Div. 3)")
    157 
    158 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution (awoo)**
    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 struct op{
    174     int t, x, y, i;
    175 };
    176 
    177 int dx[] = {-1, 0, 1, 0};
    178 int dy[] = {0, 1, 0, -1};
    179 
    180 int main(){
    181     int n, m, k;
    182     cin >> n >> m >> k;
    183     vector<vector<string>> a(k + 1, vector<string>(n));
    184     forn(z, k + 1) forn(i, n)
    185         cin >> a[z][i];
    186     
    187     vector<int> cnt(k + 1);
    188     forn(z, k + 1){
    189         for (int i = 1; i < n - 1; ++i){
    190             for (int j = 1; j < m - 1; ++j){
    191                 bool ok = true;
    192                 forn(t, 4)
    193                     ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]];
    194                 cnt[z] += ok;
    195             }
    196         }
    197     }
    198     
    199     vector<int> ord(k + 1);
    200     iota(ord.begin(), ord.end(), 0);
    201     sort(ord.begin(), ord.end(), [&cnt](int x, int y){
    202         return cnt[x] > cnt[y];
    203     });
    204     
    205     vector<op> ops;
    206     forn(z, k){
    207         forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){
    208             a[ord[z]][i][j] ^= '0' ^ '1';
    209             ops.push_back({1, i + 1, j + 1, -1});
    210         }
    211         ops.push_back({2, -1, -1, ord[z + 1] + 1});
    212     }
    213     
    214     cout << ord[0] + 1 << '\n';
    215     cout << ops.size() << '\n';
    216     for (auto it : ops){
    217         cout << it.t << " ";
    218         if (it.t == 1)
    219             cout << it.x << " " << it.y << '\n';
    220         else
    221             cout << it.i << '\n';
    222     }
    223 }
    224 ```
    225 
    226 [1772G - Gaining Rating](/contest/1772/problem/G "Codeforces Round 839 (Div. 3)")
    227 
    228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Solution (adedalic)**
    235 
    236 ```
    237 #include<bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    242 #define sz(a) int((a).size())
    243 
    244 typedef long long li;
    245 
    246 int n;
    247 li x, y;
    248 vector<li> a;
    249 
    250 inline bool read() {
    251     if(!(cin >> n >> x >> y))
    252         return false;
    253     a.resize(n);
    254     fore (i, 0, n)
    255         cin >> a[i];
    256     return true;
    257 }
    258 
    259 li ceil(li a, li b) {
    260     assert(a >= 0 && b >= 0);
    261     return (a + b - 1) / b;
    262 }
    263 
    264 inline void solve() {
    265     sort(a.begin(), a.end());
    266     
    267     vector<li> t(n), b(n);
    268     fore (i, 0, n) {
    269         if (i > 0 && b[i - 1] >= a[i]) {
    270             t[i] = t[i - 1];
    271             b[i] = b[i - 1] + 1;
    272         } else {
    273             t[i] = a[i] - i;
    274             b[i] = a[i] + 1;
    275         }
    276     }
    277     
    278     li ans = 0;
    279     while (x < y) {
    280         int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
    281         
    282         li p = pos, m = n - pos;
    283         if (x + p >= y) {
    284             cout << ans + (y - x) << endl;
    285             return;
    286         }
    287         if (p <= m) {
    288             cout << -1 << endl;
    289             return;
    290         }
    291         
    292         //1. x + k(p - m) + p >= y
    293         li k = ceil(y - x - p, p - m);
    294         if (pos < n) {
    295             //2. x + k(p - m) >= t[pos]
    296             k = min(k, ceil(t[pos] - x, p - m));
    297         }
    298         ans += k * n;
    299         //x + k(p - m) < y, since 1. and p >= p - m
    300         x += k * (p - m);
    301     }
    302     assert(false);
    303 }
    304 
    305 int main() {
    306 #ifdef _DEBUG
    307     freopen("input.txt", "r", stdin);
    308     int tt = clock();
    309 #endif
    310     ios_base::sync_with_stdio(false);
    311     cin.tie(0), cout.tie(0);
    312     cout << fixed << setprecision(15);
    313     
    314     int t; cin >> t;
    315     while (t--) {
    316         read();
    317         solve();
    318         
    319 #ifdef _DEBUG
    320         cerr << "TIME = " << clock() - tt << endl;
    321         tt = clock();
    322 #endif
    323     }
    324     return 0;
    325 }
    326 ```