codeforces-scrape

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

1141.md (5260B)


      1 Source: https://codeforces.com/blog/entry/66062
      2 
      3 Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round!
      4 
      5 Tutorial is loading...
      6 
      7 **Code**
      8 
      9 ```
     10 int n, m;
     11 cin >> n >> m;
     12 int result = -1;
     13 if (m % n == 0) {
     14     result = 0;
     15     int d = m / n;
     16     while (d % 2 == 0)
     17         d /= 2, result++;
     18     while (d % 3 == 0)
     19         d /= 3, result++;
     20     if (d != 1)
     21         result = -1;
     22 }
     23 cout << result << endl;
     24 ```
     25 
     26 Tutorial is loading...
     27 
     28 **Code**
     29 
     30 ```
     31 int n;
     32 cin >> n;
     33 vector<int> a(n);
     34 for (int i = 0; i < n; i++)
     35     cin >> a[i];
     36 int result = 0;
     37 int len = 0;
     38 for (int i = 0; i < 2 * n; i++) {
     39     if (a[i % n] == 1) {
     40         len++;
     41         result = max(result, len);
     42     } else {
     43         len = 0;
     44     }
     45 }
     46 cout << result << endl;
     47 ```
     48 
     49 Tutorial is loading...
     50 
     51 **Code**
     52 
     53 ```
     54 int n;
     55 cin >> n;
     56 vector<int> q(n - 1);
     57 long long sum = 0;
     58 long long min_val = 0;
     59 for (int i = 0; i + 1 < n; i++) {
     60     cin >> q[i];
     61     sum += q[i];
     62     if (sum < min_val)
     63         min_val = sum;
     64 }
     65 vector<long long> p(n);
     66 p[0] = 1 - min_val;
     67 forn(i, n - 1)
     68     p[i + 1] = p[i] + q[i];
     69 bool ok = true;
     70 for (int i = 0; i < n; i++)
     71     if (p[i] < 1 || p[i] > n)
     72         ok = false;
     73 if (ok)
     74     ok = set<long long>(p.begin(), p.end()).size() == n;
     75 if (ok) {
     76     forn(i, n)
     77         cout << p[i] << " ";
     78 } else
     79     cout << -1 << endl;
     80 ```
     81 
     82 Tutorial is loading...
     83 
     84 **Code**
     85 
     86 ```
     87 #define forn(i, n) for (int i = 0; i < int(n); i++)
     88 const int A = 26;
     89 ...
     90 int n;
     91 cin >> n;
     92 string l;
     93 cin >> l;
     94 vector<vector<int>> left(A);
     95 vector<int> wl;
     96 forn(i, n)
     97     if (l[i] != '?')
     98         left[l[i] - 'a'].push_back(i);
     99     else
    100         wl.push_back(i);
    101 string r;
    102 cin >> r;
    103 vector<vector<int>> right(A);
    104 vector<int> wr;
    105 forn(i, n)
    106     if (r[i] != '?')
    107         right[r[i] - 'a'].push_back(i);
    108     else
    109         wr.push_back(i);
    110 vector<pair<int,int>> p;
    111 vector<int> cl(A), cr(A);
    112 forn(i, A) {
    113     forn(j, min(left[i].size(), right[i].size()))
    114         p.push_back(make_pair(left[i][j] + 1, right[i][j] + 1));
    115     cl[i] = cr[i] = min(left[i].size(), right[i].size());
    116 }
    117 forn(i, A)
    118     while (cl[i] < left[i].size() && !wr.empty()) {
    119         p.push_back(make_pair(left[i][cl[i]] + 1, wr[wr.size() - 1] + 1));
    120         cl[i]++;
    121         wr.pop_back();
    122     }
    123 forn(i, A)
    124     while (cr[i] < right[i].size() && !wl.empty()) {
    125         p.push_back(make_pair(wl[wl.size() - 1] + 1, right[i][cr[i]] + 1));
    126         wl.pop_back();
    127         cr[i]++;
    128     }
    129 forn(j, min(wl.size(), wr.size()))
    130     p.push_back(make_pair(wl[j] + 1, wr[j] + 1));
    131 cout << p.size() << endl;
    132 for (auto pp: p)
    133     cout << pp.first << " " << pp.second << endl;
    134 ```
    135 
    136 Tutorial is loading...
    137 
    138 **Code**
    139 
    140 ```
    141 long long H;
    142 int n;
    143 cin >> H >> n;
    144 vector<long long> a(n);
    145 long long sum = 0;
    146 long long gap = 0;
    147 long long h = H;
    148 for (int i = 0; i < n; i++) {
    149     cin >> a[i];
    150     sum -= a[i];
    151     h += a[i];
    152     if (h <= 0) {
    153         cout << i + 1 << endl;
    154         return 0;
    155     }
    156     gap = max(gap, sum);
    157 }
    158 if (sum <= 0) {
    159     cout << -1 << endl;
    160     return 0;
    161 }
    162 
    163 long long whole = (H - gap) / sum;
    164 H -= whole * sum;
    165 long long result = whole * n;
    166 
    167 for (int i = 0;; i++) {
    168     H += a[i % n];
    169     result++;
    170     if (H <= 0) {
    171         cout << result << endl;
    172         break;
    173     }
    174 }
    175 ```
    176 
    177 Tutorial is loading...
    178 
    179 Tutorial is loading...
    180 
    181 **Code**
    182 
    183 ```
    184 int n;
    185 cin >> n;
    186 vector<int> a(n);
    187 for (int i = 0; i < n; i++)
    188     cin >> a[i];
    189 map<int, vector<pair<int,int>>> segs;
    190 for (int r = 0; r < n; r++) {
    191     int sum = 0;                              
    192     for (int l = r; l >= 0; l--) {
    193         sum += a[l];
    194         segs[sum].push_back({l, r});
    195     }
    196 }
    197 int result = 0;
    198 vector<pair<int,int>> best;
    199 for (const auto& p: segs) {
    200     const vector<pair<int,int>>& pp = p.second;
    201     int cur = 0;
    202     int r = -1;
    203     vector<pair<int,int>> now;
    204     for (auto seg: pp)
    205         if (seg.first > r) {
    206             cur++;
    207             now.push_back(seg);
    208             r = seg.second;
    209         }
    210     if (cur > result) {
    211         result = cur;
    212         best = now;
    213     }
    214 }
    215 cout << result << endl;
    216 for (auto seg: best)
    217     cout << seg.first + 1 << " " << seg.second + 1 << endl;
    218 ```
    219 
    220 Tutorial is loading...
    221 
    222 **Code**
    223 
    224 ```
    225 int n, k, r;
    226 vector<vector<pair<int,int>>> g;
    227 int D;
    228 vector<int> col;
    229 
    230 void dfs(int u, int p, int f) {
    231     int color = 0;
    232     for (auto e: g[u])
    233         if (p != e.first) {
    234             if (color == f) {
    235                 color = (color + 1) % D;
    236                 f = -1;
    237             }
    238             col[e.second] = color;
    239             dfs(e.first, u, color);
    240             color = (color + 1) % D;
    241         }         
    242 }
    243 
    244 int main() {
    245     cin >> n >> k;
    246     g.resize(n);
    247     vector<int> d(n);
    248     for (int i = 0; i + 1 < n; i++) {
    249         int x, y;
    250         cin >> x >> y;
    251         x--, y--;
    252         g[x].push_back({y, i});
    253         g[y].push_back({x, i});
    254         d[x]++, d[y]++;
    255     }
    256     map<int,int> cnt;
    257     for (int dd: d)
    258         cnt[dd]++;
    259     
    260     int kk = n;
    261     D = 0;
    262     for (auto p: cnt)
    263         if (kk > k)
    264             D = p.first,
    265             kk -= p.second;
    266         else
    267             break;
    268     col = vector<int>(n - 1);
    269     dfs(0, -1, -1);    
    270     cout << D << endl;
    271     for (int i = 0; i + 1 < n; i++)
    272         cout << col[i] + 1 << " ";
    273 }
    274 ```