codeforces-scrape

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

1003.md (6623B)


      1 Source: https://codeforces.com/blog/entry/60417
      2 
      3 [1003A - Polycarp's Pockets](/contest/1003/problem/A "Codeforces Round 494 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int n;
     23 	cin >> n;
     24 	
     25 	vector<int> cnt(101);
     26 	for (int i = 0; i < n; ++i) {
     27 		int x;
     28 		cin >> x;
     29 		++cnt[x];
     30 	}
     31 	
     32 	cout << *max_element(cnt.begin(), cnt.end()) << endl;
     33 	
     34 	return 0;
     35 }
     36 ```
     37 
     38 [1003B - Binary String Constructing](/contest/1003/problem/B "Codeforces Round 494 (Div. 3)")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (Vovuh)**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 int main() {
     52 #ifdef _DEBUG
     53 	freopen("input.txt", "r", stdin);
     54 //	freopen("output.txt", "w", stdout);
     55 #endif
     56 	
     57 	int a, b, x;
     58 	cin >> a >> b >> x;
     59 	
     60 	if (x % 2 == 0) {
     61 		if (a > b) {
     62 			for (int i = 0; i < x / 2; ++i)
     63 				cout << "01";
     64 			cout << string(b - x / 2, '1');
     65 			cout << string(a - x / 2, '0');
     66 		} else {
     67 			for (int i = 0; i < x / 2; ++i)
     68 				cout << "10";
     69 			cout << string(a - x / 2, '0');
     70 			cout << string(b - x / 2, '1');
     71 		}
     72 	} else if (a > b) {
     73 		for (int i = 0; i < x / 2; ++i)
     74 			cout << "01";
     75 		cout << string(a - x / 2, '0');
     76 		cout << string(b - x / 2, '1');
     77 	} else {
     78 		for (int i = 0; i < x / 2; ++i)
     79 			cout << "10";
     80 		cout << string(b - x / 2, '1');
     81 		cout << string(a - x / 2, '0');
     82 	}
     83 	cout << endl;
     84 	
     85 	return 0;
     86 }
     87 ```
     88 
     89 [1003C - Intense Heat](/contest/1003/problem/C "Codeforces Round 494 (Div. 3)")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution (PikMike)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 
    100 using namespace std;
    101 
    102 #define x first
    103 #define y second
    104 #define mp make_pair
    105 #define pb push_back
    106 #define sqr(a) ((a) * (a))
    107 #define sz(a) int(a.size())
    108 #define all(a) a.begin(), a.end()
    109 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    110 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    111 
    112 typedef long long li;
    113 typedef long double ld;
    114 typedef pair<int, int> pt;
    115 
    116 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    117 	return out << "(" << a.x << ", " << a.y << ")";
    118 }
    119 
    120 template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    121 	out << "[";
    122 	forn(i, sz(v)) {
    123 		if(i) out << ", ";
    124 		out << v[i];
    125 	}
    126 	return out << "]";
    127 }
    128 
    129 mt19937 rnd(time(NULL));
    130 
    131 const int INF = int(2e9);
    132 const li INF64 = li(1e18);
    133 const int MOD = INF + 7;
    134 const ld EPS = 1e-9;
    135 const ld PI = acos(-1.0);
    136 
    137 const int N = 10000 + 7;
    138 
    139 int n, k;
    140 int a[N];
    141 
    142 bool read () {
    143 	if (scanf("%d%d", &n, &k) != 2)
    144 		return false;
    145 	forn(i, n) scanf("%d", &a[i]);
    146 	return true;
    147 }
    148 
    149 int pr[N];
    150 
    151 void solve() {
    152 	pr[0] = 0;
    153 	forn(i, n) pr[i + 1] = pr[i] + a[i];
    154 	
    155 	ld ans = 0;
    156 	forn(r, n) forn(l, r + 1){
    157 		if (r - l + 1 >= k){
    158 			ans = max(ans, (pr[r + 1] - pr[l]) / ld(r - l + 1));
    159 		}
    160 	}
    161 	
    162 	printf("%.15f\n", double(ans));
    163 }
    164 
    165 int main() {
    166 #ifdef _DEBUG
    167 	freopen("input.txt", "r", stdin);
    168 //	freopen("output.txt", "w", stdout);
    169 	
    170 	int tt = clock();
    171 	
    172 #endif
    173 	
    174 	cerr.precision(15);
    175 	cout.precision(15);
    176 	cerr << fixed;
    177 	cout << fixed;
    178 
    179 	while(read()) {	
    180 		solve();
    181 		
    182 #ifdef _DEBUG
    183 	cerr << "TIME = " << clock() - tt << endl;
    184 	tt = clock();
    185 #endif
    186 
    187 	}
    188 }
    189 ```
    190 
    191 [1003D - Coins and Queries](/contest/1003/problem/D "Codeforces Round 494 (Div. 3)")
    192 
    193 **Tutorial**
    194 
    195 Tutorial is loading...
    196 
    197 **Solution (Vovuh)**
    198 
    199 ```
    200 #include <bits/stdc++.h>
    201 
    202 using namespace std;
    203 
    204 int main() {
    205 #ifdef _DEBUG
    206 	freopen("input.txt", "r", stdin);
    207 //	freopen("output.txt", "w", stdout);
    208 #endif
    209 	
    210 	int n, q;
    211 	cin >> n >> q;
    212 	
    213 	vector<int> cnt(31);
    214 	for (int i = 0; i < n; ++i) {
    215 		int x;
    216 		cin >> x;
    217 		++cnt[__builtin_ctz(x)];
    218 	}
    219 	
    220 	while (q--) {
    221 		int x;
    222 		cin >> x;
    223 		
    224 		int ans = 0;
    225 		for (int i = 30; i >= 0 && x > 0; --i) {
    226 			int need = min(x >> i, cnt[i]);
    227 			ans += need;
    228 			x -= (1 << i) * need;
    229 		}
    230 		
    231 		if (x > 0)
    232 			ans = -1;
    233 		cout << ans << endl;
    234 	}
    235 	
    236 	return 0;
    237 }
    238 ```
    239 
    240 [1003E - Tree Constructing](/contest/1003/problem/E "Codeforces Round 494 (Div. 3)")
    241 
    242 **Tutorial**
    243 
    244 Tutorial is loading...
    245 
    246 **Solution (Vovuh)**
    247 
    248 ```
    249 #include <bits/stdc++.h>
    250 
    251 using namespace std;
    252 
    253 int main() {
    254 #ifdef _DEBUG
    255 	freopen("input.txt", "r", stdin);
    256 //	freopen("output.txt", "w", stdout);
    257 #endif
    258 	
    259 	int n, d, k;
    260 	cin >> n >> d >> k;
    261 	
    262 	if (d >= n) {
    263 		cout << "NO" << endl;
    264 		return 0;
    265 	}
    266 	
    267 	vector<int> deg(n);
    268 	vector<pair<int, int>> ans;
    269 	set<pair<int, int>> q;
    270 	
    271 	for (int i = 0; i < d; ++i) {
    272 		++deg[i];
    273 		++deg[i + 1];
    274 		if (deg[i] > k || deg[i + 1] > k) {
    275 			cout << "NO" << endl;
    276 			return 0;
    277 		}
    278 		ans.push_back(make_pair(i, i + 1));
    279 	}
    280 	for (int i = 1; i < d; ++i)
    281 		q.insert(make_pair(max(i, d - i), i));
    282 	
    283 	for (int i = d + 1; i < n; ++i) {
    284 		while (!q.empty() && deg[q.begin()->second] == k)
    285 			q.erase(q.begin());
    286 		if (q.empty() || q.begin()->first == d) {
    287 			cout << "NO" << endl;
    288 			return 0;
    289 		}
    290 		++deg[i];
    291 		++deg[q.begin()->second];
    292 		ans.push_back(make_pair(i, q.begin()->second));
    293 		q.insert(make_pair(q.begin()->first + 1, i));
    294 	}
    295 	
    296 	assert(int(ans.size()) == n - 1);
    297 	cout << "YES" << endl;
    298 	vector<int> p(n);
    299 	for (int i = 0; i < n; i++)
    300 	    p[i] = i;
    301 	random_shuffle(p.begin(), p.end());
    302 	for (int i = 0; i < n - 1; ++i)
    303 	    if (rand() % 2)
    304 		    cout << p[ans[i].first] + 1 << " " << p[ans[i].second] + 1 << endl;
    305 		else
    306 		    cout << p[ans[i].second] + 1 << " " << p[ans[i].first] + 1 << endl;
    307 	
    308 	return 0;
    309 }
    310 ```
    311 
    312 [1003F - Abbreviation](/contest/1003/problem/F "Codeforces Round 494 (Div. 3)")
    313 
    314 **Tutorial**
    315 
    316 Tutorial is loading...
    317 
    318 **Solution (Vovuh)**
    319 
    320 ```
    321 #include <bits/stdc++.h>
    322 
    323 using namespace std;
    324 
    325 const int N = 303;
    326 
    327 int n;
    328 bool eq[N][N];
    329 int dp[N][N];
    330 string s[N];
    331 
    332 int main() {
    333 #ifdef _DEBUG
    334 	freopen("input.txt", "r", stdin);
    335 //	freopen("output.txt", "w", stdout);
    336 #endif
    337 
    338 	cin >> n;
    339 	int allsum = n - 1;
    340 	for (int i = 0; i < n; ++i) {
    341 		cin >> s[i];
    342 		allsum += s[i].size();
    343 	}
    344 	
    345 	for (int i = 0; i < n; ++i) {
    346 		eq[i][i] = true;
    347 		for (int j = 0; j < i; ++j) {
    348 			eq[i][j] = eq[j][i] = s[i] == s[j];
    349 		}
    350 	}
    351 	
    352 	for (int i = n - 1; i >= 0; --i) {
    353 		for (int j = n - 1; j >= 0; --j) {
    354 			if (eq[i][j]) {
    355 				if (i + 1 < n && j + 1 < n)
    356 					dp[i][j] = dp[i + 1][j + 1] + 1;
    357 				else
    358 					dp[i][j] = 1;
    359 			}
    360 		}
    361 	}
    362 	
    363 	int ans = allsum;
    364 	for (int i = 0; i < n; ++i) {
    365 		int sum = 0;
    366 		for (int j = 0; i + j < n; ++j) {
    367 			sum += s[i + j].size();
    368 			int cnt = 1;
    369 			for (int pos = i + j + 1; pos < n; ++pos) {
    370 				if (dp[i][pos] > j) {
    371 					++cnt;
    372 					pos += j;
    373 				}
    374 			}
    375 			int cur = allsum - sum * cnt + (j + 1) * cnt - j * cnt;
    376 			if (cnt > 1 && ans > cur) {
    377 				ans = cur;
    378 			}
    379 		}
    380 	}
    381 	
    382 	cout << ans << endl;
    383 	
    384 	return 0;
    385 }
    386 ```