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