1521.md (8991B)
1 Source: https://codeforces.com/blog/entry/90477 2 3 Thanks for participating! 4 5 [1521A - Nastia and Nearly Good Numbers](/contest/1521/problem/A "Codeforces Round 720 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 ios_base::sync_with_stdio(false); 20 cin.tie(nullptr); cout.tie(nullptr); 21 22 int q; 23 cin >> q; 24 25 while (q--) { 26 int a, b; cin >> a >> b; 27 if (b == 1) { 28 cout << "NO" << endl; 29 } else { 30 cout << "YES" << endl; 31 cout << a << ' ' << a * (long long)b << ' ' << a * (long long)(b + 1) << endl; 32 } 33 } 34 } 35 ``` 36 37 [1521B - Nastia and a Good Array](/contest/1521/problem/B "Codeforces Round 720 (Div. 2)") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include "bits/stdc++.h" 47 48 using namespace std; 49 50 int main() { 51 ios_base::sync_with_stdio(false); 52 cin.tie(nullptr); cout.tie(nullptr); 53 54 int q; 55 cin >> q; 56 57 while (q--) { 58 int n; cin >> n; 59 int x = 1e9 + 7, pos = -1; 60 for (int i = 0; i < n; ++i) { 61 int a; cin >> a; 62 if (a < x) x = a, pos = i; 63 } 64 cout << n - 1 << endl; 65 for (int i = 0; i < n; ++i) { 66 if (i == pos) continue; 67 cout << pos + 1 << ' ' << i + 1 << ' ' << x << ' ' << x + abs(i - pos) << "\n"; 68 } 69 } 70 } 71 ``` 72 73 [1521C - Nastia and a Hidden Permutation](/contest/1521/problem/C "Codeforces Round 720 (Div. 2)") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution 1** 80 81 ``` 82 #include "bits/stdc++.h" 83 84 using namespace std; 85 86 int ask(int t, int i, int j, int x) { 87 cout << "? " << t << ' ' << i + 1 << ' ' << j + 1 << ' ' << x << endl; 88 int val; cin >> val; 89 if (val == -1) exit(0); 90 return val; 91 } 92 93 int main() { 94 ios_base::sync_with_stdio(false); 95 cin.tie(nullptr); cout.tie(nullptr); 96 97 int q; 98 cin >> q; 99 100 while (q--) { 101 int n; cin >> n; 102 vector<int> p(n, -1); 103 for (int i = 1; i < n; i += 2) { 104 int pos1 = i - 1, pos2 = i; 105 int val = ask(1, pos1, pos2, n - 1); 106 if (val == n - 1) { 107 val = ask(1, pos2, pos1, n - 1); 108 if (val == n) { 109 p[pos1] = val; 110 p[pos2] = ask(2, pos2, pos1, 1); 111 continue; 112 } 113 } 114 int get = ask(1, pos1, pos2, val - 1); 115 if (get == val) { 116 p[pos2] = val; 117 p[pos1] = ask(2, pos1, pos2, 1); 118 } 119 if (get == val - 1) { 120 p[pos1] = val; 121 p[pos2] = ask(2, pos2, pos1, 1); 122 } 123 } 124 if (p.back() == -1) { 125 vector<bool> us(n + 1); 126 for (int i = 0; i < n - 1; ++i) { 127 us[p[i]] = true; 128 } 129 for (int i = 1; i <= n; ++i) { 130 if (!us[i]) { 131 assert(p[p.size() - 1] == -1); 132 p[p.size() - 1] = i; 133 } 134 } 135 } 136 cout << "! "; 137 for (int i = 0; i < n; ++i) { 138 cout << p[i] << ' '; 139 } cout << endl; 140 } 141 } 142 ``` 143 144 [1521D - Nastia Plays with a Tree](/contest/1521/problem/D "Codeforces Round 720 (Div. 2)") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Solution** 151 152 ``` 153 #include <bits/stdc++.h> 154 155 using namespace std; 156 157 const int N = 1e5 + 7; 158 159 struct edge { 160 int v, u; 161 }; 162 163 vector<pair<edge, edge>> operations; 164 165 int dp[N], answer = 0; 166 167 bool isDeleted[N]; 168 169 vector<pair<int, int>> g[N]; 170 171 void dfs(int v, int p = -1) { 172 int sz = (int)g[v].size() - (p != -1); 173 for (auto to : g[v]) { 174 if (to.first == p) continue; 175 dfs(to.first, v); 176 if (dp[to.first]) { 177 --sz; ++answer; 178 isDeleted[to.second] = true; 179 } 180 } 181 if (sz >= 2) { 182 dp[v] = true; 183 for (auto to : g[v]) { 184 if (to.first == p) continue; 185 if (sz <= 2) break; 186 if (!dp[to.first]) { 187 --sz; ++answer; 188 isDeleted[to.second] = true; 189 } 190 } 191 } 192 } 193 194 vector<pair<int, int>> bamboos; 195 196 bool used[N]; 197 198 vector<int> leaves; 199 200 void dfs2(int v, int root) { 201 used[v] = true; 202 int numberOfChildren = 0; 203 for (auto to : g[v]) { 204 if (used[to.first] || isDeleted[to.second]) continue; 205 ++numberOfChildren; dfs2(to.first, root); 206 } 207 if (v == root && numberOfChildren == 1) { 208 leaves.push_back(v); 209 } else if (!numberOfChildren) { 210 leaves.push_back(v); 211 } 212 } 213 214 void clear(int n) { 215 answer = 0; 216 for (int i = 0; i < n; ++i) { 217 dp[i] = 0; 218 g[i].clear(); 219 used[i] = isDeleted[i] = false; 220 } 221 bamboos.clear(); 222 operations.clear(); 223 } 224 225 signed main() { 226 ios_base::sync_with_stdio(false); 227 cin.tie(nullptr); cout.tie(nullptr); 228 229 int q; 230 cin >> q; 231 232 while (q--) { 233 int n; cin >> n; 234 235 for (int i = 0; i < n - 1; ++i) { 236 int a, b; cin >> a >> b; 237 --a; --b; 238 g[a].push_back({b, i}); 239 g[b].push_back({a, i}); 240 } 241 242 dfs(0); 243 for (int i = 0; i < n; ++i) { 244 if (!used[i]) { 245 dfs2(i, i); 246 assert((int)leaves.size() <= 2); 247 if ((int)leaves.size() == 2) { 248 bamboos.push_back({leaves[0], leaves[1]}); 249 } 250 if ((int)leaves.size() == 1) { 251 bamboos.push_back({leaves.back(), leaves.back()}); 252 } 253 leaves.clear(); 254 } 255 } 256 257 vector<edge> deletedEdges, addedEdges; 258 for (int v = 0; v < n; ++v) { 259 for (auto to : g[v]) { 260 if (isDeleted[to.second]) { 261 if (v < to.first) { 262 deletedEdges.push_back({v, to.first}); 263 } 264 } 265 } 266 } 267 for (int i = 1; i < (int)bamboos.size(); ++i) { 268 addedEdges.push_back({bamboos[i - 1].second, bamboos[i].first}); 269 } 270 271 assert(answer == (int)deletedEdges.size()); 272 assert((int)deletedEdges.size() == (int)addedEdges.size()); 273 274 for (int i = 0; i < answer; ++i) { 275 operations.push_back({deletedEdges[i], addedEdges[i]}); 276 } 277 278 assert(answer == (int)operations.size()); 279 280 cout << answer << endl; 281 for (pair<edge, edge> to : operations) { 282 cout << to.first.v + 1 << ' ' << to.first.u + 1 << ' '; 283 cout << to.second.v + 1 << ' ' << to.second.u + 1 << endl; 284 } 285 286 clear(n); 287 } 288 } 289 ``` 290 291 [1521E - Nastia and a Beautiful Matrix](/contest/1521/problem/E "Codeforces Round 720 (Div. 2)") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include "bits/stdc++.h" 301 302 using namespace std; 303 304 int main() { 305 ios_base::sync_with_stdio(false); 306 cin.tie(nullptr); cout.tie(nullptr); 307 308 int q; 309 cin >> q; 310 311 while (q--) { 312 int m, k; cin >> m >> k; 313 314 pair<int, int> a[k]; 315 for (int i = 0; i < k; ++i) { 316 cin >> a[i].first, a[i].second = i + 1; 317 } sort(a, a + k, greater<pair<int, int>>()); 318 319 int mx = a[0].first; 320 for (int n = 1; n <= m; ++n) { 321 // mx <= n * ceil(n / 2) 322 if (mx > n * (long long)((n + 1) / 2)) continue; 323 // m <= n ^ 2 - floor(n / 2) ^ 2 324 if (m > n * (long long)n - (n / 2) * (long long)(n / 2)) continue; 325 326 // answer = n 327 vector<pair<int, int>> x, y, z; 328 for (int i = 0; i < n; ++i) { 329 for (int j = 0; j < n; ++j) { 330 if ((i + j) % 2 == 1) { 331 if (i % 2 == 0) x.push_back({i, j}); 332 else y.push_back({i, j}); 333 } else { 334 if (i % 2 == 0) z.push_back({i, j}); 335 } 336 } 337 } 338 339 int ans[n][n]; 340 for (int i = 0; i < n; ++i) { 341 for (int j = 0; j < n; ++j) { 342 ans[i][j] = 0; 343 } 344 } 345 346 for (int i = 0; i < k; ++i) { 347 vector<pair<int, int>> &cur = (x.empty() ? y : x); 348 while (a[i].first && !cur.empty()) { 349 pair<int, int> pos = cur.back(); 350 ans[pos.first][pos.second] = a[i].second; 351 cur.pop_back(); --a[i].first; 352 } 353 while(a[i].first--) { 354 assert((int)z.size() > 0); 355 pair<int, int> pos = z.back(); 356 ans[pos.first][pos.second] = a[i].second; 357 z.pop_back(); 358 } 359 } 360 361 // print answer 362 cout << n << endl; 363 for (int i = 0; i < n; ++i) { 364 for (int j = 0; j < n; ++j) { 365 cout << ans[i][j] << ' '; 366 } cout << endl; 367 } 368 369 break; 370 } 371 } 372 } 373 ```