codeforces-scrape

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

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