прикреплённый файл:oolym-2013-1-bN.py к странице LecturesVMSH/Python/2013-03-22

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Был обычный весенний вечер. За окном завывала метель. Бухгалтер Евгений скучал
   5 …бла-бла-бла…
   6 
   7 Короче.
   8 Имеется последовательность цифр. Следует подсчитать количество
   9 всевозможных разбиений этой последовательности на отрезки вида
  10   [....1][....2][....3][....4][....5][....6][....7][....8]
  11 с учётом, что любого отрезка в ней может не быть (только не всех).
  12 Дополнительное условие: в начале каждого отрезка стоимт не 0
  13 Ответ дать в виде остатка от деления на 1000000007
  14 '''
  15 
  16 import sys
  17 
  18 def gen():
  19     '''Это генератор тестовых условий. Он не участвует в решении!'''
  20     import random
  21     size=len(sys.argv)>2 and sys.argv[2][0] in "123456789" and int(sys.argv[2]) or 999999
  22     last=sys.argv[1].isdigit() and sys.argv[1][0] or random.choice("0123456789")
  23     sys.stdout.write(random.choice("123456789"))
  24     size-=1
  25     for i in xrange(size-1):
  26         sys.stdout.write(random.choice("0123456789"))
  27     sys.stdout.write(last)
  28 
  29 if len(sys.argv)>1:
  30     gen()
  31     sys.exit(0)
  32 
  33 Buf=raw_input()
  34 if Buf[-1] in "09" or Buf[0]=="0":
  35     print 0
  36     sys.exit(0)
  37 
  38 def checkn():
  39     '''Эта неправильная :( проверочная функция не входит в решение!'''
  40     LL=tuple(reversed(Buf))  # перевернём строку для удобства подсчёта
  41     def chk(D,n):
  42         # решить задачу для цифры, строго меньшей D, и подстроки с началом в n
  43         # строка слишком короткая или начинается не с той цифры
  44         if n>len(LL)-2 or LL[n]=='0' or LL[n]>=D: return 0
  45         # Хотя бы одно решение есть (в конце строки стоит не 0)
  46         res=1
  47         # съедим '0'
  48         for k in xrange(n+1,len(LL)):
  49             if LL[k]!='0': break
  50         # добавим все варианты разбиения на отрезки
  51         for j in xrange(k+1,len(LL)):
  52             res+=chk(LL[n],j)
  53         return res%1000000007
  54     return chk('9',0)
  55 
  56 def check():
  57     '''Эта проверочная функция не входит в решение!'''
  58     LL=tuple(reversed(Buf))  # перевернём строку для удобства подсчёта
  59     def chk(n):
  60         # решить задачу для подстроки с началом в n
  61         # подстрока считается проверенно годной, поэтому одно решение
  62         # есть всегда (единственный отрезок с началом в начале)
  63         res=1
  64         for k in xrange(n+1,len(LL)-2):
  65             # Найдем все места, где может начинаться наш отрезок
  66             # и заканчиваться какой-то предыдущий
  67             if LL[k]!='0' and LL[k+1]!='0' and LL[k+1]<LL[n]:
  68                 res=(res+chk(k+1))%1000000007
  69         return res
  70     return chk(0)
  71 
  72 # Отсюда начинается решение задачи
  73 
  74 # Количество решений для каждой цифры,
  75 # предпоследняя цифра и результат для неё,
  76 # последняя цифра и результат для неё
  77 D,IDO,Old,New=[0]*10,0,0,0
  78 # Цифра в конце последнего отрезка
  79 Mx=int(Buf[-1])
  80 # Цикл по всем возможным концам отрезков, кроме последнего
  81 for k in xrange(1,len(Buf)-2):
  82     c=Buf[k]
  83     i=int(c)
  84     # А точно ли тут возможен конец одного отрезка?
  85     if i==0: continue
  86     # Если при этом невозможно начало следующего отрезка, решений нет
  87     # Иначе как минимум один вариант: все предыдущие цифры — это одно число.
  88     # Плюс все решения для всех меньших цифр, вычисленные на позапрошлом шаге,
  89     # потому что каждое из них годится в качестве продолжения.
  90     New=i<Mx and Buf[k+1]!='0' and (1+sum(D[1:i])) or 0
  91     D[IDO]=(D[IDO]+Old)%1000000007
  92     Old,IDO=New,i
  93     #print "*",D,Buf[:k+1]
  94 D[IDO]=(D[IDO]+Old)%1000000007
  95 New=1+sum(D[:Mx])
  96 #print "#",D,Buf[:k+1]
  97 c,cn=check(),New
  98 if c!=cn:
  99     print c,cn,Buf
 100     sys.exit(1)
 101 else: print c