Problem:


Problem H: Eleven Lover

Edward Leven loves multiples of eleven very much. When he sees a number, he always tries
to find consecutive subsequences (or substrings) forming multiples of eleven. He calls such
subsequences as 11-sequences. For example, he can find an 11-sequence 781 in a number 17819.

He thinks a number which has many 11-sequences is a good number. He would like to find out
a very good number. As the first step, he wants an easy way to count how many 11-sequences
are there in a given number. Even for him, counting them from a big number is not easy.
Fortunately, one of his friends, you, is a brilliant programmer. He asks you to write a program
to count the number of 11-sequences. Note that an 11-sequence must be a positive number
without leading zeros.

Input

The input is a sequence of lines each of which contains a number consisting of less than or equal
to 80000 digits.

The end of the input is indicated by a line containing a single zero, which should not be processed.

Output

For each input number, output a line containing the number of 11-sequences.

You can assume the answer fits in a 32-bit signed integer.

Sample Input

17819
1111
11011
1234567891011121314151617181920
0

Output for the Sample Input

1
4
4
38



Sample input:
17819
1111
11011
1234567891011121314151617181920
0


Sample output:
1
4
4
38

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = 1
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= 1
    print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def fact(num):
    if num <= 1:
        return 1
    return fact(num - 1) + 1

print fact(100000)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def fact(num):
    if num <= 1:
        return 1
    return fact(num - 1) + 1

print fact(150000)

Submission status: Memory Limit Exceeded

Solution code:
targ =  input()
while True:
    ans = [[0 for n in range(len(targ))] for m in range(len(targ) -1)]
    for o in range(len(targ)):
        for i in range(o+1,len(targ)):
            if targ[o] == '0':
                ans[o][i] = ans[o-1][i]
            elif i == len(ans):
                ans[o][i] = int((int(targ[o] + targ[o+1:i+1])) % 11 == 0) + ans[o][i-1] + ans[o-1][i]
    
            else:
                ans[o][i] = int((int(targ[o] + targ[o+1:i+1])) % 11 == 0) + ans[o][i-1]
    print(ans[-1][-1])
    targ = input()
    if targ == '0':
        break

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        s = S()
        if s == '0':
            break
        d = collections.defaultdict(int)
        r = 0
        for c in s:
            c = int(c)
            nd = collections.defaultdict(int)
            for k,v in d.items():
                nd[(k*10+c) % 11] = v
            if c > 0:
                nd[c] += 1
            r += nd[0]
            d = nd
        rr.append(r)

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
while(True):
    s = input()
    m = len(s)
    if s == "0":
        quit()
    dp = [[0 for j in range(11)] for i in range(m)]
    for i in range(m):
        n = int(s[i])
        if n == 0:
            tmp = dp[i-1][1:]
            tmp.reverse()
            dp[i] = [dp[i-1][0]]+tmp
        else:
            tmp = dp[i-1][1:]
            tmp.reverse()
            tmp = [dp[i-1][0]]+tmp
            dp[i] = tmp[-n:]+tmp[:-n]
            dp[i][n] += 1
    ans = 0
    for i in range(m):
        ans += dp[i][0]
    print(ans)

Submission status: Accepted

