codeforces-scrape

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

1520.md (8835B)


      1 Source: https://codeforces.com/blog/entry/90342
      2 
      3 [1520A - Do Not Be Distracted!](/contest/1520/problem/A "Codeforces Round 719 (Div. 3)")
      4 
      5 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      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 using ll = long long;
     19 using ld = long double;
     20 using pii = pair<int, int>;
     21 using cd = complex<ld>;
     22 
     23 void solve() {
     24     int n;
     25     cin >> n;
     26     string s;
     27     cin >> s;
     28     for (char c = 'A'; c <= 'Z'; c++) {
     29         int first = n;
     30         int last = -1;
     31         for (int i = 0; i < n; i++) {
     32             if (s[i] == c) {
     33                 first = min(first, i);
     34                 last = max(last, i);
     35             }
     36         }
     37         for (int i = first; i <= last; i++) {
     38             if (s[i] != c) {
     39                 cout << "NO\n";
     40                 return;
     41             }
     42         }
     43     }
     44     cout << "YES\n";
     45 }
     46 
     47 int main() {
     48     ios_base::sync_with_stdio(false);
     49     cin.tie(nullptr);
     50     int t;
     51     cin >> t;
     52     while (t--) {
     53         solve();
     54     }
     55 }
     56 ```
     57 
     58 [1520B - Ordinary Numbers](/contest/1520/problem/B "Codeforces Round 719 (Div. 3)")
     59 
     60 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     61 
     62 **Tutorial**
     63 
     64 Tutorial is loading...
     65 
     66 **Solution**
     67 
     68 ```
     69 #include <bits/stdc++.h>
     70 using namespace std;
     71 
     72 using ll = long long;
     73 
     74 void solve() {
     75   int n;
     76   cin >> n;
     77   int res = 0;
     78   for (ll pw = 1; pw <= n; pw = pw * 10 + 1) {
     79     for (int d = 1; d <= 9;  d++) {
     80       if (pw * d <= n) {
     81         res++;
     82       }
     83     }
     84   }
     85   cout << res << endl;
     86 }
     87 
     88 int main() {
     89   int tests;
     90   cin >> tests;
     91   while (tests-- > 0) {
     92     solve();
     93   }
     94   return 0;
     95 }
     96 ```
     97 
     98 [1520C - Not Adjacent Matrix](/contest/1520/problem/C "Codeforces Round 719 (Div. 3)")
     99 
    100 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110 using namespace std;
    111 
    112 void solve() {
    113   int n;
    114   cin >> n;
    115   if (n == 1) {
    116     cout << "1" << endl;
    117     return;
    118   } else if (n == 2) {
    119     cout << "-1" << endl;
    120     return;
    121   }
    122   vector<vector<int>> a(n, vector<int>(n));
    123   a[0][0] = 1;
    124   a[n - 1][n - 1] = n * n;
    125   int x = n * n - 1;
    126   for (int i = 1; i + 1 < n; i++) {
    127     for (int j = i; j >= 0; j--, x--) {
    128       a[i - j][j] = x;
    129     }
    130   }
    131   x = 2;
    132   for (int j = n - 2; j > 0; j--) {
    133     for (int i = 0; i < n - j; i++, x++) {
    134       a[n - i - 1][j + i] = x;
    135     }
    136   }
    137   for (int i = n - 1; i >= 0; i--, x++) {
    138     a[i][n - i - 1] = x;
    139   }
    140   for (int i = 0; i < n; i++) {
    141     for (int j = 0; j < n; j++) {
    142       cout << a[i][j] << " ";
    143     }
    144     cout << endl;
    145   }
    146 }
    147 
    148 int main() {
    149   int tests;
    150   cin >> tests;
    151   while (tests-- > 0) {
    152     solve();
    153   }
    154   return 0;
    155 }
    156 ```
    157 
    158 [1520D - Same Differences](/contest/1520/problem/D "Codeforces Round 719 (Div. 3)")
    159 
    160 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution**
    167 
    168 ```
    169 #include <bits/stdc++.h>
    170 using namespace std;
    171 
    172 void solve() {
    173   int n;
    174   cin >> n;
    175   map<int, int> a;
    176   long long res = 0;
    177   for (int i = 0; i < n; i++) {
    178     int x;
    179     cin >> x;
    180     x -= i;
    181     res += a[x];
    182     a[x]++;
    183   }
    184   cout << res << endl;
    185 }
    186 
    187 int main() {
    188   int tests;
    189   cin >> tests;
    190   while (tests-- > 0) {
    191     solve();
    192   }
    193   return 0;
    194 }
    195 ```
    196 
    197 [1520E - Arranging The Sheep](/contest/1520/problem/E "Codeforces Round 719 (Div. 3)")
    198 
    199 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution**
    206 
    207 ```
    208 #include<bits/stdc++.h>
    209  
    210 using namespace std;
    211  
    212 void solve()
    213 {
    214 	int n;
    215 	cin >> n;
    216 	string s;
    217 	cin >> s;
    218 	int cnt = 0;
    219 	for(auto x : s)
    220 		cnt += (x == '*' ? 1 : 0);
    221 	int pos = -1;
    222 	int cur = -1;
    223 	for(int i = 0; i < n; i++)
    224 	{
    225 	 	if(s[i] == '*')
    226 	 	{
    227 	 	    cur++;
    228 	 	    if(cur == cnt / 2)
    229 	 	    	pos = i;
    230 	 	}	
    231 	}
    232 	long long ans = 0;
    233 	cur = pos - cnt / 2;
    234 	for(int i = 0; i < n; i++)
    235 		if(s[i] == '*')
    236 		{
    237 		 	ans += abs(cur - i);
    238 		 	cur++;
    239 		}
    240 	cout << ans << endl;
    241 }
    242  
    243 int main()
    244 {
    245 	ios_base::sync_with_stdio(0);
    246 	cin.tie(0);
    247 	int tc = 1;
    248 	cin >> tc;
    249 	for(int i = 0; i < tc; i++)
    250 	{
    251 	 	solve();
    252 	}
    253 }
    254 ```
    255 
    256 [1520F1 - Guess the K-th Zero (Easy version)](/contest/1520/problem/F1 "Codeforces Round 719 (Div. 3)")
    257 
    258 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly")
    259 
    260 **Tutorial**
    261 
    262 Tutorial is loading...
    263 
    264 **Solution**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 
    269 using namespace std;
    270 
    271 using ll = long long;
    272 using ld = long double;
    273 using pii = pair<int, int>;
    274 using cd = complex<ld>;
    275 
    276 void calc(int l, int r, int k) {
    277     if (l == r) {
    278         cout << "! " << l << endl;
    279         return;
    280     }
    281     int m = (l + r) / 2;
    282     cout << "? " << l << " " << m << endl;
    283     int sum;
    284     cin >> sum;
    285     if ((m - l + 1) - sum >= k) {
    286         calc(l, m, k);
    287     } else {
    288         calc(m + 1, r, k - (m - l + 1) + sum);
    289     }
    290 }
    291 
    292 int main() {
    293     ios_base::sync_with_stdio(false);
    294     cin.tie(nullptr);
    295     int n, t, k;
    296     cin >> n >> t >> k;
    297     calc(1, n, k);
    298 }
    299 ```
    300 
    301 [1520F2 - Guess the K-th Zero (Hard version)](/contest/1520/problem/F2 "Codeforces Round 719 (Div. 3)")
    302 
    303 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    304 
    305 **Tutorial**
    306 
    307 Tutorial is loading...
    308 
    309 **Solution**
    310 
    311 ```
    312 #include <bits/stdc++.h>
    313 
    314 using namespace std;
    315 
    316 #define forn(i, n) for (int i = 0; i < int(n); i++)
    317 
    318 map<pair<int,int>, int> cache;
    319 
    320 void dec(int pos, int L, int R) {
    321     cache[{L, R}]--;
    322 
    323     if (L != R) {
    324         int M = (L + R) / 2;
    325         if (pos <= M)
    326             dec(pos, L, M);
    327         else
    328             dec(pos, M + 1, R);
    329     }
    330 }
    331 
    332 int main() {
    333     int n, cases;
    334     cin >> n >> cases;
    335     forn(case_, cases) {
    336         int k;
    337         cin >> k;
    338         int L = 0, R = n - 1;
    339         while (L != R) {
    340             int M = (L + R) / 2;
    341             
    342             pair<int,int> range = make_pair(L, M);
    343             if (cache.count(range) == 0) {
    344                 cout << "? " << range.first + 1 << " " << range.second + 1 << endl;
    345                 cin >> cache[range];
    346                 cache[range] = range.second - range.first + 1 - cache[range];
    347             }
    348 
    349             int value = cache[range];
    350             if (k <= value)
    351                 R = M;
    352             else {
    353                 k -= value;
    354                 L = M + 1;
    355             }
    356         }
    357 
    358         cout << "! " << L + 1 << endl;
    359         dec(L, 0, n - 1);
    360     }
    361 }
    362 ```
    363 
    364 [1520G - To Go Or Not To Go?](/contest/1520/problem/G "Codeforces Round 719 (Div. 3)")
    365 
    366 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly"), [Aris](/profile/Aris "Candidate Master Aris")
    367 
    368 **Tutorial**
    369 
    370 Tutorial is loading...
    371 
    372 **Solution**
    373 
    374 ```
    375 #include <bits/stdc++.h>
    376 
    377 using namespace std;
    378 
    379 using ll = long long;
    380 using ld = long double;
    381 using pii = pair<int, int>;
    382 using cd = complex<ld>;
    383 
    384 const int MAX_N = 2010;
    385 
    386 int dd[4][2] = {
    387         {1, 0},
    388         {0, 1},
    389         {-1, 0},
    390         {0, -1}
    391 };
    392 
    393 void bfs(int sx, int sy, vector<vector<int>> &d, vector<vector<int>> &a) {
    394     int n = d.size();
    395     int m = d[0].size();
    396     queue<pair<int, int>> q;
    397     q.push({sx, sy});
    398     d[sx][sy] = 1;
    399     while (!q.empty()) {
    400         auto [x, y] = q.front();
    401         q.pop();
    402         for (auto [dx, dy] : dd) {
    403             int tx = x + dx;
    404             int ty = y + dy;
    405             if (tx >= 0 && ty >= 0 && tx < n && ty < m && d[tx][ty] == 0 && a[tx][ty] != -1) {
    406                 d[tx][ty] = d[x][y] + 1;
    407                 q.push({tx, ty});
    408             }
    409         }
    410     }
    411     for (auto &e : d) {
    412         for (auto &i : e) {
    413             i--;
    414         }
    415     }
    416 }
    417 
    418 int main() {
    419     ios_base::sync_with_stdio(false);
    420     cin.tie(nullptr);
    421     int n, m, w;
    422     cin >> n >> m >> w;
    423     vector<vector<int>> a(n, vector<int>(m));
    424     vector<vector<int>> d1(n, vector<int>(m));
    425     vector<vector<int>> d2(n, vector<int>(m));
    426     for (int i = 0; i < n; i++) {
    427         for (int j = 0; j < m; j++) {
    428             cin >> a[i][j];
    429         }
    430     }
    431     bfs(0, 0, d1, a);
    432     bfs(n - 1, m - 1, d2, a);
    433     ll bestFinish = 1e18;
    434     for (int i = 0; i < n; i++) {
    435         for (int j = 0; j < m; j++) {
    436             if (d2[i][j] != -1 && a[i][j] >= 1) {
    437                 bestFinish = min(bestFinish, a[i][j] + w * 1ll * d2[i][j]);
    438             }
    439         }
    440     }
    441     ll ans = w * 1ll * d1[n - 1][m - 1];
    442     if (d1[n - 1][m - 1] == -1) {
    443         ans = 1e18;
    444     }
    445     for (int i = 0; i < n; i++) {
    446         for (int j = 0; j < m; j++) {
    447             if (d1[i][j] != -1 && a[i][j] >= 1 && bestFinish != 1e18) {
    448                 ans = min(ans, w * 1ll * d1[i][j] + a[i][j] + bestFinish);
    449             }
    450         }
    451     }
    452     if (ans == 1e18) {
    453         cout << -1;
    454     } else {
    455         cout << ans;
    456     }
    457 }
    458 ```