Прикреплённый файл «oolym-2013-1-bN.py»
Загрузка 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
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2013-03-29 09:45:21, 1.1 KB) [[attachment:2013-03-22.paystep.py]]
- [получить | показать] (2013-03-29 13:21:16, 3.7 KB) [[attachment:2013-03-22.raspil.py]]
- [получить | показать] (2013-03-29 09:48:53, 3.4 KB) [[attachment:2013-03-22.turtle.py]]
- [получить | показать] (2013-03-22 15:22:12, 2.6 KB) [[attachment:oolym-2013-1-b.py]]
- [получить | показать] (2013-03-29 09:48:17, 4.7 KB) [[attachment:oolym-2013-1-bN.py]]
Вам нельзя прикреплять файлы к этой странице.