ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1017. Staircases

How can I improve this program?
Posted by thefourtheye 23 Jun 2013 10:27
Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]

It produces following output (first column input, second column output)

0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63

But it exceeds 1 sec limit when the input is 88.

Edited by author 23.06.2013 10:28

Edited by author 23.06.2013 10:28
Re: How can I improve this program?
Posted by thefourtheye 23 Jun 2013 16:06
thefourtheye wrote 23 June 2013 10:27
Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]

It produces following output (first column input, second column output)

0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63

But it exceeds 1 sec limit when the input is 88.

Never mind. Memoization did the trick.