1202.md (8015B)
1 Source: https://codeforces.com/blog/entry/68972 2 3 [1202A - You Are Given Two Binary Strings...](/contest/1202/problem/A "Educational Codeforces Round 70 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main(args: Array<String>) { 15 val T = readLine()!!.toInt() 16 for (tc in 1..T) { 17 val x = readLine()!!.reversed() 18 val y = readLine()!!.reversed() 19 20 val posY = y.indexOf('1') 21 val posX = x.indexOf('1', posY) 22 println(posX - posY) 23 } 24 } 25 ``` 26 27 [1202B - You Are Given a Decimal String...](/contest/1202/problem/B "Educational Codeforces Round 70 (Rated for Div. 2)") 28 29 Idea: [adedalic](/profile/adedalic "International Master adedalic") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (adedalic)** 36 37 ``` 38 const val INF = 1e9.toInt() 39 40 fun main(args: Array<String>) { 41 val s = readLine()!!.map { it - '0' } 42 val cf = Array(10) {Array(10) {0}} 43 for (i in 1 until s.size) 44 cf[s[i - 1]][s[i]]++ 45 46 for (x in 0..9) { 47 for (y in 0..9) { 48 val ds = Array(10) {Array(10) {INF + 7}} 49 50 for (v in 0..9) { 51 for (cx in 0..9) { 52 for (cy in 0..9) { 53 if (cx + cy == 0) 54 continue 55 56 val to = (v + cx * x + cy * y) % 10 57 ds[v][to] = minOf(ds[v][to], cx + cy) 58 } 59 } 60 } 61 62 var res = 0 63 for (v in 0..9) { 64 for (to in 0..9) { 65 if (ds[v][to] > INF && cf[v][to] > 0) { 66 res = -1 67 break 68 } 69 res += (ds[v][to] - 1) * cf[v][to] 70 } 71 if (res == -1) 72 break 73 } 74 75 print("$res ") 76 } 77 println() 78 } 79 } 80 ``` 81 82 [1202C - You Are Given a WASD-string...](/contest/1202/problem/C "Educational Codeforces Round 70 (Rated for Div. 2)") 83 84 Idea: [adedalic](/profile/adedalic "International Master adedalic") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution (adedalic)** 91 92 ``` 93 const val INF = 1e9.toInt() 94 95 fun main(args: Array<String>) { 96 val T = readLine()!!.toInt() 97 for (tc in 1..T) { 98 val s = readLine()!! 99 val alp = arrayOf("WS", "AD") 100 val aDir = arrayOf( 101 s.filter { alp[0].indexOf(it) != -1 }, 102 s.filter { alp[1].indexOf(it) != -1 } 103 ) 104 105 val baseW = arrayOf(INF, INF) 106 val bestW = arrayOf(INF, INF) 107 108 for (k in 0..1) { 109 val pSum = arrayListOf(0) 110 for (c in aDir[k]) { 111 val add = if (c == alp[k][0]) +1 else -1 112 pSum.add(pSum.last() + add) 113 } 114 115 for (tp in 0..1) { 116 val firstMin = pSum.withIndex().minBy { it.value }!!.index 117 val lastMax = pSum.withIndex().reversed().maxBy { it.value }!!.index 118 119 val curBase = pSum[lastMax] - pSum[firstMin] + 1 120 var curBest = curBase 121 if (curBase > 2 && lastMax < firstMin) 122 --curBest 123 124 baseW[k] = minOf(baseW[k], curBase) 125 bestW[k] = minOf(bestW[k], curBest) 126 127 for (i in pSum.indices) 128 pSum[i] = -pSum[i] 129 } 130 } 131 132 println("${minOf(baseW[0] * 1L * bestW[1], baseW[1] * 1L * bestW[0] )}") 133 } 134 } 135 ``` 136 137 [1202D - Print a 1337-string...](/contest/1202/problem/D "Educational Codeforces Round 70 (Rated for Div. 2)") 138 139 Idea: [Roms](/profile/Roms "Master Roms") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution (Roms)** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 using namespace std; 151 152 int main() { 153 int t; 154 cin >> t; 155 for(int tc = 0; tc < t; ++tc){ 156 int n; 157 cin >> n; 158 int len = 2; 159 while(len * (len + 1) / 2 <= n) 160 ++len; 161 162 n -= len * (len - 1) / 2; 163 assert(n >= 0); 164 assert(n <= 45000); 165 166 string s = "133"; 167 while(n > 0){ 168 --n; 169 s += "7"; 170 } 171 172 len -= 2; 173 while(len > 0){ 174 --len; 175 s += "3"; 176 } 177 s += "7"; 178 cout << s << endl; 179 } 180 return 0; 181 } 182 ``` 183 184 [1202E - You Are Given Some Strings...](/contest/1202/problem/E "Educational Codeforces Round 70 (Rated for Div. 2)") 185 186 Idea: [Roms](/profile/Roms "Master Roms") 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 **Solution (adedalic)** 193 194 ``` 195 #include<bits/stdc++.h> 196 using namespace std; 197 198 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 199 #define forn(i, n) fore(i, 0, n) 200 201 #define sz(a) (int)(a).size() 202 #define all(a) (a).begin(), (a).end() 203 204 #define x first 205 #define y second 206 207 typedef long long li; 208 typedef pair<int, int> pt; 209 210 const int INF = int(1e9) + 7; 211 const li INF64 = li(1e18) + 7; 212 213 const int N = 500005; 214 const int A = 27; 215 const int MAG = 500; 216 217 struct node { 218 node *to[A]; 219 int cnt; 220 } nodes[N]; 221 int szn = 0; 222 223 typedef node* vt; 224 225 vt getNode() { 226 assert(szn < N); 227 fore(i, 0, A) 228 nodes[szn].to[i] = NULL; 229 nodes[szn].cnt = 0; 230 return &nodes[szn++]; 231 } 232 233 void addWord(vt v, const string &s) { 234 fore(i, 0, sz(s)) { 235 int c = s[i] - 'a'; 236 if (!v->to[c]) 237 v->to[c] = getNode(); 238 v = v->to[c]; 239 } 240 v->cnt++; 241 } 242 243 int calcCnt(vt v, const string &s, int pos) { 244 assert(v->cnt == 0); 245 int ans = 0; 246 while(pos < sz(s)) { 247 int c = s[pos] - 'a'; 248 if (!v->to[c]) 249 break; 250 v = v->to[c]; 251 ans += v->cnt; 252 pos++; 253 } 254 return ans; 255 } 256 257 vector<int> zf(string s) { 258 vector<int> z(sz(s), 0); 259 for (int i = 1, l = 0, r = 0; i < sz(s); ++i) { 260 if(i < r) 261 z[i] = min(r - i, z[i - l]); 262 while (i + z[i] < sz(s) && s[i + z[i]] == s[z[i]]) 263 z[i]++; 264 265 if(i + z[i] > r) 266 l = i, r = i + z[i]; 267 } 268 return z; 269 } 270 271 string t; 272 int n; 273 vector<string> s; 274 275 inline bool read() { 276 if(!(cin >> t)) 277 return false; 278 cin >> n; 279 s.resize(n); 280 fore(i, 0, n) 281 cin >> s[i]; 282 return true; 283 } 284 285 inline void solve() { 286 vector<int> cnt[2]; 287 fore(k, 0, 2) { 288 cnt[k].assign(sz(t) + 1, 0); 289 szn = 0; 290 vt root = getNode(); 291 292 forn(i, n) { 293 if (sz(s[i]) > MAG) { 294 auto z = zf(s[i] + t); 295 fore(j, 0, sz(t)) 296 cnt[k][j] += (z[sz(s[i]) + j] >= sz(s[i])); 297 } else { 298 addWord(root, s[i]); 299 } 300 } 301 302 fore(i, 0, sz(t)) 303 cnt[k][i] += calcCnt(root, t, i); 304 305 reverse(all(t)); 306 fore(i, 0, n) 307 reverse(all(s[i])); 308 } 309 310 li ans = 0; 311 fore(i, 0, sz(t) + 1) 312 ans += cnt[0][i] * 1ll * cnt[1][sz(t) - i]; 313 cout << ans << endl; 314 } 315 316 int main() { 317 #ifdef _DEBUG 318 freopen("input.txt", "r", stdin); 319 int tt = clock(); 320 #endif 321 ios_base::sync_with_stdio(0); 322 cin.tie(0), cout.tie(0); 323 cerr << fixed << setprecision(15); 324 325 if(read()) { 326 solve(); 327 328 #ifdef _DEBUG 329 cerr << "TIME = " << clock() - tt << endl; 330 tt = clock(); 331 #endif 332 } 333 return 0; 334 } 335 ``` 336 337 [1202F - You Are Given Some Letters...](/contest/1202/problem/F "Educational Codeforces Round 70 (Rated for Div. 2)") 338 339 Idea: [adedalic](/profile/adedalic "International Master adedalic") 340 341 **Tutorial** 342 343 Tutorial is loading... 344 345 **Solution (PikMike)** 346 347 ``` 348 #include <bits/stdc++.h> 349 350 #define forn(i, n) for (int i = 0; i < int(n); i++) 351 352 using namespace std; 353 354 int main() { 355 int a, b; 356 scanf("%d%d", &a, &b); 357 358 int n = a + b; 359 int ans = 0; 360 int l = 1; 361 while (l <= n){ 362 int g = n / l; 363 364 if (a < g || b < g){ 365 l = n / g + 1; 366 continue; 367 } 368 369 int r = n / g; 370 371 int a_low = (a + g) / (g + 1); 372 int a_high = a / g; 373 int b_low = (b + g) / (g + 1); 374 int b_high = b / g; 375 376 if (a_low <= a_high && b_low <= b_high) 377 ans += max(0, min(r, a_high + b_high) - max(l, a_low + b_low) + 1); 378 l = r + 1; 379 } 380 381 printf("%d\n", ans); 382 } 383 ```