#http://p...content-available-to-author-only...e.com/q/268022/51441
 
 
# s:
#   input digit string that should be checked
# L:
#   the start of the substring that should be investigated
# L:
#   the end of the substring that should be investigated
# cnt:
#   number of 3divisble substrings found so far
# ss0:
#   number of substrings that end at the current position
#   and are divisible by 3
# ss1:
#   number of substrings that end at the current position
#   and have the remainder 1 when divided by 3
# ss2:
#   number of substrings that end at the current position
#   and have the remainder 2 when divided by 3
 
 
def ss(s,L,R):
    cnt=0
    (ss0,ss1,ss2)=(0,0,0)
    for i in range(L,R+1):
        r=int(s[i])%3
        if r==0:
            ss0+=1
        elif r==1:
            (ss0,ss1,ss2)=(ss2,ss0,ss1)
            ss1+=1
        elif r==2:
            (ss0,ss1,ss2)=(ss1,ss2,ss0)
            ss2+=1
        cnt+=ss0
    return(cnt)
 
print(ss('392301',0,len('392301')-1))
print(ss('2035498',2,5))
 

I2h0dHA6Ly9wLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9xLzI2ODAyMi81MTQ0MQoKCiMgczoKIyAgIGlucHV0IGRpZ2l0IHN0cmluZyB0aGF0IHNob3VsZCBiZSBjaGVja2VkCiMgTDoKIyAgIHRoZSBzdGFydCBvZiB0aGUgc3Vic3RyaW5nIHRoYXQgc2hvdWxkIGJlIGludmVzdGlnYXRlZAojIEw6CiMgICB0aGUgZW5kIG9mIHRoZSBzdWJzdHJpbmcgdGhhdCBzaG91bGQgYmUgaW52ZXN0aWdhdGVkCiMgY250OgojICAgbnVtYmVyIG9mIDNkaXZpc2JsZSBzdWJzdHJpbmdzIGZvdW5kIHNvIGZhcgojIHNzMDoKIyAgIG51bWJlciBvZiBzdWJzdHJpbmdzIHRoYXQgZW5kIGF0IHRoZSBjdXJyZW50IHBvc2l0aW9uCiMgICBhbmQgYXJlIGRpdmlzaWJsZSBieSAzCiMgc3MxOgojICAgbnVtYmVyIG9mIHN1YnN0cmluZ3MgdGhhdCBlbmQgYXQgdGhlIGN1cnJlbnQgcG9zaXRpb24KIyAgIGFuZCBoYXZlIHRoZSByZW1haW5kZXIgMSB3aGVuIGRpdmlkZWQgYnkgMwojIHNzMjoKIyAgIG51bWJlciBvZiBzdWJzdHJpbmdzIHRoYXQgZW5kIGF0IHRoZSBjdXJyZW50IHBvc2l0aW9uCiMgICBhbmQgaGF2ZSB0aGUgcmVtYWluZGVyIDIgd2hlbiBkaXZpZGVkIGJ5IDMKCgpkZWYgc3MocyxMLFIpOgogICAgY250PTAKICAgIChzczAsc3MxLHNzMik9KDAsMCwwKQogICAgZm9yIGkgaW4gcmFuZ2UoTCxSKzEpOgogICAgICAgIHI9aW50KHNbaV0pJTMKICAgICAgICBpZiByPT0wOgogICAgICAgICAgICBzczArPTEKICAgICAgICBlbGlmIHI9PTE6CiAgICAgICAgICAgIChzczAsc3MxLHNzMik9KHNzMixzczAsc3MxKQogICAgICAgICAgICBzczErPTEKICAgICAgICBlbGlmIHI9PTI6CiAgICAgICAgICAgIChzczAsc3MxLHNzMik9KHNzMSxzczIsc3MwKQogICAgICAgICAgICBzczIrPTEKICAgICAgICBjbnQrPXNzMAogICAgcmV0dXJuKGNudCkKCnByaW50KHNzKCczOTIzMDEnLDAsbGVuKCczOTIzMDEnKS0xKSkKcHJpbnQoc3MoJzIwMzU0OTgnLDIsNSkpCg==