codeforces-scrape

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

1490.md (6265B)


      1 Source: https://codeforces.com/blog/entry/87874
      2 
      3 [1490A - Dense Array](/contest/1490/problem/A "Codeforces Round 702 (Div. 3)")
      4 
      5 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 using ll = long long;
     18 
     19 void solve() {
     20   int n;
     21   cin >> n;
     22   int last;
     23   cin >> last;
     24   int ans = 0;
     25   for (int i = 1; i < n; i++) {
     26     int nw;
     27     cin >> nw;
     28     int a = min(last, nw), b = max(last, nw);
     29     while (a * 2 < b) {
     30       ans++;
     31       a *= 2;
     32     }
     33     last = nw;
     34   }
     35   cout << ans << "\n";
     36 }
     37 
     38 int main() {
     39   int t;
     40   cin >> t;
     41   while (t--) {
     42     solve();
     43   }
     44 }
     45 ```
     46 
     47 [1490B - Balanced Remainders](/contest/1490/problem/B "Codeforces Round 702 (Div. 3)")
     48 
     49 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     50 
     51 **Editorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution**
     56 
     57 ```
     58 #include <bits/stdc++.h>
     59 
     60 using namespace std;
     61 
     62 void solve() {
     63   int n;
     64   cin >> n;
     65   vector<int> a(n);
     66   for (int &x : a) {
     67     cin >> x;
     68   }
     69 
     70   int res = 0;
     71   vector<int> cnt(3);
     72   for (int x = 0; x <= 2; x++) {
     73       for (int i = 0; i < n; i++) {
     74           if (a[i] % 3 == x) {
     75               cnt[x]++;
     76           }
     77       }
     78   }
     79   
     80   while (*min_element(cnt.begin(), cnt.end()) != n / 3) {
     81       for (int i = 0; i < 3; i++) {
     82           if (cnt[i] > n / 3) {
     83               res++;
     84               cnt[i]--;
     85               cnt[(i + 1) % 3]++;
     86           }
     87       }
     88   }
     89   cout << res << endl;
     90 }
     91 
     92 int main() {
     93   int t;
     94   cin >> t;
     95   while (t--) {
     96     solve();
     97   }
     98 }
     99 ```
    100 
    101 [1490C - Sum of Cubes](/contest/1490/problem/C "Codeforces Round 702 (Div. 3)")
    102 
    103 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    104 
    105 **Editorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 using ll = long long;
    116 using ld = long double;
    117 
    118 const ll N = 1'000'000'000'000L;
    119 
    120 unordered_set<ll> cubes;
    121 
    122 void precalc() {
    123   for (ll i = 1; i * i * i <= N; i++) {
    124     cubes.insert(i * i * i);
    125   }
    126 }
    127 
    128 void solve() {
    129   ll x;
    130   cin >> x;
    131   for (ll i = 1; i * i * i <= x; i++) {
    132     if (cubes.count(x - i * i * i)) {
    133       cout << "YES\n";
    134       return;
    135     }
    136   }
    137   cout << "NO\n";
    138 }
    139 
    140 int main() {
    141   precalc();
    142   int t;
    143   cin >> t;
    144   while (t--) {
    145     solve();
    146   }
    147 }
    148 ```
    149 
    150 [1490D - Permutation Transformation](/contest/1490/problem/D "Codeforces Round 702 (Div. 3)")
    151 
    152 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    153 
    154 **Editorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 
    163 using namespace std;
    164 
    165 void build(int l, int r, vector<int> const &a, vector<int> &d, int curD = 0) {
    166   if (r < l) {
    167     return;
    168   }
    169   if (l == r) {
    170     d[l] = curD;
    171     return;
    172   }
    173   int m = l;
    174   for (int i = l + 1; i <= r; i++) {
    175     if (a[m] < a[i]) {
    176       m = i;
    177     }
    178   }
    179   d[m] = curD;
    180   build(l, m - 1, a, d, curD + 1);
    181   build(m + 1, r, a, d, curD + 1);
    182 }
    183 
    184 void solve() {
    185   int n;
    186   cin >> n;
    187   vector<int> a(n);
    188   for (int &x : a) {
    189     cin >> x;
    190   }
    191   vector<int> d(n);
    192   build(0, n - 1, a, d);
    193   for (int x :d) {
    194     cout << x << " ";
    195   }
    196   cout << endl;
    197 }
    198 
    199 int main() {
    200   int t;
    201   cin >> t;
    202   while (t--) {
    203     solve();
    204   }
    205 }
    206 ```
    207 
    208 [1490E - Accidental Victory](/contest/1490/problem/E "Codeforces Round 702 (Div. 3)")
    209 
    210 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    211 
    212 **Editorial**
    213 
    214 Tutorial is loading...
    215 
    216 **Solution**
    217 
    218 ```
    219 def win(pos : int, a : list):
    220     power = a[pos]
    221     for i in range(len(a)):
    222         if i == pos:
    223             continue
    224         if power < a[i]:
    225             return False
    226         power += a[i]
    227     return True
    228 
    229 t = int(input())
    230 
    231 while t > 0:
    232     t -= 1
    233     n = int(input())
    234     a = list(map(int, input().split(' ')))
    235     b = a.copy()
    236     a.sort()
    237 
    238     l = -1
    239     r = n - 1
    240     while r - l > 1:
    241         m = (l + r) // 2
    242         if (win(m, a)):
    243             r = m
    244         else:
    245             l = m
    246 
    247     winIds = []
    248     for i in range(n):
    249         if b[i] >= a[r]:
    250             winIds.append(i + 1)
    251 
    252     print(len(winIds))
    253     print(*winIds)
    254 ```
    255 
    256 [1490F - Equalize the Array](/contest/1490/problem/F "Codeforces Round 702 (Div. 3)")
    257 
    258 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    259 
    260 **Editorial**
    261 
    262 Tutorial is loading...
    263 
    264 **Solution**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 using namespace std;
    269 
    270 void solve() {
    271   int n;
    272   cin >> n;
    273   map<int, int> cnt;
    274   for (int i = 0; i < n; i++) {
    275     int x;
    276     cin >> x;
    277     cnt[x]++;
    278   }
    279   map<int, int> groupedByCnt;
    280   for (auto[x, y] : cnt) {
    281     groupedByCnt[y]++;
    282   }
    283 
    284   int res = n;
    285   int left = 0, right = n, rightCnt = (int) cnt.size();
    286   for (auto[x, y] : groupedByCnt) {
    287     res = min(res, left + right - rightCnt * x);
    288     left += x * y;
    289     right -= x * y;
    290     rightCnt -= y;
    291   }
    292   cout << res << endl;
    293 }
    294 
    295 int main() {
    296   int tests;
    297   cin >> tests;
    298   while (tests-- > 0) {
    299     solve();
    300   }
    301   return 0;
    302 }
    303 ```
    304 
    305 [1490G - Old Floppy Drive](/contest/1490/problem/G "Codeforces Round 702 (Div. 3)")
    306 
    307 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [sodafago](/profile/sodafago "Specialist sodafago")
    308 
    309 **Editorial**
    310 
    311 Tutorial is loading...
    312 
    313 **Solution**
    314 
    315 ```
    316 #include <bits/stdc++.h>
    317 
    318 using namespace std;
    319 using ll = long long;
    320 
    321 void solve() {
    322   int n, m;
    323   cin >> n >> m;
    324   vector<ll> a(n);
    325   ll allSum = 0;
    326   vector<ll> pref;
    327   vector<int> ind;
    328   int curInd = 0;
    329   for (ll &e : a) {
    330     cin >> e;
    331     allSum += e;
    332     if (pref.empty() || allSum > pref.back()) {
    333       pref.push_back(allSum);
    334       ind.push_back(curInd);
    335     }
    336     curInd++;
    337   }
    338   for (int q = 0; q < m; q++) {
    339     ll x;
    340     cin >> x;
    341     if (pref.back() < x && allSum <= 0) {
    342       cout << -1 << " ";
    343       continue;
    344     }
    345     ll needTimes = 0;
    346     if (pref.back() < x) {
    347       needTimes = (x - pref.back() + allSum - 1) / allSum;
    348     }
    349     x -= needTimes * allSum;
    350     cout << needTimes * n + ind[lower_bound(pref.begin(), pref.end(), x) - pref.begin()] << " ";
    351   }
    352   cout << "\n";
    353 }
    354 
    355 int main() {
    356   int t;
    357   cin >> t;
    358   while (t--) {
    359     solve();
    360   }
    361 }
    362 ```