Advertisement
matheus_monteiro

Holodeck Hacking

Jun 26th, 2022
863
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. int cnt[20];
  4.  
  5. void build_sums() {
  6.     for(int i = 0; i <= 9; ++i) {
  7.         for(int j = 0; j <= 9; ++j) {
  8.             cnt[i + j]++;
  9.         }
  10.     }
  11. }
  12.  
  13. long long count(long long val, long long pot, int first) {
  14.     if(!pot and !val) return 1;
  15.     if(val < 0 or val >= 20 * pot) return 0;
  16.     if(pot == 1) return (val & 1) ^ 1;
  17.     long long ans = 0;
  18.     for(int s = val % 10; s < 20; s += 10) {
  19.         ans += (cnt[s] - first) * count((val - s * pot - s) / 10, pot / 100, 0);
  20.         first = 0;
  21.     }
  22.     return ans;
  23. }
  24.  
  25. int main() {
  26.  
  27.     build_sums();
  28.     int t;
  29.     std::cin >> t;
  30.     while(t--) {
  31.         long long x;
  32.         long long ans = 0;
  33.         std::cin >> x;
  34.         for(long long d = 1; d <= x + 1; d *= 10) {
  35.             ans += count(x, d, 1);
  36.         }
  37.         std::cout << ans << std::endl;
  38.     }
  39.     return 0;
  40. }
Advertisement
RAW Paste Data Copied
Advertisement