codeforces-scrape

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

1512.md (8237B)


      1 Source: https://codeforces.com/blog/entry/89535
      2 
      3 [1512A - Spy Detected!](/contest/1512/problem/A "Codeforces Round 713 (Div. 3)")
      4 
      5 Author: [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 typedef long long ll;
     19 
     20 void solve() {
     21     int n;
     22     cin >> n;
     23     vector<int> v(n);
     24     for (int &e : v) {
     25         cin >> e;
     26     }
     27     vector<int> a = v;
     28     sort(a.begin(), a.end());
     29     for (int i = 0; i < n; i++) {
     30         if (v[i] != a[1]) {
     31             cout << i + 1 << "\n";
     32         }
     33     }
     34 }
     35 
     36 int main() {
     37     int n;
     38     cin >> n;
     39     while (n--) {
     40         solve();
     41     }
     42     return 0;
     43 }
     44 ```
     45 
     46 [1512B - Almost Rectangle](/contest/1512/problem/B "Codeforces Round 713 (Div. 3)")
     47 
     48 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 #define forn(i, n) for (int i = 0; i < int(n); i++)
     62 
     63 int main() {    
     64     int t;
     65     cin >> t;
     66     forn(tt, t) {
     67         int n;
     68         cin >> n;
     69         vector<string> f(n);
     70         vector<pair<int,int>> p;
     71         forn(i, n) {
     72             cin >> f[i];
     73             forn(j, n)
     74                 if (f[i][j] == '*')
     75                     p.push_back({i, j});
     76         }
     77 
     78         p.push_back(p[0]);
     79         p.push_back(p[1]);
     80         if (p[0].first == p[1].first) {
     81             p[2].first = (p[2].first + 1) % n;
     82             p[3].first = (p[3].first + 1) % n;
     83         } else if (p[0].second == p[1].second) {
     84             p[2].second = (p[2].second + 1) % n;
     85             p[3].second = (p[3].second + 1) % n;
     86         } else
     87             swap(p[2].first, p[3].first);
     88 
     89         f[p[2].first][p[2].second] = '*';
     90         f[p[3].first][p[3].second] = '*';
     91         forn(i, n)
     92             cout << f[i] << endl;
     93     }
     94 }
     95 ```
     96 
     97 [1512C - A-B Palindrome](/contest/1512/problem/C "Codeforces Round 713 (Div. 3)")
     98 
     99 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 using namespace std;
    110 
    111 void no() {
    112   cout << "-1" << endl;
    113 }
    114 
    115 void solve() {
    116   int a, b;
    117   cin >> a >> b;
    118   string s;
    119   cin >> s;
    120   for (int times = 0; times < 2; times++) {
    121     for (int i = 0; i < (int) s.size(); i++) {
    122       int j = (int) s.size() - i - 1;
    123       if (s[i] != '?') {
    124         if (s[j] == '?') {
    125           s[j] = s[i];
    126         } else if (s[i] != s[j]) {
    127           no();
    128           return;
    129         }
    130       }
    131     }
    132     reverse(s.begin(), s.end());
    133   }
    134   a -= count(s.begin(), s.end(), '0');
    135   b -= count(s.begin(), s.end(), '1');
    136   int ques = count(s.begin(), s.end(), '?');
    137   bool emptyMid = (s.size() % 2 == 1 && s[s.size() / 2] == '?');
    138   if (a < 0 || b < 0 || a + b != ques || (emptyMid && a % 2 == 0 && b % 2 == 0)) {
    139     no();
    140     return;
    141   }
    142   if (a % 2 == 1 || b % 2 == 1) {
    143     int i = s.size() / 2;
    144     if (s[i] != '?') {
    145       no();
    146       return;
    147     }
    148     s[i] = (a % 2 == 1 ? '0' : '1');
    149     if (a % 2 == 1) {
    150       a--;
    151     } else {
    152       b--;
    153     }
    154   }
    155   if (a % 2 == 1 || b % 2 == 1) {
    156     no();
    157     return;
    158   }
    159   for (int i = 0; i < (int) s.size(); i++) {
    160     if (s[i] == '?') {
    161       int j = s.size() - i - 1;
    162       if (a > 0) {
    163         a -= 2;
    164         s[i] = s[j] = '0';
    165       } else {
    166         b -= 2;
    167         s[i] = s[j] = '1';
    168       }
    169     }
    170   }
    171   cout << s << endl;
    172 }
    173 
    174 int main() {
    175   int tests;
    176   cin >> tests;
    177   while (tests-- > 0) {
    178     solve();
    179   }
    180   return 0;
    181 }
    182 ```
    183 
    184 [1512D - Corrupted Array](/contest/1512/problem/D "Codeforces Round 713 (Div. 3)")
    185 
    186 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    187 
    188 **Tutorial**
    189 
    190 Tutorial is loading...
    191 
    192 **Solution**
    193 
    194 ```
    195 #include <bits/stdc++.h>
    196 using namespace std;
    197 
    198 void no() {
    199   cout << "-1" << endl;
    200 }
    201 
    202 void solve() {
    203   int n;
    204   cin >> n;
    205   vector<int> b(n + 2);
    206   for (int &x : b) {
    207     cin >> x;
    208   }
    209 
    210   multiset<int> have(b.begin(), b.end());
    211   long long sum = accumulate(b.begin(), b.end(), 0LL);
    212   for (int x : b) {
    213     have.erase(have.find(x));
    214     sum -= x;
    215     if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end()) {
    216       have.erase(have.find(sum / 2));
    217       for (int y : have) {
    218         cout << y << " ";
    219       }
    220       cout << endl;
    221       return;
    222     }
    223     sum += x;
    224     have.insert(x);
    225   }
    226   no();
    227 }
    228 
    229 int main() {
    230   int tests;
    231   cin >> tests;
    232   while (tests-- > 0) {
    233     solve();
    234   }
    235   return 0;
    236 }
    237 ```
    238 
    239 [1512E - Permutation by Sum](/contest/1512/problem/E "Codeforces Round 713 (Div. 3)")
    240 
    241 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    242 
    243 **Tutorial**
    244 
    245 Tutorial is loading...
    246 
    247 **Solution**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251 
    252 using namespace std;
    253 using ll = long long;
    254 
    255 void solve() {
    256     int n, l, r, s;
    257     cin >> n >> l >> r >> s;
    258     l--; r--;
    259     for (int first = 1; first + (r - l) <= n; first++) {
    260         int sum = 0;
    261         for (int i = l; i <= r; i++) {
    262             sum += first + (i - l);
    263         }
    264         if (sum <= s && s - sum <= r - l + 1) {
    265             int needAdd = r - (s - sum) + 1;
    266             vector<int> ans(n);
    267             set<int> non_blocked;
    268             for (int i = 1; i <= n; i++) {
    269                 non_blocked.insert(i);
    270             }
    271             for (int i = l; i <= r; i++) {
    272                 ans[i] = first + (i - l);
    273                 if (i >= needAdd) {
    274                     ans[i]++;
    275                 }
    276                 non_blocked.erase(ans[i]);
    277             }
    278             if (ans[r] > n) {
    279                 continue;
    280             }
    281             non_blocked.erase(ans[r]);
    282             for (int i = 0; i < l; i++) {
    283                 ans[i] = *non_blocked.begin();
    284                 non_blocked.erase(non_blocked.begin());
    285             }
    286             for (int i = r + 1; i < n; i++) {
    287                 ans[i] = *non_blocked.begin();
    288                 non_blocked.erase(non_blocked.begin());
    289             }
    290             for (int i : ans) {
    291                 cout << i << " ";
    292             }
    293             cout << "\n";
    294             return;
    295         }
    296     }
    297     cout << "-1\n";
    298 }
    299 
    300 int main() {
    301     ios_base::sync_with_stdio(false);
    302     cin.tie(nullptr); cout.tie(nullptr);
    303     int n;
    304     cin >> n;
    305     while (n--) {
    306         solve();
    307     }
    308 }
    309 ```
    310 
    311 [1512F - Education](/contest/1512/problem/F "Codeforces Round 713 (Div. 3)")
    312 
    313 Author: [sodafago](/profile/sodafago "Specialist sodafago")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution**
    320 
    321 ```
    322 #include <bits/stdc++.h>
    323 
    324 using namespace std;
    325 
    326 typedef long long ll;
    327 
    328 void solve() {
    329     int n, c;
    330     cin >> n >> c;
    331     vector<int> a(n);
    332     vector<int> b(n - 1);
    333     for (int &e : a) {
    334         cin >> e;
    335     }
    336     for (int &e : b) {
    337         cin >> e;
    338     }
    339     b.push_back(0);
    340     ll ans = 1e18;
    341     ll cur = 0;
    342     ll bal = 0;
    343     for (int i = 0; i < n; i++) {
    344         ans = min(ans, cur + max(0ll, c - bal + a[i] - 1) / a[i]);
    345         ll newDays = max(0ll, b[i] - bal + a[i] - 1) / a[i];
    346         cur += newDays + 1;
    347         bal += a[i] * newDays - b[i];
    348     }
    349     cout << ans << "\n";
    350 }
    351 
    352 int main() {
    353     int n;
    354     cin >> n;
    355     while (n--) {
    356         solve();
    357     }
    358     return 0;
    359 }
    360 ```
    361 
    362 [1512G - Short Task](/contest/1512/problem/G "Codeforces Round 713 (Div. 3)")
    363 
    364 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    365 
    366 **Tutorial**
    367 
    368 Tutorial is loading...
    369 
    370 **Solution**
    371 
    372 ```
    373 #include <bits/stdc++.h>
    374 using namespace std;
    375 
    376 const int N = (int) 1e7 + 100;
    377 
    378 long long s[N];
    379 int d[N];
    380 int ans[N];
    381 
    382 int main() {
    383   fill(d, d + N, -1);
    384   d[1] = 1;
    385   for (int i = 2; i * i < N; i++) {
    386     if (d[i] == -1) {
    387       d[i] = i;
    388       for (int j = i * i; j < N; j += i) {
    389         if (d[j] == -1) {
    390           d[j] = i;
    391         }
    392       }
    393     }
    394   }
    395   s[1] = 1;
    396   for (int i = 2; i < N; i++) {
    397     if (d[i] == -1) {
    398       d[i] = i;
    399       s[i] = i + 1;
    400     } else {
    401       int j = i;
    402       s[i] = 1;
    403       while (j % d[i] == 0) {
    404         j /= d[i];
    405         s[i] = s[i] * d[i] + 1;
    406       }
    407       s[i] *= s[j];
    408     }
    409   }
    410   fill(ans, ans + N, -1);
    411   for (int i = N - 1; i > 0; i--) {
    412     if (s[i] < N) {
    413       ans[s[i]] = i;
    414     }
    415   }
    416   int tests;
    417   cin >> tests;
    418   while (tests-- > 0) {
    419     int c;
    420     cin >> c;
    421     cout << ans[c] << endl;
    422   }
    423   return 0;
    424 }
    425 ```