fork(1) download
  1. const fs = require('fs');
  2.  
  3. const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
  4. const a = Number(input[0]);
  5. const b = Number(input[1]);
  6.  
  7. const countClaps = (n) => {
  8. if (n < 1) return 0;
  9. const s = String(n);
  10.  
  11. const memo = new Map();
  12.  
  13. const dp = (pos, tight, leading) => {
  14. if (pos === s.length) {
  15. return [1, 0];
  16. }
  17.  
  18. const key = `${pos}|${tight ? 1 : 0}|${leading ? 1 : 0}`;
  19. if (memo.has(key)) return memo.get(key);
  20.  
  21. const limit = tight ? Number(s[pos]) : 9;
  22. let totalNumbers = 0;
  23. let totalClaps = 0;
  24.  
  25. for (let d = 0; d <= limit; d++) {
  26. const newTight = tight && d === limit;
  27. const newLeading = leading && d === 0;
  28.  
  29. const [cnt, clp] = dp(pos + 1, newTight, newLeading);
  30.  
  31. totalNumbers += cnt;
  32. totalClaps += clp;
  33.  
  34. if (!newLeading && (d === 3 || d === 6 || d === 9)) {
  35. totalClaps += cnt;
  36. }
  37. }
  38.  
  39. const result = [totalNumbers, totalClaps];
  40. memo.set(key, result);
  41. return result;
  42. };
  43.  
  44. const [_n, totalClapsFrom0ToN] = dp(0, true, true);
  45. return totalClapsFrom0ToN;
  46. };
  47.  
  48. const solve369 = (a, b) => countClaps(b) - countClaps(a - 1);
  49.  
  50. console.log(solve369(a, b));
Success #stdin #stdout 0.05s 40428KB
stdin
1 100
stdout
60