1612.md (9335B)
1 Source: https://codeforces.com/blog/entry/97164 2 3 [1612A - Distance](/contest/1612/problem/A "Educational Codeforces Round 117 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 x, y = map(int, input().split()) 17 xc = -1 18 yc = -1 19 for j in range(0, 51): 20 for k in range(0, 51): 21 if 2 * (j + k) == x + y and 2 * (abs(x - j) + abs(y - k)) == x + y: 22 xc, yc = j, k 23 print(xc, yc) 24 ``` 25 26 [1612B - Special Permutation](/contest/1612/problem/B "Educational Codeforces Round 117 (Rated for Div. 2)") 27 28 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (BledDest)** 35 36 ``` 37 t = int(input()) 38 for i in range(t): 39 n, a, b = map(int, input().split()) 40 p = [a] 41 for j in range(n, 0, -1): 42 if j != a and j != b: 43 p.append(j) 44 p.append(b) 45 if(len(p) == n and min(p[0:n//2]) == a and max(p[n//2:n]) == b): 46 print(*p) 47 else: 48 print(-1) 49 ``` 50 51 [1612C - Chat Ban](/contest/1612/problem/C "Educational Codeforces Round 117 (Rated for Div. 2)") 52 53 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (vovuh)** 60 61 ``` 62 #include <bits/stdc++.h> 63 64 using namespace std; 65 66 long long get(int x) { 67 return x * 1ll * (x + 1) / 2; 68 } 69 70 int main() { 71 #ifdef _DEBUG 72 freopen("input.txt", "r", stdin); 73 // freopen("output.txt", "w", stdout); 74 #endif 75 76 int t; 77 cin >> t; 78 while (t--) { 79 int k; 80 long long x; 81 cin >> k >> x; 82 long long l = 1, r = 2 * k - 1; 83 long long res = 2 * k - 1; 84 bool over = false; 85 while (l <= r) { 86 int mid = (l + r) >> 1; 87 if (mid >= k) { 88 over = (get(k) + get(k - 1) - get(2 * k - 1 - mid) >= x); 89 } else { 90 over = (get(mid) >= x); 91 } 92 if (over) { 93 res = mid; 94 r = mid - 1; 95 } else { 96 l = mid + 1; 97 } 98 } 99 cout << res << endl; 100 } 101 102 return 0; 103 } 104 ``` 105 106 [1612D - X-Magic Pair](/contest/1612/problem/D "Educational Codeforces Round 117 (Rated for Div. 2)") 107 108 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh") 109 110 **Tutorial** 111 112 Tutorial is loading... 113 114 **Solution (vovuh)** 115 116 ``` 117 #include <bits/stdc++.h> 118 119 using namespace std; 120 121 bool get(long long a, long long b, long long x) { 122 if (a == x || b == x) return true; 123 if (a < b) swap(a, b); 124 if (b > a - b) b = a - b; 125 if (x > max(a, b) || a == 0 || b == 0) return false; 126 long long cnt = max(1ll, (a - max(x, b)) / (2 * b)); 127 return get(a - b * cnt, b, x); 128 } 129 130 int main() { 131 #ifdef _DEBUG 132 freopen("input.txt", "r", stdin); 133 // freopen("output.txt", "w", stdout); 134 #endif 135 136 int t; 137 cin >> t; 138 while (t--) { 139 long long a, b, x; 140 cin >> a >> b >> x; 141 if (get(a, b, x)) { 142 cout << "YES" << endl; 143 } else { 144 cout << "NO" << endl; 145 } 146 } 147 148 return 0; 149 } 150 ``` 151 152 [1612E - Messages](/contest/1612/problem/E "Educational Codeforces Round 117 (Rated for Div. 2)") 153 154 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 155 156 **Tutorial** 157 158 Tutorial is loading... 159 160 **Solution (BledDest)** 161 162 ``` 163 #include <bits/stdc++.h> 164 165 using namespace std; 166 167 const int N = 200043; 168 const int K = 20; 169 vector<int> idx[N]; 170 int m[N], k[N]; 171 172 bool frac_greater(pair<int, int> a, pair<int, int> b) 173 { 174 return a.first * b.second > a.second * b.first; 175 } 176 177 int main() 178 { 179 int n; 180 scanf("%d", &n); 181 for(int i = 0; i < n; i++) 182 { 183 scanf("%d %d", &m[i], &k[i]); 184 idx[m[i]].push_back(i); 185 } 186 187 vector<int> cert; 188 pair<int, int> ans = {0, 1}; 189 for(int i = 1; i <= K; i++) 190 { 191 vector<int> score(N); 192 for(int j = 0; j < n; j++) 193 score[m[j]] += min(i, k[j]); 194 vector<pair<int, int>> aux; 195 for(int j = 0; j < N; j++) 196 aux.push_back(make_pair(score[j], j)); 197 sort(aux.rbegin(), aux.rend()); 198 pair<int, int> cur_ans = {0, i}; 199 vector<int> cur_cert; 200 for(int j = 0; j < i; j++) 201 { 202 cur_ans.first += aux[j].first; 203 cur_cert.push_back(aux[j].second); 204 } 205 if(frac_greater(cur_ans, ans)) 206 { 207 ans = cur_ans; 208 cert = cur_cert; 209 } 210 } 211 cout << cert.size() << endl; 212 shuffle(cert.begin(), cert.end(), mt19937(time(NULL))); 213 for(auto x : cert) cout << x << " "; 214 cout << endl; 215 } 216 ``` 217 218 [1612F - Armor and Weapons](/contest/1612/problem/F "Educational Codeforces Round 117 (Rated for Div. 2)") 219 220 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution (BledDest)** 227 228 ``` 229 #include<bits/stdc++.h> 230 231 using namespace std; 232 233 int n, m; 234 235 #define x first 236 #define y second 237 238 typedef pair<int, int> comb; 239 240 comb norm(const comb& a) 241 { 242 return make_pair(min(a.x, n), min(a.y, m)); 243 } 244 245 bool good(const comb& a) 246 { 247 return a.x == n || a.y == m; 248 } 249 250 bool comp(const comb& a, const comb& b) 251 { 252 if(a.x != b.x) 253 return a.x > b.x; 254 return a.y > b.y; 255 } 256 257 int main() 258 { 259 scanf("%d %d", &n, &m); 260 int v; 261 scanf("%d", &v); 262 set<comb> s; 263 for(int i = 0; i < v; i++) 264 { 265 int x, y; 266 scanf("%d %d", &x, &y); 267 s.insert(make_pair(x, y)); 268 } 269 int steps = 0; 270 vector<comb> cur; 271 cur.push_back(make_pair(1, 1)); 272 while(true) 273 { 274 if(cur[0] == make_pair(n, m)) 275 break; 276 vector<comb> ncur; 277 for(auto x : cur) 278 { 279 int sum = x.x + x.y; 280 if(s.count(x)) 281 sum++; 282 comb z = x; 283 z.x = sum; 284 ncur.push_back(norm(z)); 285 z = x; 286 z.y = sum; 287 ncur.push_back(norm(z)); 288 } 289 sort(ncur.begin(), ncur.end(), comp); 290 int mx = 0; 291 vector<comb> ncur2; 292 for(auto x : ncur) 293 { 294 if(x.y <= mx) continue; 295 mx = max(mx, x.y); 296 ncur2.push_back(x); 297 } 298 cur = ncur2; 299 steps++; 300 } 301 printf("%d\n", steps); 302 } 303 ``` 304 305 [1612G - Max Sum Array](/contest/1612/problem/G "Educational Codeforces Round 117 (Rated for Div. 2)") 306 307 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 308 309 **Tutorial** 310 311 Tutorial is loading... 312 313 **Solution (adedalic)** 314 315 ``` 316 #include<bits/stdc++.h> 317 318 using namespace std; 319 320 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 321 #define sz(a) int((a).size()) 322 323 #define x first 324 #define y second 325 326 typedef long long li; 327 typedef pair<int, int> pt; 328 329 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 330 return out << "(" << p.x << " " << p.y << ")"; 331 } 332 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 333 fore(i, 0, sz(v)) { 334 if(i) out << " "; 335 out << v[i]; 336 } 337 return out; 338 } 339 340 const int INF = int(1e9); 341 const li INF64 = li(1e18); 342 343 const int MOD = int(1e9) + 7; 344 345 int norm(int a) { 346 while (a >= MOD) 347 a -= MOD; 348 while (a < 0) 349 a += MOD; 350 return a; 351 } 352 int mul(int a, int b) { 353 return int(a * 1ll * b % MOD); 354 } 355 356 const int MX = int(1e6) + 55; 357 int n; 358 li total; 359 int cnt[MX]; 360 361 inline bool read() { 362 if(!(cin >> n)) 363 return false; 364 total = 0; 365 fore (i, 0, n) { 366 int k; cin >> k; 367 cnt[k]++; 368 total += k; 369 } 370 return true; 371 } 372 373 int fact[MX]; 374 375 inline void solve() { 376 fact[0] = 1; 377 fore (i, 1, MX) 378 fact[i] = mul(fact[i - 1], i); 379 380 int ansSum = 0; 381 int ansCnt = 1; 382 383 for (int lvl = MX - 1; lvl > 1; lvl--) { 384 ansCnt = mul(ansCnt, mul(fact[cnt[lvl]], fact[cnt[lvl]])); 385 386 //each color gives (lvl - 1) * (r_i - l_i) 387 // or (lvl - 1) * (sum r_i - sum l_i) 388 // l_i is permutation of [0,..., cnt[lvl]), so sum l_i = (cnt[lvl] - 1) * cnt[lvl] / 2 389 // r_i is permutation of [total - cnt[lvl],..., total), so sum = cnt[lvl] * (total - cnt[lvl]) + (cnt[lvl] - 1) * cnt[lvl] / 2 390 391 ansSum = norm(ansSum + mul(mul(lvl - 1, cnt[lvl]), (total - cnt[lvl]) % MOD)); 392 393 total -= 2 * cnt[lvl]; 394 cnt[lvl - 2] += cnt[lvl]; 395 } 396 397 ansCnt = mul(ansCnt, fact[cnt[1]]); 398 399 cout << ansSum << " " << ansCnt << endl; 400 } 401 402 int main() { 403 #ifdef _DEBUG 404 freopen("input.txt", "r", stdin); 405 int tt = clock(); 406 #endif 407 ios_base::sync_with_stdio(false); 408 cin.tie(0), cout.tie(0); 409 cout << fixed << setprecision(15); 410 411 if(read()) { 412 solve(); 413 414 #ifdef _DEBUG 415 cerr << "TIME = " << clock() - tt << endl; 416 tt = clock(); 417 #endif 418 } 419 return 0; 420 } 421 ```