1490.md (6265B)
1 Source: https://codeforces.com/blog/entry/87874 2 3 [1490A - Dense Array](/contest/1490/problem/A "Codeforces Round 702 (Div. 3)") 4 5 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 using ll = long long; 18 19 void solve() { 20 int n; 21 cin >> n; 22 int last; 23 cin >> last; 24 int ans = 0; 25 for (int i = 1; i < n; i++) { 26 int nw; 27 cin >> nw; 28 int a = min(last, nw), b = max(last, nw); 29 while (a * 2 < b) { 30 ans++; 31 a *= 2; 32 } 33 last = nw; 34 } 35 cout << ans << "\n"; 36 } 37 38 int main() { 39 int t; 40 cin >> t; 41 while (t--) { 42 solve(); 43 } 44 } 45 ``` 46 47 [1490B - Balanced Remainders](/contest/1490/problem/B "Codeforces Round 702 (Div. 3)") 48 49 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 50 51 **Editorial** 52 53 Tutorial is loading... 54 55 **Solution** 56 57 ``` 58 #include <bits/stdc++.h> 59 60 using namespace std; 61 62 void solve() { 63 int n; 64 cin >> n; 65 vector<int> a(n); 66 for (int &x : a) { 67 cin >> x; 68 } 69 70 int res = 0; 71 vector<int> cnt(3); 72 for (int x = 0; x <= 2; x++) { 73 for (int i = 0; i < n; i++) { 74 if (a[i] % 3 == x) { 75 cnt[x]++; 76 } 77 } 78 } 79 80 while (*min_element(cnt.begin(), cnt.end()) != n / 3) { 81 for (int i = 0; i < 3; i++) { 82 if (cnt[i] > n / 3) { 83 res++; 84 cnt[i]--; 85 cnt[(i + 1) % 3]++; 86 } 87 } 88 } 89 cout << res << endl; 90 } 91 92 int main() { 93 int t; 94 cin >> t; 95 while (t--) { 96 solve(); 97 } 98 } 99 ``` 100 101 [1490C - Sum of Cubes](/contest/1490/problem/C "Codeforces Round 702 (Div. 3)") 102 103 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 104 105 **Editorial** 106 107 Tutorial is loading... 108 109 **Solution** 110 111 ``` 112 #include <bits/stdc++.h> 113 114 using namespace std; 115 using ll = long long; 116 using ld = long double; 117 118 const ll N = 1'000'000'000'000L; 119 120 unordered_set<ll> cubes; 121 122 void precalc() { 123 for (ll i = 1; i * i * i <= N; i++) { 124 cubes.insert(i * i * i); 125 } 126 } 127 128 void solve() { 129 ll x; 130 cin >> x; 131 for (ll i = 1; i * i * i <= x; i++) { 132 if (cubes.count(x - i * i * i)) { 133 cout << "YES\n"; 134 return; 135 } 136 } 137 cout << "NO\n"; 138 } 139 140 int main() { 141 precalc(); 142 int t; 143 cin >> t; 144 while (t--) { 145 solve(); 146 } 147 } 148 ``` 149 150 [1490D - Permutation Transformation](/contest/1490/problem/D "Codeforces Round 702 (Div. 3)") 151 152 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 153 154 **Editorial** 155 156 Tutorial is loading... 157 158 **Solution** 159 160 ``` 161 #include <bits/stdc++.h> 162 163 using namespace std; 164 165 void build(int l, int r, vector<int> const &a, vector<int> &d, int curD = 0) { 166 if (r < l) { 167 return; 168 } 169 if (l == r) { 170 d[l] = curD; 171 return; 172 } 173 int m = l; 174 for (int i = l + 1; i <= r; i++) { 175 if (a[m] < a[i]) { 176 m = i; 177 } 178 } 179 d[m] = curD; 180 build(l, m - 1, a, d, curD + 1); 181 build(m + 1, r, a, d, curD + 1); 182 } 183 184 void solve() { 185 int n; 186 cin >> n; 187 vector<int> a(n); 188 for (int &x : a) { 189 cin >> x; 190 } 191 vector<int> d(n); 192 build(0, n - 1, a, d); 193 for (int x :d) { 194 cout << x << " "; 195 } 196 cout << endl; 197 } 198 199 int main() { 200 int t; 201 cin >> t; 202 while (t--) { 203 solve(); 204 } 205 } 206 ``` 207 208 [1490E - Accidental Victory](/contest/1490/problem/E "Codeforces Round 702 (Div. 3)") 209 210 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 211 212 **Editorial** 213 214 Tutorial is loading... 215 216 **Solution** 217 218 ``` 219 def win(pos : int, a : list): 220 power = a[pos] 221 for i in range(len(a)): 222 if i == pos: 223 continue 224 if power < a[i]: 225 return False 226 power += a[i] 227 return True 228 229 t = int(input()) 230 231 while t > 0: 232 t -= 1 233 n = int(input()) 234 a = list(map(int, input().split(' '))) 235 b = a.copy() 236 a.sort() 237 238 l = -1 239 r = n - 1 240 while r - l > 1: 241 m = (l + r) // 2 242 if (win(m, a)): 243 r = m 244 else: 245 l = m 246 247 winIds = [] 248 for i in range(n): 249 if b[i] >= a[r]: 250 winIds.append(i + 1) 251 252 print(len(winIds)) 253 print(*winIds) 254 ``` 255 256 [1490F - Equalize the Array](/contest/1490/problem/F "Codeforces Round 702 (Div. 3)") 257 258 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 259 260 **Editorial** 261 262 Tutorial is loading... 263 264 **Solution** 265 266 ``` 267 #include <bits/stdc++.h> 268 using namespace std; 269 270 void solve() { 271 int n; 272 cin >> n; 273 map<int, int> cnt; 274 for (int i = 0; i < n; i++) { 275 int x; 276 cin >> x; 277 cnt[x]++; 278 } 279 map<int, int> groupedByCnt; 280 for (auto[x, y] : cnt) { 281 groupedByCnt[y]++; 282 } 283 284 int res = n; 285 int left = 0, right = n, rightCnt = (int) cnt.size(); 286 for (auto[x, y] : groupedByCnt) { 287 res = min(res, left + right - rightCnt * x); 288 left += x * y; 289 right -= x * y; 290 rightCnt -= y; 291 } 292 cout << res << endl; 293 } 294 295 int main() { 296 int tests; 297 cin >> tests; 298 while (tests-- > 0) { 299 solve(); 300 } 301 return 0; 302 } 303 ``` 304 305 [1490G - Old Floppy Drive](/contest/1490/problem/G "Codeforces Round 702 (Div. 3)") 306 307 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [sodafago](/profile/sodafago "Specialist sodafago") 308 309 **Editorial** 310 311 Tutorial is loading... 312 313 **Solution** 314 315 ``` 316 #include <bits/stdc++.h> 317 318 using namespace std; 319 using ll = long long; 320 321 void solve() { 322 int n, m; 323 cin >> n >> m; 324 vector<ll> a(n); 325 ll allSum = 0; 326 vector<ll> pref; 327 vector<int> ind; 328 int curInd = 0; 329 for (ll &e : a) { 330 cin >> e; 331 allSum += e; 332 if (pref.empty() || allSum > pref.back()) { 333 pref.push_back(allSum); 334 ind.push_back(curInd); 335 } 336 curInd++; 337 } 338 for (int q = 0; q < m; q++) { 339 ll x; 340 cin >> x; 341 if (pref.back() < x && allSum <= 0) { 342 cout << -1 << " "; 343 continue; 344 } 345 ll needTimes = 0; 346 if (pref.back() < x) { 347 needTimes = (x - pref.back() + allSum - 1) / allSum; 348 } 349 x -= needTimes * allSum; 350 cout << needTimes * n + ind[lower_bound(pref.begin(), pref.end(), x) - pref.begin()] << " "; 351 } 352 cout << "\n"; 353 } 354 355 int main() { 356 int t; 357 cin >> t; 358 while (t--) { 359 solve(); 360 } 361 } 362 ```