codeforces-scrape

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

1330.md (20532B)


      1 Source: https://codeforces.com/blog/entry/75559
      2 
      3 Tutorial is loading...
      4 
      5 **author's code:**
      6 
      7 ```
      8 #include<cstdio>
      9 const int MAX_V = 201;
     10 bool achieve[MAX_V];
     11 void solve() {
     12     int n, x;
     13     scanf("%d%d", &n, &x);
     14     for(int i = 1; i <= n + x; i++) {
     15         achieve[i] = false;
     16     }
     17     for(int i = 1; i <= n; i++) {
     18         int ranking;
     19         scanf("%d", &ranking);
     20         achieve[ranking] = true;
     21     }
     22     for(int k = n + x; k > 0; k--) {
     23         int v = 0;
     24         for(int i = 1; i <= k; i++) {
     25             if(!achieve[i]) v++;
     26         }
     27         if(v <= x) {
     28             printf("%d\n", k);
     29             return;
     30         }
     31     }
     32 }
     33 int main() {
     34     int T;
     35     scanf("%d", &T);
     36     while(T--) solve();
     37     return 0;
     38 }
     39 ```
     40 
     41 Tutorial is loading...
     42 
     43 **author's code**
     44 
     45 ```
     46 #include<cstdio>
     47 const int SIZE = 200000;
     48 int p[SIZE];
     49 int ans[SIZE][2];
     50 int ans_cnt;
     51 bool judge(int a[], int n){
     52     static int used[SIZE+1];
     53     for(int i = 1; i <= n; i++) used[i] = 0;
     54     for(int i = 0; i < n; i++) used[a[i]] = 1;
     55     for(int i = 1; i <= n; i++) {
     56         if(!used[i]) return 0;
     57     }
     58     return 1;
     59 }
     60 bool judge(int len1, int n){
     61     return judge(p, len1) && judge(p + len1, n - len1);
     62 }
     63 int main() {
     64     int t = 0;
     65     scanf("%d", &t);
     66     while(t--) {
     67         ans_cnt = 0;
     68         int n;
     69         scanf("%d", &n);
     70         int ma=0;
     71         for(int i = 0; i < n; i++) {
     72             scanf("%d", &p[i]);
     73             if(ma < p[i]) ma = p[i];
     74         }
     75         if(judge(n - ma,n)) {
     76             ans[ans_cnt][0] = n - ma;
     77             ans[ans_cnt++][1] = ma;
     78         }
     79         if(ma * 2 != n && judge(ma,n)) {
     80             ans[ans_cnt][0] = ma;
     81             ans[ans_cnt++][1] = n - ma;
     82         }
     83         printf("%d\n", ans_cnt);
     84         for(int i = 0; i < ans_cnt; i++) {
     85             printf("%d %d\n", ans[i][0], ans[i][1]);
     86         }
     87     }
     88     return 0;
     89 }
     90 ```
     91 
     92 Tutorial is loading...
     93 
     94 **author's code**
     95 
     96 ```
     97 #include<bits/stdc++.h>
     98 const int SIZE = 100002;
     99 int len[SIZE];
    100 long long suffix_sum[SIZE];
    101 void err() {puts("-1");}
    102 void solve() {
    103     int N, M;
    104     scanf("%d%d", &N, &M);
    105     for(int i = 1; i <= M; i++) {
    106         scanf("%d", &len[i]);
    107         if(len[i] + i - 1 > N) {
    108             err();
    109             return;
    110         }
    111     }
    112     for(int i = M; i > 0; i--) {
    113         suffix_sum[i] = suffix_sum[i + 1] + len[i];
    114     }
    115     if(suffix_sum[1] < N) {
    116         err();
    117         return;
    118     }
    119     for(int i = 1; i <= M; i++) {
    120         printf("%lld", std::max((long long)i, N - suffix_sum[i] + 1));
    121         if(i < M) putchar(' ');
    122         else puts("");
    123     }
    124 }
    125 int main() {
    126     solve();
    127     return 0;
    128 }
    129 ```
    130 
    131 Tutorial is loading...
    132 
    133 **UPD: [onthefloor](/profile/onthefloor "Мастер onthefloor") provides proof for what I mention** [here](https://codeforces.com/blog/entry/75559?#comment-597742).
    134 
    135 **author's code**
    136 
    137 ```
    138 #include<bits/stdc++.h>
    139 void solve(){
    140     int d, m;
    141     scanf("%d%d",&d, &m);
    142     long long answer=1;
    143     for(int i = 0; i < 30; i++) {
    144         if(d < (1 << i)) break;
    145         answer = answer * (std::min((1 << (i+1)) - 1, d) - (1 << i) + 2) % m;
    146     }
    147     answer--;
    148     if(answer < 0) answer += m;
    149     printf("%lld\n",answer);
    150 }
    151 int main() {
    152     int T;
    153     scanf("%d", &T);
    154     while(T--) {
    155         solve();
    156     }
    157 }
    158 ```
    159 
    160 Tutorial is loading...
    161 
    162 [a super simple solution which is differet to this blog](https://codeforces.com/blog/entry/75559?#comment-597934) provided by [Swistakk](/profile/Swistakk "Легендарный гроссмейстер Swistakk").
    163 
    164 **author's code (from bottom to top with min heap)**
    165 
    166 ```
    167 #include<bits/stdc++.h>
    168 using namespace std;
    169 const int SIZE = 1<<20;
    170 int INF = 1000000001;
    171 pair<int, int> a[SIZE];
    172 int final_v[SIZE];
    173 bool used[SIZE];
    174 int h, g;
    175 void pull(int id) {
    176     while(a[id] > min(a[id<<1], a[(id<<1)|1])) {
    177         if(a[id<<1] < a[(id << 1) | 1]) {
    178             swap(a[id<<1], a[id]);
    179             id <<= 1;
    180         }
    181         else {
    182             swap(a[(id<<1)|1], a[id]);
    183             id = (id << 1) | 1;
    184         }
    185         if(id >= (1 << h)) return;
    186     }
    187 }
    188 void solve() {
    189     scanf("%d%d", &h, &g);
    190     long long an = 0;
    191     for(int i = 1; i < (1 << h); i++) {
    192         used[i] = 0;
    193         scanf("%d", &a[i].first);
    194         a[i].second = i;
    195         final_v[i] = 0;
    196     }
    197     h--;
    198     for(int lv = h - 1; lv >= 0; lv--) {
    199         int ll = 1 << lv;
    200         int rr = 1 << (lv + 1);
    201         for(int i = ll; i < rr; i++) {
    202             pair<int, int> tmp = a[i];
    203             int bot = i << (h - lv);
    204             a[i] = a[bot];
    205             a[bot] = make_pair(INF, 0);
    206             pull(i);
    207             if(lv < g) {
    208                 int need_mi = max(final_v[i * 2], final_v[i * 2 + 1]);
    209                 while(a[i].first < need_mi) {
    210                     a[i] = make_pair(INF, 0);
    211                     pull(i);
    212                 }
    213                 an += final_v[i] = a[i].first;
    214                 used[a[i].second] = 1;
    215                 a[i] = tmp;
    216                 pull(i);
    217             }
    218             else {
    219                 a[bot] = tmp;
    220             }
    221         }
    222     }
    223     printf("%lld\n", an);
    224     bool first_time = true;
    225     for(int i = (1 << (h + 1)) - 1; i > 0; i--) {
    226         if(!used[i]) {
    227             if(!first_time) printf(" ");
    228             else first_time = false;
    229             printf("%d", i);
    230         }
    231     }
    232     puts("");
    233 }
    234 int main(){
    235     int T;
    236     scanf("%d", &T);
    237     while(T--) solve();
    238     return 0;
    239 }
    240 ```
    241 
    242 **isaf27's code(from bottom to top with sorted array)**
    243 
    244 ```
    245 //#pragma GCC optimize("O3")
    246 #include <bits/stdc++.h>
    247 
    248 using namespace std;
    249 
    250 //defines
    251 typedef long long ll;
    252 typedef long double ld;
    253 #define TIME clock() * 1.0 / CLOCKS_PER_SEC
    254 #define prev _prev
    255 #define y0 _y0
    256 #define kill _kill
    257 
    258 //permanent constants
    259 const ld pi = acos(-1.0);
    260 const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    261 const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    262 const int dx[4] = {0, 1, 0, -1};
    263 const int dy[4] = {1, 0, -1, 0};
    264 const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    265 const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    266 const int alf = 26;
    267 const int dig = 10;
    268 const int two = 2;
    269 const int th = 3;
    270 const ll prost = 239;
    271 const ll btc = 30;
    272 const ld eps = 1e-8;
    273 const ll INF = (ll)(1e18 + 239);
    274 const int BIG = (int)(1e9 + 239);
    275 const int MOD = 1e9 + 7; //
    276 
    277 //random
    278 mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());
    279 
    280 //constants
    281 const int M = (int)(2e5 + 239);
    282 const int N = (int)(2e3 + 239);
    283 const int L = 20;
    284 const int T = (1 << 20) + 239;
    285 const int B = 500;
    286 const int X = 35;
    287 const int T2 = 2 * T;
    288 
    289 int h, g, a[T2], n;
    290 bool mark[T];
    291 int id[T], buf[T], timer;
    292 
    293 bool cmp(int i, int j)
    294 {
    295     return (a[i] < a[j]);
    296 }
    297 
    298 int pos;
    299 
    300 void dfs_write(int p)
    301 {
    302     id[pos++] = p;
    303     if (2 * p + 1 <= n)
    304     {
    305         dfs_write(2 * p);
    306         dfs_write(2 * p + 1);
    307     }
    308 }
    309 
    310 int dfs(int p, int sz)
    311 {
    312     if ((1 << (g - 1)) <= p && p < (1 << g))
    313     {
    314         int l = timer;
    315         timer += sz;
    316         pos = l;
    317         dfs_write(p);
    318         sort(id + l, id + l + sz, cmp);
    319         mark[id[l]] = true;
    320         return id[l];
    321     }
    322     int l = timer;
    323     int new_sz = ((sz - 1) / 2);
    324     int s1 = dfs(2 * p, new_sz);
    325     int s2 = dfs(2 * p + 1, new_sz);
    326     merge(id + l, id + l + new_sz, id + l + new_sz, id + l + new_sz + new_sz, buf, cmp);
    327     buf[sz - 1] = p;
    328     for (int i = 0; i < sz; i++)
    329         id[i + l] = buf[i];
    330     timer++;
    331     if (cmp(s1, s2))
    332         s1 = s2;
    333     for (int i = 0; i < sz; i++)
    334         if (cmp(s1, id[i + l]))
    335         {
    336             mark[id[i + l]] = true;
    337             return id[i + l];
    338         }
    339     return 0;
    340 }
    341 
    342 void rm(int i)
    343 {
    344     if (a[2 * i] == 0 && a[2 * i + 1] == 0)
    345     {
    346         a[i] = 0;
    347         mark[i] = false;
    348         return;
    349     }
    350     if (a[2 * i] > a[2 * i + 1])
    351     {
    352         a[i] = a[2 * i];
    353         mark[i] = mark[2 * i];
    354         rm(2 * i);
    355     }
    356     else
    357     {
    358         a[i] = a[2 * i + 1];
    359         mark[i] = mark[2 * i + 1];
    360         rm(2 * i + 1);
    361     }
    362 }
    363 
    364 void dfs_ans(int p)
    365 {
    366     while (a[p] != 0 && !mark[p])
    367     {
    368         cout << p << " ";
    369         rm(p);
    370     }
    371     if (a[p] == 0)
    372         return;
    373     dfs_ans(2 * p);
    374     dfs_ans(2 * p + 1);
    375 }
    376 
    377 void solve()
    378 {
    379     cin >> h >> g;
    380     n = (1 << h) - 1;
    381     for (int i = 1; i <= n; i++)
    382         cin >> a[i];
    383     for (int i = 1; i <= n; i++)
    384         mark[i] = false;
    385     timer = 0;
    386     dfs(1, n);
    387     ll ans = 0;
    388     for (int i = 1; i <= n; i++)
    389         if (mark[i])
    390             ans += a[i];
    391     cout << ans << "\n";
    392     dfs_ans(1);
    393     cout << "\n";
    394     for (int i = 0; i <= n; i++)
    395         a[i] = 0;
    396 }
    397 
    398 int32_t main()
    399 {
    400 #ifdef ONPC
    401     freopen("input", "r", stdin);
    402 #endif
    403     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    404     int t;
    405     cin >> t;
    406     while (t--)
    407         solve();
    408     return 0;
    409 }
    410 ```
    411 
    412 **author's code (from top to bottom)**
    413 
    414 ```
    415 #include<bits/stdc++.h>
    416 using namespace std;
    417 const int SIZE = 1<<20;
    418 int INF = 1000000001;
    419 int a[SIZE], ops[SIZE];
    420 int h, g;
    421 int qq[24], qn;
    422 int pull(int id) {
    423     int tmp = a[id];
    424     a[id] = 0;
    425     qn = 0;
    426     qq[qn++] = id;
    427     while(id * 2 < (1 << h) && a[id] < max(a[id<<1], a[(id<<1)|1])) {
    428         if(a[id<<1] > a[(id << 1) | 1]) {
    429             swap(a[id<<1], a[id]);
    430             id <<= 1;
    431         }
    432         else {
    433             swap(a[(id<<1)|1], a[id]);
    434             id = (id << 1) | 1;
    435         }
    436         qq[qn++] = id;
    437     }
    438     if(id < (1 << g)) {
    439         for(int i = qn - 1; i > 0; i--) {
    440             a[qq[i]] = a[qq[i - 1]];
    441         }
    442         a[qq[0]] = tmp;
    443         return 0;
    444     }
    445     return tmp;
    446 }
    447 void solve() {
    448     scanf("%d%d", &h, &g);
    449     long long an = 0;
    450     for(int i = 1; i < (1 << h); i++) {
    451         scanf("%d", &a[i]);
    452         an += a[i];
    453     }
    454     int need = 0;
    455     for(int i = 1; i < (1 << g); i++) {
    456         while(1) {
    457             int v = pull(i);
    458             if(v) {
    459                 an -= v;
    460                 ops[need++] = i;
    461             }
    462             else break;
    463         }
    464     }
    465     printf("%lld\n", an);
    466     for(int i = 0; i < need; i++) printf("%d%c", ops[i], " \n"[i == need - 1]);
    467 }
    468 int main(){
    469     int T;
    470     scanf("%d", &T);
    471     while(T--) solve();
    472     return 0;
    473 }
    474 ```
    475 
    476 Tutorial is loading...
    477 
    478 **author's code**
    479 
    480 ```
    481 #include<bits/stdc++.h>
    482 using namespace std;
    483 const int SIZE = 2e5+10;
    484 char s[SIZE];
    485 int cnt[SIZE];
    486 int cc[26];
    487 int all_cnt;
    488 int ma;
    489 void update_ma() {
    490     while(ma > 0 && !cnt[ma]) ma--;
    491 }
    492 void dec1(int id) {
    493     cnt[cc[id]]--;
    494     cc[id]--;
    495     cnt[cc[id]]++;
    496 }
    497 pair<int, int> stk[SIZE];
    498 int sn;
    499 int m;
    500 int now;
    501 int last_len;
    502 void add(int i, bool flag) {
    503     if(flag) {
    504         dec1(stk[sn - 1].second);
    505         dec1(stk[i].second);
    506         all_cnt -= 2;
    507         printf("%d %d\n",now + 1, now + stk[i].first);
    508         update_ma();
    509         sn--;
    510         now -= stk[sn].first;
    511         if(i + 1 < m) {
    512             stk[i + 1].first += stk[sn].first;
    513         }
    514         else{
    515             last_len += stk[sn].first;
    516         }
    517     }
    518     else {
    519         stk[sn++] = stk[i];
    520         now += stk[i].first;
    521     }
    522 }
    523 void solve(){
    524     scanf("%s", s);
    525     int n = strlen(s);
    526     all_cnt = 0;
    527     int lt = 0;
    528     m = 0;
    529     for(int i = 1; i < n; i++) {
    530         if(s[i] == s[i - 1]) {
    531             cc[s[i] - 'a']++;
    532             all_cnt++;
    533             stk[m++] = make_pair(i - lt, (int)(s[i] - 'a'));
    534             lt = i;
    535         }
    536     }
    537     last_len = n - lt;
    538     ma = 0;
    539     for(int i = 0; i < 26; i++) {
    540         cnt[cc[i]]++;
    541         ma = max(ma, cc[i]);
    542     }
    543     printf("%d\n", 1 + max(ma, (all_cnt + 1) / 2));
    544     if(ma * 2 < all_cnt) {
    545         sn = now = 0;
    546         for(int i = 0; i < m; i++) {
    547             add(i, sn && stk[sn - 1].second != stk[i].second && ma * 2 < all_cnt);
    548         }
    549         m = sn;
    550     }
    551     int main_id = -1;
    552     for(int i = 0; i < 26; i++) {
    553         if(cc[i] == ma) main_id = i;
    554     }
    555     sn = now = 0;
    556     for(int i = 0; i < m; i++) {
    557         add(i, sn && ((stk[sn - 1].second == main_id) ^ (stk[i].second == main_id)));
    558     }
    559     for(int i = 0; i < sn; i++) {
    560         printf("%d %d\n",1 ,stk[i].first);
    561     }
    562     printf("%d %d\n", 1, last_len);
    563     memset(cc, 0, sizeof(cc));
    564     memset(cnt, 0, sizeof(int) * (ma + 1));
    565 }
    566 int main(){
    567     int T;
    568     scanf("%d", &T);
    569     for(int i = 1; i <= T; i++) solve();
    570     return 0;
    571 }
    572 ```
    573 
    574 Tutorial is loading...
    575 
    576 **isaf27's solution**
    577 
    578 ```
    579 //#pragma GCC optimize("O3")
    580 #include <bits/stdc++.h>
    581 
    582 using namespace std;
    583 
    584 //defines
    585 typedef long long ll;
    586 typedef long double ld;
    587 #define TIME clock() * 1.0 / CLOCKS_PER_SEC
    588 #define prev _prev
    589 #define y0 _y0
    590 #define kill _kill
    591 
    592 //permanent constants
    593 const ld pi = acos(-1.0);
    594 const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    595 const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    596 const int dx[4] = {0, 1, 0, -1};
    597 const int dy[4] = {1, 0, -1, 0};
    598 const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    599 const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    600 const int alf = 26;
    601 const int dig = 10;
    602 const int two = 2;
    603 const int th = 3;
    604 const ll prost = 239;
    605 const ll btc = 30;
    606 const ld eps = 1e-8;
    607 const ll INF = (ll)(1e18 + 239);
    608 const int BIG = (int)(1e9 + 239);
    609 const int MOD = 1e9 + 7; //
    610 
    611 //random
    612 mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());
    613 
    614 //constants
    615 const int M = (int)(4e5 + 239);
    616 const int N = (int)(2e3 + 239);
    617 const int L = 20;
    618 const int T = (1 << 18) + 239;
    619 const int B = 500;
    620 const int X = 210;
    621 
    622 ll up(ll a, ll b)
    623 {
    624     return (a + b - 1) / b;
    625 }
    626 
    627 ll down(ll a, ll b)
    628 {
    629     return a / b;
    630 }
    631 
    632 int m;
    633 ll l[M], n, k;
    634 
    635 void solve()
    636 {
    637     cin >> n >> m >> k;
    638     ll pr = 0;
    639     for (int i = 0; i < m; i++)
    640     {
    641         ll p;
    642         cin >> p;
    643         l[i] = p - pr;
    644         pr = p;
    645     }
    646     l[m++] = n - pr;
    647     //for (int i = 0; i < m; i++)
    648     //    cerr << l[i] << " ";
    649     //cerr << "\n";
    650     ll sum = k + m;
    651     ll bl = 1;
    652     ll br = n + 1;
    653     while (br - bl > 1)
    654     {
    655         ll h = (bl + br) >> 1LL;
    656         ll cur = 0;
    657         for (int i = 0; i < m; i++)
    658             cur += down(l[i], h);
    659         if (sum <= cur)
    660             bl = h;
    661         else
    662             br = h;
    663     }
    664     ll MIN = bl;
    665     bl = 0;
    666     br = n + 1;
    667     while (br - bl > 1)
    668     {
    669         ll h = (bl + br) >> 1LL;
    670         ll cur = 0;
    671         for (int i = 0; i < m; i++)
    672             cur += up(l[i], h);
    673         if (sum >= cur)
    674             br = h;
    675         else
    676             bl = h;
    677     }
    678     ll MAX = br;
    679     vector<pair<ll, ll>> ban;
    680     for (int i = 0; i < m; i++)
    681     {
    682         if (up(l[i], MAX) <= down(l[i], MIN))
    683             continue;
    684         ll bl = 0;
    685         ll br = MIN;
    686         while (br - bl > 1)
    687         {
    688             ll h = (bl + br) >> 1LL;
    689             if (down(l[i], h) == down(l[i], MIN))
    690                 br = h;
    691             else
    692                 bl = h;
    693         }
    694         ll first = MIN - br;
    695         bl = MAX;
    696         br = INF;
    697         while (br - bl > 1)
    698         {
    699             ll h = (bl + br) >> 1LL;
    700             if (up(l[i], MAX) == up(l[i], h))
    701                 bl = h;
    702             else
    703                 br = h;
    704         }
    705         ll second = bl - MAX;
    706         ban.push_back(make_pair(first, second));
    707     }
    708     ll add = MAX - MIN;
    709     if (ban.empty())
    710     {
    711         cout << add << "\n";
    712         return;
    713     }
    714     sort(ban.begin(), ban.end());
    715     vector<pair<ll, ll>> a;
    716     for (int i = 0; i < (int)ban.size(); i++)
    717     {
    718         while (!a.empty() && a.back().second <= ban[i].second)
    719             a.pop_back();
    720         a.push_back(ban[i]);
    721     }
    722     ll ans = INF;
    723     ans = min(a[0].second + 1, ans);
    724     ans = min(a.back().first + 1, ans);
    725     for (int i = 0; i + 1 < (int)a.size(); i++)
    726         ans = min(ans, a[i].first + a[i + 1].second + 2);
    727     cout << ans + add << "\n";
    728 }
    729 
    730 int32_t main()
    731 {
    732 #ifdef ONPC
    733     freopen("input", "r", stdin);
    734 #endif
    735     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    736     int t;
    737     cin >> t;
    738     while (t--)
    739         solve();
    740     return 0;
    741 }
    742 ```
    743 
    744 **author's solution**
    745 
    746 ```
    747 /*{{{*/
    748 #include<cstdio>
    749 #include<cstdlib>
    750 #include<cstring>
    751 #include<cmath>
    752 #include<algorithm>
    753 #include<string>
    754 #include<iostream>
    755 #include<sstream>
    756 #include<set>
    757 #include<map>
    758 #include<queue>
    759 #include<bitset>
    760 #include<vector>
    761 #include<limits.h>
    762 #include<assert.h>
    763 #define SZ(X) ((int)(X).size())
    764 #define ALL(X) (X).begin(), (X).end()
    765 #define REP(I, N) for (int I = 0; I < (N); ++I)
    766 #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
    767 #define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
    768 #define FORS(I, S) for (int I = 0; S[I]; ++I)
    769 #define RS(X) scanf("%s", (X))
    770 #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
    771 #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
    772 #define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
    773 #define MP make_pair
    774 #define PB push_back
    775 #define MS0(X) memset((X), 0, sizeof((X)))
    776 #define MS1(X) memset((X), -1, sizeof((X)))
    777 #define LEN(X) strlen(X)
    778 #define F first
    779 #define S second
    780 using namespace std;
    781 typedef long long LL;
    782 typedef unsigned long long ULL;
    783 typedef long double LD;
    784 typedef pair<int,int> PII;
    785 typedef vector<int> VI;
    786 typedef vector<LL> VL;
    787 typedef vector<PII> VPII;
    788 typedef pair<LL,LL> PLL;
    789 typedef vector<PLL> VPLL;
    790 template<class T> void _R(T &x) { cin >> x; }
    791 void _R(int &x) { scanf("%d", &x); }
    792 void _R(LL &x) { scanf("%lld", &x); }
    793 void _R(double &x) { scanf("%lf", &x); }
    794 void _R(char &x) { scanf(" %c", &x); }
    795 void _R(char *x) { scanf("%s", x); }
    796 void R() {}
    797 template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
    798 template<class T> void _W(const T &x) { cout << x; }
    799 void _W(const int &x) { printf("%d", x); }
    800 void _W(const LL &x) { printf("%lld", x); }
    801 void _W(const double &x) { printf("%.16f", x); }
    802 void _W(const char &x) { putchar(x); }
    803 void _W(const char *x) { printf("%s", x); }
    804 template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
    805 template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
    806 void W() {}
    807 template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
    808 #ifdef HOME
    809  #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
    810 #else
    811  #define DEBUG(...)
    812 #endif
    813 int MOD = 1e9+7;
    814 void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
    815 /*}}}*/
    816 const int SIZE = 1e6+10;
    817 LL a[SIZE],num[SIZE];
    818 bool done[SIZE],be_added[SIZE];
    819 int n;
    820 LL K;
    821 LL get_upper_bound(int i){
    822     LL v=a[i]/num[i];
    823     if(v*num[i]!=a[i])v++;
    824     return v;
    825 }
    826 LL get_next_upper_bound(int i){
    827     LL v=a[i]/(num[i]-1);
    828     if(v*(num[i]-1)!=a[i])v++;
    829     return v;
    830 }
    831 LL go(){
    832     if(K==n){
    833         return a[n-1]-a[0];
    834     }
    835     LL ll=1,rr=a[n-1];
    836     while(ll<rr){
    837         LL mm=(ll+rr)/2;
    838         LL need=0;
    839         REP(i,n){
    840             if(a[i]>mm)need+=a[i]/mm;
    841             else need++;
    842         }
    843         if(need>=K)ll=mm+1;
    844         else rr=mm;
    845     }
    846     LL low=ll;
    847     VPLL pp;
    848     LL need=0;
    849     REP(i,n){
    850         if(a[i]>=low){
    851             num[i]=a[i]/low;
    852             pp.PB({a[i]/(num[i]+1),i});
    853         }
    854         else {
    855             num[i]=1;
    856         }
    857         need+=num[i];
    858     }
    859     {
    860         bool fail=0;
    861         REP(i,n){
    862             if(get_upper_bound(i)>=low){
    863                 fail=1;
    864                 break;
    865             }
    866         }
    867         if(!fail) return low-1-min(low-1,a[0]);
    868     }
    869     REP(i,n){
    870         if(a[i]>=low&&a[i]/(num[i]+1)==low-1){
    871             LL v=a[i]/(low-1);
    872             LL mi=min(v-num[i],K-need);
    873             num[i]+=mi;
    874             need+=mi;
    875             if(need==K)break;
    876         }
    877     }
    878     priority_queue<PLL,VPLL,greater<PLL>>added;
    879     priority_queue<PLL>top;
    880     LL mi=a[0];
    881     REP(i,n){
    882         if(num[i]>1){
    883             added.push(MP(get_next_upper_bound(i),i));
    884         }
    885         top.push(MP(get_upper_bound(i),i));
    886         mi=min(mi,a[i]/num[i]);
    887     }
    888     LL an=top.top().F-mi;
    889     REP(i,n)be_added[i]=done[i]=0;
    890     LL ma=low-1;
    891     while(!top.empty()&&!added.empty()){
    892         int id=top.top().S;
    893         if(be_added[id])break;
    894         done[id]=1;
    895         top.pop();
    896         num[id]++;
    897         mi=min(mi,a[id]/num[id]);
    898         auto tmp=added.top();
    899         added.pop();
    900         if(done[tmp.S])break;
    901         be_added[tmp.S]=1;
    902         num[tmp.S]--;
    903         if(num[tmp.S]>1)added.push({get_next_upper_bound(tmp.S),tmp.S});
    904         ma=max(ma,tmp.F);
    905         an=min(an,(top.empty()?ma:max(ma,top.top().F))-mi);
    906     }
    907     return an;
    908 }
    909 void solve(){
    910     LL L;
    911     //R(n,K,L);
    912     R(L,n,K);
    913     K+=n+1;
    914     LL lt=0;
    915     REP(i,n){
    916         LL x;
    917         R(x);
    918         a[i]=x-lt;
    919         lt=x;
    920     }
    921     a[n++]=L-lt;
    922     sort(a,a+n);
    923     W(go());
    924 }
    925 int main(){
    926     CASET{
    927         solve();
    928     }
    929     return 0;
    930 }
    931 ```