codeforces-scrape

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

1974.md (6223B)


      1 Source: https://codeforces.com/blog/entry/129686
      2 
      3 [1974A - Phone Desktop](/contest/1974/problem/A "Codeforces Round 946 (Div. 3)")
      4 
      5 Idea: [Aksenov239](/profile/Aksenov239 "Candidate Master Aksenov239")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 nt = int(input())
     15  
     16 for t in range(nt):
     17     line = input()
     18     x, y = [int(q) for q in line.split()]
     19     mm = (y + 1) // 2
     20     x -= (mm * 5 * 3 - y * 2 * 2)
     21     x = max(x, 0)
     22     mm += (x + 5 * 3 - 1) // (5 * 3)
     23     print(mm)
     24 ```
     25 
     26 [1974B - Symmetric Encoding](/contest/1974/problem/B "Codeforces Round 946 (Div. 3)")
     27 
     28 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution**
     35 
     36 ```
     37 def solve():
     38     n = int(input())
     39     b = input()
     40     cnt = [0] * 26
     41     for c in b:
     42         cnt[ord(c) - ord('a')] = 1
     43     tmp = ''
     44     for i in range(26):
     45         if cnt[i] > 0:
     46             tmp += chr(ord('a') + i)
     47     a = ''
     48     for c in b:
     49         a += tmp[-1 - tmp.find(c)]
     50     print(a)
     51     
     52  
     53 for _ in range(int(input())):
     54     solve()
     55 ```
     56 
     57 [1974C - Beautiful Triple Pairs](/contest/1974/problem/C "Codeforces Round 946 (Div. 3)")
     58 
     59 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     60 
     61 **Tutorial**
     62 
     63 Tutorial is loading...
     64 
     65 **Solution**
     66 
     67 ```
     68 def solve():
     69     n = int(input())
     70     a = [int(x) for x in input().split()]
     71     cnt = dict()
     72     ans = 0
     73     for i in range(n - 2):
     74         triplet = (a[i], a[i + 1], a[i + 2])
     75         mist = [0] * 3
     76         mist[0] = (0, a[i + 1], a[i + 2])
     77         mist[1] = (a[i], 0, a[i + 2])
     78         mist[2] = (a[i], a[i + 1], 0)
     79         for trip in mist:
     80             ans += cnt.get(trip, 0) - cnt.get(triplet, 0)
     81             cnt[trip] = cnt.get(trip, 0) + 1
     82         cnt[triplet] = cnt.get(triplet, 0) + 1
     83     print(ans)
     84     
     85     
     86 for i in range(int(input())):
     87     solve()
     88 ```
     89 
     90 [1974D - Ingenuity-2](/contest/1974/problem/D "Codeforces Round 946 (Div. 3)")
     91 
     92 Idea: [MaxBuzz](/profile/MaxBuzz "Master MaxBuzz")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution**
     99 
    100 ```
    101 inv = {'N':'S', 'S': 'N',
    102     'E': 'W', 'W': 'E'}
    103 
    104 def solve():
    105     n = int(input())
    106     s = input()
    107     x, y = 0, 0
    108     for c in s:
    109         if c == 'N':
    110             y += 1
    111         if c == 'S':
    112             y -= 1
    113         if c == 'E':
    114             x += 1
    115         if c == 'W':
    116             x -= 1
    117     if x % 2 == 1 or y % 2 == 1:
    118         print('NO')
    119         return
    120     ans = ['R'] * n
    121     if x == y == 0:
    122         if n == 2:
    123             print('NO')
    124             return
    125         ans[0] = ans[s.find(inv[s[0]])] = 'H'
    126     else:
    127         for i in range(n):
    128             if s[i] == 'N' and y > 0:
    129                 y -= 2
    130                 ans[i] = 'H'
    131             if s[i] == 'S' and y < 0:
    132                 y += 2
    133                 ans[i] = 'H'
    134             if s[i] == 'E' and x > 0:
    135                 x -= 2
    136                 ans[i] = 'H'
    137             if s[i] == 'W' and x < 0:
    138                 x += 2
    139                 ans[i] = 'H'
    140     print(*ans, sep='')
    141     
    142     
    143 for _ in range(int(input())):
    144     solve()
    145 ```
    146 
    147 [1974E - Money Buys Happiness](/contest/1974/problem/E "Codeforces Round 946 (Div. 3)")
    148 
    149 Idea: [RobinFromTheHood](/profile/RobinFromTheHood "Expert RobinFromTheHood")
    150 
    151 **Tutorial**
    152 
    153 Tutorial is loading...
    154 
    155 **Solution**
    156 
    157 ```
    158 T = int(input())
    159 big = float('inf')
    160 for _ in range(T):
    161     m, x = map(int, input().split())
    162     c = []
    163     h = []
    164     for i in range(m):
    165         ci, hi = map(int, input().split())
    166         c.append(ci)
    167         h.append(hi)
    168     mh = sum(h)
    169     dp = [0] + [big] * mh
    170     for i in range(m):
    171         for j in range(mh, h[i]-1, -1):
    172             if dp[j-h[i]] + c[i] <= i*x:
    173                 dp[j] = min(dp[j], dp[j-h[i]]+c[i])
    174     for i in range(mh, -1, -1):
    175         if dp[i] != big:
    176             print(i)
    177             break
    178 ```
    179 
    180 [1974F - Cutting Game](/contest/1974/problem/F "Codeforces Round 946 (Div. 3)")
    181 
    182 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    183 
    184 **Tutorial**
    185 
    186 Tutorial is loading...
    187 
    188 **Solution**
    189 
    190 ```
    191 def solve(tc):
    192     a, b, n, m = map(int, input().split())
    193     ver, hor = [], []
    194     for i in range(n):
    195         x, y = map(int, input().split())
    196         ver.append((x, y))
    197         hor.append((y, x))
    198     deleted = set()
    199     hor.sort()
    200     ver.sort()
    201     ans = [0, 0]
    202     u, d = 1, a
    203     l, r = 1, b
    204     hl, hr = 0, n - 1
    205     vl, vr = 0, n - 1
    206     for i in range(m):
    207         c, k = input().split()
    208         k = int(k)
    209         if c == 'U':
    210             u += k
    211             while vl <= vr and ver[vl][0] < u:
    212                 if ver[vl] not in deleted:
    213                     ans[i % 2] += 1
    214                     deleted.add(ver[vl])
    215                 vl += 1
    216         if c == 'D':
    217             d -= k
    218             while vl <= vr and ver[vr][0] > d:
    219                 if ver[vr] not in deleted:
    220                     ans[i % 2] += 1
    221                     deleted.add(ver[vr])
    222                 vr -= 1
    223         if c == 'L':
    224             l += k
    225             while hl <= hr and hor[hl][0] < l:
    226                 if (hor[hl][1], hor[hl][0]) not in deleted:
    227                     ans[i % 2] += 1
    228                     deleted.add((hor[hl][1], hor[hl][0]))
    229                 hl += 1
    230         if c == 'R':
    231             r -= k
    232             while hl <= hr and hor[hr][0] > r:
    233                 if (hor[hr][1], hor[hr][0]) not in deleted:
    234                     ans[i % 2] += 1
    235                     deleted.add((hor[hr][1], hor[hr][0]))
    236                 hr -= 1
    237     print(ans[0], ans[1])
    238 
    239 t = int(input())
    240 for i in range(1, t + 1):
    241     solve(i)
    242 ```
    243 
    244 [1974G - Money Buys Less Happiness Now](/contest/1974/problem/G "Codeforces Round 946 (Div. 3)")
    245 
    246 Idea: [RobinFromTheHood](/profile/RobinFromTheHood "Expert RobinFromTheHood"), [izban](/profile/izban "International Grandmaster izban"), [Aksenov239](/profile/Aksenov239 "Candidate Master Aksenov239")
    247 
    248 **Tutorial**
    249 
    250 Tutorial is loading...
    251 
    252 **Solution**
    253 
    254 ```
    255 from heapq import *
    256 for _ in range(int(input())):
    257     m, x = map(int, input().split())
    258     c = [int(x) for x in input().split()]
    259     budget = 0
    260     Q = []
    261     for i in c:
    262         if budget >= i:
    263             heappush(Q, -i)
    264             budget -= i
    265         elif Q and -Q[0] > i:
    266             budget += -heappop(Q)-i
    267             heappush(Q, -i)
    268         budget += x
    269     print(len(Q))
    270 ```