QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136202#2412. Canvas LineBUET_TEAM_ONE#AC ✓4ms4056kbC++203.0kb2023-08-07 16:24:492023-08-07 16:24:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-07 16:24:50]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:4056kb
  • [2023-08-07 16:24:49]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long int ll;
#define endl            '\n'
#define pb             push_back
#define l first
#define r second
#define mp              make_pair
#define pll             pair<ll,ll> 
#define fill(x, y)     memset(x, y, sizeof(x))
#define all(x)         (x).begin(), (x).end()
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define IO	       { ios_base::sync_with_stdio(false); cin.tie(0); }
#define read(x)	       freopen(x, "r", stdin)
#define write(x)       freopen(x, "w", stdout)


using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;

const int N = 2000;
int dp[N][2];
int al[N][2];
vector<ii> canvas;
vector<int> pegs;
map<int, bool> atPos;

const int inf = 1e8;

int n, p;
int solve(int pos, int peg) {
    if (pos == n) return 0;
    if (dp[pos][peg] != -1) return dp[pos][peg];

    int already = 0;
    for (int i=0; i<pegs.size(); i++) 
        if (pegs[i] >= canvas[pos].first and pegs[i] <= canvas[pos].second) already++;
    
    al[pos][peg] = already + peg;

    if (already + peg > 2) return dp[pos][peg] = inf;
    if (pos == n-1) {
        return dp[pos][peg] = 2 - already - peg;
    }
    if (already + peg == 2) {
        return dp[pos][peg] = solve(pos + 1, 0);
    }
    else {
        if (canvas[pos].r == canvas[pos+1].l and !atPos[canvas[pos].r]) {
            dp[pos][peg] = min(solve(pos + 1, 1), solve(pos + 1, 0)) + (2 - already - peg);
        }
        else {
            dp[pos][peg] = solve(pos + 1, 0) + (2 - already - peg);
        }
        return dp[pos][peg];
    }

}



