1041.md (5361B)
1 Source: https://codeforces.com/blog/entry/61876 2 3 [1041A - Кража в магазине](/contest/1041/problem/A "Codeforces Round 509 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int main(){ 16 ios_base::sync_with_stdio(0); 17 cin.tie(0); 18 cout.tie(0); 19 int n; 20 cin >> n; 21 int mn = 1e9, mx = 0; 22 for (int i = 1; i <= n; i++){ 23 int x; 24 cin >> x; 25 mn = min(mn, x); 26 mx = max(mx, x); 27 } 28 cout << max(0, (mx-mn)-n+1); 29 } 30 ``` 31 32 [1041B - Покупка телевизора](/contest/1041/problem/B "Codeforces Round 509 (Div. 2)") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution** 39 40 ``` 41 #include <bits/stdc++.h> 42 using namespace std; 43 typedef long long ll; 44 45 int main(){ 46 ios_base::sync_with_stdio(0); 47 cin.tie(0); 48 cout.tie(0); 49 50 ll a, b, c, d; 51 cin >> a >> b >> c >> d; 52 ll gc = __gcd(c, d); 53 c /= gc; 54 d /= gc; 55 cout << min(a/c, b/d); 56 } 57 ``` 58 59 [1041C - Перерывы на кофе](/contest/1041/problem/C "Codeforces Round 509 (Div. 2)") 60 61 **Tutorial** 62 63 Tutorial is loading... 64 65 **Solution** 66 67 ``` 68 #include <bits/stdc++.h> 69 using namespace std; 70 71 const int N = 200100; 72 73 set<pair<int, int> > q; 74 75 int ans[N], n, a[N], m, k; 76 77 int main(){ 78 ios_base::sync_with_stdio(0); 79 cin.tie(0); 80 cout.tie(0); 81 82 cin >> n >> m >> k; 83 for (int i = 1; i <= n; i++){ 84 cin >> a[i]; 85 q.insert({a[i], i}); 86 } 87 int cnt = 0; 88 while(!q.empty()){ 89 ++cnt; 90 int pos = q.begin()->second; 91 ans[pos] = cnt; 92 q.erase(q.begin()); 93 while(true){ 94 auto it = q.lower_bound({a[pos]+1+k, 0}); 95 if (it == q.end()) 96 break; 97 pos = it->second; 98 q.erase(it); 99 ans[pos] = cnt; 100 } 101 } 102 cout << cnt << "\n"; 103 for (int i = 1; i <= n; i++) 104 cout << ans[i] << ' '; 105 } 106 ``` 107 108 [1041D - Планерист](/contest/1041/problem/D "Codeforces Round 509 (Div. 2)") 109 110 **Tutorial** 111 112 Tutorial is loading... 113 114 **Solution** 115 116 ``` 117 #include<bits/stdc++.h> 118 119 using namespace std; 120 121 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 122 123 #define x first 124 #define y second 125 126 typedef long long li; 127 typedef long double ld; 128 typedef pair<int, int> pt; 129 130 const int INF = int(1e9); 131 const li INF64 = li(1e18); 132 const ld EPS = 1e-9; 133 134 const int N = 200 * 1000 + 555; 135 136 int n, h; 137 pt a[N]; 138 139 inline bool read() { 140 if(!(cin >> n >> h)) 141 return false; 142 fore(i, 0, n) 143 assert(scanf("%d%d", &a[i].x, &a[i].y) == 2); 144 sort(a, a + n); 145 return true; 146 } 147 148 int ps[N]; 149 150 int getH(int lf, int rg) { 151 int l = int(lower_bound(a, a + n, pt(lf, -1)) - a); 152 int r = int(lower_bound(a, a + n, pt(rg, -1)) - a); 153 154 int sum = ps[r] - ps[l]; 155 if(l > 0) 156 sum += max(0, a[l - 1].y - lf); 157 158 assert(rg - lf - sum >= 0); 159 return rg - lf - sum; 160 } 161 162 inline void solve() { 163 ps[0] = 0; 164 fore(i, 0, n) 165 ps[i + 1] = ps[i] + (a[i].y - a[i].x); 166 167 int ans = 0; 168 fore(i, 0, n) { 169 int lx = a[i].y + 1; 170 171 int lf = -(h + 1), rg = lx; 172 while(rg - lf > 1) { 173 int mid = (lf + rg) / 2; 174 if(getH(mid, lx) > h) 175 lf = mid; 176 else 177 rg = mid; 178 } 179 assert(getH(rg, lx) == h); 180 ans = max(ans, lx - rg); 181 } 182 cout << ans << endl; 183 } 184 185 int main() { 186 if(read()) { 187 solve(); 188 } 189 return 0; 190 } 191 ``` 192 193 [1041E - Восстановление дерева](/contest/1041/problem/E "Codeforces Round 509 (Div. 2)") 194 195 **Tutorial** 196 197 Tutorial is loading... 198 199 **Solution** 200 201 ``` 202 #include<bits/stdc++.h> 203 204 using namespace std; 205 206 const int N = 200043; 207 208 int cnt[N]; 209 210 int main() 211 { 212 int n; 213 scanf("%d", &n); 214 for(int i = 0; i < n - 1; i++) 215 { 216 int x, y; 217 scanf("%d %d", &x, &y); 218 if(y != n) 219 { 220 puts("NO"); 221 return 0; 222 } 223 cnt[x]++; 224 } 225 int cur = 0; 226 for(int i = 1; i < n; i++) 227 { 228 cur += cnt[i]; 229 if(cur > i) 230 { 231 puts("NO"); 232 return 0; 233 } 234 } 235 int last = -1; 236 puts("YES"); 237 set<int> unused; 238 for(int i = 1; i < n; i++) 239 unused.insert(i); 240 for(int i = 1; i < n; i++) 241 { 242 if(cnt[i] > 0) 243 { 244 unused.erase(i); 245 if(last != -1) 246 printf("%d %d\n", last, i); 247 last = i; 248 cnt[i]--; 249 } 250 while(cnt[i] > 0) 251 { 252 printf("%d %d\n", last, *unused.begin()); 253 last = *unused.begin(); 254 cnt[i]--; 255 unused.erase(unused.begin()); 256 } 257 } 258 printf("%d %d\n", last, n); 259 } 260 ``` 261 262 [1041F - Луч в трубе](/contest/1041/problem/F "Codeforces Round 509 (Div. 2)") 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution** 269 270 ``` 271 #include<bits/stdc++.h> 272 273 using namespace std; 274 275 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 276 277 #define sz(a) int((a).size()) 278 #define all(a) (a).begin(), (a).end() 279 280 typedef long long li; 281 typedef long double ld; 282 typedef pair<int, int> pt; 283 284 const int INF = int(1e9); 285 const li INF64 = li(1e18); 286 const ld EPS = 1e-9; 287 288 const int N = 100 * 1000 + 555; 289 290 int n[2], y[2]; 291 int x[2][N]; 292 293 inline bool read() { 294 fore(k, 0, 2) { 295 if(!(cin >> n[k] >> y[k])) 296 return false; 297 fore(i, 0, n[k]) 298 assert(scanf("%d", &x[k][i]) == 1); 299 } 300 return true; 301 } 302 303 inline void solve() { 304 int ans = 2; 305 for(int dx = 1; dx < int(1e9); dx *= 2) { 306 int mod = 2 * dx; 307 map<int, int> cnt; 308 309 int add[2] = {0, dx}; 310 fore(k, 0, 2) { 311 fore(i, 0, n[k]) 312 cnt[(x[k][i] + add[k]) & (mod - 1)]++; 313 } 314 315 for(auto curAns : cnt) 316 ans = max(ans, curAns.second); 317 } 318 cout << ans << endl; 319 } 320 321 int main() { 322 if(read()) { 323 solve(); 324 } 325 return 0; 326 } 327 ```