codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```