1759.md (6731B)
1 Source: https://codeforces.com/blog/entry/109254 2 3 [1759A - Yes-Yes?](/contest/1759/problem/A "Codeforces Round 834 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 full = 'Yes' * 18 15 t = int(input()) 16 for _ in range(t): 17 if full.find(input()) >= 0: 18 print('YES') 19 else: 20 print('NO') 21 ``` 22 23 [1759B - Lost Permutation](/contest/1759/problem/B "Codeforces Round 834 (Div. 3)") 24 25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution** 32 33 ``` 34 t = int(input()) 35 for _ in range(t): 36 n, s = map(int, input().split()) 37 a = [int(x) for x in input().split()] 38 s += sum(a) 39 sm = 0 40 cnt = 0 41 for i in range(1, s + 1): 42 if sm >= s: 43 break 44 sm += i 45 cnt = i 46 if sm != s or max(a) > cnt or cnt <= n: 47 print("NO"); 48 else: 49 print("YES") 50 ``` 51 52 [1759C - Thermostat](/contest/1759/problem/C "Codeforces Round 834 (Div. 3)") 53 54 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution** 61 62 ``` 63 def solve(): 64 l, r, x = map(int, input().split()) 65 a, b = map(int, input().split()) 66 if a == b: 67 return 0 68 if abs(a - b) >= x: 69 return 1 70 if r - max(a, b) >= x or min(a, b) - l >= x: 71 return 2 72 if r - b >= x and a - l >= x or r - a >= x and b - l >= x: 73 return 3 74 return -1 75 76 t = int(input()) 77 for _ in range(t): 78 print(solve()) 79 ``` 80 81 [1759D - Make It Round](/contest/1759/problem/D "Codeforces Round 834 (Div. 3)") 82 83 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution** 90 91 ``` 92 #include <bits/stdc++.h> 93 94 using namespace std; 95 96 #define forn(i, n) for (int i = 0; i < int(n); i++) 97 #define sz(v) (int)v.size() 98 #define all(v) v.begin(),v.end() 99 #define eb emplace_back 100 101 using ll = long long; 102 103 void solve() { 104 ll n,m; cin >> n >> m; 105 ll n0 = n; 106 int cnt2 = 0, cnt5 = 0; 107 ll k = 1; 108 while (n > 0 && n % 2 == 0) { 109 n /= 2; 110 cnt2++; 111 } 112 while (n > 0 && n % 5 == 0) { 113 n /= 5; 114 cnt5++; 115 } 116 while (cnt2 < cnt5 && k * 2 <= m) { 117 cnt2++; 118 k *= 2; 119 } 120 while (cnt5 < cnt2 && k * 5 <= m) { 121 cnt5++; 122 k *= 5; 123 } 124 while (k * 10 <= m) { 125 k *= 10; 126 } 127 if (k == 1) { 128 cout << n0 * m << endl; 129 } else { 130 k *= m / k; // 1 <= m/k < 10 131 cout << n0 * k << endl; 132 } 133 } 134 135 int main() { 136 int t; 137 cin >> t; 138 139 forn(tt, t) { 140 solve(); 141 } 142 } 143 ``` 144 145 [1759E - The Humanoid](/contest/1759/problem/E "Codeforces Round 834 (Div. 3)") 146 147 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution** 154 155 ``` 156 #include <bits/stdc++.h> 157 158 using namespace std; 159 160 const int MAXN = 200200; 161 162 int n; 163 int arr[MAXN]; 164 165 int solve(int i, long long h, int s2, int s3) { 166 if (i == n) return 0; 167 if (arr[i] < h) 168 return solve(i + 1, h + (arr[i] / 2), s2, s3) + 1; 169 int ans1 = (s2 ? solve(i, h * 2, s2 - 1, s3) : 0); 170 int ans2 = (s3 ? solve(i, h * 3, s2, s3 - 1) : 0); 171 return max(ans1, ans2); 172 } 173 174 int main() { 175 int t; cin >> t; 176 while(t--) { 177 long long h; cin >> n >> h; 178 for (int i = 0; i < n; ++i) 179 cin >> arr[i]; 180 sort(arr, arr + n); 181 cout << solve(0, h, 2, 1) << endl; 182 } 183 } 184 ``` 185 186 [1759F - All Possible Digits](/contest/1759/problem/F "Codeforces Round 834 (Div. 3)") 187 188 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 189 190 **Tutorial** 191 192 Tutorial is loading... 193 194 **Solution** 195 196 ``` 197 #pragma GCC optimize("Ofast") 198 199 #include <bits/stdc++.h> 200 201 using namespace std; 202 203 #include <ext/pb_ds/assoc_container.hpp> 204 205 using namespace __gnu_pbds; 206 207 typedef long long ll; 208 typedef long double ld; 209 typedef tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 210 211 int newDigit = -1; 212 213 bool check(set<int> digits, int l, int r, bool useNewDigit) { 214 for (int i = l; i <= r; ++i) { 215 if (useNewDigit && i == newDigit) { 216 continue; 217 } 218 if (!digits.count(i)) { 219 return false; 220 } 221 } 222 return true; 223 } 224 225 void solve() { 226 int n, p; 227 cin >> n >> p; 228 vector<int> a(n + 1); 229 set<int> digits; 230 for (int i = 1; i <= n; ++i) { 231 cin >> a[i]; 232 digits.insert(a[i]); 233 } 234 if (digits.size() == p) { 235 cout << "0\n"; 236 return; 237 } 238 for (int i = n - 1; i >= 0; --i) { 239 if (a[i] < p - 1) { 240 newDigit = a[i] + 1; 241 break; 242 } 243 } 244 int l = 0, r = p - 1; 245 int x = a[n]; 246 while (l < r) { 247 int m = (l + r) >> 1; 248 bool res = false; 249 if (x + m >= p) { 250 if (check(digits, x + m + 1 - p, x - 1, true)) { 251 res = true; 252 } 253 } else { 254 if (check(digits, 0, x - 1, false) && check(digits, x + m + 1, p - 1, false)) { 255 res = true; 256 } 257 } 258 if (res) { 259 r = m; 260 } else { 261 l = m + 1; 262 } 263 } 264 cout << l << '\n'; 265 } 266 267 bool multitest = true; 268 269 int main() { 270 ios_base::sync_with_stdio(0); 271 cin.tie(0); 272 cout.tie(0); 273 cout.precision(25); 274 size_t number_of_tests = 1; 275 if (multitest) { 276 cin >> number_of_tests; 277 } 278 for (size_t _ = 0; _ < number_of_tests; ++_) { 279 solve(); 280 } 281 return 0; 282 } 283 ``` 284 285 [1759G - Restore the Permutation](/contest/1759/problem/G "Codeforces Round 834 (Div. 3)") 286 287 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 288 289 **Tutorial** 290 291 Tutorial is loading... 292 293 **Solution** 294 295 ``` 296 #include "bits/stdc++.h" 297 using namespace std; 298 int n; 299 300 void solve(){ 301 cin >> n; 302 vector<int>b(n / 2), p(n); 303 vector<bool>isUsed(n + 1, false); 304 set<int>unused; 305 306 for(int i = 0; i < n / 2; i++){ 307 cin >> b[i]; 308 p[i * 2 + 1] = b[i]; 309 isUsed[b[i]] = true; 310 } 311 for(int i = 1; i <= n; i++){ 312 if(!isUsed[i]) unused.insert(i); 313 } 314 315 if(int(unused.size()) != n / 2){ 316 cout << "-1\n"; 317 return; 318 } 319 320 for(int i = n / 2 - 1; i >= 0; i--){ 321 auto k = unused.upper_bound(p[2 * i + 1]); 322 if(k == unused.begin()){ 323 cout << "-1\n"; 324 return; 325 } 326 327 k--; 328 329 if(*k < p[2 * i + 1]){ 330 p[2 * i] = *k; 331 unused.erase(k); 332 } 333 else{ 334 cout << "-1\n"; 335 return; 336 } 337 } 338 for(auto i : p) cout << i << ' '; 339 cout << endl; 340 } 341 342 int main(){ 343 ios_base::sync_with_stdio(false); 344 cin.tie(nullptr); 345 346 int t; 347 cin >> t; 348 while(t--){ 349 solve(); 350 } 351 352 } 353 ```