codeforces-scrape

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

1966.md (8302B)


      1 Source: https://codeforces.com/blog/entry/128914
      2 
      3 [1966A - Card Exchange](/contest/1966/problem/A "Codeforces Round 941 (Div. 2)")
      4 
      5 **Solution**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 t = int(input())
     13 
     14 for tc in range(t):
     15     n, k = map(int, input().split())
     16 
     17     cards = list(map(int, input().split()))
     18     ct = {}
     19 
     20     ans = n
     21 
     22     for c in cards:
     23         if c in ct:
     24             ct.update({c: ct[c] + 1})
     25         else:
     26             ct.update({c: 1})
     27         if ct[c] >= k:
     28             ans = k - 1
     29 
     30     print(ans)
     31 ```
     32 
     33 [1966B - Rectangle Filling](/contest/1966/problem/B "Codeforces Round 941 (Div. 2)")
     34 
     35 **Solution**
     36 
     37 Tutorial is loading...
     38 
     39 **Code**
     40 
     41 ```
     42 t = int(input())
     43 
     44 for tc in range(t):
     45     n, m = map(int, input().split())
     46     gr = []
     47 
     48     for i in range(n):
     49         gr.append(input())
     50 
     51     ans = "YES"
     52 
     53     if gr[0][0] != gr[n - 1][m - 1]:
     54 
     55         impossible = True
     56         for j in range(m - 1):
     57             if gr[0][j] != gr[0][j + 1] or gr[n - 1][j] != gr[n - 1][j + 1]:
     58                 impossible = False
     59 
     60         if impossible:
     61             ans = "NO"
     62 
     63         impossible = True
     64         for i in range(n - 1):
     65             if gr[i][0] != gr[i + 1][0] or gr[i][m - 1] != gr[i + 1][m - 1]:
     66                 impossible = False
     67 
     68         if impossible:
     69             ans = "NO"
     70 
     71     print(ans)
     72 ```
     73 
     74 [1965A - Everything Nim](/contest/1965/problem/A "Codeforces Round 941 (Div. 1)")
     75 
     76 **Solution**
     77 
     78 Tutorial is loading...
     79 
     80 **Code**
     81 
     82 ```
     83 t = int(input())
     84 
     85 for tc in range(t):
     86 
     87     n = int(input())
     88     a = list(map(int, input().split()))
     89 
     90     maxsize = max(a)
     91 
     92     a.sort()
     93     mexsize = 1
     94     for sz in a:
     95         if sz == mexsize:
     96             mexsize = mexsize + 1
     97 
     98     if mexsize > maxsize:
     99         print("Alice" if maxsize % 2 == 1 else "Bob")
    100     else:
    101         print("Alice" if mexsize % 2 == 1 else "Bob")
    102 ```
    103 
    104 [1965B - Missing Subsequence Sum](/contest/1965/problem/B "Codeforces Round 941 (Div. 1)")
    105 
    106 **Solution**
    107 
    108 Tutorial is loading...
    109 
    110 **Code**
    111 
    112 ```
    113 t = int(input())
    114 
    115 for tc in range(t):
    116     n, k = map(int, input().split())
    117 
    118     i = 0
    119     while (1 << (i + 1)) <= k:
    120         i = i + 1
    121 
    122     ans = [k - (1 << i), k + 1, k + 1 + (1 << i)]
    123 
    124     for j in range(20):
    125         if j != i:
    126             ans.append(1 << j);
    127 
    128     print(len(ans))
    129     print(*ans)
    130 ```
    131 
    132 [1965C - Folding Strip](/contest/1965/problem/C "Codeforces Round 941 (Div. 1)")
    133 
    134 **Solution**
    135 
    136 Tutorial is loading...
    137 
    138 **Code**
    139 
    140 ```
    141 t = int(input())
    142 
    143 for tc in range(t):
    144     n = int(input())
    145     s = input()
    146     mn = 0
    147     mx = 0
    148     cur = 0
    149 
    150     for c in s:
    151 
    152         if (cur % 2 == 0) == (c == '1'):
    153             cur = cur + 1
    154         else:
    155             cur = cur - 1
    156 
    157         mn = min(mn, cur)
    158         mx = max(mx, cur)
    159 
    160     print(mx - mn)
    161 ```
    162 
    163 [1965D - Missing Subarray Sum](/contest/1965/problem/D "Codeforces Round 941 (Div. 1)")
    164 
    165 **Solution**
    166 
    167 Tutorial is loading...
    168 
    169 **Code**
    170 
    171 ```
    172 def getSubarraySums(a):
    173 
    174     cts = []
    175     for i in range(len(a)):
    176         sm = 0
    177         for j in range(i, len(a)):
    178             sm = sm + a[j]
    179             cts.append(sm)
    180 
    181     cts.sort()
    182     return cts
    183 
    184 def getOddOccurringElements(cts):
    185 
    186     odds = []
    187 
    188     for ct in cts:
    189         if len(odds) > 0 and ct == odds[-1]:
    190             odds.pop()
    191         else:
    192             odds.append(ct)
    193     return odds
    194 
    195 def getPalindrome(odds, n):
    196 
    197     a = [0] * n
    198     prev = 0
    199     idx = (n - 1) // 2
    200     
    201     for x in odds:
    202         if idx == n - 1 - idx:
    203             a[idx] = x
    204         else:
    205             a[idx] = (x - prev) // 2
    206             a[n - 1 - idx] = (x - prev) // 2
    207         prev = x
    208         idx = idx - 1
    209     
    210     return a
    211 
    212 def getLargestExcluded(bigList, smallList):
    213 
    214     while len(smallList) > 0 and bigList[-1] == smallList[-1]:
    215         bigList.pop()
    216         smallList.pop()
    217     return bigList[-1]
    218 
    219 t = int(input())
    220 
    221 for tc in range(t):
    222 
    223     n = int(input())
    224     
    225     subarraySums = list(map(int, input().split()))
    226     subarraySums.sort()
    227     odds = getOddOccurringElements(subarraySums)
    228     
    229     missingSum = -1
    230     
    231     if len(odds) > (n + 1) // 2:
    232     
    233         oddvals = []
    234         evenvals = []
    235         for x in odds:
    236             if x % 2 == 1:
    237                 oddvals.append(x)
    238             else:
    239                 evenvals.append(x)
    240 
    241         if len(evenvals) > 0 and len(oddvals) > 0:
    242 
    243             missingSum = evenvals[0] if len(evenvals) == 1 else oddvals[0]
    244 
    245         else:
    246 
    247             b = getPalindrome(odds, n + 2)
    248             bSums = getSubarraySums(b)
    249             y = bSums[-1]
    250             x = getLargestExcluded(bSums, subarraySums)
    251             missingSum = 2 * x - y
    252     
    253     else:
    254         
    255         b = getPalindrome(odds, n - 2)
    256         bSums = getSubarraySums(b)
    257         y = bSums[-1]
    258         x = getLargestExcluded(subarraySums, bSums)
    259         missingSum = 2 * x - y
    260 
    261     odds.append(missingSum)
    262     odds.sort()
    263     odds = getOddOccurringElements(odds)
    264     
    265     ans = getPalindrome(odds, n)
    266     print(*ans)
    267 ```
    268 
    269 [1965E - Connected Cubes](/contest/1965/problem/E "Codeforces Round 941 (Div. 1)")
    270 
    271 **Solution**
    272 
    273 Tutorial is loading...
    274 
    275 **Code**
    276 
    277 ```
    278 n, m, k = map(int, input().split())
    279 a = []
    280 
    281 for i in range(n):
    282     a.append(list(map(int, input().split())))
    283 
    284 ans = []
    285 
    286 for x in range(n):
    287     for y in range(m):
    288         for z in range(1, n + 1):
    289             if y % 2 == 1:
    290                 ans.append([x, y, z, a[x][y]])
    291             else:
    292                 ans.append([x, y, z, a[min(x, n - z)][y]])
    293         for z in range(n + 1, n + k + 1):
    294             if y % 2 == 1:
    295                 ans.append([x, y, z, a[x][y]])
    296             else:
    297                 ans.append([x, y, z, z - n])
    298 
    299 for x in range(n, n + k):
    300     for y in range(m):
    301         for z in range(1, n + 1):
    302             if y % 2 == 1:
    303                 ans.append([x, y, z, x - n + 1])
    304             else:
    305                 ans.append([x, y, z, a[n - z][y]])
    306         ans.append([x, y, n + 1, x - n + 1])
    307 
    308 for y in range(m):
    309     for z in range(n + 2, n + k + 1):
    310         ans.append([n, y, z, z - n])
    311 
    312 for x in range(n + 1, n + k):
    313     for z in range(n + 2, n + k + 1):
    314         ans.append([x, 0, z, max(x - n + 1, z - n)])
    315 
    316 print(len(ans))
    317 
    318 for cube in ans:
    319     print(cube[0] + 1, cube[1] + 1, cube[2] + 1, cube[3])
    320 ```
    321 
    322 [1965F - Conference](/contest/1965/problem/F "Codeforces Round 941 (Div. 1)")
    323 
    324 **Solution**
    325 
    326 Tutorial is loading...
    327 
    328 **Code**
    329 
    330 ```
    331 /**
    332  *    author:  tourist
    333  *    created: 26.11.2023 09:36:38       
    334 **/
    335 #include <bits/stdc++.h>
    336  
    337 using namespace std;
    338  
    339 #ifdef LOCAL
    340 #include "algo/debug.h"
    341 #else
    342 #define debug(...) 42
    343 #endif
    344  
    345 const long long inf = (long long) 1e18;
    346  
    347 int main() {
    348   ios::sync_with_stdio(false);
    349   cin.tie(0);
    350   int n;
    351   cin >> n;
    352   vector<long long> l(n), r(n);
    353   for (int i = 0; i < n; i++) {
    354     cin >> l[i] >> r[i];
    355   }
    356   int original_n = n;
    357   for (int rot = 0; rot < 2; rot++) {
    358     // make all left ends distinct
    359     map<long long, vector<long long>> mp;
    360     for (int i = 0; i < n; i++) {
    361       mp[l[i]].push_back(r[i]);
    362     }
    363     vector<long long> new_l, new_r;
    364     auto it = mp.begin();
    365     multiset<long long> s;
    366     long long T = -inf;
    367     while (true) {
    368       if (s.empty()) {
    369         if (it == mp.end()) {
    370           break;
    371         }
    372         T = it->first;
    373       }
    374       while (it != mp.end() && T == it->first) {
    375         s.insert(it->second.begin(), it->second.end());
    376         ++it;
    377       }
    378       assert(!s.empty());
    379       new_l.push_back(T);
    380       new_r.push_back(*s.begin());
    381       s.erase(s.begin());
    382       T += 1;
    383       while (!s.empty() && *s.begin() < T) {
    384         s.erase(s.begin());
    385       }
    386     }
    387     swap(l, new_l);
    388     swap(r, new_r);
    389     n = (int) l.size();
    390     for (int i = 0; i < n; i++) {
    391       l[i] *= -1;
    392       r[i] *= -1;
    393       swap(l[i], r[i]);
    394     }
    395   }
    396   sort(l.begin(), l.end());
    397   sort(r.begin(), r.end());
    398   vector<long long> ans(original_n + 1);
    399   long long lx = -inf, rx = -inf;
    400   int pl = 0, pr = 0;
    401   int k = 0;
    402   while (pl < n || pr < n) {
    403     long long wait = min(pl < n ? l[pl] - lx : inf, pr < n ? r[pr] - rx : inf);
    404     ans[k] += wait;
    405     lx += wait;
    406     rx += wait;
    407     while (pl < n && l[pl] == lx) {
    408       k += 1;
    409       lx += 1;
    410       pl += 1;
    411     }
    412     while (pr < n && r[pr] == rx) {
    413       ans[k] += 1;
    414       k -= 1;
    415       rx += 1;
    416       pr += 1;
    417     }
    418   }
    419   for (int i = n; i > 1; i--) {
    420     ans[i - 1] += ans[i];
    421   }
    422   for (int i = 1; i <= original_n; i++) {
    423     cout << ans[i] << '\n';
    424   }
    425   return 0;
    426 }
    427 ```