fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ms(s,n) memset(s,n,sizeof(s))
  5. #define all(a) a.begin(),a.end()
  6. #define present(t, x) (t.find(x) != t.end())
  7. #define sz(a) int((a).size())
  8. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  9. #define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
  10. #define pb push_back
  11. #define pf push_front
  12. #define fi first
  13. #define se second
  14. #define mp make_pair
  15. #define endl "\n"
  16.  
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef pair<int,int> pi;
  22. typedef vector<int> vi;
  23. typedef vector<pi> vii;
  24.  
  25. const int MOD = (int) 1e9+7;
  26. const int INF = (int) 1e9+1;
  27. inline ll gcd(ll a,ll b){ll r;while(b){r=a%b;a=b;b=r;}return a;}
  28. inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  29.  
  30. bool cmp(pi a, pi b){
  31.     return a.se < b.se;
  32. }
  33.  
  34. int num(char c){
  35.     return c - '0';
  36. }
  37.  
  38. void TC(){
  39.     string s; cin >> s;
  40.     int len = s.length();
  41.     int dp[len+1][3];
  42.     int pre[len+1];
  43.     ms(dp, 0);
  44.     ms(pre, 0);
  45.     int sum = 0;
  46.     dp[0][0] = 1;
  47.     for(int i = 1; i <= len; i++){
  48.         sum += s[i-1]-'0';
  49.         sum %= 3;
  50.         pre[i] = sum;
  51.         dp[i][sum] += 1;
  52.         dp[i][0] += dp[i-1][0];
  53.         dp[i][1] += dp[i-1][1];
  54.         dp[i][2] += dp[i-1][2];
  55.     }
  56.     int ans = 0;
  57.     for(int i = 1; i <= len; i++){
  58.         int num = s[i-1] - '0';
  59.         if(num == 8) ++ans;
  60.         if(i >=2 ){
  61.             int tmp = (s[i-2] - '0') * 10 + (s[i-1] -'0');
  62.             if(tmp % 8 == 0 && tmp % 3 != 0){
  63.                 ++ans;
  64.             }
  65.         }
  66.         if(i >= 3){
  67.             int tmp = (s[i-3] - '0') * 100 +(s[i-2] - '0') * 10 + s[i-1] - '0';
  68.             if(tmp % 8 == 0){
  69.                 ans += i - 2;
  70.                 ans -= dp[i-3][pre[i]];
  71.             }
  72.         }
  73.     }
  74.     cout << ans << endl;
  75. }
  76.  
  77. int main(){
  78.     //freopen("input.txt","r", stdin);
  79.     //freopen("output.txt","w",stdout);
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(nullptr);
  82.     int t; cin >> t;
  83.     while(t--){
  84.         TC();
  85.     }
  86. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
1
5784
stdout
copy 
2
https://ideone.com/zZjIvB
language:
C++14 (gcc 8.3)
created:
44 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!