int main(){
    IO;
    cout<<fixed<<setprecision(2);
    
    memset(dp, -1, sizeof dp);
    cin >> n;

    canvas.resize(n+1);
    for (int i=0; i<n; i++) {
        cin >> canvas[i].first >> canvas[i].second;
    }   

    cin >> p;

    for (int i=0; i<p; i++) {
        int x;
        cin >> x;
        atPos[x] = true;
        pegs.push_back(x);
    }

    
    int x = solve(0, 0);
    if (x >= inf) {
        cout << "impossible" << endl;
    } 
    else {
        cout << x << endl;
        
        int peg = 0;
        for (int i=0; i<n; i++) {
            int req = 2 - al[i][peg];
            if (i == n-1 or dp[i][peg] == dp[i+1][0] + req) {
                peg = 0;
                vi place;
                for (int k=1; k<6; k++) {
                    if (atPos[canvas[i].l + k] == false) place.pb(canvas[i].l + k);
                }
                for (int k=0; k<req; k++) {
                    cout << place[k] << " ";
                }
            }
            else {
                peg = 1;
                vi place;
                for (int k=1; k<6; k++) {
                    if (atPos[canvas[i].l + k] == false) place.pb(canvas[i].l + k);
                }
                for (int k=0; k<req-1; k++) cout << place[k] << " ";
                cout << canvas[i].r << " ";
            }
        }
        cout << endl;

    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3516kb

input:

5
0 100
100 200
200 300
300 400
400 500
2
100 200

output:

4
1 300 400 401 

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

20
0 100
100 200
200 300
300 400
400 500
500 600
600 700
700 800
800 900
900 1000
1000 1100
1100 1200
1200 1300
1300 1400
1400 1500
1500 1600
1600 1700
1700 1800
1800 1900
1900 2000
3
300 900 2000

output:

18
1 100 200 400 500 600 700 800 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 

result:

ok 

Test #3:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

300
0 10
10 20
20 30
30 40
40 50
50 60
60 70
70 80
80 90
90 100
100 110
110 120
120 130
130 140
140 150
150 160
160 170
170 180
180 190
190 200
200 210
210 220
220 230
230 240
240 250
250 260
260 270
270 280
280 290
290 300
300 310
310 320
320 330
330 340
340 350
350 360
360 370
370 380
380 390
390 ...

output:

299
1 20 21 50 60 70 71 90 100 101 120 130 131 151 160 170 180 190 191 210 220 221 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650 660 670 680 690 700 710 720 730 740 750 760 770 7...

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

1
9000 9020
2
8990 9030

output:

2
9001 9002 

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

2
0 10
10 20
1
10

output:

2
1 11 

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

2
0 10
10 20
1
0

output:

2
10 11 

result:

ok 

Test #7:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

3
0 20
20 30
30 50
4
0 10 40 50

output:

2
21 22 

result:

ok 

Test #8:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

2
3000 13000
13010 13100
5
9120 11900 13000 13010 13090

output:

impossible

result:

ok 

Test #9:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

1
10 10000
1000
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5600 5700 5800 590...

output:

impossible

result:

ok 

Test #10:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

4
0 18
18 28
28 40
49 60
4
6 12 35 60

output:

3
19 28 50 

result:

ok 

Test #11:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

2
0 10
20 30
2
0 10

output:

2
21 22 

result:

ok 

Test #12:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

2
0 10
10 20
0


output:

3
1 10 11 

result:

ok 

Test #13:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

4
500 510
510 520
530 540
540 550
3
510 520 540

output:

3
501 531 541 

result:

ok 

Test #14:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

1000
0 10
20 30
40 50
60 70
80 90
100 110
120 130
140 150
160 170
180 190
200 210
220 230
240 250
260 270
280 290
300 310
320 330
340 350
360 370
380 390
400 410
420 430
440 450
460 470
480 490
500 510
520 530
540 550
560 570
580 590
600 610
620 630
640 650
660 670
680 690
700 710
720 730
740 750
76...

output:

1000
1 21 41 62 81 101 121 141 162 181 201 221 241 261 281 301 321 341 361 381 401 421 441 461 481 501 521 541 561 581 601 621 641 661 681 701 721 742 761 781 801 821 841 861 881 901 921 941 961 982 1001 1021 1041 1061 1081 1101 1121 1141 1161 1181 1201 1221 1241 1261 1281 1301 1321 1341 1361 1381 1...

result:

ok 

Test #15:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

1000
0 33
33 66
66 99
99 132
132 165
165 198
198 231
231 264
264 297
297 330
330 363
363 396
396 429
429 462
462 495
495 528
528 561
561 594
594 627
627 660
660 693
693 726
726 759
759 792
792 825
825 858
858 891
891 924
924 957
957 990
990 1023
1023 1056
1056 1089
1089 1122
1122 1155
1155 1188
1188...

output:

913
1 33 66 99 132 165 198 231 264 297 330 363 396 429 528 561 594 693 726 759 792 825 858 891 924 957 990 1056 1089 1122 1155 1188 1221 1254 1287 1320 1353 1386 1419 1420 1485 1518 1551 1584 1617 1650 1683 1716 1749 1782 1815 1881 1914 1947 1980 2013 2046 2112 2145 2178 2211 2244 2277 2310 2343 237...

result:

ok 

Test #16:

score: 0
Accepted
time: 3ms
memory: 3964kb

input:

1000
0 33
33 66
66 99
99 132
132 165
165 198
198 231
231 264
264 297
297 330
330 363
363 396
396 429
429 462
462 495
495 528
528 561
561 594
594 627
627 660
660 693
693 726
726 759
759 792
792 825
825 858
858 891
891 924
924 957
957 990
990 1023
1023 1056
1056 1089
1089 1122
1122 1155
1155 1188
1188...

output:

688
33 66 165 166 264 297 298 364 396 429 462 463 562 594 595 661 693 726 727 793 825 858 859 924 925 991 992 1056 1089 1122 1221 1320 1386 1419 1452 1518 1585 1617 1650 1717 1782 1815 1882 2014 2015 2079 2080 2211 2212 2310 2343 2376 2476 2541 2542 2607 2640 2706 2707 2805 2871 2904 2937 2970 3003 ...

result:

ok 

Test #17:

score: 0
Accepted
time: 3ms
memory: 3900kb

input:

1000
0 33
33 66
66 99
99 132
132 165
165 198
198 231
231 264
264 297
297 330
330 363
363 396
396 429
429 462
462 495
495 528
528 561
561 594
594 627
627 660
660 693
693 726
726 759
759 792
792 825
825 858
858 891
891 924
924 957
957 990
990 1023
1023 1056
1056 1089
1089 1122
1122 1155
1155 1188
1188...

output:

614
67 165 198 265 331 332 429 430 561 562 792 858 891 924 991 1056 1057 1122 1188 1255 1256 1320 1353 1551 1552 1651 1652 1716 1749 1849 1915 1947 1981 2047 2146 2178 2244 2311 2508 2509 2608 2609 2673 2706 2707 2806 2807 2871 2938 2939 3003 3036 3069 3135 3136 3234 3235 3333 3334 3432 3465 3498 34...

result:

ok 

Test #18:

score: 0
Accepted
time: 3ms
memory: 3920kb

input:

1000
0 33
33 66
66 99
99 132
132 165
165 198
198 231
231 264
264 297
297 330
330 363
363 396
396 429
429 462
462 495
495 528
528 561
561 594
594 627
627 660
660 693
693 726
726 759
759 792
792 825
825 858
858 891
891 924
924 957
957 990
990 1023
1023 1056
1056 1089
1089 1122
1122 1155
1155 1188
1188...

output:

415
231 232 297 363 396 496 595 596 727 826 827 925 1056 1057 1122 1155 1222 1387 1519 1585 1717 1848 1881 1948 2046 2113 2114 2212 2344 2410 2476 2477 2542 2574 2773 2839 2971 3003 3103 3135 3202 3234 3235 3367 3630 3697 3698 4060 4125 4225 4291 4292 4457 4588 4819 4820 4885 4886 5379 5380 5710 590...

result:

ok 

Test #19:

score: 0
Accepted
time: 3ms
memory: 3912kb

input:

1000
0 33
33 66
66 99
99 132
132 165
165 198
198 231
231 264
264 297
297 330
330 363
363 396
396 429
429 462
462 495
495 528
528 561
561 594
594 627
627 660
660 693
693 726
726 759
759 792
792 825
825 858
858 891
891 924
924 957
957 990
990 1023
1023 1056
1056 1089
1089 1122
1122 1155
1155 1188
1188...

output:

182
165 265 396 463 529 661 1156 1453 1717 1948 2079 2707 3069 3235 3236 3367 3368 3565 3631 3928 4423 4424 4884 4885 5050 5446 5447 5809 5974 6271 6568 6931 7161 7558 7986 7987 8119 8185 8383 8448 8613 8680 9043 9175 9241 9306 9439 9505 9571 9703 9835 10033 10397 10891 11056 11155 11716 11717 12475...

result:

ok 

Test #20:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

10
0 897295
897295 1185774
1185774 1234783
1234783 2032897
2032897 2992228
2992228 3861506
3861506 4515440
4515440 4530303
4530303 4960434
4960434 5039539
10
897295 1191004 1218782 2026187 2032897 3409148 3817647 4410915 4515440 4522602

output:

6
1 897296 2032898 4530304 4960434 4960435 

result:

ok 

Test #21:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

5
2 15
15 25
25 40
42 52
52 62
3
5 29 52

output:

4
15 25 43 53 

result:

ok 

Test #22:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

100
0 41275
41275 358342
358342 716632
716632 762394
762394 1021131
1021131 1425233
1425233 1844446
1844446 2502361
2502361 3130148
3130148 3984772
3984772 4413739
4413739 4634425
4634425 4772966
4772966 5289086
5289086 5997849
5997849 6276152
6276152 7056556
7056556 7275248
7275248 7373865
7373865 ...

output:

37
41275 358343 1021131 1021132 3984773 3984774 4772967 5289087 7373866 7701519 9593949 10494849 10494850 12835063 14734797 16258536 18497410 19002662 19297439 20202962 23039835 24514909 25327288 26025923 27495496 27942672 31256663 31516382 32913080 34648611 36519094 40002223 41492031 42110414 44854...

result:

ok 

Test #23:

score: 0
Accepted
time: 3ms
memory: 3972kb

input:

1000
0 304786
304786 1286505
1286505 1602298
1602298 1889356
1889356 2427543
2427543 3041205
3041205 3293335
3293335 3683972
3683972 4455853
4455853 5009532
5009532 5138657
5138657 5264375
5264375 5443816
5443816 5978077
5978077 6706267
6706267 6766803
6766803 7317810
7317810 7745466
7745466 7951246...

output:

400
1 304787 1602299 1889356 3041205 3041206 5009532 5138658 5443817 7745466 9567855 12574095 13089336 14175023 16811797 18148228 19601835 20510329 20510330 22143838 23347111 24134096 24295073 25245418 25800530 28530074 28530075 29699363 29699364 30864229 32163313 34465732 39586035 44760231 44838704...

result:

ok 

Test #24:

score: 0
Accepted
time: 3ms
memory: 3976kb

input:

1000
0 668627
668627 1493991
1493991 1955432
1955432 2462090
2462090 3348370
3348370 3649888
3649888 4232217
4232217 4920841
4920841 5154187
5154187 5824420
5824420 6496201
6496201 6692463
6692463 7679806
7679806 8184427
8184427 9056696
9056696 9415570
9415570 10371466
10371466 11055208
11055208 120...

output:

404
1493992 2462090 3649889 3649890 5154188 8184428 9056696 12026926 12813933 13150907 14283238 14456139 15319523 17854389 18699976 23379263 23379264 24016271 24578398 24996525 26342037 27108802 28399385 30111012 30111013 33534545 37154387 39637055 40382147 42172517 42172518 43627727 44753006 452855...

result:

ok 

Test #25:

score: 0
Accepted
time: 3ms
memory: 3952kb

input:

1000
0 729025
729025 1403003
1403003 1430577
1430577 1655007
1655007 2318039
2318039 3152162
3152162 3612408
3612408 3698378
3698378 3847122
3847122 4099203
4099203 4394638
4394638 4535183
4535183 4679224
4679224 4924266
4924266 5809106
5809106 6092706
6092706 6512636
6512636 7182863
7182863 7889942...

output:

309
1430577 2318040 3847122 4535184 6092707 7182863 9002493 10023694 11018026 13690360 14527914 15784600 18019683 19786517 21590100 24799630 25737468 26267475 30978137 32007433 33834880 35514783 36296277 39412486 40097278 41761972 42687472 43831863 45650986 48366539 50083096 52767150 55090088 560252...

result:

ok 

Test #26:

score: 0
Accepted
time: 3ms
memory: 4056kb

input:

1000
0 551688
551688 698391
698391 698615
698615 1524420
1524420 1823936
1823936 2477838
2477838 2648920
2648920 3634817
3634817 3954585
3954585 4387372
4387372 4749036
4749036 5696471
5696471 5917145
5917145 6471607
6471607 7138159
7138159 8064119
8064119 8853507
8853507 9794300
9794300 10024230
10...

output:

47
1823937 12311304 17610907 20465596 41242070 48067810 54592417 61081516 65519249 77197454 83567459 97614477 112468203 118427239 136585339 176898108 191683714 194282572 213875716 224100644 234486385 236985363 239320875 240056510 255868797 267733409 278752004 284037864 299705094 320316342 340880181 ...

result:

ok 

Test #27:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

1000
0 737798
737798 1692350
1692350 2375226
2375226 2910782
2910782 3102289
3102289 3905018
3905018 4281758
4281758 4632993
4632993 5380689
5380689 6270471
6270471 6477095
6477095 6956831
6956831 7035284
7035284 7484603
7484603 7625533
7625533 8474133
8474133 8475172
8475172 8952662
8952662 9482058...

output:

0


result:

ok 

Test #28:

score: 0
Accepted
time: 4ms
memory: 4028kb

input:

1000
0 10
10 20
20 30
30 40
40 50
50 60
60 70
70 80
80 90
90 100
100 110
110 120
120 130
130 140
140 150
150 160
160 170
170 180
180 190
190 200
200 210
210 220
220 230
230 240
240 250
250 260
260 270
270 280
280 290
290 300
300 310
310 320
320 330
330 340
340 350
350 360
360 370
370 380
380 390
390...

output:

1001
1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650 660 670 680 690 700 710 720 730 740 750 76...

result:

ok 

Test #29:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

1001
1 999000 1998000 2997000 3996000 4995000 5994000 6993000 7992000 8991000 9990000 10989000 11988000 12987000 13986000 14985000 15984000 16983000 17982000 18981000 19980000 20979000 21978000 22977000 23976000 24975000 25974000 26973000 27972000 28971000 29970000 30969000 31968000 32967000 3396600...

result:

ok 

Test #30:

score: 0
Accepted
time: 2ms
memory: 3940kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

1001
1 999000 1998000 2997000 3996000 4995000 5994000 6993000 7992000 8991000 9990000 10989000 11988000 12987000 13986000 14985000 15984000 16983000 17982000 18981000 19980000 20979000 21978000 22977000 23976000 24975000 25974000 26973000 27972000 28971000 29970000 30969000 31968000 32967000 3396600...

result:

ok 

Test #31:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

963
278 373
558 1124
1816 3746
4646 5751
7119 7749
8001 8531
10824 10916
11489 11614
11778 12015
12413 13786
14482 15328
15554 15901
16704 17819
18297 18517
18623 18923
18934 19443
20309 20465
20906 21053
21360 21524
23313 23360
23372 23649
23654 23693
24766 25747
25795 26469
26587 27322
27429 27798...

output:

impossible

result:

ok 

Test #32:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

3
0 60
60 120
120 140
4
20 60 80 120

output:

impossible

result:

ok 

Test #33:

score: 0
Accepted
time: 2ms
memory: 3956kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

1001
1 999000 1998000 2997000 3996000 4995000 5994000 6993000 7992000 8991000 9990000 10989000 11988000 12987000 13986000 14985000 15984000 16983000 17982000 18981000 19980000 20979000 21978000 22977000 23976000 24975000 25974000 26973000 27972000 28971000 29970000 30969000 31968000 32967000 3396600...

result:

ok 

Test #34:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

impossible

result:

ok 

Test #35:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

1001
1 999000 1998000 2997000 3996000 4995000 5994000 6993000 7992000 8991000 9990000 10989000 11988000 12987000 13986000 14985000 15984000 16983000 17982000 18981000 19980000 20979000 21978000 22977000 23976000 24975000 25974000 26973000 27972000 28971000 29970000 30969000 31968000 32967000 3396600...

result:

ok 

Test #36:

score: 0
Accepted
time: 2ms
memory: 3988kb

input:

1000
0 999000
999000 1998000
1998000 2997000
2997000 3996000
3996000 4995000
4995000 5994000
5994000 6993000
6993000 7992000
7992000 8991000
8991000 9990000
9990000 10989000
10989000 11988000
11988000 12987000
12987000 13986000
13986000 14985000
14985000 15984000
15984000 16983000
16983000 17982000
...

output:

1001
1 999000 1998000 2997000 3996000 4995000 5994000 6993000 7992000 8991000 9990000 10989000 11988000 12987000 13986000 14985000 15984000 16983000 17982000 18981000 19980000 20979000 21978000 22977000 23976000 24975000 25974000 26973000 27972000 28971000 29970000 30969000 31968000 32967000 3396600...

result:

ok 

Test #37:

score: 0
Accepted
time: 3ms
memory: 3964kb

input:

1000
200 626
986 1415
1499 1525
1545 1631
1778 2124
2269 2347
2541 3428
4010 4152
4202 4383
4589 4695
4754 4947
4961 5674
5760 5778
5907 6513
7229 7460
7496 7632
8001 8390
8580 8643
8880 8944
9028 9231
9912 9995
10233 10368
10421 10477
10508 11192
11518 11821
12271 12302
12696 14543
14552 15289
1557...

output:

2000
201 202 987 988 1500 1501 1546 1547 1779 1780 2270 2271 2542 2543 4011 4012 4203 4204 4590 4591 4755 4756 4962 4963 5761 5762 5908 5909 7230 7231 7497 7498 8002 8003 8581 8582 8881 8882 9029 9030 9913 9914 10234 10235 10422 10423 10509 10510 11519 11520 12272 12273 12697 12698 14553 14554 15576...

result:

ok 

Test #38:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

1000
17 97
142 227
413 2466
2862 3208
3853 4194
5001 5286
5809 7448
7971 8576
8775 9174
9288 9593
9724 9774
10880 11010
11770 12970
13192 13240
13486 14498
14531 14890
15025 15937
16142 16612
16759 16792
17143 17155
17364 17620
17685 18038
18382 19725
19873 19883
19989 20990
21024 21288
21318 21328
...

output:

1801
18 19 143 144 414 415 2863 2864 3854 3855 5002 5003 5810 5811 7972 7973 8776 8777 9289 9290 9725 9726 10881 10882 11771 11772 13193 13194 13487 13488 14532 14533 15026 15027 16143 16144 16760 16761 17144 17145 17365 17366 17686 17687 18383 18384 19874 19875 19990 19991 21025 21026 21319 21320 2...

result:

ok 

Test #39:

score: 0
Accepted
time: 3ms
memory: 3924kb

input:

1000
500191 500310
500340 500524
500567 501061
501677 501687
501718 502130
502475 502623
502722 502894
502921 503453
503475 503509
503630 503647
504072 504906
505359 505435
505559 506024
506167 506397
507248 507376
507776 508667
508723 508996
509601 509904
510124 510252
510740 511076
511165 511513
5...

output:

2000
500192 500193 500341 500342 500568 500569 501678 501679 501719 501720 502476 502477 502723 502724 502922 502923 503476 503477 503631 503632 504073 504074 505360 505361 505560 505561 506168 506169 507249 507250 507777 507778 508724 508725 509602 509603 510125 510126 510741 510742 511166 511167 5...

result:

ok 

Test #40:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

1000
2147 2551
2606 2664
3757 5547
7714 8439
8799 9596
9951 10144
10241 10420
10672 10682
10721 11109
11189 11887
14469 14777
15853 16655
16894 17178
17371 19016
19354 19832
20990 21404
21495 21535
21887 23158
23884 23900
24488 25562
25643 26249
26324 26506
27320 27450
28236 28261
28377 28396
28516 ...

output:

1801
83972 106227 106228 106780 106781 107037 107038 107436 107437 108113 108114 109274 109275 109535 109536 110107 110108 110891 110892 111041 111042 111317 111318 112017 112018 112451 112452 114953 114954 115170 115171 115584 115585 116724 116725 118783 118784 119158 119159 119492 119493 122079 12...

result:

ok 

Test #41:

score: 0
Accepted
time: 4ms
memory: 3948kb

input:

1000
0 10
10 20
20 30
30 40
40 50
50 60
60 70
70 80
80 90
90 100
100 110
110 120
120 130
130 140
140 150
150 160
160 170
170 180
180 190
190 200
200 210
210 220
220 230
230 240
240 250
250 260
260 270
270 280
280 290
290 300
300 310
310 320
320 330
330 340
340 350
350 360
360 370
370 380
380 390
390...

output:

666
1 20 31 50 61 80 91 110 121 140 151 170 181 200 211 230 241 260 271 290 301 320 331 350 361 380 391 410 421 440 451 470 481 500 511 530 541 560 571 590 601 620 631 650 661 680 691 710 721 740 751 770 781 800 811 830 841 860 871 890 901 920 931 950 961 980 991 1010 1021 1040 1051 1070 1081 1100 1...

result:

ok