989.md (9112B)
1 Source: https://codeforces.com/blog/entry/59968 2 3 Selamat petang! 4 5 The curtain has fallen on [Codeforces Round 487 (Div. 2)](/contest/989 "Codeforces Round 487 (Div. 2)"). Have you enjoyed the problems themselves? Or the stories? Or both? Neither? 6 7 I hadn't ever intended to create a hard contest, believe me... (╥﹏╥) The author will try to find ways to estimate the difficulty better in the future. Also, stronger pretests, notes taken. 8 9 Anyways, hope you've all enjoyed the challenges you've faced, and gained something from this round. Congratulations to those who performed well, and commiserations to those waiting for their next chance to shine (^_−)−☆ 10 11 Below are the tutorials of all problems. Feel free to point out mistakes (if any) or share your ideas in the comments! I might be overcomplicating or confusing something > < 12 13 Tutorial is loading... 14 15 **Short Ruby solution** 16 17 ``` 18 puts gets.codepoints.each_cons(3).any?{|x,y,z|x*y*z==287430}?'Yes':'No' 19 ``` 20 21 Tutorial is loading... 22 23 **Noam's C++ solution** 24 25 ``` 26 #include <bits/stdc++.h> 27 #define endl '\n' 28 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) 29 #define finish(x) return cout << x << endl, 0 30 using namespace std; 31 32 string s, t; 33 int n, p; 34 35 bool isperiod() { 36 for (int i = p; i < n; i++) 37 if (t[i] != t[i - p]) return false; 38 return true; 39 } 40 41 int main() { 42 fast; 43 cin >> n >> p >> s; 44 45 // attempt 1 46 t = s; 47 for (auto &i : t) 48 if (i == '.') i = '0'; 49 if (!isperiod()) finish(t); 50 51 // attempt 2 52 int i = 0; 53 while (i < n && s[i] != '.') i++; 54 if (i + p < n) { 55 t[i] = '1'; 56 finish(t); 57 } 58 i = n - 1; 59 while (i >= 0 && s[i] != '.') i--; 60 if (i - p >= 0) { 61 t[i] = '1'; 62 finish(t); 63 } 64 65 finish("No"); 66 } 67 ``` 68 69 **Python solution for the original problem as well as for the last challenge** 70 71 ``` 72 n, p = map(int, input().split()) 73 s = input() 74 75 t = s.replace('.', '0') 76 77 if all(t[i] == t[i + p] for i in range(n - p)): 78 rmost = -1 79 for r in range(p - 1, -1, -1): 80 x = s[r::p].rfind('.') 81 if x != -1 and s[r::p] != '.': 82 rmost = max(rmost, x * p + r) 83 if rmost == -1: 84 print('No') 85 else: 86 print(t[:rmost] + '1' + t[(rmost + 1):]) 87 else: 88 print(t) 89 ``` 90 91 **C++ seemingly-brute-force solution** 92 93 ``` 94 #include <algorithm> 95 #include <cstdio> 96 97 static const int MAXN = 2005; 98 99 static int n, p; 100 static char s[MAXN]; 101 102 static int dots_ct = 0, dots[MAXN]; 103 104 int main() 105 { 106 scanf("%d%d%s", &n, &p, s); 107 108 for (int i = 0; i < n; ++i) if (s[i] == '.') { 109 dots[dots_ct++] = i; 110 s[i] = '0'; 111 } 112 113 for (int i = 1; i <= (1 << std::min(dots_ct, 19)); ++i) { 114 bool is_period = true; 115 for (int j = 0; j < n - p; ++j) 116 if (s[j] != s[j + p]) { is_period = false; break; } 117 if (!is_period) { 118 puts(s); 119 return 0; 120 } 121 for (int j = 0; j <= __builtin_ctz(i); ++j) 122 s[dots[j]] ^= 1; 123 } 124 125 puts("No"); 126 return 0; 127 } 128 ``` 129 130 Tutorial is loading... 131 132 **Model solution** 133 134 ``` 135 #include <cstdio> 136 #include <cstdlib> 137 #include <algorithm> 138 #include <string> 139 #include <utility> 140 #include <vector> 141 142 static const int MAXM = 50; 143 144 int main() 145 { 146 srand(1); 147 148 int a[4]; 149 scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]); 150 151 int M = std::max(2, std::min(MAXM, *std::max_element(a, a + 4))); 152 std::vector<std::string> g; 153 154 for (int k = 0; k < 4; ++k) { 155 int islands = a[(k + 1) % 4] - 1; 156 std::string s(M, 'A' + k); 157 std::vector<std::pair<int, int>> pos; 158 159 g.push_back(s); 160 for (int x = 0; x < (islands + (M - 2)) / (M - 1); ++x) { 161 for (int i = 0; i < 3; ++i) g.push_back(s); 162 for (int i = (x & 1); i < M - !(x & 1); ++i) 163 pos.push_back({(int)g.size() - 2 - ((i ^ x) & 1), i}); 164 } 165 166 std::random_shuffle(pos.begin(), pos.end()); 167 for (int i = 0; i < islands; ++i) 168 g[pos[i].first][pos[i].second] = 'A' + (k + 1) % 4; 169 } 170 171 if (g.size() <= M) { 172 printf("%lu %d\n", g.size(), M); 173 for (int i = 0; i < g.size(); ++i) puts(g[i].c_str()); 174 } else { 175 printf("%d %lu\n", M, g.size()); 176 for (int i = 0; i < M; ++i) { 177 for (int j = 0; j < g.size(); ++j) putchar(g[j][i]); 178 putchar('\n'); 179 } 180 } 181 182 return 0; 183 } 184 ``` 185 186 Tutorial is loading... 187 188 **Model solution** 189 190 ``` 191 #include <cstdio> 192 #include <algorithm> 193 #include <vector> 194 195 static const int MAXN = 1e5 + 3; 196 static const int INF32 = 0x7fffffff; 197 typedef long long int64; 198 199 static int n, l, w; 200 static int x[MAXN], v[MAXN]; 201 static std::vector<int> pos, neg; 202 203 inline int div_floor(int64 a, int b) 204 { 205 if (b == 0) return (a > 0 ? +INF32 : -INF32); 206 if (a % b < 0) a -= (b + a % b); 207 return a / b; 208 } 209 210 int main() 211 { 212 scanf("%d%d%d", &n, &l, &w); 213 214 for (int i = 0; i < n; ++i) { 215 scanf("%d%d", &x[i], &v[i]); 216 (v[i] == +1 ? pos : neg).push_back(x[i]); 217 } 218 std::sort(pos.begin(), pos.end()); 219 std::sort(neg.begin(), neg.end()); 220 221 int64 ans = 0; 222 for (int v : neg) { 223 auto barrier = std::lower_bound(pos.begin(), pos.end(), -v - l); 224 int u_max_0 = div_floor((int64)(v + l) * (w + 1) - 1, w - 1), 225 u_max_1 = div_floor((int64)(v + l) * (w - 1) - 1, w + 1); 226 ans += 227 (std::upper_bound(pos.begin(), barrier, u_max_0) - pos.begin()) + 228 (std::upper_bound(barrier, pos.end(), std::min(v, u_max_1)) - barrier); 229 } 230 231 printf("%lld\n", ans); 232 return 0; 233 } 234 ``` 235 236 Tutorial is loading... 237 238 **Model solution** 239 240 ``` 241 #include <cassert> 242 #include <cstdio> 243 #include <algorithm> 244 #include <utility> 245 #include <vector> 246 247 static const int MAXN = 202; 248 static const int LOGM = 15; 249 250 static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 251 252 struct point { 253 int x, y; 254 point(int x = 0, int y = 0) : x(x), y(y) { } 255 }; 256 257 struct line { 258 // ax + by + c = 0 259 int a, b, c; 260 261 line() : a(0), b(0), c(0) { } 262 line(const point &p, const point &q) 263 : a(p.y - q.y) 264 , b(q.x - p.x) 265 , c(q.y * p.x - q.x * p.y) 266 { 267 int g = gcd(gcd(a, b), c); 268 if (g != 1) { a /= g; b /= g; c /= g; } 269 if (a < 0) { a = -a; b = -b; c = -c; } 270 } 271 272 inline bool contains(const point &p) { 273 return a * p.x + b * p.y + c == 0; 274 } 275 276 // For sorting & duplicate removing 277 inline bool operator < (const line &other) const { 278 return a != other.a ? a < other.a : 279 b != other.b ? b < other.b : c < other.c; 280 } 281 inline bool operator == (const line &other) const { 282 return a == other.a && b == other.b && c == other.c; 283 } 284 }; 285 286 struct mat { 287 static const int N = ::MAXN; 288 int sz; 289 double a[N][N]; 290 291 mat(int sz = N, int id = 0) : sz(sz) { 292 for (int i = 0; i < N; ++i) 293 for (int j = 0; j < N; ++j) 294 a[i][j] = (i == j ? id : 0); 295 } 296 297 inline mat operator * (const mat &other) { 298 assert(other.sz == this->sz); 299 mat ret(sz, 0); 300 for (int i = 0; i < sz; ++i) 301 for (int k = 0; k < sz; ++k) 302 for (int j = 0; j < sz; ++j) 303 ret.a[i][j] += this->a[i][k] * other.a[k][j]; 304 return ret; 305 } 306 307 inline std::vector<double> operator * (const std::vector<double> &u) { 308 assert(u.size() == this->sz); 309 std::vector<double> v(sz); 310 for (int i = 0; i < sz; ++i) 311 for (int j = 0; j < sz; ++j) 312 v[i] += a[i][j] * u[j]; 313 return v; 314 } 315 }; 316 317 static int n, q; 318 static point p[MAXN]; 319 320 static line l[MAXN * MAXN / 2]; 321 // Lists of lines that pass through points 322 static std::vector<int> pl[MAXN]; 323 // Lists of points that lie on lines 324 static std::vector<int> lp[MAXN * MAXN / 2]; 325 326 static mat A, Ap[LOGM]; 327 328 int main() 329 { 330 scanf("%d", &n); 331 for (int i = 0; i < n; ++i) scanf("%d%d", &p[i].x, &p[i].y); 332 333 int l_num = 0; 334 for (int i = 0; i < n; ++i) 335 for (int j = i + 1; j < n; ++j) 336 l[l_num++] = line(p[i], p[j]); 337 std::sort(l, l + l_num); 338 l_num = std::unique(l, l + l_num) - &l[0]; 339 340 for (int i = 0; i < n; ++i) 341 for (int j = 0; j < l_num; ++j) 342 if (l[j].contains(p[i])) { 343 pl[i].push_back(j); 344 lp[j].push_back(i); 345 } 346 347 A = mat(n, 0); 348 for (int i = 0; i < n; ++i) { 349 for (int j : pl[i]) 350 for (int k : lp[j]) 351 A.a[i][k] += 1.0L / (pl[i].size() * lp[j].size()); 352 } 353 354 Ap[0] = A; 355 for (int i = 1; i < LOGM; ++i) Ap[i] = Ap[i - 1] * Ap[i - 1]; 356 357 scanf("%d", &q); 358 std::vector<double> u(n); 359 for (int i = 0, t, m; i < q; ++i) { 360 scanf("%d%d", &t, &m); --t; 361 362 std::fill(u.begin(), u.end(), 0); 363 u[t] = 1.0; 364 for (int j = 0; j < LOGM; ++j) 365 if ((m - 1) & (1 << j)) u = Ap[j] * u; 366 367 double max = -1.0; 368 for (int j = 0; j < l_num; ++j) { 369 double cur = 0.0; 370 for (int k : lp[j]) cur += u[k]; 371 cur /= lp[j].size(); 372 max = std::max(max, cur); 373 } 374 printf("%.12lf\n", (double)max); 375 } 376 377 return 0; 378 } 379 ``` 380 381 --- 382 383 See you next time! I hope I'll be welcomed. Cheers!