Solution code:
#教室内の位置は右*中央
#問題は「Eleven Lover」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182&lang=jp)
#本当は問題「Planning Rolling Blackouts」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1176&lang=jp)
#を解こうとしたのですが、小区間での分割をひたすら統合する解法までは立ったものの実装力がなかったので一旦やめました
while(True):
    #今回はinputの数字を文字列として一桁ずつ扱った方が嬉しいのでint()しません
    s = input()
    m = len(s)
    #0を弾くやつ
    if s == "0":
        quit()
    #pdfに書いていた方針と全く同じやり方をします
    #配列dpをA_i,jとしてとります
    dp = [[0 for j in range(11)] for i in range(m)]
    for i in range(m):
        n = int(s[i])
        #ここで、どこかの桁が0になってる時に注意します
        #というのも、問題文中に「0から始まる数は11の倍数に含めない」としてあるからです
        #したがって0が出た時はそこまでの数字を10倍する効果しか持たないことになります
        if n == 0:
            tmp = dp[i-1][1:]
            tmp.reverse()
            #dp[i][0]=dp[i-1][0]
            #dp[i][k]=dp[i-1][11-k] (if k >= 1)となります(これがtmp.reverse()の意図)
            dp[i] = [dp[i-1][0]]+tmp
        else:
            #やるだけ
            tmp = dp[i-1][1:]
            tmp.reverse()
            #10倍なのでA[i][k] (k>=1)をリバース(上と同じ)
            tmp = [dp[i-1][0]]+tmp
            #i桁目の数字を見てその分A_i,jをずらします
            #添字に注意
            dp[i] = tmp[-n:]+tmp[:-n]
            dp[i][n] += 1 #インクリメントも忘れずに
    #あとはdp[k][0]を足すだけ
    print(sum([i[0] for i in dp]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = {}
    for i in range(11):
        m[i] = []
    m[0].append(11)
    diff = 0
    even = True
    S = reversed(S)
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        m[diff].append(num)
        even = (not even)
    ans = 0
    #print m
    for i in range(11):
        lst = m[i]
        for i in range(len(lst)):
            if lst[i] != 0:
                ans += i
    
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = True
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even = (not even)
    
    print ans

Submission status: Accepted

Solution code:
while True:
    S = raw_input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = True
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even = (not even)
    
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = 1
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = 0
    even = 1
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = ans = 0
    even = 1
    S = reversed(S)
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = ans = 0
    even = 1
    S = reversed(S)
    for c in S:
        diff = (diff + int(c) * even) % 11
        if int(c) != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
 S = raw_input()
 if S == '0':break
 m = [1] + [0 for i in range(10)]
 diff = ans = 0
 even = 1
 S = reversed(S)
 for c in S:
  diff = (diff + int(c) * even) % 11  
  if int(c) != 0:
   ans += m[diff]
  m[diff] += 1
  even *= -1
 print ans

Submission status: Accepted

Solution code:
while True:
 S = raw_input()
 if S == '0':break
 m = [1] + [0 for i in range(10)]
 d = A = 0
 e = 1
 S = reversed(S)
 for c in S:
  d = (d + int(c) * e) % 11  
  if int(c) != 0:
   A += m[d]
  m[d] += 1
  e *= -1
 print A

Submission status: Accepted

Solution code:
while True:
 S = raw_input()
 if S == '0':break
 m = [1] + [0 for i in range(10)]
 d = A = 0
 e = 1
 S = reversed(S)
 for c in S:
  d = (d + int(c) * e) % 11  
  if int(c) != 0:A += m[d]
  m[d] += 1
  e *= -1
 print A

Submission status: Accepted

Solution code:
while True:
 S=raw_input()
 if S=='0':break
 m=[1]+[0 for i in range(10)]
 d=A=0
 e=1
 S=reversed(S)
 for c in S:
  d=(d+int(c)*e)%11  
  if int(c)!=0:A+=m[d]
  m[d]+=1
  e*=-1
 print A

Submission status: Accepted

Solution code:
def solve(n):
    length = len(n)
    dp = [[0 for j in range(11)] for i in range(length)]
    for i in range(length):
        q = int(n[i])
        if q == 0:
            tmp = dp[i-1][1:]
            tmp.reverse()
            dp[i] = [dp[i-1][0]]+tmp
        else:
            tmp = dp[i-1][1:]
            tmp.reverse()
            tmp = [dp[i-1][0]]+tmp
            dp[i] = tmp[-q:]+tmp[:-q]
            dp[i][q] += 1 
    return(sum([i[0] for i in dp]))

while True:
    n=input()
    
    if n== str(0):
        break
    else:
        print(solve(n))

Submission status: Accepted

Solution code:
INF = 10 ** 7
def solve(N):
    ans = 0
    for i in range(len(N)):
        if i == 0:
            before = [0] * 11
            before[int(N[i])] += 1
            ans += before[0]
        elif N[i] == '0':
            now = [0] * 11
            for j in range(11):
                k = j*10%11
                now[k] += before[j]
            ans += now[0]
            before = now
        else:
            M = int(N[i])
            now = [0] * 11
            for j in range(11):
                k = (j*10 + M)%11
                now[k] += before[j]
            now[M%11] += 1
            ans += now[0]
            before = now
    print(ans)

def main():
    while True:
        N = input()
        if N == '0':
            return
        solve(N)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    N=list(input())
    if N==["0"]:
        exit()
    else:
        ans=0
        cnt={i:0 for i in range(11)}
        sums=0
        cnt[0]=1
        N=N[::-1]
        for i in range(len(N)):
            sums+=pow(10,i,11)*int(N[i])
            sums%=11
            cnt[sums]+=1
            if int(N[i])==0:
                ans-=(cnt[sums]-1)
        for i in range(11):
            K=cnt[i]
            ans+=(K*(K-1))//2
        print(ans)
        return solve()
if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
while 1:
    N = input()
    if N == "0":
        break
    dp = [[0 for i in range(11)] for j in range(len(N) + 1)]
    for i, c in enumerate(N, 1):
        for j, kazu in enumerate(dp[i - 1]):
            if kazu != 0:
                dp[i][(j * 10 + int(c)) % 11] = kazu
        if int(c) != 0:
            dp[i][int(c) % 11] += 1
    ans = 0
    for d in dp:
        ans += d[0]
    print(ans)

Submission status: Accepted

Solution code:
a = input()
while (int(a) != 0):
    remain = [0for i in range(11)]
    remain[int(a[0])] = remain[int(a[0])] + 1  ##V0
    n = len(a)
    cnt = 0
    for i in range(1,n):
        copy = remain[:]
        remain = [0for i in range(11)]
        a_i = int(a[i])
        if (a_i != 0):
            for k in range(11):
                rem = (k*10 + a_i)%11
                remain[rem] += copy[k]
            remain[a_i] += 1
        elif (a_i == 0):
            for k in range(11):
                rem = (k*10 + a_i)%11
                remain[rem] += copy[k]
        cnt += remain[0]
    print(cnt)
    a = input()

Submission status: Accepted

Solution code:
while True:
    S = raw_input()[::-1]
    if S == '0' : break
    m = [1] + [0] * 10
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num : ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Runtime Error

Solution code:
targ =  input()
while True:
    ans = 0
    length = len(targ)
    for o in range(length-1):
        disp = [0 for n in range(length)]
        for i in range(o+1,length):
            if targ[o] == '0':
                disp[i] = ans
            elif i == length - 1:
                disp[i] = int((int(targ[o] + targ[o+1:i+1])) % 11 == 0) + disp[i-1] + ans
            else:
                disp[i] = int((int(targ[o] + targ[o+1:i+1])) % 11 == 0) + disp[i-1]
        ans = disp[-1]
        del disp
    print(ans)
    targ = input()
    if targ == '0':
        break

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = reversed(raw_input())
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def fact(num):
    if num <= 1:
        return 1
    return fact(num - 1) + 1

print fact(200000)

Submission status: Runtime Error

Solution code:
while 1:
	n = raw_input()
	if n == "0": break
	c = 0
	for i in range(2,len(n) + 1):
		for sp in range(len(n) - i + 1):
			if n[sp] != "0" and int(n[sp:sp + i])%11 == 0:
				c += 1
	print c

Submission status: Runtime Error

Solution code:
def isEle(n):
	s = 0
	for i in range(len(n)):
		s += (-1)**i * int(n[i])
	return True if s%11 == 0 else False
		
while 1:
	n = raw_input()
	if n == "0": break
	c = 0
	for i in range(2,len(n) + 1):
		for sp in range(len(n) - i + 1):
			if n[sp] != "0" and isEle(n[sp:sp + i]):
				c += 1
	print c

Submission status: Runtime Error

Solution code:
while 1:
	n = raw_input()
	if n == "0": break
	size = len(n)
	s = 0
	diff = [0]*(size + 1)
	for i in range(size):
		s += (-1)**i * int(n[i])
		diff[i + 1] = s
	c = 0
	for sp in range(size - 1):
		if n[sp] == "0":
			continue
		for l in range(2,size - sp + 1):
			if abs((diff[sp + l] - diff[sp])%11) == 0:
				c += 1
	print c

Submission status: Runtime Error

Solution code:
while 1:
	try:
		n = raw_input()
		if n == "0": break
		size = len(n)
		s = 0
		diff = [0]*(size + 1)
		for i in range(size):
			s += (-1)**i * int(n[i])
			diff[i + 1] = s
		c = 0
		for sp in range(size - 1):
			if n[sp] == "0":
				continue
			for l in range(2,size - sp + 1):
				if abs((diff[sp + l] - diff[sp])%11) == 0:
					c += 1
		print c
	except:
		pass