1674.md (7109B)
1 Source: https://codeforces.com/blog/entry/102482 2 3 [1674A - Number Transformation](/contest/1674/problem/A "Codeforces Round 786 (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 x, y = map(int, input().split()) 17 if y % x != 0: 18 print(0, 0) 19 else: 20 print(1, y // x) 21 ``` 22 23 [1674B - Dictionary](/contest/1674/problem/B "Codeforces Round 786 (Div. 3)") 24 25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (BledDest)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 using namespace std; 37 38 int main() 39 { 40 string w = "aa"; 41 map<string, int> idx; 42 int i = 1; 43 for(w[0] = 'a'; w[0] <= 'z'; w[0]++) 44 for(w[1] = 'a'; w[1] <= 'z'; w[1]++) 45 if(w[0] != w[1]) 46 idx[w] = i++; 47 int t; 48 cin >> t; 49 for(int i = 0; i < t; i++) 50 { 51 string s; 52 cin >> s; 53 cout << idx[s] << endl; 54 } 55 } 56 ``` 57 58 [1674C - Infinite Replacement](/contest/1674/problem/C "Codeforces Round 786 (Div. 3)") 59 60 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution (awoo)** 67 68 ``` 69 for _ in range(int(input())): 70 s = input() 71 t = input() 72 if t == "a": 73 print(1) 74 elif t.count('a') != 0: 75 print(-1) 76 else: 77 print(2**len(s)) 78 ``` 79 80 [1674D - A-B-C Sort](/contest/1674/problem/D "Codeforces Round 786 (Div. 3)") 81 82 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution (adedalic)** 89 90 ``` 91 fun main() { 92 repeat(readLine()!!.toInt()) { 93 val n = readLine()!!.toInt() 94 val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray() 95 for (i in (n % 2) until n step 2) { 96 if (a[i] > a[i + 1]) 97 a[i] = a[i + 1].also { a[i + 1] = a[i] } 98 } 99 var sorted = true 100 for (i in a.indices) 101 if (i > 0 && a[i - 1] > a[i]) 102 sorted = false 103 println(if(sorted) "YES" else "NO") 104 } 105 } 106 ``` 107 108 [1674E - Breaking the Wall](/contest/1674/problem/E "Codeforces Round 786 (Div. 3)") 109 110 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Solution (fcspartakm)** 117 118 ``` 119 #include <iostream> 120 #include <sstream> 121 #include <cstdio> 122 #include <vector> 123 #include <cmath> 124 #include <queue> 125 #include <string> 126 #include <cstring> 127 #include <cassert> 128 #include <iomanip> 129 #include <algorithm> 130 #include <set> 131 #include <map> 132 #include <ctime> 133 #include <cmath> 134 135 #define forn(i, n) for(int i=0;i<n;++i) 136 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i) 137 #define sz(v) int(v.size()) 138 #define all(v) v.begin(), v.end() 139 #define pb push_back 140 #define mp make_pair 141 #define x first 142 #define y1 ________y1 143 #define y second 144 #define ft first 145 #define sc second 146 #define pt pair<int, int> 147 148 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; } 149 template<typename X> inline X sqr(const X& a) { return a * a; } 150 151 typedef long long li; 152 typedef long double ld; 153 154 using namespace std; 155 156 const int INF = 1000 * 1000 * 1000; 157 const ld EPS = 1e-9; 158 const ld PI = acos(-1.0); 159 160 const int N = 200 * 1000 + 13; 161 162 int n; 163 int a[N]; 164 165 inline void read() { 166 cin >> n; 167 for (int i = 0; i < n; i++) { 168 cin >> a[i]; 169 } 170 } 171 172 inline void solve() { 173 int ans = INF; 174 for (int i = 0; i < n - 1; i++) { 175 int cur = 0; 176 int x = a[i], y = a[i + 1]; 177 if (x < y) { 178 swap(x, y); 179 } 180 int cnt = min(x - y, (x + 1) / 2); 181 cur += cnt; 182 x -= 2 * cnt; 183 y -= cnt; 184 if (x > 0 && y > 0) { 185 cur += (x + y + 2) / 3; 186 } 187 ans = min(ans, cur); 188 } 189 190 for (int i = 0; i < n - 2; i++) { 191 int cur = 0; 192 int x = a[i], y = a[i + 2]; 193 if (x < y) { 194 swap(x, y); 195 } 196 int cnt = (x - y + 1) / 2; 197 cur += cnt; 198 cur += y; 199 ans = min(ans, cur); 200 } 201 202 sort(a, a + n); 203 ans = min(ans, (a[0] + 1) / 2 + (a[1] + 1) / 2); 204 cout << ans << endl; 205 } 206 207 int main () { 208 #ifdef fcspartakm 209 freopen("input.txt", "r", stdin); 210 //freopen("output.txt", "w", stdout); 211 #endif 212 srand(time(NULL)); 213 cerr << setprecision(10) << fixed; 214 215 read(); 216 solve(); 217 218 //cerr << "TIME: " << clock() << endl; 219 } 220 ``` 221 222 [1674F - Desktop Rearrangement](/contest/1674/problem/F "Codeforces Round 786 (Div. 3)") 223 224 Idea: [vovuh](/profile/vovuh "Master vovuh") 225 226 **Tutorial** 227 228 Tutorial is loading... 229 230 **Solution (vovuh)** 231 232 ``` 233 #include <bits/stdc++.h> 234 235 using namespace std; 236 237 static char buf[1010]; 238 239 int main() { 240 #ifdef _DEBUG 241 freopen("input.txt", "r", stdin); 242 // freopen("output.txt", "w", stdout); 243 #endif 244 245 int n, m, q; 246 scanf("%d %d %d", &n, &m, &q); 247 vector<string> tmp(n); 248 string s; 249 int sum = 0; 250 for (int i = 0; i < n; ++i) { 251 scanf("%s", buf); 252 tmp[i] = buf; 253 sum += count(tmp[i].begin(), tmp[i].end(), '*'); 254 } 255 256 for (int j = 0; j < m; ++j) { 257 for (int i = 0; i < n; ++i) { 258 s += tmp[i][j]; 259 } 260 } 261 int res = count(s.begin(), s.begin() + sum, '.'); 262 int pos = sum; 263 for (int i = 0; i < q; ++i) { 264 int x, y; 265 scanf("%d %d", &x, &y); 266 --x, --y; 267 int p = y * n + x; 268 if (p < pos) { 269 if (s[p] == '.') { 270 --res; 271 } else { 272 ++res; 273 } 274 } 275 s[p] = (s[p] == '.' ? '*' : '.'); 276 if (s[p] == '*') { 277 if (s[pos] == '.') { 278 ++res; 279 } 280 ++pos; 281 } else { 282 if (s[pos - 1] == '.') { 283 --res; 284 } 285 --pos; 286 } 287 printf("%d\n", res); 288 } 289 290 return 0; 291 } 292 ``` 293 294 [1674G - Remove Directed Edges](/contest/1674/problem/G "Codeforces Round 786 (Div. 3)") 295 296 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 297 298 **Tutorial** 299 300 Tutorial is loading... 301 302 **Solution (awoo)** 303 304 ``` 305 #include <bits/stdc++.h> 306 307 #define forn(i, n) for (int i = 0; i < int(n); i++) 308 309 using namespace std; 310 311 const int INF = 1e9; 312 313 vector<int> in, out; 314 vector<vector<int>> g; 315 vector<int> dp; 316 317 int calc(int v){ 318 if (dp[v] != -1) return dp[v]; 319 if (in[v] >= 2 && out[v] >= 2){ 320 dp[v] = 1; 321 for (int u : g[v]) 322 dp[v] = max(dp[v], calc(u) + 1); 323 } 324 else if (in[v] >= 2){ 325 dp[v] = 1; 326 } 327 else{ 328 dp[v] = -INF; 329 } 330 return dp[v]; 331 } 332 333 int main() { 334 int n, m; 335 scanf("%d%d", &n, &m); 336 g.resize(n); 337 in.resize(n); 338 out.resize(n); 339 forn(i, m){ 340 int v, u; 341 scanf("%d%d", &v, &u); 342 --v, --u; 343 g[v].push_back(u); 344 ++in[u]; 345 ++out[v]; 346 } 347 int ans = 1; 348 dp.resize(n, -1); 349 forn(v, n) if (out[v] >= 2){ 350 for (int u : g[v]){ 351 ans = max(ans, calc(u) + 1); 352 } 353 } 354 printf("%d\n", ans); 355 return 0; 356 } 357 ```