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 ```