SRM 722, D1, 250-Pointer (TCPhoneHome)

James S. Plank

Thu Oct 12 20:36:49 EDT 2017

BTW, if you want to print a long long named v with printf(), you do:

printf("%lld\n", v);

sprintf() and sscanf() work the same way.


This is a good problem for a map, which can help you keep track of excluded regions of numbers, and non-excluded regions of numbers. I'm going to walk you though how I recommend that you solve this problem. Even if you solve it in another way, I urge you to read through this, because it is a very good technique.
Each prefix defines two numbers: In example 0, where d equals 7, you have the following: Let's do a few subtle ones that aren't part of the examples, again when d equals 7: Ok -- what I suggest is the following. You are going to have a map whose keys are long longs, and whose vals are integers. Start by inserting 0 and 10(d+1) into the map with vals of zero. Then, go through the following steps: Your map now has a wonderful structure to it -- you can traverse it, maintaining an integer that will tell you whether various values are excluded or not. Let's call that integer E, and initialize it to zero. Traverse the map. For each value: Return the running total.

I understand that I'm not explaining how this works, but I'm hoping that you understand it after seeing it. The map handles what happens when excluded regions overlap.

I'm going to go through all of the examples and show you l, h, the map, the values of E, and the running total as you run through the map. I've added example 5 to main.cpp, which has two cases that may trip you up, and example 6, which is from the topcoder system test.


