跳转至

Problem A. No Nine

Kickstart Round B 2018

题目链接: https://code.google.com/codejam/contest/dashboard?c=10284486

1、题目描述

This contest is open for practice. You can try every problem as many times as you like, though we won't keep track of which problems you solve. Read the Quick-Start Guide to get started.

Small input 7 points Solve A-small
Large input 13 points Solve A-large

Problem

No Nine is a counting game that you can try when you are bored. In this game, you are only allowed to say numbers that are legal. A number is legal if and only if all of the following are true:

  • it is a natural number (i.e. in the set {1, 2, 3...})
  • it does not contain the digit 9 anywhere in its base 10 representation
  • it is not divisible by 9

For example, the numbers 16 and 17 are legal. The numbers 18, 19, 17.2, and -17 are not legal.

On the first turn of the game, you choose and say a legal number F. On each subsequent turn, you say the next legal number. For example, if you played a game with F = 16, you would say 16, 17, 20, 21, and so on.

Alice is very good at this game and never makes mistakes. She remembers that she played a game in which the first number was F and the last number was L (when she got tired of the game and stopped), and she wonders how many turns were in the game in total (that is, how many numbers she said).

Input

The input starts with one line containing one integer T; T test cases follow. Each test case consists of a single line containing two integers F and L: the first and last numbers from the game, as described above.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1), and y is the number of the turns played in the game.

Limits

1 ≤ T ≤ 100. F does not contain a 9 digit. F is not divisible by 9. L does not contain a 9 digit. L is not divisible by 9.

Small dataset

$ 1 ≤ F < L ≤ 10^6 $

Large dataset

1 ≤ F < L ≤ 10^{18}

Sample

Input           Output 

2               Case #1: 9
16 26           Case #2: 4
88 102

In Sample Case #1, the game lasted for 9 turns, and the numbers Alice said were: 16, 17, 20, 21, 22, 23, 24, 25, 26.

In Sample Case #2, the game lasted for 4 turns, and the numbers Alice said were: 88, 100, 101, 102.

2、解题思路

由于数据集很大,因此不能一个一个去判断,只能寻找中间的规律

经过分析得到,满足条件的数据按照下面的规律:

  • 0-9:8
  • 10-19:8
  • 20-29:8

我们发现,每次递增10,则会增加8个元素

特殊情况为:90-99,满足条件的为0

  • 0-99:72 = 8*9
  • 100-199:72 = 8*9

  • 200-199:72=8*9

  • 0-999:648=8*9*9

  • 1000-2000:648=8*9*9

  • 2000-3000:648=8*9*9
  • 0-9999:5832=8*9*9*9

如上所示,依次类推

因为提供的是两个数,F与L,我们分别计算0-F与0-L的结果,然后,R(0-L)-R(0-F)+1,即为最终结果

def calculate_line(F, L):
    f_nums = calculate(F)
    l_nums = calculate(L)
    return l_nums - f_nums + 1


def calculate(num):
    count = 0
    power = 0
    temp_num = num

    while temp_num > 0:

        if power == 0:
            count += judge_nums(num // 10 * 10, num)
        else:
            current_num = temp_num % 10
            current_num = current_num if current_num < 9 else current_num - 1
            count += current_num * (9 ** (power - 1)) * 8
        power += 1
        temp_num //= 10
    return count


def judge_nums(first, last):
    count = 0
    for i in range(first, last + 1):
        if str(i).find('9') == -1 and i % 9:
            count += 1
    return count

对于最后面几个数字需要特殊判断

3、测试数据集

  • 小数据集
100
88 102
372 461581
427480 427487
747466 846825
840 111021
325 257248
453 705313
218065 218074
512 880446
350 657250
248 480874
667832 884126
453 821647
102831 303586
777630 814525
7 526182
678383 678388
211166 410071
810178 810188
437 643143
220133 220141
7044 205276
263 606124
118 630123
21736 21746
136871 136875
235 284036
876 166267
410584 713330
256530 526265
254201 318223
8205 8211
367 403628
775 415545
587 333017
62171 286453
183011 183021
16 26
503 602407
361 873266
142 776661
848 760565
455 342446
546 351181
512 464303
26 243615
11 652217
272622 604005
38 547136
212455 618287
161155 161164
3673 3676
16 218776
363586 531764
104 143032
451 127680
543 400777
618646 618654
61325 110578
806447 806451
538 715082
114 154028
77776 77777
175 832667
60577 60581
35 656647
1 2
125035 125041
52676 81372
764 665688
510 748112
672637 672640
584 180368
175 734041
242 232618
411446 411447
1 1000000
157777 807542
164648 721412
647452 647456
236 667408
712816 785842
724 287221
230 135188
580 866011
2 3
586064 586066
433 625461
643 626773
743 768201
372 263516
628 347574
285 315232
523 751618
867 273842
274 518172
86113 86117
272 223700
340411 523315
213 813047
  • 大数据集
100
134 345003354268427150
37722564158777743 37722564158777746
553 744070800163010120
1 1000000000000000000
20 653161544328834085
262 312751415740440344
787 765488712621837568
834 836003763370515747
251055677350652765 251055677350652767
687680825673347760 687680825673347763
2 3
113728855458826550 113728855458826551
534 612241450425221431
238605161774822471 424447873427222135
755 543513120631246886
437 268871007147576328
188 148105657834618881
523 142014055450384705
66 866082783616213480
14 558356132200118300
264 627434366046502025
335760340027663525 335760340027663533
863 681143534478248341
34586772532124308 307412606172378586
480 562033048381046574
24 745472640880804307
423607014662003552 423607014662003560
88 102
671 288414115311485370
377520164340020446 377520164340020453
73248256132240682 570177841434462116
82101021638858264 82101021638858272
583 342830610753471710
163146004776237513 474683304070075441
101520605261482523 101520605261482531
47420857307851376 47420857307851385
276540626178267812 276540626178267814
421 134257881665606023
403 783211307023271010
670248680058038166 670248680058038168
524 244166755620186420
414247380374331121 767483282202134586
521 265157607862557226
328228727004765710 600738016175866240
573758114026187038 573758114026187046
836 160223476285736776
262 548455147134753562
80 103765757741357164
825 548537830413770147
553027568065573218 877340416724406166
44262525468870276 44262525468870280
435374303840178431 435374303840178432
350 421610055541764202
411287537104773848 816480672504511075
271858168881546036 271858168881546037
478 306701574442816512
146261153716600665 751345540814843052
566266065263125471 566266065263125473
274663785867234818 274663785867234826
110825356517657022 844167334872388088
205 557203230231461411
24 816312864177065800
84821254406128373 425261223251256066
241 427628000461482016
547 101185864723603540
768 156854746648135538
16 26
773 420146512654685453
508245353378380456 538687417707842413
737 112121528445015785
732 247375517116136183
1 2
316 305783106815705471
52671005661335883 662166222648864764
146 564486171783243348
248727420144001022 255133053358152667
544855571884645373 753780466853250468
67 761187261580137417
115 552731034428065874
635 333706734011212582
58 316862800575710873
212 221232434522830242
580 475225402583648154
228 208043478361776340
707014363361204480 837803052171447475
411 225186463680646243
313 320470785730057168
81827278843181633 386426000418686742
570 157737751456104582
202 173086167460445771
30 445341306026475708
716 107862771340743223
21461024181415810 716631542205713425
410427502212752014 410427502212752015
77776 77777
424 632654433526561318
337 350062858235163872
132607503130466657 315513837273428101
325367554842505655 325367554842505664
255510041185758531 384118872558371363