Hi All,

Just want to share my experience solving this problem. I did it like this let the i be the number of bricks available and j be the height of the last step.
S[i][j] = sum(S[i-j][:j]) + (1 if (i-j) < j else 0)

So basically all i am doing is the number of stairs with i bricks and height j is also the same number of stairs with i-j bricks and max height of j - 1(hence the array stops at index j) and one more if i - j bricks are less than height j.

There might be more slick solution avaiable, but this worked for me :)

Edited by author 21.04.2018 01:11

Can you give some tests? The stars coordinates aren't natural numbers?

To find the shortest path from point O to lines AB and CD (in that order) one needs to consider three possibilities, namely projection from O to CD (if it intersects AB); projection on CD of the reflection of O thru AB (if it intersects AB); intersection of AB and CD.

#include <bits/stdc++.h>
using namespace std;

int query(int l, int r, vector<int> bucket, vector<int> v) {
    int n = v.size();
    int bkt_sz = sqrt(n);
    int bkts = bucket.size();

    int lb = l/bkt_sz;
    int rb = r/bkt_sz;
    int lbp = l%bkt_sz;
    int rbp = r%bkt_sz;


    int retval = -1;

    if (lb == rb) {
        for (int i=lb*bkt_sz+lbp; i <= lb*bkt_sz+rbp; i++)
            retval = max(retval, v[i]);
        return retval;
    }

    for (int i=lb+1; i < rb; i++)
        retval = max(retval, bucket[i]);

    for (int i=lb*bkt_sz+lbp; i<n; i++) {
        if (i >= (lb+1)*bkt_sz) break;
        retval = max(retval, v[i]);
    }

    for (int i=rb*bkt_sz; i <= rb*bkt_sz+rbp; i++) {
        retval = max(retval, v[i]);
    }

    return retval;
}

int main() {

    int k;
    cin >> k;

    vector<int> v;

    while (true) {
        int a;
        cin >> a;
        if (a == -1) break;
        v.push_back(a);
    }

    int n = v.size();
    int bkt_sz = sqrt(n);

    vector<int> bucket;

    int count = bkt_sz;
    int max_value = -1;
    for (int i=0; i<n; i++) {
        if (count == 0) {
            count = bkt_sz;
            bucket.push_back(max_value);
            max_value = -1;
        }
        count -= 1;
        max_value = max(max_value, v[i]);
    }

    bucket.push_back(max_value);

    for (int i=0; i+k-1 < n; i++) {
        cout << query(i, i+k-1, bucket, v) << endl;
    }

}

Edited by author 19.04.2018 22:19

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication8
{
    class Program
    {
        static void Main(string[] args)
        {
            int x;
            x = Convert.ToInt32 (Console.ReadLine());
            if ((x > 1 & x <= 4)
            {
                Console.WriteLine("few");
            }
            if (x > 5 & x<= 9)
            {
                Console.WriteLine("several");
            }
            if (x > 10 & x <= 19)
            {
                Console.WriteLine("pack");
            }
            if (x > 20 & x <= 49)
            {
                Console.WriteLine("lots");
            }
            if (x > 50 & x <= 99)
            {
                Console.WriteLine("horde");
            }
            if (x > 100 & x <= 249)
            {
                Console.WriteLine("throng");
            }
            if (x > 250 & x <= 499)
            {
                Console.WriteLine("swarm");
            }
            if (x > 500 & x <= 499)
            {
                Console.WriteLine("zounds");
            }
            if (x > 1000)
            {
                Console.WriteLine("legion");
            }
        }
    }
}

Да что тут не так?

Edited by author 18.04.2018 23:36

Edited by author 18.04.2018 23:37

there is O(n*m) D&C algorithm...  similar with ural 1674 and ural 1596

it is just extend of fermat point, the angle is 2*pi/3 if it is fermat point in this problem

three angles are  acos((c1*c1-c2*c2-c3*c3)/(2*c2*c3)),acos((c2*c2-c1*c1-c3*c3)/(2*c1*c3) and

acos((c3*c3-c1*c1-c2*c2)/(2*c1*c2))

how to get it ,just let two partial derivative to be zero,and square and add two equtation we can get it ,it is easy

Edited by moderator 23.08.2020 01:12

there is a line which isn't token "end" and has no ':' character and there is only one nonempty token..
I use OLE test it must be wrong test...

Unfortunately, std::string in C++ class is very slow...

use N = 100001 instead N = 100000

Solution is a sum( [ sqrt(2*i*R - i^2) ], i = 1,2,...,R), where [ x ] - round to up.

But, I always GOT TL on 17 test).

Consider 2D problem in polar coordinates: intersect disk with given radius R and center in the origin with triangle with vertexes in origin, (R1,0), and (R2,phi). Solve it using quadratic equation... Combine the algebraic sum of solutions to get the final result.

Edited by author 12.04.2018 22:45

Check: SBT; SAT, SABT, SBAT, SACT; the same four with swapped A and C

33
1 2 5 6 4 4 5 2 1 6
2 2 4 3 1 3 3 3 3 1
2 1 4 4 3 2 4 3 1 4
1 1 3 3 0 2 2 2 2 0
2 2 6 1 -1 1 5 6 5 0
2 2 0 3 -1 1 5 6 5 0
2 2 -4 0 -1 1 5 6 5 0
2 2 6 7 -1 1 5 6 5 0
2 2 5 7 -1 1 4 6 5 0
1 1 6 6 2 2 3 3 4 4
1 1 6 6 2 4 3 3 4 2
1 1 2 2 -1 -1 -1 -2 -2 -1
1 1 3 3 4 6 2 2 6 4
1 1 3 3 4 6 1 2 6 4
1 1 3 3 4 6 1 2 7 4
1 1 2 2 1 3 3 3 3 1
1 1 1 5 0 8 1 2 3 2
5 2 3 5 -1 2 4 5 6 3
4 1 5 5 2 3 6 4 5 2
1 1 7 5 2 3 6 4 5 2
1 1 3 3 2 4 2 2 4 2
6 1 6 4 0 5 7 2 6 5
2 2 4 2 2 1 3 6 4 1
4 2 2 2 2 1 3 6 4 1
8 7 1 3 6 1 7 4 0 9
5 1 2 2 2 1 4 1 8 9
9 -1 3 1 0 0 7 0 3 3
1 -1 6 7 0 0 7 0 3 3
0 0 8 0 2 0 4 0 6 0
1 1 4 4 0 3 3 3 3 0
0 0 0 4 2 1 0 2 2 3
0 0 0 4 0 2 2 2 3 2
1 1 5 2 1 2 5 1 0 3

8.000000
3.650282
3.828427
4.576491
5.019765
5.398346
6.324555
10.676619
10.605551
7.071068
7.634414
1.414214
8.993230
8.993230
9.162278
1.414214
5.841619
5.242641
5.064495
7.621233
4.576491
5.576491
4.000000
4.000000
11.709720
4.000000
9.211103
10.633758
8.000000
6.359174
4.000000
4.000000
5.000000

I do not understand why, but my program gives
different result, than sample.

in this picture, i draw a figure with yellow,
i think area of this figure is an answer, i am right ?
download this picture:
http://slil.ru/28091271

Does anyone know the input for test 7?

The time limit for the problem has been corrected from 2.0 sec to 1.0 sec. The new value better reflects the original expectations for accepted solutions back from 2006. Around 40 authors have lost their AC (mostly submitted since 2017).