#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==