SRM 510 2 250TheAlmostLuckyNumbersDivTwo(数位dp)

SRM 510 2 250TheAlmostLuckyNumbersDivTwo

Problem Statement

John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, an almost lucky number is a number that contains at most one non-lucky digit in its decimal representation. Return the total number of almost lucky numbers between a and b, inclusive.

Definition

ClassTheAlmostLuckyNumbersDivTwo
Methodfind
Parametersint , int
Returnsint
Method signatureint find(int a, int b)

(be sure your method is public)

Limits

Time limit (s)2.000
Memory limit (MB)64

Constraints

a will be between 1 and 1,000,000, inclusive.
b will be between a and 1,000,000, inclusive.

Test cases

- a4
- b7
Returns4

All numbers between 4 and 7 are almost lucky.
- a8
- b19
Returns4

Numbers 8, 9, 14 and 17 are almost lucky.
- a28
- b33
Returns0

No almost lucky numbers here.
- a1234
- b4321
Returns36

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <ctime>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <set>
  8 #include <vector>
  9 #include <sstream>
 10 #include <typeinfo>
 11 #include <fstream>
 12 
 13 using namespace std;
 14 int dp[10][10] , dp2[10][10];
 15 int dig[10] ;
 16 int vis[10] ;
 17 
 18 void init ()
 19 {
 20     memset (dp , 0 , sizeof(dp)) ;
 21     memset (dp2 , 0 , sizeof(dp2) ) ;
 22     for (int i = 0 ; i < 10 ; i ++) dp[1][i] = 1 ;
 23     for (int i = 2 ; i <= 7 ; i ++ ) {
 24         for (int j = 0 ; j < 10 ; j ++) {
 25           dp[i][j] += dp[i-1][4] + dp[i-1][7] ;
 26         }
 27     }
 28     int a , b , c = 0 , d = 0 ;
 29     for (int i = 1 ; i <= 7 ; i ++) for (int j = 0 ; j < 10 ; j ++) dp2[i][j] = dp[i][j] ;
 30     for (int i = 2 ; i <= 7 ; i ++) {
 31         a = dp[i][4] , b = dp[i][7] ;
 32         for (int j = 0 ; j < 10 ; j ++) {
 33             if (!(j == 4 || j == 7)) {
 34                 dp2[i][4] += dp[i-1][j] ;
 35                 dp2[i][7] += dp[i-1][j] ;
 36             }
 37             else if (j == 4) {
 38                 dp2[i][4] += c ;
 39                 dp2[i][7] += c ;
 40             }
 41             else if (j == 7) {
 42                 dp2[i][4] += d ;
 43                 dp2[i][7] += d ;
 44             }
 45         }
 46    //    printf ("dp[%d][4]=%d , dp[%d][7]=%d
" , i , dp[i][4] , i , dp[i][7]) ;
 47         c = dp2[i][4] - a , d = dp2[i][7] - b ;
 48     }
 49 }
 50 
 51 int cal (int x)
 52 {
 53     memset (dig , 0 , sizeof(dig)) ;
 54     memset (vis , 0 , sizeof(vis)) ;
 55     int ans = 0 ;
 56     int len = 1 ;
 57     int tmp = x ;
 58     int cnt = 0 ;
 59     while (x) {
 60         dig[len ++] = x % 10 ;
 61         x /= 10 ;
 62     }
 63     for (int i = len - 1 ; i >= 1 ; i --) {
 64         vis[i] = cnt ;
 65         if (dig[i] != 4 && dig[i] != 7) cnt ++ ;
 66     }
 67     //for (int i = 0 ; i < dig[1] ; i ++) ans += dp[1][i] ;
 68  //   ans += 10 ;
 69   //  printf ("hahaha") ;
 70   //  printf ("%d " , vis[0]) ;
 71    // for (int i = 1 ; i < len ; i ++) printf ("%d " , vis[i]) ; puts ("") ;
 72     for (int i = 1 ; i < len  ; i ++) {
 73        printf ("vis[%d]=%d:

" , i , vis[i] ) ;
 74         if (vis[i] == 0 ) {
 75             for (int j = 0 ; j < dig[i] ; j ++) ans += dp2[i][j] ;
 76         }
 77         else if (vis[i] == 1) {
 78             for (int j = 0 ; j < dig[i] ; j ++) if (j == 4 || j == 7) ans += dp[i][j]  , printf ("dp[%d][%d]=%d
" , i , j , dp[i][j]) ;
 79         }
 80         if (i == len -1 ) ans -= dp[i][0] ;
 81     }
 82     printf ("ans = %d
" , ans ) ;
 83     if (len == 2) {
 84         ans += dp[1][0] ;
 85     }
 86     else {
 87         ans += dp[1][0] ;
 88         for (int i = 1 ; i < len - 1 ; i ++) {
 89             for (int j = 1 ; j < 10 ; j ++) ans += dp2[i][j] ;
 90         }
 91     }
 92     printf ("%d:ans = %d
" , tmp , ans) ;
 93     printf ("-----------------------------------
") ;
 94     return ans ;
 95 }
 96 
 97 class TheAlmostLuckyNumbersDivTwo {
 98     public:
 99     int find(int a, int b) {
100         puts ("") ;
101         if (a > b) swap(a,b) ;
102         init () ;
103         printf ("%d ~ %d
" , a , b) ;
104      //   printf ("%d - %d
" , cal(b) , cal(a-1)) ;
105         return cal(b+1) - cal(a) ;
106         //return 0 ;
107     }
108 };
109 
110 // CUT begin
111 ifstream data("TheAlmostLuckyNumbersDivTwo.sample");
112 
113 string next_line() {
114     string s;
115     getline(data, s);
116     return s;
117 }
118 
119 template <typename T> void from_stream(T &t) {
120     stringstream ss(next_line());
121     ss >> t;
122 }
123 
124 void from_stream(string &s) {
125     s = next_line();
126 }
127 
128 template <typename T>
129 string to_string(T t) {
130     stringstream s;
131     s << t;
132     return s.str();
133 }
134 
135 string to_string(string t) {
136     return """ + t + """;
137 }
138 
139 bool do_test(int a, int b, int __expected) {
140     time_t startClock = clock();
141     TheAlmostLuckyNumbersDivTwo *instance = new TheAlmostLuckyNumbersDivTwo();
142     int __result = instance->find(a, b);
143     double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC;
144     delete instance;
145 
146     if (__result == __expected) {
147         cout << "PASSED!" << " (" << elapsed << " seconds)" << endl;
148         return true;
149     }
150     else {
151         cout << "FAILED!" << " (" << elapsed << " seconds)" << endl;
152         cout << "           Expected: " << to_string(__expected) << endl;
153         cout << "           Received: " << to_string(__result) << endl;
154         return false;
155     }
156 }
157 
158 int run_test(bool mainProcess, const set<int> &case_set, const string command) {
159     int cases = 0, passed = 0;
160     while (true) {
161         if (next_line().find("--") != 0)
162             break;
163         int a;
164         from_stream(a);
165         int b;
166         from_stream(b);
167         next_line();
168         int __answer;
169         from_stream(__answer);
170 
171         cases++;
172         if (case_set.size() > 0 && case_set.find(cases - 1) == case_set.end())
173             continue;
174 
175         cout << "  Testcase #" << cases - 1 << " ... ";
176         if ( do_test(a, b, __answer)) {
177             passed++;
178         }
179     }
180     if (mainProcess) {
181         cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl;
182         int T = time(NULL) - 1435285921;
183         double PT = T / 60.0, TT = 75.0;
184         cout << "Time   : " << T / 60 << " minutes " << T % 60 << " secs" << endl;
185         cout << "Score  : " << 250 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl;
186     }
187     return 0;
188 }
189 
190 int main(int argc, char *argv[]) {
191     cout.setf(ios::fixed, ios::floatfield);
192     cout.precision(2);
193     set<int> cases;
194     bool mainProcess = true;
195     for (int i = 1; i < argc; ++i) {
196         if ( string(argv[i]) == "-") {
197             mainProcess = false;
198         } else {
199             cases.insert(atoi(argv[i]));
200         }
201     }
202     if (mainProcess) {
203         cout << "TheAlmostLuckyNumbersDivTwo (250 Points)" << endl << endl;
204     }
205     return run_test(mainProcess, cases, argv[0]);
206 }
207 // CUT end

View Code

数位dp,,,,蛮有趣的，写了我三天，还好现在是考试季。数位dp能大大减少复杂度，拿这道题来说。如果用暴力来做要O(1e6),但用数位dp来的话，只需O(70)!!!!!

但同时换来的是复杂的构造。