Example 0 Digits = 7, sp is `specialPrefixes' sp[i] l[i] h[i] ------- ------- ------- 0 0 1000000 1 1000000 2000000 911 9110000 9120000 Key Next-Key Val | E Total ------- ------- -- | -- ------- Start Start | 0 0 0 1000000 -1 | -1 0 1000000 2000000 0 | -1 0 2000000 9110000 1 | 0 7110000 9110000 9120000 -1 | -1 7110000 9120000 10000000 1 | 0 7990000 7990000
Example 1 Digits = 10, sp is `specialPrefixes' sp[i] l[i] h[i] ---------- ---------- ---------- 0 0 1000000000 1 1000000000 2000000000 911 9110000000 9120000000 Key Next-Key Val | E Total ---------- ---------- -- | -- ---------- Start Start | 0 0 0 1000000000 -1 | -1 0 1000000000 2000000000 0 | -1 0 2000000000 9110000000 1 | 0 7110000000 9110000000 9120000000 -1 | -1 7110000000 9120000000 10000000000 1 | 0 7990000000 7990000000
Example 2 Digits = 8, sp is `specialPrefixes' sp[i] l[i] h[i] -------- -------- -------- 1 10000000 20000000 12 12000000 13000000 123 12300000 12400000 Key Next-Key Val | E Total -------- -------- -- | -- -------- Start Start | 0 0 0 10000000 0 | 0 10000000 10000000 12000000 -1 | -1 10000000 12000000 12300000 -1 | -2 10000000 12300000 12400000 -1 | -3 10000000 12400000 13000000 1 | -2 10000000 13000000 20000000 1 | -1 10000000 20000000 100000000 1 | 0 90000000 90000000
Example 3 Digits = 9, sp is `specialPrefixes' sp[i] l[i] h[i] --------- --------- --------- 12 120000000 130000000 13 130000000 140000000 14 140000000 150000000 Key Next-Key Val | E Total --------- --------- -- | -- --------- Start Start | 0 0 0 120000000 0 | 0 120000000 120000000 130000000 -1 | -1 120000000 130000000 140000000 0 | -1 120000000 140000000 150000000 0 | -1 120000000 150000000 1000000000 1 | 0 970000000 970000000
Example 4 Digits = 3, sp is `specialPrefixes' sp[i] l[i] h[i] --- --- --- 411 411 412 Key Next-Key Val | E Total --- --- -- | -- --- Start Start | 0 0 0 411 0 | 0 411 411 412 -1 | -1 411 412 1000 1 | 0 999 999
Example 5 Digits = 8, sp is `specialPrefixes' sp[i] l[i] h[i] -------- -------- -------- 00200 200000 201000 999 99900000 100000000 Key Next-Key Val | E Total -------- -------- -- | -- -------- Start Start | 0 0 0 200000 0 | 0 200000 200000 201000 -1 | -1 200000 201000 99900000 1 | 0 99899000 99900000 100000000 -1 | -1 99899000 99899000
Example 6 Digits = 14, sp is `specialPrefixes' sp[i] l[i] h[i] -------------- -------------- -------------- 817575480605 81757548060500 81757548060600 0186 1860000000000 1870000000000 899928586 89992858600000 89992858700000 6281723 62817230000000 62817240000000 2715311551770 27153115517700 27153115517710 489488 48948800000000 48948900000000 8988028888062 89880288880620 89880288880630 833678624 83367862400000 83367862500000 93 93000000000000 94000000000000 8922 89220000000000 89230000000000 503736 50373600000000 50373700000000 9377 93770000000000 93780000000000 718754 71875400000000 71875500000000 800265796 80026579600000 80026579700000 9855611210637 98556112106370 98556112106380 8404855 84048550000000 84048560000000 563 56300000000000 56400000000000 48715 48715000000000 48716000000000 5039180064 50391800640000 50391800650000 3943531 39435310000000 39435320000000 31137291 31137291000000 31137292000000 63495 63495000000000 63496000000000 Key Next-Key Val | E Total -------------- -------------- -- | -- -------------- Start Start | 0 0 0 1860000000000 0 | 0 1860000000000 1860000000000 1870000000000 -1 | -1 1860000000000 1870000000000 27153115517700 1 | 0 27143115517700 27153115517700 27153115517710 -1 | -1 27143115517700 27153115517710 31137291000000 1 | 0 31127290999990 31137291000000 31137292000000 -1 | -1 31127290999990 31137292000000 39435310000000 1 | 0 39425308999990 39435310000000 39435320000000 -1 | -1 39425308999990 39435320000000 48715000000000 1 | 0 48704988999990 48715000000000 48716000000000 -1 | -1 48704988999990 48716000000000 48948800000000 1 | 0 48937788999990 48948800000000 48948900000000 -1 | -1 48937788999990 48948900000000 50373600000000 1 | 0 50362488999990 50373600000000 50373700000000 -1 | -1 50362488999990 50373700000000 50391800640000 1 | 0 50380589639990 50391800640000 50391800650000 -1 | -1 50380589639990 50391800650000 56300000000000 1 | 0 56288788989990 56300000000000 56400000000000 -1 | -1 56288788989990 56400000000000 62817230000000 1 | 0 62706018989990 62817230000000 62817240000000 -1 | -1 62706018989990 62817240000000 63495000000000 1 | 0 63383778989990 63495000000000 63496000000000 -1 | -1 63383778989990 63496000000000 71875400000000 1 | 0 71763178989990 71875400000000 71875500000000 -1 | -1 71763178989990 71875500000000 80026579600000 1 | 0 79914258589990 80026579600000 80026579700000 -1 | -1 79914258589990 80026579700000 81757548060500 1 | 0 81645226950490 81757548060500 81757548060600 -1 | -1 81645226950490 81757548060600 83367862400000 1 | 0 83255541289890 83367862400000 83367862500000 -1 | -1 83255541289890 83367862500000 84048550000000 1 | 0 83936228789890 84048550000000 84048560000000 -1 | -1 83936228789890 84048560000000 89220000000000 1 | 0 89107668789890 89220000000000 89230000000000 -1 | -1 89107668789890 89230000000000 89880288880620 1 | 0 89757957670510 89880288880620 89880288880630 -1 | -1 89757957670510 89880288880630 89992858600000 1 | 0 89870527389880 89992858600000 89992858700000 -1 | -1 89870527389880 89992858700000 93000000000000 1 | 0 92877668689880 93000000000000 93770000000000 -1 | -1 92877668689880 93770000000000 93780000000000 -1 | -2 92877668689880 93780000000000 94000000000000 1 | -1 92877668689880 94000000000000 98556112106370 1 | 0 97433780796250 98556112106370 98556112106380 -1 | -1 97433780796250 98556112106380 100000000000000 1 | 0 98877668689870 98877668689870