Code don't works with big numbers, Python 3.4

k=int(input())

a=[]

a.append(0)

a.append(1)

a.append(1)

a.append(2)

a.append(2)

s=0

for j in range(5,k+1):

if j%2==1:

for i in range(1,j//2+1):

s+=a[i]

a.append(s)

else:

for i in range(1,j//2):

s+=a[i]

s=s+a[j//2]-1

a.append(s)

s=0

print(a)

Re: Code don't works with big numbers, Python 3.4

You are printing a, print(a). A is a LIST.

Re: Code don't works with big numbers, Python 3.4

FUUUCK, thanks, its so stupid error(

Re: Code don't works with big numbers, Python 3.4

but code still not works, starting with the second test, and in example program gives WA, but I check code at least 3 times, I cant find errors((

Re: Code don't works with big numbers, Python 3.4

I don't understand how does your algorithm work. My AC - program is calculating values sequentially for different ladders. Time complexity is O(N*N*N). So, it is basically two dimensional dynamic programming.

Re: Code don't works with big numbers, Python 3.4

And your algorithm has time complexity just O(N*N). It is not surprising that I can't understand it without explanation. It is extremely optimized solution, with heavy math behind.

*Edited by author 23.06.2017 23:28*

Re: Code don't works with big numbers, Python 3.4

you don't need heavy math you can in O(n^2) time and O(n^2) space i don't know how u got O(n^3)

cin >> n;

for(int i = 0; i < n; i++)

dp[i][0] = 1;

for(int i = 1; i < n; i++)

for(int j = 1; j <= n; j++)

{

dp[i][j] = dp[i - 1][j];

if(j >= i)

dp[i][j] += dp[i - 1][j - i];

}

cout << dp[n - 1][n];

*Edited by author 11.08.2017 05:18*

*Edited by author 11.08.2017 05:19*

Re: Code don't works with big numbers, Python 3.4

When I was solving it

I thought

There is a staircase consists of X cubes and it's height is Y

Then just add some new stair with height Z

Z is strictly greater than Y

Get new staircase with X+Z cubes and height Z

Re: Code don't works with big numbers, Python 3.4

But also I know

There is a solution based on generating functions

I can't understand generating functions theory

So I have AC on task but don't understand generating functions and that guy didn't had AC at the moment

So probably generating functions are hard for him just like they are hard for me

That is why I have called generating functions "heavy math"

Re: Code don't works with big numbers, Python 3.4

tell me more, do you know a good article for this?