codeforces-scrape

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

1612.md (9335B)


      1 Source: https://codeforces.com/blog/entry/97164
      2 
      3 [1612A - Distance](/contest/1612/problem/A "Educational Codeforces Round 117 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     x, y = map(int, input().split())
     17     xc = -1
     18     yc = -1
     19     for j in range(0, 51):
     20         for k in range(0, 51):
     21             if 2 * (j + k) == x + y and 2 * (abs(x - j) + abs(y - k)) == x + y:
     22                 xc, yc = j, k
     23     print(xc, yc)
     24 ```
     25 
     26 [1612B - Special Permutation](/contest/1612/problem/B "Educational Codeforces Round 117 (Rated for Div. 2)")
     27 
     28 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (BledDest)**
     35 
     36 ```
     37 t = int(input())
     38 for i in range(t):
     39     n, a, b = map(int, input().split())
     40     p = [a]
     41     for j in range(n, 0, -1):
     42         if j != a and j != b:
     43             p.append(j)
     44     p.append(b)
     45     if(len(p) == n and min(p[0:n//2]) == a and max(p[n//2:n]) == b):
     46         print(*p)
     47     else:
     48         print(-1)
     49 ```
     50 
     51 [1612C - Chat Ban](/contest/1612/problem/C "Educational Codeforces Round 117 (Rated for Div. 2)")
     52 
     53 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (vovuh)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63 
     64 using namespace std;
     65 
     66 long long get(int x) {
     67     return x * 1ll * (x + 1) / 2;
     68 }
     69 
     70 int main() {
     71 #ifdef _DEBUG
     72     freopen("input.txt", "r", stdin);
     73 //  freopen("output.txt", "w", stdout);
     74 #endif
     75     
     76     int t;
     77     cin >> t;
     78     while (t--) {
     79         int k;
     80         long long x;
     81         cin >> k >> x;
     82         long long l = 1, r = 2 * k - 1;
     83         long long res = 2 * k - 1;
     84         bool over = false;
     85         while (l <= r) {
     86             int mid = (l + r) >> 1;
     87             if (mid >= k) {
     88                 over = (get(k) + get(k - 1) - get(2 * k - 1 - mid) >= x);
     89             } else {
     90                 over = (get(mid) >= x);
     91             }
     92             if (over) {
     93                 res = mid;
     94                 r = mid - 1;
     95             } else {
     96                 l = mid + 1;
     97             }
     98         }
     99         cout << res << endl;
    100     }
    101     
    102     return 0;
    103 }
    104 ```
    105 
    106 [1612D - X-Magic Pair](/contest/1612/problem/D "Educational Codeforces Round 117 (Rated for Div. 2)")
    107 
    108 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh")
    109 
    110 **Tutorial**
    111 
    112 Tutorial is loading...
    113 
    114 **Solution (vovuh)**
    115 
    116 ```
    117 #include <bits/stdc++.h>
    118 
    119 using namespace std;
    120 
    121 bool get(long long a, long long b, long long x) {
    122     if (a == x || b == x) return true;
    123     if (a < b) swap(a, b);
    124     if (b > a - b) b = a - b;
    125     if (x > max(a, b) || a == 0 || b == 0) return false;
    126     long long cnt = max(1ll, (a - max(x, b)) / (2 * b));
    127     return get(a - b * cnt, b, x);
    128 }
    129 
    130 int main() {
    131 #ifdef _DEBUG
    132     freopen("input.txt", "r", stdin);
    133 //  freopen("output.txt", "w", stdout);
    134 #endif
    135     
    136     int t;
    137     cin >> t;
    138     while (t--) {
    139         long long a, b, x;
    140         cin >> a >> b >> x;
    141         if (get(a, b, x)) {
    142             cout << "YES" << endl;
    143         } else {
    144             cout << "NO" << endl;
    145         }
    146     }
    147     
    148     return 0;
    149 }
    150 ```
    151 
    152 [1612E - Messages](/contest/1612/problem/E "Educational Codeforces Round 117 (Rated for Div. 2)")
    153 
    154 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    155 
    156 **Tutorial**
    157 
    158 Tutorial is loading...
    159 
    160 **Solution (BledDest)**
    161 
    162 ```
    163 #include <bits/stdc++.h>     
    164 
    165 using namespace std;
    166 
    167 const int N = 200043;
    168 const int K = 20;
    169 vector<int> idx[N];
    170 int m[N], k[N];
    171 
    172 bool frac_greater(pair<int, int> a, pair<int, int> b)
    173 {
    174     return a.first * b.second > a.second * b.first;
    175 }
    176 
    177 int main()
    178 {
    179     int n;
    180     scanf("%d", &n);
    181     for(int i = 0; i < n; i++)
    182     {
    183         scanf("%d %d", &m[i], &k[i]);
    184         idx[m[i]].push_back(i);
    185     }
    186 
    187     vector<int> cert;
    188     pair<int, int> ans = {0, 1};
    189     for(int i = 1; i <= K; i++)
    190     {
    191         vector<int> score(N);
    192         for(int j = 0; j < n; j++)
    193             score[m[j]] += min(i, k[j]);
    194         vector<pair<int, int>> aux;
    195         for(int j = 0; j < N; j++)
    196             aux.push_back(make_pair(score[j], j));
    197         sort(aux.rbegin(), aux.rend());
    198         pair<int, int> cur_ans = {0, i};
    199         vector<int> cur_cert;
    200         for(int j = 0; j < i; j++)
    201         {
    202             cur_ans.first += aux[j].first;
    203             cur_cert.push_back(aux[j].second);
    204         }
    205         if(frac_greater(cur_ans, ans))
    206         {
    207             ans = cur_ans;
    208             cert = cur_cert;
    209         }
    210     }
    211     cout << cert.size() << endl;
    212     shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));
    213     for(auto x : cert) cout << x << " ";
    214     cout << endl;
    215 }
    216 ```
    217 
    218 [1612F - Armor and Weapons](/contest/1612/problem/F "Educational Codeforces Round 117 (Rated for Div. 2)")
    219 
    220 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (BledDest)**
    227 
    228 ```
    229 #include<bits/stdc++.h>
    230 
    231 using namespace std;
    232 
    233 int n, m;
    234 
    235 #define x first
    236 #define y second
    237 
    238 typedef pair<int, int> comb;
    239 
    240 comb norm(const comb& a)
    241 {
    242     return make_pair(min(a.x, n), min(a.y, m));
    243 }
    244 
    245 bool good(const comb& a)
    246 {
    247     return a.x == n || a.y == m;
    248 }
    249 
    250 bool comp(const comb& a, const comb& b)
    251 {
    252     if(a.x != b.x)
    253         return a.x > b.x;
    254     return a.y > b.y;
    255 }
    256 
    257 int main()
    258 {
    259     scanf("%d %d", &n, &m);
    260     int v;
    261     scanf("%d", &v);
    262     set<comb> s;
    263     for(int i = 0; i < v; i++)
    264     {
    265         int x, y;
    266         scanf("%d %d", &x, &y);
    267         s.insert(make_pair(x, y));
    268     }
    269     int steps = 0;
    270     vector<comb> cur;
    271     cur.push_back(make_pair(1, 1));
    272     while(true)
    273     {
    274         if(cur[0] == make_pair(n, m))
    275             break;
    276         vector<comb> ncur;
    277         for(auto x : cur)
    278         {
    279             int sum = x.x + x.y;
    280             if(s.count(x))
    281                 sum++;
    282             comb z = x;
    283             z.x = sum;
    284             ncur.push_back(norm(z));
    285             z = x;
    286             z.y = sum;
    287             ncur.push_back(norm(z));
    288         }
    289         sort(ncur.begin(), ncur.end(), comp);
    290         int mx = 0;
    291         vector<comb> ncur2;
    292         for(auto x : ncur)
    293         {
    294             if(x.y <= mx) continue;
    295             mx = max(mx, x.y);
    296             ncur2.push_back(x);
    297         }
    298         cur = ncur2;
    299         steps++;
    300     }
    301     printf("%d\n", steps);
    302 }
    303 ```
    304 
    305 [1612G - Max Sum Array](/contest/1612/problem/G "Educational Codeforces Round 117 (Rated for Div. 2)")
    306 
    307 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    308 
    309 **Tutorial**
    310 
    311 Tutorial is loading...
    312 
    313 **Solution (adedalic)**
    314 
    315 ```
    316 #include<bits/stdc++.h>
    317 
    318 using namespace std;
    319 
    320 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    321 #define sz(a) int((a).size())
    322 
    323 #define x first
    324 #define y second
    325 
    326 typedef long long li;
    327 typedef pair<int, int> pt;
    328 
    329 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    330     return out << "(" << p.x << " " << p.y << ")";
    331 }
    332 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    333     fore(i, 0, sz(v)) {
    334         if(i) out << " ";
    335         out << v[i];
    336     }
    337     return out;
    338 }
    339 
    340 const int INF = int(1e9);
    341 const li INF64 = li(1e18);
    342 
    343 const int MOD = int(1e9) + 7;
    344 
    345 int norm(int a) {
    346     while (a >= MOD)
    347         a -= MOD;
    348     while (a < 0)
    349         a += MOD;
    350     return a;
    351 }
    352 int mul(int a, int b) {
    353     return int(a * 1ll * b % MOD);
    354 }
    355 
    356 const int MX = int(1e6) + 55;
    357 int n;
    358 li total;
    359 int cnt[MX];
    360 
    361 inline bool read() {
    362     if(!(cin >> n))
    363         return false;
    364     total = 0;
    365     fore (i, 0, n) {
    366         int k; cin >> k;
    367         cnt[k]++;
    368         total += k;
    369     }
    370     return true;
    371 }
    372 
    373 int fact[MX];
    374 
    375 inline void solve() {
    376     fact[0] = 1;
    377     fore (i, 1, MX)
    378         fact[i] = mul(fact[i - 1], i);
    379     
    380     int ansSum = 0;
    381     int ansCnt = 1;
    382     
    383     for (int lvl = MX - 1; lvl > 1; lvl--) {
    384         ansCnt = mul(ansCnt, mul(fact[cnt[lvl]], fact[cnt[lvl]]));
    385         
    386         //each color gives (lvl - 1) * (r_i - l_i)
    387         // or (lvl - 1) * (sum r_i - sum l_i)
    388         // l_i is permutation of [0,..., cnt[lvl]), so sum l_i = (cnt[lvl] - 1) * cnt[lvl] / 2
    389         // r_i is permutation of [total - cnt[lvl],..., total), so sum = cnt[lvl] * (total - cnt[lvl]) + (cnt[lvl] - 1) * cnt[lvl] / 2
    390         
    391         ansSum = norm(ansSum + mul(mul(lvl - 1, cnt[lvl]), (total - cnt[lvl]) % MOD));
    392         
    393         total -= 2 * cnt[lvl];
    394         cnt[lvl - 2] += cnt[lvl];
    395     }
    396     
    397     ansCnt = mul(ansCnt, fact[cnt[1]]);
    398     
    399     cout << ansSum << " " << ansCnt << endl;
    400 }
    401 
    402 int main() {
    403 #ifdef _DEBUG
    404     freopen("input.txt", "r", stdin);
    405     int tt = clock();
    406 #endif
    407     ios_base::sync_with_stdio(false);
    408     cin.tie(0), cout.tie(0);
    409     cout << fixed << setprecision(15);
    410     
    411     if(read()) {
    412         solve();
    413         
    414 #ifdef _DEBUG
    415         cerr << "TIME = " << clock() - tt << endl;
    416         tt = clock();
    417 #endif
    418     }
    419     return 0;
    420 }
    421 ```