fork download
  1. 'use strict';
  2.  
  3. process.stdin.resume();
  4. process.stdin.setEncoding('utf8');
  5.  
  6. var remainder = '';
  7.  
  8. process.stdin.on('data', function(chunk) {
  9. remainder += chunk;
  10. });
  11.  
  12. process.stdin.on('end', function() {
  13. // Tách input theo dòng và loại bỏ những dòng trống
  14. var lines = remainder.split('\n').filter(function(line) {
  15. return line.trim() !== '';
  16. });
  17.  
  18. // Giả sử input nằm ở dòng đầu tiên: "a b"
  19. if (lines.length > 0) {
  20. var tokens = lines[0].trim().split(/\s+/);
  21. var a = parseInt(tokens[0], 10);
  22. var b = parseInt(tokens[1], 10);
  23.  
  24. var result = computeClaps(b) - (a > 0 ? computeClaps(a - 1) : 0);
  25. process.stdout.write(result.toString() + "\n");
  26. }
  27. });
  28.  
  29. function computeClaps(n) {
  30. var s = n.toString();
  31. var memo = {};
  32.  
  33. function dp(pos, tight, started) {
  34. if (pos === s.length) return { ways: 1, claps: 0 };
  35.  
  36. var key = pos + '_' + (tight ? 1 : 0) + '_' + (started ? 1 : 0);
  37. if (memo.hasOwnProperty(key)) return memo[key];
  38.  
  39. var ways = 0, claps = 0;
  40. var limit = tight ? parseInt(s.charAt(pos), 10) : 9;
  41.  
  42. for (var d = 0; d <= limit; d++) {
  43. var newTight = tight && (d === limit);
  44. var newStarted = started || (d !== 0);
  45. var res = dp(pos + 1, newTight, newStarted);
  46. var clap = (newStarted && (d === 3 || d === 6 || d === 9)) ? 1 : 0;
  47. ways += res.ways;
  48. claps += res.claps + res.ways * clap;
  49. }
  50.  
  51. memo[key] = { ways: ways, claps: claps };
  52. return memo[key];
  53. }
  54.  
  55. return dp(0, true, false).claps;
  56. }
  57.  
Success #stdin #stdout 0.09s 36112KB
stdin
999999 10000000
stdout
19200006