1772.md (6727B)
1 Source: https://codeforces.com/blog/entry/110313 2 3 [1772A - A+B?](/contest/1772/problem/A "Codeforces Round 839 (Div. 3)") 4 5 Idea: [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 print(eval(input())) 17 ``` 18 19 [1772B - Matrix Rotation](/contest/1772/problem/B "Codeforces Round 839 (Div. 3)") 20 21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (BledDest)** 28 29 ``` 30 #include<bits/stdc++.h> 31 32 using namespace std; 33 34 int main() 35 { 36 int t; 37 cin >> t; 38 for(int _ = 0; _ < t; _++) 39 { 40 vector<int> a(4); 41 for(int i = 0; i < 4; i++) 42 cin >> a[i]; 43 int maxpos = max_element(a.begin(), a.end()) - a.begin(); 44 int minpos = min_element(a.begin(), a.end()) - a.begin(); 45 if(maxpos + minpos == 3) 46 puts("YES"); 47 else 48 puts("NO"); 49 } 50 } 51 ``` 52 53 [1772C - Different Differences](/contest/1772/problem/C "Codeforces Round 839 (Div. 3)") 54 55 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution (BledDest)** 62 63 ``` 64 def construct(f, k): 65 return [(i + 2 if i < f - 1 else 1) for i in range(k)] 66 67 t = int(input()) 68 for i in range(t): 69 k, n = map(int, input().split()) 70 ans = 1 71 for f in range(1, k): 72 d = construct(f, k - 1) 73 if sum(d) <= n - 1: 74 ans = f 75 res = [1] 76 d = construct(ans, k - 1) 77 for x in d: 78 res.append(res[-1] + x) 79 print(*res) 80 ``` 81 82 [1772D - Absolute Sorting](/contest/1772/problem/D "Codeforces Round 839 (Div. 3)") 83 84 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution (BledDest)** 91 92 ``` 93 #include <bits/stdc++.h> 94 95 using namespace std; 96 97 int main() 98 { 99 int t; 100 cin >> t; 101 for(int i = 0; i < t; i++) 102 { 103 int n; 104 cin >> n; 105 vector<int> a(n); 106 for(int j = 0; j < n; j++) 107 cin >> a[j]; 108 int mn = 0, mx = int(1e9); 109 for(int j = 0; j + 1 < n; j++) 110 { 111 int x = a[j]; 112 int y = a[j + 1]; 113 int midL = (x + y) / 2; 114 int midR = (x + y + 1) / 2; 115 if(x < y) 116 mx = min(mx, midL); 117 if(x > y) 118 mn = max(mn, midR); 119 } 120 if(mn <= mx) cout << mn << endl; 121 else cout << -1 << endl; 122 } 123 } 124 ``` 125 126 [1772E - Permutation Game](/contest/1772/problem/E "Codeforces Round 839 (Div. 3)") 127 128 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 129 130 **Tutorial** 131 132 Tutorial is loading... 133 134 **Solution (Neon)** 135 136 ``` 137 for tc in range(int(input())): 138 n = int(input()) 139 p = list(map(int, input().split())) 140 a, b, c = 0, 0, 0 141 for i in range(n): 142 if p[i] != i + 1 and p[i] != n - i: 143 c += 1 144 elif p[i] != i + 1: 145 a += 1 146 elif p[i] != n - i: 147 b += 1 148 if a + c <= b: 149 print("First") 150 elif b + c < a: 151 print("Second") 152 else: 153 print("Tie") 154 ``` 155 156 [1772F - Copy of a Copy of a Copy](/contest/1772/problem/F "Codeforces Round 839 (Div. 3)") 157 158 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 159 160 **Tutorial** 161 162 Tutorial is loading... 163 164 **Solution (awoo)** 165 166 ``` 167 #include <bits/stdc++.h> 168 169 using namespace std; 170 171 #define forn(i, n) for(int i = 0; i < int(n); i++) 172 173 struct op{ 174 int t, x, y, i; 175 }; 176 177 int dx[] = {-1, 0, 1, 0}; 178 int dy[] = {0, 1, 0, -1}; 179 180 int main(){ 181 int n, m, k; 182 cin >> n >> m >> k; 183 vector<vector<string>> a(k + 1, vector<string>(n)); 184 forn(z, k + 1) forn(i, n) 185 cin >> a[z][i]; 186 187 vector<int> cnt(k + 1); 188 forn(z, k + 1){ 189 for (int i = 1; i < n - 1; ++i){ 190 for (int j = 1; j < m - 1; ++j){ 191 bool ok = true; 192 forn(t, 4) 193 ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]]; 194 cnt[z] += ok; 195 } 196 } 197 } 198 199 vector<int> ord(k + 1); 200 iota(ord.begin(), ord.end(), 0); 201 sort(ord.begin(), ord.end(), [&cnt](int x, int y){ 202 return cnt[x] > cnt[y]; 203 }); 204 205 vector<op> ops; 206 forn(z, k){ 207 forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){ 208 a[ord[z]][i][j] ^= '0' ^ '1'; 209 ops.push_back({1, i + 1, j + 1, -1}); 210 } 211 ops.push_back({2, -1, -1, ord[z + 1] + 1}); 212 } 213 214 cout << ord[0] + 1 << '\n'; 215 cout << ops.size() << '\n'; 216 for (auto it : ops){ 217 cout << it.t << " "; 218 if (it.t == 1) 219 cout << it.x << " " << it.y << '\n'; 220 else 221 cout << it.i << '\n'; 222 } 223 } 224 ``` 225 226 [1772G - Gaining Rating](/contest/1772/problem/G "Codeforces Round 839 (Div. 3)") 227 228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution (adedalic)** 235 236 ``` 237 #include<bits/stdc++.h> 238 239 using namespace std; 240 241 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 242 #define sz(a) int((a).size()) 243 244 typedef long long li; 245 246 int n; 247 li x, y; 248 vector<li> a; 249 250 inline bool read() { 251 if(!(cin >> n >> x >> y)) 252 return false; 253 a.resize(n); 254 fore (i, 0, n) 255 cin >> a[i]; 256 return true; 257 } 258 259 li ceil(li a, li b) { 260 assert(a >= 0 && b >= 0); 261 return (a + b - 1) / b; 262 } 263 264 inline void solve() { 265 sort(a.begin(), a.end()); 266 267 vector<li> t(n), b(n); 268 fore (i, 0, n) { 269 if (i > 0 && b[i - 1] >= a[i]) { 270 t[i] = t[i - 1]; 271 b[i] = b[i - 1] + 1; 272 } else { 273 t[i] = a[i] - i; 274 b[i] = a[i] + 1; 275 } 276 } 277 278 li ans = 0; 279 while (x < y) { 280 int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin()); 281 282 li p = pos, m = n - pos; 283 if (x + p >= y) { 284 cout << ans + (y - x) << endl; 285 return; 286 } 287 if (p <= m) { 288 cout << -1 << endl; 289 return; 290 } 291 292 //1. x + k(p - m) + p >= y 293 li k = ceil(y - x - p, p - m); 294 if (pos < n) { 295 //2. x + k(p - m) >= t[pos] 296 k = min(k, ceil(t[pos] - x, p - m)); 297 } 298 ans += k * n; 299 //x + k(p - m) < y, since 1. and p >= p - m 300 x += k * (p - m); 301 } 302 assert(false); 303 } 304 305 int main() { 306 #ifdef _DEBUG 307 freopen("input.txt", "r", stdin); 308 int tt = clock(); 309 #endif 310 ios_base::sync_with_stdio(false); 311 cin.tie(0), cout.tie(0); 312 cout << fixed << setprecision(15); 313 314 int t; cin >> t; 315 while (t--) { 316 read(); 317 solve(); 318 319 #ifdef _DEBUG 320 cerr << "TIME = " << clock() - tt << endl; 321 tt = clock(); 322 #endif 323 } 324 return 0; 325 } 326 ```