codeforces-scrape

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

1519.md (7789B)


      1 Source: https://codeforces.com/blog/entry/90212
      2 
      3 [1519A - Red and Blue Beans](/contest/1519/problem/A "Educational Codeforces Round 108 (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() {
     15     repeat(readLine()!!.toInt()) {
     16         val (r, b, d) = readLine()!!.split(' ').map { it.toInt() }
     17         println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO")
     18     }
     19 }
     20 ```
     21 
     22 [1519B - The Cake Is a Lie](/contest/1519/problem/B "Educational Codeforces Round 108 (Rated for Div. 2)")
     23 
     24 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (adedalic)**
     31 
     32 ```
     33 fun main() {
     34     repeat(readLine()!!.toInt()) {
     35         val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }
     36         println(if (n * m - 1 == k) "YES" else "NO")
     37     }
     38 }
     39 ```
     40 
     41 [1519C - Berland Regional](/contest/1519/problem/C "Educational Codeforces Round 108 (Rated for Div. 2)")
     42 
     43 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution (awoo)**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 
     54 #define forn(i, n) for (int i = 0; i < int(n); i++)
     55 
     56 using namespace std;
     57 
     58 int main() {
     59     int t;
     60     scanf("%d", &t);
     61     forn(_, t){
     62         int n;
     63         scanf("%d", &n);
     64         vector<int> s(n), u(n);
     65         forn(i, n){
     66             scanf("%d", &s[i]);
     67             --s[i];
     68         }
     69         forn(i, n){
     70             scanf("%d", &u[i]);
     71         }
     72         vector<vector<int>> bst(n);
     73         forn(i, n) bst[s[i]].push_back(u[i]);
     74         forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>());
     75         vector<vector<long long>> pr(n, vector<long long>(1, 0));
     76         forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x);
     77         vector<long long> ans(n);
     78         forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k)
     79             ans[k - 1] += pr[i][bst[i].size() / k * k];
     80         forn(i, n)
     81             printf("%lld ", ans[i]);
     82         puts("");
     83     }
     84     return 0;
     85 }
     86 ```
     87 
     88 [1519D - Maximum Sum of Products](/contest/1519/problem/D "Educational Codeforces Round 108 (Rated for Div. 2)")
     89 
     90 Idea: [vovuh](/profile/vovuh "Master vovuh")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution (Neon)**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 using li = long long;
    104 
    105 int main() {
    106   int n;
    107   cin >> n;
    108   vector<li> a(n), b(n);
    109   for (auto& x : a) cin >> x;
    110   for (auto& x : b) cin >> x;
    111   vector<li> pr(n + 1, 0);
    112   for (int i = 0; i < n; ++i)
    113     pr[i + 1] = pr[i] + a[i] * b[i];
    114   li ans = pr[n];
    115   for (int c = 0; c < n; ++c) {
    116     li cur = a[c] * b[c];
    117     for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) {
    118       cur += a[l] * b[r];
    119       cur += a[r] * b[l];
    120       ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    121     }
    122     cur = 0;
    123     for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) {
    124       cur += a[l] * b[r];
    125       cur += a[r] * b[l];
    126       ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    127     }
    128   }
    129   cout << ans << endl;
    130 }
    131 ```
    132 
    133 [1519E - Off by One](/contest/1519/problem/E "Educational Codeforces Round 108 (Rated for Div. 2)")
    134 
    135 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution (awoo)**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145 
    146 #define forn(i, n) for (int i = 0; i < int(n); i++)
    147 #define x first
    148 #define y second
    149 
    150 using namespace std;
    151 
    152 struct point{
    153     int a, b, c, d;
    154 };
    155 
    156 typedef pair<long long, long long> frac;
    157 typedef pair<int, int> pt;
    158 
    159 int n;
    160 vector<point> a;
    161 map<frac, int> sv;
    162 
    163 frac norm(long long x, long long y){
    164     long long g = __gcd(x, y);
    165     return {x / g, y / g};
    166 }
    167 
    168 vector<vector<pt>> g;
    169 vector<int> used;
    170 vector<pt> ans;
    171 
    172 int dfs(int v){
    173     used[v] = 1;
    174     int cur = -1;
    175     for (auto it : g[v]){
    176         int u = it.x;
    177         int i = it.y;
    178         if (used[u] == 1) continue;
    179         int nw = i;
    180         if (!used[u]){
    181             int tmp = dfs(u);
    182             if (tmp != -1){
    183                 ans.push_back({nw, tmp});
    184                 nw = -1;
    185             }
    186         }
    187         if (nw != -1){
    188             if (cur != -1){
    189                 ans.push_back({cur, nw});
    190                 cur = -1;
    191             }
    192             else{
    193                 cur = nw;
    194             }
    195         }
    196     }
    197     used[v] = 2;
    198     return cur;
    199 }
    200 
    201 int main() {
    202     scanf("%d", &n);
    203     a.resize(n);
    204     forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
    205     g.resize(2 * n);
    206     forn(i, n){
    207         frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c);
    208         frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d));
    209         if (!sv.count(f1)){
    210             int k = sv.size();
    211             sv[f1] = k;
    212         }
    213         if (!sv.count(f2)){
    214             int k = sv.size();
    215             sv[f2] = k;
    216         }
    217         g[sv[f1]].push_back({sv[f2], i});
    218         g[sv[f2]].push_back({sv[f1], i});
    219     }
    220     used.resize(sv.size());
    221     forn(i, sv.size()) if (!used[i])
    222         dfs(i);
    223     printf("%d\n", int(ans.size()));
    224     for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1);
    225 }
    226 ```
    227 
    228 [1519F - Chests and Keys](/contest/1519/problem/F "Educational Codeforces Round 108 (Rated for Div. 2)")
    229 
    230 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution (BledDest)**
    237 
    238 ```
    239 #include<bits/stdc++.h>
    240 
    241 using namespace std;
    242 
    243 const int N = 6;
    244 const int M = 400;
    245 const int INF = int(1e9);
    246 
    247 int a[N];
    248 int b[N];
    249 int c[N][N];
    250 int n, m;
    251 
    252 struct state
    253 {
    254     vector<int> need;
    255     int v2;
    256     int v1;
    257     int rem;
    258     state() {};
    259     state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {};
    260 };
    261 
    262 int get_code(const vector<int>& v)
    263 {
    264     int ans = 0;
    265     for(int i = 0; i < v.size(); i++)
    266         ans = ans * 5 + v[i];
    267     return ans;
    268 }
    269 
    270 int get_code(const state& s)
    271 {
    272     int code = get_code(s.need);
    273     code = code * 6 + s.v2;
    274     code = code * 6 + s.v1;
    275     code = code * 5 + s.rem;
    276     return code; 
    277 }
    278 
    279 vector<int> get_vector(int code, int n)
    280 {
    281     vector<int> res(n);
    282     for(int i = n - 1; i >= 0; i--)
    283     {
    284         res[i] = code % 5;
    285         code /= 5;
    286     }
    287     return res;
    288 }
    289 
    290 state get_state(int code)
    291 {
    292     int rem = code % 5;
    293     code /= 5;
    294     int v1 = code % 6;
    295     code /= 6;
    296     int v2 = code % 6;
    297     code /= 6;
    298     vector<int> need = get_vector(code, n);
    299     return state(need, v1, v2, rem);
    300 }
    301 
    302 const int Z = 40 * int(1e6);
    303 int dp[Z];
    304 
    305 int main()
    306 {
    307     cin >> n >> m;
    308     for(int i = 0; i < n; i++)
    309         cin >> a[i];
    310     for(int i = 0; i < m; i++)
    311         cin >> b[i];
    312     for(int i = 0; i < n; i++)
    313         for(int j = 0; j < m; j++)
    314             cin >> c[i][j];
    315     for(int i = 0; i < Z; i++)
    316         dp[i] = INF;
    317     state start(vector<int>(n, 0), 0, 0, 0);
    318     int ans = INF;
    319     dp[get_code(start)] = 0;
    320     for(int i = 0; i < Z; i++)
    321     {
    322         if(dp[i] == INF) continue;
    323         state s = get_state(i);
    324         for(int f = 0; f <= 4; f++)
    325         {
    326             if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2])
    327                 continue;
    328             int add = (f == 0 ? 0 : c[s.v1][s.v2]);
    329             state nw = s;
    330             nw.need[s.v1] += f;
    331             nw.rem += f;
    332             if(s.v1 == n - 1)
    333             {
    334                 nw.v1 = 0;
    335                 nw.v2 = s.v2 + 1;
    336                 nw.rem = 0;
    337             }
    338             else
    339             {
    340                 nw.v1 = s.v1 + 1;
    341             }
    342             if(nw.need == vector<int>(a, a + n))
    343                 ans = min(ans, dp[i] + add);
    344             if(nw.v2 < m)
    345             {
    346                 int code = get_code(nw);
    347                 dp[code] = min(dp[code], dp[i] + add);
    348             }
    349         }
    350     }
    351     if(ans == INF) ans = -1;
    352     cout << ans << endl;
    353 
    354 }
    355 ```