Lets say there are 5 Steaks and capacity of pan is 4.
Step 1: Cook first 4 one side for 1 minute.
Step 2: Replace 1 one sided cooked steak with completely uncooked (remaining) one and
        cook for next 1 minute.
Step 3: Now the chef has 3 completely cooked and 2 Half cooked. Cook the remaining
        2 half cooked for another one minute.

so 1 minute at each step, hence 3 minutes total minimal time.

However, story doesn't end here :-). Lets take another example

Now, Lets say there are 7 Steaks and capacity of pan is 4.
Step 1: Cook first 4 one side for 1 minute.
Step 2: Replace 3 one sided cooked steak with completely uncooked (remaining) three
        and cook for next 1 minute.
Step 3: Now the chef has 1 completely cooked and 6 Half cooked. Cook 4 steaks from
        half cooked six for another one minute.
Step 4: Last cook final 2 half cooked one for another one minute

So total minimum time take is 4 minute. 1 minute at each step.

Please keep in mind the scenarios where 0 steaks or steaks less then cooking capacity of pan.

Edited by author 08.06.2017 20:19

Edited by author 08.06.2017 20:20

Wrong Anser 7 test

First sample != test 1 :(

var
n:integer;
s:real;
begin
read(n);
s:=n*((n+1 )/2)*(n+2);
write(s);
end.

Hi people.
It looks like there is no one solution which used Python 3.8 x64. I use a linear algorithm (one pass, actually) but I still get TLE21. Are there any options for python or should I just use another language?
Thanks.

answer = min(2*(n-1), 2*m-1);
//don't forget about 32-bit signed  integer overflow

Here any three consecutive numbers means every three consecutive numbers.
For Eg. if the four digit number is abcd then (abc) itself has to be a three digit prime and also (bcd) should also be a three digit prime.
Taking the example for n = 5 let the 5 digit number be abcde then (abc) itself has to be a three digit prime, (bcd) should also be a three digit prime and at last (cde) should also be a three digit prime.

If any of the problem setter reads this then please clarify clearly about this. As I was stuck on this for almost 2 days, by pondering how come the answer for n = 4 is 204 while even bruteforce was giving me 2513.

Edited by author 09.11.2020 11:45

Edited by author 09.11.2020 11:45

I know that the task was rejudged.
I added the condition for new test, where A, B and C collinear: cos(ACB) - 1.0 < eps, where eps = 1e-8, then answer = AB, but I've still get WA 48. Give me a hint, please.
Thanks in advance.

You should find the permutation with the maximum number of inversions. You can use segment tree to calculate inversions for each element, just store sorted leafes in each node.

Didn't know will it be useful for someone and is it on the right path to solve the problem, but I wish to publish this code for SSP solver. To invent good heuristics for MSSP is utmost harder.

using I = short;

template<typename T = I, typename S = I>
struct DDP // dynamic dynamic programming solver for subset sum problem O(n^3 * 2^sqrt(n)) (n is number of input bits)
{
    T terms[2][10001];
    S sums[2][10001];

    template<typename Term, typename Sum>
    std::pair<Term, Sum> solve(const Term termsBeg, const Term termsEnd, const Sum sumsBeg, const Sum sumsEnd)
    {
        static_assert(std::is_same<typename std::iterator_traits<Term>::value_type, T>::value, "!");
        static_assert(std::is_same<typename std::iterator_traits<Sum>::value_type, S>::value, "!");

        auto sumMax = std::max_element(sumsBeg, sumsEnd);

        auto termsSrc = terms[0];
        auto termsDst = terms[1];

        auto sumsSrc = sums[0];
        auto sumsDst = sums[1];

        *termsSrc = {};
        *sumsSrc = {};

        auto sumsSrcEnd = std::next(sumsSrc);
        for (auto t = termsBeg; t != termsEnd; ++t) {
            auto termsSrcBeg = termsSrc;
            auto termsDstBeg = termsDst;

            auto sumsSrcBeg = sumsSrc;
            auto sumsShiftedBeg = sumsSrc;
            auto sumsDstBeg = sumsDst;

            // merge unique
            assert(std::size_t(std::distance(sumsSrcBeg, sumsSrcEnd)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            while (sumsSrcBeg != sumsSrcEnd) {
                if (sumsShiftedBeg == sumsSrcEnd) {
                    break;
                }
                I shiftedSum = *sumsShiftedBeg + *t;
                if (shiftedSum < *sumsSrcBeg) {
                    *sumsDstBeg++ = shiftedSum;
                    ++sumsShiftedBeg;
                    *termsDstBeg++ = *t;
                } else {
                    if (shiftedSum == *sumsSrcBeg) {
                        ++sumsShiftedBeg;
                        assert(*sumsShiftedBeg + *t != *sumsSrcBeg);
                    }
                    *sumsDstBeg++ = *sumsSrcBeg++;
                    *termsDstBeg++ = *termsSrcBeg++;
                }
                assert(std::size_t(std::distance(sumsDst, sumsDstBeg)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            }
            if (sumsShiftedBeg == sumsSrcEnd) {
                sumsSrcEnd = std::copy(sumsSrcBeg, sumsSrcEnd, sumsDstBeg);
                termsDstBeg = std::copy_n(termsSrcBeg, std::distance(sumsDstBeg, sumsSrcEnd), termsDstBeg);
            } else {
                assert(sumsSrcBeg == sumsSrcEnd);
                sumsSrcEnd = std::transform(sumsShiftedBeg, sumsSrcEnd, sumsDstBeg, [t] (S s) { return s + *t; });
                termsDstBeg = std::fill_n(termsDstBeg, std::distance(sumsDstBeg, sumsSrcEnd), *t);
            }

            std::swap(termsSrc, termsDst);
            std::swap(sumsSrc, sumsDst);

            for (auto sum = sumsBeg; sum != sumsEnd; ++sum) {
                sumsSrcBeg = std::lower_bound(sumsSrc, sumsSrcEnd, *sum);
                if ((sumsSrcBeg != sumsSrcEnd) && (*sumsSrcBeg == *sum)) {
                    sumsSrcEnd = sumsSrcBeg;
                    assert((*std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd)) == *t));
                    auto termsDstEnd = termsDst;
                    do {
                        auto term = *std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd));
                        *termsDstEnd++ = term;
                        sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumsSrcEnd - term);
                    } while (sumsSrcEnd != sumsSrc);
                    assert((std::accumulate(termsDst, termsDstEnd, S{}) == *sum));
                    termsDstBeg = termsDst;
                    auto termsSrcEnd = t;
                    assert(*termsSrcEnd == *termsDstBeg);
                    auto termsTail = termsSrcEnd;
                    while (++termsDstBeg != termsDstEnd) {
                        while (*--termsSrcEnd != *termsDstBeg) {
                            *termsTail-- = *termsSrcEnd;
                        }
                    }
                    while (termsBeg != termsSrcEnd) {
                        *termsTail-- = *--termsSrcEnd;
                    }
                    assert(std::distance(termsBeg, termsTail) + 1 == std::distance(termsDst, termsDstEnd));
                    auto term = termsTail;
                    termsDstBeg = termsDst;
                    assert(termsDstBeg != termsDstEnd);
                    do {
                        *termsTail-- = *termsDstBeg++;
                    } while (termsDstBeg != termsDstEnd);
                    assert(termsTail == std::prev(termsBeg));
                    return {term, sum}; // not past the end element for found range but exactly last element
                }
            }
            sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumMax); // crop
        }
        return {termsEnd, sumsEnd};
    }
};

