codeforces-scrape

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

1497.md (8257B)


      1 Source: https://codeforces.com/blog/entry/88677
      2 
      3 We are really sorry to make the round unrated. Anyway, we hope that you enjoyed the problems!
      4 
      5 [1497A - Meximization](/contest/1497/problem/A "Codeforces Round 708 (Div. 2)")
      6 
      7 Idea: [shishyando](/profile/shishyando "Expert shishyando")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 // один манул
     17 #include <bits/stdc++.h>
     18 using namespace std;
     19 
     20 int main() {
     21     int T;
     22     cin >> T;
     23     while (T --> 0) {
     24         int n;
     25         cin >> n;
     26         vector<int> a(n);
     27         for (int i = 0; i < n; ++i) cin >> a[i];
     28         sort(a.begin(), a.end());
     29         vector<int> b;
     30         for (int i = 0; i < n; i++) {
     31             if (i == 0 || a[i] != a[i - 1]) {
     32                 b.emplace_back(a[i]);
     33             }
     34         }
     35         for (int i = 0; i < n; i++) {
     36             if (i > 0 && a[i] == a[i - 1]) {
     37                 b.emplace_back(a[i]);
     38             }
     39         }
     40         for (auto x : b) cout << x << ' ';
     41         cout << '\n';
     42     }
     43     return 0;
     44     cout << "amogus";
     45 }
     46 ```
     47 
     48 [1497B - M-arrays](/contest/1497/problem/B "Codeforces Round 708 (Div. 2)")
     49 
     50 Idea: [Artyom123](/profile/Artyom123 "Master Artyom123")
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Implementation**
     57 
     58 ```
     59 //два манула
     60 #include <bits/stdc++.h>
     61 using namespace std;
     62 
     63 int main() {
     64     int t;
     65     cin >> t;
     66     while (t--) {
     67         int n, m;
     68         cin >> n >> m;
     69         map<int, int> cnt;
     70         while (n--) {
     71             int x;
     72             cin >> x;
     73             cnt[x % m]++;
     74         }
     75         int ans = 0;
     76         for (auto &c : cnt) {
     77             if (c.first == 0) ans++;
     78             else if (2 * c.first == m) {
     79                 ans++;
     80             } else if (2 * c.first < m || cnt.find(m - c.first) == cnt.end()) {
     81                 int x = c.second, y = cnt[m - c.first];
     82                 ans += 1 + max(0, abs(x - y) - 1);
     83             }
     84         }
     85         cout << ans << '\n';
     86     }
     87     return 0;
     88 }
     89 ```
     90 
     91 [1497C1 - k-LCM (easy version)](/contest/1497/problem/C1 "Codeforces Round 708 (Div. 2)")
     92 
     93 Idea: [shishyando](/profile/shishyando "Expert shishyando")
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Implementation**
    100 
    101 ```
    102 // три манула
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 
    106 int main() {
    107     int T;
    108     cin >> T;
    109     while (T --> 0) {
    110         int n, k;
    111         cin >> n >> k;
    112         if (n % 2) cout << 1 << ' ' << n / 2 << ' ' << n / 2 << '\n';
    113         else if (n % 2 == 0 && n % 4) cout << 2 << ' ' << n / 2 - 1 << ' ' << n / 2  - 1 << '\n';
    114         else cout << n / 2 << ' ' << n / 4 << ' ' << n / 4 << '\n';
    115     }
    116     return 0;
    117 }
    118 ```
    119 
    120 [1497C2 - k-LCM (hard version)](/contest/1497/problem/C2 "Codeforces Round 708 (Div. 2)")
    121 
    122 Idea: [isaf27](/profile/isaf27 "International Grandmaster isaf27")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Implementation**
    129 
    130 ```
    131 // четыре манула
    132 #include <bits/stdc++.h>
    133 using namespace std;
    134 
    135 vector<int> solve3(int n) {
    136     if (n % 2 == 1) return {1, n / 2, n / 2};
    137     if (n % 4 == 0) return {n / 2, n / 4, n / 4};
    138     if (n % 2 == 0) return {2, n / 2 - 1, n / 2 - 1};
    139 }
    140 
    141 int main() {
    142     int T;
    143     cin >> T;
    144     while (T --> 0) {
    145         int n, k;
    146         cin >> n >> k;
    147         vector<int> added = solve3(n - k + 3);
    148         for (int i = 0; i < k; ++i) {
    149             cout << (i <3 ? added[i] : 1) << ' '; // <3
    150         }
    151         cout << '\n';
    152     }
    153     return 0;
    154 }
    155 ```
    156 
    157 [1497D - Genius](/contest/1497/problem/D "Codeforces Round 708 (Div. 2)")
    158 
    159 Idea: [shishyando](/profile/shishyando "Expert shishyando")
    160 
    161 **Tutorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Implementation**
    166 
    167 ```
    168 // пять манулов
    169 #include <bits/stdc++.h>
    170 using namespace std;
    171 
    172 int main() {
    173     int T;
    174     cin >> T;
    175     while (T --> 0) {
    176         int n;
    177         cin >> n;
    178         vector<long long> s(n), tag(n), dp(n, 0);
    179         for (int i = 0; i < n; ++i) cin >> tag[i];
    180         for (int i = 0; i < n; ++i) cin >> s[i];
    181         for (int j = 1; j < n; ++j) {
    182             for (int i = j - 1; i >= 0; --i) {
    183                 if (tag[i] == tag[j]) continue;
    184                 long long dpi = dp[i], dpj = dp[j], p = abs(s[i] - s[j]);
    185                 dp[i] = max(dp[i], dpj + p);
    186                 dp[j] = max(dp[j], dpi + p);
    187             }
    188         }
    189         cout << *max_element(dp.begin(), dp.end()) << '\n';
    190     }
    191     return 0;
    192 }
    193 ```
    194 
    195 [1497E1 - Square-Free Division (easy version)](/contest/1497/problem/E1 "Codeforces Round 708 (Div. 2)")
    196 
    197 Idea: [Artyom123](/profile/Artyom123 "Master Artyom123")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Implementation**
    204 
    205 ```
    206 // шесть манулов
    207 #include <bits/stdc++.h>
    208 using namespace std;
    209 
    210 const int MAXA = 1e7;
    211 
    212 vector<int> primes;
    213 int mind[MAXA + 1];
    214 
    215 int main() {
    216 
    217     for (int i = 2; i <= MAXA; ++i) {
    218         if (mind[i] == 0) {
    219             primes.emplace_back(i);
    220             mind[i] = i;
    221         }
    222         for (auto &x : primes) {
    223             if (x > mind[i] || x * i > MAXA) break;
    224             mind[x * i] = x;
    225         }
    226     }
    227     
    228     int T;
    229     cin >> T;
    230     while (T --> 0) {
    231         int n, k;
    232         cin >> n >> k;
    233         vector<int> a(n, 1);
    234         for (int i = 0; i < n; ++i) {
    235             int x;
    236             cin >> x;
    237             int cnt = 0, last = 0;
    238             while (x > 1) {
    239                 int p = mind[x];
    240                 if (last == p) {
    241                     ++cnt;
    242                 } else {
    243                     if (cnt % 2 == 1) a[i] *= last;
    244                     last = p;
    245                     cnt = 1;
    246                 }
    247                 x /= p;
    248             }
    249             if (cnt % 2 == 1) a[i] *= last;
    250         }
    251         
    252         int L = 0, ans = 1;
    253         map<int, int> last;
    254         for (int i = 0; i < n; ++i) {
    255             if (last.find(a[i]) != last.end() && last[a[i]] >= L) {
    256                 ++ans;
    257                 L = i;
    258             }
    259             last[a[i]] = i;
    260         }
    261         cout << ans << '\n';
    262     }
    263     
    264     return 0;
    265 }
    266 ```
    267 
    268 [1497E2 - Square-Free Division (hard version)](/contest/1497/problem/E2 "Codeforces Round 708 (Div. 2)")
    269 
    270 Idea: [isaf27](/profile/isaf27 "International Grandmaster isaf27")
    271 
    272 **Tutorial**
    273 
    274 Tutorial is loading...
    275 
    276 **Implementation**
    277 
    278 ```
    279 // семь манулов
    280 #include <bits/stdc++.h>
    281 using namespace std;
    282 
    283 const int INF = 1e9 + 1;
    284 const int MAXA = 1e7;
    285 vector<int> primes;
    286 int mind[MAXA + 1];
    287 
    288 int main() {
    289     for (int i = 2; i <= MAXA; ++i) {
    290         if (mind[i] == 0) {
    291             primes.emplace_back(i);
    292             mind[i] = i;
    293         }
    294         for (auto &x : primes) {
    295             if (x > mind[i] || x * i > MAXA) break;
    296             mind[x * i] = x;
    297         }
    298     }
    299     vector<int> cnt(MAXA + 1);
    300     int t;
    301     cin >> t;
    302     while (t--) {
    303         int n, k;
    304         cin >> n >> k; // уже k манулов
    305         vector<int> a(n, 1);
    306         for (int i = 0; i < n; ++i) {
    307             int x;
    308             cin >> x;
    309             int cnt = 0, last = 0;
    310             while (x > 1) {
    311                 int p = mind[x];
    312                 if (last == p) {
    313                     ++cnt;
    314                 } else {
    315                     if (cnt % 2 == 1) a[i] *= last;
    316                     last = p;
    317                     cnt = 1;
    318                 }
    319                 x /= p;
    320             }
    321             if (cnt % 2 == 1) a[i] *= last;
    322         }
    323         vector<vector<int>> mnleft(n, vector<int>(k + 1));
    324         for (int j = 0; j <= k; j++) {
    325             int l = n, now = 0;
    326             for (int i = n - 1; i >= 0; i--) {
    327                 while (l - 1 >= 0 && now + (cnt[a[l - 1]] > 0) <= j) {
    328                     l--;
    329                     now += (cnt[a[l]] > 0);
    330                     cnt[a[l]]++;
    331                 }
    332                 mnleft[i][j] = l;
    333                 if (cnt[a[i]] > 1) now--;
    334                 cnt[a[i]]--;
    335             }
    336         }
    337         vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
    338         for (auto &c : dp[0]) c = 0;
    339         for (int i = 1; i <= n; i++) {
    340             for (int j = 0; j <= k; j++) {
    341                 if (j > 0) dp[i][j] = dp[i][j - 1];
    342                 for (int lst = 0; lst <= j; lst++) {
    343                     dp[i][j] = min(dp[i][j], dp[mnleft[i - 1][lst]][j - lst] + 1);
    344                 }
    345             }
    346         }
    347         int ans = INF;
    348         for (auto &c : dp.back()) ans = min(ans, c);
    349         cout << ans << "\n";
    350     }
    351     return 0;
    352 }
    353 ```