The reason why you got time limit is that you don't use optimal algorithm. Your algorithm can be even correct, but to pass you need downgrade your algorithm. Maybe you could find some formula that would describe the whole process. Python is not the case here. You would get the same time limit issue with C.

I launched your script with N = 10000000 and K = 2 and it took 1.833s on my machine to get the correct answer when the time limit is 0.25s. Of course it will grow up nonlinearly with bigger N. So it would take ages with N = 10^9 (the edge value).

$ time echo "10000000 2" | python 1131_bruteforce.py

real    0m1.833s
user    0m1.824s
sys     0m0.007s


P.S. I don't need your money if you finally solve it :)

Edited by author 13.02.2020 06:12

Edited by author 13.02.2020 06:12

Correct me if I'm wrong, but isn't test #2 invalid because it has one more possible answer?

5
3 checks
dealing turn
5 checks
3 bets 10
5 raises 5 to 15

for test #2 answer, wouldn't:
2
3 bets 10
5 raises 5 to 15

be correct too?

and for test #3 raises
shouldn't it be
3 raises 80 to 100

Thx in advance

EDIT: Sorry, i misundestood

Edited by author 02.12.2019 06:28

Edited by author 02.12.2019 06:28

Edited by author 21.02.2020 17:41

Accepted!!!!
BFS - very good thing!!!!

#include <iostream>
#include <algorithm>
#include <string>

unsigned counter = 0;
void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){
    if(splitIndex[i] == 0){
        std::cout<<str.substr(0, i+1)<<" ";
    }else{
        printPalindroms(splitIndex, splitIndex[i]-1, str);
        std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" ";
    }
}

int main()
{
    std::string strr;
    std::cin>>strr;
    const char* str = strr.data();

    unsigned length = strr.size();
    unsigned arrSize = (length*length + length)/2;
    bool *pArrData = new bool[arrSize];
    bool **pArr = new bool*[length];

    unsigned short *splitWeights = new unsigned short [length];
    unsigned short *splitIndex = new unsigned short[length];

    std::fill(pArrData, pArrData + arrSize, false);
    std::fill(splitWeights, splitWeights + length, length +2);
    std::fill(splitIndex, splitIndex + length, 0);

    unsigned offset = 0;
    for(unsigned i = 0; i<length; ++i){
        pArr[i] = pArrData + offset;
        offset += length - i;
    }

    // init the first row
    std::fill(pArr[0], pArr[0] + length, true);

    //init the second row
    for(unsigned i = 0; i<length - 1; ++i){
        if(str[i] == str[i+1]){
             pArr[1][i] = true;
        }
    }

    for(unsigned i = 2; i < length; ++i){
        for(unsigned j = 0; j< length - i; ++j){
            if(pArr[i-2][j+1] && str[j] == str[j+i]){
                pArr[i][j] = true;
            }
        }
    }

    for(unsigned  i = 0; i < length; ++i){
        if(pArr[i][0] == true){
            splitWeights[i] = 0;
            splitIndex[i] = 0;
        }else{
            for(unsigned j = 1; j <= i; ++j){
                if(pArr[i-j][j]){
                    unsigned short temp = splitWeights[j-1] + 1;
                    if(temp < splitWeights[i]){
                        splitWeights[i] = temp;
                        splitIndex[i] = j;
                    }
                }
            }
        }
    }

    std::cout<<splitWeights[length -1] + 1<<std::endl;

    printPalindroms(splitIndex, length - 1, strr);

    delete[] splitIndex;
    delete[] splitWeights;
    delete[] pArr;
    delete[] pArrData;


    return 0;
}

Let's start from the beginning:
Let R(n) will be the function that returns count of unique staircases.
Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks.
Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step.

G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n))

G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0)

We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j).

But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n)

//Alloc and init matrix g with zeroes

//Calculat g matrix
for(i = 2; i<=N; ++i){
    g[i][0] = 1;
    for(j=1; j<i;++j){
        g[i][0] += g[i-j, j];
    }
    for(j=1; j<i;++j){
        g[i][j] = g[i][j-1] - g[i-j,j];
    }
}
cout<<g[N][0]-1;

Edited by author 09.02.2020 17:14

did u get answer
448 0
?

It's a nice case to fix program but still it doesn't fix WA7.

Edited by author 09.02.2020 15:46

I got AC. I'm stupid.

Don't use sort!

1) Please read task, especially "from the last one till the first" carefully. Look at the example.
2) Your sqrt function lies. https://ideone.com/wcJVz0

L=p^(q-1),p and q prima numbers.

The 1st assumption is right.
The 2nd one seems to be wrong. I can't say exactly if the result always fits in int64, but temporary (or itermediate) calculations exceed 2^64 for sure.

Answer to your test is wrong. In this test the denominators of intermediate fractions (before reduction) exceed 2^64.

My AC program answer:
1/6265197409

I got Wa22(ac 1-21) under positions:
r1*r2!=k*k-"irrational";(BUT IF i>min and i<MAX ONLY!)
else
1/sqrt(r)=a/sqrt(r1)+b/sqrt(r2);
a,b- recursion f(n,2i)=f(n-1,i),f(n,2i+1)=f(n-1,i)+f(n-1,i+1)
All- __int64
AC now:
a,b<=30- by induction.
int- is enought, nor __int64, nor BigInteger

Edited by author 27.02.2011 12:18

We have 4 case of perfect position of birds. I found the amount of flips for all cases. I used min_element() from algorithm.h to find the result, but it gave me WA 9. Then i replaced min_element() and found minimal by myself and my code finally accepted. Hope it will help you, good luck!

  for(i=0; i<=n*9; ++i){
      ans += soma[i]*soma[i];
  }

i is out of soma range.

are there any test?

У меня аналогичная ошибка. В том, что файл содержит один публичный класс, совпадающий с именем файла уверен на 100%. Причем проверил на файлах, которые отправлял ранее и удачно решенные, тоже самое.

Даже решение из руководства не проходит...