auto x = solve(std::begin(ships), std::end(ships), std::cbegin(rows), std::cend(rows)) if succeeded, it gives rearranged ships range such, that range [std::begin(ships), x.first] is a solution and sum of all ships is *x.second. [std::begin(ships), std::end(ships)) still consists of exactly the same ships. If not succeeded then it return a pair of std::end(ships) and std::cend(rows)

Edited by author 11.06.2020 12:53

dp[n][k] = max{dp[n-1][k] or a[n], dp[n-1][k-1]}
any hints?? thank you.

Edited by author 18.01.2017 13:16

A simple way to solve is to begin with a value x which going to depend whether n % k == 0. and increase it by k until it becomes n. and of course on each step multiply it to your sum which is initially 1.

Are multiple '1' digits possible in the circle ? If yes , then will they produce separate click if they are currently in the window ?

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

http://e-maxx.ru/algo/connected_components
You need to output number of components minus 1.
Tests:

4 4 0
3 4
1 2
3 1
2 4
0


1 0 0
0

6 0 0
5

6 5 1
1 2
1 4
2 5
3 6
4 5
1 2
1

6 5 0
1 2
1 4
2 5
3 6
4 5
1

6 3 4
1 2
2 3
4 5
2

6 4 0
1 3
3 4
4 6
5 6
1

Edited by author 04.11.2020 21:20

 longest palindromic substring is "kazak" itself. What am i missing ?

WHYYYYY
if u have same problem
solution is 3 4 5

The key to solve is that : Driver won't take less than offered, and Petr won't pay more than asked. So if you using a loop for example in each step a will be always min(a + b, c) and c will always be max(c - d, a)

What is test 23?