Straightforward Link/Cut Tree solution. Just dfs the input grid and build the tree graph represented by LCT; represent paths as bamboo splay trees: just make dfs-child the right child if turnout is good and do nothing otherwise. All parents in dfs-tree that do not satisfy turnout make path parents (see LCT terminology). Now each query is just a single access—sometimes called expose—operation that saves all path parents on the path.

You should iterate from v.begin to v.end. No the reverse way.

It can be solved only with 2 divisions in BigDecimal, but answer length is about 32000 so [maybe] toString gives TLE on conversion binary data to decimal representation.
If somebody knows, how to solve this problem - please tell me

Please, write your messages in English, because it's international language. We, Russians, don't understand O'zbek

lol
http://ega-math.narod.ru/Quant/Tickets.htm
need learn math )

Edited by author 13.12.2010 16:36

Edited by author 03.02.2012 16:53

print(([0,10,670,55252,4816030])[int(input())//2])
hahahahahahaha

:D

ha ha

I found many other ways.
1)Monte Carlo - slow for this problem
2)Separation of real and complex roots. Can be used to solve this problem. Binary search for Re(z)=alfa, Re(z)=beta, Im(z)=gamma, Im(z)=delta
  Березин И.С., Жидков Н.П. Методы вычислений, Т.2. М.: ГИФМЛ, 1959.
3)Ferrari method.
  Куликов Л.Я. Алгебра и теория чисел
4)Barstow method. It's numeric iterative method.
  Саманчук_билеты_с_ответами.pdf
  Численные методы

I use combination from 3):
binary search for yo
then formulas

Edited by author 12.08.2018 21:04

only test 7 I can't get right ans. I have 33
And WA4

Removed my post, because apparently I can't alphabet :)

Edited by author 12.07.2016 14:45

IN TEST CASE 2, FOR INPUT 0 , WHY ANS IS ONLY 2 IT CAN BE 1,2,3,4,5.......35. BECAUSE ZERO IS DIVISIBLE BY ALL.

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;
}